Bienvenido a ProgramaciónLineal.net un sitio enfocado exclusivamente a los contenidos de esta importante área de la Investigación de Operaciones. Se busca presentar los contenidos de una forma simple y didáctica, que permita al estudiante complementar su estudio formal de esta disciplina. Invitamos a los usuarios a plantear sus consultas y comentarios escribiendo a info@programacionlineal.net
SEP
2018
Método Simplex
El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.
La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.
FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL
Consideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que sigue por:
- Min c1x1 + c2x2 + ... + cnxn
- sa a11x1 + a12x2 + ... + a1nxn = b1
- a21x1 + a22x2 + ... + a2nxn = b2
- ... ... ...
- am1x1 + am2x2 + ... + amnxn = bm
- xi >= 0, i = 1, 2, ..., n y m <= n
Matricialmente escrito como:
Min cTx
s.a Ax = b
x >= 0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:
- EJEMPLO
- P) Max 9u + 2v + 5z
- sa 4u + 3v + 6z <= 50
- u + 2v - 3z >= 8
- 2u - 4v + z = 5
- u,v >= 0
- z e IR
- Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x)
- Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.
- Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
- Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:
- Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
- sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50
- x1 + 2x2 - 3x3 + 3x4 - x6 = 8
- 2x1 - 4x2 + x3 - x4 = 5
- xi >= 0, i=1,2,3,4,5,6.
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.
Esta estrategia se utiliza cuando no es inmediata una solución básica factible inicial en las variables originales del modelo.
FASE 1: Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible. Resolver por Simplex un problema que considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo es cero, seguir a la Fase II, en caso contrario, no existe solución factible.
FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase I.
- P) Max 2X1 + X2
- sa 10X1 + 10X2 <= 9
- 10X1 + 5X2 >= 1
- X1, X2 >= 0
Se debe agregar X3 como variable de holgura de la restricción 1, X4 como variable de exceso de la restricción 2 y X5 variable auxiliar para poder comenzar la Fase 1. (Nótese que solo agregando X3 como variable de holgura a la restricción 1 y X4 como variable de exceso a las segunda restricción no se obtiene una solución básica factible inicial, en particular X4<0).
- F1) Min X5
sa ...............10X1 + 10X2 + X3 = 9 - 10X1 + 5X2 - X4 + X5 = 1
- X1, X2, X3, X4, X5 >= 0
La tabla inicial asociada a la Fase I queda en consecuencia definida de la siguiente forma:
X1 |
X2 |
X3 |
X4 |
X5 |
|
10 |
10 |
1 |
0 |
0 |
9 |
10 |
5 |
0 |
-1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
Luego, se debe hacer 0 el costo reducido de X5, obteniendo la siguiente tabla inicial para hacer el uso de Simplex:
X1 |
X2 |
X3 |
X4 |
X5 |
|
10 |
10 |
1 |
0 |
0 |
9 |
10 |
5 |
0 |
-1 |
1 |
1 |
-10 |
-5 |
0 |
1 |
0 |
-1 |
Se escoge X1 como variable que entra a la base al tener el costo reducido más negativo. Posteriormente, mediante el criterio del mínimo cuociente se selecciona la variable que sale de la base: Min {9/10; 1/10} = 1/10, X5 sale de la base:
X1 |
X2 |
X3 |
X4 |
X5 |
|
0 |
5 |
1 |
1 |
-1 |
8 |
1 |
1/2 |
0 |
-1/10 |
1/10 |
1/10 |
0 |
0 |
0 |
0 |
1 |
0 |
Se obtiene la solución óptima de la Fase I, con valor óptimo cero. Luego iniciamos la Fase II del método tomando X1 y X3 como variables básicas iniciales.
FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase I.
X1 |
X2 |
X3 |
X4 |
|
0 |
5 |
1 |
1 |
8 |
1 |
1/2 |
0 |
-1/10 |
1/10 |
-2 |
-1 |
0 |
0 |
0 |
Hacemos cero los costos reducidos de las variables básicas:
X1 |
X2 |
X3 |
X4 |
|
0 |
5 |
1 |
1 |
8 |
1 |
1/2 |
0 |
-1/10 |
1/10 |
0 |
0 |
0 |
-1/5 |
1/5 |
X4 entra a la base. Por el criterio del mínimo cuociente, el pivote se encuentra en la fila 1, por tanto X3 sale de la base:
X1 |
X2 |
X3 |
X4 |
|
0 |
5 |
1 |
1 |
8 |
1 |
1 |
1/10 |
0 |
9/10 |
0 |
1 |
1/5 |
0 |
9/5 |
Donde la solución óptima es: X1=9/10 X2=0 Con valor óptimo V(P) = 9/5.
RESUELVA AQUI SUS PROBLEMAS DE PROGRAMACIÓN LINEAL UTILIZANDO EL MÉTODO SIMPLEX
La siguiente aplicación permite resolver modelos de Programación Lineal utilizando el Método Simplex. Consideremos uno de los ejemplos de esta sección para ver su uso. Nótese que no es necesario agregar las restricciones de no negatividad. De aquí se obtiene la solución óptima, valor óptimo y cada una de las tablas del Método Simplex. Para una mejor visualización de las tablas se recomienda seleccionar el modo "Fracción".
Aplicación usada con la autorización de ZweigMedia Inc. Los derechos de autor corresponde a ZweigMedia.
¿Problemas usando la aplicación? Háganos llegar sus consultas. Ingrese a nuestro Formulario de Contacto:
NUESTROS REFERIDOS
A continuación se presenta un compendio de Links de Interés para el usuario.
MÉTODO SIMPLEX - CASOS ESPECIALES
Llevar un problema de Programación Lineal a su forma estándar no siempre es inmediato. Un error frecuente es tratar de resolver por el Método Simplex un modelo que no cumple con el diseño que exige el método. A continuación algunos ejemplos y casos especiales a tener en cuenta:
CAMBIO DE VARIABLES
Resuelva el siguiente problema de Programación Lineal utilizando el Método Simplex.
Max 2X1 + 2X2 + 4X3
S.A.
X2 + 2X3 <= 240 (R1)
X1 + X2 + X3 <= 400 (R2)
2X1 + X2 + X3 <= 360 (R3)
X1>=100 (R4) X2>=60 (R5) X3>=60 (R6)
Si quisiéramos resolver directamente este problema utilizando Simplex deberíamos agregar variables de exceso para R4, R5 y R6 y luego variables artificiales para disponer de una solución básica factible de modo de utilizar el Método Simplex de 2 Fases. Claramente esto es un trabajo tedioso por el gran tamaño de la tabla resultante.
En consecuencia, lo más eficiente es hacer un cambio de variables de modo que todas las restricciones queden del tipo "<=" y de esta forma se dispone de una solución básica factible inicial. Sea Y1=X1-100>=0; Y2=X2-60>=0; Y3=X3-60>=0. Reemplazamos en el modelo anterior, el cual queda de la siguiente forma:
Max 2Y1 + 2Y2 + 4Y3 + 560
S.A.
Y2 + 2Y3 <= 60 (R1)
Y1 + Y2 + Y3 <= 180 (R2)
2Y1 + Y2 + Y3 <= 40 (R3)
Y1>=0 (R4) Y2>=0 (R5) Y3>=0 (R6)
Nótese que se podría obviar la restricción 2 y obtener identicos resultados. De todos modos definimos la tabla inicial asociada a este nuevo problema:
Y1 |
Y2 |
Y3 |
S1 |
S2 |
S3 |
|
0 |
1 |
2 |
1 |
0 |
0 |
60 |
1 |
1 |
1 |
0 |
1 |
0 |
180 |
2 |
1 |
1 |
0 |
0 |
1 |
40 |
-2 |
-2 |
-4 |
0 |
0 |
0 |
0 |
Compruebe que Y1=5 (X1=105), Y2=0 (X2=60), Y3=30 (X3=90) con V(P)=690.
PROBLEMA INFACTIBLE
Esta situación se detecta cuando el valor óptimo del problema de la fase 1 es distinto de cero.
Max 3x1 + 2x2
s.a: 2x1 + x2 <= 2
3x1 + 4x2 >= 12
x1,x2 >= 0
Llevamos el modelo a su forma estándar agregando X3 como variable de holgura de la restricción 1, X4 como variable de exceso de la restricción 2 y X5 como variable artificial de la restricción 2 que nos permita formar la base. De esta forma el modelo de la fase 1 queda definido por:
Min x5
s.a: 2x1 + x2 + x3 = 2
3x1 + 4x2 -x4 + x5= 12
x1,x2,x3,x4,x5 >= 0
Con tabla inicial:
X1 |
X2 |
X3 |
X4 |
X5 |
|
2 |
1 |
1 |
0 |
0 |
2 |
3 |
4 |
0 |
-1 |
1 |
12 |
0 |
0 |
0 |
0 |
1 |
0 |
Y tabla final de la fase 1:
X1 |
X2 |
X3 |
X4 |
X5 |
|
2 |
1 |
1 |
0 |
0 |
2 |
-5 |
0 |
-4 |
-1 |
1 |
4 |
5 |
0 |
4 |
0 |
0 |
-4 |
EJEMPLO PROBLEMA NO ACOTADO:
Esta situación se detecta cuando al realizar el cálculo de la variable que deja la base, todos los elementos ykj de la columna j en la tabla, son negativos para j el índice de una variable no básica con costo reducido negativo.
Max 2x1 + x2
s.a: x1 - x2 <= 10
2x1 <= 40
x1,x2 >= 0
Donde la tabla inicial del método simplex luego de agregar X3 y X4 como variables de holgura para las restricciones 1 y 2 respectivamente es:
X1 |
X2 |
X3 |
X4 |
|
1 |
-1 |
1 |
0 |
10 |
2 |
0 |
0 |
1 |
40 |
-2 |
-1 |
0 |
0 |
0 |
Cabe destacar que en esta instancia ya se puede constatar que el problema es no acotado. X2 siendo variable no básica los elementos de la respectiva columna son negativos o cero. Sin embargo, si el usuario no se percata inmediatamente de esto, de todos modos llegará a la misma conclusión en la iteración posterior, luego de hacer entrar X1 a la base como aquella variable no básica con costo reducido más negativo.
MÚLTIPLES SOLUCIONES ÓPTIMAS
Esta situación se detecta cuando existen costos reducidos iguales a cero en una o más de las variables no básicas óptimas.
Max 3x1 + 2x2
s.a: 5x1 + 2x2 <= 140
3x1 + 2x2 <= 120
x1,x2 >= 0
Con tabla final del Método Simplex:
X1 |
X2 |
X3 |
X4 |
|
1 |
0 |
1/2 |
-1/2 |
10 |
0 |
1 |
-3/4 |
5/4 |
45 |
0 |
0 |
0 |
1 |
120 |
Nótese que se ha encontrado una de las infinitas soluciones óptimas para el problema (X1=10, X2=45, V(P)=120). Esto debido a que la variable no básica X3 tiene costo reducido igual a cero en el óptimo. ¿Cómo se puede obtener otro vértice con similar valor óptimo?. Se debe forzar la entrada entonces de X3 a la base y sacar de la base una de las variables básicas actuales (si sigue el cálculo notará que esta corresponde a X1). Finalmente, el nuevo vértice óptimo es X1=0, X2=60, V(P)=120. El resto de las infinitas soluciones óptimas esta contenida en tramo que une los 2 vértices tal como se muestra en la figura:
¿LE HA RESULTADO ÚTIL ESTE SITIO?