Método de la M grande

Método de resolución de problemas de programación lineal

En la investigación de operaciones , el método Big M es un método para resolver problemas de programación lineal utilizando el algoritmo símplex . El método Big M extiende el algoritmo símplex a problemas que contienen restricciones de tipo "mayor que". Lo hace asociando las restricciones con constantes negativas grandes que no serían parte de ninguna solución óptima, si existiera.

Algoritmo

El algoritmo simplex es el método original y todavía uno de los más utilizados para resolver problemas de maximización lineal. Sin embargo, para aplicarlo, el origen (todas las variables iguales a 0) debe ser un punto factible. Esta condición se cumple solo cuando todas las restricciones (excepto la no negatividad) son restricciones menores que y con una constante positiva en el lado derecho. El método de la M grande introduce variables excedentes y artificiales para convertir todas las desigualdades en esa forma. La "M grande" se refiere a un gran número asociado con las variables artificiales, representado por la letra M.

Los pasos del algoritmo son los siguientes:

1. Multiplica las restricciones de desigualdad para garantizar que el lado derecho sea positivo.
2. Si el problema es de minimización, transformar a maximización multiplicando el objetivo por −1.
3. Para cualquier restricción 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 el objetivo de la forma −M multiplicando las variables artificiales.
5. Para restricciones menores o iguales, 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. Se debe demostrar que las variables artificiales son 0. La función que se va a 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 sea parte de ninguna solución factible.

Para una M suficientemente grande, la solución óptima contiene cualquier variable artificial en la base (es decir, valores positivos) si y sólo 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.}

Otros usos

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

Cuando se utiliza en las propias restricciones, uno de los muchos usos de Big M, por ejemplo, se refiere a garantizar la igualdad de variables solo cuando una determinada variable binaria toma un valor, pero dejar las variables "abiertas" si la variable binaria toma su valor opuesto. Un ejemplo de esto es el siguiente: para una variable binaria M y z suficientemente grandes (0 o 1), las restricciones

${\displaystyle x-y\leq Mz}$

${\displaystyle x-y\geq -Mz}$

Asegúrese de que cuando entonces . De lo contrario, cuando , entonces , lo que indica que las variables x e y pueden tener cualquier valor siempre que el valor absoluto de su diferencia esté acotado por (de ahí la necesidad de que M sea "suficientemente grande"). ${\displaystyle z=0}$ ${\displaystyle x=y}$ ${\displaystyle z=1}$ ${\displaystyle -M\leq x-y\leq M}$ ${\displaystyle M}$

Véase también

• 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.

Enlaces externos

Bibliografía

• Grivá, 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, Dublin City University .
• El método de la M mayúscula, entrepreneuragementcourses.org
• El método de la gran M, Mark Hutchinson
• El método Big-M con el infinito numérico M, una variante sin parámetros introducida recientemente
• MÉTODO SIMPLEX TRIFÁSICO PARA PROBLEMAS DE PROGRAMACIÓN LINEAL INUTILIZABLES E ILIMITADOS, método Big M para M=1

Referencias

1. Cococcioni, Marco; Fiaschi, Lorenzo (2021). "El método Big-M con el infinito numérico M". Optimization Letters . 15 (1): 2455–2468. doi :10.1007/s11590-020-01644-6. hdl : 11568/1061259 .