Modelos Cuantitativos: Metodo Simplex
Repasemos: la idea del metodo simplex es ir pasando de solucion factible en solucion factible hasta
encontrar una solucion optima. Para tal fin, se usa tanto la notacion como las operaciones elementales
de filas (lo cual permite usar mas de dos variables en el problema). Es necesario, para aplicar simplex,
que el problema sea un problema en forma estandar:
Maximizar Z
= c1 x1 + c2 x2 + + cn xn , sujeto a las restricciones
a11 x1 + a12 x2 + + a1n xn b1
a21 x1 + a22 x2 + + a2n xn b2
..
..
..
..
..
.
.
.
.
.
am1 x1 + am2 x2 + + amn xn bm
donde x1 , x2 , xn y b1 , b2 , , bn son no negativas.
La funcion Z es llmada funcion objetivo. Existe un conjunto no vacio de valores para (x1 , x2 , , xn )
que satisface todas las restricciones, del cual siempre seleccionamos para empezar la solucion trivial
(0, 0, , 0). Para poder usar las operaciones de filas en matrices, necesitamos trabajar con igualdades, no desigualdades, asi que primero debemos arreglar las restricciones: para cada desigualdad que
tengamos agregamos una variable de holgura si , con signo positivo, a la izquierda, de manera que las
restricciones se convierten en
a11 x1 + a12 x2 + + a1n xn + s1 = b1
a21 x1 + a22 x2 + + a2n xn + s2 = b2
..
..
..
..
..
.
.
.
.
.
am1 x1 + am2 x2 + + amn xn + sm = bm
Las variables originales se denominan variables estructurales. Una solucion al problema debe involucrar
ambos tipos de variables, aunque por simplicidad, cierta cantidad de variables deben ser cero en
cualquier momento: a estas las llamamos variables no basicas (y las distintas de cero se llaman basicas,
como no). Cuantas variables no basicas debe haber? El numero esta dado por la diferencia entre el
numero total de variables (incluidas las de holgura) menos el numero de restricciones. En esta ultima
cuenta podemos agregar la variable objetivo Z y la funcion objetivo como restriccion, y no hay cambio
en el numero de variables no basicas. Una solucion que tenga este numero de variables basicas y no
basicas se denomina solucion basica factible. Ahora, vamos a escribir las restricciones en notacion
matricial, dejando una columna para cada variable y una fila para cada restriccion. A
nadimos en la
ultima fila la funcion objetivo despejando uno de los lados, con lo cual tenemos la tabla simplex
s1
s2
..
.
x1
a11
a21
..
.
x2
a12
a22
..
.
xn
a1n
a2n
..
.
s1
1
0
..
.
s2
0
1
..
.
sm
0
0
..
.
sm
Z
am1
c1
am2
c2
amn
cn
0
0
0
0
1
0
Z
0
0
b
b1
b2
0
0
1
b1
bm
0
Las variables en la parte superior de la tabla sirven para recordar que variable esta asociada a que
valor durante el proceso. Las varaibles a la izquierda son las variables basicas, que toman los valores
de la columna de la derecha. La ultima fila es la fila de los indicadores, uno para cada variable. Asi,
esta tabla simplex corresponde con la solucion basica factible
(x1 , x2 , , xn , s1 , s2 , , sm ) = (0, 0, , 0, b1 , b2 , , bm )
donde todas las variables estructurales son cero. Desde aqui, vamos a buscar otra solucion basica
factible (SBF) escogiendo una variable a la vez para que se vuelva distinta de cero, garantizando
que en cada momento es la que mas aporte al incremento de la funcion objetivo. A la par que una
variable no basica deja de ser cero, una de las variables basicas debe volverse cero. Este proceso es
completamente algoritmico, y se guia por los siguientes pasos
1. Construir la tabla simplex (hecho)
2. Si los indicadores en la ultima fila son todos no negativos, ninguna de las variables puede aportar
mas al incremento de Z, y el valor optimo de Z es el valor en la esquina inferior derecha de la tabla
simplex. Si al menos hay un indicador negativo, localize la columna con el indicador negativo
mas grande. Esta columna corresponde a la variable que entra a las variables basicas, y es la que
mas aporta al incremento de Z. Si hay mas de una columna, se puede escoger cualquiera.
3. Dividir cada entrada positiva por encima del indicador de la variable que entra, con el correspondiente valor de b. El cociente mas peque
no de los obtenidos corresponde a la fila de la variable
que sale, que se se
nala en la columna de la izquierda.
4. En la entrada que corresponde a la variable que entra y la que sale, colocamos un pivote (1)
usando operaciones elementales de filas, y lo usamos para dejar el resto de la columna en ceros.
5. En la columna de la izquierda, la variable que sale se reemplaza con la variable que entra. Esta
columna corresponde a las variables basicas, cuyos valores estan dados por la columna mas a la
derecha. Todas las otras variables son cero. Esta es la solucion basica factible actual
6. Vuelva al paso 2.
Por que a
nadimos lo de dividir por las entradas positivas? Consideremos la siguiente tabla simplex
s1
s2
Z
x1
3
5
-3
x2
-2
4
-5
s1
1
0
0
s2
0
1
0
Z
0
0
1
b
4
8
0
Aqui, el indicador negativo mas grande es 5, que corresponde a la variable x2 . En este momento, x1
y x2 son variables no basicas, con lo que las restricciones se leen como s1 = 4, s2 = 8. Si permitimos
que x2 deje de ser cero, debemos escoger una variable entre las dos para que se vuelva cero, y esto lo
hacemos escogiendo aquella que le da el mayor margen de crecimiento a x2 sin volverse negativa.
2x2 + s1 = 4
4x2 + s2 = 3
despejando
s1 = 4 + 2x2
s2 = 8 4x2
la segunda ecuacion dice que podriamos subir el valor de x2 hasta 2, garantizando que s2 va a seguir
siendo no negativa (se va a volver cero si x2 = 2, y saldria). Pero en la primera ecuacion no hay
problema en darle a x2 valores positivos tan grandes como quiera, y no podria volver a s1 cero. Eso
sacaria a x2 de la region factible (la region que cumple las restricciones), y por eso descartamos esas
posibilidad. Asi, aqui la variable que sale es s2 .
Hagamos un par de ejemplos:
(
2x1 + x2 8
1. Maximizar Z = x1 + 2x2 con las restricciones
y x1 , x2 0 Construyamos la
2x1 + 3x2 12
tabla simplex, agregando una variable de holgura en cada desigualdad.
SFB= (x1 , x2 , s1 , s2 ) = (0, 0, 8, 12)
En los indicadores, el mayor valor negativo es 5, que corresponde a la variable x2 , que es la
variable que entra. Calculemos los cocientes entre los valores de b y las entradas en la columna
de x2 . De los cocientes, el menor es el correspondiente a la segunda fila, asi que la variable que
sale es s2
2
Aqui, el valor sombreado corresponde a la entrada donde se debe colocar el nuevo pivote. Usando
operaciones elementales, tenemos
SFB= (x1 , x2 , s1 , s2 ) = (0, 4, 4, 0)
Aqui ya no tenemos ningun indicador negativo, asi que hemos terminado, y el valor optimo de Z
es 8.
(
x1 + x2 1
y x1 , x2 , x3 0.
2. Maximizar Z = 2x1 + x2 x3 con las restricciones
x1 2x2 x3 2
Primero, el problema debe estar en la forma estandar, asi que la segunda restriccion debe multiplicarse por -1, y el problema se convierte en
(
x1 + x2 1
y x1 , x2 , x3 0
Maximizar Z = 2x1 + x2 x3 con las restricciones
x1 + 2x2 + x3 2
SFB= (x1 , x2 , x3 , s1 , s2 ) = (0, 0, 0, 1, 2)
El mayor indicador negativo es 2, que corresponde a x1 , que es la variable que entra. Al hacer
los cocientes, una de las entradas sobre este 2 es negativa, asi que esa fila no se cuenta. La
variable que sale entonces es s1
y ahora pivoteamos, pero ya hay un 1, asi que podemos empezar a limpiar el resto de la columna.
SFB= (x1 , x2 , x3 , s1 , s2 ) = (1, 0, 0, 0, 3)
y ya no hay mas indicadores negativos, asi que hemos encontrado una solucion optima.
2x1 + x2 + x3 2
3. Maximizar Z = 2x1 + x2 2x3 con las restricciones x1 x2 + x3 4
y x1 , x2 , x3 0.
x1 + x2 + 2x3 6
La primera restriccion, de nuevo, hay que multiplicarla
por -1. Entonces tenemos
2x1 x2 x3 2
Maximizar Z = 2x1 + x2 2x3 con las restricciones x1 x2 + x3 4
y x1 , x2 , x3 0. Y
x1 + x2 + 2x3 6
planteamos la tabla simplex
3
SFB= (x1 , x2 , x3 , s1 , s2 , s3 ) = (0, 0, 0, 2, 4, 6)
Y otra vez: el indicador negativo mas grande es 2, correspondiente a x1 , y al hacer los cocientes,
la variable que sale es s1
y pivoteando
aqui aun hay un indicador negativo, el de x2 . Solo hay un cociente valido, y sale s3
y pivoteando
SFB= (x1 , x2 , x3 , s1 , s2 , s3 ) = (2,67, 3,33, 0, 0, 4,67, 0)
Y ahora, para practicar mientras tanto, resolver usando el metodo simplex
2x1 + x2 8
1. Maximizar Z = x1 + 2x2 , sujeto a 2x1 + 3x2 12
x1 , y1 0
xy 1
x + 2y 8
2. Maximizar Z = 8x + 2y, sujeto a
x+y 5
x, y 0
2x + y z 4
3. Maximizar Z = 2x y + z, sujeto a x + y + z 2
x, y, z 0
x+y 1
x y 1
4. Maximizar Z = x + 2y, sujeto a x y 2
x2
x, y 0
4
4x + 3y z 1
x + y z 2
5. Maximizar Z = x 12y + 4z, sujeto a
x + y + z 1
x, y, z 0
x + z w 1
x z + w 2
6. Maximizar Z = 4x + 10y 6z w, sujeto a
x + y z + w 4
x, y, z, w 0
