PROGRAMACI N LINEAL LD - ejercicios formulados · programaciÓn lineal liliana delgado hidalgo ......

9/19/2012

1

PROGRAMACIÓN LINEAL

LILIANA DELGADO HIDALGO [email protected]

Universidad del Valle

EjemplosEjemplos dede modelamientomodelamiento..

i) Problema de Transporte. El problema consiste endecidir cuántas unidades trasladar desde ciertos puntosde origen (plantas, ciudades, etc.) a ciertos puntos dedestino (centros de distribución, ciudades, etc..) demodo de minimizar los costos de transporte, dada laoferta y demanda en dichos puntos.

Se suponen conocidos los costos unitarios detransporte, los requerimientos de demanda y la ofertadisponible.

EJEMPLOS PROBLEMAS DE PL

9/19/2012

2

191328Planta 2

152521Planta 1

C.Dist.3C.Dist.2 C.Dist. 1

191328Planta 2

152521Planta 1

C.Dist.3C.Dist.2 C.Dist. 1

… Ejemplos de … Ejemplos de modelamientomodelamiento (Problema del transporte)(Problema del transporte)

Por ejemplo, suponga que una empresa posee dos plantas que

elaboran un determinado producto en cantidades de 250 y

450 unidades diarias, respectivamente. Dichas unidades

deben ser trasladadas a tres centros de distribución con

demandas diarias de 200, 200 y 250 unidades,

respectivamente. Los costos de transporte (en $/unidad) son:


…… EjemplosEjemplos dede modelamientomodelamiento (Problema(Problema deldel Transporte)Transporte)

Diagrama:

Planta 1

Planta 2

C.D.2

C.D.1

C.D.3

X11

X12

X21 X22

X13

X23

Orígenes Destinos


9/19/2012

3

…… EjemplosEjemplos dede modelamientomodelamiento (Problema(Problema deldeltransporte)transporte)

Variables de decisión:

xij = Unidades transportadas desde la planta i (i=1,2),hasta el centro de distribución j (j=1,2,3)

Función Objetivo:

Minimizar el costo total de transporte dado por lafunción:

21x11+25x12+15x13+28x21+13x22+19x23


EjemplosEjemplos dede modelamientomodelamiento.. (Problema(Problema deldel transporte)transporte)

Restricciones del problema:

1) No Negatividad: xij ≥≥≥≥ 0

2) Demanda:

CD1 : x11 +x21 = 200

CD2 : x12 +x22 = 200

CD3 : x13 + x23 = 250


9/19/2012

4

…… EjemplosEjemplos dede modelamientomodelamiento.. (Problema(Problema deldel Transporte)Transporte)

3) Oferta :

P1 : x11 + x12 + x13 ≤≤≤≤ 250

P2 : x21 + x22 + x23 ≤≤≤≤ 450

Las variables de decisión deben aceptar soluciones como

números reales para tener un modelo de P.L.


…… EjemplosEjemplos dede modelamientomodelamiento.. (Problema(Problema dede Dieta)Dieta)

ii) Problema de la dieta: este consiste en determinar una dieta

de manera eficiente, a partir de un conjunto dado de alimentos,

de modo de satisfacer ciertos requerimientos nutricionales.

Supongamos que se tiene la siguiente información:

Leche(galon)

Legumbre(1 porción)

Naranjas(unidad)

RequerimientosNutricionales

Niacina 3,2 4,9 0,8 13

Tianina 1,12 1,3 0,19 15

Vitamina C 32 0 93 45

Costo 2 0,2 0,25


9/19/2012

5

…… EjemplosEjemplos dede modelamientomodelamiento.. (Problema(Problema dede Dieta)Dieta)


x1 : galones de leche utilizados en la dieta.

x2 : porciones de legumbre utilizadas en la dieta.

x3 : unidades de naranja utilizadas en la dieta.

Función Objetivo:

Minimizar el costo total de la dieta, dado por:

2 x1 + 0.2 x2 + 0.25 x3


