unmsm fisi - estudio de casos de problemas de programación lineal - io1 cl05
Post on 20-Jul-2015
1.036 Views
Preview:
TRANSCRIPT
1
Estudio de casos de problemas de
Programación Lineal
Docente : Lic. Gabriel Solari Carbajal
Universidad Nacional Mayor de San MarcosFacultad de Ingeniería de Sistemas e Informática
Investigación Operativa I
2
CASO 1: ASIGNACION DE RECURSOS AGRICOLAS
Una Cooperativa opera 3 granjas.Los datos acerca de las granjas son las siguientes:
TERRENO AGUAUTILIZABLE DISPONIBLE
(ha) (m3)1 700 20002 800 24003 600 1500
GRANJA
La Cooperativa considera sembrar 4 productos A, B, Cy D.
Estudio de Casos de PPL
2
3
No se puede mostrar la imagen en este momento.
CANTIDAD CONSUMO UTILIDADMAXIMA DE DE ESPERADATERRENO AGUA POR HECTAREA
(ha) (m3/ha) ($)A 500 5 2000B 700 4 1500C 400 3 1000D 600 4 1500
PRODUCTO
Además para mantener una carga uniforme de trabajo,se establece que en todas las granjas se debe utilizar elmismo porcentaje de terreno.
Determine el plan óptimo de sembrío para maximizar lautilidad esperada.
Estudio de Casos de PPL
4
SOLUCION:
Determinando los posibles sembrios en cada granja:
1 2 3
A A1 A2 A3B B1 B2 B3C C1 C2 C3D D1 D2 D3
Estudio de Casos de PPL
3
5
1
2
3
A
B
C
D
PRODUCTOS
GRANJAS
A1A2
A3B1
B2B3C1
C2C3
D2D1
D3
Estudio de Casos de PPL
6
Variables de decisión:
Ai i = 1, 2, 3
Bi i = 1, 2, 3
Ci i = 1, 2, 3
Ejemplo
C2: número de hectáreas a sembrar del producto C enla granja 2
Estudio de Casos de PPL
4
7
Restricciones:
Por terreno utilizableA1 + B1 + C1 + D1 ≤ 700
A2 + B2 + C2 + D2 ≤ 800
A3 + B3 + C3 + D3 ≤ 600
5 A3 + 4 B3 + 3 C3 + 4 D3 ≤ 1500
Por agua disponible5 A1 + 4 B1 + 3 C1 + 4 D1 ≤ 2000
5 A2 + 4 B2 + 3 C2 + 4 D2 ≤ 2400
Estudio de Casos de PPL
8
Por cantidad máxima a sembrar de cada productoA1 + A2 + A3 ≤ 500
B1 + B2 + B3 ≤ 700
C1 + C2 + C3 ≤ 400
7 A3 + 7 B3 + 7 C3 + 7 D3 – 6 A1 – 6 B1 – 6 C1 – 6 D1 = 0
Por carga uniforme de trabajo
8 A1 + 8 B1 + 8 C1 + 8 D1 – 7 A2 – 7 B2 – 7 C2 – 7 D2 = 0
8 A3 + 8 B3 + 8 C3 + 8 D3 – 6 A2 – 6 B2 – 6 C2 – 6 D2 = 0
D1 + D2 + D3 ≤ 600
6003D3C3B3A
8002D2C2B2A
7001D1C1B1A +++
=+++
=+++
Estudio de Casos de PPL
5
9
Por no negatividadA1, A2, A3, B1, B2, B3, C1, C2, C3, D1, D2, D3 ≥ 0
Función objetivo:Maximizamos la utilidadMax Z = 2000 (A1 + A2 + A3) + 1500 (B1 + B2 + B3) + 1000 (C1 + C2 + C3) +
1500 (D1 + D2 + D3)
Estudio de Casos de PPL
10
Un barco tiene tres bodegas: en la proa, en el centro yen la popa. Los límites de capacidad son:
CapacidadPeso Volumen(Ton) (Pies3)
Proa 2,000 100,000Centro 3,000 135,000Popa 1,500 30,000
Bodega
CASO 2: CARGA DEL BARCO
Estudio de Casos de PPL
6
11
Se ofrecen los siguientes cargamentos y los dueños delos barcos pueden aceptar el total o una porcióncualquiera de cada artículo.
Cantidad GanaciaPeso Vol/Ton por Ton(Ton) (Pies3) ($)
A 6,000 60 6B 4,000 50 8C 2,000 25 5
Artículo
Estudio de Casos de PPL
12
Para preservar el equilibrio de barco, el peso en cadabodega debe ser proporcional a la capacidad entoneladas.
¿Cómo debe distribuirse la carga para hacer máxima laganancia?
Estudio de Casos de PPL
7
13
La siguiente gráfica permite visualizar el problema eidentificar las variables de decisión.
POPA
CENTRO
PROA
A
B
C
A1
A2A3
B1B2
B3
C1 C2
C3
SOLUCION:
Estudio de Casos de PPL
14
Variables de decisión:
Ai i = 1, 2, 3
Bi i = 1, 2, 3
Ci i = 1, 2, 3
Ejemplo
C1: cantidad de toneladas del producto C que setransporta en la bodega 1 (proa)
i = 1 (Proa), 2 (Centro) y 3 (Popa)
Estudio de Casos de PPL
8
15
Por límite de cantidad de artículosRestricciones
Por límite de capacidad de peso del barco
A1 + A2 + A3 ≤ 6000
B1 + B2 + B3 ≤ 4000
C1 + C2 + C3 ≤ 2000
A1 + B1 + C1 ≤ 2000
A2 + B2 + C2 ≤ 3000
A3 + B3 + C3 ≤ 1500
Estudio de Casos de PPL
16
Por límite de capacidad de volumen del barco
Por equilibrio del barco
60 A1 + 50 B1 + 25 C1 ≤ 100000
60 A2 + 50 B2 + 25 C2 ≤ 135000
60 A3 + 50 B3 + 25 C3 ≤ 30000
500,13C3B3A
000,32C2B2A
000,21C1B1A ++
=++
=++
3 A1 + 3 B1 + 3 C1 – 2 A2 – 2 B2 – 2 C2 = 0
2 A3 + 2 B3 + 2 C3 – 1.5 A1 – 1.5 B1 – 1.5 C1 = 0
2 A3 + 2 B3 + 2 C3 – A2 – B2 – C2 = 0
Estudio de Casos de PPL
9
17
Por no negatividadA1, A2, A3, B1, B2, B3, C1, C2, C3 ≥ 0
Función objetivo:Maximizamos la gananciaMax Z = 6 A1 + 6 A2 + 6 A3 + 8 B1 + 8 B2 + 8 B3 + 5 C1 + 5 C2 + 5 C3
Estudio de Casos de PPL
18
CASO 3: PROBLEMA DE LOS CORTES DE PAPEL
Una compañía papelera produce rollos de 3dimensiones:
Rollo Dimensión(cm.)
A 100B 150C 200
Estudio de Casos de PPL
10
19
La compañía tiene los siguientes pedidos de papel:
Dimensión Cantidad pedida(cm.) (und.)
50 18070 20080 15090 80
Estudio de Casos de PPL
20
Además se sabe que para la próxima semana sólo setendrán disponibles:
Rollo Disponible(und.)
A gran cantidadB 115C 90
Plantee un modelo para determinar una planificaciónóptima de cortes y resuelva utilizando LINDO/PC.
Estudio de Casos de PPL
11
21
SOLUCION:
Determinando las modalidades de cortes
Rollo A = 100 cm.Corte A1 A2 A3 A450 cm 2 - - -70 cm - 1 - -80 cm - - 1 -90 cm - - - 1
Desperdicio 0 30 20 10
Estudio de Casos de PPL
22
Rollo B = 150 cm.Corte B1 B2 B3 B4 B5 B650 cm 3 1 1 1 - -70 cm - 1 - - 2 180 cm - - 1 - - 190 cm - - - 1 - -
Desperdicio 0 30 20 10 10 0
Rollo C = 200 cm.Corte C1 C2 C3 C4 C5 C6 C7 C8 C9 C1050 cm 4 2 2 2 1 1 - - - -70 cm - 1 - - 2 1 1 - - -80 cm - - 1 - - 1 - 2 1 -90 cm - - - 1 - - 1 - 1 2
Desperdicio 0 30 20 10 10 0 40 40 30 20
Estudio de Casos de PPL
12
23
Variables de decisión:
Ai i = 1, 2, 3, 4
Bi i = 1, 2, 3, 4, 5, 6
Ci i = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Ejemplo
C5: número de veces que se utiliza el proceso decorte C5
Estudio de Casos de PPL
24
Restricciones:
Por cantidad pedida2 A1 + 3 B1 + B2 + B3 + B4 + 4 C1 + 2 C2 + 2 C3 + 2 C4 + C5 + C6 = 180
A2 + B2 + 2 B5 + B6 + C2 + 2 C5 + C6 + C7 = 200
A3 + B3 + B6 + C3 + C6 + 2 C8 + C9 = 150
A4 + B4 + C4 + C7 + C9 + 2 C10 = 80
Por disponibilidadB1 + B2 + B3 + B4 + B5 + B6 ≤ 115
C1 + C2 + C3 + C4 + C5 + C6 + C7 + C8 + C9 + C10 ≤ 80
Estudio de Casos de PPL
13
25
Por enteros no negativosA1, A2, A3, A4, B1, B2, B3, B4, B5, B6, C1, C2, C3, C4, C5, C6, C7, C8, C9,C10 enteros ≥ 0
Función objetivo:Minimizamos el desperdicioMin Z = 30 A2 + 20 A3 + 10 A4 + 30 B2 + 20 B3 + 10 B4 + 10 B5 + 30 C2 + 20
C3 + 10 C4 + 10 C5 + 40 C7 + 40 C8 + 30 C9 + 20 C10
Estudio de Casos de PPL
26
CASO 4: SELECCIÓN DE PROYECTOS
Una compañía tiene que escoger un conjunto deproyectos de la siguiente lista para un horizonte deplaneación de 3 años.
Su objetivo es maximizar el Valor Presente Neto Total,pero sin gastar más de lo presupuestado en cualquierade los 3 años.
Unidad monetaria: $ 1000.
Estudio de Casos de PPL
14
27
AÑO 1 AÑO 2 AÑO 3
1 30 80 10 80
2 40 70 50 96
3 50 60 70 88
4 60 60 10 92
5 70 40 10 76
6 20 30 90 87
7 20 50 20 78
8 25 80 60 81
9 40 20 15 94
PRESUPUESTO 300 320 220
PROYECTOREINVERSIONES VALOR
PRESENTE NETO
Estudio de Casos de PPL
28
Unidad monetaria: $ 1000.
Además se dan las siguientes condiciones:
a) La compañía debe escoger de todas maneras unode los proyectos 1 o 9, (o ambos).
b) Si el proyecto 6 es seleccionado, entonces elproyecto 8 también debe ser seleccionado.
c) Los proyectos 1 y 3 no deben ser seleccionados ala vez.
Estudio de Casos de PPL
15
29
SOLUCION:Variables de decisión:
Estudio de Casos de PPL
⎩⎨⎧= 01Pi si el Proyecto i es seleccionado
en caso contrario
i = 1, 2, 3, ...., 9
30
Restricciones:
Por presupuesto30 P1 + 40 P2 + 50 P3 + 60 P4 + 70 P5 + 20 P6 + 20 P7 + 25 P8 + 40 P9 ≤ 300
80 P1 + 70 P2 + 60 P3 + 60 P4 + 40 P5 + 30 P6 + 50 P7 + 80 P8 + 20 P9 ≤ 320
10 P1 + 50 P2 + 70 P3 + 10 P4 + 10 P5 + 90 P6 + 20 P7 + 60 P8 + 15 P9 ≤ 220
Por selección del proyecto 1 o 9P1 + P9 ≥ 1
Estudio de Casos de PPL
Por posible selección de los proyectos 6 y 8P6 - P8 ≤ 0
16
31
Por binariosP1, P2, P3, P4, P5, P6, P7, P8, P9 binarios {0,1}
Función objetivo:Maximizamos el Valor presente NetoMax Z = 80 P1 + 96 P2 + 88 P3 + 92 P4 + 76 P5 + 87 P6 + 78 P7 + 81 P8 + 94
P9
Estudio de Casos de PPL
Por la no selección de los proyectos 1 y 3 a la vezP1 + P3 ≤ 1
32
CASO 5: PLANIFICACION FINANCIERA
Un inversionista dispone de un capital de $ 100,000 ytrata de determinar en que actividades le será másconveniente invertir durante un horizonte deplanificación de 6 años.
Estudio de Casos de PPL
17
33
Plantee un modelo de Programación Lineal paradeterminar un plan óptimo de inversiones.
A 1, 2, 3, 4, 5 1.4 al cabo de 2 años
B 1, 2, 3, 4 1.6 al cabo de 3 años
C 6 1.3 al cabo de 1 año
D 2, 3 1.8 al cabo de 4 años
E 4 1.8 al final del año 6
RETORNO POR CADA DÓLAR INVERTIDO
ACTIVIDADDISPONIBLE A INICIO DEL
AÑO
Estudio de Casos de PPL
34
SOLUCION:Grafiquemos el plan de inversiones para la actividad A:
Estudio de Casos de PPL
año 1 año 2 año 3 año 4 año 5 año 6
A1 A2 A3 A4 A5
18
35
Grafiquemos el plan de inversiones para la actividad B:
Estudio de Casos de PPL
año 1 año 2 año 3 año 4 año 5 año 6
B1 B2 B3 B4
Grafiquemos el plan de inversiones para la actividad C:
año 1 año 2 año 3 año 4 año 5 año 6
C6
36
Grafiquemos el plan de inversiones para la actividad D:
Estudio de Casos de PPL
Grafiquemos el plan de inversiones para la actividad E:
año 1 año 2 año 3 año 4 año 5 año 6
D2 D3
año 1 año 2 año 3 año 4 año 5 año 6
E4
19
37
Variables de decisión:
Ai i = 1, 2, 3, 4, 5Bi i = 1, 2, 3, 4Ci i = 6
Ejemplo
B2: cantidad a invertir en la actividad B a inicio delaño 2.
Estudio de Casos de PPL
Di i = 2, 3Ei i = 4
38
Estudio de Casos de PPL
1 100,000 A1 + B1 S1
2 S1 A2 + B2 + D2 S2
3 S2 + 1.4 A1 A3 + B3 + D3 S3
4 S3 + 1.4 A2 + 1.6 B1 A4 + B4 + E4 S4
5 S4 + 1.4 A3 + 1.6 B2 A5 S5
6 S5 + 1.4 A4 + 1.6 B3 + 1.8 D2 C6 S6
CANTIDAD DISPONIBLE A INICIO DEL AÑO i
CANTIDAD A INVERTIR EN EL
AÑO i
CANTIDAD DISPONIBLE AL FINAL DEL AÑO i
AÑO i
20
39
Restricciones:
Por planes seleccionadosA1 + B1 + S1 = 100000
A2 + B2 + D2 + S2 – S1 = 0
A3 + B3 + D3 + S3 – S2 – 1.4 A1 = 0
A4 + B4 + E4 + S4 – S3 – 1.4 A2 – 1.6 B1 = 0
Estudio de Casos de PPL
Por no negatividadA1, A2, A3, A4, A5, B1, B2, B3, B4, C6, D2, D3, E4 ≥ 0
A5 + S5 – S4 – 1.4 A3 – 1.6 B2 = 0
C6 + S6 – S5 – 1.4 A4 – 1.6 B3 – 1.8 D2 = 0
40
Función objetivo:Maximizamos el retornoMax Z = S6 + 1.4 A5 + 1.6 B4 + 1.3 C6 + 1.8 D3 + 1.8 E4
Estudio de Casos de PPL
21
41
CASO 6: PROGRAMACION DE TURNOS DEVIGILANTES
Una compañía requiere la siguiente cantidad devigilantes durante las 24 horas de cada día.
2 - 6 86 - 10 610 - 14 714 - 18 1018 - 22 1222 - 2 9
HORAS CANTIDAD MINIMA
Estudio de Casos de PPL
42
Cada vigilante trabaja 8 horas/día en forma continua ycobra según los siguientes turnos:
Estudio de Casos de PPL
Plantee un modelo de Programación Lineal paraminimizar el costo de vigilantes necesarios para cubrirlos requerimientos.
TURNO PERIODO Costo-hora ($)1 6 - 14 102 14 - 22 123 22 - 6 18
22
43
SOLUCION:Grafiquemos el requerimiento de vigilantes:
Estudio de Casos de PPL
2 6 10 14 18 22 2
76 10 12 98
Los posibles ingresos de vigilantes:2 6 10 14 18 22 2
76 10 12 98V2 V6 V10 V14 V18 V22
44
Estudio de Casos de PPL
2 6 10 14 18 22 2
V2
V6
V10
V14
V18
V22
23
45
Variables de decisión:
V2, V6, V10, V14, V18, V22
Ejemplo
V10: número de vigilantes que entran a trabajar a las10.
Estudio de Casos de PPL
46
Restricciones:
Por cubrimientoV2 + V6 ≥ 6
V6 + V10 ≥ 7
V10 + V14 ≥ 10
V14 + V18 ≥ 12
Estudio de Casos de PPL
Por no negatividadV2, V6, V10, V14, V18, V22 enteros ≥ 0
V18 + V22 ≥ 9
V2 + V22 ≥ 8
24
47
Estudio de Casos de PPL
2 6 10 14 18 22 2
TURNO 3
V2 V6 V10 V14 V18 V22
TURNO 1 TURNO 2 TURNO 3
VIGILANTES TURNO 1 TURNO 2 TURNO 3 TOTALV2 40 72 112V6 80 80V10 40 48 88V14 96 96V18 48 72 120V22 144 144
48
Función objetivo:Minimizamos el pago por vigilantesMin Z = 112 V2 + 80 V6 + 88 V10 + 96 V14 + 120 V18 + 144 V22
Estudio de Casos de PPL
top related