Métodos simplex, sensibilidad, dual y posoptimalidad - Taha (3 y 4)
Método Dual
Algoritmo:
Asigne una variable dual por cada restricción primal.
Construya una restricción dual por cada variable primal
Los coeficientes de restricción (columna) y el coeficiente objetivo de la variable
primal j-ésima definen respectivamente los lados izquierdo y derecho de la restricción
dual j-ésima.
El problema dual se define a partir del modelo de PL primal (u original).
Los dos problemas están estrechamente relacionados en el sentido de que la solución óptima de uno proporciona automáticamente la solución óptima al otro.
Cambios que afectan la optimalidad
Cambios en los coeficientes de la función objetivo
Si no la satisface, se utiliza el simplex
primal para recuperar la optimalidad.
Adición de una nueva restricción
Agregar una nueva restricción nunca puede
mejorar el valor objetivo óptimo actual
Si la nueva restricción es redundante, no
afectará la solución actual.
Además, la solución actual no satisface la nueva restricción,
y debe determinarse una nueva solución mediante el método simplex dual.
El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.
Para convertir una desigualdad ecuación se agrega una variable de holgura al lado izquierdo de la restricción.
Lado derecho de la ecuación sea no negativo. Si no, multiplicando ambos lados de la ecuación por -1.
Método gráfico
Usa la función objetivo para determinar
el punto de esquina óptimo
Método algebraico
Determina las solucione básicas factibles
de la ecuacione
las soluciones básicas corresponden a los puntos de esquina en el espacio de soluciones gráficas. Se determinan igualando n 2 m variables a cero y resolviendo las m ecuaciones
para las m variables restantes, siempre que la solución resultante es única.
En problemas de minimización,
la condición de optimalidad requiere seleccionar la variable de entrada como la
variable no básica con el coeficiente objetivo más positivo en la ecuación objetivo, la regla exacta opuesta del caso de maximización. Esto obedece a que máx z equivale a mín (2z). En cuanto a la condición de factibilidad para seleccionar la variable de salida, la regla no cambia.
Manera 1
Valor óptimo de
la variable dual yi
Coeficiente z primal óptimo de la variable inicial xi
+
Coeficiente objetivo original de xi
Manera 2
Valores óptimos de
las variables duales
Vector fila de los Inversa coeficientes objetivo originales de las X primal
variables básicas primales óptimas óptima