• Author / Uploaded
• Jose F. Maestre

• Categories
• Programación lineal
• Conceptos matemáticos
• Física y matemáticas
• Matemáticas
• Álgebra

Citation preview

METODO SIMPLEX Este método resuelve un problema con cualquier número de restricciones y variables. Utiliza matrices, operaciones elementales sobre renglones y aritmética básica y no implica el uso de geometría. Comienza con una solución factible y prueba si es o no optima, si no lo es, el método sigue a una mejor solución (si es que existe la solución óptima) PROCEDIMIENTO: 1. Las restricciones se convierten en ecuaciones sumando o restando una cantidad “S” llamada variable de holgura (puesto que absorbe la holgura o bien absorbe la falta de consistencia que existe en lado izquierdo). Por ejemplo, si 2𝑋1 + 𝑋2 ≤ 8 → 2𝑋1 + 𝑋2 + 𝑆1 = 8 (para que el miembro de la izquierda sea igual al de la derecha, le sumamos 𝑆1 ). Si 3𝑋1 + 2𝑋2 ≥ 8 → 2𝑋1 + 𝑋2 - 𝑆2 = 8 el subíndice de “S” indica el número de la restricción, 𝑆1 pertenece a la primera restricción, 𝑆2 pertenece a la segunda restricción, es importante este orden para efectos del análisis de sensibilidad que veremos más adelante. 2. Construir la tabla SIMPLEX inicial que muestra la columna de la base, la columna de los elementos de la solución y la fila de los Indicadores (por norma es el último renglón de la tabla). 3. Elegir el indicador más negativo para la variable que entra a la base y elegir el menor cociente (elementos de la solución entre los elementos de la variable que entra a la base) como la variable que sale de la base. 4. Elegir el PIVOTE como el elemento de intersección entre la columna de los elementos de la variable que entra a la base y la fila de los elementos de la variable que sale de la base. 5. Convertir el pivote en 1 y convertir en cero los demás elementos de esa columna, mediante operaciones por renglones que tiene como apoyo la fila que contiene el pivote. 6. Construir la nueva matriz con los nuevos renglones, teniendo en cuenta la variable que va a entrar a la base y que reemplaza a la que sale. 7. El proceso es repetitivo hasta cuando se obtenga en la nueva tabla todos los indicadores NO NEGATIVOS (es decir, positivos incluido el cero) y los elementos de la columna solución sean todos positivos. PROBLEMAS DE APLICACIÓN POR EL METODO SIMPLEX 1. Una empresa fabrica tres tipos de refrigeradores: Modelo 1, Modelo 2 y Modelo 3. Para fabricar una unidad del primer modelo se necesitan 3 horas de trabajo y $300 de materiales; para cada unidad del segundo modelo se necesitan 2 horas de trabajo y $200 de materiales; mientras que para una unidad del tercer modelo se necesita 1 hora de trabajo y $100 de materiales. El costo de la materia prima para cada uno de los tres modelos es de $200 por unidad. Se dispone de un presupuesto de $300 por día para materiales y la nómina de trabajadores nos permite dedicar 60 horas diarias a la fabricación.

Sabiendo que la empresa obtiene ingresos por venta de $7000 del primer modelo; $8000 del segundo modelo y $6000 por unidad del tercer modelo: a). Formular el problema como un modelo de programación lineal que permita maximizar la utilidad b) ¿Cuántos modelos de cada tipo de refrigeradores se deben fabricar diariamente para que la utilidad sea máxima?

SOLUCION El primer paso siempre será definir las variables que intervienen en el proceso (las variables se definen de acuerdo a lo que nos piden en el problema): 𝑿𝟏 = Número de unidades del primer modelo a fabricar diariamente → (und. /día) 𝑿𝟐 = Número de unidades del segundo modelo a fabricar diariamente → (und. /día) 𝑿𝟑 = Número de unidades del tercer modelo a fabricar diariamente → (und. /día)

Tabla Resumen de datos: Refrigeradores Primer modelo Segundo modelo Tercer modelo Disponibilidad

Horas requeridas(hr/und) 3 2 1 60 hr/día

Material requerido($/und.) 300 200 100 $300/día

Costo Materia Prima ($/und.) 200 200 200 ------

Ingresos Por ventas ($/und.) 7000 8000 6000 --------

Calculamos la Utilidad de cada tipo para obtener los coeficientes de la función objetivo: UTILIDAD= VENTAS – COSTOS Para el Tipo 1: Utilidad = 7000 – 200 = $6800/und. Para el Tipo 2: Utilidad = 8000 – 200 = $7800/und. Para el Tipo 3: Utilidad = 6000 – 200 = $5800/und. Formulamos la función objetivo (el objetivo en todo negocio es maximizar la utilidad): Maximizar Z = 6800𝑋1 + 7800𝑋2 + 5800𝑋3 o bien, Maximizar Z = 68𝑋1 + 78𝑋2 + 58𝑋3 →

(X102 )

Tenga muy en cuenta las unidades: ($/día) = ($/und.) (und. /día) Formulación de las restricciones: Existe restricción en el tiempo y restricción en el material, así: Restricción de tiempo:

3𝑋1 + 2𝑋2 + 1𝑋3 ≤ 60 → (hr/und) (und. /día) = (hr/día)

Restricción de materiales:

300𝑋1 + 200𝑋2 + 100𝑋3 ≤ 300

Tenga muy en cuenta las unidades: ($/und.) (Und./día) ≤ ($/día) Restricciones de NO NEGATIVIDAD de las Variables: 𝑋𝑖 ≥ 0 Resumiendo, el Modelo matemático como un modelo de programación lineal:

Max. Z = 68𝑋1 + 78𝑋2 + 58𝑋3 → (X102 )

a)

3𝑋1 + 2𝑋2 + 1𝑋3 ≤ 60

Sujeta a:

300𝑋1 + 200𝑋2 + 100𝑋3 ≤ 300 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

b) Solución por el Método Simplex: El primer paso es convertir las desigualdades en ecuaciones mediante la adición de las variables de holguras 𝑆𝑖 puesto que las restricciones son del tipo ≤ y el coeficiente de “S” es +1, llamaremos (1) a la primera restricción y (2) a la segunda restricción, así: De (1): 3𝑋1 + 2𝑋2 + 1𝑋3 + 𝑆1 = 60 De (2): 300𝑋1 + 200𝑋2 + 100𝑋3 + 𝑆2 = 300 De Z = 68𝑋1 + 78𝑋2 + 58𝑋3 igualamos a cero: - 68𝑋1 - 78𝑋2 - 58𝑋3 + Z = 0 esta será la fila de los indicadores que ubicaremos de ultima en la tabla. El paso siguiente es construir la Tabla Simplex Inicial” Tabla Simplex 1

BASE

𝑿𝟏

𝑿𝟐

𝑿𝟑

S1

S2 Z

SOL.

3

2

1

1

0

0

60

←S2

300 (200) 100 0

1

0

300

Z

-68

1

0

S1

-78 ↑

-58 0 0

Cocientes

Formular operaciones F2 /200= NF2 (fila de apoyo) 60/2=30 -2NF2 + F1 = NF1 78NF2 + F3 = NF3 300/200=1.5 (menor cociente) Con esas operaciones por fila, convertimos el pivote en 1 y en cero los elementos por encima y por debajo (200) = Pivote de él en esa columna.

Entra a la base 𝑋2 (por tener el indicador más negativo), y sale de la base S2 (por tener el menor cociente que resulta de dividir el elemento de la columna solución entre el elemento de la variable que entra). Las operaciones matemáticas formuladas se muestran a continuación:

3⁄2 1 1⁄2 0 1⁄200 0 3⁄2

117 78 39 0 -68 -78 -58 0 49 0 -19 0

NF2(fila de apoyo) -3 -2 3 2 0 0

-1 1 0

0 -1⁄100 0 -3 1 0 0 60 ⁄ 1 -1 100 0 57 NF1

39⁄100 0 117 0 1 0 ⁄ 39 100 1 117 NF3

Construimos la nueva tabla Simplex con las nuevas filas, NF1, NF2 y NF3 teniendo en cuenta que en la columna de la base aparecerá 𝑋2 y no S2 como en la Tabla 1, así:

Tabla Simplex 2

BASE

𝑿𝟏

Cocientes

Z

3⁄2 1 (1⁄2) 0 1⁄200 0

3⁄2

0 -19 0 39⁄100 ↑

117

0

49

2

S2

0

0

Z

3

𝑿𝟑 S1

SOL. 57

S1 ←X2

𝑿𝟐

0

1 -1⁄100

0 1⁄100 0

1

3

1

Formular operaciones 2F2 = NF2 (fila de apoyo) 57/0=∞(des) F1 = NF1 19NF2 + F3 = NF3 3 1 ÷ = 3(menor cociente) 2 2 Con esas operaciones por fila, convertimos el pivote en 1 y en cero los elementos por encima y por debajo (1/2) = Pivote de él en esa columna.

NF2(fila de apoyo) 57 38 19 0 19⁄100 0 57 49 0 -19 0 39/100 1 117 106 38 0 0 58/100 1 174 NF3

Construimos la nueva tabla simplex (tabla optima porque los indicadores son todos no negativos, es decir, positivos incluido los ceros) teniendo en cuenta que en la base aparecerá 𝑿𝟑 en vez de 𝑿𝟐 , así:

Tabla Simplex Óptima

BASE

𝑿𝟏

𝑿𝟐

𝑿𝟑 S1

S2

Z

SOL.

S1

0

0

0

1 -1⁄100 0

57

𝑿𝟑

3

2

1

0 1/100 0

3

Z

106 38 0 0

58/100 1

174

Solución Óptima: 𝑿𝟏 = 0 (variable no básica)

𝑿𝟐 = 0 (variable no básica) 𝑿𝟑 = 3 (variable que está en la base)

S1 =57;

S2 =0

Z = $ 174 → (X102 ) Verificación: Z = 68(0) + 78(0) + 58(3) = 174 CONCLUSION: La empresa industrial debe fabricar tres (3) refrigeradores del modelo 3 y no debe fabricar refrigeradores del modelo 1 ni del modelo 2 para que la utilidad sea máxima, equivalente a $ 174 → (X102 ), es decir, $17400 por día.

S1 =57 significa que la disponibilidad de tiempo es abundante S2 =0 Significa que la disponibilidad de materiales se agotó (es escasa). 2. Una compañía

Naviera fabrica tres tipos de chalupas: Grandes, Medianas y Pequeñas.

