,

Ejercicio Resuelto – Método Simplex – Soluciones ilimitadas no acotadas

En este problema, resolveremos un caso de maximización con el método simplex, donde el resultado tendrá soluciones ilimitadas no acotadas.

Las soluciones ilimitadas en el método simplex se presentan cuando ninguna variable puede entrar en la base (no se cumple la condición de factibilidad):

Maximizar 2x1+3x2

Sujeto a:
-x1 + x2 ≤ 2
x2 ≤ 5
x1, x≥ 0

Solución

Para resolver el problema utilizaremos la versión de membresía de nuestra calculadora de programación lineal:

Función Objetivo

Maximizar: Z = 2X1 + 3X2

Sujeto a:

-1X1 + 1X2 ≤ 2

0X1 + 1X2 ≤ 5

X1, X2 ≥ 0

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

  • Restricción 1: Tiene signo “≤” (menor igual) por lo que se agregará la variable de holgura S1. En la tabla inicial, S1 estará en la base.
  • Restricción 2: Tiene signo “≤” (menor igual) por lo que se agregará la variable de holgura S2. En la tabla inicial, S2 estará en la base.
  • A continuación se muestra el problema en la forma estándar. Se colocará el coeficiente 0 (cero) donde corresponda para crear nuestra matriz:

Función Objetivo

Maximizar: Z = 2X1 + 3X2 + 0S1 + 0S2

Sujeto a:

-1X1 + 1X2 + 1S1 + 0S2 = 2

0X1 + 1X2 + 0S1 + 1S2 = 5

X1, X2, S1, S2 ≥ 0

Las letras presentes en las tablas corresponden a:

  • Cj: Vector de costes. Contiene los coeficientes de las variables de la función objetivo.
  • Cb: Coeficientes de los variables que conforman el vector solución.
  • Base: Variables que forman el vector solución.
  • Z: En esta fila encontrarás los valores del vector de costes reducidos. Se calcula multiplicando el vector solución por los coeficientes de las restricciones y se resta el vector de costes.
  • Xn, Sn: En cada una de las columnas se encuentran los coefientes de su variable correspondiente.
  • R: En esta columna se encuentra el término independiente de cada ecuación.
  • Se agregará un subíndice numérico adicional en las ecuaciones para identificar su posición en la tabla. Ejemplo: X1,2: Coeficiente de X1 en la fila 2. Para Cj y Z los subíndices indicarán su posición en la columna. Ejemplo: Cj,3: Indicaría el coeficiente de Cj en la columna 3.

Solución

Matriz Inicial

Para esta tabla, el valor de la fila Z se calculará así:

Z1 = (Cb,1*X1,1) + (Cb,2*X1,2) – Cj1 = (0*-1) + (0*0) – (2) = -2

Z2 = (Cb,1*X2,1) + (Cb,2*X2,2) – Cj2 = (0*1) + (0*1) – (3) = -3

Z3 = (Cb,1*S1,1) + (Cb,2*S1,2) – Cj3 = (0*1) + (0*0) – (0) = 0

Z4 = (Cb,1*S2,1) + (Cb,2*S2,2) – Cj4 = (0*0) + (0*1) – (0) = 0

Z5 = (Cb,1*R,1) + (Cb,2*R,2) = (0*2) + (0*5) = 0

Tabla 1 Cj 2 3 0 0
Cb Base X1 X2 S1 S2 R
0 S1 -1 1 1 0 2
0 S2 0 1 0 1 5
Z -2 -3 0 0 0

En el vector de costes reducidos (Z) tenemos valores negativos, por lo que debemos seleccionar el más negativo para la columna pivote (maximización).

El vector solución esta compuesto por los siguientes números: [-2, -3, 0, 0]. El más negativo 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.

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 positivo definirá la variable que saldrá de la base:

Fila S1 → R1 / X2,1 = 2 / 1 = 2 (Menor Valor Positivo)
Fila S2 → R2 / X2,2 = 5 / 1 = 5

El menor valor positivo 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

Iteración 1

Realizaremos las iteraciones de cada valor en la tabla considerando lo siguiente:

  • Nuevo Valor Fila Pivote = Valor Actual Fila Pivote / Elemento Pivote
  • Nuevo Valor = Valor Actual – (Elemento Fila Columna Pivote*Nuevo Valor Fila Pivote)

Cálculos en fila Pivote (Fila N° 1):

Valor Actual Fila Pivote -1 1 1 0 2
Elemento Pivote 1 1 1 1 1
Nuevo Valor Fila Pivote -1 / 1 = -1 1 / 1 = 1 1 / 1 = 1 0 / 1 = 0 2 / 1 = 2

