Manual de Ejercicios Programación Lineal PDF

Preview

Summary

Teoría y ejercicios de programación lineal...

Description

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

INVESTIGACIÓN DE OPERACIONES

SISTEMA DE EJERCICIOS DE PROGRAMACIÓN LINEAL: MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN DE RESULTADOS.

JOSÉ E. VÁZQUEZ ARÉVALO PROCESOS TECNOLÓGICOS E INDUSTRIALES ITESO

JEVA / PTI

1

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

PROBLEMAS TIPO "MEZCLA DE PRODUCTOS". PROBLEMAS DE NIVEL BÁSICO. 1. Dijes. Un joyero puede disponer semanalmente de 800 gramos de oro, 2.4 kilogramos de plata y 14 kilogramos de cobre. Actualmente fabrica dos dijes que tienen gran demanda. Se llevan 10 gramos de oro en cualquier dije que fabrique, pero el dije 1 lleva también 40 gramos de plata y 150 de cobre mientras que el dije 2 requiere de 250 gramos de cobre y 20 de plata. Se tiene una utilidad total de $90 y $70 para el dije 1 y 2 respectivamente. a. Haga una tabla con los datos del problema. b. Desarrolle un modelo que ayude a hacer un programa de producción que maximice la utilidad total. Tabla de Datos. Dije 1 2 Disponibilidad (gramos/semana)

Ma teri ales (gramos/dije) Oro Plata Cobre 10 40 150 10 20 250 800

2,400

Utilidad ($/dije) 90 70

14,000

Modelación. Variables de Decisión. Xi = Dije tipo "i" a fabricarse semanalmente. (d/s) Función Objetivo. Máx. Z = 90X1 + 70X2 $/s ($/d) (d/s) = $/s Restricciones. 1. Materiales. Oro Plata Cobre

10X1 + 10X2 ≤ 800 40X1 + 20X2 ≤ 2,400 150X1 + 250X2 ≤ 14,000 (g/d)( d/s) = g/s g/s 2. No negatividad Xi ≥ 0

Análisis Dimensional: Probado. Solución Optima. X1 = 45.77143 X2 = 28.571|4 0ro (H1) = 57.1429 Máx. Z = 6,114.286 Interpretación. Como los dijes son una variable discreta que solo se pueden fabricar en unidades enteras, se tienen dos posibles alternativas de fabricación para la siguiente semana: fabricar 46 dijes 1 y 28 dijes 2 ó 45 dijes 1 y 29 dijes 2.  Alternativa 1: si se fabrican 46 dijes 1 y 28 dijes 2, se tendrá un sobrante de 60 gramos de oro y 100 gramos de cobre, con una utilidad total de $6,100.  Alternativa 2: fabricar 45 dijes 1 y 29 dijes 2, se tendrán sobrantes de 60 gramos de oro y 20 gramos de plata, con una utilidad total de $6,080. La mejor decisión será fabricar la alternativa 1 donde la restricción dominante o “cuello de botella” es la disponibilidad de la plata. JEVA / PTI

2

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

2. Productos de Moda. Una empresa fabrica tres productos de moda, que Mercadotecnia ha nombrado como producto 1, 2 y 3. Estos productos se fabrican a partir de tres ingredientes A, B y C. Los kilogramos de cada ingrediente que se requieren para fabricar un kilogramo de producto terminado se presentan en la siguiente tabla:

Tipo de Producto P1 P2 P3

Ingredientes (KgIng./kgProd. Terminado) A B C 8 7 4 7 9 3 12 2 2

