Método
Simplex Dual
Miguel Angel Traslaviña Rodriguez - 160004841
Daniel Felipe Villegas Reyes - 160004844
Simplex Dual
El método Simplex es un algoritmo iterativo que, iniciando en una solución básica
factible pero no óptima, genera soluciones básicas factibles mejores tras cada
iteración, manteniendo la factibilidad, mientras se busca la optimalidad hasta
encontrar la solución óptima (en el caso de que esta exista).
Como contraparte del Simplex tradicional, el método Simplex dual comienza generando
una solución básica óptima, pero no factible, y mantiene la inmejorabilidad mientras
busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.
En que casos se aplica Simplex
Dual
Problemas con restricciones de tipo "≥" (mayor o igual) o “=” (igual): Cuando el problema de
maximización tiene restricciones de tipo "≥" o “=”, se dificulta la aplicación directa del
método Simplex Tradicional. El método dual es más adecuado en estos casos, ya que
maneja este tipo de restricciones con más eficiencia.
Problemas grandes: Cuando el número de variables y restricciones es excesivamente
grande volviendose computacionalmente costoso.
Problemas donde no es fácil encontrar una solución básica factible inicial en el problema original:
En lugar de trabajar directamente con el problema original, transformar las restricciones
originales para construir un problema dual, que suele ser más fácil de resolver.
Ejercicio 1: Maximización
Partiendo de la forma canónica de la programación lineal del planteamiento del ejercicio, tenemos:
Max Z = 50 x₁ +120x₂
sujeto a.
100x₁ + 200 x₂ ⩾ 10000
10x₁ + 30x₂ ⩽ 1200
x₁ + x₂ ⩽ 110
x₁, x₂ ⩾ 0
El primer paso consiste en reescribir las restricciones (sin contar la no negatividad) y la función objetivo de la
forma canónica a forma estándar, adicionando únicamente variables de holgura (tal cual el método simplex
estándar)
100x₁ + 200 x₂ - s₁ = 10000
10x₁ + 30x₂ + s₂ = 1200
x₁ + x₂ + s₃ = 110
Z - 50 x₁ - 120x₂ =0
Se prosigue haciendo que todas las variables de holgura tengan su respectivo coeficiente positivo
multiplicando por (-1) las ecuaciones correspondientes
-100x₁ - 200 x₂ + s₁ = -10000
10x₁ + 30x₂ + s₂ = 1200
x₁ + x₂ + s₃ = 110
Z - 50 x₁ - 120x₂ =0
Ya a partir de este nuevo modelo de programación lineal, se construye el primer tablero Simplex
x₁ x₂ s₁ s₂ s₃ CR
s₁ -100 -200 1 0 0 -10000
s₂ 10 30 0 1 0 1200
s₃ 1 1 0 0 1 110
Z -50 -120 0 0 0 0
Se eligen la fila y columna pivote siguiendo las reglas detalladas en el lateral
x₁ x₂ s₁ s₂ s₃ CR
s₁ -100 -200 1 0 0 -10000
Fila Pivot: Mayor negativo de CR
s₂ 10 30 0 1 0 1200
Menor valor al hacer la división de Z
s₃ 1 1 0 0 1 110 Columna
entre la fila pivote (solo si ambos
Pivot: valores son negativos)
Z -50 -120 0 0 0 0
Z/fila-pivote 0.5 0.6
Se elabora un nuevo tablero Simplex, aplicando operaciones elementales a cada una de las filas con el método de Gauss
- Jordan de tal forma que el elemento pivote se haga 1, y los demás elementos de la columna pivote se hagan cero
Ya que no hay valores negativos en CR, se dice que la
x₁ x₂ s₁ s₂ s₃ CR
tabla actual es una solución factible.
x₁ 1 2 -1/100 0 0 100 (-1/100)f₁ → f₁
Pero dado que para obtener la solución optimizada
s₂ 0 10 1/10 1 0 200 (-10)f₁ + f₂ → f₂
se requiere que la fila Z sea positiva, el ejercicio se
s₃ 0 -1 1/100 0 1 10 (-1)f₁ + f₃ → f₃ continúa realizando el método Simplex estándar de
Z 0 -20 -1/2 0 0 5000 (50)f₁ + f₄ → f₄ selección de elemento pivote
Ejercicio 2: Minimización
Min Z = 2500x + 2000y
s.a.
6x + 2y ≥ 100
5x + 3y = 150
x,y ≥ 0
Se escribe en la forma estándar, teniendo en cuenta que
A. Las restricciones de tipo ‘ ≥ ’ deben ser multiplicadas por -1 permitiendo así que su holgura sea no
negativa (no se tienen en cuenta la restricción de no negatividad). Al agregar las
B. Las restricciones de tipo ‘ = ’ deben ser separadas en dos igualdades (una con ‘ ≥ ’ y la otra con ‘ ≤ ’ ) y holguras se
repetir con el resultado lo del inciso A cambia a
igualdad
6x + 2y ≥ 100 → - 6x - 2y ≤ -100 - 6x - 2y + s₁ = -100
5x + 3y + s₂ = 150
5x + 3y ≤ 150
5x + 3y = 150 → → 5x + 3y ≤ 150 -5x - 3y + s₃ = -150
5x + 3y ≥ 150 -5x - 3y ≤ -150
Z - 2500x - 2000y = 0
Se aplica el inciso A.
Se escribe de forma matricial y se halla la fila pivote y posteriormente la columna pivote
X Y s₁ s₂ s₃ CR
s₁ -6 -2 1 0 0 -100
Fila Pivot: Mayor negativo de CR
s₂ -5 -3 0 1 0 -150
Menor valor al hacer la división de Z entre
s₃ 5 3 0 0 1 150 la fila pivote (solo si ambos valores son
Z -2500 -2000 0 0 0 0 Columna negativos) los valores que den cero o
Pivot: indeterminación se ignoran
Z/fila-pivote 500 666.6666667
Se procede a realizar operaciones elementales entre filas con el método Gauss - Jordan
X Y s₁ s₂ s₃ CR
s₁ 0 8/5 1 -6/5 0 80 6 f₂ + f₁ → f₁
X 1 3/5 0 -1/5 0 30 -⅕ f₂ → f₂
s₃ 0 0 0 1 1 0 -5 f₂ + f₃ → f₃
Z 0 -500 0 -500 0 75000
Se termina el ejercicio porque no hay
más negativos en CR, además al ser Solución Óptima
minimización, el hecho de que en Z
X = 30
queden las variables en negativo no
indica ningún problema, a diferencia de Z = 75000
maximización
Ejercicios:
Max Z = 30x + 48y Min Z = 3x + 2y
s.a. s.a.
5x + 12y ≥ 40 2x + y ≥ 4
10x + 6y ≤ 60 x + 2y ≥ 6
x,y ≥ 0 x,y ≥ 0