EjemplosEjemplos dede modelamientomodelamiento.. (Problema(Problema dede Dieta)Dieta)


Requerimientos mínimos de los nutrientes considerados:

3.2 x1 + 4.9 x2 + 0.8 x3 ≥≥≥≥ 13

1.12 x1+ 1.3 x2 + 0.19 x3 ≥≥≥≥ 15

32 x1+ + 9 x3 ≥≥≥≥ 45

x1 ≥≥≥≥ 0 ; x2 ≥≥≥≥ 0 ; x3 ≥≥≥≥ 0


9/19/2012

6

EjemplosEjemplos dede modelamientomodelamiento.. (Lote(Lote dede producción)producción)

iii) Problema de dimensionamiento de lotes: este consiste enhallar una política óptima de producción para satisfacerdemandas fluctuantes en el tiempo, de modo que se logreminimizar costos de producción e inventario, considerando ladisponibilidad de diversos recursos escasos.

Supongamos que una fábrica puede elaborar hasta 150 unidadesen cada uno de los 4 periodos en que se ha subdividido elhorizonte de planificación y se tiene adicionalmente la siguienteinformación:


…… EjemplosEjemplos dede modelamientomodelamiento.. (Lote(Lote dede Producción)Producción)

Supuestos adicionales:

1) Existe un inventario inicial de 15 unidades.

2) No se acepta demanda pendiente o faltante (es decir, sedebe satisfacer toda la demanda del periodo).

Periodos Demandas(unidades)

Costo Prod.(US$/unidad)

Costo de Inventario(US$/unidad)

1 130 6 2

2 80 4 1

3 125 8 2.5

4 195 9 3


9/19/2012

7

…… EjemplosEjemplos dede modelamientomodelamiento.. (Lote(Lote dede producción)producción)


xt : número de unidades elaboradas en el periodo t.

It : número de unidades de inventario al final del periodo t.

Función objetivo:

Consiste en minimizar los costos de producción y el costo demantenimiento de inventario.

6x1+ 4x2 + 8x3 + 9x4 + 2I1 + I2 + 2.5I3 + 3I4



Notar que en el óptimo I4 va a ser 0, así que incluso podríamosno incluirla, pero de todos modos la consideramos.


1) Restricciones de cotas, que reflejan la capacidad deproducción.

xt ≤≤≤≤150

.


9/19/2012

8


2) Restricciones de no negatividad

xt ≥≥≥≥ 0

3) Restricciones de demanda

x1 + I0 – I1 = 130 Periodo 1 I0=15

x2 + I1 – I2 = 80 Periodo 2

x3 + I2 – I3 = 125 Periodo 3

x4 + I3 – I4 = 195 Periodo 4


…… EjemplosEjemplos dede modelamientomodelamiento.. (Planeación(Planeación financiera)financiera)

iv) Problema de planificación financiera:

Supongamos que un banco dispone de $250 millones paradestinar a 4 tipo de créditos ofrecidos, los cuales tienen lassiguientes, tasas de crédito:

• Primer crédito corriente :12%

• Segundo crédito corriente :16%

• Crédito para el hogar :16%

• Crédito personal :10%


9/19/2012

9


La asignación de estos créditos, debe satisfacer la siguientepolítica utilizada por la institución:

El monto asignado a los PCC, debe ser al menos, el 55% delmonto asignado a los créditos corrientes, y al menos un 25% deltotal del dinero prestado.

El SCC, no puede exceder el 30% del total del dinero prestado,por políticas tributarias el interés recibido por el banco no debeexceder a un retorno del 14% sobre el capital prestado.


…… EjemplosEjemplos dede modelamientomodelamiento.. (Planeación(Planeación Financiera)Financiera)

¿Cuánto asignar a cada tipo de crédito, de la manera más

eficiente, respetando la política del banco?


x1 :Monto asignado al PCC.

x2 : Monto asignado SCC.

x3 : Monto asignado al crédito para el hogar.

