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 “≥” (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.
• 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.
• Restricción 3: 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.

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_b,3×X_1,3) - C_j,1 = (M×1) + (M×-1) + (0×0) - (1) = -1
• Z₂ = (C_b,1×X_2,1) + (C_b,2×X_2,2) + (C_b,3×X_2,3) - C_j,2 = (M×1) + (M×1) + (0×1) - (-2) = 2M + 2
• Z₃ = (C_b,1×S_1,1) + (C_b,2×S_1,2) + (C_b,3×S_1,3) - C_j,3 = (M×-1) + (M×0) + (0×0) - (0) = -M
• Z₄ = (C_b,1×S_2,1) + (C_b,2×S_2,2) + (C_b,3×S_2,3) - C_j,4 = (M×0) + (M×-1) + (0×0) - (0) = -M
• Z₅ = (C_b,1×S_3,1) + (C_b,2×S_3,2) + (C_b,3×S_3,3) - C_j,5 = (M×0) + (M×0) + (0×1) - (0) = 0
• Z₆ = (C_b,1×A_1,1) + (C_b,2×A_1,2) + (C_b,3×A_1,3) - C_j,6 = (M×1) + (M×0) + (0×0) - (M) = 0
• Z₇ = (C_b,1×A_2,1) + (C_b,2×A_2,2) + (C_b,3×A_2,3) - C_j,7 = (M×0) + (M×1) + (0×0) - (M) = 0
• Z₈ = (C_b,1×R₁) + (C_b,2×R₂) + (C_b,3×R₃) = (M×2) + (M×1) + (0×3) = 3M

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: [-1, 2M + 2, -M, -M, 0, 0, 0]. El mayor valor es = 2M + 2 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 A₁ → R₁ / X_2,1 = 2 / 1 = 2
• Fila A₂ → R₂ / X_2,2 = 1 / 1 = 1 (Menor Valor)
• Fila S₃ → R₃ / X_2,3 = 3 / 1 = 3

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