Método simplex
Estudiante: LUIS Henry Mariscal Arismendi
Universidad Privada Domingo Savio
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.
El Método Simplex es un algoritmo iterativo que
permite mejorar la solución a cada paso. La
explicación matemática de esta mejora radica,
principalmente, en que el algoritmo permite
“trasladarse” de un vértice a otro del poliedro formado
por las restricciones (conocido como el área posible
de resultados) de tal manera que el valor encontrado
aumente o disminuya.
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.
UN EJEMPLO HISTÓRICO.
El ejemplo original de George Dantzig se refería a la
búsqueda de la mejor asignación de 70 personas a
70 puestos de trabajo. Este ejemplo fue el punto de
partida para mostrar la utilidad de la Programación
Lineal.
En este ejemplo histórico, la potencia de
computación necesaria para examinar todas las
permutaciones, a fin de seleccionar la mejor
asignación, es inmensa. Tan es así, que al
calcularse el número de posibles configuraciones
se encontró que éste excedía al número de
partículas en el universo.
Sin embargo, tan solo toma un momento encontrar
la solución óptima mediante el planteamiento del
problema a través de la Programación Lineal y con
la aplicación del Método Simplex.
Ventajas:
La gran virtud del Método Simplex es su
sencillez, es un método muy práctico, ya que
tan solo trabaja con los coeficientes de la
función objetivo (Z) y de las restricciones.
Es fácil de implementar y tiene una alta eficacia.
Limitaciones:
Tal vez la mayor limitante de este método es
que converge (se acerca) más lentamente hacia
el óptimo que otros métodos, ya que requiere
un mayor número de iteraciones (tantas como
vértices tenga el poliedro).
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².
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.
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.
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.
Estas restricciones se deducen de todas las
necesidades que requiere cada árbol: terreno, horas
de trabajo anuales y riego. Para ello, se debe
identificar lo siguiente:
Necesidades de terreno:
32X1 + 8X2 + 8X3 + 24X4 ≤ 1280
Necesidades de horas anuales:
30X1 + 5X2 + 10X3 + 20X4 ≤ 1800
Necesidades de riego:
4X1 + 2X2 + 2X3 + 4X4 ≤ 400
Una vez establecidas las restricciones, entonces se
expresan todas las condiciones implícitamente
establecidas por la naturaleza de las variables: que
no sean negativas, que sean enteras, que sólo
puedan tomar determinados valores.
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.