x4 : Monto asignado al crédito personal.


9/19/2012

10


Función Objetivo:

Se propone maximizar los retornos recibidos en la asignación,

dados por:

0.12 x1 + 0.16 x2 + 0.16 x3 + 0.10 x4


…… EjemplosEjemplos dede modelamientomodelamiento.. (Planeación(Planeación Financiera)Financiera)


x1 ≥≥≥≥ 0.55 ( x1 + x2 )

x1 ≥≥≥≥ 0.25 ( x1 + x2 +x3 + x4 )

x2 ≤≤≤≤ 0.30 ( x1 + x2 +x3 + x4 )

(0.12x1+0.16x2+0.16x3+0.10x4 ) ≤≤≤≤ 0.14 ( x1+ x2 +x3 +x4 )

Adicionalmente: x1 + x2 +x3 + x4 ≤≤≤≤ 250


9/19/2012

11

EjemplosEjemplos dede modelamientomodelamiento.. (Mezcla(Mezcla dede productos)productos)

v) Problema de mezcla de productos: en este problema una

refinería produce 4 tipos de gasolina (gas 1, gas 2, gas 3 y gas 4).

Dos características importantes de cada gasolina son su número

de performance (NP) y su presión de vapor (RVP), que están

dados por:

NP RVP Barriles diarios

gas 1 107 5 3814

gas 2 93 8 2666

gas 3 87 4 4016

gas 4 108 21 1300


…… EjemplosEjemplos dede modelamientomodelamiento.. (Mezcla(Mezcla dede Productos)Productos)

Estas gasolinas pueden ser vendidas directamente a un precio de

$24,83 por barril o bien mezcladas para obtener gasolinas de

aviación (avgas A y avgas B). La calidad de estas dos últimas junto

con sus precios de venta son:

NP (proporciones)

RV Precio por barril (US$)

avgas A Al menos 100 A lo más 7 26,45

Avgas B Al menos 91 A lo más 6 25,91


9/19/2012

12

…… EjemplosEjemplos dede modelamientomodelamiento.. (Mezcla(Mezcla dede Productos)Productos)


xj : cantidad de barriles del gas j que son vendidos sin mezclar,

con j = 1, 2, 3, 4.

xA : cantidad de barriles de avgas A.

xB : cantidad de barriles de avgas B.

xjA: cantidad de gas j usado en avgas A.

xjB: cantidad de gas j usado en avgas B.


…… EjemplosEjemplos dede modelamientomodelamiento.. (Mezcla(Mezcla dede productos)productos)

Función objetivo:

Max 24,83 (x1 + x2 + x3 + x4) + 26,45xA + 25,91xB

Restricciones: x1 + x1A + x1B = 3814

x2 + x2A + x2B = 2666

x3 + x3A + x3B = 4016

x4 + x4A + x4B = 1300

x1A + x2A + x3A + x4A = xA

x1B + x2B + x3B + x4B = xB


9/19/2012

13

…… EjemplosEjemplos dede modelamientomodelamiento.. (Mezcla(Mezcla dede productos)productos)

NP, avgas A:

NP, avgas B:

RVP, avgas A:

RVP, avgas B:

100x

x108x87x93x107

A

A4A3A2A1 ≥≥≥≥++++++++++++

91x

x108x87x93x107

B

B4B3B2B1 ≥≥≥≥++++++++++++

7x

x21x4x8x5

A

A4A3A2A1 ≤≤≤≤++++++++++++

621485 4321 ≤+++

B

BBBB

x

xxxx


CORTE DE PAPEL (CUTTING STOCK)

Una industria productora de papel recibe un pedido de la siguiente forma:

600 rollos de 35 pulg. de ancho




La industria tiene en sus bodegas rollos semejantes, pero de 114 pulg. deancho, y en cantidad suficiente y decide utilizarlos para el pedido, cortándolosen los diferentes anchos solicitados. ¿Cuál es la mejor forma de cortar losrollos de 114 pulg. de ancho para satisfacer el pedido y minimizar eldesperdicio de papel?

