Programacin Lineal (PL). Construccin de Modelos. Investigacin de Operaciones I(SIS-209; IND-225)Ing. Viktoria Belianskaya

Programacin Lineal (PL). Construccin de Modelos.Contenido:

El impacto de PL en la actualidad. Elementos de los modelos de PL. Proceso de construccin de los modelos de PL. Ejemplo prototipo. Suposiciones y limitaciones de los modelos de PL.Ejemplos de construccin de los modelos de PL para diferentes reas de aplicacin.

Programacin Lineal (PL).Dio un impulso al desarrollo de la IO.Una de las ms aplicables herramientas de IO.Netamente determinstica.Se usa en varias temas especficos que trata IO.

Programacin Lineal (PL)Nace oficialmente el 1947. Modelo General de PL y su solucin. Proyecto SCOOP (Scientific Computation of Optimum Program). George Dantzig.Primeras aplicaciones: militares, econmicas y teora de juegos. Actualmente: transporte, medio ambiente, sociologa, hospitales, industria en general.

Mtodo de solucin de PL.Mtodo SIMPLEX de la solucin del modelo general de PL (1947).Primera computadora (1946).Primer problema de PL resuelto con xito: problema de la dieta (1948), manualmente tom 120 das-hombre, hoy con el uso de computadora es fraccin de segundo.

Ejemplo Prototipo 1George Bell intenta determinar cuntas unidades de telfonos inalmbricos producir cada da. Uno de ellos es el modelo estndar; el otro, es el modelo de luxe. La utilidad por unidad en el modelo estndar es de 40 dlares mientras que la utilidad por el modelo de luxe es de 60 dlares. Cada uno de ellos requiere 30 minutos de tiempo de ensamble. Los tiempos de inspeccin necesarios son: en el modelo de lujo 15 minutos, mientras que en el modelo estndar 10 minutos. La compaa debe llenar una orden de 6 telfonos de luxe. Hay 450 minutos de tiempo de ensamble y 180 minutos de tiempo de inspeccin disponibles cada da. Cuntas unidades de cada producto deben ser fabricados para maximizar las utilidades?

Entender el Problema:Qu se quiere encontrar?Existen condiciones o limitaciones en el contexto? Cules?Cul es la meta en el problema?

Modelo Ejemplo 1Xe cantidad de los telfonos estndar para la produccin diaria (en unidades);

Xl cantidad de los telfonos deluxe para la produccin diaria (en unidades).Xe0, Xl 0

30Xe+30Xl 450 lmite del tiempo de ensamblaje

10Xe+15Xl 180 lmite de tiempo de inspeccin Xl 6 se debe cumplir la orden de los tel. de luxe

Z= 40Xe + 60Xl max ganancia total debe ser la

mxima posible

Ejemplo Prototipo 2 (problema de la dieta)Un granjero cra cerdos para venta y desea determinar las cantidades de los distintos tipos de alimentos disponibles (maz, grasas y alfalfa) que debe dar a cada cerdo. Como los cerdos se comern cualquier mezcla de estos tipos de alimentos, el objetivo es determinar que mezcla cumple ciertos requerimientos nutricionales a un costo mnimo. En la siguiente tabla se dan las unidades de cada tipo de ingrediente nutritivo bsico contenido en un kilogramo de cada tipo de alimento, junto con los requisitos nutricionales diarios y los costos de los alimentos.

Ingredientenutricional Kilogramo de maz Kilogramode grasas Kilogramode alfalfa Requerimientomnimo diario Carbohidratos 902040200Protenas 308060 180Vitaminas102060150Costo(u.m.)847260

Modelo Ejemplo 2Qu se quiere encontrar?

X1- cantidad de maz (en kg) en alimentoX2- cantidad de grasas (en kg) en alimentoX3- cantidad de alfalfa (en kg) en alimentoX1,X2,X3 0.

Existen condiciones o limitaciones en el contexto? Cules?