La empresa dispone de 400, 800 y 1000 kilogramos de los ingredientes A, B y C respectivamente. Con las condiciones actuales del mercado, el margen de utilidad por kilogramo para el producto 1 es de $180, para el producto 2 es de $100 y de $120 para el producto 3. Modele el problema para determinar la cantidad de cada producto que debe fabricarse para maximizar las utilidades. Modelación. Variables de Decisión. Xi = Producto Terminado tipo "i" a fabricarse. (KgPT) Función Objetivo. Máx Z = 180X1 + 100 X2 + 120 X3 $ ($/Kgpt)Kgpt = $ Restricciones. 1. Ingredientes. A 4X1 + 3X2 + 2X3 ≤ 400 B 7X1 + 9X2 + 2X3 ≤ 800 C 8X1 + 7X2 + 12X3 ≤ 1000 (Kgi/Kgpt)Kgpt = Kgi Kgi 2. No negatividad. Xi ≥ 0 Análisis Dimensional: Probado. Solución Optima. X1 = 87.5 X3 = 25 Ingrediente B (H2) = 137.5 Máx. Z = 18,750 Interpretación. Como los kilogramos son una variable continua que se pueden fabricar en cualquier valor fraccionario, el programa de producción indica que se deben de fabricar 87.5 Kg del producto 1 y 25 Kg del producto 3 para así lograr la máxima utilidad de $18,750. Fabricando este programa, se tendrá un sobrante de 137.5 Kg del ingrediente B considerando como restricciones dominantes la disponibilidad de los ingredientes A y C. 3. Paquetes de Botanas. Una empresa dedicada a la venta de botanas fabrica tres paquetes para su distribución: el familiar, el estándar y el jumbo. El paquete familiar tiene 200 gramos de cacahuate salado, 150 gramos de cacahuate enchilado, 300 gramos de pepita y 150 gramos de pistache. El estándar tiene 150 gramos de cacahuate salado, 100 gramos de cacahuate enchilado, 200 gramos de pepita, 100 de pistache y 70 gramos de nuez de la india. Finalmente el jumbo tiene 400 gramos de cacahuate salado, 250 de cacahuate enchilado, 300 de pepita, 300 de pistache y 150 de nuez de la india. Las existencias que se tienen en la bodega son de 100 kilogramos de cacahuate salado, 80 de cacahuate enchilado, 80 de pepita, 65 de pistache y 40 de nuez de la india. El margen de utilidad de cada paquete familiar, estándar y jumbo es de $5, $7 y $10 respectivamente.

JEVA / PTI

3

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

a. Elabore una tabla donde resuma los datos del problema. b. Desarrolle un modelo para hacer un programa de producción diario que indique la cantidad de paquetes que deben ser elaborados para maximizar la utilidad total. Tabla de datos. Tipo de Paquete Familiar Estándar Jumbo Disponibilidad (kg/día)

Cacahuate Salado 200 150 400 100

Ingredientes (gramos/paquete) Cacahuate Pepitas Pistache Enchilado 150 300 150 100 200 100 300 300 250 80 80 65

Nuez de la India 0 70 150 40

Utilidad ($/paquete) 5 7 10

Modelación. Variables de Decisión. Xi = Paquete de botanas tipo "i" a fabricar por día. (p/d) Función Objetivo. Máx. Z = 5X1 + 7X2 + 10X3 $/d ($/p)(p/d) = $/d Restricciones. 1. Ingredientes. Cacahuate salado Cacahuate enchilado Pepitas Pistache Nuez de la india 2. No negatividad

0.20X1 + 0.15X2 + 0.40X3 ≤ 100 0.15X1 + 0.10X2 + 0.25X3 ≤ 80 0.30X1 + 0.20X2 + 0.30X3 ≤ 80 0.15X1 + 0.10X2 + 0.30X3 ≤ 65 0.07X 2 + 0.15X3 ≤ 40 (kg/p)(p/d) = kg/d kg/d Xi ≥ 0

