Método de la gran "M"

Existen problemas de Programación Lineal para el caso de minimización donde el método simplex ya conocido no es funcional debido a que los valores de una o más variables básicas son negativas y eso significa que se está violando el principio de no negatividad en las restricciones para ello el problema se podrá resolver por otros métodos que son:

a) El método de la gran ¨M¨
b) El método de las dos fases

Método de la gran M (Penalización)

Consiste en modificar el problema original para dar lugar a un nuevo problema, agregando una variable ¨W ¨ llamada artificial y que se penalizara mediante un costo ¨M¨ de valores grandes y positivos que en forma arbitraria, permite que la función objetivo forme valores muy grandes también cuando sea minimización llegara el momento en que ¨W¨ = O y esto indica haber regresado al problema original, pero si se llega W > 0 entonces el problema no tiene solución.

≥ Variable artificial = -R1
≤ Variable artificial = +R2

Minimice
Z = 4x1 + x2

Sujeta a 3x1 + x2 = 3
4x1 + 3x2 ≥ 6
X1 + 2x2 ≤ 4

X1, x2 ≥ 0 3x1 + x2 = 3 → 3x1 + x2 = 3

4x1 + 3x2 ≥ 6 → 4x1 + 3x2 + -x3 = 6

X1 + 2x2 ≤ 4 → x1 + 2x2 + x4 = 4

X1, x2 ≥ 0 → x1, x2, x3, x4 ≥ 0 condición de no negatividad

Minimice z= 4x1 + x2 + Mr1 + Mr2

3x1 + x2 + R1 = 3
4x1 + 3x2 –x3 + R2 = 6
X1 + 2x2 +x4 = 4

X1, x2, x3, x4, R1, R2 ≥ 0
Z = -4x – x2 – Mr1 – Mr2 = 0