metodo SIMPLEX

Vista previa del material en texto

Unidad 3 
 
 
 
 
 
 
 
 Método Simplex 
 
 
 
 
 
 
 

Programación Lineal 
 Solución mediante el método Simplex 
 La resolución gráfica es una excelente herramienta para 
entender claramente el problema. 
 Sin embargo está limitada a problemas con 2 variables. 
 En esta parte vamos a analizar la resolución 
matemática del problema de programación lineal, con 
un método matricial denominado Método Simplex. 
 La ventaja del Simplex es que no tiene limitaciones 
respecto a la cantidad de variables y es una 
metodología muy mecánica por lo que resulta fácil su 
sistematización. 
Método Simplex 
 
 
 
 
 Vamos a aplicar el mismo ejemplo de las conservas para explicar el 
método.
 El primer paso para una resolución matemática es transformar las 
inecuaciones en ecuaciones.
 Cuando estamos frente a inecuaciones del tipo “menor o igual a …” 
debemos agregar algo en el término que es menor para representar la 
igualdad:
2𝑥1 + 1𝑥2 + 𝑥3 = 1200 Cantidad de fruta 
3𝑥1 + 4𝑥2+𝑥4= 2400 Tiempo de producción 
𝑥1 + 𝑥2 + 𝑥5 = 800 Limite producción total 
𝑥1 − 𝑥2 + 𝑥6 = 450 Producción en exceso 
Método Simplex 
 
 
 
 Las variables agregadas 𝑥3, 𝑥4, 𝑥5 y 𝑥6 se denominan variables “Slack” 
o variables de holgura y cuyo valor, en el caso que sea distinto de 
cero, va a representar el recurso no consumido o en exceso para la 
solución final.
 
 El valor de beneficio o costo de estas variables es cero.
 
 Por ello la función objetivo para este ejemplo, quedaría expresada 
como:
 
𝑧 = 800 𝑥1 + 500 𝑥2 + 0 𝑥3 + 0 𝑥4 + 0 𝑥5 + 0 𝑥6 
Método Simplex 
 
 
 
 
 Nuestro segundo paso es construir la matriz Simplex
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
 
 
 
 
 zj 
zj-cj 
 
 La primera fila (Cj) la integran los coeficientes de la función objetivo
 La primer columna (xk) nos indicará cuáles son las variables que se encuentran en 
la solución propuesta.
 La segunda (Ck) columna la integran los coeficientes de beneficio o costo 
asociados a cada variable xk
Método Simplex 
 
 
 
 
 Nuestro segundo paso es construir la matriz Simplex
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
 
 
 
 
 zj 
zj-cj 
 
 La tercer columna (B) la integra la disponibilidad de cada recurso
 A partir de la cuarta se agregan tantas columnas como variables tenemos (Aj)
 La última columna (θ) es un factor de decisión que luego explicaremos.
Método Simplex 
 
 
 
 
 Nuestro segundo paso es construir la matriz Simplex
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
 
 
 
 
 zj 
zj-cj 
 
 Se agregan tantas filas como restricciones tenemos. En este caso 4.
 La penúltima fila (zj) no entregará la ganancia (si maximizo) o costo (si minimizo) 
en su valor total y en cuanto al aporte de cada variable.
 La última fila (zj-cj) nos va brindar la mejora marginal que cada variable producirá 
al pasar a ser parte de la iteración siguiente.
Método Simplex 
 
 
 
 
 El Simplex es un método matricial iterativo: a partir de una propuesta 
inicial, en cada iteración, se ira acercando a la solución óptima.
 
 Desde el punto de vista matemático contamos ahora con 4 ecuaciones 
con 6 incógnitas. Por ello en cada iteración deberemos elegir sólo 4 
de ellas y mantener dos variables con valor cero.
 
 Para la propuesta inicial tomaremos el peor de los casos, para luego 
avanzar hacia la mejor solución.
 
 La peor situación es que 𝑥1y 𝑥2 sean cero, es decir, no se produce 
nada.
 
 De esta forma trabajaremos nuestra situación inicial sólo con las 
variables de holgura.
Método Simplex 
 
 
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 1200 2 1 1 0 0 0 
x4 0 2400 3 4 0 1 0 0 
x5 0 800 1 1 0 0 1 0 
x6 0 450 1 -1 0 0 0 1 
 zj 