9/19/2012

14

Definición de las Variables de decisiónSe hace necesario encontrar todos los posibles patrones de corte lógicos que se pueden hacerpara satisfacer el pedido; ellos son:

Se consideran desperdicio de los rollos, resultantes de menos de 30 pulg. de ancho.

El desperdicio se considera proporcional al ancho perdido, pues se supone que todos los rollos de114 pulg. de ancho son del mismo largo.

Así, las variables de decisión serían:

Xi = Número de rollos de 114 pulg. de ancho a cortar según el patrón i (i = 1, 2,

.., 12).


Función Objetivo

Minimizar el desperdicio total:

RestriccionesLas restricciones surgen de la satisfacción del pedido, así:


9/19/2012

15

Solución con restricciones de igualdad:

En todos los casos: Dmín = 2600 pul

Solución con restricciones de ≥

Dmín = 1800 pul.

Aquí sobran rollos, pero se cumple con el pedido.


PROGRAMA DE PN EN EL

TIEMPO

Un fabricante debe cumplir un contrato a cuatro meses durantelos cuales varían los costos de producción. El costo dealmacenamiento de unidades producidas en un mesdeterminado y no vendidas en ese mes es de $10 por unidad ypor mes. Se dispone de la siguiente información:

Formule un modelo matemático para determinar el programaóptimo de producción que cumple con el contrato a costo totalmínimo.

9/19/2012

16

El “arte” de definir correctamente variables de decisión

Primera forma de formulación:

Variables de decisiónSean Xi = Número de unidades producidas

en el mes i; i =1, 2, 3, 4.

Función ObjetivoLa función objetivo tiene dos componentes:

Los costos de producción y los costos de almacenamiento.

Costos de producción

Costos de almacenamiento CA

Para encontrar la expresión para estos costos, es necesario ilustrar

el “balance de las unidades” a través del tiempo, así:


TIEMPO

Así, utilizando la convención de “fin de mes”, los costos de almacenamiento

serían:

O sea que la función objetivo simplificada es:


TIEMPO

9/19/2012

17

Restricciones:Por capacidad de producción:

Por contrato de ventas:

Obvias:


TIEMPO

Segunda forma de formulación:

Definición de las Variables de decisiónSean Xij = Número de unidades producidas en el mes i y vendidas en el mes j;

i =1, 2, 3, 4; j =1, 2, 3, 4. j ≥ i

X11, X12, X13, X14, X22, X23, X24, X33, X34 y X44,

Función Objetivo

Costos de almacenamiento CA:

Costos de producción CP:


TIEMPO

9/19/2012

18

Restricciones:

Por capacidad de producción:

Por contrato de ventas:

Obvias:


TIEMPO

Solución

Primera forma de formulación:

Costo mínimo = $22.100

X1 = 40

X2 = 30

X3 = 30

X4 = 40

Segunda forma de formulación:

Costo mínimo = $22.100

Se producen infinitas soluciones. Las 2 básicas

son:

X11 = 20 X11 = 20

X13 = 20 X12 = 20

X22 = 30 X22 = 10

X33 = 30 X23 = 20

X44 = 40 X33 = 30

X44 = 40

Número de variables

Información relevante. Cuándo se produce y cuándo se vende


TIEMPO

9/19/2012

19

PROGRAMACIÓN DE METAS

Cierta compañía planea introducir al mercado tres nuevos productos, debido a la próximaobsolescencia de los que produce actualmente. El interés de la gerencia es determinar las tasasde producción de cada uno de los productos, teniendo en cuenta tres objetivos fundamentales:

a. Lograr un Valor Presente Neto mínimo de mil millones de pesos (Utilidad a largo plazo).

b. Mantener el recurso laboral actual de 100 empleados (Nivel de empleo).

c. Sostener la inversión de capital en el nuevo equipo de 400 millones de pesos (Inversión inicial).

