Referencia: Publicacin del Mtodo por George Dantzig en 1947.
Primera implementacin computacional
del Mtodo Simplex el ao 1952 en un problema de 71 variables y 48 ecuaciones, tarda 18 horas. En
1956, un cdigo llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolucin de
modelos con 255 restricciones.
Consideremos un modelo de Programacin Lineal en su forma estandar, que denotaremos en lo que
sigue por:
Min
c1x1 + c2x2 + ... + cnxn
sa
a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
...
...
...
am1x1 + am2x2 + ... + amnxn = bm
xi >= 0, i = 1, 2, ..., n
m <= n
Matricialmente escrito como:
Min
cTx
sa
Ax = b
x >= 0
No existe prdida de generalidad en asumir que un modelo de PL viene dado en su forma estndar.
EJEMPLO
P)
Max
sa
9u + 2v + 5z
4u + 3v + 6z <= 50
u + 2v - 3z >= 8
2u 4v + z = 5
u,v >= 0
z e IR
1.
2.
3.
4.
Siempre es posible llevar un problema de maximizacin a uno de minimizacin. Si f(x) es la
funcin objetivo a maximizar y x* es la solucin ptima f(x*) >= f(x), para todo x factible. -f(x*) <=
- f(x), para todo x factible. En consecuencia: x* es tambin mnimo de -f(x)
Cada restriccin del tipo <= puede ser llevada a una ecuacin de igualdad usando una (nueva)
variable deholgura no negativa, con coeficiente nulo en la funcin objetivo.
Cada restriccin del tipo >= puede ser llevada a una ecuacin de igualdad usando una (nueva)
variable deexceso no negativa, con coeficiente nulo en la funcin objetivo.
Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no
negativas.
Considerando la siguiente notacin: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el
problema P) puede ser escrito en forma equivalente como:
Min
sa:
- 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
4x1 + 3x2 + 6x3 - 6x4 +
x5
= 50
x1 + 2x2 - 3x3 + 3x4
- x6 = 8
2x1 - 4x2 + x3 - x4
= 5
xi >= 0,
i=1,2,3,4,5,6.
Ejemplo
Resolver el siguiente problema de Programacin Lineal utilizando el Mtodo Simplex:
Max
40*X1 + 60*X2
s.a.
2*X1 + 1*X2 <= 70
1*X1 + 1*X2 <= 40
1*X1 + 3*X2 <= 90
X1
>=
X2
>=
Para poder aplicar el Mtodo Simplex, es necesario llevar el modelo a su formato estndar, para lo cual
definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restriccin 1, 2 y 3. De esta
forma queda definida la tabla inicial del mtodo de la siguiente forma:
X1
X2
X3 X4 X5
0 70
40
90
1 ..... 3
-40 -60
En esta situacin, las variables de holgura definen una solucin bsica factible inicial, condicin
necesaria para la aplicacin del mtodo. Luego, se verifican los costos reducidos de las variables no
bsicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo
reducido
"ms
negativo".
En
este
caso, X2.
Luego, para escoger que variable bsica deja la base debemos buscar el mnimo cuociente entre el lado
derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0
marcados en rojo en la tabla anterior). El mnimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la
tercera fila, el cual corresponde a la variable bsica actual X5, en consecuencia, X5 deja la base. En la
posicin que se alcanza el mnimo cuociente lo llamaremos"Pivote" (marcado con azul) el cual nos
servir para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteracin.
X1 X2 X3 X4 X5
5/3 0
-1/3
40
2/3 0
-1/3
10
1/3 1
1/3
30
-20 0
20
1.800
El valor de la funcin objetivo luego de una iteracin ha pasado de 0 a 1.800. Se recomienda al lector
hacer una representacin grfica del problema y notar como las soluciones factibles del mtodo
corresponden
a
vrtices
del
dominio
de
puntos
factibles.
La actual tabla no corresponde a la solucin ptima del problema P) debido a que existe una variable no
bsica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del
mnimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15,
asociado a la fila 2 (variable bsica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica
una iteracin del mtodo:
X1 X2 X3 X4
X5
-5/2 1/2
15
3/2 -1/2
15
-1/2 1/2
25
30
10
2.100
Finalmente se alcanza la solucin ptima del problema P) y se verifica que los costos reducidos
asociados a las variables no bsicas (X4 y X5 son mayores o iguals que cero). Notse que la existencia
de un costo reducido igual a cero para una variable no bsica en esta etapa define un problema con
"infinitas
soluciones".
La solucin alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos
asociados a las variables no bsicas definen el precio sombra asociado a las restricciones 1, 2 y 3,
respectivamente, lo cual es equivalente a la obtencin del precio sombra mediante el mtodo grfico.
Dejaremos para una posterior presentacin, la forma de calcular el intervalo de variacin para el lado
derecho que permite la validez del precio sombra, utilizando la tabla final del Mtodo Simplex.
METODO
SIMPLEX
DE
FASES
Esta estrategia se utiliza cuando no es inmediata una solucin bsica factible inicial en las variables
originales
del
modelo.
FASE
Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del
problema, de modo de obtener una solucin bsica factible. Resolver por Simplex un problema que
considera como funcin objetivo la suma de las variables auxiliares. Si el valor ptimo es cero, seguir a la
Fase
II,
en
caso
contrario,
no
existe
solucin
factible.
FASE
II
Resolver por Simplex el problema original a partir de la solucin bsica factible inicial hallada en la Fase
I.
EJEMPLO
P)
Max
2X1 + X2
sa
10X1 + 10X2 <= 9
10X1 + 5X2 >= 1
X1,
X2 >= 0
Se debe agregar X3 como variable de holgura de la restriccin 1, X4 como variable de exceso de la
restriccin 2 y X5 variable auxiliar para poder comenzar la Fase 1.
F1)
Min
X5
sa
10X1 + 10X2 + X3
10X1 + 5X2
= 9
- X4 + X5 = 1
X1, X2, X3, X4, X5 >= 0
La tabla inicial asociada a la Fase I queda en consecuencia definida de la siguiente forma:
X1
10
10
0
X2
10
5
0
X3
1
0
0
X4
0
-1
0
X5
0 9
1 1
1 0
Luego, se debe hacer 0 el costo reducido de X5, obteniendo la siguiente tabla inicial para hacer el uso de
Simplex:
X1
10
10
10
X2 X3 X4 X5
10 1 0 0 9
5 0 -1 1 1
-5 0 1 0
1
Se escoge X1 como variable que entra a la base al tener el costo reducido ms negativo. Posteriormente,
mediante el criterio del mnimo cuociente se selecciona la variable que sale de la base: Min {9/10; 1/10} =
1/10, X5 sale de la base.
X1 X2 X3 X4 X5
0 5 1
1
-1
8
1 1/2 0
1/10 1/10
1/10
0 0 0
0
1
0
Una vez obtenida la solucin ptima de la Fase I, con valor ptimo cero, tomamos X1 y X3 como
variables bsicas iniciales para la Fase II.
X1 X2 X3
0
1 1/2 0
-2 -1
X4
1
1/10
1/10
0
Hacemos cero los costos reducidos de las variables bsicas:
X1 X2 X3 X4
0 5 1
1
8
1 1/2 0
1/10
1/10
0 -1/5 1/5
X4 entra a la base. Por el criterio del mnimo cuociente, el pivote se encuentra en la fila 1, por
tanto X3 sale de la base.
X1 X2
Donde la solucin ptima es: X1=9/10
X3
X4
1/10
9/10
1/5
9/5
X2=0
Con valor ptimo V(P) = 9/5
Unos grandes almacenes encargan a un fabricante pantalones y chaquetas
deportivas.
El fabricante dispone para la confeccin de 750 m de tejido de algodn y 1000 m
de tejido de polister. Cada pantaln precisa 1 m de algodn y 2 m de polister.
Para cada chaqueta se necesitan 1.5 m de algodn y 1 m de polister.
El precio del pantaln se fija en 50 y el de la chaqueta en 40 .
Qu nmero de pantalones y chaquetas debe suministrar el fabricante a los
almacenes para que estos consigan una beneficio mxima?
1 Eleccin de las incgnitas.
x = nmero de pantalones
y = nmero de chaquetas
2 Funcin objetivo
f(x,y)= 50x + 40y
3 Restricciones
Para escribir las restricciones vamos a ayudarnos de una tabla:
pantalones
chaquetas
disponible
algodn
1,5
750
polister
1000
x + 1.5y 750
2x+3y 1500
2x + y 1000
Como el nmero de pantalones y chaquetas son nmeros naturales, tendremos
dos restricciones ms:
x0
y0
4 Hallar el conjunto de soluciones factibles
Tenemos que representar grficamente las restricciones.
Al ser x 0 e y 0, trabajaremos en el primer cuadrante.
Representamos las rectas, a partir de sus puntos de corte con los ejes.
Resolvemos grficamente la inecuacin: x + 1.5y 750, para ello tomamos un
punto del plano, por ejemplo el (0,0).
0 + 1.5 0 750
0 750 entonces el punto (0,0) se encuentra en el semiplano donde se cumple la
desigualdad.
De modo anlogo resolvemos 2x + y 1000.
2 0 + 0 1 000
La zona de interseccin de las soluciones de las inecuaciones sera la solucin al
sistema de inecuaciones, que constituye el conjunto de las soluciones factibles.
5 Calcular las coordenadas de los vrtices del recinto de las soluciones
factibles.
La solucin ptima, si es nica, se encuentra en un vrtice del recinto. Estas son
las soluciones a los sistemas:
2x + 3y = 1500; x = 0 (0, 500)
2x + y = 1000; y = 0 (500, 0)
2x + 3y =1500; 2x + y = 1000 (375, 250)
6 Calcular el valor de la funcin objetivo
En la funcin objetivo sustituimos cada uno de los vrtices.
f(x, y) = 50x + 40y
f(0, 500) = 50 0 + 40 500 = 20 000
f(500, 0) = 50 500 + 40 0 = 25 000
f(375, 250) = 50 375 + 40 250 = 28 750
Mximo
La solucin ptima es fabricar 375 pantalones y 250 chaquetas para obtener
un beneficio de 28750 .
Solucin mltiple
La solucin no siempre es nica, tambin podemos encontrarnos con una
solucin mltiple.
Si la funcin objetivo del ejercicio anterior hubiese sido:
f(x,y)= 20x + 30y
f(0,500) = 20 0 + 30 500 = 15 000
f(500, 0) = 20 500 + 30 0 = 10 000
Mximo
f(375, 250) = 20 375 + 30 250 = 15 000
Mximo
En este caso todos los pares, con soluciones enteras, del segmento trazado en
negro seran mximos.
f(300, 300)= 20 300 + 30 300 = 15 000
Mximo
1 Una compaa fabrica y venden dos modelos de lmpara L 1 y L 2 . Para su
fabricacin se necesita un trabajo manual de 20 minutos para el modelo L 1 y de
30 minutos para el L 2 ; y un trabajo de mquina para L 1 y de 10 minutos para
L 2 . Se dispone para el trabajo manual de 100 horas al mes y para la mquina
80 horas al mes. Sabiendo que el beneficio por unidad es de 15 y 10 euros
para L 1 y L 2 , respectivamente, planificar la produccin para obtener el mximo
beneficio.
2 Con el comienzo del curso se va a lanzar unas ofertas de material escolar.
Unos almacenes quieren ofrecer 60 0 cuadernos, 500 carpetas y 400 bolgrafos
para la oferta, empaquetndolo de dos formas distintas; en el primer bloque
pondr 2 cuadernos, 1 carpeta y 2 bolgrafos; en el segundo, pondrn 3
cuadernos, 1 carpeta y 1 bolgrafo. Los precios de cada paquete se rn 6.5 y 7
, respectivamente. Cuntos paquetes le conviene poner de cada tipo para
obtener el mximo beneficio?
3 En
una
granja
de
pollos
se
da
una
dieta,
para
engordar,
con
una
composicin mnima de 15 unidades de una sustancia A y otras 15 de una
sustancia B. En el mercado slo se encuentra dos clases de compuestos: el tipo
X con una composicin de una unidad de A y 5 de B, y el otro tipo, Y, con una
composicin de cinco unidades de A y una de B. El precio del tipo X es de 10
euros y del tipo Y es de 30 . Qu cantidades se han de comprar de cada tipo
para cubrir las necesidades con un coste mnimo?
4 Se dispone de 600 g de un determinado frmaco para elaborar pastillas
grandes y pequeas. Las grandes pesan 40 g y las pequeas 30 g. Se necesitan
al menos tres pastillas grandes, y al menos el doble de pequeas que de las
grandes. Cada pastilla grande proporciona un beneficio de 2 y la pequea de
1 . Cuntas pastillas se han de elaborar de cada clase para que el beneficio
sea mximo?
5 Unos grandes almacenes desean liquidar 200 camisas y 100 pantalones de
la temporada anterior. Para ello lanzan, dos ofertas, A y B. La oferta A consiste
en un lote de una camisa y un pantaln, que se venden a 30 ; la oferta B
consiste en un lote de tres camisas y un pantal n, que se vende a 50 . No se
desea ofrecer menos de 20 lotes de la oferta A ni menos de 10 de la B.
Cuntos lotes ha de vender de cada tipo para maximizar la ganancia?
Ejercicio 1 resuelto
Una compaa fabrica y venden dos modelos de lmpara L 1 y L 2 . Para su
fabricacin se necesita un trabajo manual de 20 minutos para el modelo
L 1 y de 30 minutos para el L 2 ; y un trabajo de mquina para L 1 y de 10
minutos para L 2 . Se dispone para el trabajo manual de 100 horas al mes y
para la mquina 80 horas al mes. Sabiendo que el beneficio por unidad es
de 15 y 10 euros para L 1 y L 2 , respectivamente, planificar la produccin
para obtener el mximo beneficio.
1 Eleccin de las incgnitas.
x = n de lmparas L 1
y = n de lmparas L 2
2 Funcin objetivo
f(x, y) = 15 x + 10y
3 Restricciones
Pasamos los tiempos a horas
20 min = 1/3 h
30 min = 1/2 h
10 min = 1/6 h
Para escribir las restricciones vamos a ayudarnos de una tabla:
L1
L2
Tiempo
Manual
1/3
1/2
100
Mquina
1/3
1/6
80
1/3x + 1/2y 100
1/3x + 1/6y 80
Como el nmero de lmparas son nmeros naturales, tendremos dos
restricciones ms:
x 0
y 0
4 Hallar el conjunto de soluciones factibles
Tenemos que representar grficamente las restricciones.
Al ser x 0 e y 0, trabajaremos en el primer cuadrante.
Representamos las rectas, a partir de sus puntos de corte con los ejes.
Resolvemos grficamente la inecuacin: 1/3 x + 1/2 y 100; para ello
tomamos un punto del plano, por ejemplo el (0,0).
1/30 + 1/20 100
1/30 + 1/60 80
La zona de interseccin de las soluciones de las inecuaciones sera la
solucin al sistema de inecuaciones, que constituye el conjunto de las
soluciones factibles.
5 Calcular las coordenadas de los vrtices del recinto de las soluciones
factibles.
La solucin ptima si es ni ca se encuentra en un vrtice del recinto.
estos son las soluciones a los sistemas:
1/3x + 1/2y = 100; x = 0 (0, 200)
1/3x + 1/6y = 80; y = 0(240, 0)
1/3x + 1/2y = 100; 1/3x + 1/6y = 80(210, 60)
6 Calcular el valor de la funcin objetivo
En la funcin objetivo sustituimos cada uno de los vrtices.
f(x, y) = 15x + 10y
f(0, 200) = 150 + 10200 = 2 000
f(240, 0 ) = 15240 + 100 = 3 600
f(210, 60) = 15210 + 1060 = 3 750
Mximo
La solucin ptima es fabricar 210 del modelo L 1 y 60 del modelo
L 1 para obtener un beneficio de 3 750 .
jercicio 2 resuelto
Con el comienzo del curso se va a lanzar unas ofertas de material escolar.
Unos almacenes quieren ofrecer 600 cuadernos, 500
carpetas y 400
bolgrafos para la oferta, empaquetndolo de do s formas distintas; en el
primer bloque
pondr 2
cuadernos, 1
carpeta y 2 bolgrafos; en el
segundo, pondrn 3 cuadernos, 1 carpeta y 1 bolgrafo. Los precios de
cada paquete sern 6.5 y 7 , respectivamente. Cuntos paquetes le
conviene poner de cada tip o para obtener el mximo beneficio?
1 Eleccin de las incgnitas.
x = P1
y = P2
2 Funcin objetivo
f(x, y) = 6.5x + 7y
3 Restricciones
Cuadernos
P1
P2
Disponibles
600
Carpetas
500
Bolgrafos
400
2x + 3y 600
x + y 500
2x + y 400
x 0
y 0
4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones
factibles.
6 Calcular el valor de la funcin objetivo
f(x,y) = 6.5 200 + 7 0 = 1300
f(x,y)= 6.5 0 + 7 200 = 1 400
f(x,y)= 6.5 150 + 7 100 = 1 675
Mximo
La solucin ptima son 150 P 1 y 100 P 2 con la que se obtienen 1 675
jercicio 3 resuelto
En
una
granja
de
pollos
se
da
una
dieta,
para
engordar,
con
una
composicin mnima de 15 unidades de una sustancia A y otras 15 de una
sustancia B. En el mercado slo se encuentra dos clases de compuestos:
el tipo X con una composicin de una unidad de A y 5 de B, y el otro tipo,
Y, con una composicin de cinco unidades de A y una de B. El precio del
tipo X es de 10 euros y del tipo Y es de 30 . Qu cantidades se han de
comprar de cada tipo para cubrir las necesidades con un coste mnimo?
1 Eleccin de las incgnitas.
x = X
y = Y
2 Funcin objetivo
f(x,y) = 10x + 30y
3 Restricciones
Mnimo
15
15
x + 5y 15
5x + y 15
x 0
y 0
4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones
factibles.
6 Calcular el valor de la funcin objetivo
f(0, 15) = 10 0 + 30 15 = 450
f(15, 0) = 10 15 + 30 0 = 150
f(5/2, 5/2) = 10 5/2 + 30 5/2 = 100
Mnimo
El coste mnimo son 100 para X = 5/2 e Y = 5/2.
jercicio 4 resuelto
Se dispone de 600 g de un determinado frmaco para elaborar pastillas
grandes y pequeas. Las grandes pesan 40 g y las pequeas 30 g. Se
necesitan
al
menos
pequeas
que
de
tres
las
pastillas
grandes.
grandes,
Cada
pastilla
al
menos
grande
el
doble
de
pro porciona
un
beneficio de 2 y la pequea de 1 . Cuntas pastillas se han de
elaborar de cada clase para que el beneficio sea mximo?
1 Eleccin de las incgnitas.
x = Pastillas grandes
y = Pastillas pequeas
2 Funcin objetivo
f(x, y) = 2x + y
3 Restricciones
40x + 30y 600
x 3
y 2x
x 0
y 0
4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones
factibles.
6 Calcular el valor de la funcin objetivo
f(x, y) = 2 3 + 16 = 22
f(x, y) = 2 3 + 6 = 12
f(x, y) = 2 6 + 12 = 24
El
mximo
beneficio
es
Mximo
de 24
se
obtiene
fabricando 6
pastillas
grandes y 12 pequeas.
jercicio 5 resuelto
Unos grandes almacenes desean liquidar 200 camisas y 100 pantalones de
la temporada anterior. Para ello lanzan, dos ofertas, A y B. La oferta A
consiste en un lote de una camisa y un pantaln, que se venden a 30 ; la
oferta B consiste en un lote de tres camisas y un pantaln, que se vende
a 50 . No se desea ofrecer menos de 20 lotes de la oferta A ni menos de
10 de la B. Cuntos lotes ha de vender de cada tipo para maximizar la
ganancia?
1 Eleccin de las incgnitas.
x = n de lotes de A
y = n de lotes de B
2 Funcin objetivo
f(x, y) = 30x + 50y
3 Restricciones
Mnimo
Camisas
200
Pantalones
100
x + 3y 200
x + y 100
x 20
y 10
4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones
factibles.
6 Calcular el valor de la funcin objetivo
f(x, y) = 30 20 + 50 10 = 1100
f(x, y) = 30 90 + 50 10 = 3200
f(x, y) = 30 20 + 50 60 = 3600
f(x, y) = 30 50 + 50 50 = 4000
Mximo
Con 50 lotes de cada tipo se obtiene una ganancia mxima de 4000