Para fabricar una chalupa grande se necesitan 4 horas de trabajo, $300 de materiales y $50 de insumos. Por cada chalupa Mediana se necesitan 3 horas de trabajo, $200 de materiales y $30 de insumos; mientras que por cada unidad de la pequeña se necesitan 2 horas de trabajo, $100 de material y $20 de insumos. El costo de materia prima para la chalupa Grande es de $200 por unidad; $150 para la Mediana y $60 por unidad de la pequeña. Se dispone de un presupuesto de $500 por día para material; $400 por día para insumo y la nómina de trabajadores nos permite 65 horas diarias en la fabricación. Sabiendo que la compañía obtiene ingresos por ventas de $8000 por unidad de chalupa Grande; $7000 por la Mediana y de $5000 por unidad de la pequeña. a). Formular el problema como un modelo de programación lineal. b) ¿Cuántas chalupas de cada tamaño se deben fabricar diariamente para maximizar la utilidad? SOLUCION El primer paso siempre será definir las variables que intervienen en el proceso: 𝑿𝟏 = Número de chalupas grandes a fabricar diariamente → (und. /día) 𝑿𝟐 = Número de chalupas medianas a fabricar diariamente → (und. /día) 𝑿𝟑 = Número de chalupas pequeñas a fabricar diariamente → (und. /día) Los datos deben resumirse en una tabla para facilitar y visualizar mejor la formulación del problema:

CHALUPAS

Horas requeridas(hr/unid.)

Material requerido($/u)

Insumo requerido(($/u)

Ingresos por ventas($/u)

$50/und.

Costo materia prima($/und.) $200/und.

Grande

4 hr/und.

$300/und.

Mediana

3

“

200

“

30

“

150 “

7000

“

Pequeña

2

“

100

“

20

“

60

5000

“

Disponibilidad

65 hr/día

$500/día

$400/día

“

-----------

$8000/un

----------

Calculamos la utilidad de cada tipo de chalupas para obtener los coeficientes de la función objetivo: UTILIDAD = VENTA – COSTOS Para la Chalupa grande: Utilidad = 8000 – 200 = $7800/und. Para la Chalupa Mediana: Utilidad = 7000 – 150 = $6850/und. Para la Chalupa Pequeña: Utilidad =5 000 – 60 = $4940/und. La utilidad son los coeficientes de la función objetivo: Maximizar Z = 7800𝑋1 + 6850𝑋2 + 49400𝑋3 o bien, Maximizar Z = 780𝑋1 + 685𝑋2 + 494𝑋3 → (X101 ), simplificamos las cifras y al final en la solución óptima, multiplicamos por 10 el valor Z. Tenga muy en cuenta las unidades: ($/día) = ($/und.) (und. /día) Formulación de las restricciones: Existe restricción en el tiempo y restricción en el material, así: Restricción de tiempo:

4𝑋1 + 3𝑋2 + 2𝑋3 ≤ 65

Restricción de materiales:

300𝑋1 + 200𝑋2 + 100𝑋3 ≤ 500

Restricción de Insumos:

50𝑋1 + 30𝑋2 + 20𝑋3 ≤ 400

Tenga muy en cuenta las unidades: (hr/und.) (Und./día) ≤ (Hr/día) Restricciones de NO NEGATIVIDAD de las Variables: 𝑋1 , 𝑋2 , 𝑋3 ≥ 0 Resumiendo, el Modelo matemático como un modelo de programación lineal: a)

Max. Z = 780𝑋1 + 685𝑋2 + 494𝑋3 → (X101 )

Sujeta a:

4𝑋1 + 3𝑋2 + 2𝑋3 ≤ 65 300𝑋1 + 200𝑋2 + 100𝑋3 ≤ 500 50𝑋1 + 30𝑋2 + 20𝑋3 ≤ 400 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

b) Solución por el Método Simplex:

El primer paso es convertir las desigualdades en ecuaciones mediante la adición de las variables de holguras 𝑆𝑖 puesto que las restricciones son del tipo ≤ y el coeficiente de “S” es +1, llamaremos (1) a la primera restricción, (2) a la segunda restricción y (3) a la tercera, así: De (1): 4𝑋1 + 3𝑋2 + 2𝑋3 + 𝑆1 = 65 De (2): 300𝑋1 + 200𝑋2 + 100𝑋3 + 𝑆2 = 500 De (3): 50𝑋1 + 30𝑋2 + 20𝑋3 +𝑆3 = = 400 De Z = 780𝑋1 + 685𝑋2 + 494𝑋3 igualamos a cero: - 780𝑋1 - 685𝑋2 - 494𝑋3 + Z = 0 esta será la fila de los indicadores que ubicaremos de ultima en la tabla. El paso siguiente es construir la Tabla Simplex Inicial Tabla Simplex 1

BASE S1 ←S2

𝑿𝟏

𝑿𝟐

𝑿𝟑 S1 S2 S3

4

3

2

Z

SOL.

1

0

0 0

65

(300) 200 100 0

1

0 0

500

S3

50

30 20 0 0

1

0

400

Z

-780 -685 -494 0 0 0 ↑

1

0

Cocientes 65/4=16.2 500/300=1.6

Formular operaciones F2 /300= NF2 (apoyo) -4NF2 + F1 = NF1 -50NF2 + F3 = NF3 780NF2 + F4 = NF4

400/50=8

(300) = Pivote Con esas operaciones por fila, convertimos el pivote en 1 y en cero los elementos por encima y por debajo del pivote. Entra a la base 𝑋2 (por tener el indicador más negativo), y sale de la base S2 (por tener el menor cociente que resulta de dividir el elemento de la columna solución entre el elemento de la variable que entra). Las operaciones matemáticas formuladas se muestran a continuación: 1 2⁄3 1⁄3 0 1⁄300 0 0 5/3

NF2(fila de apoyo)

-4 -8/3 -4/3 0 -4⁄300 0 0 -20/300 4 3 2 1 0 0 0 63 ⁄ 0 1/3 2/3 1 -4 300 0 0 173/3 NF1 -50 -100/3 -50/3 0 -50/300 0 0 −250⁄3 50 30 20 0 0 1 0 400 0

-10/3 10/3 0

-1/6

1

0

950/3 NF3

780 520 260 0 780/300 0 0 1300 -780 -685 -494 0 0 0 1 0 0

-165

-234 0

39/15 0 1 1300 NF4

Con estas nuevas operaciones construimos la nueva tabla simplex cambiando S2 por𝑿𝟏 (base)

Tabla Simplex 2

BASE

𝑿𝟏 𝑿𝟐

S1

𝑿𝟑 S1 S2

S3

0 1/3 2/3 1 2/150 0

Z

SOL.

0

175/3

Formular operaciones

5/3 ÷1/3=5 (menor cociente)

← 𝑿𝟏

1 2/3 (1/3) 0 1/300 0 0 0

5/3

S3

0 -10/3 10/3 0 -1/6 1 0

950/3

Z

0 -165 -234 0 39/15 0 ↑

1300

1

Cocientes 87.5

950/3÷10/3=95

Formulamos las operaciones:

(1/3) = Pivote

3F2 = NF2 (fila de apoyo) -2/3NF2 + F1 = NF1 -10/3NF2 + F3 = NF3 234NF2 + F4 = NF4

Entra a la base 𝑋3 (por tener el indicador más negativo), y sale de la base 𝑿𝟏 (por tener el menor cociente que resulta de dividir el elemento de la columna solución entre el elemento de la variable que entra). El razonamiento analítico de las operaciones matemáticas es el siguiente: 3

2 1

0 1/100 0 0 5

-2 -4/3 -2/3 0 1/3 2/3

0 1

-2/300 2/150

-2

1

1/150

-1

0

-10 -20/3 -10/3 0 -1/30 0

→NF2 (apoyo)

0 0 0

0 −10⁄3 0 175/3 0

0 -50/3

0 -10/3 10/3 0 -1/6 1

0 950/3

-10 -10

300 NF3

0

0 -1/5

1

0

55 NF1

702 468 234 0 234/100 0 0 1170 0 -165 -234 0 39/15 0 1 1300 702

303

0

0

247/50

0 1 2470 NF4

Tabla Simplex óptima

BASE

𝑿𝟏 𝑿𝟐 𝑿𝟑 S1 S2

S3

Z

SOL.

SOLUCION ÓPTIMA: 𝑿𝟏 = 0(no básica)

S1

-2 -1

0 1 1/150 0

0

55

𝑿𝟑

3

1 0 1/100 0

0

5

S3

-10 -10 0 0 -1/5

1

0

300

Z

702 303 0 0 247/50 0

1

2470

2

𝑿𝟐 = 0(no básica) 𝑿𝟑 = 5(básica) Z = $2470 → (X101 )

CONCLUSIÖN: La compañía naviera debe producir solamente 5 chalupas pequeñas por día para que la utilidad sea máxima, equivalente a $24700/día. 3. Una compañía fabrica dos tipos de productos: “A” y “B”. Las operaciones, tiempo requerido y mano de obra son las siguientes: Operación 1 2 3 4

Tiempo requerido (min. /und) A B 30 12 18 20 16 40 8 0

Maquinaria utilizada 2 maq. 3 maq. 4 maq. 1 maq.

Costo de mano de obra por hora $30/hr $60/hr $90/hr $45/hr

El precio de venta del producto A es de $121 y de B de $150 por unidad. El costo de la materia prima para ambos productos es de $34 por unidad. Cada máquina trabaja 40 horas por semana. a) Formular el problema como un modelo de programación lineal que permita maximizar las utilidades de cada producto. b) Encontrar el número de unidades que se deben fabricar por semana, de cada producto. SOLUCION El primer paso siempre será definir las variables que intervienen en el proceso: 𝑿𝟏 = Número de unidades del producto A, a fabricar por semana → (und. /sem.) 𝑿𝟐 = Número de unidades del producto B, a fabricar por semana → (und. /sem.) Calculamos la utilidad de cada producto para obtener los coeficientes de la función objetivo: UTILIDAD = VENTA – COSTOS Para el producto A: como el precio de venta está en $/und. Significa que los costos totales debemos llevarlos también a $/und. (Convertimos los minutos a horas):

1

1

1

-Costo de mano de obra= 30(60)(hr/und)($30/hr) +18(60)(hr/und)($60/hr) + 16(60)(hr/und)($90/hr) + 1

8(60)(Hr/und)($45/hr) = $63/und. -Costo de materia prima = $34/und. (Lo da el enunciado del problema en esas unidades). -Costos totales del producto A = $63/und. + $34/und. = $97/und. Utilidad del producto A = $121/und. - $97/und. = $24/und. Para el producto B: 1