Ahora calcularemos los nuevos valores para las otras filas de la tabla:

Fila 2:

Valor Actual 0 1 0 1 5
Elemento Fila Columna Pivote 1 1 1 1 1
Nuevo Valor Fila Pivote -1 1 1 0 2
Nuevo Valor 0 – (1×-1) = 1 1 – (1×1) = 0 0 – (1×1) = -1 1 – (1×0) = 1 5 – (1×2) = 3

Fila 3:

Valor Actual -2 -3 0 0 0
Elemento Fila Columna Pivote -3 -3 -3 -3 -3
Nuevo Valor Fila Pivote -1 1 1 0 2
Nuevo Valor -2 – (-3×-1) = -5 -3 – (-3×1) = 0 0 – (-3×1) = 3 0 – (-3×0) = 0 0 – (-3×2) = 6
Tabla 2 Cj 2 3 0 0
Cb Base X1 X2 S1 S2 R
3 X2 -1 1 1 0 2
0 S2 1 0 -1 1 3
Z -5 0 3 0 6

En el vector de costes reducidos (Z) tenemos valores negativos, por lo que debemos seleccionar el más negativo para la columna pivote (maximización).

El vector solución esta compuesto por los siguientes números: [-5, 0, 3, 0]. El más negativo es = -5 que corresponde a la variable X1. Esta variable ingresará a la base y sus valores en la tabla conformarán nuestra columna pivote.

Se verificará la condición de factibilidad, dividiendo los valores de la columna R entre la columna pivote X1. 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 positivo definirá la variable que saldrá de la base:

Fila X2 → R1 / X1,1 = 2 / -1 = N/A
Fila S2 → R2 / X1,2 = 3 / 1 = 3 (Menor Valor Positivo)

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

Ingresa la variable X1 y sale de la base la variable S2. El elemento pivote es 1

Iteración 2

Realizaremos las iteraciones de cada valor en la tabla considerando lo siguiente:

  • Nuevo Valor Fila Pivote = Valor Actual Fila Pivote / Elemento Pivote
  • Nuevo Valor = Valor Actual – (Elemento Fila Columna Pivote*Nuevo Valor Fila Pivote)

Cálculos en fila Pivote (Fila N° 2):

Valor Actual Fila Pivote 1 0 -1 1 3
Elemento Pivote 1 1 1 1 1
Nuevo Valor Fila Pivote 1 / 1 = 1 0 / 1 = 0 -1 / 1 = -1 1 / 1 = 1 3 / 1 = 3

Ahora calcularemos los nuevos valores para las otras filas de la tabla:

Fila 1:

Valor Actual -1 1 1 0 2
Elemento Fila Columna Pivote -1 -1 -1 -1 -1
Nuevo Valor Fila Pivote 1 0 -1 1 3
Nuevo Valor -1 – (-1×1) = 0 1 – (-1×0) = 1 1 – (-1×-1) = 0 0 – (-1×1) = 1 2 – (-1×3) = 5

Fila 3:

Valor Actual -5 0 3 0 6
Elemento Fila Columna Pivote -5 -5 -5 -5 -5
Nuevo Valor Fila Pivote 1 0 -1 1 3
Nuevo Valor -5 – (-5×1) = 0 0 – (-5×0) = 0 3 – (-5×-1) = -2 0 – (-5×1) = 5 6 – (-5×3) = 21
Tabla 3 Cj 2 3 0 0
Cb Base X1 X2 S1 S2 R
3 X2 0 1 0 1 5
2 X1 1 0 -1 1 3
Z 0 0 -2 5 21

En el vector de costes reducidos (Z) tenemos valores negativos, por lo que debemos seleccionar el más negativo para la columna pivote (maximización).

El vector solución esta compuesto por los siguientes números: [0, 0, -2, 5]. El más negativo es = -2 que corresponde a la variable S1. Esta variable ingresará a la base y sus valores en la tabla conformarán nuestra columna pivote.

Se verificará la condición de factibilidad, dividiendo los valores de la columna R entre la columna pivote S1. 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 positivo definirá la variable que saldrá de la base:

Fila X2 → R1 / S1,1 = 5 / 0 = N/A
Fila X1 → R2 / S1,2 = 3 / -1 = N/A

Ninguno de los valores de la columna pivote (denominador) son positivos; por lo tanto, no se cumple la condición de factibilidad y tenemos una solución ilimitada (no acotada).

El problema tiene solución ilimitada (no acotada). La variable S1 debe entrar a la base pero ninguna variable puede salir.

Ver Listado de Problemas Resueltos