1. No category

Método Simplex Revisado con Cotas
Daniel Severin
Esta vez, vamos a resolver un ejercicio cuyo enunciado es:
Resolver el siguiente problema mediante el método simplex revisado con cotas.
máx z = x1 − x2
s/a
x1 − 2x2 ≤ −2
x1 + x2 ≤ 10
x1 ≤ 4
2 ≤ x2 ≤ 5
Preliminares. Lo primero que hacemos es convertir el problema a su
forma standard:
máx z = x1 − x2
s/a
x1 − 2x2 + x3 = −2
x1 + x2 + x4 = 10
x1 ≤ 4
2 ≤ x2 ≤ 5
0 ≤ x3
0 ≤ x4
Matricialmente,
máx z = c.x
s/a
A.x = b
l≤x≤u
1
donde,


x
1
 x2 
1 −2 1 0
−2

A=
,b =
,x = 
 x3 
1 1 0 1
10
x4
y c = (1, −1, 0, 0). Las cotas inferiores y superiores son l = (−∞, 2, 0, 0) y
u = (4, 5, +∞, +∞) respectivamente.
Búsqueda primer solución factible. El método es el siguiente: Se
propone una solución básica y, si es factible, se comienza a trabajar con ella
como primer solución factible. Si, en cambio, resulta no factible, se resuelve
primero el problema de inicialización.
A primera vista, la función objetivo muestra que conviene hacer crecer x1
tanto como se pueda, y conviene hacer decrecer x2 también. Ası́ que proponemos como solución básica, la que envı́a x1 a su cota superior y x2 a su cota
inferior. Es decir,
x1 = 4, x2 = 2, x3 = −2, x4 = 4.
Sin embargo, es no factible pues x3 se vuelve negativa. Entonces, vamos a
resolver un problema auxiliar. Cuando a cada restricción le corresponde una
slack, un método posible es agregar tantas variables artificiales como restricciones se violen (en nuestro ejercicio se viola la primera restricción) y tomar
como variables básicas a las artificiales más las slacks cuyas restricciones asociadas no se violan (en nuestro ejercicio, x4 ).
máx v = x5
s/a
x1 − 2x2 + x3 + x5 = −2
x1 + x2 + x4 = 10
x1 ≤ 4
2 ≤ x2 ≤ 5
0 ≤ x3
0 ≤ x4
x5 ≤ 0
La variable artificial agregada es x5 . La idea es que x5 alcance su cota superior
que vale cero. Las matrices y vectores que conforman el problema auxiliar
2
son

A=
1 −2 1 0 1
1 1 0 1 0
,b =
−2
10


,x = 


x1
x2
x3
x4
x5