1

1

-Costo de mano de obra= 12(60)(hr/und)($30/hr) +20(60)(hr/und)($60/hr) + 40(60)(hr/und)($90/hr) + 1

0( )(hr/und)($45/hr) = $86/und. 60

-Costo de materia prima = $34/und. (lo da el enunciado del problema en esas unidades). -Costos totales del producto B = $86/und. + $34/und. = $120/und. Utilidad del producto B = $150/und. - $120/und. = $30/und. 24𝑿𝟏 = ganancia por producir 𝑿𝟏 unidades de A, que se venden a $24/und. 30𝑿𝟐 = ganancia por producir 𝑿𝟐 unidades de B, que se venden a $30/und.

Formulamos la función objetivo (el objetivo en todo negocio es maximizar la utilidad): Maximizar Z = 24𝑋1 + 30𝑋2 o bien, Max. Z = 24𝑋1 + 30𝑋2 Definimos las restricciones: El problema nos dice que cada máquina trabaja 40 horas por semana, esto significa que 2 máquinas trabajan 80 hrs/sem. De forma análoga 3 máquinas trabajan 120 hrs/sem…etc. El tiempo requerido para A y B de la tabla, lo convertimos en hr/und. Así: 1

1

60

60

Para la operación 1: 30( )(hr/und) 𝑿𝟏 (und/sem)+12( )(hr/und) 𝑿𝟐(und/sem) ≤ 80hrs/sem 1

1

1

1

Para la operación 2: 18(60)(hr/und) 𝑿𝟏 (und/sem) + 20(60)(hr/und) 𝑿𝟐 (und/sem) ≤ 120hrs/sem Para la operación 3: 16(60)(hr/und) 𝑿𝟏 (und/sem) + 40(60)(hr/und) 𝑿𝟐 (und/sem) ≤ 160hrs/sem 1

1

60

60

Para la operación 4: 8( )(hr/und) 𝑿𝟏 (und/sem) + 0( )(hr/und) 𝑿𝟐 (und/sem) ≤ 40hrs/sem Restricción de no negatividad de las variables: 𝑋1 , 𝑋2 , ≥ 0 Resumiendo, el Modelo matemático como un modelo de programación lineal corresponde a: a)

Max. Z = 24𝑋1 + 30𝑋2

1/2𝑋1 + 1/5𝑋2 ≤ 80

Sujeta a:

3/10𝑋1 + 1/3𝑋2 ≤ 120 4/15𝑋1 + 2/3𝑋2 ≤ 160 2/15𝑋1 + 0 ≤ 40 𝑋1 , 𝑋2 ≥ 0 b) Solución por el Método Simplex: El primer paso es convertir las desigualdades en ecuaciones mediante la adición de las variables de holguras 𝑆𝑖 puesto que las restricciones son del tipo ≤ y el coeficiente de “S” es +1, llamaremos (1) a la primera restricción, (2) a la segunda restricción, (3) a la tercera, así: De (1):

1/2𝑋1 + 1/5𝑋2 + 𝑆1 = 80

De (2):

3/10𝑋1 + 1/3𝑋2 + 𝑆2 = 120

De (3):

4/15𝑋1 + 2/3𝑋2 +𝑆3 = = 160

De (4):

2/15𝑋1 +𝑆4

= 40

De Z = 24𝑋1 + 30𝑋2 igualamos a cero:

−24𝑋1 - 30𝑋2 + Z = 0

Esa será la fila de los indicadores que ubicaremos de última en la tabla. El paso siguiente es construir la Tabla Simplex Inicial” encabezada por las variables estructurales o variables de decisión y por las variables de holguras (la variable Z es opcional en el encabezamiento), tanto las variables de holgura como la variable Z tienen coeficientes 1, esto permite la conformación de la matriz unitaria entre ellas y es una característica muy particular del método Simplex, es decir, la intersección de las mismas variables que están en la base con las mismas que encabezan el primer renglón, siempre debe tener 1 como elemento de intersección.

Tabla Simplex 1

BASE

𝑿𝟏

𝑿𝟐

S1 S2 S3

S4 Z

SOLUCION COCIENTES

S1 S2 ←S3 S4 Z

1/2 1/5 1 0

0 0

80

400

0

0

120

360

4/15 (2/3) 0 0 1

0 0

160

240 →

2/15 0 -24 -30 ↑

1 0

3/10 1/3

0

0 1 0

0 0 0 0 0 0

0 1

40

40/0= ∞ 0

(2/3) = Pivote Formular operaciones 3/2F3 = NF3 (fila de apoyo) -1/5NF3 + F1 = NF1 -1/3NF3 + F2 = NF2 F4 = NF4 30NF3 + F5 = NF5 Con esas operaciones por fila convertimos el pivote en 1 y convertimos en cero los demás elementos que están por encima y por debajo del pivote en esa columna. Después de dos iteraciones se llega a la tabla óptima simplex y se concluye que se deben fabricar semanalmente 314 unidades del producto “A” y 115 unidades del producto “B” para que la utilidad sea máxima, equivalente a $10986 por semana. 4. Una compañía fabrica tres tipos de muebles: Sillas, mecedoras y sofá. Cada uno de estos artículos requiere madera, plástico y aluminio, como lo indica la tabla siguiente: MUEBLES Silla Mecedora Sofá

MADERA 1 unidad 1 unidad 1 unidad

PLASTICO 1 unidad 1 unidad 2 unidades

ALUMINIO 2 unidades 3 unidades 5 unidades

La compañía dispone de 400 unidades de madera, 500 unidades de plástico y 1450 unidades de aluminio. Cada silla, mecedora y sofá producen utilidades de $7, $8 y $12 respectivamente. Suponiendo que pueden venderse todos los muebles: a) Formular el problema como un modelo de programación lineal que permita maximizar los ingresos. b) ¿Cuántas unidades de cada producto se deben fabricar mensualmente para que los ingresos totales sean máximos y a cuánto ascienden? SOLUCION El primer paso siempre será definir las variables que intervienen en el proceso: 𝑿𝟏 = Número de sillas a fabricar mensualmente → (und. Silla /mes)

𝑿𝟐 = Número de mecedoras a fabricar mensualmente → (und. Meced. /Mes) 𝑿𝟑 = Número de sofás a fabricar mensualmente → (und. Sofás/mes) Para la función objetivo las unidades corresponden a: ($/und.) (Und. /Mes) = $/mes. Resumimos los datos en una Tabla: Tabla resumen de datos MUEBLES Silla Mecedora Sofá

MADERA 1 unidad 1 unidad 1 unidad

PLASTICO 1 unidad

1 unidad 2 unidad

ALUMINIO 2 unidades 3 unidades 5 unidades

UTILIDAD $7/ unidad $8/unidad $12 /unidad

Disponibilidad

400 unds/mes

500 unds/mes

1450 unds/mes

------------------

Formulamos la Función Objetivo teniendo en cuenta que los coeficientes de las variables son las Utilidades obtenidas en la fabricación de cada tipo de mueble, así: a)

Max. Z = 7𝑋1 + 8𝑋2 + 12𝑋3

Sujeta a:

𝑋1 + 𝑋2 + 𝑋3 ≤ 400 𝑋1 + 𝑋2 + 2𝑋3 ≤ 500 2𝑋1 + 3𝑋2 + 5𝑋3 ≤ 1450 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

b) Solución por el Método Simplex: El primer paso es convertir las desigualdades en ecuaciones mediante la adición de las variables de holguras (𝑆𝑖 ) puesto que las restricciones son del tipo ≤ y el coeficiente de “S” es +1, llamaremos (1) a la primera restricción, (2) a la segunda restricción y (3) a la tercera, así: De (1): 𝑋1 + 𝑋2 + 𝑋3 + 𝑆1 = 400 De (2): 𝑋1 + 𝑋2 + 2𝑋3 + 𝑆2 = 500 De (3): 2𝑋1 + 3𝑋2 + 5𝑋3 + 𝑆3 = 1450 De Z = 7𝑋1 + 8𝑋2 + 12𝑋3 igualamos a cero: - 7𝑋1 - 8𝑋2 - 12𝑋3 + Z = 0 esta será la fila de los indicadores que ubicaremos de ultima en la tabla (esta será la última fila en la tabla para que la matriz unitaria se construya correctamente en la tabla inicial). El paso siguiente es construir la Tabla “Simplex Inicial” en donde aparezcan en el renglón superior las variables estructurales Xi y las variables de holgura Si (la variable Z es opcional en ese renglón, pero si debe ubicarse en la columna de la base en la parte inferior). Las variables estructurales también se conocen como variables de decisión.

Tabla Simplex Inicial BASE 𝑺𝟏

← 𝑺𝟐 𝑺𝟑 Z

𝑿𝟏

𝑿𝟐

𝑿𝟑

𝑺𝟏

1 1 2 -7

1 1 3 -8

1 (2) 5 -12

1 0 0 0

𝑺𝟐 0 1 0 0

𝑺𝟑 Z

SOL

0 0 1 0

400 500 1450 0

0 0 0 1

↑ Pivote = (2) Formulación de las operaciones: 1/2𝐹2= 𝑁𝐹2 (fila de apoyo), 𝑁𝐹2 = Nueva fila 2 −1𝑁𝐹2 + 𝐹1 = 𝑁𝐹1 ; -5 𝑁𝐹2 + 𝐹3 = 𝑁𝐹3 ;

1/2

1

-1/2 -1/2 1 1

-1 1

1/2

1/2

0

1/2

0

-5/2 -5/2 2 3

-5 5

-1/2

1/2

0

½

0 1 1

0 0

0

0

NF2 (apoyo)

250

-1/2 0

0 0

0 0

-1/2

0

0

-5/2 0

0 1

0 0

0 -5/2

12𝑁𝐹2 + 𝐹4 = 𝑁𝐹4

1

-250 400 150 NF1

-1250 1450 0

6 -7

6 -8

12 -12

0 0

6 0

0 0

0 1

-1

-2

0

0

6

0

1

200 NF3

3000 0 3000 NF4

Una vez realizadas las operaciones algebraicas, obtenemos las nuevas Filas con las cuales construimos la nueva matriz (tabla simplex 2), teniendo en cuenta que aparecerá 𝑿𝟑 en vez de S2 en la columna de la base, así:

Tabla Simplex 2 BASE

𝑿𝟏

𝑿𝟐

𝑿𝟑

