METODO SIMPLEX

ING RUBEN HUALLANCA

 LOGRO DE LA SESION

Entender y conceptualizar de forma práctica, el

creciente avance del desarrollo científico y
tecnológico aplicado a modelos de optimización en
las operaciones industriales .

Datos/Observaciones
 TEMAS A TRATAR

1.- Método Simplex

Datos/Observaciones
Datos/Observaciones
Datos/Observaciones
¿Cómo resolver un problema de Programación
Lineal?

En la mayoría de los casos, el camino para identificar una solución óptima será:

1) Plantear el problema;

2) Traducirlo a un modo algebráico;

3) Definir las restricciones y;

4) Buscar el óptimo dependiendo del método que se quiera aplicar. Este óptimo se

puede encontrar a través de diferentes métodos.

Datos/Observaciones
 EL MÉTODO SIMPLEX.

El Método Simplex es un algoritmo analítico que bien puede solucionar

problemas de Programación Lineal. Además, este método es capaz de abordar

planteamientos más complejos que aquellos resueltos mediante el Método

Gráfico, ya que no toma en cuenta restricción alguna para el número de variables.

Por supuesto, este último procedimiento dependerá si la función objetivo se

maximiza o minimiza. En todo caso, como el número de vértices que tiene un
poliedro es finito entonces siempre se hallará una solución con el Método
Simplex.
Datos/Observaciones
APLICACIÓN DEL MÉTODO SIMPLEX.
Un agricultor tiene una parcela de 1280 m² para dedicarla al cultivo de árboles
frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué manera
debería repartir la superficie de su parcela, entre las variedades antes
mencionadas, para conseguir el máximo beneficio sabiendo que cada naranjo
necesita un mínimo de 32 m², cada peral 8 m², cada manzano 8 m² y cada
limonero 24 m².

Datos/Observaciones
Dispone de 1800 horas de trabajo al año, de las cuales cada naranjo necesita 30
horas al año, cada peral 5 horas, cada manzano 10 horas y, finalmente, cada
limonero necesita 20 horas.

A causa de la sequía, el agricultor tiene restricciones para el riego, ya que le han

asignado 400 m³ de agua anuales. Las necesidades anuales son de 4 m³ por cada
naranjo, 2 m³ por cada peral, 2 m³ por cada manzano y 4 m³ por cada limonero.

Datos/Observaciones
Finalmente, los beneficios unitarios para el agricultor son de $1000 por cada
naranjo, $500 por cada peral, $400 por cada manzano y $600 por cada limonero.

Si bien el planteamiento del problema es un poco extenso, los cáclulos realizados

empíricamente serían aún más. Por ello, a continuación le daremos solución
utilizando el Método Simplex.

Datos/Observaciones
 SOLUCIÓN.
Lo primero que debe hacerse es determinar las denominadas “variables
de decisión” y representarlas algebráicamente. En este caso:

X1: Número de naranjos.

X2: Número de perales.
X3: Número de manzanos.
X4: Número de limoneros.

Posteriormente se determinan las restricciones y se expresan como

inecuaciones de las ya conocidas variables de decisión.

Datos/Observaciones
Datos/Observaciones
En nuestro caso las restricciones son: a) El número de

árboles no puede ser negativo y; b) El total de árboles

debe ser un número entero. Es decir:

Xi ≥ 0 y todo Xi es entero con i=1,2,3,…,n.

Finalmente, se plantea la función objetivo:

Maximizar
Z(X1,X2,X3,X4)=1000X1+500X2+400X3+600X4
Por lo tanto, nuestro problema se reduce a resolver el
siguiente planteamiento:

Max Z=1000X1+500X2+400X3+600X4

Sujeto a:

32X1 + 8X2 + 8X3 + 24X4 ≤ 1280

30X1 + 5X2 + 10X3 + 20X4 ≤ 1800
4X1 + 2X2 + 2X3 + 4X4 ≤ 400

con Xi ≥ 0 y todo Xi entero.

La solución de nuestro problema puede seguir una
serie de pasos.

PASO I) Igualar la función objetivo a cero.

Z-1000X1-500X2-400X3-600X4=0

PASO II) Convertir todas las desigualdades en

igualdades.

32X1 + 8X2 + 8X3 + 24X4=1280

30X1 + 5X2 + 10X3 + 20X4=1800
4X1 + 2X2 + 2X3 + 4X4=400
PASO III) Para cada nueva igualdad crear una variable
ficticia llamada, generalmente, holgura.

32X1 + 8X2 + 8X3 + 24X4+H1=1280

30X1 + 5X2 + 10X3 + 20X4+H2=1800
4X1 + 2X2 + 2X3 + 4X4+H3=400

PASO IV) Construir la tabla inicial del Simplex y

comezar su solución. ¿Cómo se construye?

La tabla inicial del Simplex concentra toda la

información de las igualdades así como también el
punto de partida para la función objetivo Z.
 Tabla inicial del Simplex.
BASE X1 X2 X3 X4 H1 H2 H3 SOL.

H1
32 8 8 24 1 0 0 1280

H2 30 5 10 20 0 1 0 1800

H3 4 2 2 4 0 0 1 400

Z -1000 -500 -400 -600 0 0 0 0

Toda vez que la tabla inicial del Simplex se ha creado, podemos observar que en dicha tabla se aprecian dos matrices. La

formada por las variables de decisión (roja) y la matriz formada por las holguras (azul). Esta última se conoce como la

matriz identidad. La idea, grosso modo, es “llevar” a la matriz en rojo a una matriz como la azul.

Para ello es necesario lo siguiente:

1) Identificar la columna pivote.

2) Identificar la fila pivote.

3) Hacer unitario el elemento pivote, que no es otra

