Matematicas

María del Rosario Duran Navarro.
Practica No 4.

Ejercicio del Método simplex.
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 latabla 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 estasituació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 basedebemos 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). Elmí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ínimocuociente 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...