Programación Lineal: “El Método Simplex”:

Programación Lineal: “El Método Simplex”

Definición: El modelo Simplex es un método algebraico sistemático e iterativo utilizado para
resolver modelos de Programación Lineal, que examinan los vértices de un conjunto convexo,
hasta encontrar la alternativa óptima que resuelve el modelo.

Procedimiento: Todas las restricciones del modelo deben ser transformadas a igualdades,
para poder establecer una solución básica factible inicial, y así poder resolver un sistema de
ecuaciones simultáneas utilizando la Función Objetivo como la referencia para establecer la
solución óptima. El espacio dentro del cual se encuentra delimitada el área definida por todas
las restricciones define lo que se conoce como <polígono de Soluciones Factibles. Cada
vértice de dicho Polígono corresponde a una alternativa que resuelve el sistema de ecuaciones

y variables, y la Solución óptima del mismo estará localizada en uno de sus vértices. 


Tipos de soluciones a las ecuaciones originales

Alternativas Potenciales. Este término se refiere simplemente a cualquier conjunto de valores de las variables que satisfagan a todas y cada una de las restricciones.


Alternativa Factible: Es una alternativa potencial que satisface todas las restricciones y las condiciones de no negatividad (cuando así lo exija el modelo).


Alternativa Óptima. Es la alternativa que produce el mejor valor en la función objetivo. Esta alternativa está compuesta por todas y cada una de las variables con sus respectivos valores (incluye tanto variables de decisión como variables de holgura y/o de excedente).





Ejemplo

EJEMPLO:

Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

• Max     40*X1 + 60*X2
• s.a.     2*X1 + 1*X2 <= 70
•             1*X1 + 1*X2 <= 40
•             1*X1 + 3*X2 <= 90
•              X1 >= 0  X2 >= 0
Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:


X1	X2	X3	X4	X5
2	1	1	0	0	70
1	1	0	1	0	40
1	3	0	0	1	90
-40	-60	0	0	0	0

En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2.

Luego, para escoger que variable básica deja la base debemos buscar el mínimo 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 mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración:

X1	X2	X3	X4	X5
5/3	0	1	0	-1/3	40
2/3	0	0	1	-1/3	10
1/3	1	0	0	1/3	30
-20	0	0	0	20	1800

El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.

La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo 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 básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:

X1	X2	X3	X4	X5
0	0	1	-5/2	1/2	15
1	0	0	3/2	-1/2	15
0	1	0	-1/2	1/2	25
0	0	0	30	10	2100

Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".

La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.

VIDEO EJEMPLO