cosa más que el número donde se cruzan la columna
pivote y la fila pivote.
¿Cómo identificar la columna pivote?

Esta columna se define al seleccionar el número más

negativo en la función Z. En nuestro caso es el -1000.

¿Cómo identificar la fila pivote?

Una vez identificada la columna pivote entonces la

solución de cada fila, sin tomar en cuenta la fila de la
función objetivo Z, se divide entre su correspondiente
coeficiente de la columna pivote.
El número positivo más pequeño de estas divisiones determinará a

la fila pivote. Es importante mencionar que no se toman aquellas

divisiones con un resultado negativo y tampoco aquellas divisiones

entre cero.
Como el número positivo más pequeño de las tres divisiones es 40 entonces éste define a la fila

pivote. Si existen resultado negativos o bien divisiones entre 0 entonces no se toman dichas

divisiones. Por su parte, si existen dos divisiones con el mismo resultado entonces se toma

cualquiera de ellos.

A la intersección de la “columna pivote” y la “fila pivote” se le conoce como “elemento pivote”. En

nuestro caso es 32. Si continuamos con el Método Simplex entonces este último elemento ahora

debe hacerse unitario.

Es decir, se debe buscar un número que al multiplicarlo por 32 nos de como resultado 1.

Es claro que el número es 1/32. Ello quiere decir que debemos multiplicar toda la fila pivote por

1/32. El resultado de ello es la siguiente tabla:

BASE X1 X2 X3 X4 H1 H2 H3 SOL.

H1
1 1/4 1/4 3/4 1/32 0 0 40

H2 30 5 10 20 0 1 0 1800

H3 4 2 2 4 0 0 1 400

Z -1000 -500 -400 -600 0 0 0 0

Al definir el elemento pivote entonces la variable de

decisión X1 toma el lugar de la variable holgura H1 en
la base. Se dice que X1 entra en la solución y H1 sale.
 Ya que hemos hecho el elemento pivote unitario
entonces el objetivo es hacer “ceros” tanto arriba
como abajo de dicho elemento pivote, según sea
el caso.
BASE X1 X2 X3 X4 H1 H2 H3 SOL.

X1
1 1/4 1/4 3/4 1/32 0 0 40

H2 30 5 10 20 0 1 0 1800

H3 4 2 2 4 0 0 1 400

Z -1000 -500 -400 -600 0 0 0 0

Es decir, multiplicamos la fila pivote por -30 y se la sumamos (entrada
por entrada) a la fila de H2, posteriormente multiplicamos la fila pivote
por -4 y se la sumamos a la fila de H3. Finalmente, multiplicamos la
fila pivote por 1000 y se la sumamos a la fila de Z. Los resultados se
pueden apreciar en la siguiente tabla.
 Nueva fila pivote
Nuevo elemento pivote

BASE X1 X2 X3 X4 H1 H2 H3 SOL. Div.

X1
1 1/4 1/4 3/4 1/32 0 0 40 160

H2 0 -5/2 5/2 -5/2 -15/16 1 0 600 -240

H3 0 1 1 1 -1/8 0 1 240 240

Z 0 -250 -150 150 125/4 0 0 40000

Nueva columna pivote

Datos/Observaciones
 Toda vez que hemos realizado correctamente las
operaciones anteriores entonces el procedimiento
se repite desde el paso en que se identifica a la
columna pivote.

Nuevamente al hacer el elemento pivote unitario

entonces multiplicamos la nueva fila pivote por 5/2 y
se la sumamos a la fila de H2. Posteriormente
multiplicamos la nueva fila pivote por -1 y se la
sumamos a la fila de H3.

Datos/Observaciones
 Por último, multiplicamos la nueva fila pivote por 250

y se la sumamos a la fila de la función objetivo Z.

Los resultados que se presentan en la siguiente

tabla implican que el algoritmo se ha terminado.

¿Por qué?
El Método del Simplex concluye cuando en toda la
fila de la función objetivo Z ya no tenemos ningún
número negativo.

Datos/Observaciones
 Como puede apreciarse en la tabla, ya no tenemos números
negativos en la fila de Z. Es decir hemos encontrado una solución
que optimiza (maximiza) nuestro problema.

BASE X1 X2 X3 X4 H1 H2 H3 SOL.

X2
4 1 1 3 1/8 0 0 160

H2 10 0 5 5 -5/8 1 0 1000

H3 -4 0 0 -2 -1/4 0 1 80

Z 1000 0 100 900 125/2 0 0 80000

Datos/Observaciones Ya no hay números negativos !!!

La interpretación de los resultados, en la última tabla, es la siguiente:

Como la variable X2 entró en la solución eso quiere decir que tomará un valor y éste será

de 160. Por su parte, como las variables X3 y X4 no entraron en la solución eso quiere

decir que serán 0.

Además, también la variable X1 salió de la solución, lo cual implica que X1=0. Asimismo,

como la variable de holgura H1 salió de la solución entonces ello implica que dicha variable

será 0. Por último, en la última tabla se aprecia que la variable de holgura H2=1000 y

H3=80.

Datos/Observaciones
 Sustituyendo los valores encontrados en las
restricciones, se obtiene lo siguiente:

32(0) + 8(160) + 8(0) + 24(0) + H1= 1280

30(0) + 5(160) + 10(0) + 20(0) + H2= 1800
4(0) + 2(160) + 2(0) + 4(0) + H3= 400

Donde:

1280=1280 entonces H1=0

800+H2=1800 entonces H2=1000
320+H3=400 entonces H3=80
Datos/Observaciones
 Por lo tanto, estos son los valores para la mejor

estrategia del agricultor quien, a su vez, obtendrá

un beneficio máximo de Z=500(160)=80000.

Datos/Observaciones