zj-cj 
 
 
 En la columna xk colocamos las variables elegidas para la solución inicialmente 
propuesta. 
 En la columna Ck sus coeficientes de beneficio. Por ser variables de holgura, todos 
los valores son cero. 
 En la columna B los valores del lado derecho de las restricciones. 
 En cada fila los coeficientes que tiene cada variable en las restricciones 
Método Simplex 
 
 
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 1200 2 1 1 0 0 0 
x4 0 2400 3 4 0 1 0 0 
x5 0 800 1 1 0 0 1 0 
x6 0 450 1 -1 0 0 0 1 
 zj 0 0 0 0 0 0 0 
zj-cj -8 -5 0 0 0 0 
 
 
 En la fila zj calculamos la suma del vector columna por la columna Ck. Para la 
columna B nos queda 1200*0+2400*0+800*0+450*0. El resultado 0 indica que no 
estamos ganando nada con la solución propuesta.
 Hacemos el mismo cálculo para cada vector columna multiplicado por la columna 
Ck
 En la fila zj-cj se realiza la operación indicada.
Método Simplex 
 
 
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 1200 2 1 1 0 0 0 
x4 0 2400 3 4 0 1 0 0 
x5 0 800 1 1 0 0 1 0 
x6 0 450 1 -1 0 0 0 1 
 zj 0 0 0 0 0 0 0 
zj-cj -8 -5 0 0 0 0 
 
 
 El valor obtenido indica lo que se está dejando de ganar por no considerar esa 
variable como parte de la solución. 
 Por ello se elige el valor más negativo de todos para que ingrese a la solución 
propuesta. Pero esto implica sacar otra para que siempre queden 4 variables. 
 Se ingresará x1. 
Método Simplex 
 
 
Iteración 0 
 
 
 
 
 
 
 
 
 
 Para elegir la variable que debe salir dividiremos el vector de las disponibilidades 
(B) por el vector columna elegido. El resultado se ubica en la columna θ 
 Las cantidades que aparecen en θ corresponden a la máxima cantidad que 
podemos utilizar del recurso que representa sin que el resto alcance un valor 
negativo. 
 Se debe elegir la variable cuyo θ es el menor. 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 1200 2 1 1 0 0 0 600 
x4 0 2400 3 4 0 1 0 0 800 
x5 0 800 1 1 0 0 1 0 800 
x6 0 450 1 -1 0 0 0 1 450 
 zj 0 0 0 0 0 0 0 
zj-cj -8 -5 0 0 0 0 
 
Método Simplex 
 
 
Iteración 0 
 
 
 
 
 
 
 
 
 
 La variable que sale de la solución propuesta es x6 para que ingrese x1 
 El valor que aparece marcado por ambas áreas sombreadas se denomina 
elemento pivote 
 Con esta información construiremos la siguiente matriz Simplex 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 1200 2 1 1 0 0 0 600 
x4 0 2400 3 4 0 1 0 0 800 
x5 0 800 1 1 0 0 1 0 800 
x6 0 450 1 -1 0 0 0 1 450 
 zj 0 0 0 0 0 0 0 
zj-cj -8 -5 0 0 0 0 
 
Método Simplex 
 
 
Iteración 1 
 
 
 
 
 
 
 
 
 
 En la fila donde estaba x6 ahora está x1, por eso cambia el valor del Ck 
 Los valores que se encontraban en la fila x6 se dividen por el elemento pivote 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 
x4 0 
x5 0 
x1 8 450 1 -1 0 0 0 1 
 zj 
zj-cj 
 
Método Simplex 
 
 
Iteración 1 
 
 
 
 
 
 
 
 
 
 En la columna Aj correspondiente a cada variable que se encuentra en la solución 
propuesta en esta etapa le pondremos un 1 en la fila que le corresponde y el resto 
en cero 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 0 1 0 0 
x4 0 0 0 1 0 
x5 0 0 0 0 1 
x1 8 450 1 -1 0 0 0 1 
 zj 
zj-cj 
 
Método Simplex 
 
 
Iteración 1 
 
 
 
 
 
 
 
 
 Los valores faltantes se calculan utilizando la matriz anterior y manteniendo fijo el
pivote: 
Iteración 0  Se calcula el valor de cada 
celda menos el producto del 
número que está en la misma 
fila pero en la columna del 
pivote y el número que está en 
la misma columna pero a la 
altura del pivote, dividido el 
pivote 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 0 1 0 0 
x4 0 0 0 1 0 
x5 0 0 0 0 1 
x1 8 450 1 -1 0 0 0 1 
 zj 
