Programación Lineal

¿Cuál de las siguientes características NO corresponde a la representación en forma estandar?

• La función objetivo se debe maximizar

• Todas las restricciones deben ser únicamente de mayor o igual

• Todas las variables deben tener la restricción de no negatividad

• Todas las restricciones y la función objetivo deben ser ecuaciones lineales

¿Qué es la forma holgura en programación lineal?

• Expresión del problema con múltiples funciones objetivo

• Expresión del problema con función objetivo a maximizar, restricciones de igualdad y variables no negativas

• Expresión del problema como un problema equivalente en el que se agregan variables Slack que permiten calcular la solución básica

• Expresión del problema con función objetivo a maximizar, restricciones de mayor o igual y variables no negativas

• Expresión del problema con función objetivo a minimizar, restricciones de mayor o igual y variables positivas

¿Qué implica que un problema de programación es ilimitado?

• Que tiene infinitas soluciones óptimas

• Que tiene infinitas soluciones factibles

• Que no tiene solución optima por crecer de forma infinita

• Que no tiene restricciones de no negatividad sus variables de decisión

Si analizamos gráficamente el problema de programación lineal con solución expresado en forma de estandar. ¿Cual de las siguientes afirmaciones NO es correcta?

• Conforma un espacio n dimensional (n=número de variables)

• El área con las soluciones factibles del problema conforma un politopo convexo

• La función objetivo corresponde a un hiperplano que intersecta al politopo

• Una solución óptima estará ubicada siempre en un punto extremo del politopo

• Todas las opciones son correctas

Dos problemas de maximización en forma estandar son equivalentes si

• Comparten el espacio de soluciones entre sí

• Las restricciones del problema son iguales

• Para toda solucion factible del primero problema existe otra en el otro problema con el mismo valor objetivo (y viceversa)

• Ninguna de las anteriores

• Todas las anteriores

¿Cuál de las siguientes corresponde a la definición o nombre alternativo de las variable básicas?

• variables que se encuentran multiplicadas por coeficientes en las restricciones y función objetivo en la expresión de holgura

• variables de decisión del problema

• variables de holgura del problema

• variables cuya valor están previamente establecidos por las restricciones del problema

• variables en el primer término de la igualdad en las restricciones expresadas en forma de holgura

¿Qué significa que una variable en programación lineal esté ajustada?

• variable básica que no se puede modificar en su valor

• variable básica cuyo valor en la ecuación es la mayor posible

• variable libre cuyo valor en la ecuación de restricción es cero

• variable de decisión del problema cuyo valor ya se a establecido para el calculo de la solución óptima

El algoritmo Simplex (marque lo que NO corresponde)

• expresa el problema en forma de holgura

• Finaliza cuando todas las variables libres están acompañadas por coeficientes negativos en la función objetivo

• En cada iteración se ubica en un punto extremo diferente del politopo

• En cada iteración ajusta una variable libre

• Todas son correctas

La complejidad temporal del algoritmo Simplex corresponde a ...
(m=número de restricciones, n=número de variables)

• O(nm)

• O(n+m)

• O(n^2 * (n+m))

• O((\binom{n+m}{n})*n*m)

¿Cuál de los siguientes NO corresponde a un algoritmo que resuelve programación lineal?

• Simplex

• método elipsoide

• método de los puntos interiores

• Duplex

• Todos corresponden