Ejercicio 3.11 – Gutchi Company – Método Simplex 3 Variables – Investigación de Operaciones – Hamdy A. Taha
Gutchi Company fabrica bolsos de mano, bolsos para rasuradora y mochilas. La elaboración incluye piel y materiales sintéticos, y la piel es la materia prima escasa. El proceso de producción requiere dos tipos de mano de obra calificada: costura y acabado. La siguiente tabla da la disponibilidad de los recursos, su consumo por los tres productos y las utilidades por unidad.
REQUERIMIENTOS DE RECURSOS POR UNIDAD | ||||
---|---|---|---|---|
Recurso | Bolsos de Mano | Bolsos para rasuradora | Mochila | Disponibilidad diaria |
Piel (pies2) | 2 | 1 | 3 | 42 pies2 |
Costura (h) | 2 | 1 | 2 | 40 h |
Acabado (h) | 1 | 0.5 | 1 | 45 h |
Precio de venta ($) | 24 | 22 | 45 |
- Formule el problema como un programa lineal, y halle la solución óptima.
- A partir de la solución óptima, determine el estado de cada recurso.
Solución
a. El planteamiento del problema serÃa:
Maximizar Z=24x1+22x2+45x3
Sujeto a:
2x1+x2+3x3≤42
2x1+x2+2x3≤40
x1+0.5x2+x3≤45
x1, x2, x3≥0
Para resolver el problema por el método simplex utilizaremos la versión de membresÃa de nuestra calculadora de programación lineal:
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.
- Restricción 3: Tiene signo “≤” (menor igual) por lo que se agregará la variable de holgura S3. En la tabla inicial, S3 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 = 24X1 + 22X2 + 45X3 + 0S1 + 0S2 + 0S3
Sujeto a:
2X1 + 1X2 + 3X3 + 1S1 + 0S2 + 0S3 = 42
2X1 + 1X2 + 2X3 + 0S1 + 1S2 + 0S3 = 40
1X1 + 1/2X2 + 1X3 + 0S1 + 0S2 + 1S3 = 45
X1, X2, X3, S1, S2, S3 ≥ 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) + (Cb,3*X1,3) – Cj1 = (0*2) + (0*2) + (0*1) – (24) = -24
Z2 = (Cb,1*X2,1) + (Cb,2*X2,2) + (Cb,3*X2,3) – Cj2 = (0*1) + (0*1) + (0*1/2) – (22) = -22
Z3 = (Cb,1*X3,1) + (Cb,2*X3,2) + (Cb,3*X3,3) – Cj3 = (0*3) + (0*2) + (0*1) – (45) = -45
Z4 = (Cb,1*S1,1) + (Cb,2*S1,2) + (Cb,3*S1,3) – Cj4 = (0*1) + (0*0) + (0*0) – (0) = 0
Z5 = (Cb,1*S2,1) + (Cb,2*S2,2) + (Cb,3*S2,3) – Cj5 = (0*0) + (0*1) + (0*0) – (0) = 0
Z6 = (Cb,1*S3,1) + (Cb,2*S3,2) + (Cb,3*S3,3) – Cj6 = (0*0) + (0*0) + (0*1) – (0) = 0
Z7 = (Cb,1*R,1) + (Cb,2*R,2) + (Cb,3*R,3) = (0*42) + (0*40) + (0*45) = 0
Tabla 1 | Cj | 24 | 22 | 45 | 0 | 0 | 0 | |
---|---|---|---|---|---|---|---|---|
Cb | Base | X1 | X2 | X3 | S1 | S2 | S3 | R |
0 | S1 | 2 | 1 | 3 | 1 | 0 | 0 | 42 |
0 | S2 | 2 | 1 | 2 | 0 | 1 | 0 | 40 |
0 | S3 | 1 | 1/2 | 1 | 0 | 0 | 1 | 45 |
Z | -24 | -22 | -45 | 0 | 0 | 0 | 0 |
Se verificará la condición de factibilidad, dividiendo los valores de la columna R entre la columna pivote X3. 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 / X3,1 = 42 / 3 = 14 (Menor Valor Positivo)
Fila S2 → R2 / X3,2 = 40 / 2 = 20
Fila S3 → R3 / X3,3 = 45 / 1 = 45
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 X3 y la fila S1 = 3.
Ingresa la variable X3 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 | 1 | 3 | 1 | 0 | 0 | 42 |
---|---|---|---|---|---|---|---|
Elemento Pivote | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
Nuevo Valor Fila Pivote | 2 / 3 = 2/3 | 1 / 3 = 1/3 | 3 / 3 = 1 | 1 / 3 = 1/3 | 0 / 3 = 0 | 0 / 3 = 0 | 42 / 3 = 14 |
Ahora calcularemos los nuevos valores para las otras filas de la tabla:
Fila 2:
Valor Actual | 2 | 1 | 2 | 0 | 1 | 0 | 40 |
---|---|---|---|---|---|---|---|
Elemento Fila Columna Pivote | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
Nuevo Valor Fila Pivote | 2/3 | 1/3 | 1 | 1/3 | 0 | 0 | 14 |
Nuevo Valor | 2 – (2×2/3) = 2/3 | 1 – (2×1/3) = 1/3 | 2 – (2×1) = 0 | 0 – (2×1/3) = -2/3 | 1 – (2×0) = 1 | 0 – (2×0) = 0 | 40 – (2×14) = 12 |
Fila 3:
Valor Actual | 1 | 1/2 | 1 | 0 | 0 | 1 | 45 |
---|---|---|---|---|---|---|---|
Elemento Fila Columna Pivote | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Nuevo Valor Fila Pivote | 2/3 | 1/3 | 1 | 1/3 | 0 | 0 | 14 |
Nuevo Valor | 1 – (1×2/3) = 1/3 | 1/2 – (1×1/3) = 1/6 | 1 – (1×1) = 0 | 0 – (1×1/3) = -1/3 | 0 – (1×0) = 0 | 1 – (1×0) = 1 | 45 – (1×14) = 31 |
Fila 4:
Valor Actual | -24 | -22 | -45 | 0 | 0 | 0 | 0 |
---|---|---|---|---|---|---|---|
Elemento Fila Columna Pivote | -45 | -45 | -45 | -45 | -45 | -45 | -45 |
Nuevo Valor Fila Pivote | 2/3 | 1/3 | 1 | 1/3 | 0 | 0 | 14 |
Nuevo Valor | -24 – (-45×2/3) = 6 | -22 – (-45×1/3) = -7 | -45 – (-45×1) = 0 | 0 – (-45×1/3) = 15 | 0 – (-45×0) = 0 | 0 – (-45×0) = 0 | 0 – (-45×14) = 630 |
Tabla 2 | Cj | 24 | 22 | 45 | 0 | 0 | 0 | |
---|---|---|---|---|---|---|---|---|
Cb | Base | X1 | X2 | X3 | S1 | S2 | S3 | R |
45 | X3 | 2/3 | 1/3 | 1 | 1/3 | 0 | 0 | 14 |
0 | S2 | 2/3 | 1/3 | 0 | -2/3 | 1 | 0 | 12 |
0 | S3 | 1/3 | 1/6 | 0 | -1/3 | 0 | 1 | 31 |
Z | 6 | -7 | 0 | 15 | 0 | 0 | 630 |
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 X3 → R1 / X2,1 = 14 / 1/3 = 42
Fila S2 → R2 / X2,2 = 12 / 1/3 = 36 (Menor Valor Positivo)
Fila S3 → R3 / X2,3 = 31 / 1/6 = 186
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 X2 y la fila S2 = 1/3.
Ingresa la variable X2 y sale de la base la variable S2. El elemento pivote es 1/3
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 | 2/3 | 1/3 | 0 | -2/3 | 1 | 0 | 12 |
---|---|---|---|---|---|---|---|
Elemento Pivote | 1/3 | 1/3 | 1/3 | 1/3 | 1/3 | 1/3 | 1/3 |
Nuevo Valor Fila Pivote | 2/3 / 1/3 = 2 | 1/3 / 1/3 = 1 | 0 / 1/3 = 0 | -2/3 / 1/3 = -2 | 1 / 1/3 = 3 | 0 / 1/3 = 0 | 12 / 1/3 = 36 |
Ahora calcularemos los nuevos valores para las otras filas de la tabla:
Fila 1:
Valor Actual | 2/3 | 1/3 | 1 | 1/3 | 0 | 0 | 14 |
---|---|---|---|---|---|---|---|
Elemento Fila Columna Pivote | 1/3 | 1/3 | 1/3 | 1/3 | 1/3 | 1/3 | 1/3 |
Nuevo Valor Fila Pivote | 2 | 1 | 0 | -2 | 3 | 0 | 36 |
Nuevo Valor | 2/3 – (1/3×2) = 0 | 1/3 – (1/3×1) = 0 | 1 – (1/3×0) = 1 | 1/3 – (1/3×-2) = 1 | 0 – (1/3×3) = -1 | 0 – (1/3×0) = 0 | 14 – (1/3×36) = 2 |
Fila 3:
Valor Actual | 1/3 | 1/6 | 0 | -1/3 | 0 | 1 | 31 |
---|---|---|---|---|---|---|---|
Elemento Fila Columna Pivote | 1/6 | 1/6 | 1/6 | 1/6 | 1/6 | 1/6 | 1/6 |
Nuevo Valor Fila Pivote | 2 | 1 | 0 | -2 | 3 | 0 | 36 |
Nuevo Valor | 1/3 – (1/6×2) = 0 | 1/6 – (1/6×1) = 0 | 0 – (1/6×0) = 0 | -1/3 – (1/6×-2) = 0 | 0 – (1/6×3) = -1/2 | 1 – (1/6×0) = 1 | 31 – (1/6×36) = 25 |
Fila 4:
Valor Actual | 6 | -7 | 0 | 15 | 0 | 0 | 630 |
---|---|---|---|---|---|---|---|
Elemento Fila Columna Pivote | -7 | -7 | -7 | -7 | -7 | -7 | -7 |
Nuevo Valor Fila Pivote | 2 | 1 | 0 | -2 | 3 | 0 | 36 |
Nuevo Valor | 6 – (-7×2) = 20 | -7 – (-7×1) = 0 | 0 – (-7×0) = 0 | 15 – (-7×-2) = 1 | 0 – (-7×3) = 21 | 0 – (-7×0) = 0 | 630 – (-7×36) = 882 |
Tabla 3 | Cj | 24 | 22 | 45 | 0 | 0 | 0 | |
---|---|---|---|---|---|---|---|---|
Cb | Base | X1 | X2 | X3 | S1 | S2 | S3 | R |
45 | X3 | 0 | 0 | 1 | 1 | -1 | 0 | 2 |
22 | X2 | 2 | 1 | 0 | -2 | 3 | 0 | 36 |
0 | S3 | 0 | 0 | 0 | 0 | -1/2 | 1 | 25 |
Z | 20 | 0 | 0 | 1 | 21 | 0 | 882 |
La solución óptima es Z = 882
X1= 0, X2= 36, X3= 2, S1= 0, S2= 0, S3= 25
b. El estado de cada recurso serÃa:
Recurso | Holgura | Estado |
---|---|---|
Piel (pies2) | 0 | Escaso |
Costura (h) | 0 | Escaso |
Acabado (h) | 25 | Abundante |