zj-cj 
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 1200 2 1 1 0 0 0 600 
x4 0 2400 3 4 0 1 0 0800 
x5 0 800 1 1 0 0 1 0 800 
x6 0 450 1 -1 0 0 0 1 450 
 zj 0 0 0 0 0 0 0 
zj-cj -8 -5 0 0 0 0 
 
Método Simplex 
 
 
Iteración 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Iteración 0 El valor que corresponde a la 
columna B, fila x3 es: 
1200 − 
450 ∗ 2 
1 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 300 0 1 0 0 
x4 0 0 0 1 0 
x5 0 0 0 0 1 
x1 8 450 1 -1 0 0 0 1 
 zj 
zj-cj 
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 1200 2 1 1 0 0 0 600 
x4 0 2400 3 4 0 1 0 0 800 
x5 0 800 1 1 0 0 1 0 800 
x6 0 450 1 -1 0 0 0 1 450 
 zj 0 0 0 0 0 0 0 
zj-cj -8 -5 0 0 0 0 
 
Método Simplex 
 
 
Iteración 1 
 
 
 
 
 
 
 
 
 
 De esta forma se completan todos los lugares vacíos (no calculamos θ aún). 
 Esta iteración nos dice que si producimos 450 unidades de conservas de durazno 
obtendremos una ganancia de $3600 (z). 
 Sin embargo la fila zj-cj me está diciendo que estamos perdiendo dinero al no 
incluir x2. Por lo tanto no llegamos al óptimo. 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 300 0 3 1 0 0 -2 
x4 0 1050 0 7 0 1 0 -3 
x5 0 350 0 2 0 0 1 -1 
x1 8 450 1 -1 0 0 0 1 
 zj 3600 8 -8 0 0 0 8 
zj-cj 0 -13 0 0 0 8 
 
Método Simplex 
 
 
Iteración 1 
 
 
 
 
 
 
 
 
 
 Elegimos x2 como variable para que ingrese a la solución. 
 Calculamos los valores de θ para saber cual variable hay que sacar. 
 El valor menor corresponde al de x3 ya que no se consideran los valores negativos. 
 Cj 8 5 0 0 0 0 
θ 
 xk Ck B A1 A2 A3 A4 A5 A6 
 x3 0 300 0 3 1 0 0 -2 100 
 x4 0 1050 0 7 0 1 0 -3 150 
 x5 0 350 0 2 0 0 1 -1 175 
 x1 8 450 1 -1 0 0 0 1 -450 
 zj 3600 8 -8 0 0 0 8 
zj-cj 0 -13 0 0 0 8 
 
Método Simplex 
 
 
Iteración 2 
 
 
 
 
 
 
 
 
 
 
 
 
Iteración 1 
Utilizando la iteración anterior 
se procede de la misma forma 
con el nuevo pivote 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x2 5 100 0 1 0,33 0 0 -0,7 
x4 0 0 0 1 0 
x5 0 0 0 0 1 
x1 8 1 0 0 0 
 zj 
zj-cj 
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 300 0 3 1 0 0 -2 100 
x4 0 1050 0 7 0 1 0 -3 150 
x5 0 350 0 2 0 0 1 -1 175 
x1 8 450 1 -1 0 0 0 1 -450 
 zj 3600 8 -8 0 0 0 8 
zj-cj 0 -13 0 0 0 8 
 
Método Simplex 
 
 
Iteración 2 
 
 
 
 
 
 
 
 
 
 
 
 
Iteración 1 
Calculamos con la misma 
mecánica los valores faltantes 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x2 5 100 0 1 0,33 0 0 -0,7 
x4 0 350 0 0 -2,3 1 0 1,67 
x5 0 150 0 0 -0,7 0 1 0,33 
x1 8 550 1 0 0,33 0 0 0,33 
 zj 
zj-cj 
 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x3 0 300 0 3 1 0 0 -2 100 
x4 0 1050 0 7 0 1 0 -3 150 
x5 0 350 0 2 0 0 1 -1 175 
x1 8 450 1 -1 0 0 0 1 -450 
 zj 3600 8 -8 0 0 0 8 
zj-cj 0 -13 0 0 0 8 
 
