2_209_Modelos_PL

Programación Lineal (PL).

Construcción de Modelos.

Investigación de Operaciones I(SIS-209; IND-225)Ing. Viktoria Belianskaya

Programación Lineal (PL). Construcción de Modelos.

Contenido:

El impacto de PL en la actualidad. Elementos de los modelos de PL. Proceso de construcción de los modelos de PL. Ejemplo prototipo. Suposiciones y limitaciones de los modelos de PL. Ejemplos de construcción de los modelos de PL

para diferentes áreas de aplicación.

Programación Lineal (PL).

Dio un impulso al desarrollo de la IO. Una de las más aplicables herramientas

de IO. Netamente determinística. Se usa en varias temas específicos que

trata IO.

Programación Lineal (PL)

Nace oficialmente el 1947. Modelo General de PL y su solución. Proyecto SCOOP (Scientific Computation of Optimum Program). George Dantzig.

Primeras aplicaciones: militares, económicas y teoría de juegos. Actualmente: transporte, medio ambiente, sociología, hospitales, industria en general.

Método de solución de PL.

Método SIMPLEX de la solución del modelo general de PL (1947).

Primera computadora (1946). Primer problema de PL resuelto con éxito:

problema de la dieta (1948), manualmente tomó 120 días-hombre, hoy con el uso de computadora es fracción de segundo.

Ejemplo Prototipo 1 George Bell intenta determinar cuántas unidades de teléfonos

inalámbricos producir cada día. Uno de ellos es el modelo estándar; el otro, es el modelo de luxe. La utilidad por unidad en el modelo estándar es de 40 dólares mientras que la utilidad por el modelo de luxe es de 60 dólares. Cada uno de ellos requiere 30 minutos de tiempo de ensamble. Los tiempos de inspección necesarios son: en el modelo de lujo 15 minutos, mientras que en el modelo estándar 10 minutos. La compañía debe llenar una orden de 6 teléfonos de luxe. Hay 450 minutos de tiempo de ensamble y 180 minutos de tiempo de inspección disponibles cada día. ¿Cuántas 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? ¿Cuáles? ¿Cuál es la meta en el problema?

Modelo Ejemplo 1 Xe – cantidad de los teléfonos estándar para la

producción diaria (en unidades);Xl – cantidad de los teléfonos deluxe para la producción diaria (en unidades).Xe≥0, Xl ≥0

30Xe+30Xl ≤ 450 límite del tiempo de ensamblaje10Xe+15Xl ≤ 180 límite de tiempo de inspección

Xl ≥ 6 se debe cumplir la orden de los tel. de luxe

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

máxima posible

Ejemplo Prototipo 2 (problema de la dieta) Un granjero cría cerdos para venta y desea determinar las

cantidades de los distintos tipos de alimentos disponibles (maíz, grasas y alfalfa) que debe dar a cada cerdo. Como los cerdos se comerán cualquier mezcla de estos tipos de alimentos, el objetivo es determinar que mezcla cumple ciertos requerimientos nutricionales a un costo mínimo. En la siguiente tabla se dan las unidades de cada tipo de ingrediente nutritivo básico contenido en un kilogramo de cada tipo de alimento, junto con los requisitos nutricionales diarios y los costos de los alimentos.

Ingrediente

nutricional

Kilogramo de

maíz Kilogramo

de grasas Kilogramo

de alfalfa Requerimiento

mínimo diario Carbohidratos 90 20 40 200Proteínas 30 80 60 180Vitaminas 10 20 60 150Costo(u.m.) 84 72 60

Modelo Ejemplo 2 ¿Qué se quiere encontrar?

