Ejemplo de Programacion Lineal - Método Simplex - Dos Fases

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 “=” (igual), por lo tanto se agregará la variable artificial A₁. Esta variable se ubicará en la base en la matriz inicial.
• Restricción 2: Tiene signo “=” (igual), por lo tanto se agregará la variable artificial A₂. Esta variable se ubicará en la base en la matriz inicial.
• Restricción 3: Tiene signo “=” (igual), por lo tanto se agregará la variable artificial A₃. Esta variable se ubicará en la base en la matriz inicial.

Dado que el problema tiene variables artificiales, se utilizará el método de las dos fases. En la primera fase, la función objetivo se modificará para minimizar la suma de las variables artificiales.

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

Matriz Inicial Primera Fase

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 = (1×1) + (1×-1) + (1×0) - (0) = 0
• Z₂ = (C_b,1×X_2,1) + (C_b,2×X_2,2) + (C_b,3×X_2,3) - C_j,2 = (1×1) + (1×1) + (1×2) - (0) = 4
• Z₃ = (C_b,1×X_3,1) + (C_b,2×X_3,2) + (C_b,3×X_3,3) - C_j,3 = (1×1) + (1×2) + (1×3) - (0) = 6
• Z₄ = (C_b,1×A_1,1) + (C_b,2×A_1,2) + (C_b,3×A_1,3) - C_j,4 = (1×1) + (1×0) + (1×0) - (1) = 0
• Z₅ = (C_b,1×A_2,1) + (C_b,2×A_2,2) + (C_b,3×A_2,3) - C_j,5 = (1×0) + (1×1) + (1×0) - (1) = 0
• Z₆ = (C_b,1×A_3,1) + (C_b,2×A_3,2) + (C_b,3×A_3,3) - C_j,6 = (1×0) + (1×0) + (1×1) - (1) = 0
• Z₇ = (C_b,1×R₁) + (C_b,2×R₂) + (C_b,3×R₃) = (1×6) + (1×4) + (1×10) = 20

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: [0, 4, 6, 0, 0, 0]. El mayor valor es = 6 que corresponde a la variable X₃. Esta variable ingresará a la base y sus valores en la tabla conformarán nuestra columna pivote.

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_3,1 = 6 / 1 = 6
• Fila A₂ → R₂ / X_3,2 = 4 / 2 = 2 (Menor Valor)
• Fila A₃ → R₃ / X_3,3 = 10 / 3 = 3.333

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₂ = 2.