Análisis Dimensional: Probado. Solución Optima. X2 = 400 Cacahuate salado (H1) = 40 Cacahuate enchilado (H2) = 40 Pistache (H4) = 25 Nuez de la india (H5) = 12 Máx. Z = 2,800 Interpretación. El programa de producción para mañana debe ser de 400 paquetes estándar que dará la máxima utilidad de $2,800. Al fabricar este programa, se tendrán los siguientes sobrantes: 40 Kg de cacahuate salado, 40 Kg de cacahuate enchilado, 25 Kg de pistache y 12 Kg de nuez de la india. El recurso que realmente limitó la fabricación fueron las pepitas. Si se tuviera suficiente existencia de pepitas, esta restricción dominante podría dejar de serlo para que otro de los recursos se convirtiera en el siguiente cuello de botella. 4. Zapatos. Una fabrica de zapatos fabrica tres modelos distintos, el modelo 1, 2 y 3 que utilizan los mismos materiales y mano de obra.

JEVA / PTI

4

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

Se disponen de 1,000 pares de plantillas especiales para los zapatos del modelo 2 y 3 que se utilizan dos pares para el modelo 3 y un par para el modelo 2. Se tienen 1,200 trozos de piel del tipo "A", utilizándose 4 trozos en el modelo 1 y 2 trozos en el modelo 2. Además hay 2,400 trozos de piel tipo "B", requiriéndose 4 trozos para el modelo 1 y 2 para el modelo 3. Se dispone de 40 horas para la fabricación, considerando que el tiempo requerido para cada par de zapatos del modelo 2 es de 4 minutos, de 7 minutos para el modelo 3 y de 2 minutos para el modelo 1. Los precios de venta son de $100, $200 y $300 para los zapatos del modelo 1, 2 y 3 respectivamente. ¿Cuántos pares de cada tipo se deben de fabricar para que el ingreso por ventas sea máximo? Modelación. Variables de Decisión. Xi = Pares del Modelo "i" a fabricarse. (p) Función Objetivo. Máx. Z = 100X1 + 200X2 + 300X3 $ ($/p) (p) = $ Restricciones. 1. Materiales. Plantillas especiales X2 + 2X3 ≤ 1,000 (pp/p)(p) = pp pp Trozos de piel: Tipo "A" 4X1 + 2X2 ≤ 1,200 Tipo "B" 4X1 + 2X3 ≤ 2,400 (t/p)(p) = t t 2. Producción 2X1 + 4X2 + 7X3 ≤ 2,400 (m/p)(p) = m m 3. No negatividad Xi ≥ 0 Análisis Dimensional: Probado. Solución Optima. X2 = 600 Plantillas especiales (H1) = 400 Piel tipo "B" (H3) = 2,400 Máx. Z = 120,000 Interpretación. Para tener el máximo ingreso posible de $120,000, se debe fabricar 600 pares del modelo 2. Al fabricar este programa, se tendrá un sobrante de 400 pares de plantillas especiales y 2,400 trozos de piel tipo "B". Existen dos restricciones dominantes: producción y la piel tipo "A". 5. Empresa Automotriz. Una empresa automotriz vende automóviles y camionetas. La empresa obtiene $30,000 de utilidad en cada automóvil que vende y $40,000 por cada camioneta. El fabricante no puede entregar más de 300 automóviles ni más de 200 camionetas por mes de acuerdo a su capacidad de producción. Para la venta de las unidades, la empresa necesita prepararlas en su taller donde se dispone de 900 horas mensuales. El arreglo de cada automóvil requiere de 2 horas y 3 horas para cada camioneta. Modele el problema para determinar cuántos vehículos de cada tipo se deben comprar mensualmente para maximizar las utilidades de la empresa. Modelación. Variables de Decisión. Xi = Vehículos "i" a comprarse mensualmente. (v/m) Función Objetivo.

JEVA / PTI

5

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

