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

Datos del Problema

Se requiere Minimizar el siguiente problema:

Función Objetivo
Z = -3X1 + 4X2
Sujeto a las siguientes restricciones
  • X1 + X2 4
  • 2X1 + 3X2 18

X1, X2 ≥ 0

Enunciado Original
Ejercicio no factible

Solución

Para resolver el problema se realizarán las iteraciones del método simplex hasta encontrar la solución óptima.

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 S1. 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 S2 y se sumará la variable artificial A1. En la matriz inicial, A1 estará en la base.

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:

Función Objetivo:

Minimizar Z = 0X1 + 0X2 + 0S1 + 0S2 + A1

Sujeto a:

  • X1 + X2 + S1 + 0S2 + 0A1 = 4
  • 2X1 + 3X2 + 0S1 - S2 + A1 = 18

Matriz Inicial Primera Fase

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

Tabla 1Cj00001
CbBaseX1X2S1S2A1R
0S1111004
1A1230-1118
Z230-1018

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

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

  • Z1 = (Cb,1×X1,1) + (Cb,2×X1,2) - Cj,1 = (0×1) + (1×2) - (0) = 2
  • Z2 = (Cb,1×X2,1) + (Cb,2×X2,2) - Cj,2 = (0×1) + (1×3) - (0) = 3
  • Z3 = (Cb,1×S1,1) + (Cb,2×S1,2) - Cj,3 = (0×1) + (1×0) - (0) = 0
  • Z4 = (Cb,1×S2,1) + (Cb,2×S2,2) - Cj,4 = (0×0) + (1×-1) - (0) = -1
  • Z5 = (Cb,1×A1,1) + (Cb,2×A1,2) - Cj,5 = (0×0) + (1×1) - (1) = 0
  • Z6 = (Cb,1×R1) + (Cb,2×R2) = (0×4) + (1×18) = 18

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: [2, 3, 0, -1, 0]. El mayor valor es = 3 que corresponde a la variable X2. 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 X2. 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 S1 → R1 / X2,1 = 4 / 1 = 4 (Menor Valor)
  • Fila A1 → R2 / X2,2 = 18 / 3 = 6

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

Ingresa la variable X2 y sale de la base la variable S1. El elemento pivote es 1

Aprende con explicaciones paso a paso

En Plan de Mejora nos esforzamos para ayudarte a superar esas materias complicadas de forma más fácil.

Membresía

Con el acceso a nuestra membresía tendrás acceso a 13 aplicativos para aprender proyectos, programación lineal, estadística entre otros.

¿Qué calculadoras incluyen?

  • Ruta Crítica PERT y CPM

  • Método Gráfico de Programación Lineal

  • Distribución Normal

  • Punto de Equilibrio y más