LP: método M grande

Método Big M

Cuando el simplex tiene variables artificiales, es posible no encontrar una solución inicial obvia (pruebe si el origen está en el dominio de definición). En este caso, se debe encontrar una solución de partida con el M.

Este método calcula un problema auxiliar antes de resolver el símplex del programa lineal, por lo que hablamos de un símplex bifásico.

¿Por qué una variable artificial?

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

Tomemos como ejemplo el siguiente programa lineal:

método Big M

Agreguemos las variables de varianza:

método Big M

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.

método Big M

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:

método Big M

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:

método Big M

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:

método Big M

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:

método Big M

 

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: