EL MÉTODO SIMPLEX
INTRODUCCIÓN
El Simplex es un método iterativo para resolver un programa lineal en su forma
estándar. Cuando se aplica a problemas no degenerados se mueve de una solución
básica factible (punto extremo) a otra adyacente.
El simplex un ejemplo del método del punto factible, donde cada solución estimada
es una solución básica. En cada iteración el método prueba si la solución actual es
óptima. Si no lo es, el método selecciona una dirección factible en la cual la función
objetivo mejora y se mueve en esta dirección a una solución adyacente básica
factible. Este proceso se repite.
Min z= -x1-2x2 El PL en su forma estándar:
s.a.: -2x1+x2 ≤ 2` Min z= -x1-2x2
-x1+x2 ≤ 7 s.a.: -2x1+x2+x3 =2
x1 ≤3 -x1+2x2 +x4 =7
x1, x2 ≥ 0 x1 +x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Como es usual la función objetivo es z=cTx y las restricciones por Ax=b
con x≥0
En este problema cada restricción tiene una variable
de holgura, esto hace fácil encontrar una SBF,
xB=(x3,x4,x5)T y xN=(x1,x2)T
Con lo que B=I 🡪 IxB=xB=b
Luego, la solución inicial básica factible es:
(x1 x2 x3 x4 x5)T=(0 0 2 7 3)T que corresponde al (0,0)
Probamos si este punto es óptimo, determinando
si existe alguna dirección factible descendente.
Expresando las v. básicas en función de las v. no
básicas:
X3=2+2x1-x2
X4=7+x1-2x2
X5=3-x1
Todos los otros puntos factibles pueden ser encontrados
incrementando los actuales valores de las v. no básicas y asegurando la
no negatividad de todas las variables, si esto es posible la solución
actual no es la óptima.
Por otro lado nuestro objetivo es minimizar z=-x1-2x2, que con la SBF
actual es igual a 0, de ser posible incrementar x1 o x2, z mejorará.
El simplex, se mueve de una base a otra adyacente, por lo que
corresponde el incremento de x1 o x2 no de ambos, como el
coeficiente de x2 es mas negativo que el de x1, x2 es el preferido.
Pero x2 no puede aumentar indefinidamente: Con x1=0,
X3=2-x2 La no negatividad implica que x2≤2 o que x2≤7/2,
X4=7-2x2 evidentemente
X5=3 x2=2 también cumple x2≤7/2.
T
Luego con x1=0, x2=2 se obtiene la SBF x =(0 2 0 3 3), en
este punto x3 se vuelve 0 y sale de la base y x2 entra a la
base. Ahora z=-4.
La iteración se completa expresando las xB y z en términos de XN
(xB=(x2 x4 x5)T xN=(x1 x3)T). De las restricciones,
X2=2+2X1-X3
x4=7+x1-2x2 =7+x1-2(2+2x1-x3)=7+x1-4-4x1+2x3=3-3x1+2x3
x5=3-x1
También z=-x1-2(2+2x1-x3)=-4-5x1+2x3, que muestra x=(0 2 0 3 3)T; z=-4
Iniciamos una nueva iteración ya que hay coeficiente negativo en z
Sólo nos interesa que ingrese a la base x1 (tiene coeficiente negativo), x3=0,
luego:
x2=2+2x1 🡪 no hay riesgo de negatividad
x4=3-3x1 🡪 x1≤ 1 🡪 x1=1, x4=0, x2=4, x3=0, x5=2 🡪 x=(1 4 0 0 2)T z=-9
x5=3-x1 🡪 x1≤ 3 CONTINUA hasta que todos los coeficientes de Z son
no negativos
•
•
•
•
•
•
•
•
•
•
MÉTODO SIMPLEX TABULAR
Facilita el cálculo “a mano”
Para el ejemplo:
El PL en su forma estándar:
Min z= -x1-2x2
s.a.: -2x1+x2+x3 =2
-x1+2x2 +x4 =7
x1 +x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Y considerando la base xB={x3, x4, x5}, la tabla inicial es:
base x1 x2 x3 x4 x5 rhs
-z -1 -2 0 0 0 0
x3 -2 1 1 0 0 2
x4 -1 2 0 1 0 7
x5 1 0 0 0 1 3
El programa lineal original corresponde a la tabla:
base xB xN rhs
-z c BT c NT 0
xB B N b
Y la tabla para el problema en la base actual es:
Costos reducidos
base xB xN rhs
-z 0 cNT-cBTB-1N -cBTB-1b
xB I B-1N B-1b
El Simplex comienza con la prueba de optimalidad, para las variables
básicas los costos reducidos son cero. En el ejemplo, los CR de las v.
No básicas son negativas por lo que la base actual no es óptima. Por
Tener x2 el CR mas grande en magnitud, se selecciona x2 como v.
entrante.
Se determina la v. saliente a través del ratio test, que se realiza
dividiendo los valores del RHS y los valores de la columna de la v.
entrante. El menor valor del cociente corresponde a la v. saliente.
base x1 x2 x3 x4 x5 rhs ratio test
-z -1 -2 0 0 0 0
x3 -2 1 1 0 0 2 2=2/1
x4 -1 2 0 1 0 7 3,5=7/2
x5 1 0 0 0 1 3 x
El paso final es transformar la tabla para expresar los coeficientes en
términos de la nueva base. Aplicando operaciones elementales de fila,
•
•
base inversa rhs
-z -yT
B-1
•
Si las restricciones del problema original son factibles, entonces el
óptimo de la fase 1 es z*=0, si hay infactibilidad z*>0.
Min z=2x1+3x2 Min z= 2x1+3x2
s.a.: 3x1+2x2=14 s.a.: 3x1+2x2 =14
2x1-4x2 ≥ 2 2x1- 4x2 – x3 = 2
4x1+3x2 ≤ 19 4x1+3x2 + x4 = 19
x1,x2,x3,x4≥0
x1,x2≥0
Min z= 2x1+3x2
s.a.: 3x1+2x2 + a1 =14
2x1- 4x2 – x3 +a2 = 2
4x1+3x2 + x4 = 19
x1,x2,x3,x4,a1,a2≥0
En la fase 1: Min z’=a1+a2
La tabla del simplex fase 1 es:
base x1 x2 x3 x4 a1 a2 rhs
-z’ 0 0 0 0 1 1 0 Costos reducidos
de a1 y a2 deben
a1 3 2 0 0 1 0 14 ser iguales a cero.
a2 2 -4 -1 0 0 1 2
x4 4 3 0 1 0 0 19
base x1 x2 x3 x4 a1 a2 rhs
-z’ -5 2 1 0 0 0 -16
a1 3 2 0 0 1 0 14 La solución de la fase 1
sólo da la solución
a2 2 -4 -1 0 0 1 2 inicial de la fase 2
x4 4 3 0 1 0 0 19
En la fase 1 cuando resulta que una variable artificial es la saliente, esta
es removida del problema-
FASE 2:
Se tiene como función objetivo z y solución inicial es la solución final de
la fase 1, transformar para que los costos reducidos de las variables
básicas sean iguales a cero.
•
base x1 x2 x3 x4 a1 a2 rhs
Costos reducidos
-z’ 2 3 0 0 M M 0
de a1 y a2 deben
a1 3 2 0 0 1 0 14 ser iguales a cero.
a2 2 -4 -1 0 0 1 2
x4 4 3 0 1 0 0 19
base x1 x2 x3 x4 a1 a2 rhs
-z’ -5M+2 2M+3 M 0 0 0 -16M
a1 3 2 0 0 1 0 14
a2 2 -4 -1 0 0 1 2
x4 4 3 0 1 0 0 19
Se desea maximizar los ingresos por la venta de 3 tipos de automóviles.
El total de vehículos que se puede ofertar es 25, se exige que el número
de automóviles del tipo 1 a vender sea por lo menos el doble que el del
tipo 3. Los precios de venta para cada uno de los tipos de automóvil
son de 25, 30 y 50 miles de dólares respectivamente.
xi: Nº de automóviles del tipo i a vender. i=1,2,3
Max z=25x1+30x2+50x3 Min z’=-25x1-30x2-50x3
Sujeto a: x1+x2+x3 ≤ 25 Sujeto a: x1+x2+x3 +x4 = 25
x1- 2x3 ≥ 0 x1- 2x3 -x5 = 0
x1,x2,x3,x4, x5 ≥ 0
x1,x2,x3≥ 0
Solución óptima: x1=12, x2=6, x3=5, x4= 2 , x5=2 z’ opti=-730
EL PROBLEMA DEGENERADO
Min z=-x1-x2
s.a.:
x1<=2
x1+x2<=2
x1,x2>=0