cap tulo 3 metodo del simplex para la programacion lineal
TRANSCRIPT
Capıtulo 3
METODO DEL SIMPLEX PARALA PROGRAMACION LINEAL.
Indice
1. Introduccion. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Fundamentos del metodo del simplex. . . . . . . . . . . . . 1
2.1. Notacion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2. La matriz de coordenadas basicas Y . . . . . . . . . . . . . . . 3
2.3. Costes marginales. Regla de parada. . . . . . . . . . . . . . . 4
2.4. Regla de la variable de entrada . . . . . . . . . . . . . . . . . 5
2.5. Regla de la variable de salida . . . . . . . . . . . . . . . . . . 6
2.6. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3. Metodo del Simplex. . . . . . . . . . . . . . . . . . . . . . . 9
4. Soluciones especiales en los problemas de programacionlineal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1. Soluciones no acotadas. . . . . . . . . . . . . . . . . . . . . . 13
4.2. Solucion optima multiple. . . . . . . . . . . . . . . . . . . . . 14
4.3. Problemas sin solucion. . . . . . . . . . . . . . . . . . . . . . 15
4.4. Problemas degenerados. . . . . . . . . . . . . . . . . . . . . . 15
0
Este tema es una continuacion del anterior, y en el veremos como resolver losproblemas de programacion lineal. Para ello estudiaremos el metodo del Simplex, que esun algoritmo ideado por Dantzig en 1947 con interesantes interpretaciones economicas.
Veremos los fundamentos del metodo, ası como sus propiedades. Por ultimo veremossoluciones especiales de problemas de programacion lineal y como reconocerlas en latabla del Simplex.
1. Introduccion.
En el tema anterior vimos que, despues de anadir las variables de holgura y/o arti-ficiales, resulta sencillo determinar una solucion factible basica inicial (punto extremo),sin mas que utilizar algunas de las variables utilizadas para modificar las restricciones.
Por otra parte, sabemos que en la busqueda de las solucion optima, hay que exa-minar unicamente los puntos extremos del espacio de soluciones.
A continuacion vamos a estudiar el metodo del Simplex, que es un procedimientopor el cual se lleva a cabo el movimiento desde una solucion factible basica (la inicialo cualquier otra) a una solucion factible basica adyacente, mejorando, o al menos noempeorando el valor de la funcion objetivo.
NOTA: el metodo del Simplex lo vamos a ver solo en el caso de maximizacion (paraminimizacion es analogo).
A grandes rasgos, los pasos generales del algoritmo son:Paso 0.- buscar una solucion factible basica (punto extremo).Paso 1.- Determinar si el paso a una solucion factible basica adyacente puede mejorarel valor de la funcion objetivo. Si es ası, ir al paso 2. En caso contrario, hemos alcanzadola solucion optima.Paso 2.- Determinar la solucion factible basica adyacente con mayor mejora en el valorde la funcion objetivo. Volver al paso 1 y repetir el proceso hasta alcanzar una solucionoptima.
A continuacion vamos a estudiar bajo que condiciones es posible la mejora que seindica en el paso 1, lo que nos servira como indicador en la aplicacion del algoritmo.
2. Fundamentos del metodo del simplex.
Para entender mejor este apartado, a la par que damos las formulas generales (co-lumna izda.) mostraremos un ejemplo (columna dcha.).
2.1. Notacion.
En primer lugar fijaremos algunas notaciones.
Notacion. Supongamos un problema de programacion lineal planteado en forma estandar:
Max. z = ~c · ~xs.a. A~x = ~b
~x ≥ 0,
(3.1)
Max. z = 3x1 + 4x2 − 2x3 + x5 (3.2)
2x1 +x2 +x3 + x4 = 5x3 +3x4 = 2
x1 + x4 +x5 = 8(3.3)
x1, x2, x3, x4, x5 ≥ 0.
1
con A ∈Mm×n, Rang(A) = m < n. Deno-tamos las columnas de A por: A1,. . . ,An. A=(A1A2A3A4A5)=
2 1 1 1 00 0 1 3 01 0 0 1 1
,~c es el vector fila ~c = (c1, . . . , cn) y ~x,~b son vectores columna respectivamente
~x =
x1. . .xn
y ~b =
b1. . .bm
.
~c = (3, 4,−2, 0, 1),
~x =
x1x2x3x4x5
, ~b =
528
.
Para ese problema fijemos una base B formada por m columnas cualquiera de Aque sean linealmente independientes.
B = (B1 . . . Bm) = (Aβ1 . . . Aβm) Elegimos para la base B las columnas2,3 y 5. Es decir, segun la notacion anteriorβ1 = 2, β2 = 3, β3 = 5.
B = (B1, B2, B3) = (A2, A3, A5) =1 1 00 1 00 0 1
.
Llamaremos columnas no basicas a las n−m columnas restantes y denotaremospor N a una matriz formada por dichas columnas. Ası, N = (Aη1 . . . Aηn−m), conla union disjunta {η1, . . . , ηn−m} ·∪ {β1, . . . , βm} = {1, . . . , n}.
N = (Aη1 . . . Aηn−m)N = (Aη1 , Aη2) = (A1, A4) =
2 10 31 1
El vector de variables ~x ∈ Rn se puede descomponer en el vector de variablesbasicas ~xB ∈ Rm y el vector de variables no basicas ~xN ∈ Rn−m:
~xB =
xβ1. . .xβm
y ~xN =
xη1. . .xηn−m
~xB =
x2x3x5
y ~xN =
(x1x4
).
Tambien podemos dividir el vector de costos ~c en el vector de costos basicos~cB ∈ Rm y el vector de costos no basicos ~cN ∈ Rn−m:
~cB = (cβ1 , . . . , cβm) y~cN = (cη1 , . . . , cηn−m)
~cB = (c2, c3, c5) = (4,−2, 1) y~cN = (c1, c4) = (3, 0).
Entonces, la funcion objetivo puede escribirse como:
z = ~cB · ~xB + ~cN · ~xNz = (4,−2, 1)
x2x3x5
+ (3, 0)
(x1x4
).
Asociada a esa base, existe una solucion basica unica: x∗ ∈ Rn. Llamemos z0 :=z(x∗) al valor de la funcion objetivo en esa solucion basica.
2
Recordemos que:x∗B = B−1~b,x∗N = ~0,z0 = ~cB · x∗B + ~cN · x∗N = ~cB · x∗B.
x∗B =
x∗2x∗3x∗5
=
1 −1 00 1 00 0 1
528
=
328
x∗N = (x∗1, x
∗4)T = (0, 0)T .
x∗ = (0, 3, 2, 0, 8)T .z0 = (4,−2, 1) · (3, 2, 8)T = 16.
2.2. La matriz de coordenadas basicas Y .
Nuestro proposito es, dado el problema lineal (3.1) y fijada una base B, cambia-
remos el sistema A~x = ~b en otro equivalente, (B−1A)~x = B−1~b. Este nuevo sistema,que obviamente tiene las mismas soluciones que el anterior, es mas amigable para di-cha base, en el sentido de que las variables basicas estan listas para ser despejadas.Veamoslo.
Denotamos Y := B−1A, y le llamamos matriz de coordenadas basicas. Notese que elsistema equivalente se puede escribir Y ~x = x∗B. Ademas, si denotamos Y = (Y1, . . . , Yn)-es decir, Yj es la columna j-esima de Y - notemos que Yj = B−1Aj (j = 1, . . . , n).
~x cumple A~x = ~b ⇔ 2 1 1 1 00 0 1 3 01 0 0 1 1
x1x2x3x4x5
=
528
⇔~x cumple B−1A~x = B−1~b 1 −1 0
0 1 00 0 1
2 1 1 1 00 0 1 3 01 0 0 1 1
x1x2x3x4x5
=
1 −1 00 1 00 0 1
528
(Y ~x = x∗B) 2 1 0 −2 0
0 0 1 3 01 0 0 1 1
x1x2x3x4x5
=
328
Y1x1 + Y2x2 + . . .+ Ynxn = x∗B, (3.4)
con Yj = B−1Aj j = 1, . . . , n.
201
x1+1
00
x2+0
10
x3+−2
31
x4+0
01
x5=3
28
.Se puede probar1 que las columnas de Y correspondientes a la base son vectores
canonicos de Rm. Es decir Yβi := B−1Aβi = ~eiT .
1Notese que B−1B = Im = (~e1T , ~e2
T , . . . , ~emT ). Como B = (B1, B2, . . . , Bm), se tiene que B−1B =
(B−1B1, B−1B2, . . . , B
−1Bm). Por tanto, la columna de Y correspondiente al i-esimo elemento basees Yβi
= B−1Aβi= B−1Bi = ~ei
T .Otra forma mas elaborada de probarlo es la siguiente: como B es una matriz regular, sus columnas
forman una base del espacio vectorial Rm. Veamos que a Y se le llama matriz de coordenadas basicas
porque sus columnas Yj=
y1jy2j. . .ymj
son las coordenadas de Aj en la base que forman las columnas de B:
3
Ası, en el ejemplo de la derecha, la base estaba formada por las columnas 2,3 y 5(e.d. β1 = 2, β2 = 3, β3 = 5) y se tiene Yβ1 = Y2 = ~e1
T , Yβ2 = Y3 = ~e2T , Yβ3 = Y5 = ~e3
T .
Ahora ya podemos concluir el objetivo de este apartado: que el sistema A~x = ~b(cuyas infinitas soluciones son una variedad afın dependiente de n−m parametros) esequivalente a Y ~x = x∗B, que es mas amigable para B porque agrupando en (3.4) lascolumnas correspondientes a la base tiene la formaxβ1
. . .xβm
+∑
j∈{η1,...,ηn−m}
Yjxj = x∗B,
x2x3x5
+
201
x1 +
−231
x4=3
28
.que esta listo para despejar las variables basicas ~xB en funcion de las n−m variables
no basicas:
~xB =
xβ1· · ·xβm
= x∗B −∑
j∈{η1,...,ηn−m}
Yjxj
(3.5)
x2x3x5
=
328
−2
01
x1 −−2
31
x4..Es decir, la solucion general del sistema A~x = ~b, fijada una base, se puede escribir
de forma que los xβ1 , . . . , xβm esten despejados en funcion de la solucion basica y losn−m parametros xη1 , . . . , xηn−m .
2.3. Costes marginales. Regla de parada.
En el apartado anterior, dado el problema de programacion lineal (3.1) y una base
concreta B, hemos escrito el sistema A~x = ~b de un modo Y ~x = B−1~b, mas amigablepara dicha base, ya que las variables basicas son trivialmente despejables en funcionde las n−m no basicas (ecuacion (3.5)).
En este apartado estudiaremos como escribir la funcion objetivo z = ~c · ~x de modoamigable para la base B: en funcion unicamente de las variables no basicas. De estemodo obtendremos informacion muy util para el metodo del simplex. Veamoslo:
Sea ~x ∈ Rn es una solucion cualquiera (basica o no) de A~x = ~b. El valor de lafuncion objetivo en ~x valdra
z = ~c · ~x = ~cB · ~xB + ~cN · ~xN
(ver (3.2) en el ejemplo)z = 3x1 + 4x2 − 2x3 + x5 =
= (4,−2, 1) ·
x2x3x5
+ (3, 0)
(x1x4
)Por la ecuacion (3.5), ponemos las variables basicas en funcion de n−m variables
no basicas y sustituimos:
Aj = y1jB1 + y2jB2 + . . . + ymjBm ⇔ Aj = B ·
y1jy2j. . .ymj
⇔ Aj = BYj ⇔ Yj = B−1Aj .
En consecuencia, las coordenadas de la columna basica Aβi= Bi respecto a la base de columnas de
B son todo ceros menos la coordenada i-esima. Por tanto, Yβi= ~ei
T .
4
z = ~cB · x∗B −∑
j∈{η1,...,ηn−m}
~cBYjxj +~cN · ~xN
z = (4,−2, 1)
328
︸ ︷︷ ︸
~cBx∗B=z0
− (4,−2, 1)
201
︸ ︷︷ ︸
~cBY1
x1
− (4,−2, 1)
−231
︸ ︷︷ ︸
~cBY4
x4 + (3, 0)
(x1x4
)
Notar que z0 := ~cB · x∗B es el valor de la funcion objetivo en la solucion basicaasociada a B (x∗ = (x∗B, x
∗N) con x∗N = 0).
z= z0−∑
j∈{η1,...,ηn−m}
~cBYjxj+∑
j∈{η1,...,ηn−m}
cjxj
= z0 +∑
j∈{η1,...,ηn−m}
(cj − ~cBYj)xj.
z= 16︸︷︷︸z0
− 9︸︷︷︸~cBY1
x1−(−13)︸ ︷︷ ︸~cBY4
x4+ 3︸︷︷︸c1
x1+ 0︸︷︷︸c4
x4
= 16 + (−6)︸︷︷︸c1−~cBY1
x1 + 13︸︷︷︸c4−~cBY4
x4.
Definicion 1. En el contexto de un problema estandar, dada una base, llamamoscoste marginal o coste relativo de una variable no basica xj a la cantidad c′j :=cj − zj := cj − ~cBYj.
Entonces:z = z0 +
∑j∈{η1,...,ηn−m}
c′jxj (3.6)
Ası, el costo marginal nos indica lo que varıa el valor de la funcion objetivo si la variablexj (no basica) se incrementa desde 0 hasta 1 en una nueva solucion factible.
Notar que el coste marginal tambien se puede definir para variables basicas mediantela misma formula: c′βi := cβi − ~cBYβi = cβi − ~cB~ei
T = cβi − cβi = 0.Finalmente, por (3.6), notar que si todos los costos marginales de las variables
no basicas son menores o iguales que cero, no existe ninguna solucion factiblemejor que la solucion basica, que es la solucion optima. Por tanto, terminamosde ejecutar el algoritmo del simplex.
2.4. Regla de la variable de entrada
Supongamos que estamos en una base factible B y que alguna variable no basicatiene coste marginal estrictamente positivo. Buscamos ahora una nueva base factibleB adyacente a la anterior en la que no empeore el valor de la funcion objetivo.
Para ello debemos determinar cual de las variables es la que debe dejar de ser basica(su vector asociado dejara de estar en la base) y que otra variable es la que debe entraren su lugar.
SiB = (Aβ1 . . . Aβm), y su solucion basica factible es x∗, entonces una base adyacentecoincide en todas las columnas elegidas, menos en una. Supongamos que la nuevacolumna es Aj con j /∈ {β1, . . . , βm}. Supongamos que la columna que eliminamos es
Bk = Aβk . Entonces, la nueva matriz basica es B = (Aβ1 . . .���ZZZ
Aβk . . . AβmAj). Para estanueva base, sea su solucion basica factible x. Denotemos por θ = xj ≥ 0 lo que vale lanueva variable basica xj en la solucion x.
5
Debido a (3.6), el nuevo valor de la funcion objetivo sera
z = z0 + c′jθ.
Ası, el coste marginal c′j de una variable no basica, nos indica la variacion del valorde la funcion objetivo por cada unidad de xj en la nueva solucion basica formada alintroducir dicha variable en la base. Entonces:Regla de la variable de entradaLa variable que entra en la base, sera aquella cuyo costo marginal sea el mas positivo.En caso de empate, se elige arbitrariamente.
Realmente podemos elegir para entrar en la base una variable cualquiera cuyo costomarginal sea positivo y no empeoraremos el valor de la funcion objetivo. Pero a priori,sin hacer mas cuentas la que tiene el coste marginal mas positivo es la que nos daexpectativas de una mayor mejora (aunque esto no tiene por que suceder finalmente).
2.5. Regla de la variable de salida
Una vez que hemos decidido que variable xj entra en la base, nuestro propositoahora es elegir que variable xβk sale de la base para que:
B sea efectivamente una base y su solucion basica: x, sea factible.
No toda coleccion de m columnas de A forman una base. Han de ser linealmenteindependientes. Ası, que B sea una base, es equivalente a que el sistema A~x = ~b (o
Y ~x = B−1~b) junto con la condicion de que sean cero las variables no asociadas a las
columnas de B tenga solucion unica. Por (3.5),dicho sistema queda:xβ1· · ·��HHxβk· · ·xβm
= x∗B − Yjxj,
xβ1 = x∗β1 − y1jxj. . .
��HHxβk = x∗βk − ykjxj. . .xβm = x∗βm − ymjxj
Si ykj 6= 0, existe solucion y es unica ya que es facil de obtener, primero despejando xjen la k-esima ecuacion y despues cada xβi se despeja en funcion de xj.
Para esta nueva base, la nueva solucion basica x pudiera ser no factible. Denotemoslos valores de x por xβ1 , . . . , xβm (uno de ellos, xβk = 0) y sea θ := xj ≥ 0 el valor dela nueva variable basica xj. La solucion sera factible si y solo si
θ := xj =x∗βkykj≥ 0 ⇔ ykj > 0
y ademas, para todo i ∈ {1, . . . ,��SSk, . . . ,m}
xβi = x∗βi − yijθ ≥ 0 ⇔ θ ≤x∗βiyij
en caso de que yij > 0
En consecuencia (∗) equivale a que
θ := mın{x∗βiyij
: i = 1, . . . ,m; yij > 0}
6
Regla de la variable de salida.Si ha entrado en la base xj, tomara en la nueva base el valor de
θ := mın1≤i≤m
{x∗βiyij
: yij > 0}
y la variable que sale de la base, xβk , debe ser elegida como la que minimiza la razonanterior.
Observaciones. Notar que si la columna Yj tuviera todos sus componentes negativos onulos, no podemos ejecutar la regla de la variable de salida. No nos preocupemos poresto ahora, lo trataremos mas adelante.
Ejemplo. Para entender mejor como se justifican las formulas que llevan a la variablede salida, continuamos con el ejemplo anterior,
z = 16− 6x1 + 13x3.
Decidimos que entre en la base la variable x3. Notese que cuanto mayor valor tenga x3,mayor sera el valor de 13x3 y mas incrementaremos el valor de z.
Ahora nos preguntamos que variable de las basicas: x2, x3, x5, debe salir de la base.Recordemos que el sistema Y ~x = B−1~b estaba dado por ecuacion (3.5), que suponiendoque son cero las variables que no estan en la base anterior {x2, x3, x5} ni la que va aentrar, x3, quedax2x3
x5
=
328
−−2
31
︸ ︷︷ ︸
Y4
x4,x2 = 3 −(−2)x4x3 = 2 −3x4x5 = 8 −1x4.
(3.7)
Como x2 = 3− (−2)x4 notemos que, como y14 = −2 < 0, para cualquier valor quedemos a x4 ≥ 0, por muy grande que sea, x2 seguira siendo positivo, nunca se anularao se hara negativo. Ası que x2 no puede ser la variable que salga de la base.
En la segunda ecuacion x3 = 2 − 3x4, como y24 = 3 > 0, para que x3 ≥ 0 y lasolucion sea factible, se tiene que 0 ≤ x4 ≤ 2/3 y no puede ser mas grande.
En la tercera ecuacion x5 = 8−x4, ası que para que x5 ≥ 0 y la solucion sea factible,como y34 = 1 > 0, se tiene que cumplir 0 ≤ x4 ≤ 8.
En resumen, para que la solucion sea factible: 0 ≤ x4 ≤ mın{8/1, 2/3} = 2/3, ypara que sea basica, una variable tiene que hacerse cero y salir de la base, y esto solosucede cuando x4 = mın{8/1, 2/3} = 2/3 y se hace cero x3. Una vez fijado x4, el restode variables x3 = 0, x5 = 8− 2/3 = 22/3, x2 = 3 + 2(2/3) = 13/3 se calculan de modounico despejando. Luego al asumir x3 = 0, el sistema (3.7) tiene solucion unica y deaquı se concluye que {x2, x5, x4} forman una base.
Por otro lado, notese que manteniendo la condicion de obtener una solucion factible,si se elimina la restriccion de que la nueva solucion sea basica y permitimos tener 4variables {x2, x3, x5, x4} no nulas, basta con que 0 ≤ x4 ≤ mın{8/1, 2/3} = 2/3, yde las infinitas soluciones posibles, la que mayor valor nos da de la funcion objetivoz es x4 = 2/3. Esto es un hecho general. Si simplemente, dada una nueva variable nonula, buscaramos la solucion factible con mayor valor de dicha variable, y por tantocon mayor valor de funcion objetivo, dicha variable se puede ir aumentando hasta queen la ecuacion (3.7) una de las variable basica, con yij > 0 se haya hecho tan pequenaque se anule. Con lo cual, sin buscarlo, hemos obtenido otra solucion basica.
7
2.6. Ejemplo
Sea el problema: Max. z = 2x1 + 3x2
sujeto a
{x1 + x2 ≤ 9
3x1 + x2 ≤ 12
x1, x2 ≥ 0.
En forma estandar, este problema es:
Max. z = 2x1 + 3x2
sujeto a
{x1 + x2 + x3 = 9
3x1 + x2 + x4 = 12
x1, x2, x3, x4 ≥ 0.
Podemos obtener facilmente una base inicial a partir de las variables de holgura. Estabase es:
B = (A3, A4) =
(1 00 1
)con lo que x∗B = B−1~b =
(1 00 1
)·(
912
)=
(912
)=
(x3x4
),
con z0 = ~cB · x∗B = (0, 0) ·(
912
)= 0. Veamos si es posible la mejora, para lo cual
tenemos que calcular los Yj y los costos marginales c′j para las variables no basicas:
Yj = B−1Aj ⇒ Y1 = B−1A1 =
(1 00 1
)·(
13
)=
(13
)
Y2 = B−1A2 =
(1 00 1
)·(
11
)=
(11
)zj = ~cBYj ⇒ z1 = ~cB · Y1 = (0, 0)
(13
)= 0 ⇒ c′1 = c1 − z1 = 2− 0 = 2
z2 = ~cB · Y2 = (0, 0)
(11
)= 0 ⇒ c′2 = c2 − z2 = 3− 0 = 3
Como los costos marginales son positivos, esto nos indica que es posible una mejora enel valor de la funcion objetivo. Como 2 < 3 ⇒ x2 es la variable que debe entrar en labase.
Veamos que variable debe salir:
mın{x∗βiyi2
: i = 1, 2; yi2 > 0} = mın{x∗β1y12
,x∗β2y22} = mın{ x
∗3
y12,x∗4y22} = mın{9
1,12
1} =
9
1=
x∗3y12
Luego, la primera variable basica x∗β1 = x∗3, es la que debe salir.La nueva base es:
B = (A2, A4) =
(1 01 1
)
8
con lo que x∗B
= B−1~b =
(1 0−1 1
)·(
912
)=
(93
)=
(x2x4
),
con z0 = ~cB · ~xB = (3, 0) ·(
93
)= 27. Veamos si es posible la mejora. Volvemos a
calcular los Yj y los costos marginales c′j para las variables no basicas:
Yj = B−1Aj ⇒ Y1 = B−1A1 =
(1 0−1 1
)·(
13
)=
(12
)
Y3 = B−1A3 =
(1 0−1 1
)·(
10
)=
(1−1
)zj = ~cBYj ⇒ z1 = ~cB · Y1 = (3, 0)
(12
)= 3 ⇒ c′1 = c1 − z1 = 2− 3 = −1
z3 = ~cB · Y3 = (3, 0)
(1−1
)= 3 ⇒ c′3 = c3 − z3 = 0− 3 = −3
Como los costos marginales son no positivos (los de la base son nulos), no es posible lamejora, y la solucion actual nos da el valor optimo de la funcion objetivo.
x∗ = (0, 9, 0, 3)T con z = 27.
En la resolucion del problema anterior, hemos aplicado el metodo del Simplex, lo quenos da una idea de los calculos que son necesarios para su aplicacion.
Este enfoque, que a primera vista parece bastante laborioso, veremos que se sim-plifica considerablemente al desarrollarlo de forma tabular, lo que lo hara mas sencilloy sistematico en su aplicacion a problemas de mayor tamano.
3. Metodo del Simplex.
En esta seccion utilizaremos la notacion que aparecio en el apartado 2.1. Suponga-mos un problema de programacion lineal planteado en forma estandar:
Max. z = ~c · ~xs.a. A~x = ~b
~x ≥ 0
con A ∈ Mm×n, Rang(A) = m < n, y donde ~c y ~x son vectores fila y columnarespectivamente ~c = (c1, . . . , cn) y ~xT = (x1, . . . , xn).
En el metodo del simplex en forma tabular, dada una base, lleva asociada la tabla:
xβk xB cB x1 . . . xn
B−1~b ~cB B−1A = Y
z = ~cB ·B−1 ·~b c′1 . . . c′n
donde:
9
- xBk , es el valor de la solucion basica
- xB, indica las variables que estan en la base. Es la lista de variables basicas.
- z, es el valor de la funcion objetivo en la solucion basica
- ~cB, son los costos de las variables basicas
- c′j, son los costos marginales. c′j = cj −~cBYj = cj − zj, con zj = ~cB ·Yj, costos basicospor componentes.
- En la tabla aparece el sistema Y · ~x = B−1~b. Recordemos que cada columna Yβicorrespondiente a la i-esima variable basica es ei y que c′βi = 0.
Algoritmo del Simplex.
Para poder aplicar el algoritmo del Simplex tiene que existir factibilidad primal,es decir que se tiene que cumplir que los valores de las variables basicas sean todos nonegativos.
Los pasos que sigue este algoritmo son los siguientes:
P1.- Dado cualquier problema de programacion lineal, se transforma a la forma estandar,introduciendo las variables de holgura y/o artificiales necesarias, para convertirlas desigualdades en igualdades, con lo que tenemos:
Max. z = ~c · ~xs.a. A · ~x = ~b
~x ≥ 0
y la matriz A tiene una submatriz identidad, que correspondera a la primera base.Construimos la tabla inicial con los coeficientes del problema.
P2.- Comprobamos si la solucion que tenemos es optima. Para lo cual, todos los costosmarginales deben ser no positivos. Si algun costo marginal es positivo, entoncesla base no es optima, y por lo tanto hay que cambiar de base.
P3.- Seleccionamos el vector de entrada en la base, eligiendo aquel cuyo costo marginalsea mayor. En caso de empate, se coge uno cualquiera.
P4.- Una vez elegida la variable de entrada (xj), seleccionamos la variable de salida(xβk), como aquella que hace mınimo el cociente:
mın1≤i≤m
{x∗βiyij
: yij > 0}
P5.- Mediante operaciones del metodo de Gauss, transformamos el vector asociado ala variable de entrada en unitario2, y volvemos al paso 2.
2es decir, si la variable xj entra en la base en la posicion i-esima, esto es xj = xβi , tenemos queaplicar el metodo de Gauss para conseguir que la columna Yj = Yβi
= ei. Este metodo no va a afectaral resto de columnas basicas, ası que como resultado obtendremos una submatriz identidad en lascolumnas basicas. Notemos que entoces hemos obtenido un sistema de ecuaciones “amigable” para lanueva base. La ventaja de utilizar el metodo de Gauss es que como la base no cambia mucho (se pasa
10
Ejemplo.
Max. z = 100x1 + 200x2s.a. 3x1 + 2x2 ≤ 250
3x1 + 4x2 ≤ 3002x1 + 6x2 ≤ 300
x1, x2 ≥ 0
Solucion:Anadimos las variables de holgura:
Max. z = 100x1 + 200x2s.a. 3x1 + 2x2 + x3 = 250
3x1 + 4x2 + x4 = 3002x1 + 6x2 + x5 = 300x1, x2, x3, x4, x5 ≥ 0
Construimos la tabla:
100 200 0 0 0
xBk xB cB x1 x2 x3 x4 x5
250 x3 0 3 2 1 0 0300 x4 0 3 4 0 1 0300 x5 0 2 6 0 0 1
z=0 100 200 0 0 0
Esta solucion no es optima porque hay costos marginales no negativos.Entra en la base x2 ya que es el que tiene mayor costo marginal.
Sale la variable que hace mınimo el cociente:x∗βkyk2
, con yk2 ≥ 0, es decir,
mın{x∗β1y12
,x∗β2y22
,x∗β3y32} = mın{ x3
y12,x4y22
,x5y32} = mın{250
2,300
4,300
6} = mın{125, 75, 50} = 50,
luego sale la variable: x5.Hacemos el cambio de base y arreglamos la tabla teniendo en cuenta que el vector
asociado a la variable x2 debe ser unitario.
100 200 0 0 0
xBk xB cB x1 x2 x3 x4 x5
150 x3 0 7/3 0 1 0 -1/3100 x4 0 5/3 0 0 1 -2/350 x2 200 1/3 1 0 0 1/6
z=10.000 100/3 0 0 0 -100/3
de una base a otra adyacente), simplemente hay que dejar la columna correspondiente a xj como unvector canonico, para lo que hay que hacer menos cuentas que como hemos explicado antes (invertirla nueva base y multiplicar). Notese que ambos metodos nos llevan al mismo resultado, ya que cadapaso del metodo de Gauss es equivalente a un producto de matriz a izda. y si el resultado es unamatriz con identidad en las columnas basicas es que hemos multiplicado por la inversa de la base.
11
Esta solucion sigue sin ser optima.
Entra x1, y sale el que hace mın{150
7/3,100
5/3,
50
1/3} = mın{450
7,300
5, 150}= mın{64,3, 60, 150}
⇒ sale x4. Reconstruimos la tabla:
100 200 0 0 0
xBk xB cB x1 x2 x3 x4 x5
10 x3 0 0 0 1 -7/5 3/560 x1 100 1 0 0 3/5 -2/530 x2 200 0 1 0 -1/5 3/10
z=12.000 0 0 0 -20 -20
Esta solucion es optima.La solucion que hemos obtenido es:
x1 = 60, x2 = 30, z = 12 000.
El valor de x3 es 10, y x3 es una variable de holgura, lo que significa que sobran 10unidades del recurso 1. Ademas, x4 = x5 = 0.
Veamos que esta solucion verifica las restricciones:
1.- 3x1 + 2x2 + x3 = 250 (3 ∗ 60 + 2 ∗ 30 + 10 = 180 + 60 + 10 = 250)
2.- 3x1 + 4x2 + x4 = 300 (3 ∗ 60 + 4 ∗ 30 + 0 = 180 + 120 + 0 = 300)
3.- 2x1 + 6x2 + x5 = 300 (2 ∗ 60 + 6 ∗ 30 + 0 = 120 + 180 + 0 = 300)
Ejercicios propuestos: (Resolverlos primero graficamente)
1.-Max z = 5 000x1 + 3 000x2s. a: 3x1 + 5x2 ≤ 15
5x1 + 2x2 ≤ 10x1, x2 ≥ 0
solucion: x1 = 20/19, x2 = 45/19, z = 235 000/19.
2.-Max z = 4x1 + 3x2s. a: 2x1 + 3x2 ≤ 6
−3x1 + 2x2 ≤ 32x2 ≤ 5
2x1 + x2 ≤ 4x1, x2 ≥ 0
solucion: (x1, x2, x4, x5) = (3/2, 1, 11/2, 3), z = 9.
4. Soluciones especiales en los problemas de pro-
gramacion lineal.
Ademas de las soluciones que hemos visto hasta ahora, al resolver un problema senos pueden presentar otros tipos de soluciones “especiales”, que son las que vamos aver a continuacion. Tambien se estudiara cual es el motivo de que se presente este casoparticular y como detectarlo en la tabla del Simplex.
12
4.1. Soluciones no acotadas.
Puede ocurrir que la solucion de un problema de programacion lineal sea no acotada,es decir, que la funcion objetivo pueda tomar valores tan grandes como queramos,tendiendo a infinito.
* Esto solo puede ocurrir cuando la region de factibilidad es no acotada.
* En la tabla del Simplex se detecta cuando: al intentar hacer un cambio de base, nopodemos hacer el test del cociente por ser todos los elementos de la columna de Ycorrespondiente a la variable de entrada en la base ≤ 0.
Ejemplo:
Max z = 4x1 + 5x2s. a: −2x1 + 2x2 ≥ 2
−x1 + x2 ≤ 4xi ≥ 0
14
§3.- Soluciones especiales en los problemas de programación lineal.
Además de las soluciones reales que hemos visto hasta ahora, al resolver un problema se nos pueden presentar otros tipos de soluciones "especiales", que son las que vamos a ver a continuación. También se estudiará cuál es el motivo de que se presente este caso particular y cómo detectarlo en la tabla del Simplex.
1.- Soluciones no acotadas.
Puede ocurrir que la solución de un problema de programación lineal sea no acotada, es decir, que alguna (o varias) de las variables tomen valor infinito.
* Esto puede ocurrir cuando la región de factibilidad es no acotada.
* En la tabla del Simplex se detecta cuando: al intentar hacer un cambio de base, no podemos hacer el test del cociente por ser todos los elementos de la columna correspondiente a la variable de entrada en la base 0.
Ejemplo:
Max z = 4 x1 +5 x2 s. a: -2 x1 +2 x2 2 - x1 + x2 4 xi 0
1
4
-4 -1
4 5 0 -M 0 xBk xB cB x1 x2 x3 w1 x4
2 w1 0 -2 2 -1 1 0
4 x4 0 -1 1 0 0 1
z = 0 4 5 0 0
1 x2 5 -1 1 -1/2 1/2 0
3 x4 0 0 0 1/2 -1/2 1
z = 5 9 0 5/2 -M-5/2 0
4 x2 5 -1 1 0 0 1
6 x3 0 0 0 1 -1 2
z = 5 9 0 0 -M -5
4 5 0 -M 0
xBk xB cB x1 x2 x3 w1 x4
2 w1 -M -2 2 -1 1 04 x4 0 -1 1 0 0 1
z=-2M 4-2M 5+2M -M 0 0
1 x2 5 -1 1 -1/2 1/2 03 x4 0 0 0 1/2 -1/2 1
z=5 9 0 5/2 -M-5/2 0
4 x2 5 -1 1 0 0 16 x3 0 0 0 1 -1 2
z=20 9 0 0 -M -5
Tendrıa que entrar x1 en la base, pero no podemos hacer el test del cociente, para verque variable sale de la base. Por lo tanto la solucion es NO ACOTADA.
Justificacion.
Cuando explicamos la regla de la variable de salida, hicimos una observacion de quetratarıamos mas adelante el caso de que la variable de entrada, xj, tuviera la columnaYj con todos sus componentes ≤ 0. Este es el momento de tratarlo. Supongamos quetenemos una base B con solucion basica x∗B. Sean (xβ1 , . . . , xβm) variables basicas yla variable no basica xj tiene coste marginal c′j > 0. Asumamos que cuando vamos ameter xj en la base no podemos hacer el test del cociente porque Yj ≤ 0.
Entonces, el sistema xβ1· · ·xβm
= x∗B − Yjxj,
13
tiene para valores de xj > 0 tan grandes como queramos soluciones factibles con(xβ1 , . . . , xβm) cada vez mas grandes. Notese que las soluciones factibles de dicho sistema(y el resto de variables igual a cero) son puntos del dominio con valor de z = z0 + c′jxjtan grande como queramos.
4.2. Solucion optima multiple.
Hay problemas de programacion lineal cuya solucion no es un punto, sino infinitos,ya que el optimo puede alcanzarse en varios vertices o existir direcciones extremas ~dcon ~c · ~d = 0 (recordar Teorema 7 de tema 1).
* En la tabla, se detecta una solucion multiple, si en la solucion optima hay algunavariable no basica cuyo costo marginal es igual a cero.
En este caso, las infinitas soluciones son los infinitos puntos que se pueden escribircomo combinacion lineal convexa de las soluciones basicas halladas3.
Ejemplo:
Max z = 5x1 + 2x2s. a: 6x1 + 10x2 ≤ 30
10x1 + 4x2 ≤ 20x1, x2 ≥ 0
15
Tendría que entrar x1 en la base, pero no podemos hacer el test del cociente, para ver qué variable sale de la base. Por lo tanto la solución es NO ACOTADA.
2.- Solución óptima múltiple.
Hay problemas de programación lineal cuya solución no es un punto, sino los infinitos puntos de un hiperplano (recta en 2).
* Esto ocurre cuando la función objetivo coincide en un segmento rectilíneo con alguna de las restricciones.
* En la tabla, se detecta una solución múltiple, si en la solución óptima hay alguna variable no básica cuyo costo marginal es igual a cero.
En este caso, las infinitas soluciones son los infinitos puntos que se pueden escribir como combinación lineal convexa de las soluciones halladas.
Ejemplo:
Max z = 5x1 + 2x2 s. a: 6x1 + 10x2 30 10x1 +4x2 20 x1 ,x2 0
5
3
2 5
A
B
La función objetivo es una recta que se desplaza paralela a la segunda restricción, y alcanza el óptimo la llegar al punto B. Pero a la vez que toca en ese punto, toca también en todos los puntos del segmento [A,B].
Luego las soluciones del problema son todos los puntos de dicho segmento.
E. d.: {soluciones}={x/ x= A+(1-)B, [0,1]}
Veámoslo:
La funcion objetivo es una recta que se desplaza paralela a la segunda restriccion,y alcanza el optimo la llegar al punto B. Pero a la vez que toca en ese punto, tocatambien en todos los puntos del segmento [A,B].
Luego las soluciones del problema son todos los puntos de dicho segmento. E. d.:{soluciones} = {x ∈ R2|x = λA+ (1− λ)B, λ ∈ [0, 1]}. Veamoslo:
5 2 0 0
xBk xB cB x1 x2 x3 x4
30 x3 0 6 10 1 020 x4 0 10 4 0 1
z=0 5 2 0 0
18 x3 0 0 38/5 1 -3/52 x1 5 1 2/5 0 1/10
z=10 0 0 0 -1/2
Hemos obtenido una solucion optima en el punto (2, 0), pero el costo marginal de lavariable x2 es cero, y por lo tanto podemos hacer un cambio de base: entra x2, y salex3. Entonces:
3mas combinacion conica de las direcciones extremas perpendiculares a ~c, si las hubiera.
14
5 2 0 0
xBk xB cB x1 x2 x3 x4
45/19 x2 2 0 1 5/38 -3/3820/19 x1 5 1 0 -1/19 5/38
z=10 0 0 0 -1/2
Al hacer este cambio, hemos obtenido otro punto (20/19, 45/19), en el que la funcionobjetivo alcanza el mismo valor optimo. Por lo tanto, la funcion objetivo alcanza eloptimo en todos los puntos del segmento:
[(2, 0), (20/19, 45/19)] , y ese valor optimo es z = 10.
E. d. el conjunto de soluciones es:
{λ(2, 0) + (1− λ)(20
19,45
19) : λ ∈ [0, 1]} =
{(2λ+ (1− λ)
20
19, (1− λ)
45
19
): λ ∈ [0, 1]
}4.3. Problemas sin solucion.
En alguna ocasion nos podemos encontrar con un problema sin solucion.
* Esto ocurre cuando las restricciones del problema son inconsistentes, porque no sepueden verificar todas a la vez (o lo que es lo mismo, cuando la region de factibilidades el vacıo).
* En la tabla del Simplex se detecta un problema sin solucion, cuando se llega a unasolucion optima con variables artificiales no nulas.
4.4. Problemas degenerados.
Cuando hay un empate entre las variables que tienen que salir de la base, la nuevasolucion basica resultante, sera una solucion degenerada.
En este caso, se puede producir un ciclo y no llegar nunca a la solucion optima.Para evitar esto, a la hora de elegir la variable que sale de la base (en caso de empate),se utiliza el llamado metodo lexico-grafico.Metodo lexico-grafico.Cuando aplicamos el metodo del Simplex para resolver un problema de programacionlineal, puede ocurrir que, al aplicar el criterio de salida:
mın1≤i≤m
{x∗βiyij
: yij > 0},
obtengamos un empate. Es decir, que haya mas de una variable para la que se obtengael mınimo.
Para deshacer el empate hacemos lo siguiente:
1.- Sea I={ındices de las variables de la base}
Calculamos mın1≤i≤m{x∗βiyij
: yij > 0, βi ∈ I}* Si el mınimo es unico, esa variable sale de la base.* En caso contrario, consideramos el conjunto:
I1 = {i ∈ I, para los que (x∗βi/yij > 0), es mınimo}, subconjunto de I.
15
2.- Construimos una nueva tabla, con las filas correspondientes a los elementos de I1,y de modo que las m primeras columnas sean las de las variables que tenıan lamatriz identidad en la primera tabla (normalmente de holgura o artificiales), y laultima sea la de la variable de entrada.
3.- Calculamos : mın{yi1yij/i ∈ I1}
* Si ese mınimo es unico, la variable correspondiente sale de la base.* En caso contrario, consideramos el conjunto:
I2 = {i ∈ I1, para los que (yi1yij/i ∈ I1), es mınimo}, subconjunto de I1.
4.- Calculamos: mın{yi2yij/i ∈ I2}
y proseguimos de forma analoga al paso 3.
Llegara un momento en el que se deshace el empate.
Ejemplo.
Max. z = 3/4x1 − 20x2 + 1/2x3 − 6x4s. a: x3 ≤ 1
1/4x1 − 8x2 − x3 + 9x4 ≤ 01/2x1 − 12x2 − 1/2x3 + 3x4 ≤ 0
xi ≥ 0
3/4 -20 1/2 -6 0 0 0
xBk xB cB x1 x2 x3 x4 x5 x6 x7
1 x5 0 0 0 1 0 1 0 00 x6 0 1/4 -8 -1 9 0 1 00 x7 0 1/2 -12 -1/2 3 0 0 1
z=0 3/4 -20 1/2 -6 0 0 0
Entra x1, y sale mın{ 01/4, 01/2} = 0.
Aplicamos el metodo lexico grafico:
1.- I1 = {6, 7}.
2.-
xB x5 x6 x7 x1
x6 0 1 0 1/4x7 0 0 1 1/2
3.- mın{yi5yi1/i ∈ I1} = mın{ 0
1/4, 01/2}, no se deshace el empate.
I2 = {6, 7},mın{yi6
yi1/i ∈ I2} = mın{ 1
1/4, 01/2} = 0, luego sale x7.
16
xBk xB cB x1 x2 x3 x4 x5 x6 x7
1 x5 0 0 0 1 0 1 0 00 x6 0 0 -2 -3/4 15/2 0 1 -1/20 x1 3/4 1 -24 -1 6 0 0 2
z=0 0 -2 5/4 -21/2 0 0 -3/2
1 x3 1/2 0 0 1 0 1 0 03/4 x6 0 0 -2 0 15/2 3/4 1 -1/21 x1 3/4 1 -24 0 6 1 0 2
z=5/4 0 -2 0 -21/2 -5/4 0 -3/2
La solucion optima es: x1 = 1, x3 = 1, z = 5/4.Veamos lo que hubiera pasado si sacamos x6 en lugar de x7:
xBk xB cB x1 x2 x3 x4 x5 x6 x7
1 x5 0 0 0 1 0 1 0 00 x1 3/4 1 -32 -4 36 0 4 00 x7 0 0 4 3/2 -15 0 -2 1
z=0 0 4 7/2 -33 0 -3 0
1 x5 0 0 0 1 0 1 0 00 x1 3/4 1 0 *8 -84 0 -12 80 x2 -20 0 1 3/8 -15/4 0 -1/2 1/4
z=0 0 0 2 -18 0 -1 -1
1 x5 0 -1/8 0 0 21/2 1 3/2 -10 x3 1/2 1/8 0 1 -21/2 0 -3/2 10 x2 -20 -3/64 1 0 3/16 0 1/16 -1/8
z=0 -1/4 0 0 3 0 2 -3
1 x5 0 5/2 -56 0 0 1 -2 60 x3 1/2 -5/2 56 1 0 0 *2 -60 x4 -6 -1/4 16/3 0 1 0 1/3 -2/3
z= 0 1/2 -16 0 0 0 1 -1
xBk xB cB x1 x2 x3 x4 x5 x6 x7
1 x5 0 0 0 1 0 1 0 00 x6 0 -5/4 28 1/2 0 0 1 -30 x4 -6 1/6 -4 -1/6 1 0 0 1/3
z= 0 7/4 -44 -1/2 0 0 0 2
Ahora, entra en la base la variable x7 y sale la variable x4. Por tanto, hemos vueltoa llegar a la base de partida (x5, x6, x7), formando un ciclo.
Notese que se han producido empates en la regla de la variable de salida, aparte deen la primera tabla, en otras tablas (*). Si hubiesemos desempatado de modo diferente,hubieramos llegado a la solucion optima, evitando el ciclo.
17