Máx. Z = 30,000 X1 + 40,000 X2 $/m ($/v)(v/m) = $/m Restricciones. 1. Capacidad del proveedor. Autos X1 ≤ 300 Camionetas X2 ≤ 200 v/m v/m 2. Capacidad del taller. 2 X1 + 3 X2 ≤ 900 (h/v)(v/m) = h/m h/m 3. No negatividad Xi ≥ 0 Análisis Dimensional: Probado. Solución Optima. X1 = 300 X2 = 100 Capacidad prov. camionetas (H2) = 100 Máx. Z = 13'000,000 Interpretación. Se deben de comprar para el siguiente mes 300 automóviles y 100 camionetas para obtener la máxima utilidad para la empresa de $13'000,000. Con este programa de compras, al proveedor le sobra capacidad para entregar 100 camionetas más y la capacidad del taller se saturó convirtiéndose en la restricción dominante. 6. Bombas Hidráulicas. Una empresa fabrica y vende dos tipos de bombas hidráulicas, la normal y la extragrande. El proceso de manufactura para las bombas se expresa en la siguiente tabla: Proceso de Manufactura (horas/unidad) Ensamble Pintura Control de Calidad 3.6 1.6 0.6 4.8 1.8 0.6

Tipo de Bomba Normal Extragrande

En la venta de cada bomba se obtiene un margen de utilidad de $500 para la bomba normal y de $750 para la extragrande. Analizando las estadísticas de las ventas pasadas, se observó que la mínima cantidad de bombas normales que se vendieron fueron de 300 semanales y 180 de las extragrandes. En el proceso de manufactura, se tienen disponibles semanalmente 4800 horas en ensamble, 1980 en pintura y 900 en control de calidad. a. Desarrolle una tabla de datos para el problema. b. La empresa quiere hacer un modelo para programar su producción de tal forma que le ayude a maximizar sus utilidades. Tabla de Datos. Tipo de Bomba Normal Extragrande Tiempo Disponible (horas/semana)

Proceso de Manufactura (hrs/unidad) Ensamble Pintura Control de Calidad 3.6 1.6 0.6 4.8 1.8 0.6 4,800

1,980

Utilidad ($/unidad) 500 750

Ventas mínimas (unid/sem) 300 180

900

Modelación. Variables de Decisión. Xi = Bomba tipo "i" a fabricarse por semana.

JEVA / PTI

6

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

(b/s)

Función Objetivo. Máx. Z = 500X1 + 750X2 $/s ($/b) (b/s) = $/s Restricciones. 1. Producción. Ensamble 3.6X1 + 4.8X2 ≤ 4,800 Pintura 1.6X1 + 1.8X2 ≤ 1,980 Control Calidad 0.6X1 + 0.6X2 ≤ 900 (h/b) (b/s) = h/s h/s 2. Ventas. Bomba Normal X1 ≥ 300 Bomba Extragrande X2 ≥ 180 b/s b/s 3. No negatividad Xi ≥ 0 Análisis Dimensional: Probado. Solución Optima. X1 = 300 X2 = 775 Pintura (H2) = 105.0001 C. Calidad (H3) = 255 Ventas B. Extragrande (E5) = 595 Máx. Z = 731,250 Interpretación. El programa de producción para la siguiente semana, debe fabricar 300 bombas normales y 775 extragrandes para tener la máxima utilidad de $731,250. Con esta fabricación, se tendrán en pintura un sobrante de 105.0001 horas y en control de calidad de 255 horas. En lo referente a las ventas, se tendrá un excedente de 595 bombas extragrandes respecto a la venta mínima de 180. La restricción dominante está en ensamble. 7. Agricultura: Comunidad Rural. Un grupo de ingenieros agrónomos está dando asesoría a una comunidad rural. Han recomendado a la comunidad cultivar brócoli y coliflor en sus 500 hectáreas de terreno. Una hectárea de brócoli da una utilidad de $500 mientras que una de coliflor da $1,000. Debido a un estudio de mercado realizado por los asesores, se determinó que no se podrá cultivar más de 200 hectáreas de brócoli por razones de demanda. Durante la temporada de la plantación se dispondrá de 120,000 horas-plantador, considerando que una hectárea de brócoli requiere de 250 horas-hombre y una de coliflor 550. El grupo de asesores le piden que modele el problema para determinar cuántas hectáreas de cada cultivo deben plantarse para maximizar las utilidades de la comunidad rural. Modelación. Variables de Decisión. Xi = Hectáreas a plantarse del cultivo "i". (ha) Función Objetivo. Máx Z = 500 X1 + 1000 X2 $ ($/ha)ha = $ Restricciones. 1. Terreno