𝑺𝟏

𝑺𝟐

𝑺𝟑

Z

SOL

COCIENTES

← S1

1/2

(1/2)

0

1

-1/2

0

0

150

150/1/2=300→

𝑿𝟑 𝑺𝟑 Z

1/2 -1/2 -1

1/2 1/2 -2

(2) 5 0

0 0 0

1 0 6

0 1 0

0 0 1

250 200 3000

250/1/2=500 200/1/2=400

↑ Pivote = (1/2) Obsérvese que el indicador más negativo es -2, esto significa que entra a la base X2 y para elegir la variable saliente escogimos el menor cociente, es decir, 150/ (1/2) = 300 (que es menor que 400 y menor que 500) Formulación de las operaciones: 2𝐹1 = 𝑁𝐹1 (fila de apoyo), 𝑁𝐹1 = Nueva fila 1 −1/2𝑁𝐹1 + 𝐹2 = 𝑁𝐹2 ; -1/2𝑁𝐹1 + 𝐹3 = 𝑁𝐹3 ;

1

1

0

-1/2 -1/2 1/2 1/2 0

2

0 1

0

-1

0

0

-1 0

1/2 1/2

0

1

0

1

-1

0 0

0

100 NF2

-150 200

-1 0

1/2 -5/2

0 1

0 0

-1

0

-1

-2

1

0

1

-150 250

0

0 0

2 -1

NF1 (apoyo

300

-1/2 -1/2 -1/2 1/2 0

2𝑁𝐹1 + 𝐹4 = 𝑁𝐹4

200 NF3

2 -2

0 0

4 0

-2 6

0 0

0 1

600 3000

0

0

4

4

0

1

3600 NF 4

Una vez realizadas las operaciones algebraicas, obtenemos las nuevas Filas con las cuales construimos la nueva matriz (tabla óptima simplex), teniendo en cuenta que aparecerá 𝑿𝟐 en vez de S1 en la columna de la base, así: Tabla Óptima Simplex BASE 𝑿𝟐 𝑿𝟑 𝑺𝟑 Z

𝑿𝟏

𝑿𝟐

1 0 -1 1

1 0 0 0

𝑿𝟑

𝑺𝟏

0 1 0 0

2 -1 -1 4

𝑺𝟐 -1 1 -2 4

𝑺𝟑

Z

SOL

0 0 1 0

0 0 0 1

300 100 50 3600

SOLUCION ÓPTIMA: 𝑿𝟏 = 0 (no básica); X2 = 300 y X3 = 100 y Z = $3600/mes. Prueba: Z = 7(0) + 8(300) + 12(100) = 3600 CONCLUSION: La compañía debe fabricar mensualmente 300 mecedoras, 100 sofás y no debe fabricar sillas, para que los ingresos totales sean máximos, equivalentes a $3600/mes. 5. Una compañía fabrica dos tipos de productos: “A” y “B”. Las operaciones, tiempo requerido y mano de obra son las siguientes: Operación 1 2 3

Tiempo requerido (min. /und) A B 30 12 18 20 8 0

Maquinaria utilizada 2 maq. 3 maq. 1 maq.

Costo de mano de obra por hora $30/hr $60/hr $45/hr

El precio de venta del producto A es de $121 y de B de $150 por unidad. El costo de la materia prima para ambos productos es de $34 por unidad. Cada máquina trabaja 40 horas por semana. a) Formular el problema como un modelo de programación lineal que permita maximizar las utilidades de cada producto. b) Encontrar el número de unidades que se deben fabricar de cada producto por semana. SOLUCION El primer paso siempre será definir las variables que intervienen en el proceso: 𝑿𝟏 = Número de unidades del producto A, a fabricar por semana → (und. /sem.) 𝑿𝟐 = Número de unidades del producto B, a fabricar por semana → (und. /sem.) Para mejor apreciación construimos la tabla resumen convirtiendo los minutos en hora en las columnas encabezadas por “A” y B”, es decir, dividimos por 60 y simplificamos para trabajar con fraccionarios: TABLA RESUMEN DE DATOS Operación 1 2 3 Costo materia prima Precio de Venta

Tiempo requerido (hr. /und) A B 1/2 1/5 3/10 1/3 2/15 0

Maquinaria utilizada 2 maq. 3 maq. 1 maq.

Costo de mano de obra por hora $30/hr $60/hr $45/hr

$34/und.

$34/und.

-----------------

----------------

$121/und.

$150/und.

------------------

-----------------

Calculamos la utilidad de cada producto para obtener los coeficientes de la función objetivo: UTILIDAD = VENTA – COSTOS Para el producto A: como el precio de venta está en $/und. Significa que los costos totales debemos llevarlos también a $/und. (Convertimos los minutos a horas): 1

1

60

60

-Costo de mano de obra= 30( )(hr/und)($30/hr) +18( )(hr/und)($60/hr)

1

+ 8( )(Hr/und)($45/hr) = 60

$39/und. -Costo de materia prima = $34/und. (Lo da el enunciado del problema en esas unidades). -Costos totales del producto A = $39/und. + $34/und. = $73/und. Utilidad del producto A = $121/und. - $73/und. = $48/und. Para el producto B: 1

1

1

-Costo de mano de obra= 12(60)(hr/und)($30/hr) +20(60)(hr/und)($60/hr) + 0(60)(hr/und)($45/hr) = $26/und. -Costo de materia prima = $34/und. (Lo da el enunciado del problema en esas unidades). -Costos totales del producto B = $26/und. + $34/und. = $60/und. Utilidad del producto B = $150/und. - $60/und. = $90/und. 48𝑿𝟏 = Utilidad por producir 𝑿𝟏 unidades de A, que se venden a $48/und. 90𝑿𝟐 = Utilidad por producir 𝑿𝟐 unidades de B, que se venden a $70/und.

Formulamos la función objetivo (el objetivo en todo negocio es maximizar la utilidad): Maximizar Z = 48𝑋1 + 90𝑋2 o bien, Max. Z = 48𝑋1 + 90𝑋2 Definimos las restricciones: El problema nos dice que cada máquina trabaja 40 horas por semana, esto significa que 2 máquinas trabajan 80 hrs/sem. De forma análoga 3 máquinas trabajan 120 hrs/sem…etc. 1/2𝑋1 + 1/5𝑋2 ≤ 80 → la operación 1 tiene 2 máquinas (2x 40=80 hrs/semana) 3/10𝑋1 + 1/3𝑋2 ≤ 120 → la operación 2 tiene 3 máquinas (3x 40=120 hrs/semana) 2/15𝑋1 + 0 ≤ 40→ la operación 1 tiene 1 máquinas (1x 40=40 hrs/semana) Resumiendo, el Modelo matemático como un modelo de programación lineal corresponde a: a)

Max. Z = 48𝑋1 + 90𝑋2

1/2𝑋1 + 1/5𝑋2 ≤ 80

Sujeta a:

3/10𝑋1 + 1/3𝑋2 ≤ 120 2/15𝑋1 + ≤ 40 𝑋1 , 𝑋2 ≥ 0 b) Solución por el Método Simplex: El primer paso es convertir las desigualdades en ecuaciones mediante la adición de las variables de holguras 𝑆𝑖 puesto que las restricciones son del tipo ≤ y el coeficiente de “S” es +1, llamaremos (1) a la primera restricción, (2) a la segunda restricción, (3) a la tercera, así: De (1):

1/2𝑋1 + 1/5𝑋2 + 𝑆1 = 80

De (2):

3/10𝑋1 + 1/3𝑋2 + 𝑆2 = 120

De (3):

2/15𝑋1 + 𝑆3 = = 40

De Z = 48𝑋1 + 90𝑋2 igualamos a cero:

−48𝑋1 - 90𝑋2 + Z = 0

Esa será la fila de los indicadores que ubicaremos de última en la tabla. El paso siguiente es construir la Tabla Simplex Inicial” encabezada por las variables estructurales o variables de decisión y por las variables de holguras (la variable Z es opcional en el encabezamiento), tanto las variables de holgura como la variable Z tienen coeficientes 1, esto permite la conformación de la matriz unitaria entre ellas y es una característica muy particular del método Simplex, es decir, la intersección de las mismas variables que están en la base con las mismas que encabezan el primer renglón, siempre debe tener 1 como elemento de intersección. Tabla Simplex 1

BASE S1

S3

Z

1

0

0

0

80

400

3/10 (1/3 ) 0 1

0

0

120

360→

2/15

40

𝑿𝟐

1/2 1/5

←S2 S3

Z

S1 S2

𝑿𝟏

-48

0

0

0

1

0

-90 ↑

0

0

0

1

(1/3) = Pivote Formular operaciones 3F2 = NF2 (fila de apoyo) -1/5NF2 + F1 = NF1 F3 = NF3 90NF2 + F4 = NF4

SOLUCION COCIENTES

∞ (descarta)

0

Con esas operaciones por fila convertimos el pivote en 1 y convertimos en cero los demás elementos que están por encima y por debajo del pivote en esa columna. 1

9/10

0

-9/50 -1/5 1/2 1/5 8/25

3

0

0

0 1

-3/5 0

0 0

0 0

1

-3/5

0

0

0

→ NF2 (apoyo)

360

- 72 80 8 →NF1

0

0

0

1

0

81 -48

90 -90

0 0

270 0

0 0

0 0

32400 0

33

0

0

270

0

0

32400 NF4

2/15

40

NF3

Una vez realizadas las operaciones algebraicas, obtenemos las nuevas Filas con las cuales construimos la nueva matriz (tabla óptima simplex), teniendo en cuenta que aparecerá 𝑿𝟐 en vez de S2 en la columna de la base, así: Tabla Simplex Optima

BASE S1

𝑿𝟏

𝑿𝟐

8/25 0

S1 S2

S3

1 -3/5

Z

0

SOLUCION

0

8

X2

9/10

1

0

3

0

0

360

S3

2/15

0

0

0

1

0

40

33

0

0

270 0

Z

1

32400

SOLUCION OPTIMA: Z=32400 cuando 𝑿𝟏 = 0 (no básica); 𝑿𝟐 = 360 CONCLUSION: La compañía debe fabricar 300 unidades por semana del producto “B” y no debe fabricar el producto “A” para que las utilidades sean Máximas equivalentes a $32400 por semana