X1- cantidad de maíz (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? ¿Cuáles?90X1+20X2+40X3 ≥ 200 cumplir los requerimientos en carbohidratos30X1+80X2+60X3 ≥ 180 cumplir los requerimientos en vitaminas10X1+20X2+60X3 ≥ 150 cumplir los requerimientos en proteínas

¿Cuál es la meta en el problema?

Z = 84X1+72X2+60X3 → min el costo de alimento debe ser el mínimo posible

Ejemplo Prototipo 3(requerimiento de personal) El famoso restaurante E.S. Mann está abierto las 24 horas del día. 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 mínimo número de trabajadores necesarios durante los seis períodos en que está dividido el día. El problema de programación de Mann es la determinación de cuántos meseros y ayudantes deben reportarse al trabajo al principio de cada período de tiempo, con el fin de minimizar el total de empleados requeridos para un día de operación: (pista: Xi es igual al número de meseros y ayudantes que inician su trabajo en el período i, donde i=1,2,3,4,5,6).

Período Hora

Número requerido de meseros y ayudantes

1 3 am - 7am 3

2 7 am - 11am 12

3 11am - 3pm 16

4 3 pm - 7 pm 9

5 7 pm - 11pm 11

6 11pm - 3 am 4

Modelo Ejemplo 3 Variables

Xi - el número de meseros y ayudantes que inician su trabajo en el período i, donde i=1,2,3,4,5,6)

Xi≥0 Restricciones La cantidad de los trabajadores debe alcanzar para el

periodo determinadoPeríodo1: X6+X1 ≥ 3 Período4: X3+X4 ≥ 9Período2: X1+X2 ≥ 12 Período5: X4+X5 ≥ 11Período 3:X2+X3 ≥ 16 Período6: X5+X6 ≥ 4

Función ObjetivoZ= X1+X2+X3+X4+X5+X6 → min

minimizar el total de los meseros y ayudantes contratados

Ejemplo 4 (analizando los procesos)Una compañía de productos químicos dispone de 2 procesos de

reacción 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 día. La cantidad del compuesto Dipirona debe ser mayor a los 7 [kg] por

día. Las horas que se ejecuta el primer proceso no deben ser mayor a 5

[Hr] en el día con respecto a las horas que se ejecuta el proceso 2. El máximo 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.

<=30 kg

20$/kg

Dipirona

3 kg/h

1 kg/h

1 kg/h

Proceso 2

<=9 horas

<=9 horas

Proceso 1

Aspirina

>=7 kg

60$/kg

2 kg/h

En la misma hora !!!

En la misma hora !!!

Modelo ejemplo 4 Variables:

Xi – horas de ejecución del proceso i Xi>=0

Restricciones:1) Aspirina no más que 30 kg

2*X1+3*X2<=30 kg/h*h+kg/h*h= kg+kg= kg<=kganálisis dimensional

2) Dipirona no menos que 7 kg 1*X1+1*X2>=7

3) Cada proceso no más que 9 horasX1<=0 X2<=9

4) Horas Proceso1-Horas Proceso 2<=5 horasX1-X2<=5

Función Objetivo:Utilidad total máxima:

Z=20*(2*X1+3*X2) + 60*(X1+X2)=100*X1+120*X2max

Ejemplo 5 (con tratamiento de %)

En Explosives, Inc. se mezclan azufre, carbón y salitre para producir pólvora. El producto final debe contener al menos 10%, pero no más de 20%, de carbón por unidad de peso. La cantidad de salitre no puede exceder el 50% de la cantidad de carbón usado. Para evitar una explosión accidental, la suma de 50% del azufre más 60% del carbón más 30% del salitre usados no puede exceder el 35% del producto final. El azufre es con mucho el componente más caro. Formule un modelo para determinar la cantidad de cada ingrediente que debe utilizarse para producir cada libra de pólvora que satisfaga las restricciones y, a la vez, que requiera la menor cantidad de azufre.


Xi – peso de ingrediente i (en lb) en una libra de pólvora Xi>=0, i=1..3 (1-azufre, 2- carbón, 3-salitre)

Restricciones:1) Todos los ingredientes forman 1 lb

X1+X2+X3=1 2) Contenido de carbón (en una libra del producto final):

a) al menos 10% X2>=0.1

b) no más que 20% X2<=0.2

3) Cantidad de selitre no puede exceder 50% de carbón usadoX3<=0.5X2

4) Para evitar una explosión:0.5X1+0.6X2+0.3X3<=0.35

Función Objetivo:Usar la cantidad mínima posible de azufre:

Z=X1min

Ejemplo 6. Entender proceso e identificar las relaciones

La ciudad 1 produce 500 toneladas de basura por día, 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 incineración 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 día. 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 1 Incinerador 2

Ciudad 1 30 5

Ciudad 2 36 42

Basural 1 Basural 2

Incinerador 1 5 8