JEVA / PTI

X1 + X2 ≤ 500 ha ha

7

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

2. Demanda

X1 ≤ 200 ha ha 3. Plantación 250 X 1 + 550 X2 ≤ 120000 (h-h/ha) ha = h-h h-h 4. No negatividad Xi ≥ 0 Análisis Dimensional: Probado. Solución optima. X1 = 200 X2 = 127.2727 Terreno (H1) = 172.7273 Máx. Z = 227, 272.7 Interpretación. Se deben plantar 200 hectáreas de brocolí y 127.2727 de coliflor para tener la máxima utilidad posible de $227,272.70. Con este programa de cultivo se tiene un sobrante de 172.7273 hectáreas de terreno y se tiene como restricción dominante la demanda y la plantación. 8. Bolsas de Piel. Una empresa fabrica dos bolsas de piel. El tipo "A" es fina con un precio de venta de $550 y el tipo "B" es corriente y se vende a $230. El abastecimiento de piel es suficiente para hacer 170 bolsas diarias. Se fabrican dos bolsas "B" por una de "A" y diariamente se pueden fabricar 250 bolsas del tipo "B" si solamente se hicen de éstas. La bolsa "A" requiere de un broche elegante, disponiéndose de solo 80 broches de este tipo y para la bolsa "B" que lleva un broche más sencillo se tienen 100. Pueden venderse por lo menos 130 bolsas diarias combinando el tipo "A" y "B". ¿Qué cantidad de bolsas se debe fabricar para maximizar los ingresos por venta? Modelación. Variables de Decisión. Xi = Bolsa tipo "i" a fabricarse diariamente. (b/d) Función Objetivo. Máx. Z = 550X1 + 230X2 $/d ($/b)(b/d) = $/d Restricciones. 1. Materiales. Piel

X1 + X2 ≤ 170 b/d b/d

Broches: Bolsa "A" X1 ≤ 80 Bolsa "B" X2 ≤ 100 (br/b)(b/d)=br/d br/d 2. Producción. Proporción Bolsa "B" 3. Ventas 4. No negatividad

X2 2 = X1 1 - 2X1 + X2 = 0 X2 ≤ 250 b/d b/d X1 + X2 ≥ 130 b/d b/d Xi ≥ 0

Análisis Dimensional: Probado. JEVA / PTI

8

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

Solución Optima. X1 = 43.3333 X2 = 86.6667 Piel (H1) = 40 Broche A (H2) = 36.6667 Broche B (H3) = 13.3333 Producción bolsa B (H4) = 163.3333 Máx. Z = 43, 766.67 Interpretación. La fabricación de bolsas es una variable discreta por lo que se necesita hacer un ajuste en los valores de la solución matemática. El programa de producción para mañana debe fabricar 43 bolsas del tipo A y 87 bolsas del tipo B para tener la máxima utilidad posible de $43,660. Con este programa se tendrá un sobrante de piel para 40 bolsas; un sobrante de broches para 37 bolsas del tipo A y 13 broches para bolsas del tipo B y también sobra capacidad para fabricar 163 bolsas del tipo B. La restricción dominante en este problema está dada por la proporción. Considerando el ajuste realizado, se tiene que la proporción de la bolsa B es de 2.02 veces en vez de 2. 9. Productos para Computadora. Una empresa fabrica productos para el mercado de las computadoras. Produce un paquete de limpieza y dos tipos de disco de alta densidad, el de cinco un cuarto de pulgada y el de tres y media solo en lotes de 1,000 unidades. La contribución unitaria a las utilidades es de $2 para el disco de tres y media pulgadas, $1 para el disco de cinco un cuarto y $3.50 para el paquete de limpieza. El proceso de producción tiene tres centros de manufactura por los que pasan cada uno de los productos y mediante un estudio de tiempos, se calcularon los siguientes datos:

Tipo de Producto Disco 3.5¨ Disco 5,25¨ Paquete limpieza Tiempo Disponible (horas/semana) Costo Fijo ($/semana)

Proceso de Producción (horas/lote) Centro Centro Centro3 1 2 1 2 3 3 1 4 2 2 2 60 40 80 1000

2000

1500

Desarrolle un modelo para programar la producción para la siguiente semana en lotes, de tal forma que maximice las utilidades de la empresa. Modelación. Variables de Decisión: Xi = Lotes de 1,000 unidades del Producto "i" a fabricarse por semana. (l/s) Función Objetivo: Máx Z = 2,000 X1 + 1,000 X2 + 3,500 X3 $/s ($/l)(l/s) = $/s Restricciones: Los costos fijos no forman una restricción ya que siempre se tienen haya o no producción. 1. Producción. Centro 1 3X1 + 4X2 + 2X3 ≤ 60 Centro 2 2X1 + X2 + 2X3 ≤ 40 Centro 3 X1 + 3X2 + 2X3 ≤ 80 (h/l)(l/s) = h/s h/s 2. No negatividad Xi ≥ 0

JEVA / PTI

9

EJERCICIOS DE PROGRAMACIÓN LINEAL

MODELACIÓN, SOLUCIÓN E INTERPRETACIÓN

Análisis Dimensional: Probado. Solución Optima. X3 = 20 Centro 1 (H1) = 20 Centro 3 (H3) = 40 Máx. Z = 70,000 Interpretación. En el programa de producción para la siguiente semana se debe fabricar 20 lotes de paquetes de limpieza para obtener la máxima utilidad de $70,000. Realizando este programa, se tendrá una capacidad sobrante de 20 horas en el centro 1 y de 40 horas en el centro 3. Considerando estos resultados, el cuello de botella está localizado en el centro 2. 10. Servicio de Transporte Terrestre. Una empresa adquirió un permiso del gobierno para realizar el transporte terrestre del aeropuerto a la ciudad. Actualmente se tiene una flotilla de 30 vagonetas que se reemplazarán totalmente ya que el costo de mantenimiento es muy alto por ser modelos viejos. Para el reemplazo se están considerando tres tipos de vehículos: vagoneta, minibús y autobús. La empresa ha calculado las utilidades netas esperadas para cada tipo de vehículo y las presenta en el siguiente cuadro: Tipo de Vehículo Vagoneta Minibús Autobús

Precio del Vehículo ($/unidad) 650,000 1050,000 2900,000

Utilidad Neta Esperada ($/unidad) 200,000 280,000 650,000

El consejo de administración ha autorizado $50 millones para la adquisición de vehículos. La proyección de la demanda del transporte garantiza que todos los vehículos que se puedan comprar con el capital se usarán para el transporte; sin embargo, la capacidad del taller para dar mantenimiento a los vehículos es limitada, actualmente solo puede atender a las 30 vagonetas que se tienen. La empresa no desea hacer ninguna ampliación a la capacidad del taller, pero debe estar preparado para atender también los minibuses y autobuses que se compren. Un minibús es equivalente a 1.5 vagonetas y un autobús equivale a 3 vagonetas. La empresa quiere tener un modelo que le permita determinar el número óptimo de cada tipo de vehículo que deba comprar para maximizar las utilidades netas esperadas. Modelación. Variables de Decisión. Xi = Vehículos del tipo "i" a comprarse. (v) Función Objetivo. Máx Z = 200,000X1 + 280,000X2 + ...