Como el gerente utiliza a menudo el Enfoque de Sistemas en sus decisiones, establece un“puntaje de penalización” para cada objetivo en caso de no cumplirse éste a cabalidad, así:

La contribución de cada producto la utilidad a largo plazo, al nivel de empleo y a lainversión de capital es proporcional a su tasa de producción y las contribucionesunitarias de cada producto son:

¿Cuáles deben ser las tasas de producción de cada producto para que los objetivos secumplan de la mejor forma posible?


9/19/2012

20

Variables de decisión

Dado que es necesario involucrar en el modelo los puntajes de penalización por

el incumplimiento de las metas, se definen Variables auxiliares

Si se definen las actividades como Xi = Tasa de producción del producto i(i=1,2, 3), las metas a cumplir serían las siguientes (en su orden: Objetivos (a),(b) y (c)):


Yi (i =1, 2, 3,) libres.

Si Y1> 0, indica que la utilidad ha sobrepasado los 1000 millones de pesos

Si Y1< 0, entonces la utilidad ha sido inferior a esa cifra y el objetivo no se

habría cumplido.


9/19/2012

21

Solución

El producto 2 no debería producirse.

Validación

Las metas de utilidad a largo plazo y de inversión inicial se cumplen a cabalidad,

produciéndose 100 decenas de millones de utilidad e invirtiéndose inicialmente

40 decenas de millones de pesos.La meta de nivel de empleo no puede ser cumplida, el nivel de empleados

debe ser aumentado en 5.0877 cientos, para poder cumplir con las otras dos

metas.

El puntaje óptimo P* = 15.2632 se obtiene de penalizar con 3 puntos por cada

10 empleados de más en la función objetivo.


PROBLEMA PROBABÍSTICO: ESTRATEGIA MILITAR

En cierto período de guerra, el comando aéreo recibió la orden de destruir la producción de

tanques del enemigo, quien tiene cuatro plantas claves localizadas en ciudades separadas.

La destrucción de cualquiera de las plantas parará efectivamente la producción de tanques.

Existe una aguda escasez de combustibles para llevar a cabo la misión, con un limitante de

51,000 galones. Cualquier bombardero enviado a una ciudad en particular debe tener

combustible para ir y volver y una reserva de 150 galones. El número de bombarderos

disponibles en el comando y su descripción se dan a continuación.

La información acerca de la localización de las plantas y su vulnerabilidad de ataque por

estos dos tipos de aviones es la siguiente:

9/19/2012

22

Formule un modelo de programación lineal para determinar cuántos

bombarderos de cada tipo deben ser enviados a cada planta, con el

objetivo de maximizar la probabilidad de éxito de la misión. Se asume

que no se causa ningún daño en la planta si un bombardero falla al

destruirla.


Variables de decisión:Sean Xij = Número de bombarderos tipo “i” a ser enviados a la planta

“j”;

i = 1: Bombardero tipo pesado,

i = 2: Bombardero tipo mediano,

j = 1, 2, 3, 4: Plantas 1, 2, 3 y 4, respectivamente.

Función objetivo: Minimizar la probabilidad de fracaso.

La probabilidad de fracaso sería la intersección (producto) de todas las

probabilidades de fracaso de cada bombardero a cada planta (se

considera independiente la acción de cualquier bombardero con

respecto a la de cualquier otro).


9/19/2012

23

Restricciones:

Por disponibilidad de aviones:

Por disponibilidad de combustible:

Un avión cualquiera debe tener combustible para ir a la planta, volver y tener

una reserva de 150 galonesLos aviones tipo pesado que se envíen a la planta 1 utilizarán la siguiente

cantidad de combustible:


Entonces tenemos…

Simplificando, se obtiene:


9/19/2012

24

Restricciones Obvias:

La solución óptima de este modelo de PL entera es:

X14 = 43

X24 = 34

Zmáx = 19.9572

ó probabilidad de falla de P = e−19.9572 = 2.15 ×10−9

