Catégories : Tous - variables - dual - programación - simplex

par Fermín Enrique Estrada Sánchez Il y a 6 années

716

Métodos simplex, sensibilidad, dual y posoptimalidad - Taha (3 y 4)

El Método Simplex es una herramienta eficaz para resolver problemas de programación lineal complejos, sin limitación en el número de variables, a diferencia del método gráfico. Para convertir desigualdades en ecuaciones, se añade una variable de holgura.

Métodos simplex, sensibilidad, dual y posoptimalidad - Taha (3 y 4)

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

Manera 1

Valor óptimo de la variable dual yi

Coeficiente z primal óptimo de la variable inicial xi + Coeficiente objetivo original de xi

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.

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.

Método gráfico

Usa la función objetivo para determinar el punto de esquina óptimo

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.

Lado derecho de la ecuación sea no negativo. Si no, multiplicando ambos lados de la ecuación por -1.

Para convertir una desigualdad ecuación se agrega una variable de holgura al lado izquierdo de la restricción.

Métodos simplex, sensibilidad, dual y posoptimalidad - Taha (3 y 4)

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.

Adición de una nueva restricción
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.

Agregar una nueva restricción nunca puede mejorar el valor objetivo óptimo actual
Cambios que afectan la optimalidad
Si no la satisface, se utiliza el simplex primal para recuperar la optimalidad.
Cambios en los coeficientes de la función objetivo

Método Dual

Algoritmo:
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.
Construya una restricción dual por cada variable primal
Asigne una variable dual por cada restricción primal.