Método de la gran M
Recuerde que el algoritmo simplex requiere una sfb inicial. En todos los problemas que se han resuelto hasta ahora se determino una sfb inicial usando las variables de holgura como si fueran variables físicas. Pero si un PL tiene alguna restricción ≥ o de igualdad, no sería tan evidente una sfb inicial. Mediante el ejemplo 4 se ilustra cuán difícil podría ser encontrar una sfb. Cuando una sfb no es evidente, el método de la gran M (o el método simplex de dos fases de selección) se podría explicar para resolver el problema. En esta sección se trata el método de la gran M, una versión del algoritmo simplex que determina primero un sfb mediante la suma de variables “artificiales” al problema. Naturalmente, la función …ver más…

Esta “solución” no contiene vitamina C y pone 0 onzas de agua carbonatada en una botella, ¡así que posiblemente no resuelve nuestro problema original! Si la solución optima (18) es resolver (17), entonces hay que estar seguros de que la solución optima para (18) hace que todas las variables artificiales sean iguales a cero. En un problema de minimización es posible asegurar que todas las variables artificiales serán cero al sumar un término Ma1 a la función objetivo para cada variable artificial a1. (En un problema de maximización, son un término - Ma1 a la función objetivo.) Aquí M representa un número positivo “muy grande”. Por lo tanto, en (18), la función objetivo cambiaria a: min⁡〖z=2x_1+3x_2 〗+Ma_2+Ma_3
Entonces, el renglón 0 cambiaria a min⁡〖z=2x_1+3x_2 〗+Ma_2+Ma_3=0
Modificar la función objetivo de esta manera hace extremadamente costoso que una variable artificial sea positiva. Con esta función objetivo modificada parece razonable que la solución optima para (18) tenga a a_2=a_3=0. En este caso, la solución óptima (18) resuelve el problema original (17). Sin embargo, sucede a veces que al resolver el análogo de (18), algunas de las variables artificiales para asumir valores positivos en la solución óptima si esto sucediera, el problema original no tiene solución factible.
Por razones obvias, el método se ha explicado recibe el nombre de método de la gran M. enseguida se presenta una explicación formal de este método.
Descripción del método de la gran M