Ejemplo de Programacion Lineal - Método de la M Grande

A continuación se adecuará el problema al modelo estándar de programación lineal, agregando las variables de holgura, exceso y/o artificiales en cada una de las restricciones y convirtiendo las inecuaciones en igualdades:

• Restricción 1: Tiene signo “≤” (menor igual), por lo tanto se agregará la variable de holgura S₁. Esta variable se ubicará en la base en la matriz inicial.
• Restricción 2: Tiene signo “≥” (mayor igual), por lo tanto se restará la variable de exceso S₂ y se sumará la variable artificial A₁. En la matriz inicial, A₁ estará en la base.

Dado que el problema tiene variables artificiales, se utilizará el método de la M grande. Como el problema es de minimización, se sumarán las variables artificiales a la función objetivo multiplicadas por un número muy grande (representado por la letra M) de esta forma el algoritmo simplex las penalizará y eliminará de la base.

Ahora mostraremos el problema en la forma estándar. Se colocará el coeficiente 0 (cero) donde corresponda para crear nuestra matriz inicial:

Matriz Inicial

Utilizaremos los coeficientes de las ecuaciones para elaborar nuestra primera tabla:

a) Cálculo de Vector de Costes Reducidos (Z):

Los valores registrados en la fila Z se obtuvieron de la siguiente forma:

• Z₁ = (C_b,1×X_1,1) + (C_b,2×X_1,2) - C_j,1 = (0×1) + (M×2) - (-3) = 2M + 3
• Z₂ = (C_b,1×X_2,1) + (C_b,2×X_2,2) - C_j,2 = (0×1) + (M×3) - (4) = 3M − 4
• Z₃ = (C_b,1×S_1,1) + (C_b,2×S_1,2) - C_j,3 = (0×1) + (M×0) - (0) = 0
• Z₄ = (C_b,1×S_2,1) + (C_b,2×S_2,2) - C_j,4 = (0×0) + (M×-1) - (0) = -M
• Z₅ = (C_b,1×A_1,1) + (C_b,2×A_1,2) - C_j,5 = (0×0) + (M×1) - (M) = 0
• Z₆ = (C_b,1×R₁) + (C_b,2×R₂) = (0×4) + (M×18) = 18M

b) Condición de Optimalidad (Variable Entrante):

En el vector de costes reducidos (Z) tenemos valores positivos, por lo que debemos seleccionar el mayor valor para la columna pivote (minimización).

En el vector Z (excluyendo el último valor), tenemos los siguientes números: [2M + 3, 3M − 4, 0, -M, 0]. El mayor valor es = 3M − 4 que corresponde a la variable X₂. Esta variable ingresará a la base y sus valores en la tabla conformarán nuestra columna pivote.

Nota: Para comprobar el valor elegido, basta con reemplazar la variable M por un número grande (p. ej. M = 1000000) en el vector de costes reducidos.

d) Condición de Factibilidad:

Se verificará la condición de factibilidad, dividiendo los valores de la columna R entre la columna pivote X₂. Para procesar la división, el denominador debe ser estrictamente positivo (Si es cero o negativo se colocará N/A = No aplica). El menor valor definirá la variable que saldrá de la base:

• Fila S₁ → R₁ / X_2,1 = 4 / 1 = 4 (Menor Valor)
• Fila A₁ → R₂ / X_2,2 = 18 / 3 = 6

El menor valor corresponde a la fila de S₁. Esta variable saldrá de la base. El elemento pivote corresponde al valor que cruza la columna X₂ y la fila S₁ = 1.