y c = (0, 0, 0, 0, 1). Las cotas inferiores y superiores son l = (−∞, 2, 0, 0, −∞)
y u = (4, 5, +∞, +∞, 0) respectivamente. Ahora, la primer base factible es
B = [a5 , a4 ] = I = B −1 , N1 = [a2 , a3 ], N2 = [a1 ]
(recordar que x1 tomaba su cota superior y x2 su cota inferior, y gracias a la
adjunción de la variable artificial, x3 puede tomar su cota inferior). En todo lo
que sigue, N1 corresponderán a las columnas de la no-base correspondientes
a las variables que toman su cota inferior. Y N2 corresponderán a las columnas de la no-base correspondientes a las variables que toman su cota superior.
Test de optimalidad. Recordemos que
v = cB .B −1 .b + (cN1 − cB .B −1 .N1 ).xN1 + (cN2 − cB .B −1 .N2 ).xN2
Debemos investigar los coeficientes de la función objetivo. Llamemos w al
vector que resulta del producto cB .B −1 . Utilizando la primer solución factible hallada, w = (1, 0).I = (1, 0).
Lo siguiente es evaluar los coeficientes de la función objetivo hasta encontrar
una variable no básica que, al modificarse, pueda mejorar el objetivo:
c1 − w.a1 = −1 < 0, por lo tanto entra x1 a la base y dejamos de buscar
en los coeficientes de la función objetivo.
NOTA: Las variables que estén en sus cotas superiores deben tener coeficientes negativos para entrar a la base. Las variables que estén en sus cotas
inferiores deben tener coeficientes positivos para entrar a la base.
Test de factibilidad. Ahora tenemos que hallar la variable saliente que
más restricción impone, cuando x1 comienza a decrecer. Supongamos que
x1 → x1 − ∆, con ∆ ≥ 0. Entonces, el cambio que efectúan las variables
básicas es
xB → xB + B −1 .a1 .∆.
3
Es decir, si x1 → 4 − ∆ entonces
x5 → x5 + 1.∆ = −2 + ∆,
x4 → x4 + 1.∆ = 4 + ∆.
NOTA: Dividiremos este test en 4 partes. En la primer parte estudiaremos
xB ≥ lB y asignaremos γ1 al ∆ más restringido que podamos obtener. En la
segunda parte estudiaremos xB ≤ uB y asignaremos γ2 al ∆ más restringido
que podamos obtener. En la tercer parte estudiaremos x1 ≥ l1 y asignaremos γ3 al ∆ más restringido que podamos obtener. Finalmente, calcularemos
γ = mı́n(γ1 , γ2 , γ3 ) y, si γ = +∞ el problema es no acotado. Por otra parte,
si γ = γ3 entonces x1 no entra a la base, saltando de su cota superior a su
cota inferior simplemente. En el resto de los casos, x1 entrará a la base con
valor x1 − γ y existirá una variable básica que saldrá (justamente, aquella
que imponga la mayor restricción).
PRIMERA PARTE. Las restricciones son x5 = −2 + ∆ ≥ −∞, y x4 =
4 + ∆ ≥ 0. Como ninguna acota a ∆, γ1 = +∞.
SEGUNDA PARTE. Las restricciones son x5 = −2 + ∆ ≤ 0, y x4 = 4 + ∆ ≤
+∞. Por lo tanto, x5 es una posible candidata a salir de la base y γ2 = 2.
TERCERA PARTE. La restricción es x1 = 4 − ∆ ≥ −∞. Nuevamente,
γ3 = +∞.
PARTE FINAL. Tenemos a γ = mı́n(+∞, 2, +∞) = 2. En consecuencia,
x5 resulta ser la variable saliente. Cabe aclarar que x5 va a pasar a su cota
superior.
Actualización. Para poder pasar a la próxima iteración (la cual comienza con el test de optimalidad) debemos actualizar la base:
1 0
−1
, N1 = [a2 , a3 ], N2 = [a5 ]
B = [a1 , a4 ], B =
−1 1
Algunas observaciones son:
Dado que x5 pasa a valer su cota superior, el problema auxiliar alcanza
su óptimo. Además, éste óptimo es cero lo que quiere decir que la
solución básica que tenemos es factible en el problema original. De este
modo, en la siguiente iteración ya podemos volver al problema original.
4
¿Sirve de algo mantener x5 en el problema original? NO! Es una variable
que no aporta nada; su valor es cero. Podemos quitarla de la no-base.
Por lo tanto, consideraremos N2 = [ ] y c = (1, −1, 0, 0).
Test de optimalidad. Debemos investigar otra vez los coeficientes de
la función objetivo. Sea w = cB .B −1 = (1, 0).
Ahora procedemos a evaluar los coeficientes de la función objetivo:
c2 − w.a2 = −1 + 2 = 1 > 0, por lo tanto entra x2 a la base y dejamos de
buscar en los coeficientes de la función objetivo.
Test de factibilidad. Supongamos que x2 → x2 + ∆, con ∆ ≥ 0. Entonces, el cambio que efectúan las variables básicas es
xB → xB − B −1 .a2 .∆.
Es decir, si x2 → 2 + ∆ entonces
x1 → x1 − (−2).∆ = 2 + 2∆,
x4 → x4 − 3.∆ = 6 − 3∆.
Al valor del x2 previo ya lo conocı́amos por que sabı́amos que estaba en su
cota inferior (x2 = 2). A los valores de las variables básicas los podemos
calcular usando B −1 .b − B −1 .N1 .xN1 − B −1 .N2 .xN2 :
1 0
−2
1 0
−2 1
2
2
x1
=
.
−
.
.
=
x4
−1 1
10
−1 1
1 0
0
6
PRIMERA PARTE. Las restricciones son x1 = 2 + 2∆ ≥ −∞, y x4 =
6 − 3∆ ≥ 0. Por lo tanto, x4 es una posible candidata a salir de la base y
γ1 = 2.
SEGUNDA PARTE. Las restricciones son x1 = 2 + 2∆ ≤ 4, y x4 = 6 − 3∆ ≤
+∞. Por lo tanto, x1 es una posible candidata a salir de la base y γ2 = 1.
TERCERA PARTE. Debemos verificar que x2 (que actualmente está en su
cota inferior) no sobrepase su cota superior. La restricción es x2 = 2 + ∆ ≤ 5,
lo que genera γ3 = 3.
PARTE FINAL. Tenemos a γ = mı́n(2, 1, 3) = 1. En consecuencia, x1 resulta ser la variable saliente. Cabe aclarar que x1 va a pasar a su cota superior.
5
Actualización. Para poder pasar a la próxima iteración debemos actualizar la base:
−1/2 0
−1
B = [a2 , a4 ], B =
, N1 = [a3 ], N2 = [a1 ]
1/2
1
Test de optimalidad. Sea w = cB .B −1 = (1/2, 0).
Ahora procedemos a evaluar los coeficientes de la función objetivo:
c3 − w.a3 = 0 − 1/2 = −1/2 ≤ 0,
c1 − w.a1 = 1 − 1/2 = 1/2 ≥ 0.
Como no encontramos ninguna variable en N1 (i.e. x3 ) con coeficiente positivo estricto, ni ninguna variable en N2 (i.e. x1 ) con coeficiente negativo
estricto, se cumple la condición de optimalidad.
Resultado. Como sólo nos interesa saber x∗1 y x∗2 , podemos aprovechar la
información de la última iteración. x1 pasó a su cota superior, ası́ que x∗1 = 4.
También, x2 entró a la base con el valor 2 + γ, es decir x∗2 = 3. Con esto es
suficiente para computar la función objetivo, z ∗ = x∗1 − x∗2 = 1.
NOTA: La forma general de calcular los resultados es apelando al último
diccionario,
x∗B = B −1 .b − B −1 .N1 .x∗N1 − B −1 .N2 .x∗N2
.
z = cB .B .b + (cN1 − cB .B −1 .N1 ).x∗N1 + (cN2 − cB .B −1 .N2 ).x∗N2
∗
−1
OTRA NOTA: En realidad, en este ejercicio hubo una restricción que se
podrı́a haber eliminado. Nótese que x1 − 2x2 ≤ −2, x1 ≤ 4 y 2 ≤ x2 ≤ 5
implican x1 + x2 ≤ 9 (se puede observar claramente si se dibuja el poliedro).
Es decir, que la segunda restricción del ejercicio siempre se cumple. Y además,
no se cumple por igualdad. En el método simplex, una restricción ası́ sólo
genera una fila extra en la matriz A y una variable slack inútil (en este caso,
x4 ) pues nunca puede salir de la base.
6