Método de la gran M

En investigación operativa , el método Big M es un método para resolver problemas de programación lineal utilizando el algoritmo simplex . El método Big M extiende el algoritmo simplex a problemas que contienen restricciones de "mayor que". Para ello, asocia las restricciones con grandes constantes negativas que no formarían parte de ninguna solución óptima, si es que existe.

El algoritmo simplex es el método original y aún uno de los más utilizados para resolver problemas de maximización lineal. Es evidente que los puntos que alcanzan el objetivo óptimo deben encontrarse en un vértice del simplex, que representa la región factible de un programa lineal. Los puntos en los vértices del simplex se representan como una base. Por lo tanto, para aplicar el algoritmo simplex, cuyo objetivo es mejorar la base hasta alcanzar un óptimo global, primero es necesario encontrar una base factible.

La base trivial (todas las variables del problema iguales a 0) no siempre forma parte del simplex. Es factible si y solo si todas las restricciones (excepto la de no negatividad) son menores que y con una constante positiva en el lado derecho. El método de la M grande introduce variables artificiales y de exceso para convertir todas las desigualdades a esa forma y, por lo tanto, extiende el simplex a dimensiones superiores para que sea válido en la base trivial. Siempre es un vértice debido a la restricción de positividad en las variables del problema inherente a la formulación estándar de la programación lineal. La "M grande" se refiere a un número grande asociado con las variables artificiales, representado por la letra  M.

Los pasos del algoritmo son los siguientes:

1. Multiplica las restricciones de desigualdad para asegurar que el lado derecho sea positivo.
2. Si el problema es de minimización, transfórmelo en maximización multiplicando la función objetivo por −1.
3. Para cualquier restricción de mayor que, introduzca un excedente s _i y variables artificiales a _i (como se muestra a continuación).
4. Elija un valor positivo grande M e introduzca un término en la función objetivo de la forma −M multiplicando las variables artificiales.
5. Para restricciones de menor que o igual, introduzca variables de holgura s _i de modo que todas las restricciones sean igualdades.
6. Resuelva el problema utilizando el método simplex habitual.

Por ejemplo, x  + y ≤ 100 se convierte en x + y + s ₁ = 100, mientras que x + y ≥ 100 se convierte en x + y − s ₁ + a ₁ = 100. Debe demostrarse que las variables artificiales son cero. La función que se desea maximizar se reescribe para incluir la suma de todas las variables artificiales. Luego se aplican reducciones de filas para obtener una solución final.                   

El valor de M debe elegirse lo suficientemente grande como para que la variable artificial no forme parte de ninguna solución factible.

Para un valor de M suficientemente grande, la solución óptima contiene cualquier variable artificial en la base (es decir, valores positivos) si y solo si el problema no es factible.

Sin embargo, la selección a priori de un valor apropiado para M no es trivial. En ^{[ 1 ]} se describe una forma de superar la necesidad de especificar el valor de M. Otras formas de encontrar una base inicial para el algoritmo simplex implican resolver otro programa lineal en una fase inicial.

Cuando se utiliza en la función objetivo, el método de la gran M a veces se refiere a formulaciones de problemas de optimización lineal en las que las violaciones de una restricción o un conjunto de restricciones están asociadas con una gran constante de penalización positiva, M.

En la optimización lineal de enteros mixtos, el término Big M también puede referirse al uso de un término grande en las propias restricciones. Por ejemplo, la restricción lógica.${\displaystyle z=0\iff x=y}$donde z es una variable binaria (0 o 1) se refiere a garantizar la igualdad de las variables solo cuando una determinada variable binaria toma un valor, pero dejar las variables "abiertas" si la variable binaria toma su valor opuesto. Para una M suficientemente grande y una variable binaria z (0 o 1), las restricciones

${\displaystyle xy\leq Mz}$

${\displaystyle xy\geq -Mz}$

asegúrese de que cuando${\displaystyle z=0}$entonces${\displaystyle x=y}$. De lo contrario, cuando${\displaystyle z=1}$, entonces${\displaystyle -M\leq xy\leq M}$, lo que indica que las variables x e y pueden tener cualquier valor siempre que el valor absoluto de su diferencia esté acotado por${\displaystyle M}$(de ahí la necesidad de que M sea "lo suficientemente grande"). Por lo tanto, es posible "codificar" la restricción lógica en un problema MILP.

• Método de dos fases (programación lineal): otro enfoque para resolver problemas con restricciones >=
• Condiciones de Karush-Kuhn-Tucker , que se aplican a problemas de optimización no lineal con restricciones de desigualdad.

Bibliografía

• Griva, Igor; Nash, Stephan G.; Sofer, Ariela (26 de marzo de 2009). Optimización lineal y no lineal (2ª  ed.). Sociedad de Matemáticas Industriales. ISBN 978-0-89871-661-0.

Discusión

• Simplex – Método Big M , Lynn Killen, Universidad de la Ciudad de Dublín .
• El método Big M , businessagementcourses.org
• El método Big M , Mark Hutchinson
• El método Big-M con M numéricamente infinita , una variante sin parámetros introducida recientemente.
• MÉTODO SIMPLEX DE TRES FASES PARA PROBLEMAS DE PROGRAMACIÓN LINEAL INFACIBLES E INUTILIZABLES , método Big M para M=1