O sea que si se envían 43 aviones pesados y 34 aviones medianos,

todos a la planta 4 del enemigo, la probabilidad de falla de la misión

es casi cero.


Mezcla Óptima de Productos –Variables Binarias

Una empresa europea piensa instalar plantas de producción en Cali para

lanzar sus productos al mercado nacional, por lo que necesita decidir su plan

de producción para el próximo año. La empresa puede fabricar N tipos de

productos y la elaboración de cada uno de ellos implica la compra de una

máquina especializada, a un costo de fi [$]. Además, el costo variable de

producir una unidad del producto i es de ci [$]. Así, si se decide elaborar el

producto i se deberá necesariamente incurrir en un costo de fi [$] más los

costos variables por elaboración del producto, y si se decide no fabricarlo no

se incurrirá en ningún tipo de gasto.

Si la demanda pronosticada para el producto i es de Di unidades (i = 1…N)

pudiendo venderse dicho producto a un precio de pi [$], formule un modelo

que resuelva el problema de encontrar el conjunto de productos que la

empresa debe fabricar, sabiendo que se desea producir exactamente L

productos diferentes, para los cuales se deberá satisfacer la demanda.

9/19/2012

25

CARGA AVIÓN

Un avión de carga tiene tres bodegas o compartimentos, adelante, al centro y atrás.

Estos compartimentos tienen límites de volumen y peso, así:

El propietario del avión tiene posibilidad de llevar parte de la carga o toda la que se le ofrece (si tiene

capacidad). Esta carga y sus características son las siguientes:

Para preservar el equilibrio del avión, el peso transportado en cada compartimiento debe guardar la misma

proporción con respecto a su capacidad. Formule un modelo matemático para determinar cuál tipo de carga,

qué cantidad y qué compartimentos debe el propietario del avión escoger para maximizar su utilidad y no

correr peligro durante el viaje.

PROBLEMAS DE PLProblema planeación de producción. (0)

Producción máxima. 200 artículos de A, 100 artículos de B, combinación de A y B

Capacidad diaria sección de pintura. 120 artículos de A, 160 artículos de B, combinación de

A y B

Capacidad diaria planta de tratamiento térmico. A no requiere, 90 artículos de B, o B sin

tratamiento

Procesamiento artículo A en minutos. 3 en M1 y 2 en M2

Procesamiento artículo B. Total de 5 en M1 o 2 en M1 y 1 en M2

Disponibilidad diaria de máquinas. 8 horas = 480 minutos

Consumo de material en libras. A ( 1 de X y 2 de Y) B (2 de X y 3 de Y)

Disponibilidad de material. 140 de X y 80 de Y

Costo de material por unidad. X = $200 Y = $300

Disponibilidad o presupuesto para la compra de material. $ 60.000

Restricción adicional de compra de material. De X no puede comprarse más del 20% de Y

Utilidad por cada artículo.

A = $ 4.000 B sin tratamiento = $ 3.000 B con tratamiento = $ 5.000

9/19/2012

26

PROBLEMAS DE PL

Problema producción – distribución (III)

M = número de plantas productoras.

Si = capacidad de producción por periodo de la planta i.

N = número de ciudades clientes.

T = número de periodos a analizar.

Djt = demanda de la ciudad j en el periodo t (Nota: la demanda DEBE ser satisfecha).

Cit = costo unitario de producción en la planta i en el periodo t.

P = número de bodegas.

gk = costo variable por cada unidad de producto almacenado durante un periodo en la

bodega k.

Wk = capacidad en unidades en la bodega k.

PBikt = costo de transporte desde la planta i hasta la bodega k en el periodo t.

BCkjt = costo de transporte desde la bodega k hasta la ciudad j en el periodo t.

PROGRAMACI N LINEAL LD - ejercicios formulados · programaciÓn lineal liliana delgado hidalgo ......

Documents

Transcript of PROGRAMACI N LINEAL LD - ejercicios formulados · programaciÓn lineal liliana delgado hidalgo ......