6. 3. Una fábrica de juguetes está preparando un programa de producción para tres nuevos artículos llamados “Capulina”, “Carmelina” y “Chicholina”. Los ingenieros asesores le advierten a la fábrica que ese programa que está preparando no es factible; sin embargo, la fábrica plantea lo siguiente: Cada juguete capulina requiere de 2 horas en la maquina A, 3 horas en la maquina B y 2 horas para terminado, y la utilidad por unidad de capulina es de $8 tal como lo muestra la tabla siguiente: JUGUETE

MAQUINAS(hr/und) A B 2 3 2 1 1 2

Capulina Carmelina Chicholina

TERMINADO(hr/und)

UTILIDAD($/und)

2 2 3

8 7 6

Las horas de trabajos disponibles de los empleados por semana son: para la maquina A, 70 horas por semana, 60 horas para la maquina B y para terminado, 50 horas. a) Formular el problema como un modelo matemático de programación lineal que permita maximizar las utilidades de cada juguete. b). Verificar la veracidad de los ingenieros asesores determinando el número de unidades que se deben fabricar de cada juguete por semana para maximizar la utilidad. SOLUCION El primer paso siempre será definir las variables que intervienen en el proceso: 𝑿𝟏 = Número de unidades del articulo Capulina, a fabricar por semana → (und. /sem.) 𝑿𝟐 = Número de unidades del articulo Carmelina, a fabricar por semana → (und. /sem.) 𝑿𝟑 = Número de unidades del artículo Chicholina, a fabricar por semana → (und. /sem.) Para mejor apreciación construimos la tabla resumen de datos: TABLA RESUMEN DE DATOS JUGUETE Capulina Carmelina Chicholina

MAQUINAS ( hr/und. ) A B 2 3 2 1 1 2

Disponibilidad

70 hr/sem.

60 hr/sem.

TERMINADO (hr/und.) 2 2 3 50 hr/sem.

UTILIDAD ($/hr.) 8 7 6 ----------------

Resumen del modelo como un modelo matemático de Programación Lineal a). Maximizar Z= 8X1 + 7X2 + 6X3 Sujeta a:

2𝑋1 + 2𝑋2 + 𝑋3 ≤ 70 3𝑋1 +1𝑋2 + 2𝑋3 ≤ 60 2𝑋1 + 2𝑋2 + 3𝑋3 ≤ 50

𝑋1 , 𝑋2 , 𝑋3 ≥ 0 b). Convertimos las restricciones en igualdad agregando las variables de Holgura: De (1):

2𝑋1 + 2𝑋2 + 𝑋3 + S1 = 70

De (2):

3𝑋1 +1𝑋2 + 2𝑋3 + S2 = 60

De (3):

2𝑋1 + 2𝑋2 + 3𝑋3 + S3 = 50

De la FO: - 8X1 - 7X2 - 6X3 + Z = 0 Construimos la tabla Simplex Inicial: Tabla Simplex Inicial

BASE

𝑿𝟏

𝑿𝟐

X3 S1 S2

S3

Z

S1

2

2

1

1

0

←S2

(3)

1

2

0

1

S3

2

2

3

0

Z

-8 ↑

-7

-6

0

SOLUC.

COC.

0

0

70

35

0

0

60

20 →

0

1

0

50

25

0

0

1

0

Entra X1 y sale S2 de la base. Pivote = (3) Formulamos las operaciones 1/3F2 = NF2 (fila de apoyo) -2NF2 + F1 = NF1 -2NF2 + F3 = NF3 8NF2 + F4 = NF4

Con esas operaciones por fila convertimos el pivote en 1 y convertimos en cero los demás elementos que están por encima y por debajo del pivote en esa columna. 1

1/3

2/3

0

0

0 0

0 0

-2 -2/3 -4/3 2 2 1

0 1

0

1 -2/3

0

0

0

0

0

4/3

-1/3

-2 -2/3 -4/3

-2/3 0

1/3

-2/3

0 20

-40 70 30 NF1

-40

NF2 (apoyo)

2

2

3

0

0

1

0

50

0

4/3

5/3

0 -2/3

1

0

10 NF3

8 8/3 16/3 -8 -7 -6 0

0 0

8/3 0

0 0

0 1

-13/3 -2/3 0

8/3

0

1

160 0 160 NF4

Con las nuevas filas, construimos la tabla Simplex 2, teniendo en cuenta que en la base aparecerá X1 que desplaza a S2 Tabla Simplex 2

BASE

𝑿𝟏

𝑿𝟐

X3

S1 S2

S3

Z

S1

0

4/3

-1/3

1 -2/3 0

0

30

225

X1

1

1/3

2/3

0 1/3 0

0

20

60

0

(4/3) 5/3

0 -2/3 1

0

10

7.5 →

0

-13/3 -2/3 ↑

0 8/3

1

160

0

←S3

Z

0

SOLUC.

COC.

Entra X2 y sale S3 de la base. Pivote = (4/3) Formulamos las operaciones 3/4F3 = NF3 (fila de apoyo) -4/3NF3 + F1 = NF1 -1/3NF3 + F2 = NF2 13/3NF3 + F4 = NF4

Realizamos el proceso analítico de las operaciones algebraicas: 0

1 5/4

0

-1/2

3/4

0

15/2

0 0

-10 30

0 -4/3 -5/3 0 4/3 -1/3

0 1

2/3 -2/3

-1 0

0

1

0

-1

0

-2

0

NF3 (apoyo)

20 NF1

0 -1/3 -5/12 0 1 1/3 2/3 0

1/6 1/3

-1/4 0

0 0

-5/2 20

1

1/2

-1/4

0

35/2 NF2

0

1/4

0

0 13/3 65/12 0 -13/3 -2/3

0 0

-13/6 8/3

13/4 0 0 1

65/2 16 0

0

0

1/2

13/4

385/2 NF4

0

57/12

1

Con las nuevas filas, construimos la nueva tabla Simplex que corresponde a una tabla óptima porque los indicadores son no negativos y los elementos de la solución son todos positivos. Tabla Simplex óptima

BASE

𝑿𝟏

𝑿𝟐

X3

S1 S2

S1

0

0

-2

1

0

X1

1

0

1/4

0

1/2

X2

0

1

5/4

0 -1/2

Z

0

0 57/12

0 1/2

S3

Z

SOLUC.

-1

0

20

-1/4

0

35/2

3/4

0

15/2

13/4

1

385/2

SOLUCIÓN ÓPTIMA: X1 = 35/2, X2 = 15/2, X3 =0 (no básica) y Z = 385/2 CONCLUSIÓN Se deben fabricar semanalmente 35/2 unidades del articulo capulina, 15/2 del juguete carmelina y no fabricar el juguete Chicholina para obtener la máxima utilidad, equivalente a $385/2 por semana. También se debe hacer un severo llamado de atención a los Ingenieros asesores.

SOLUCIONES ÓPTIMAS MULTIPLES EN EL METODO SIMPLEX Cuando existe un indicador cero en una variable que no está en la base en una tabla óptima, se dice que la solución es óptima múltiple y se debe realizar otra tabla haciendo entrar la variable que no está en la base y tiene el indicador cero. En un problema con soluciones óptimas múltiples se obtiene el mismo valor de Z para diferentes valores de las variables estructurales. Conociendo las dos tablas óptimas podemos obtener los valores de las variables estructurales 𝑿𝟏 , X2, X3…Xn mediante las ecuaciones siguientes: Para X1: X1 = a1 (1- t) + b1t →a1 es el primer valor obtenido de X1 en la primera tabla óptima y b1 es el segundo valor obtenido de X1 en la segunda tabla óptima. Para X2: X2 = a2 (1- t) + b2t → a2 es el primer valor obtenido de X2 en la primera tabla óptima y b2 es el segundo valor obtenido de X2 en la segunda tabla óptima. Para X3: X3 = a3 (1-t) + b3t → a3 es el primer valor obtenido de X3 en la primera tabla óptima y b3 es el segundo valor obtenido de X3 en la segunda tabla óptima.

Para Xn: Xn = an (1-t) + tbn → an es el primer valor de Xn en la primera tabla óptima y bn es el segundo valor obtenido de Xn en la segunda tabla óptima. 0≤ t ≤1 → significa que si le damos valores a t en el intervalo [0,1] obtenemos nuevas soluciones de Xi, pero el valor de Z sigue siendo el mismo. Ejemplo de ilustración sobre solución ´0ptima múltiples en el simplex: 1. Maximizar Z= -X1 + 4X2 + 6X3 𝑋1 + 2𝑋2 + 3𝑋3 ≤ 6

Sujeta a:

−2𝑋1 −5𝑋2 + 𝑋3 ≤ 10 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

SOLUCION De (1):

𝑋1 + 2𝑋2 + 3𝑋3 + S1 = 6

De (2):

−2𝑋1 −5𝑋2 + 𝑋3 + S2 = 10

De la F.O: X1 - 4X2 - 6X3 + Z = 0 Tabla Simplex Inicial Base ←S1

X1 1

X2 2

X3

S1

S2 1

0 0

1 0

(3)

Z 0

Solución 6

cocientes 6/3=2→

10

10/1=10

0 S2 Z

-2 1

-5 -4

1 -6

0 1

0

↑ (entra X3) (3) = Pivote Formulamos las operaciones de transformación de la matriz:

1/3F1 = NF2 (fila de apoyo) - 1NF1 + F2 = NF2 6NF1 + F3 = NF3

Tabla Simplex Óptima 1 Base ←X3

X1 1/3

X2 (2/3)

X3

S2

-7/3

-17/3

0

1

S1 1/3

S2 0

Z 0

Solución 2

cocientes 3 → sale

- 1/3

1

0

8

-24/17

Z

3

0

0

2

0

1

0

12

↑ (entra X2) (2/3) = Pivote Se observa que todos los indicadores son no negativos, pero existe un cero en X2 que no está en la base (ya que todas las variables básicas deben tener indicador cero), luego la primera solución óptima corresponde a: X1 = 0 (no básica) → primer valor de X1 X2 = 0 (no básica) → primer valor de X2 X3 = 2(básica) → primer valor de X3 Hallamos la segunda tabla óptima haciendo entrar a X2 (que no está en la base, pero tiene indicador cero) y sale de la base X3 (que tiene menor cociente y es la única opcionada porque el cociente de S2 es negativo y por ende se descarta). Formulación de las operaciones: 3/2𝐹1= 𝑁𝐹1 (fila de apoyo), 17/3𝑁𝐹1 + F2 = 𝑁𝐹2

y

𝐹3 = 𝑁𝐹3 (queda igual)

Tabla Simplex Óptima 2 Base

X1

X2

X3

S1

S2

Solución

0

3

5/2

1

25

0

1

12

