,

Ejercicio Resuelto – Método Simplex para Minimizar

Artículos Relacionados  IA que escribe ensayos - Escribe 10 veces más rápido con GPT-3

En este problema, resolveremos un caso de minimización con el método simplex, donde no se utilizan variables artificiales.

Al no utilizarse variables artificiales no será necesario usar el método de las 2 fases o de la M grande.

Minimizar 2x1 – x2

Sujeto a:
2x1 + 3x2 ≤ 10
x1 + x2 ≤ 6
x1, x2 ≥ 0

Solución

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

Función Objetivo

Minimizar: Z = 2X1 – 1X2

Sujeto a:

2X1 + 3X2 ≤ 10

1X1 + 1X2 ≤ 6

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.
  • Restricción 2: Tiene signo “≤” (menor igual) por lo que se agregará la variable de holgura S2.

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

Minimizar: Z = 2X1 – 1X2 + 0S1 + 0S2

Sujeto a:

2X1 + 3X2 + 1S1 + 0S2 = 10

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

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 coeficientes 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*2) + (0*1) – (2) = -2

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

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*10) + (0*6) = 0

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

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

El vector solución esta compuesto por los siguientes números: [-2, 1, 0, 0]. El mayor valor es = 1 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 definirá la variable que saldrá de la base:

Fila S1 → R1 / X2,1 = 10 / 3 = 3.(3) (Menor Valor)
Fila S2 → R2 / X2,2 = 6 / 1 = 6

Los números entre paréntesis representan decimales periódicos. Ejemplo: 1.(3) = 1.33333…

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 = 3.

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

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 2 3 1 0 10
Elemento Pivote 3 3 3 3 3
Nuevo Valor Fila Pivote 2 / 3 = 2/3 3 / 3 = 1 1 / 3 = 1/3 0 / 3 = 0 10 / 3 = 10/3

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

Fila 2:

Valor Actual 1 1 0 1 6
Elemento Fila Columna Pivote 1 1 1 1 1
Nuevo Valor Fila Pivote 2/3 1 1/3 0 10/3
Nuevo Valor 1 – (1×2/3) = 1/3 1 – (1×1) = 0 0 – (1×1/3) = -1/3 1 – (1×0) = 1 6 – (1×10/3) = 8/3

Fila 3:

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

Dado que no tenemos valores positivos en el vector de costes reducidos (Z) = [-8/3, 0, -1/3, 0], significa que nos encontramos en el punto óptimo (minimización).

La solución óptima es Z = -10/3

X1= 0, X2= 10/3, S1= 0, S2= 8/3

Ver Listado de Problemas Resueltos
/por