90X1+20X2+40X3 200 cumplir los requerimientos en carbohidratos30X1+80X2+60X3 180 cumplir los requerimientos en vitaminas10X1+20X2+60X3 150 cumplir los requerimientos en protenas

Cul es la meta en el problema?

Z = 84X1+72X2+60X3 min el costo de alimento debe ser el mnimo posible

Ejemplo Prototipo 3(requerimiento de personal)El famoso restaurante E.S. Mann est abierto las 24 horas del da. Los meseros y ayudantes se reportan para trabajar al inicio de los seis periodos indicados en la tabla, cada uno trabaja un turno de 8 horas. La siguiente tabla muestra el mnimo nmero de trabajadores necesarios durante los seis perodos en que est dividido el da. El problema de programacin de Mann es la determinacin de cuntos meseros y ayudantes deben reportarse al trabajo al principio de cada perodo de tiempo, con el fin de minimizar el total de empleados requeridos para un da de operacin: (pista: Xi es igual al nmero de meseros y ayudantes que inician su trabajo en el perodo i, donde i=1,2,3,4,5,6).

PerodoHoraNmero requerido de meseros y ayudantes13 am - 7am327 am - 11am12311am - 3pm1643 pm - 7 pm957 pm - 11pm11611pm - 3 am4

Modelo Ejemplo 3Variables

Xi - el nmero de meseros y ayudantes que inician su trabajo en el perodo i, donde i=1,2,3,4,5,6) Xi0Restricciones

La cantidad de los trabajadores debe alcanzar para el periodo determinadoPerodo1: X6+X1 3 Perodo4: X3+X4 9Perodo2: X1+X2 12 Perodo5: X4+X5 11Perodo 3:X2+X3 16 Perodo6: X5+X6 4

Funcin Objetivo

Z= X1+X2+X3+X4+X5+X6 min minimizar el total de los meseros y ayudantes contratados

Ejemplo 4 (analizando los procesos)Una compaa de productos qumicos dispone de 2 procesos de reaccin mediante los cuales debe producir 2 tipos de compuestos. Con el primer proceso se producen 2 [kg/h] del compuesto Aspirina y 1 [kg/h] del compuesto Dipirona. Mientras que el segundo proceso produce 3 [kg/h] de Aspirina y 1 [kg/h] de Dipirona.La gerencia ha determinado las siguientes condiciones:La cantidad del compuesto Aspirina no puede sobrepasar los 30 [kg] por da.La cantidad del compuesto Dipirona debe ser mayor a los 7 [kg] por da.Las horas que se ejecuta el primer proceso no deben ser mayor a 5 [Hr] en el da con respecto a las horas que se ejecuta el proceso 2. El mximo tiempo que se corre cada proceso es de 9 [Hr].El precio de venta del compuesto Aspirina es 20 [$/Kg], mientras que la Dipirona se vende a 60 [$/Kg].Objetivo es determinar las horas que debe ejecutarse cada proceso de manera que se maximice la utilidad total cumpliendo con las condiciones.

Entender el problema

Objetivo es determinar las horas que debe ejecutarse cada proceso de manera que se maximice la utilidad total cumpliendo con las condiciones.

>=7 kg60$/kg2 kg/h

En la misma hora !!!En la misma hora !!!

Modelo ejemplo 4Variables:

Xi horas de ejecucin del proceso i Xi>=0Restricciones:

1) Aspirina no ms que 30 kg 2*X1+3*X2

Ejemplo 5 (con tratamiento de %)En Explosives, Inc. se mezclan azufre, carbn y salitre para producir plvora. El producto final debe contener al menos 10%, pero no ms de 20%, de carbn por unidad de peso. La cantidad de salitre no puede exceder el 50% de la cantidad de carbn usado. Para evitar una explosin accidental, la suma de 50% del azufre ms 60% del carbn ms 30% del salitre usados no puede exceder el 35% del producto final. El azufre es con mucho el componente ms caro. Formule un modelo para determinar la cantidad de cada ingrediente que debe utilizarse para producir cada libra de plvora que satisfaga las restricciones y, a la vez, que requiera la menor cantidad de azufre.

