LP: método M grande

Método Big M

Cuando el símplex tiene variables artificiales, es posible no encontrar una solución de partida obvia (pruebe si el origen está en el campo de definición). En este caso, se debe encontrar una solución inicial utilizando el método de la gran M.

Este método calcula un problema auxiliar antes de resolver el símplex del programa lineal, por lo que se denomina símplex de dos fases.

¿Por qué una variable artificial?

Antes de explicar cómo obtener una solución para iniciar el simplex, es importante entender por qué es necesario agregar una variable artificial además de la variable de holgura.

Tomemos como ejemplo el siguiente programa lineal:

Agreguemos las variables de varianza:

El símplex comienza tomando las variables base en cero, por lo que con el siguiente vector (0, 0, -19, 32). Esto es imposible porque X3 no puede tomar un valor negativo. Por eso hay que añadir una nueva variable que, por tanto, será artificial.

Aquí el vector (0, 0, 0, 19, 32) es una solución factible. Pero como es una variable artificial, debe ser posible eliminarla del Simplex para poder encontrar una solución global. Por tanto, es necesario que X5 = 0. Para comprobar si esto es posible, buscamos minimizar X5.

Construcción de la Fase 1

Lo preparamos de forma similar a la tabla inicial del método Simplex, pero con algunas diferencias. Tomando el ejemplo anterior, intentamos resolver el siguiente problema:

Sabemos que solo X4 y X5 están en la base, por lo que el primer paso es expresar la función objetivo con las variables no base (aquí X1, X2, X3). En el ejemplo, esto es posible gracias a la primera restricción.

El primer paso es resolver el siguiente programa lineal:

Fase 2

La segunda fase del método Two-Phase se desarrolla exactamente igual que el método Simplex, excepto que antes de iniciar las iteraciones es necesario eliminar las columnas correspondientes a las variables artificiales y reconstruir la tabla original.

• Elimine las columnas de variables artificiales: Si llegamos a la conclusión de que el problema inicial tiene solución, debemos preparar nuestra tabla para la segunda fase. Este paso es muy sencillo, solo debes borrar las columnas correspondientes a las variables artificiales.
• Reconstrucción de la mesa inicial: La matriz inicial, en este caso, permanece aproximadamente igual a la última matriz de la primera fase. La línea de la función objetivo debe ser modificada solo por la del problema inicial y recalcular la línea Z (de la misma manera que en la primera tabla de la fase 1).

La condición de parada es la misma que en el método Simplex. Es decir, cuando en la línea del indicador ninguno de los valores de los costos reducidos es negativo (porque estamos en el caso de una maximización).

El simplex anterior da para la solución óptima Z = 0 con el vector (0, 19/3, 0, 20/3, 0). Eso quiere decir que se puede prescindir de la variable artificial y que la solución encontrada está en el espacio de definición del problema inicial (ya que X5 no interviene y que está fuera de base). La solución final da el siguiente simplex:

El último paso de la fase 1 consiste en tomar la función objetivo inicial (aquí -2X1 - X2) y reemplazar todas las variables base con variables no base (aquí X2 y X4 están en la base, X1 y X3 están fuera de las bases).

Tenemos para la primera restricción X2 = 19/3 - 2 / 3X1 + 1 / 3X3, por lo tanto, podemos reescribir la función objetivo por: Z = - 4 / 3X1 - 1 / 3X2 -19/3.

A partir de este punto, todas las iteraciones, hasta llegar a la solución óptima del problema, no muestran diferencia con el método Simplex.

Algoritmo simplex

Aquí está el algoritmo simplex revisado: