Mtodo simplex
Maximizar
La empresa maestro vende diversos tipos de productos, entre ellos paredes
prefabricadas (Dey Wall, Fibrocemento), se tiene los siguientes datos:
Disponibilidad del preparado 15000h/h
Disponibilidad de armado 9000h/h.
Disponibilidad de ensamblaje 7000h/h.
Adems se tiene que el lmite mximo de produccin es 600 Dey Wall (panel), y
450 Fibrocemento (panel).
Tambin el precio de venta de cada Dey Wall es $100.00, fibrocemento
$110.00; el precio de venta de cada Dey Wall es $70.00 y fibrocemento es
$90.00.
Hallar el ptimo?
Solucin:
A. Definicin de las variables de decisin
X1 = Cantidades a producir de Dey Wall.
X2 = Cantidades a producir de Fibrocemento.
B. Determinar la funcin objetivo
MAX (Z0 = 30 X1 + 20 X2)
C. Restricciones
30 X 1 +15 X 2 15000
10 X 1 +10 X 2 9000
12 X 1+ 10 X 2 7000
X 1 600
X 2 450
D. Convertir a ecuaciones
30 X 1 +15 X 2 + X 3=15000
10 X 1 +10 X 2 + X 4 =9000
12 X 1+ 10 X 2+ X 5=7000
X 1 + X 6 =600
X 2 + X 7 =450
E. 1er cuadro simplex
Ck
Cj
Xk
30
bi
F.
G. 2do cuadro simplex
H.
20
Mtodo simplex
Minimizar
La fbrica de cemento Lima SAC ubicada en Villamaria del Triunfo prepara
tipos de cemento:
Portland
Puzolanico
Cada tipo de cemento requiere de caliza L y puzolana natural calcinada Q
Solucin:
Materia prima
Tipo de cemento
Portland
Puzolanico
Precio produccin(S/.)
L
(tn)
2
3
3
Q
(tn
)
4
2
2.5
Disponibilidad
mnima requerida
(tn)
40
50
A. Definicin de las variables de decisin
X1 = Cantidades a producir de caliza L
X2 = Cantidades a producir de puzolana natural calcinada Q
B. Restricciones
2 X 1+4 X 2 40
3 X 1 +2 X 2 50
X1 X2 0
C. Convertir a ecuaciones
2 X 1+ 4 X 2X 3 =40
3 X 1 +2 X 2X 4=50
2 X 1+ 4 X 2X 3 + 1=40
3 X 1 +2 X 2X 4 + 2=50
MIN (Z 0=3 X 1 +2.5 X 2 +0 X 3 + 0 X 4 + M 1 + M 2 )
Sujeto a
2 X 1+ 4 X 2X 3 +0 X 4 + 1+ 0 2=40
3 X 1 +2 X 2 +0 X 3 X 4 +0 1 + 2 =50
D. 1er cuadro simplex
Elemen
to
Cj
Ck
Xk
bi
3
X1
40
-1
10
50
-1
25
90M
5M
6M
-M
-M
5M-3
6M-2.5
-M
-M
Zj
Z jC j
2.5
X2
0
X3
0
X4
0
1
0
2
b i / Xj
Menor
valor
cociente
Mayor valor positivo,
que se acerque a cero
(0)
Ck: Costos asociados a la variable decisin.
E. 2do cuadro simplex
Cj
Ck
Xk
Elemen
to
bi
3
X1
2.5
X2
0
X3
0
X4
0
1
0
2
b i / Xj
2.5
X2
10
1/2
-1/4
1/4
20
30
1/2
-1
-1/2
15
25+30M
5/4+2M
2.5
-5/8+M/2
-M
5/8-M/2
5/4+2M-3
-5/8+M/2
-M
5/8-M/2
Zj
Z jC j
b2=50
402
=30
4
X 21=3
22
=2
4
X 23=0
21
=1/2
4
X 24=1
20
=1
4
21=0
21
=1/2
4
22=1
20
=1
4
F. 3er cuadro simplex
Cj
Ck
Xk
bi
3
X1
2.5
X2
0
X4
0
1
0
2
X3
2.5
X2
5/2
-3/8
1/4
3/8
1/4
X1
15
1/4
-1/2
-1/4
1/2
Zj
Z jC j
b=10
301 /2
=5 /2
2
X 12=1
01/2
=1
2
X 13=1/4
X 24=0
1/21
=1/4
2
11=1/4
22=1
1/21/2
=3/8
2
1/21/2
=3/8
2
1 /21
=1 /4
2
Interpretacin:
Para minimizar mis costos debo producir:
2.5 de portland
15 de puzolanico minimizando mis costos a 51.25
Pasamos el problema a la forma estndar, aadiendo variables de exceso, holgura, y
artificiales segn corresponda (mostrar/ocultar detalles)
Como la restriccin 1 es del tipo '' se agrega la variable de holgura X3.
Como la restriccin 2 es del tipo '' se agrega la variable de holgura X4.
Como la restriccin 3 es del tipo '' se agrega la variable de holgura X5.
Como la restriccin 4 es del tipo '' se agrega la variable de holgura X6.
Como la restriccin 5 es del tipo '' se agrega la variable de holgura X7.
MAXIMIZAR: 30
X1 + 20 X2
30 X1 + 15 X2
15000
10 X1 + 10 X2
9000
12 X1 + 10 X2
7000
1 X1 + 0 X2 600
0 X1 + 1 X2 450
X1, X2 0
MAXIMIZAR: 30 X1 + 20 X2 +
0 X3 + 0 X4 + 0 X5 + 0 X6 + 0
X7
30 X1 + 15 X2 + 1 X3 = 15000
10 X1 + 10 X2 + 1 X4 = 9000
12 X1 + 10 X2 + 1 X5 = 7000
1 X1 + 1 X6 = 600
0 X1 + 1 X2 + 1 X7 = 450
X1, X2, X3, X4, X5, X6, X7 0
Pasamos a construir la primera tabla del mtodo Simplex.
Mtodo Simplex
Tabla 1
30
20
Base Cb
P0
P1
P2
P3
P4
P5
P6
P7
P3
15000 30
15
P4
9000 10
10
P5
7000 12
10
P6
600
P7
450
-30
-20
Mostrar resultados como fracciones.
La variable que sale de la base es P3 y la que entra es P1.
Operaciones intermedias (mostrar/ocultar detalles)
Fila pivote (Fila 1):
15000 / 30 = 500
30 / 30 = 1
15 / 30 = 1 / 2
1 / 30 = 1 / 30
0 / 30 = 0
0 / 30 = 0
0 / 30 = 0
0 / 30 = 0
Fila 2:
9000 - (10 * 500) = 4000
10 - (10 * 1) = 0
10 - (10 * 1 / 2) = 5
0 - (10 * 1 / 30) = -1 / 3
1 - (10 * 0) = 1
0 - (10 * 0) = 0
0 - (10 * 0) = 0
0 - (10 * 0) = 0
Fila 3:
7000 - (12 * 500) = 1000
12 - (12 * 1) = 0
10 - (12 * 1 / 2) = 4
0 - (12 * 1 / 30) = -2 / 5
0 - (12 * 0) = 0
1 - (12 * 0) = 1
0 - (12 * 0) = 0
0 - (12 * 0) = 0
Fila 4:
600 - (1 * 500) = 100
1 - (1 * 1) = 0
0 - (1 * 1 / 2) = -1 / 2
0 - (1 * 1 / 30) = -1 / 30
0 - (1 * 0) = 0
0 - (1 * 0) = 0
1 - (1 * 0) = 1
0 - (1 * 0) = 0
Fila 5:
450 - (0 * 500) = 450
0 - (0 * 1) = 0
1 - (0 * 1 / 2) = 1
0 - (0 * 1 / 30) = 0
0 - (0 * 0) = 0
0 - (0 * 0) = 0
0 - (0 * 0) = 0
1 - (0 * 0) = 1
Fila Z:
0 - (-30 * 500) = 15000
-30 - (-30 * 1) = 0
-20 - (-30 * 1 / 2) = -5
0 - (-30 * 1 / 30) = 1
0 - (-30 * 0) = 0
0 - (-30 * 0) = 0
0 - (-30 * 0) = 0
0 - (-30 * 0) = 0
Tabla 2
30
20
P4
P5
P6
P7
Base Cb
P0
P1
P2
P3
P1
30
500
1/2
1 / 30 0
P4
4000 0
-1 / 3 1
P5
1000 0
-2 / 5 0
P6
100
-1 / 2 -1 / 30 0
P7
450
-5
15000 0
Mostrar resultados como fracciones.
La variable que sale de la base es P5 y la que entra es P2.
Operaciones intermedias (mostrar/ocultar detalles)
Fila pivote (Fila 3):
1000 / 4 = 250
0/4=0
4/4=1
-2 / 5 / 4 = -1 / 10
0/4=0
1/4=1/4
0/4=0
0/4=0
Fila 1:
500 - (1 / 2 * 250) = 375
1 - (1 / 2 * 0) = 1
1 / 2 - (1 / 2 * 1) = 0
1 / 30 - (1 / 2 * -1 / 10) = 1 / 12
0 - (1 / 2 * 0) = 0
0 - (1 / 2 * 1 / 4) = -1 / 8
0 - (1 / 2 * 0) = 0
0 - (1 / 2 * 0) = 0
Fila 2:
4000 - (5 * 250) = 2750
0 - (5 * 0) = 0
5 - (5 * 1) = 0
-1 / 3 - (5 * -1 / 10) = 1 / 6
1 - (5 * 0) = 1
0 - (5 * 1 / 4) = -5 / 4
0 - (5 * 0) = 0
0 - (5 * 0) = 0
Fila 4:
100 - (-1 / 2 * 250) = 225
0 - (-1 / 2 * 0) = 0
-1 / 2 - (-1 / 2 * 1) = 0
-1 / 30 - (-1 / 2 * -1 / 10) = -1 / 12
0 - (-1 / 2 * 0) = 0
0 - (-1 / 2 * 1 / 4) = 1 / 8
1 - (-1 / 2 * 0) = 1
0 - (-1 / 2 * 0) = 0
Fila 5:
450 - (1 * 250) = 200
0 - (1 * 0) = 0
1 - (1 * 1) = 0
0 - (1 * -1 / 10) = 1 / 10
0 - (1 * 0) = 0
0 - (1 * 1 / 4) = -1 / 4
0 - (1 * 0) = 0
1 - (1 * 0) = 1
Fila Z:
15000 - (-5 * 250) = 16250
0 - (-5 * 0) = 0
-5 - (-5 * 1) = 0
1 - (-5 * -1 / 10) = 1 / 2
0 - (-5 * 0) = 0
0 - (-5 * 1 / 4) = 5 / 4
0 - (-5 * 0) = 0
0 - (-5 * 0) = 0
Tabla 3
Base
P1
P4
P2
P6
P7
Z
Cb
30
0
20
0
0
30
P1
1
0
0
0
0
0
P0
375
2750
250
225
200
16250
20
P2
0
0
1
0
0
0
0
P3
1 / 12
1/6
-1 / 10
-1 / 12
1 / 10
1/2
0
P4
0
1
0
0
0
0
0
P5
-1 / 8
-5 / 4
1/4
1/8
-1 / 4
5/4
0
P6
0
0
0
1
0
0
Mostrar resultados como fracciones.
La solucin ptima es Z = 16250
X1 = 375
X2 = 250
Resolver mediante el mtodo simplex el siguiente problema:
Maximizar
sujeto a:
Z = f(x,y) = 3x + 2y
2x + y 18
2x + 3y 42
3x + y 24
x0,y0
Se consideran las siguientes fases:
1. Realizar un cambio de variables y normalizar el signo de los trminos
independientes.
0
P7
0
0
0
0
1
0
Se realiza un cambio en la nomenclatura de las variables. Establecindose la
correspondencia siguiente:
o x pasa a ser X1
o y pasa a ser X2
Como los trminos independientes de todas las restricciones son positivos no es
necesario hacer nada. En caso contrario habra que multiplicar por "-1" en
ambos lados de la inecuacin (teniendo en cuenta que esta operacin tambin
afecta al tipo de restriccin).
2. Normalizar las restricciones.
Se convierten las inecuaciones en ecuaciones agregando variables de holgura,
exceso y artificiales segn la tabla siguiente:
Tipo de desigualdad
Tipo de variable que aparece
- exceso + artificial
+ artificial
+ holgura
En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de
las restricciones del tipo , para convertirlas en igualdades, resultando el sistema
de ecuaciones lineales:
2X1 + X2 + X3 = 18
2X1 + 3X2 + X4 = 42
3X1 + X2 + X5 = 24
3. Igualar la funcin objetivo a cero.
Z - 3X1 - X2 - 0X3 - 0X4 - 0X5 = 0
4. Escribir la tabla inicial del mtodo Simplex.
La tabla inicial del mtodo Simplex est compuesta por todos los coeficientes de
las variables de decisin del problema original y las de holgura, exceso y
artificiales agregadas en el paso 2 (en las columnas, siendo P0 el trmino
independiente y el resto de variables Pi coinciden con Xi), y las restricciones (en
las filas). La columna Cb contiene los coeficientes de las variables que se
encuentran en la base.
La primera fila est formada por los coeficientes de la funcin objetivo, mientras
que la ltima fila contiene el valor la funcin objetivo y los costes reducidos Zj Cj.
La ltima fila se calcula como sigue: Zj = (CbiPj) para i = 1..m, donde si j = 0,
P0 = bi y C0 = 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera
tabla del mtodo Simplex y ser todos los Cb nulos se puede simplificar el
clculo, y por esta vez disponer Zj = -Cj.
Base
P3
P4
P5
Z
Cb
0
0
0
P0
18
42
24
0
Tabla I . Iteracin n 1
3
2
P1
P2
2
1
2
3
3
1
-3
-2
0
P3
1
0
0
0
0
P4
0
1
0
0
0
P5
0
0
1
0
5. Condicin de parada.
Si el objetivo es la maximizacin, cuando en la ltima fila (fila indicadora) no
existe ningn valor negativo entre los costes reducidos (columnas P1 en
adelante) se alcanza la condicin de parada.
En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora.
El valor de Z (columna P0) es la solucin ptima del problema.
Otro caso posible es que en la columna de la variable entrante a la base todos los
valores son negativos o nulos. Esto indica que el problema no se encuentra
acotado y su solucin siempre resultar mejorable. Ante esta situacin no es
necesario continuar iterando indefinidamente y tambin se puede dar por
finalizado el algoritmo.
De no ser as, se ejecutan los siguientes pasos de forma iterativa.
6. Eleccin de la variable entrante y saliente de la base.
Se determina en primer lugar la variable que entra en la base. Para ello se escoge
la columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En
este caso sera la variable X1 (P1) de coeficiente -3.
Si existiesen dos o ms coeficientes iguales que cumplan la condicin anterior
(caso de empate), entonces se optar por aquella variable que sea bsica.
La columna de la variable que entra en la base se llama columna pivote (en color
verde).
Una vez obtenida la variable que entra en la base, se procede a determina cual
ser la variable que sale de la misma. La decisin se toma en base a un sencillo
clculo: dividir cada trmino independiente (columna P0) entre el elemento
correspondiente de la columna pivote, siempre que ambos elementos sean
estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado haya
resultado mnimo.
Si hubiera algn elemento menor o igual a cero no se realiza dicho cociente. En
caso de que todos los elementos de la columna pivote fueran de sta condicin
se habra cumplido la condicin de parada y el problema tendra una solucin no
acotada (ver teora del mtodo Simplex).
En este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]
El trmino de la columna pivote que en la divisin anterior dio lugar al menor
cociente positivo indica la fila de la variable de holgura que sale de la base. En
este caso resulta ser X5 (P5), de coeficiente 3. Esta fila se llama fila pivote (en
color verde).
Si al calcular los cocientes, dos o ms resultados cumplen la condicin para
elegir el elemento saliente de la base (caso de empate), se escoge aquella que no
sea variable bsica (siempre que sea es posible).
La interseccin de la fila pivote y columna pivote marca el elemento pivote, en
este caso el 3.
7. Actualizar la tabla.
Los nuevos coeficientes de la tabla se calculan de la siguiente manera:
o En la fila del elemento pivote cada nuevo elemento se calcula como:
Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote
o En el resto de las filas cada elemento se calcula:
Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento
Fila en Columna Pivote * Nuevo Elemento Fila Pivote)
Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el
resto de elementos de la columna pivote se anulan (anlogo al mtodo de GaussJordan).
Se muestran a continuacin los clculos para la fila P4:
Anterior fila P4
Anterior Elemento Fila en Columna Pivote
Nueva fila pivote
Nueva fila P4
42
2
x
8
=
26
La tabla correspondiente a esta segunda iteracin es:
2
2
x
1
=
0
3
2
x
1/3
=
7/3
0
2
x
0
=
0
1
2
x
0
=
1
0
2
x
1/3
=
-2/3
Base
P3
P4
P1
Z
Cb
0
0
3
P0
2
26
8
24
Tabla II . Iteracin n 2
3
2
0
P1
P2
P3
0
1/3
1
0
7/3
0
1
1/3
0
0
-1
0
0
P4
0
1
0
0
0
P5
-2/3
-2/3
1/3
1
8. Al comprobar la condicin de parada se observa que no se cumple ya que entre
los elementos de la ltima fila hay uno negativo, -1. Se contina iterando
nuevamente los pasos 6 y 7.
o 6.1. La variable que entra en la base es X2 (P2), por ser la variable que
corresponde a la columna donde se encuentra el coeficiente -1.
o 6.2. Para calcular la variable que sale, se dividen los trminos de la
columna P0 entre los trminos correspondientes de la nueva columna
pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el menor
cociente positivo es 6, la variable que sale de la base es X3 (P3).
o 6.3. El elemento pivote es 1/3.
o 7. Actualizando nuevamente los valores de la tabla se obtiene:
Base
P2
P4
P1
Z
Cb
2
0
3
Tabla III . Iteracin n 3
3
2
P0
P1
P2
6
0
1
12
0
0
6
1
0
30
0
0
0
P3
3
-7
-1
3
0
P4
0
1
0
0
9. Una nueva comprobacin de la condicin de parada revela que entre los
elementos de la fila indicadora vuelve a haber uno negativo, -1. Significa que
aun no se ha llegado a la solucin ptima y hay que seguir iterando (pasos 6 y
7):
o 6.1. La variable que entra en la base es X5 (P5), por ser la variable que
corresponde al coeficiente -1.
o 6.2. Se escoge la variable que sale calculando el cociente entre los
trminos de la columna de trminos independientes y los trminos
correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y
6/1 [=6]. En esta ocasin es X4 (P4).
o 6.3. El elemento pivote es 4.
o 7. Despus de actualizar todas las filas, se obtiene la tabla siguiente:
0
P5
-2
4
1
-1
Base
P2
P5
P1
Z
Cb
2
0
3
Tabla IV . Iteracin n 4
3
2
0
P1
P2
P3
0
1
-1/2
0
0
-7/4
1
0
3/4
0
0
5/4
P0
12
3
3
33
0
P4
1/2
1/4
-1/4
1/4
10. Fin del algoritmo.
Se observa que en la ltima fila todos los coeficientes son positivos
cumplindose, por tanto la condicin de parada.
La solucin ptima viene dada por el valor de Z en la columna de los trminos
independientes (P0), en este ejemplo: 33. En la misma columna se puede ver el
punto donde se alcanza, observando las filas correspondientes a las variables de
decisin que han entrado en la base: X1 = 3 y X2 = 12.
Deshaciendo el cambio de variables se obtiene x = 3 e y = 12.
Pasamos el problema a la forma estndar, aadiendo variables de exceso, holgura, y
artificiales segn corresponda (mostrar/ocultar detalles)
Como la restriccin 1 es del tipo '' se agrega la variable de exceso X3 y la
variable artificial X5.
Como la restriccin 2 es del tipo '' se agrega la variable de exceso X4 y la
variable artificial X6.
MINIMIZAR: 3 X1
+ 2.5 X2
2 X1 + 4 X2 50
3 X1 + 2 X2 40
X1, X2 0
MAXIMIZAR: -3 X1 -2.5 X2 + 0
X3 + 0 X4 + 0 X5 + 0 X6
2 X1 + 4 X2 -1 X3 + 1 X5 = 50
3 X1 + 2 X2 -1 X4 + 1 X6 = 40
X1, X2, X3, X4, X5, X6 0
Pasamos a construir la primera tabla de la Fase I del mtodo de las Dos Fases.
Tabla 1
-1
-1
0
P5
0
1
0
0
Base Cb
P0
P1
P2
P3
P4
P5
P6
P5
-1
50
-1
P6
-1
40
-1
-90
-5
-6
Mostrar resultados como fracciones.
La variable que sale de la base es P5 y la que entra es P2.
Operaciones intermedias (mostrar/ocultar detalles)
Fila pivote (Fila 1):
50 / 4 = 25 / 2
2/4=1/2
4/4=1
-1 / 4 = -1 / 4
0/4=0
1/4=1/4
0/4=0
Fila 2:
40 - (2 * 25 / 2) = 15
3 - (2 * 1 / 2) = 2
2 - (2 * 1) = 0
0 - (2 * -1 / 4) = 1 / 2
-1 - (2 * 0) = -1
0 - (2 * 1 / 4) = -1 / 2
1 - (2 * 0) = 1
Fila Z:
-90 - (-6 * 25 / 2) = -15
-5 - (-6 * 1 / 2) = -2
-6 - (-6 * 1) = 0
1 - (-6 * -1 / 4) = -1 / 2
1 - (-6 * 0) = 1
0 - (-6 * 1 / 4) = 3 / 2
0 - (-6 * 0) = 0
Tabla 2
-1
P2
P3
P4
P5
P6
0
Base Cb
P0
P2
25 / 2 1 / 2
-1 / 4 0
1/4
P6
-1
15
1/2
-1 / 2 1
-15
-2
-1 / 2 1
P1
-1
3/2
Mostrar resultados como fracciones.
La variable que sale de la base es P6 y la que entra es P1.
Operaciones intermedias (mostrar/ocultar detalles)
Fila pivote (Fila 2):
15 / 2 = 15 / 2
2/2=1
0/2=0
1/2/2=1/4
-1 / 2 = -1 / 2
-1 / 2 / 2 = -1 / 4
1/2=1/2
Fila 1:
25 / 2 - (1 / 2 * 15 / 2) = 35 / 4
1 / 2 - (1 / 2 * 1) = 0
-1
1 - (1 / 2 * 0) = 1
-1 / 4 - (1 / 2 * 1 / 4) = -3 / 8
0 - (1 / 2 * -1 / 2) = 1 / 4
1 / 4 - (1 / 2 * -1 / 4) = 3 / 8
0 - (1 / 2 * 1 / 2) = -1 / 4
Fila Z:
-15 - (-2 * 15 / 2) = 0
-2 - (-2 * 1) = 0
0 - (-2 * 0) = 0
-1 / 2 - (-2 * 1 / 4) = 0
1 - (-2 * -1 / 2) = 0
3 / 2 - (-2 * -1 / 4) = 1
0 - (-2 * 1 / 2) = 1
Tabla 3
-1
P2
P3
P4
P5
P6
3/8
-1 / 4
Base Cb
P0
P2
35 / 4 0
-3 / 8 1 / 4
P1
15 / 2 1
1/4
-1 / 2 -1 / 4 1 / 2
P1
-1
Mostrar resultados como fracciones.
Existe alguna solucin posible para el problema, por lo que podemos pasar a la
Fase II para calcularla.
