Programación Lineal: El Método Simplex

Solución Algebraica

Se obtiene mediante el método general “Algoritmo Simplex”, una técnica diseñada para resolver cualquier problema de PL.
Esta técnica permite pasar de una solución factible a otra solución mejor hasta lograr la solución óptima.
Para lograr esto es necesario expresar las inecuaciones presentes en el problema como ecuaciones y realizar iteraciones entre ellas medianteoperaciones elementales de matrices hasta encontrar el óptimo.

A diferencia de la solución Gráfica, no basta solo con cambiar la desigualdad en igualdad en forma directa, ya que esto alteraría la naturaleza del problema.
Para lograr la transformación se hace necesario utilizar 3 tipos distintos de variables complementarias. A saber:
1. Variables de Holgura: Se usa en restricciones lineales de laforma:
i=1naij*Xj≤bi
Este tipo de restricciones, comúnmente llamadas ‘menor o igual que…’, se puede convertir en ecuación agregando una nueva variable no negativa al lado izquierdo de la desigualdad. Esta nueva variable se llamará “Variable de Holgura” y será numéricamente igual a la diferencia entre el lado derecho y el izquierdo de la desigualdad, los que representan la disponibilidad delrecurso y su utilización respectivamente.
Ejemplo:
El lado Izq. es mas chico | |
| |
20X1+10X2+X3≤200 | 20X1+10X2+X3+S1=200 |
| |
| Diferencia entre ambos lados |
En la primera línea el lado izquierdo es mas pequeño que el lado derecho.En la segunda línea se ha incorporado una variable de holgura de un valor igual a la diferencia entre ambos lados, permitiendo transformar lasinecuaciones asociadas a recursos en ecuaciones mas fáciles de trabajar. |

2. Variables Superfluas: Se usan en restricciones del tipo:
i=1naij*Xj≥bi
Estas restricciones se conocen comúnmente con la denominación ‘Mayor o igual que…’ y se pueden convertir en igualdades restando una variable no negativa al lado izquierdo de la desigualdad. Esta variable será numéricamente igual a la diferenciaentre el lado izquierdo y el derecho de la desigualdad y se conocerá como “Variable Superflua”, la que representará el exceso de entrada respecto a los recursos disponibles.
Ejemplo:
El lado izq. es mas grande | |
| |
2X1+5X2+3X3≥200 | 2X1+5X2+3X3-X4=200 |
| |
| Diferencia entre ambos lados |
En la primera línea el lado izquierdo es mas grande que el lado derecho.En la segundalínea se ha incorporado una variable superflua de un valor igual a la diferencia entre ambos lados, permitiendo transformar estas inecuaciones en igualdades mas fáciles de trabajar. |

3. Variables Artificiales: Después de que todas las restricciones se han transformado en igualdades es necesario agregar otra nueva variable llamada ‘Variable Artificial’ al lado izquierdo de cada ecuación derestricción que no contenga una variable de holgura. Este paso es necesario para poder formar una matriz identidad.
Ejemplo:
X1+2X2+X3≤500 | | X1+2X2+X3+S1 =500 |
| | |
2X1+X2+5X3≥300 | | 3X1+X2+5X3-X4+A1=300 |
| | |
X1+5X2+4X3=600 | | 2X1+5X2+3X3 +A2=600 |

Las variables de Holgura y las variables Superfluas actúan solo como un apoyo para la correctatransformación de una restricción en igualdad, sin alterar la naturaleza de la restricción ni de la función objetivo, lo que permite que se agreguen a la función objetivo con “coeficientes cero”
Por otra parte, las variables artificiales cambian la naturaleza de las restricciones, ya que se agregan solo a un lado de la ecuación alterando su equilibrio. Luego, el nuevo sistema será equivalente al originalsolo si las variables artificiales son iguales a cero.

Forma Standard del modelo de PL:
Un programa lineal está en forma Standard si todas las restricciones se han transformado en ecuaciones mediante la incorporación de variables de Holgura, Superfluas y Artificiales.
Ejemplos:
Modelo Matemático |   |   | Forma Standard |
Minimizar | Z | = | X1+2X2+3X3 |   |   | Minimizar | Z | = |...