Z 1/2

X2

1/2

S2

1

3/2

0

1/2

17/2

0

0 Z

3

0

0

2

Segunda solución óptima: X1 = 0 (no básica) → segundo valor de X1 X2 = 3

→ segundo valor de X2

X3 = 0 (no básica) → segundo valor de X3 Z=12 Planteamos las ecuaciones de solución óptima múltiple para las variables estructurales 𝑋1 , 𝑋2 , 𝑋3 Para X1: X1 = (0) (1- t) + (0) t →”0” es el primer valor obtenido de X1 en la primera tabla óptima y “0” es el segundo valor obtenido de X1 en la segunda tabla óptima. Luego, X1 = 0 + 0 =0 → X1 =0 Para X2: X1 = (0) (1- t) + (3) t →”0” es el primer valor obtenido de X2 en la primera tabla óptima y “3” es el segundo valor obtenido de X2 en la segunda tabla óptima.

Luego, X2 = 0 + 3t =3t → X2 =3t Para X3: X3 = (2) (1- t) + (0) t →”2” es el primer valor obtenido de X3 en la primera tabla óptima y “0” es el segundo valor obtenido de X3 en la segunda tabla óptima. Luego, X3 = 2(1-t) + 0 → X3 =2(1-t)

CONCLUSION Z=12 cuando: X1 =0; X2 =3t; X3 =2(1- t) en el intervalo 0≤ t ≤1 → significa que si le damos valores a t en el intervalo [0,1] obtenemos nuevas soluciones de Xi, pero el valor de Z sigue siendo el mismo, es decir, Z=12, así: Para t=0 → X1 =0 → X2 =3(0) = 0 → X3 =2(1-0) = 2 → fue la que se obtuvo en la primera tabla óptima.

Z= -(0) + 4(0) + 6(2) = 12 (esta solución

Para t=1/4 → X1 =0 → X2 =3(1/4) = 3/4 → X3 =2(1-1/4) = 3/2 → Z= -(0) + 4(3/4) + 6(3/2) = 12 (esta es otra solución óptima que se obtiene sin hacer otra Iteración mas) Para t=1/2 → X1 =0 → X2 =3(1/2) = 3/2 → X3 =2(1-1/2) = 1 → Z= -(0) + 4(3/2) + 6(1) = 12 (esta es otra solución óptima que se obtiene sin hacer ninguna Iteración) Para t=3/4 → X1 =0 → X2 =3(3/4) = 9/4 → X3 =2(1-3/4) =1/2 → Z= -(0) + 4(9/4) + 6(1/2) = 12 (esta es otra solución óptima que se obtiene sin hacer ninguna Iteración) Para t=1 → X1 =0 → X2 =3(1) = 3 → X3 =2(1-1) = 0 → fue la que se obtuvo en la segunda tabla óptima).