Método Simplex 
 
 
Iteración 2 
 
 
 
 
 
 
 
 
 
 Calculamos los valores zj y zj-cj 
 El modelo obtenido dice que produciendo 550 latas de duraznos y 100 ltas 
de peras podemos ganar $4900. 
 Pero la tener un valor negativo en zj-cj, todavía me dice que no llegamos 
al óptimo. 
 Requiere una nueva iteración 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x2 5 100 0 1 0,33 0 0 -0,7 
x4 0 350 0 0 -2,3 1 0 1,67 
x5 0 150 0 0 -0,7 0 1 0,33 
x1 8 550 1 0 0,33 0 0 0,33 
 zj 4900 8 5 4,33 0 0 -0,7 
zj-cj 0 0 4,33 0 0 -0,7 
 
Método Simplex 
 
 
Iteración 2 
 
 
 
 
 
 
 
 
 
 La variable x6 vuelve a entrar. 
 Calculamos los valores θ 
 La variable que sale es x4 
 Cj 8 5 0 0 0 0 
θ 
 
xk Ck B A1 A2 A3 A4 A5 A6 
x2 5 100 0 1 0,33 0 0 -0,7 -150 
x4 0 350 0 0 -2,3 1 0 1,67 210 
x5 0 150 0 0 -0,7 0 1 0,33 450 
x1 8 550 1 0 0,33 0 0 0,33 1650 
 zj 4900 8 5 4,33 0 0 -0,7 
zj-cj 0 0 4,33 0 0 -0,7 
 
Método Simplex 
 
 
Iteración 3 
 
 
 
 
 
 
 
 
 
 No se obtuvieron valores negativos de zj-cj, por lo que hemos llegado al 
óptimo 
 El modelo obtenido dice que debemos producir 480 latas de conserva de 
durazno y 240 latas de conserva de pera, obteniendo una ganancia de $5040 
 A su vez nos dice que el límite de producción no fue alcanzado (nos sobraron 
80 unidades) y que en la diferencia entre una y otra nos quedaron aún 210 
por lo que no nos excedimos de los 450 que se había fijado. 
 Cj 8 5 0 0 0 0 
θ 
xk Ck B A1 A2 A3 A4 A5 A6 
x2 5 240 0 1 -0,6 0,4 0 0 
x6 0 210 0 0 -1,4 0,6 0 1 
x5 0 80 0 0 -0,2 -0,2 1 0 
x1 8 480 1 0 0,8 -0,2 0 0 
 zj 5040 8 5 3,4 0,4 0 0 
zj-cj 0 0 3,4 0,4 0 0 
 
 
 
 
 
 
 
 
 
 
 
 
Ejercicio con restricciones 
de tipo mayor o igual y 
menor o igual 
Planteo del problema 
 
 
Una planta petroquímica debe comprar a dos proveedores los cortes de hidrocarburos aromáticos 
que procesa para la obtención de Benceno, Tolueno, Paraxileno y Etilbenceno. 
 
La composición promedio de ambos es la siguiente: 
 
 Corte A Corte B 
Benceno 50% 10% 
Tolueno 20% 40% 
Paraxileno ---- 10% 
Etilbenceno 10% ---- 
La capacidad de almacenamiento de cortes aromáticos es de 100.000 m3. 
Para asegurar el cumplimiento de contratos previos la producción mínima de benceno debe ser de 
10.000 m3 y la cantidad mínima de tolueno debe ser de 16.000 m3. 
La capacidad del tanque de almacenamiento del Paraxileno es de 5.000 m3, mientras que el de 
Etilbenceno es 6.000 m3. 
El costo de cada corte es de $1200/m3 para el Corte A y de $700/m3 para el corte B. 
Determine la producción óptima. 
Planteo del problema 
 
 
 Corte A Corte B 
Benceno 50% 10% 
Tolueno 20% 40% 
Paraxileno ---- 10% 
Etilbenceno 10% ---- 
 
La capacidad de almacenamiento de cortes aromáticos es de 100.000 m3. 𝑥1 + 𝑥2 ≤ 100.000 
 
La producción mínima de benceno debe ser de 10.000 m3 
y la cantidad mínima de tolueno debe ser de 16.000 m3. 
La capacidad del tanque de almacenamiento del Paraxileno es de 5.000 m3 
y el de Etilbenceno es 6.000 m3. 
0,5𝑥1 + 0,1𝑥2 ≥ 10.000 
0,2𝑥1 + 0,4𝑥2 ≥ 16.000 
0,1𝑥2 ≤ 5.000 
0,1𝑥1 ≤ 6.000 
 