Incinerador 2 9 6

Entender el problema

Deshacerse 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 2

500 ton

400 ton

Ciudad 1 Incinerador1 Basural 1

Basural 2 <=200 ton

<=200 ton

<=500 ton

40$/ton

<=500 ton

30$/ton

Se reduce a 0.2

Costo de transporte: 3$/(milla*ton)


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,2 Restricciones:

1) Cantidad de basura de cada ciudad X11+X12=500

X21+X22=400 2) Capacidad de los incineradores

X11+X21<=500 X12+X22<=500

3) Relación de la cantidad de escombros que salen de los incineradoresY11+Y12=0.2(X11+X21)Y21+Y22=0.2(X12+X22)

4) Capacidad de los basurales Y11+Y21<=200Y12+Y22<=200

Función Objetivo:Minimizar el costo del procedimiento de eliminación de la basura (transporte basura, incineración, transporte escombros):

Z=3*30*X11+3*5*X12+3*36*X21+3*42*X22+ costo transp. basura + +40*(X11+X21)+30*(X12+X22)+ costo incineración + +3*5*Y11+3*8*Y12+3*9*X12+3*6*X22 min costo transp. escombros

Ejemplo 7. Programación en el tiempoHealthNut Company tiene una máquina que muele semillas de Psyllium hasta producir un polvo fino a una velocidad de 30 lb por hora. La compañía también usa la máquina para hacer crema de cacahuate con cacahuates tostados a una velocidad de 60 lb por hora. El tiempo de fijación para cambiar la máquina 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 también debe ser 0 a finales de julio. En ningún 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 máquina disponible. Formule un programa lineal para determinar un plan de producción 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 cacahuate Psyllium Crema de cacahuate Psyllium

Mayo 400 600 0.10 0.05

Junio 450 700 0.10 0.05

Julio 500 650 0.12 0.05


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 analogía con lo anterior)

Mayo X21>=600 Junio X22+(X21-600)>=700 Julio X23+(X22+(X21-600)-700)=650

3) Consideración del límite de inventario para crema de cacahuate X11-400<=500 lo que sobra en mayo X12+(X11-400)-450<=500 lo que sobra en junio, en julio será 0 y esto garantizan las restricciones con

igualdad3) Consideración del límite de inventario para Psyllium

X21-600<=1000 lo que sobra en mayo X22+(X21-600)-700<=1000 lo que sobra en junio

4) Capacidad mensual de máquina para procesamientoX11/60+X21/30<=200 MayoX12/60+X22/30<=200 JunioX13/60+X23/30<=200 Julio

Función Objetivo:Minimizar el costo de almacenamiento (basado en el inventario del inicio del mes):

Z= 0.10*(X11-400)+0.12*(X12+(X11-400)-450)+0.05*(X21-600)+0.05(X22+(X21-600)-700) min al inicio de junio y julio de cacahuate al inicio de junio y julio de Psyllium

Ejemplo 8. Análisis que produce la información para modelación.

Se cuenta con dos tipos de láminas de madera. El primer tipo es de 4 mts de largo y el segundo tipo de láminas es de 6 mts de largo. La cantidad de láminas del primer tipo es de 50 piezas y el de segundo tipo es de 75 piezas. Es necesario que las láminas 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 máxima cantidad de juegos de láminas.

Lámina 4 m

Lámina 6 m

Tipos de cortes:

1) 2 lam: 2 m

2) 1 lam: 2 m,

1 lam: 1,25 m

3) 3 lam: 1,25 mTipos de cortes:

1) 3 lam: 2 m

2) 2 lam: 2 m,

1 lam: 1,25 m

3) 1 lam: 2 m,

3 lam: 1,25 m

4) 4 lam: 1,25 m

Variables:

X1

X2

X3

Y1

Y2

Y3

Y4

Un Juego:

3 lam: 2 m,

2 lam: 1,25 m

Es necesario considerar la proporción en la cantidad de las tablas producidas para formar juegos


Xi – cantidad de láminas de 4 metros cortados de modo i Xi>=0, i=1..3 Yj – cantidad de láminas de 6 metros cortados de modo j Xj>=0, j=1..4

Restricciones:1) Límite de cantidad de láminas de 4 m