Z= -(0) + 4(3) + 6(0) = 12 (esta solución

SOLUCIÓN DEGENERADA EN EL METODO SIMPLEX Esta solución se presenta cuando hay un cociente cero en la solución óptima de la tabla Simplex. En problemas con degeneración es posible llegar al mismo valor de Z en varias etapas del proceso Simplex. Ejemplo de ilustración Max. Z=3X1 + 4X2 + 3/2X3 Sujeta a:

-X1 - 2X2 ≥ - 10 2 𝑋1 + 2𝑋2 + 𝑋3 ≤ 10 𝑋1 , 𝑋2 , 𝑋3 ≥ 0 SOLUCION

De (1) → (∗ −𝟏) → 𝑋1 + 2𝑋2 ≤ 10 →

X1 + 2X2 + 0X3 + S1 =10

De (2): 2 𝑋1 + 2𝑋2 + 𝑋3 ≤ 10

2𝑋1 +2𝑋2 + 𝑋3 + S2 = 10

→

→

De la F.O: Z=3X1 + 4X2 + 3/2X3

-3X1 - 4X2 – 3/2X3 + Z = 0

Tabla Simplex Inicial Base ←S1

X1 1

S2 Z

2 -3

X2 (2)

X3 0

S1 1

S2 0

Z 0

Solución 10

cocientes 10/2=5 →

1 0 -3/2 0 ↑ (entra X2)

1 0

0 1

10

10/2=5

-2 -4

0

(2) = Pivote, el empate entre el menor cociente, se rompe arbitrariamente, es decir, puede elegir como variable saliente a S1 o a S2, en este caso elegimos a S1 como variable saliente. Formulación de las operaciones: 1/2𝐹1= 𝑁𝐹1 (fila de apoyo), → 𝑁𝐹1 = Nueva fila 1 −2𝑁𝐹1 + 𝐹2 = 𝑁𝐹2 ; 4𝑁𝐹1 + 𝐹3 = 𝑁𝐹3 ; Una vez realizadas las operaciones algebraicas, obtenemos las nuevas Filas con las cuales construimos la nueva matriz (tabla Simplex 2), teniendo en cuenta que aparecerá 𝑿𝟐 en vez de S1 en la columna de la base, así:

½ 1

0

½

0

0

NF1 (fila de apoyo)

5

Tabla Simplex 2 Base

X1

X2

½

X2 1

X3 0

←S2

1 -1

0 0

(1) -3/2

Z

S1

S2 0

Z 0

Solución 5

cocientes 5/0=5 =∞ (se descarta)

-1 1 2 0 ↑ (entra X3)

0 1

0

0/1= 0 → sale S2

½

20

Pivote = (1), El cociente cero me dice que vamos a obtener solución factible básica pero degenerada. Factible porque son positivos (incluido cero) los elementos de la columna solución. Formulación de las operaciones: 𝐹2= 𝑁𝐹2 (fila de apoyo), → 𝑁𝐹2 = Nueva fila 2 𝐹1 = 𝑁𝐹1 ; 3/2𝑁𝐹2 + 𝐹3 = 𝑁𝐹3 ;

1

0

1

-1

1

0

0

NF2 (fila de apoyo)

Una vez realizadas las operaciones algebraicas, obtenemos las nuevas Filas con las cuales construimos la nueva matriz (tabla Simplex 3), teniendo en cuenta que X3 desplazará a S2 en la base de la nueva tabla. Tabla Simplex 3 (“óptima”)

Base

X1

X2

X3

S1

S2

1/2

1

0

1/2

0

1

0

1

1/2

0

Solución

Z X2

5

0 0

X3 -1

1

1/2

3/2

0 Z

0

20

1

La tabla Simplex 3 es una tabla básica degenerada que la consideramos óptima entre comillas, porque los indicadores son no negativos (es decir, son positivos incluido el cero) pero existe un elemento cero en la columna solución que no va a desaparecer por mucho que intentemos iterar una y otra vez y el valor de Z seguirá siendo Z= 20 CONCLUSION Z=20, es máxima cuando: X1 =0 (no básica); X2 =5; X3 =0 (básica) → significa que la solución es degenerada porque existe un cero en el elemento solución de una variable básica. Obsérvese que el valor de Z=20 lo obtuvimos tanto en la tabla 2 como en la tabla 3.

EMPATE ENTRE EL MENOR COCIENTE QUE ELIGE A LA VARIABLE QUE SALE DE LA BASE EN EL METODO SIMPLEX Cuando hay un empate entre el menor cociente, puede elegirse como variable saliente a una de las dos, y el resultado no se altera. El método Simplex normal no permite variables de Holgura negativa en la conversión de ecuación en cada restricción (ya que el elemento de intersección de la variable que está en la base con la misma variable que está en el renglón superior, es 1 y no -1), porque inicialmente los coeficientes de S(i) forman la matriz unitaria. Si la restricción lleva implícita el signo ≥ debe multiplicarse por (- 1) para convertir la desigualdad en ≤ y de esa forma convertimos en igualdad sumando la variable de holgura S1 o S2, el subíndice depende de la posición que ocupe la restricción, si es la primera restricción usamos S 1, si es la segunda restricción usamos S2, si es la tercera restricción 3 usamos S3, etcétera. Ejemplo de Ilustración: Max. Z=X1 - 12X2 + 4X3 Sujeta a:

4X1 + 3X2 - 𝑋3 ≤1 𝑋1 + 𝑋2 - 𝑋3 ≥ −2 −𝑋1 + 𝑋2 + 𝑋3 ≥ −1 𝑋1 , 𝑋2 , 𝑋3 ≥ 0 SOLUCION

De (1) ∶ 4X1 + 3X2 − 𝑋3 ≤ 1

→ 4X1 + 3X2 - 𝑋3 + S1 = 1

De (2): → (∗ −𝟏) → −𝑋1 − 𝑋2 + 𝑋3 ≤ 2 → −𝑋1 − 𝑋2 + 𝑋3 + S2 = 2 De (3): → (∗ −𝟏) → 𝑋1 - 𝑋2 - 𝑋3 ≤ 1 → 𝑋1 - 𝑋2 – X3 + S3 = 1 De la F.O: →

-X1 + 12X2 – 4X3 + Z = 0

Construimos la tabla Simplex Inicial para realizar las Iteraciones según las formulaciones de las operaciones:

Tabla Simplex Inicial Base S1 S2 S3 Z

X1

X2

X3

4 -1 1 -1

3 -1 -1 (1) -1 -1 12 -4

S1 1 0 0 0

S2

0 1 0 0 ↑ (entra X3)

S3 0 0 1 0

Z

Solución

cocientes

0 0 0 1

1 2 1 0

1/-1=-1 2/1=2→ 1/-1=-1

(1) = Pivote, el Indicador más negativo es -4, por consiguiente, entra a la base X3 y los cocientes negativos se descartan, por lo tanto, sale de la base S2 Formulación de las operaciones: 𝐹2= 𝑁𝐹2 (fila de apoyo), → 𝑁𝐹2 = Nueva fila 2 1𝑁𝐹2 + 𝐹1 = 𝐹1 ; 1NF2 + 𝐹3 = 𝑁𝐹3 ; 4NF2 + F4 = NF4 Una vez realizadas las operaciones algebraicas, y tres Iteraciones más, obtenemos la solución óptima. SOLUCION ÓPTIMA: Z=13, se maximiza cuando X1 =1; X2 =0 y X3 =3

SOLUCION NO ACOTADA EN EL METODO SIMPLEX Se dice que un problema de Programación Lineal tiene una solución no acotada, cuando en una tabla Simplex no existen cocientes posibles (es decir, el cociente es negativo, indeterminado y por consiguiente se descartan). Ejercicio de Ilustración Max. Z = X1 + 4X2 - X3 Sujeta a: -5X1 + 6X2 - 2X3 ≤ 30 -X1 + 3X2 + 6X3 ≤1 2

X1, X2, X3 ≥ 0 SOLUCIÖN De (1) -5X1 + 6X2 - 2X3 ≤ 30 → -5X1 + 6X2 - 2𝑋3 + S1 = 30 De (2): -X1 + 3X2 + 6X3 ≤1 2 → −𝑋1 + 3𝑋2 + 6𝑋3 + S2 = 12 De la F.O: →

-X1 - 4X2 + X3 + Z = 0

Tabla Simplex Inicial Base

X1

X2

X3

S1

S2

Z

Solución

S1 S2

-5 -1

6 (3)

-2 6

1 0

0 1

0 0

30 12

Z

-1

-4

1

0

0

1

0

Cocientes 30/6=5 12/3=4→(menor)

↑ (entra X2) (3) = Pivote, el Indicador más negativo es -4, por consiguiente, entra a la base X2 y sale de la base S2 (por tener menor cociente positivo). Formulación de las operaciones: 1/3𝐹2= 𝑁𝐹2 (fila de apoyo), → 𝑁𝐹2 = Nueva fila 2 −6𝑁𝐹2 + 𝐹1 = 𝐹1 ; 4NF2 + 𝐹3 = 𝑁𝐹3 Con esas operaciones algebraicas convertimos el pivote en 1 y convertimos en cero los demás elementos en esa columna (por debajo y por encima del pivote)

-1/3

1

2

2 -6 -5 6

-12 -2

-3 0

-14

-4/3 4 -5 -4 - 7/3

0

1/3 0

0 -2 1 0 1

-2

0 0

4

-24 30

0

6 NF1

8 1

0 0

4/3 0

0 1

9

0

4/3

1

0

→ 𝑁𝐹2 = Nueva fila 2 (fila de apoyo)

16 0 16 NF1

Construimos la nueva tabla con las nuevas operaciones (teniendo en cuenta que aparecerá en la base X2) Tabla Simplex 2 Base S1 X2

X1 -3 -1/3

X2

X3

S1

S2

Z

Solución

0 1

-14 2

1 0

-2 1/3

0 0

6 4

Cocientes 6/-3=- 2 (se descarta) 4/-1/3= - 12(se descarta)

Z

-7/3

0

9

0

4/3

1

16

↑ (entra X1) No existe variable saliente puesto que no existe un posible cociente, esto me indica que el problema tiene una solución NO ACOTADA. Concluimos que el problema no tiene solución óptima. EMPATE EN LOS INDICADORES PARA ELEGIR LA VARIABLE QUE ENTRA A LA BASE Cuando se presenta un empate en los indicadores, deben analizarse los dos casos, es decir, elegir arbitrariamente uno de los dos indicadores y continuar el proceso hasta llegar a la tabla óptima. Si no se llega a la solución óptima por ese lado, entonces se elige el otro indicador y se inicia un nuevo proceso hasta llegar a la tabla óptima.

EJERCICIO DE ILUSTRACIÖN DE EMPATE EN LOS INDICADORES 1. Max. Z = 3X1 + 2X2 + 3X3 Sujeta a: 2X1 + X2 + X3 ≤ 2 3X1 + 4X2 + 2X3 ≤ 8 X1, X2, X3 ≥ 0 SOLUCION De (1): 2X1 + X2 + X3 ≤ 2 → 2X1 + X2 + X3 + S1 = 2 De (2): 3X1 + 4X2 + 2X3 ≤ 8 → 3X1 + 4X2 + 2X3 + S2 = 8 De la F.O: →

- 3X1 - 2X2 – 3X3 + Z = 0

Construimos la tabla Simplex Inicial para realizar las Iteraciones según las formulaciones de las operaciones:

Tabla Simplex Inicial Base

X1

X2

X3

S1

S2

S1

2

1

1

1

0

S2

3

4

2

0

1

Z

-3

-2

-3

0

0

Solución

cocientes

2 8

2/2=1 8/3=2.6

0

↑ (entra X1 o X3) Obsérvese que se presentó un empate entre los indicadores de X1 y X3, analicemos los dos casos: Caso 1: Entra a la base la variable X1 y sale S1 → pivote = (2) Tabla Simplex Inicial

Base

X1

X2

X3

S1

S2

Solución

cocientes

S1

(2)

1

1

1

0

2 8

2/2=1→ 8/3=2.6

S2

3

4

2

0

1

Z

-3

-2

-3

0

0

0

↑ (entra X1) Formulamos las operaciones: 1/2𝐹1= 𝑁𝐹1 (fila de apoyo), → 𝑁𝐹1 = Nueva fila 1 −3𝑁𝐹1 + 𝐹2 = 𝐹2 ; 3NF1 + 𝐹3 = 𝑁𝐹3 Una vez realizadas las operaciones algebraicas por renglones, construimos la nueva tabla Simplex 2, así:

Tabla Simplex 2 Base

X1

X2

X3

S1

S2

←X1

1

1/2

1/2

1/2

S2

0

5/2

1/2

0

-1/2

-3/2

Z

Solución

cocientes

0

1

2/0.5=2→

-3/2

1

5

5/0.5=10

3/2

0

3

↑ (entra X3) Se aprecia que sale X1, variable estructural que había entrado inicialmente, esto significa que por ese lado el problema no tiene solución óptima o puede llegarse a la solución óptima con más iteraciones de las necesarias, por consiguiente, analizamos el caso 2: Caso 2: Entra a la base la variable X3 y sale S1 → pivote = (1) Tabla Simplex Inicial Base

X1

X2

X3

S1

S2

Solución

cocientes

←S1

2

1

(1)

1

0

2

2/1=2→

S2

3

4

2

8/2=4

-3

-2

-3

Z

0

1

8

0

0

0

↑ (entra X3) Formulamos las operaciones: 𝐹1 = 𝑁𝐹1 (fila de apoyo), → 𝑁𝐹1 = Nueva fila 1 −2𝑁𝐹1 + 𝐹2 = 𝐹2 ; 3NF1 + 𝐹3 = 𝑁𝐹3

Una vez realizadas las operaciones algebraicas por renglones, construimos la nueva tabla Simplex 2, que corresponde a la tabla óptima porque los indicadores son no negativos (incluido el cero) y los elementos de la columna solución son positivos, así: Tabla Simplex óptima Base X3 S2 Z

X1

X2

X3

2

1

1

-1

2

3

1

0 0

S1

S2

Solución

1

0

2

-2

1

4

3

0

6

SOLU CIÖN ÖPTIMA: Z=6 cuando X1 =0 (no básica), X2 =0 (no básica) y X3 =2

PROBLEMAS PROPUESTOS PARA RESOLVER POR EL METODO SIMPLEX 1. Una empresa manufacturera desea maximizar sus ingresos diarios, para ello fabrica dos tipos de productos P1 y P2 que requieren de tres procesos productivos para su elaboración en las siguientes cantidades (horas/unidad). PROCESO Proceso X Proceso Y Proceso Z

TIPOS DE PRODUCTO P1 P2 1 hr/und. 1 hr/und 3 hr/und. 2 hr/und 2 hr/und. 3 hr/und

La ganancia por unidad del producto P1 es 50 dólares y por unidad del producto P2 es 56 dólares. Si se disponen de 80, 220 y 210 horas diarias para los procesos x, y, z respectivamente, ¿Cuántas unidades de cada producto deberá producir diariamente la compañía para maximizar sus ingresos? Respuesta: se deben fabricar por día 30 unidades del producto P1 y 50 unidades del producto P2 para que sus ingresos diarios sean máximos, equivalentes a 4300 dólares por día.

2. Un Ingeniero monta una microempresa en la que fábrica dos productos, uno a base de Melaza y otro a base de Sábila. Cada producto requiere en su fabricación el uso de cinco aditivos; A1, A2, A3, A4 y A5. Un producto de Melaza requiere de 6 gramos de A1, 1 gramo de A2 y 1 gramo de A5; no requiere de los aditivos A3 ni A4. El producto de Sábila requiere de 6 gramos de A1, 1 gramo de A3, 1 gramo de A4; no requiere de los aditivos A2 ni A5. Suponiendo que la cantidad disponible en gramos por día debe ser a lo mucho 360 para A1, a lo mucho 60 gramos para A2, a lo mucho 40 gramos para A3, a lo mucho 25 gramos para A5 y por lo menos 20 gramos por día para el aditivo A4.

La ganancia que se obtiene con el producto a base de melaza es de $300 por unidad y de $200 por unidad del producto a base de sábila. Si la microempresa vende todos los productos que fabrica: a). Formular el problema como un modelo matemático de programación lineal. b). ¿Cuántos productos a base de melaza y cuantos a base de sábila se deben fabricar por día para Maximizar la utilidad? Respuesta: Solamente se deben producir 20 unidades por día del producto a base de Sábila y no se debe producir el producto a base de melaza para que la utilidad sea máxima, equivalente a $4000 por día.

3. Una fábrica de juguetes está preparando un programa de producción para tres nuevos artículos llamados “Capulina”, “Carmelina” y “Chicholina”. Los ingenieros asesores le advierten a la fábrica que ese programa que está preparando no es factible; sin embargo, la fábrica plantea lo siguiente: Cada juguete capulina requiere de 2 horas en la maquina A, 3 horas en la maquina B y 2 horas para terminado, y la utilidad por unidad de capulina es de 8 dólares tal como lo muestra la tabla siguiente:

JUGUETE

MAQUINAS(hr/und) TERMINADO(hr/und) UTILIDAD($/und) A B Capulina 2 3 2 8 Carmelina 3 2 1 7 Chicholina 2 1 2 6 Las horas de trabajos disponibles de los empleados por semana son: para la maquina A, 70 horas por semana, 60 horas para la maquina B y para terminado, 50 horas. a) Formular el problema como un modelo matemático de programación lineal que permita maximizar las ganancias de cada juguete. b). Verificar la veracidad de los ingenieros asesores determinando el número de unidades que se deben fabricar de cada juguete por semana para maximizar la utilidad. Respuesta: Se deben fabricar semanalmente 10 unidades de cada juguete para que la utilidad sea máxima, equivalente a 210 dólares por semana y se le debe hacer un severo llamado de atención a los ingenieros asesores. 4. Un agricultor produce maíz y trigo con tres factores de producción: Tierra, Mano de obra y Yuntas de bueyes. Posee 20 hectáreas de tierra, 30 Yuntas de bueyes y 30 obreros. Por su experiencia el agricultor ha descubierto que para producir 1 tonelada de maíz y 1 tonelada de trigo necesita utilizar lo siguiente: INSUMO TIERRA MANO DE OBRA BUEYES