El costo de cada corte es de $1200/m3 para el Corte A y de $700/m3 para el corte B. 
 
𝐹𝑢𝑛𝑐𝑖ó𝑛 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜 𝑧 = 1200𝑥1 + 700𝑥2 (min) 
 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 + 𝑥2 ≤ 100.000 
 
 
Transformamos las inecuaciones en ecuaciones 
0,1𝑥2 + 𝑥3 = 5.000 
0,1𝑥1 + 𝑥4 = 6.000 
𝑥1 + 𝑥2 + 𝑥5 = 100.000 
 
Para el caso de las inecuaciones “mayor o igual a” debemos 
restarle “algo” para igualar 
0,5𝑥1 + 0,1𝑥2 − 𝑥6 = 10.000 
0,2𝑥1 + 0,4𝑥2 − 𝑥7 = 16.000 
 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 + 𝑥2 ≤ 100.000 
 
 
Sin embargo esto no sería correcto ya que una de las posibles soluciones al 
problema sería no producir nada, es decir 𝑥1 y 𝑥2 con valor cero, quedando las 
variables slack con valor negativo 
−𝑥6 = 10.000 
−𝑥7 = 16.000 
Por esta razón se agregan variables que se denominan artificiales 
 
0,5𝑥1 + 0,1𝑥2 − 𝑥6 + 𝜆8 = 10.000 
0,2𝑥1 + 0,4𝑥2 − 𝑥7 + 𝜆9 = 16.000 
 
 
Variables artificiales 
• Las variables artificiales no tienen significado físico, no se asocian a un recurso. 
• Normalmente se las representa con la letra griega lambda para distinguirlas de las 
variables de decisión y las variables slack. 
 
• Se agregan como un artificio matemático para poder resolver este tipo de inecuaciones. 
• Debido a que no representan nada en el problema, el método debe utilizar alguna forma 
para que estas variables no aparezcan en la solución final. 
 
• Para ello se le asigna un coeficiente económico que nos produzca un perjuicio muy 
grande: 
 
 Cuando maximizamos, presenta un valor de beneficio negativo muy grande (una 
pérdida). Matemáticamente los representamos como -M 
 
 Cuando minimizamos, presenta un aumento enorme de los costos. 
Matemáticamente los representamos como +M 
 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 + 𝑥2 ≤ 100.000 
 
 
 
 
 
 
La función objetivo para este problema nos queda: 
𝑧 = 1200𝑥1 + 700𝑥2 + 0𝑥3 + 0𝑥4 + 0𝑥5 + 0𝑥6 + 0𝑥7 + 𝑀𝜆8 + 𝑀𝜆9 (𝑚í𝑛) 
 
 
En forma simplificada: 
 
 
𝑧 = 1200𝑥1 + 700𝑥2 + 𝑀𝜆8 + 𝑀𝜆9(𝑚í𝑛) 
 
 
0,1𝑥2 + 𝑥3 = 5.000 
0,1𝑥1 + 𝑥4 = 6.000 
𝑥1 + 𝑥2 + 𝑥5 = 100.000 
0,5𝑥1 + 0,1𝑥2 − 𝑥6 + 𝜆8 = 10.000 
0,2𝑥1 + 0,4𝑥2 − 𝑥7 + 𝜆9 = 16.000 
 
𝑧 = 1200𝑥1 + 700𝑥2 + 𝑀𝜆8 + 𝑀𝜆9(𝑚í𝑛) 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 
 
 
+ 𝑥2 
 
 
≤ 100.000 
 
Planteo inicial (se ha simbolizado M con un valor de 1x108) 
 
 
 Cj 1200 700 0 0 0 0 0 1,0E+08 1,0E+08 
Xk Ck B A1 A2 A3 A4 A5 A6 A7 A8 A9 θ 
X3 0 5000 0 0,1 1 0 0 0 0 0 0 
X4 0 6000 0,1 0 0 1 0 0 0 0 0 
X5 0 100000 1 1 0 0 1 0 0 0 0 
L8 1,0E+08 10000 0,5 0,1 0 0 0 -1 0 1 0 
L9 1,0E+08 16000 0,2 0,4 0 0 0 0 -1 0 1 
 Zj 2,6E+12 7E+07 5E+07 0 0 0 -1E+08 -1E+08 1E+08 1E+08 
Zj-Cj 7E+07 5E+07 0 0 0 -1E+08 -1E+08 0 0 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 
 
0,1𝑥2 + 𝑥3 = 5.000 
0,1𝑥1 + 𝑥4 = 6.000 
𝑥1 + 𝑥2 + 𝑥5 = 100.000 
0,5𝑥1 + 0,1𝑥2 − 𝑥6 + 𝜆8 = 10.000 
0,2𝑥1 + 0,4𝑥2 − 𝑥7 + 𝜆9 = 16.000 
 
𝑧 = 1200𝑥1 + 700𝑥2 + 𝑀𝜆8 + 𝑀𝜆9(𝑚í𝑛) 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 
 
 
+ 𝑥2 
 
 
≤ 100.000 
 
Planteo inicial (se ha simbolizado M con un valor de 1e8) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Entra la variable que obtuvo el 
mayor positivo 
Sale la 
variable 
con el 
menor 
positivo 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 Cj 1200 700 0 0 0 0 0 1,0E+08 1,0E+08 
Xk Ck B A1 A2 A3 A4 A5 A6 A7 A8 A9 θ 
X3 0 5000 0 0,1 1 0 0 0 0 0 0 ∞ 
X4 0 6000 0,1 0 0 1 0 0 0 0 0 60000 
X5 0 100000 1 1 0 0 1 0 0 0 0 100000 
L8 1,0E+08 10000 0,5 0,1 0 0 0 -1 0 1 0 20000 
L9 1,0E+08 16000 0,2 0,4 0 0 0 0 -1 0 1 80000 
 Zj 2,6E+12 7E+07 5E+07 0 0 0 -1E+08 -1E+08 1E+08 1E+08 
Zj-Cj 7E+07 5E+07 0 0 0 -1E+08 -1E+08 0 0 
 
 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 + 𝑥2 ≤ 100.000 
 
 
 
Primera iteración: dividir la fila seleccionada por el pivot 
 
 
 Cj 1200 700 0 0 0 0 0 1,0E+08 1,0E+08 
Xk Ck B A1 A2 A3 A4 A5 A6 A7 A8 A9 θ 
X3 0 
X4 0 
X5 0 
X1 1200 20000 1 0,2 0 0 0 -2 0 2 0 
L9 
 Zj 
Zj-Cj 
 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 + 𝑥2 ≤ 100.000 
 
 
 
Primera iteración 
 
 
 Cj 1200 700 0 0 0 0 0 1,0E+08 1,0E+08 
Xk Ck B A1 A2 A3 A4 A5 A6 A7 A8 A9 θ 
X3 0 5000 0 0,1 1 0 0 0 0 0 0 50000 
X4 0 4000 0 -0,02 0 1 0 0,2 0 -0,2 0 -200000 
X5 0 80000 0 0,8 0 0 1 2 0 -2 0 100000 
X1 1200 20000 1 0,2 0 0 0 -2 0 2 0 100000 
L9 1,0E+08 12000 0 0,36 0 0 0 0,4 -1 -0,4 1 33333,3 
 Zj 1,2E+12 1200 3,6E+07 0 0 0 4E+07 -1E+08 -4E+07 1E+08 
Zj-Cj 0 3,6E+07 0 0 0 4E+07 -1E+08 -1E+08 0 
 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 + 𝑥2 ≤ 100.000 
 
 
 
Segunda iteración: se repiten todo los pasos 
 
 
 Cj 1200 700 0 0 0 0 0 1,0E+08 1,0E+08 
Xk Ck B A1 A2 A3 A4 A5 A6 A7 A8 A9 θ 
X3 0 1666,67 0 0 1 0 0 -0,1111 0,27778 0,11111 -0,2778 
X4 0 4666,67 0 0 0 1 0 0,22222 -0,0556 -0,2222 0,05556 
X5 0 53333,3 0 0 0 0 1 1,11111 2,22222 -1,1111 -2,2222 
X1 1200 13333,3 1 0 0 0 0 -2,2222 0,55556 2,22222 -0,5556 
X2 700 33333,3 0 1 0 0 0 1,11111 -2,7778 -1,1111 2,77778 
 Zj 3,9E+07 1200 700 0 0 0 -1888,9 -1277,8 1888,89 1277,78 
Zj-Cj 0 0 0 0 0 -1888,9 -1277,8 -1E+08 -1E+08 
 
 Corte A Corte B 
Benceno 50% 10% ≥10.000 
Tolueno 20% 40% ≥16.000 
Paraxileno ---- 10% ≤ 5.000 
Etilbenceno 10% ---- ≤ 6.000 
 
 
𝐴𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑥1 + 𝑥2 ≤ 100.000 
 
 
Segunda iteración: al no haber valores positivos en 𝑧𝑗 − 𝑐𝑗 , se ha 
llegado a la solución óptima 
 
 Cj 1200 700 0 0 0 0 0 1,0E+08 1,0E+08 
Xk Ck B A1 A2 A3 A4 A5 A6 A7 A8 A9 θ 
X3 0 1666,67 0 0 1 0 0 -0,1111 0,27778 0,11111 -0,2778 
X4 0 4666,67 0 0 0 1 0 0,22222 -0,0556 -0,2222 0,05556 
X5 0 53333,3 0 0 0 0 1 1,11111 2,22222 -1,1111 -2,2222 
X1 1200 13333,3 1 0 0 0 0 -2,2222 0,55556 2,22222 -0,5556 
X2 700 33333,3 0 1 0 0 0 1,11111 -2,7778 -1,1111 2,77778 
 Zj 3,9E+07 1200 700 0 0 0 -1888,9 -1277,8 1888,89 1277,78 
Zj-Cj 0 0 0 0 0 -1888,9 -1277,8 -1E+08 -1E+08 
 
𝑧 = 39333333,33 
 
Interpretación del resultado 
 
𝑥1: Indica que se le debe comprar al proveedor del corte A, 13.333 m3 
𝑥2: Al proveedor del corte B se le debe comprar 33.333 m3. 
𝑧: Es el costo total de la operación, $39.333.333 
𝑥3: Indica que nos faltarían 1.667 m3 para llenar el tanque de paraxileno de 
5000 m3 
𝑥4: Indica que nos faltarían 4.667 m3 para llenar el tanque de etilbenceno 
de 6000 m3 
𝑥5: Indica que nos faltarían 53.333 m3 para llenar el tanque de aromáticos 
de 100.000 m3 
𝑥6: Como su valor es cero, nos indica que el recurso alcanzó el límite 
impuesto. Esto significa que la producción de benceno es la mínima 
impuesta, 10.000 m3 
𝑥7: También su valor es cero por lo que la producción de tolueno es la 
mínima impuesta, 16.000 m3 
• Conclusión: el costo está impuesto por la exigencia de producir ese 
mínimo de benceno y tolueno. 
Xk Ck B 
X3 0 1666,67 
X4 0 4666,67 
X5 0 53333,3 
X1 1200 13333,3 
X2 700 33333,3 
 Zj 3,9E+07 
 
	 Vamos a aplicar el mismo ejemplo de las conservas para explicar el método.
	 Cuando estamos frente a inecuaciones del tipo “menor o igual a …” debemos agregar algo en el término que es menor para representar la igualdad:
	3𝑥1 + 4𝑥2+𝑥4= 2400 Tiempo de producción
	𝑥1 − 𝑥2 + 𝑥6 = 450 Producción en exceso
	 El valor de beneficio o costo de estas variables es cero.
	 Nuestro segundo paso es construir la matriz Simplex
	 Nuestro segundo paso es construir la matriz Simplex (1)
	 Nuestro segundo paso es construir la matriz Simplex (2)
	 El Simplex es un método matricial iterativo: a partir de una propuesta inicial, en cada iteración, se ira acercando a la solución óptima.
	 Para la propuesta inicial tomaremos el peor de los casos, para luego avanzar hacia la mejor solución.
	 De esta forma trabajaremos nuestra situación inicial sólo con las variables de holgura.
	Iteración 0
	Iteración 0 (1)
	Iteración 1
	Iteración 1 (1)
	Iteración 1 (2)
	Iteración 0 (2)
	Iteración 1 (3)
	Iteración 1 (4)
	Iteración 1 (5)
	Iteración 2
	Iteración 2 (1)
	Iteración 2 (2)
	Iteración 2 (3)
	Iteración 3
	Variables artificiales
	Interpretación del resultado
	• Conclusión: el costo está impuesto por la exigencia de producir ese mínimo de benceno y tolueno.