X1+X2+X3<=502) Límite de cantidad de láminas de 6 m

Y1+Y2+Y3+Y4<=75 3) Consideración de la proporción de las cantidades de las tablas de 2 m y de 1,25 m (utilizando los datos de análisis de los cortes posibles) (2X1+X2+3Y1+2Y2+Y3)/ 3 = (X2+3X3+Y2+3Y3+4Y4)/2 Cada una de las partes de esta relación representa el número de los juegos que sale

Función Objetivo:Maximizar la cantidad de los juegos a producir:

Z= (2X1+X2+3Y1+2Y2+Y3)/ 3 max

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 galón 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 después en $6.00 por galón. Cada galón 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 después en $8.00 por galón.

Formule un modelo de programación lineal para determinar un plan de producción que maximice la ganancia.

Alternativas de planteamiento del modelo en función del significado de las variables.Alternativa 1:

X1 = el número de galones de jugo de naranja usados en la semana.X2 = el número de galones de jugo de toronja usados en la semana.

Alternativa 2:X1= el número de galones de concentrado de naranja producidos en la semana.X2= el número de galones de concentrado de toronja producidos en la semana

Alternativa 3:X1 = el número de horas de tiempo de máquina a usarse esta semana para destilar jugo

de Naranja.X2 = el número de horas de tiempo de máquina a usarse esta semana para destilar jugo

de Toronja.

Principios generales de modelación:

No se debe elaborar un modelo complicado cuando uno simple es suficiente

El problema no debe ajustarse al modelo o método de solución La fase deductiva de la modelación debe realizarse rigurosamente Los modelos deben validarse antes de su implantación Nunca debe pensarse que el modelo es el sistema real Un modelo nunca debe de criticarse por algo para lo que no fue

hecho No venda un modelo como perfección máxima Uno de los primeros beneficios de la modelación reside en el

desarrollo del modelo. Un modelo es tan bueno o tan malo como la información con la que

se trabaja. Los modelos no pueden reemplazar al tomador de decisiones.

Modelo general de PL

1. Función Objetivo:

2. Restricciones:

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

)(·...·· 2211 MinMaxXcXcXcZ NN

) (

..1,·...··

..1,·...··

..1,·...··

2211

2211

2211

nesrestricciototalMmln

mlnlnpbXaXaXa

lnnkbXaXaXa

njbXaXaXa

pNpNpp

kNkNkk

jNjNjj

0,...,, 21 NXXX

Suposiciones (o características) del modelo de PL

Para que un modelo sea de PL se deben verificarse siguientes características:

Proporcionalidad Aditividad Divisibilidad Certidumbre


Proporcionalidad: La contribución de cada actividad al valor de la función objetivo o a lado izquierdo de una restricción es proporcional al nivel de esa actividad (cj*Xj o aij*Xj)

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

Valores X1 Proporcionalidad

se cumple

Proporcionalidad no se cumple

Caso1 Caso2 Caso3

0 0 0 0 0

1 3 2 3 3

2 6 5 7 5

3 9 8 12 6

4 12 11 18 6


Aditividad: Cada función 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 (Contribución de actividad 1: 3*X1

Contribución de actividad 2: 5*X2)

X1 X2 Aditividad

se cumple

Aditividad no se cumple

Caso1 Caso2

1 0 3 3 3

0 1 5 5 5

1 1 8 9 7Productos

complementariosProductos en competición


Divisibilidad: los valores de las variables pueden ser fraccionarios.

Certidumbre: Los coeficientes en la función objetivo y en las restricciones deben ser conocidos y constantes.

EjercicioUna compañía posee una fábrica de pinturas para interiores y exteriores de casas para

su distribución al mayoreo. Se utilizan dos materiales básicos A y B, para producir las pinturas. La disponibilidad máxima de A es de 6 toneladas diarias, la de B es de 8 toneladas por día. 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 más de una tonelada. Asimismo, el estudio señala que la demanda máxima 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. ¿Cuánta pintura para exteriores e interiores debe producir la compañía todos los días para maximizar el ingreso bruto?

MP Ton/ton pint. ext. Ton/ton pint. int. Disponibilidad Max(ton)

A 1 2 6

B 2 1 8

W. Winston: Problema 7 , pag. 98

Documents

2_209_Modelos_PL