PRODUCTO MAIZ 0.2 hect/ton. 1 obrero/ton. 0.8 yuntas/ton.

TRIGO 0.3 hect/ton. 20 obrero/ton. 1 yunta/ton.

Sabe además que el precio de una tonelada de maíz es de $200 y el de una tonelada de trigo es de $ 150. a) Formular el problema como un modelo matemático de programación lineal

b) Determinar la cantidad de maíz y trigo que deben producirse para que el ingreso sea máximo. Respuesta: Se deben producir 30 toneladas de maíz y no producir trigo para que el ingreso sea máximo sea de $6000. 5. Un agricultor produce Algodón, Sorgo y Millo con tres factores de producción: Tierra, Mano de obra y Yunta de bueyes. Posee 15 hectáreas de tierra, 20 yuntas de bueyes y 25 obreros. Por su experiencia el agricultor ha descubierto que, para producir 1 tonelada de algodón, 1 tonelada de sorgo y 1 tonelada de millo necesita utilizar lo siguiente:

INSUMO

TIERRA MANO DE OBRA BUEYES

PRODUCTO ALGODON 0.8 hect/ton. 3 obrero/ton. 0.7 yuntas/ton.

PRODUCTO

SORGO 0.4 hect/ton. 4 obrero/ton. 1.2 yuntas/ton.

MILLO 0.3 hect/ton. 5 obrero/ton. 1.3 yuntas/ton.

Sabe además que el precio de una tonelada de algodón es de $150, el de una tonelada de sorgo es $130 y de una tonelada de millo es de $140. Formular el problema como un modelo matemático de programación lineal y determinar la cantidad de algodón, sorgo y millo que deben producirse para que el ingreso sea máximo. Respuesta: Se deben producir 25/3 toneladas de algodón y no producir sorgo ni millo para que el ingreso sea máximo sea de $1250. 6. Una Empresa fabrica dos tipos de sillas: sillas para oficina y sillas escolares. Para su fabricación requiere de tres procesos productivos; P1, P2 y P3 en las siguientes cantidades (horas por unidad): PROCESO P1 P2 P3

SILLAS OFICINA ESCOLARES 1 1

3 2

2 3

Los Ingresos por ventas son de 72 dólares para la silla de oficina y 86 dólares para la silla escolar. El costo de producción para la silla de oficina es de 22 dólares y para la escolar es de 30 dólares. Se dispone de 80 horas semanales para el proceso 1; de 220 horas semanales para el proceso 2 y de 210 horas semanales para el proceso 3.

a) Formular el problema como un modelo matemático de Programación Lineal b) ¿Cuántas unidades por semana de cada producto deberá producir la compañía para maximizar la utilidad? Respuesta: Se deben fabricar 30 sillas para oficina y 50 sillas escolares por semana para que la utilidad sea máxima, equivalente a 4300 dólares por semana. 7. Una fábrica de juguetes está preparando un programa de producción para tres nuevos artículos llamados “Capulina”, “Carmelina” y “Chicholina”. Los ingenieros asesores le advierten a la fábrica que ese programa que está preparando no es factible; sin embargo, la fábrica plantea lo siguiente: Cada juguete capulina requiere de 3 horas en la maquina A, 2 horas en la maquina B y 1 horas para terminado, y la utilidad por unidad de capulina es de 8 dólares tal como lo muestra la tabla siguiente:

JUGUETE

MAQUINAS(hr/und) TERMINADO(hr/und) UTILIDAD($/und) A B Capulina 3 2 1 8 Carmelina 2 1 2 7 Chicholina 1 2 3 6 Las horas de trabajos disponibles de los empleados por semana son: para la maquina A, 70 horas por semana, 60 horas para la maquina B y para terminado, 50 horas. a) Formular el problema como un modelo matemático de programación lineal que permita maximizar las ganancias de cada juguete. b). Verificar la veracidad de los ingenieros asesores determinando el número de unidades que se deben fabricar de cada juguete por semana para maximizar la utilidad. Respuesta: Se deben fabricar semanalmente 20 unidades del juguete Capulina, 10 unidades del juguete Chicholina y no debe fabricarse el juguete Carmelina para que la utilidad sea máxima, equivalente a 220 dólares por semana y se le debe hacer un severo llamado de atención a los ingenieros asesores. EJERCICIOS RESUELTOS DE MAXIMIZACIÓN EN EL METODO SIMPLEX 1. Maximizar Z= 2X1 + X2 S.A:

-2X1 - 5X2 ≥ -17 3X1 + 2X2 ≤ 10 X1, X2 ≥ 0 SOLUCIÖN:

El primer paso es MULTIPLICAR la primera restricción por -1 para convertir en positivo el elemento -17, la forma estándar del método Simplex normal dice que todas las restricciones deben ser del tipo ≤ y todos sus términos independientes deben ser positivos (esto con el fin que inicialmente todas las variables de holguras aparezcan en la base y conformen una matriz unitaria en el cuerpo de la tabla con las columnas encabezadas por ellas, esa es una propiedad del Simplex.) De (1): -2X1 -5X2 ≥ -17→multiplicamos por -1→ 2X1 + 5X2 ≤ 17

De (2): 3X1 + 2X2 ≤ 10→queda igual→3X1 + 2X2 ≤ 10 El modelo matemático queda de la siguiente forma: 2. Maximizar Z= 2X1 + X2 2X1 + 5X2 ≤ 17 3X1 + 2X2 ≤ 10 X1, X2 ≥ 0

S.A:

Ese es el modelo estándar del SIMPLEX, ahora agregamos las variables de holguras para convertir en igualdad las dos restricciones, así: De (1): 2X1 + 5X2 + S1= 17 De (2): 3X1 + 2X2 + S2 = 10 De la Función Objetivo: - 2X1 – X2 + Z=0 Construimos la tabla Simplex Inicial Tabla Simplex Inicial Base

X1

X2

S1

S2

Z

S1

2 (3)

5 2

1 0

0 1

0 0

17 10

-2

-1

0

0

1

0

←S2 Z

Solución

cocientes 17/2=8.5 10/3=3.3→

↑ (entra X1) (3) = Pivote, el Indicador más negativo es -2, por consiguiente, entra a la base X1 y el menor cociente positivo es 3.3, por lo tanto, sale de la base S2 Formulación de las operaciones: 1/3𝐹2= 𝑁𝐹2 (fila de apoyo), → 𝑁𝐹2 = Nueva fila 2 −2𝑁𝐹2 + 𝐹1 = 𝐹1 ; 2NF2 + 𝐹3 = 𝑁𝐹3 ; Con el desarrollo de esas operaciones logramos convertir en 1 el pivote y en cero los demás elementos por debajo y por encima del pivote en esa columna (matricialmente hablando, esta es la aplicación del método de Gauss- Jordan)

1

2/3

-2 2 0

0

1/3

0

-4/3 0 -2/3 5 1 0 11/3 1 -2/3

10/3

0 0 0

NF2 (fila de apoyo)

- 20/3 17 31/3

NF1

2 -2 0

4/3 -1 1/3

0 0 0

2/3 0 2/3

0 0 1

20/3 0 20/3

→ NF3

Construimos la nueva tabla Simplex con las nuevas operaciones por renglones y observamos que es una tabla óptima porque todos los indicadores son no negativos y todos los elementos de la columna solución son positivos, así:

Tabla Simplex Óptima Base

X1

X2

S1

S1 X1

0 1

11/3 2/3

1 0

Z

0

1/3

0

S2

Z

Solución

-2/3 1/3

0 0

31/3 10/3

2/3

1

20/3

SOLUCION ÓPTIMA: Z=20/3, se maximiza cuando X1 =10/3; X2 =0 (no básica)

EJERCICIO PROPUESTOS DE MAXIMIZACION SOBRE EL METODO SIMPLEX

1. Max. Z = X1 +2X2 Sujeta a: 2X1 + X2 ≤ 8

Solución: Z = 8 cuando X1 = 0, X2 = 4

2X1 + 3X2 + ≤ 12 X1, X2 ≥ 0

2. Max. Z = -X1 + 3X2

Solución: Z = 14 cuando X1 = 1; X2 = 5

Sujeta a: X1 + X2 ≤ 6 -X1 + X2 ≤ 4 X1, X2, ≥ 0

3. Max. Z = X1 +X2

Solución: Z = 16/3 cuando X1 = 2/3; X2 = 14/3

Sujeta a: X1 - X2 ≤ 4 - X1 + X2 ≤ 4 8X1 + 5X2 ≤ 40 2X1 + X2 ≤ 6 X1, X2, ≥ 0

4. Max. Z = X1 - 12X2 + 4X3

Solución: Z = 13 cuando X1 = 1; X2 =0, X3 = 3

Sujeta a: 4X1 + 3X2 - X3 ≤ 1 X1 + X2 - X3 ≥- 2 -X1 + X2 + X3 ≥ -1 X1, X2, X3 ≥ 0 5. Max. Z=60X1 + 90X3

Solución: Z = 600 cuando X1 = 4; X2 =1, X3 = 4, X4 =0

Sujeta a: X1 - 2X2 ≤ 2 X1 + X2 ≤ 5 X3 + X4 ≤ 4 X3 - 2X4, ≤ 7 X1, X2, X3, X4 ≥ 0

6. Max. Z = 2X1 +X2 - X3

Solución : Z = 2 cuando X1 = 1; X2 =0, X3 = 0

Sujeta a: X1 + X2 ≤ 1 X1 - 2X2 - X3 ≥- 2 X1, X2, X3 ≥ 0 7. Max. Z = -5X2 Sujeta a: X1 - X2 ≤ 1 - 0.5X1 - 5X2 ≤ 10 X1, X2, ≥ 0

Solución: Z = 0 cuando X1 = X2 =0 (no básicas) S1 =1, S2 =20

8. Min. Z = X1 - 10X2 Sujeta a: X1 – 0.5 X2 ≥ 0

Solución: No existen cocientes posibles por tanto el sistema no tiene solución óptima.

X1 - 5X2 ≥ -5 X1, X2, ≥ 0

9. Max. Z = 3X1 + X2 Sujeta a: X1 ≤ 4 X2 ≤ 4 X1 +X2 ≤ 8 X1, X2, ≥ 0

Solución: Z= 16 cuando X1 =4; X2 = 4, S3 = 0