Variables Artificiales
Las variables artificiales desempeñan el papel de holguras en la primera iteración, en el caso de que el procedimiento deba iniciar con programas lineales de mal comportamiento; para después desecharlas de forma legítima.
El método resuelve la programación lineal en dos fases:
- La fase I trata de determinar una solución básica de inicio, y si se encuentra, se realiza la fase II.
- La fase II resuelve el problema original.
Fase I
El problema se pone en forma de ecuación y se agregan a las restricciones las variables artificiales necesarias para asegurar una solución básica inicial. Luego se determina una solución básica de las ecuaciones resultantes, que minimice la suma de las variables artificiales. Si el valor mínimo de la suma es positivo, el problema no tiene solución factible y termina el proceso. En caso contrario, se prosigue a la fase II.
Fase II
Se usa la solución factible de la fase I como solución básica factible de inicio para el problema original.
La salida de las columnas de las variables artificiales al terminar la fase I solo se hace cuando todas ellas sean no básicas. Sin embargo, es posible que las V.A. sigan siendo básicas pero a nivel cero al final de la fase I. En ese caso, esas variables forman, por necesidad, parte de la solución básica de inicio para la fase II. Se deben modificar los cálculos en la fase II para asegurar que una V.A. nunca se haga positiva durante las iteraciones en esa fase II.
La regla de la fase II indica obligar a la VA a salir de la solución básica en cualquier momento en que su coeficiente de restricción en la columna de pivote sea positivo o negativo.
Análisis de Dualidad y Sensibilidad
Problema Dual
Es una programación lineal definida en forma directa y sistemática a partir del modelo original (o primal) de programación lineal.
- Todas las restricciones son ecuaciones.
- Lado derecho no negativo.
- Todas las variables son no negativas.
El dual del problema dual es en sí mismo el problema primal.
- Si z = v se tiene que:
- Z representa la utilidad monetaria.
- Bi representa la cantidad disponible de unidades del recurso i.
- Si z < v se tiene que: Utilidad < valor de los recursos, la solución primal y dual no son óptimas. La optimalidad solo se alcanza cuando se han explotado los recursos por completo, lo que solo sucede cuando los datos son iguales a los resultados.
Casos Especiales
a. Degeneración
Se produce cuando ocurre un empate en la razón mínima, al menos una variable básica será cero en la siguiente iteración. La condición indica que el modelo tiene al menos una restricción redundante o dicho de otra forma, una combinación lineal. Puede ocurrir que el procedimiento simplex repita una serie de iteraciones sin mejorar el valor objetivo, y nunca terminar los cálculos, pero esto puede ser solo temporalmente.
b. Óptimos Alternativos
Si la función objetivo es paralela a una restricción obligatoria, la FO asumirá el mismo valor óptimo, que se llama óptimos alternativos, en más de un punto de solución. ¿Cómo saber si hay óptimos alternativos en una iteración? Si al encontrar la solución óptima uno o más de los costos reducidos de las variables no básicas tiene valor 0. Esa variable podrá entrar a la solución básica sin cambiar el valor de Z, pero causando un cambio en los valores de las variables. Permite escoger entre muchas soluciones sin que deteriore el valor objetivo.
c. Solución no Acotada
Los valores de las variables pueden aumentar en forma indefinida sin violar alguna restricción, esto implica que el espacio de soluciones es no acotado o infinito. El resultado es que el valor objetivo puede aumentar (si es max.) o disminuir (si es min.) en forma indefinida, dado que no existen vértices en donde se pueda encontrar el óptimo. La no acotación apunta hacia la posibilidad de que el modelo esté mal construido. Si en cualquier iteración todos los coeficientes de restricción de toda variable no básica son cero o negativos, entonces el espacio de soluciones no está acotado en esa dirección. Si además el coeficiente objetivo de esa variable es negativo en caso de max, o positivo en caso de min, entonces también el valor objetivo es no acotado.
d. Solución no Factible
Con restricciones inconsistentes no tienen solución factible. Estos casos no suceden si todas las restricciones son del tipo <=, porque las holguras permiten tener una solución factible.
e. Problema sin Solución Factible en Simplex Dos Fases
Ocurre cuando una de las variables artificiales del problema no sale de la base y tiene valor no nulo. Con esto el problema se torna infactible.
f. Solución Básica Degenerada
Se produce cuando la solución básica está compuesta por una variable con valor cero.
Preguntas de PEP
1. Explique cuál es el aporte a la función objetivo Min Z que realiza una nueva variable a la solución base. Describir en términos de las fórmulas empleadas en clases.
Si Xi es la variable de entrada en la variable básica y Ci es el coeficiente relacionado a esta variable. Obteniendo el min ѳ se tiene:
Z1 = Z0 + ΔZ
ΔZ = min ѳ * Cj
Luego Z1 = Z0 + min ѳ * Cj
2. ¿Qué puede explicar si en el cambio de base, el criterio de factibilidad está incrementado por la condición ais <= 0? Fundamente su respuesta.
Si el criterio de factibilidad está indeterminado por esta condición, quiere decir que el problema es no acotado, ESF se encuentra no acotado. El problema no se puede seguir minimizando o maximizando, dando como resultado que el problema no tiene solución óptima, pero sí solución factible.
4. Establezca 4 posibles condiciones que pueden ocurrir en términos de la factibilidad del primal y del dual cuando se resuelve un problema de programación lineal.
- Z(x) factible y V(π) factible → solución óptima finita, dual y primal.
- Z(x) no factible y V(π) factible → dual no acotado y primal infactible.
- Z(x) factible y V(π) no factible → primal no acotado y dual infactible.
- Z(x) no factible y V(π) no factible → ambos problemas son infactibles.
5. Explique breve cual es la distinción entre sistema y proceso.
Sistema es un objeto que contiene componentes que interactúan entre sí y con el entorno mediante flujo de información y de recursos.
Un proceso, por otro lado, es una transformación que ocurre producto de un conjunto de actividades vinculadas entre sí enfocadas a obtener un producto final. Por tanto, solo es una parte de un sistema.
6. Clasificar y describir los tipos de modelos basados según su función.
a. Modelo Predictivo
Este tipo de modelos nos informan del comportamiento de la variable en un futuro, es decir, lo que debería ser. A este tipo de modelos corresponden aquellos basados en técnicas estadísticas y/o econométricas, es decir, modelos de previsión.
b. Modelo Evaluativo
Permite medir las diferentes alternativas y así poder comparar los resultados de ellas. Este tipo de modelos se corresponden con los denominados árboles de decisión.
c. Modelo de Optimización
Se trata de modelos que tratan de identificar un óptimo (por lo general, el óptimo global) del problema, es decir, buscan la mejor de las alternativas posibles. Estos métodos son los que están basados en las técnicas de programación matemática.
7. ¿Qué sucede si en la solución factible de la segunda fase (método de 2 fases) los coeficientes de la columna pivot son negativos?
El problema posee solución no acotada en la dirección de la variable para la cual los coeficientes de la columna pivot son negativos. Luego min z = infinito. El ESF no está acotado en una dirección.
8. Defina los límites o condiciones de borde de las funciones Min Z y Max V, en términos de la factibilidad del primal y del dual.
- En el óptimo se cumple que Min Z = Máx V.
- Si Mín Z no está acotado, entonces el dual es infactible.
9. Defina claramente el concepto epistemología de sistemas.
La epistemología de sistemas se refiere a la distancia de la Teoría General de Sistemas con respecto al positivismo o empirismo lógico. Según la TGS, la percepción es una reflexión de cosas reales o el conocimiento una aproximación a la verdad o la realidad, es una interacción entre conocedor y conocido, dependiente de múltiples factores de naturaleza biológica, psicológica, cultural, lingüística, etc.
10. En una formulación de programación lineal ¿Qué representan las variables de holguras y las variables duales asociadas? Tener presente que el modelo lineal representa una situación de operaciones mina real que usted está modelando.
Las variables de holgura representan la diferencia entre los recursos disponibles y los efectivamente utilizados. En el caso de una operación mina, por ejemplo, la capacidad de chancado con respecto a la cantidad de toneladas que efectivamente se chancan.
Las variables duales representan el valor marginal por unidad de recurso adicional. En el ejemplo anterior, por ejemplo, sería hasta cuánto estaríamos dispuestos a pagar por chancar una tonelada más de mineral.
11. ¿Cuál es la diferencia de la toma de decisiones determinísticas versus la toma de decisión probabilística en términos de resultados?
La toma de decisiones determinística se basa en modelos determinísticos, vale decir, en que los datos con los que se crea el modelo se conocen con absoluta certeza y por tanto el resultado del modelo entrega información puntual para la toma de decisiones. Por otro lado, la toma de decisiones probabilística se hace a partir de modelos estocásticos, vale decir, aquellos en que los datos con que se crean los modelos son probabilidades, incertidumbres o turbulencias y que generan resultados en la misma instancia, por tanto, la toma de decisiones se hace a partir de probabilidades de ocurrencia.
12. A su entender ¿Cuál es la clave del método simplex en la determinación de la solución óptima?
El método simplex busca el camino más corto para encontrar la solución óptima, por lo que es más eficiente. Al iterar recorre solo los vértices del espacio solución factible, por lo tanto, no recorre cada punto del espacio, solo los más probables de ser los óptimos hasta llegar al óptimo, siguiendo el camino más corto con el fin de realizar menos iteraciones.
13. Defina brevemente la diferencia entre las variables de holgura y las variables artificiales.
Las variables de holgura transforman una inecuación en ecuación, son mayores a cero. Las variables artificiales solo tienen como fin formar la matriz canónica y de esta forma obtener una SBF.
14. En términos gráficos exprese un espacio de soluciones factible no convexo.
Es en el cual el vector que une a 2 puntos que son soluciones de un ESF, no se encuentra dentro del ESF (como se ve en la figura):
15. Explique brevemente el criterio de entrada y de salida del método simplex, si se tiene una función minimizando.
El criterio de entrada cuando se está minimizando elige, de las variables no básicas con costos reducidos negativos, la que presente el costo reducido más negativo. Mientras que para la salida considera la variable básica que presente la mínima razón, con.
16. Las variables de holgura, porque deben ser mayores a cero ¿Qué sucede si estas son negativas?
Si son negativas no se puede generar la matriz canónica por lo que no se puede iniciar el proceso, ya que no se dispone de una solución básica inicial, en tal caso se necesita dar una variable artificial.
17. ¿Cuál es el propósito de la investigación de operación?
La capacidad de comunicar efectivamente los resultados. Y evaluar el rendimiento de un sistema con objeto de mejorarlo.
18. Explique en qué condiciones ocurre la Redundancia Geométrica de un problema de programación lineal.
Cuando se tienen restricciones que son combinaciones lineales de las otras restricciones (que el número de restricciones sea mayor que el número de variables a determinar) y cuando existe degeneración.
19. En términos de una solución factible para un problema de PL, que situaciones están presentes, si en esta solución existen variables de holgura y/o artificiales. Fundamente.
Solución no acotada: v.a. quedan en la base y con b ≠ 0.
Solución inicial factible: min w = 0.
Solución degenerada: si ѳ = 0.
20. Describa las posibles condiciones que pueden ocurrir, en términos de la factibilidad, cuando se resuelve un PPL.
- Solución no acotada: aij < 0.
- Solución degenerada: empate para obtener el min ѳ = 0.
21. ¿Qué estado de solución ocurre en el método simplex, si condición del criterio de factibilidad esta indeterminado por la condición (bi/ais) ≤ 0?
Pueden darse dos situaciones:
- Que sea infactible en el caso que bi sea negativo, o bien;
- Que sea no acotada, si ais < 0.
22. Establezca las condiciones de borde de las funciones objetivos del problema primal y dual.
min Z(x) = max V(π) solución óptima básica.
Si el primal Z(x) tiende a -∞ → dual v(π) infactible.
Si el dual v(π) tiende a +∞ → el primal Z(x) infactible.
23. ¿Cuál es la tasa de incremento/disminución que produce la nueva variable que entra a la solución base factible del PL?
ΔJ =
24. ¿Cuál es el número posible de soluciones factibles de un problema de PL?
Siendo n el número de variables y m el número de restricciones. ( ).
25. Al emplear Simplex-Dual ¿Qué puede explicar si en el cambio de base los ais >= 0? Explique.
No puede entrar una variable o las variables básicas, es decir, el espacio no es acotado en esa dirección, no hay solución óptima.
26. Explique ¿Cuál es la condición presente si en la solución óptima de la Fase I del método simplex, queda una o más variables artificiales en la base? Fundamente.
Esto depende del valor que tomen las variables artificiales.
- Si b = 0 → la solución básica factible es degenerada.
- Si b ≠ 0 → no existe solución básica inicial para el problema inicial.
27. ¿Cuáles son los fundamentos para la toma de decisiones?
El conocimiento, la lógica y la ciencia.