Modelo ejemplo 5Variables:

Xi peso de ingrediente i (en lb) en una libra de plvora Xi>=0, i=1..3 (1-azufre, 2- carbn, 3-salitre)Restricciones:

1) Todos los ingredientes forman 1 lb X1+X2+X3=1 2) Contenido de carbn (en una libra del producto final): a) al menos 10% X2>=0.1b) no ms que 20% X2

Ejemplo 6. Entender proceso e identificar las relacionesLa ciudad 1 produce 500 toneladas de basura por da, y la ciudad 2 produce 400 toneladas de basura diarias. La basura debe ser incinerada en el incinerador 1 2, y cada incinerador puede procesar hasta 500 toneladas de basura diarias. El costo de incinerar basura es de $40 por tonelada en el incinerador 1 y de $30 por tonelada en el 2. La incineracin reduce cada tonelada de basura a 0.2 toneladas de escombros, que debe depositarse en alguno de dos basurales que reciben relleno. Cada uno de ellos puede recibir a lo sumo 200 toneladas de escombros por da. Cuesta $3 por milla transportar una tonelada de material (basura o escombros). Las distancias (en millas) entre los distintos lugares se muestra en la tabla. Formular un LP que minimice el costo total de deshacerse de la basura en las dos ciudades.

Incinerador 1Incinerador 2Ciudad 1305Ciudad 23642Basural 1Basural 2Incinerador 158Incinerador 296

Entender el problemaDeshacerse de la basura es identificar qu cantidades de basura se llevan de cada ciudad a cada de los incineradores, y qu cantidades de escombros se llevan de cada incinerador a cada uno de los basurales.

Incinerador 2Ciudad 2500 ton400 tonCiudad 1

Incinerador1Basural 1Basural 2

Modelo ejemplo 6Variables:

Xij cantidad de toneladas de basura que se lleva de la ciudad i al incinerador j Yjl cantidad de toneladas de escombros que se lleva del incinerador j al basural l Xij>=0,Yij>=0 i=1,2; j=1,2; l=1,2Restricciones:

1) Cantidad de basura de cada ciudad X11+X12=500 X21+X22=400 2) Capacidad de los incineradores X11+X21

Ejemplo 7. Programacin en el tiempoHealthNut Company tiene una mquina que muele semillas de Psyllium hasta producir un polvo fino a una velocidad de 30 lb por hora. La compaa tambin usa la mquina para hacer crema de cacahuate con cacahuates tostados a una velocidad de 60 lb por hora. El tiempo de fijacin para cambiar la mquina de un producto al otro es despreciable. La demanda mensual y los costos de mantenimiento de inventario de cada producto se muestran en la tabla .El inventario inicial para cada producto a principios de mayo es 0 y tambin debe ser 0 a finales de julio. En ningn momento el inventario de Psyllium puede exceder las 1.000 libras, ni de la crema de cacahuate las 500 libras. Asimismo, cada mes hay 200 horas de tiempo de mquina disponible. Formule un programa lineal para determinar un plan de produccin para los meses de mayo, junio y julio que minimice los costos totales de almacenamiento, suponiendo que satisface la demanda al final de cada mes y que los costos de mantenimiento de existencia se basan en la cantidad del inventario a principios del mes.

DEMANDA (lb)COSTOS DEALMACENAMIENTO($/lb)Crema de cacahuatePsylliumCrema de cacahuatePsylliumMayo4006000.100.05Junio4507000.100.05Julio5006500.120.05

Modelo ejemplo 7Variables:

Xij cantidad de libras del producto i que se produce en el mes j Xij>=0, i=1,2 (1- crema de cacahate, 2- Psyllium); j=1..3 (1-mayo, 2-junio, 3-julio)Restricciones:

1) Demanda que se debe satisfacer para crema de cacahuate Mayo X11>=400, Inventario inicial es 0, lo que se produce no debe ser menor que demanda Junio X12+(X11-400)>=450 Lo que se produce mas lo sobrante del mes anterior Julio X13+(X12+(X11-400)-450)=500 Debe ser =500 para dejar el inventario final 0.2) Demanda que se debe satisfacer para Psyllium (por analoga con lo anterior) Mayo X21>=600 Junio X22+(X21-600)>=700 Julio X23+(X22+(X21-600)-700)=650 3) Consideracin del lmite de inventario para crema de cacahuate X11-400

Ejemplo 8. Anlisis que produce la informacin para modelacin.Se cuenta con dos tipos de lminas de madera. El primer tipo es de 4 mts de largo y el segundo tipo de lminas es de 6 mts de largo. La cantidad de lminas del primer tipo es de 50 piezas y el de segundo tipo es de 75 piezas. Es necesario que las lminas se corten y se forman los juegos de tablas que se componen de 3 tablas de 2 mts y 2 de 1.25 mts de largo. Se necesita fabricar la mxima cantidad de juegos de lminas.

Lmina 4 mLmina 6 mTipos de cortes:1)2 lam: 2 m2)1 lam: 2 m, 1 lam: 1,25 m3) 3 lam: 1,25 mTipos de cortes:1)3 lam: 2 m2)2 lam: 2 m, 1 lam: 1,25 m3) 1 lam: 2 m,3 lam: 1,25 m4)4 lam: 1,25 mVariables:X1X2

X3

Y1Y2

Y3

Y4Un Juego:3 lam: 2 m,2 lam: 1,25 m

Es necesario considerar la proporcin en la cantidad de las tablas producidas para formar juegos

Modelo ejemplo 8Variables:

Xi cantidad de lminas de 4 metros cortados de modo i Xi>=0, i=1..3 Yj cantidad de lminas de 6 metros cortados de modo j Xj>=0, j=1..4

Restricciones:

1) Lmite de cantidad de lminas de 4 mX1+X2+X3

Ejemplo 9 (alternativas de planteamiento)(ver archivo Citrus)Cada semana, Florida Citrus, Inc., usa una sola maquina durante 150 horas para destilar jugo de naranja y de toronja en concentrados almacenados en dos tanques separados de 1000 galones antes de congelarlos. La maquina puede procesar 25 galones de jugo de naranja por hora, pero solo 20 galones de jugo de toronja. Cada galn de jugo de naranja cuesta $1.50 y pierde 30% de contenido de agua al destilarse en concentrado. El concentrado de jugo de naranja se vende despus en $6.00 por galn. Cada galn de jugo de toronja cuesta $2.00 y pierde 25% de contenido de agua al destilarse en concentrado. El concentrado de jugo de toronja se vende despus en $8.00 por galn.Formule un modelo de programacin lineal para determinar un plan de produccin que maximice la ganancia.Alternativas de planteamiento del modelo en funcin del significado de las variables.Alternativa 1:X1 = el nmero de galones de jugo de naranja usados en la semana.X2 = el nmero de galones de jugo de toronja usados en la semana.Alternativa 2:X1= el nmero de galones de concentrado de naranja producidos en la semana.X2= el nmero de galones de concentrado de toronja producidos en la semana Alternativa 3:X1 = el nmero de horas de tiempo de mquina a usarse esta semana para destilar jugo de Naranja.X2 = el nmero de horas de tiempo de mquina a usarse esta semana para destilar jugo de Toronja.

Modelo general de PL

Funcin Objetivo:

Restricciones:

Variables:

Si n=0, en el modelo no se tienen las restricciones ; Si l=0, entonces, se ausentan las restricciones de tipo ;Si m=0, el modelo es sin restricciones con igualdades.

Suposiciones (o caractersticas) del modelo de PLPara que un modelo sea de PL se deben verificarse siguientes caractersticas:ProporcionalidadAditividadDivisibilidadCertidumbre

Suposiciones (o caractersticas) del modelo de PLProporcionalidad: La contribucin de cada actividad al valor de la funcin objetivo o a lado izquierdo de una restriccin es proporcional al nivel de esa actividad (cj*Xj o aij*Xj)

Z=3*X1+5*X2 (Ganancia del producto 1: 3*X1)

Valores X1Proporcionalidadse cumpleProporcionalidad no se cumple Caso1 Caso2 Caso300000132332657539812641211186

Suposiciones (o caractersticas) del modelo de PLAditividad: Cada funcin en el modelo (sea f.o. o las restricciones) es la suma de las contribuciones individuales de las actividades respectivas Z=3*X1+5*X2 (Contribucin de actividad 1: 3*X1

Contribucin de actividad 2: 5*X2)

X1X2Aditividadse cumpleAditividad no se cumple Caso1 Caso2103330155511897Productos complementariosProductos en competicin

Suposiciones (o caractersticas) del modelo de PLDivisibilidad: los valores de las variables pueden ser fraccionarios.

Certidumbre: Los coeficientes en la funcin objetivo y en las restricciones deben ser conocidos y constantes.

Se cumplen las suposiciones?Una empresa textil fabrica 3 tipos de ropa: camisas, pantalones y shorts. Las mquinas necesarias para la confeccin deben ser alquiladas a los siguientes costos: 200$ por semana la mquina de camisas 150$ por semana la mquina de shorts 100$ por semana la mquina de pantalonesSe dispone de 150 horas hombre y 160 m de tela.Los requerimientos, costos y precio de venta de cada tipo de ropa son los siguientes: Horas Hombre m de tela Costo Precio de Venta Camisas 3 2 12 16 Shorts 2 1 8 14 Pantalones 6 3.5 15 18 Formular un modelo que maximice las ganancias.NO!!! Costos no son proporcionales a la cantidad producida

Una corporacin est desarrollando sus planes de comercializacin para los nuevos productos del ao prximo. Esta considerando la compra de un total de cinco comerciales de televisin en las redes nacionales para tres de estos productos , con un mximo de tres ( y un mnimo de cero) para cada producto. La tabla muestra el impacto estimado de asignar 0,1,2 o 3 comerciales a cada producto . Este impacto se mide en trminos de la ganancia (en millones de dlares ) de las ventas adicionales que resultaran de los comerciales. El objetivo es asignar cinco comerciales a los productos de manera que se maximice la ganancia total.NO!!! Los datos de las ganancias no son proporcionalesSe cumplen las suposiciones?

Nmero decomercialesGananciaProducto1 2 301230 0 01 0 -13 2 23 3 4

Principios generales de modelacin:No se debe elaborar un modelo complicado cuando uno simple es suficienteEl problema no debe ajustarse al modelo o mtodo de solucinLa fase deductiva de la modelacin debe realizarse rigurosamenteLos modelos deben validarse antes de su implantacinNunca debe pensarse que el modelo es el sistema realUn modelo nunca debe de criticarse por algo para lo que no fue hechoNo venda un modelo como perfeccin mximaUno de los primeros beneficios de la modelacin reside en el desarrollo del modelo.Un modelo es tan bueno o tan malo como la informacin con la que se trabaja.Los modelos no pueden reemplazar al tomador de decisiones.

EjercicioUna compaa posee una fbrica de pinturas para interiores y exteriores de casas para su distribucin al mayoreo. Se utilizan dos materiales bsicos A y B, para producir las pinturas. La disponibilidad mxima de A es de 6 toneladas diarias, la de B es de 8 toneladas por da. La necesidad de materia prima por tonelada de pintura se resume en la tabla. Un estudio del mercado ha establecido que la demanda diaria de pintura para interiores no puede ser mayor que la pintura de exteriores en ms de una tonelada. Asimismo, el estudio seala que la demanda mxima de pintura para interiores est limitada a 2 toneladas diarias. El precio al mayoreo por tonelada es $3000 para la pintura para exteriores y $2000 para la pintura de interiores. Cunta pintura para exteriores e interiores debe producir la compaa todos los das para maximizar el ingreso bruto?

MPTon/ton pint. ext.Ton/ton pint. int.Disponibilidad Max(ton)A126B218