Fundamentos de Investigacin de Operaciones.
17.10.2002
Programacin Lineal Entera.
1.
El consejo directivo de la General Wheels Co. Est considerando siete grandes inversiones de capital.
Estas inversiones difieren en la utilidad estimada a largo plazo (valor presente neto) que van a generar,
as como en la cantidad de capital requerido, como se muestra en la siguiente tabla (en millones de
dlares):
Oportunidad de inversin
1
2
3
4
5
6
7
Utilidad estimada
9
16
18
15
6
12
11
Capital requerido
25
40
45
35
15
30
25
La cantidad total de capital disponible para estas inversiones es de US$100.000.000. Las
oportunidades de inversin 1 y 2 son mutuamente excluyentes y tambin lo son la 3 y 4. Adems, no
pueden intentarse 3 ni 4 a menos que se decida invertir en 1 o en 2. No existen restricciones sobre las
oportunidades 5, 6 y 7. El objetivo es seleccionar la combinacin de inversiones de capital que
maximice la utilidad total estimada a largo plazo (valor presente neto). Formular un modelo de
programacin lineal binaria para este problema.
2.
Cada uno de los cuatro participantes de un equipo debe responder preguntas a un tpico particular.
Los cuatro tpicos son Geografa, Historia, Msica y Deportes. Los cuatro integrantes son Adams,
Bartleson, Crommelin y Dailey. Cada uno de ellos tiene diferentes habilidades. El rendimiento de cada
uno en cada tpico es el siguiente:
Tpico
Adams
Bartleson Crommelin
Dailey
Geografa
8
8
4
9
Historia
6
8
5
7
Msica
5
8
5
8
Deportes
8
9
7
4
Considerando que la escala es de 0 a 10 para evaluar los rendimientos, y que cada integrante puede
resolver un solo tpico, Cul es la asignacin ptima?. Formular un modelo de programacin lineal
binaria para este problema.
3.
Considere el siguiente problema de programacin lineal entera:
Max 33x+12y
s.a.
-x+2y 4
5x+2y 16
2x-y 4
x, y 0
x, y Z
Resolver este modelo grficamente. Comparar el valor de la funcin objetivo para la solucin ptima
con el que se obtiene redondeando la solucin ptima de programacin lineal a la solucin entera ms
cercana.
4.
Considere el siguiente problema de programacin lineal entera. Resolver aplicando el mtodo de
ramificacin y acotamiento:
Max 3x+2y
s.a.
3x+y 9
x+3y 7
-x+y 1
x, y 0
x, y Z
5.
Una joven pareja, Eva y adn, quieren dividir los trabajos principales del hogar (compra, cocina,
lavado de platos y lavado de ropa) entre los dos, de manera que cada uno tenga dos tareas, pero
tratando de que el tiempo total que utilicen en las labores hogareas se mantenga en un mnimo. Su
eficiencia en estas tareas difiere. El tiempo (en horas semanales) que necesita cada uno para realizar
cada tarea se da en la siguiente tabla:
Compra
Cocina
Lavado de platos
Lavado de ropa
3.2
3.9
7.4
6.8
4.1
4.5
2.5
2.7
Eva
Adn
a)
b)
6.
Formule un modelo de programacin lineal binaria para este problema.
Resuelva el modelo aplicando la tcnica de ramificacin y acotamiento.
Considere el modelo matemtico siguiente: Min f1(x1) + f2(x2)
Sujeto a las siguientes restricciones:
a)
b)
c)
d)
x1 3 x2 3
Al menos una de las siguientes desigualdades se debe cumplir:
2x1 + x2 7
x1 + x2 5
x1 + 2x2 7
x1 - x2 = 0 3 6
x1 0 y x2 0
7 + 5x1 , si x1 > 0
5 + 6x2 , si x2 > 0
f2(x2) =
0,
si x1=0
0,
si x2=0
Formule un modelo de programacin lineal entera mixta para este problema.
Donde
7.
f1(x1) =
Un grupo de amigos planea realizar un viaje desde la ciudad de Santiago a la ciudad de Los Angeles.
Disponen de un vehculo que, en promedio, les permite recorrer 10 kilmetros por cada litro de
combustible. El estanque de combustible del vehculo tiene una capacidad de 50 litros. El grupo
estima que cada vez que se detienen a cargar combustible gastan 200 pesos fijos y adicionales al costo
del combustible. Debido a las caractersticas geogrficas, las nicas rutas posibles entre pares de
ciudades y su distancia se presentan en la siguiente tabla:
Ruta
Santiago Rancagua
Rancagua San Fernando
San Fernando Curic
Curic Talca
Talca Linares
Linares Chilln
Chilln Los Angeles
Distancia
D12
D23
D34
D45
D56
D67
D78
El precio promedio del combustible en cada ciudad se entrega en la siguiente tabla:
Ruta
Santiago
Rancagua
San Fernando
Curic
Distancia
C1
C2
C3
C4
Talca
Linares
Chilln
Los Angeles
C5
C6
C7
C8
Formule un modelo de programacin lineal mixta que le permita al grupo determinar en qu
ciudades deben reabastacer combustible, en qu cantidades y cul es el costo total de viaje, de
manera que este costo sea mnimo, considerando que al partir de Santiago el estanque est vaco.
Defina claramente las variables, funcin objetivo y restricciones.
8.
Una determinada aerolnea, con centro en Santiago, est diseando un nuevo sistema de atencin a
pasajeros que realicen viajes a cuatro destinos especficos: Antofagasta, Temuco, Puerto Montt y Punta
Arenas. Para eso consta de tres tipos de aviones, los que difieren en capacidad, rendimiento y costos,
segn se muestra en la siguiente tabla:
Tipo de
Costo de Operacin por viaje en la ruta a
Avin
Antofagasta
Temuco
Puerto Montt
Punta Arenas
1
2
3
1000
800
600
1100
900
800
1200
1000
800
1500
1000
900
Histricamente para esta poca se tiene una demanda mnima diaria de 90 pasajeros a Antofagasta,
100 a Temuco, 200 a Puerto Montt y de 120 pasajeros a Punta Arenas. Adems, lo que la aerolnea
recibe por pasajero a cada lugar es de 40 si el destino es Antofagasta, 40 si el destino es Temuco, 45 si
el destino es Puerto Montt y 70 si se viaja a Punta Arenas.
Los datos tanto de operacin y de disponibilidad que actualmente tiene la aerolnea son:
Tipo de Avin
Capacidad (pasajeros)
Nmero de Aviones
1
2
3
50
30
20
5
8
10
Finalmente, se ha dispuesto (de preferencia, pero no obligatoriamente) atender ms de una ruta por
cada tipo de avin, ante lo cual se ha planteado las siguientes condiciones al diseo del sistema de
pasajeros:
Tipo de
Nmero mximo de viajes diarios a
Avin
Antofagasta
Temuco
Puerto Montt
Punta Arenas
1
2
3
3
4
5
2
3
5
2
3
4
1
2
2
Determinar el modelo de programacin lineal que permita optimizar la asignacin de los aviones a las
distintas rutas.
9.
Una empresa multinacional est organizando un congreso en el que expondrn especialistas de
diversas reas de diferentes pases del mundo. Dichos especialistas hablan en su mayora Ingls y
Francs, sin embargo, tambin hay quienes hablan slo Portugus y Alemn, 2 hablan Espaol. Se
est planificando tener 3 sesiones en paralelo por da. Para esto existe un auditorio principal y dos
salas de conferencias. Cada uno posee dos cabinas para los traductores, quienes deben traducir a dos
idiomas los respectivos temas. La empresa que efectuar el trabajo de traduccin cuenta con 10
traductores, los cuales son trilinges, obviamente el idioma comn es el espaol, como se indica.
Categora 1
Hablan
Cantidad
Ingls, Francs, Espaol
Categora
Categora
Categora
Categora
2
3
4
5
Ingls, Portugus, Espaol
Alemn, Portugus, Espaol
Francs, Alemn, Espaol
Francs, Portugus, Espaol
3
2
1
1
Habr un total de 9 conferencias en 3 sesiones. La planificacin es la siguiente:
1 Sesin
2 Sesin
3 Sesin
Auditorio
Sala 1
Sala 2
Charlista 1
Charlista 4
Charlista 7
Charlista 2
Charlista 5
Charlista 8
Charlista 3
Charlista 6
Charlista 9
Se sabe que el charlista 1 habla Ingls, el 2 Francs, el 3 Alemn, el 4 Portugus, el 5 Ingls, el 6
Espaol, el 7 Espaol, el 8 Francs y el 9 Ingls.
Formule el problema de Programacin Lineal asociado para determinar la mejor distribucin de los
traductores.
Nota: Maneje los supuestos necesarios.
10. Un taller produce 2 artculos. Compromisos contrados por el taller requieren un mnimo de
produccin de 50 unidades del artculo 1 y 100 unidades del articulo 2. Estudios de mercado estiman
una demanda mxima por el producto 1 de 80 unidades y 120 unidades por el producto 2. El ingreso
unitario por la venta de cada artculo de tipo 1 es de $1.000 y $800 por cada artculo de tipo 2. Cada
artculo es producido mezclando 3 materias primas. La cantidad de cada materia prima requerida
para producir una unidad de cada artculo es presentada en la tabla 1.
11.
Materia Prima
Artculo
1
2
3
1
5
3
15
2
4
8
9
Tabla 1: Requerimientos de materias primas.
El taller tiene dos ofertas de materias primas. La cantidad de unidades de cada materia prima y el
costo total de cada oferta, incluyendo todas las unidades de todas las materias primas, se presenta en
la tabla 2.
Materia prima
Oferta
1
2
3
Costo
1
40
30
60
2.000.000
2
45
35
50
1.500.000
Tabla 2: Ofertas de materias primas.
Formule un modelo de programacin lineal mixta que permita determinar cul (es) oferta(s) aceptar y,
aceptando la(s) mejor(es) oferta(s), cules seran los niveles de produccin de cada artculo que
optimizaran la operacin del taller. Defina claramente variables, funcin objetivo y restricciones.
11. Considere el problema de distribucin de artculos desde tres centros productores a dos centros
consumidores. Los artculos pueden ser transportados entre cada centro productor y cada centro
consumidor considerando dos rutas posibles. La utilizacin de cada ruta tiene asociada un costo fijo
que es independiente de la cantidad de artculos transportados por esa ruta. La siguiente tabla
presenta las capacidades de produccin, las demandas estimadas, el costo fijo por la utilizacin de
cada ruta y el costo de transporte de un artculo desde cada entro productor a cada centro
consumidor.
Destino
Origen
1
2
3
Demanda
Ruta
a
b
a
b
a
b
1
2
Costo Fijo Costo Unitario Costo Fijo
10
3
12
20
2
24
15
5
16
25
4
32
30
7
18
35
6
36
300
Costo Unitario
9
8
12
10
16
14
500
Oferta
200
400
600
Formule un modelo de programacin lineal mixta que permita determinar la cantidad a transportar
por cada ruta que minimiza el costo total satisfaciendo todas las demandas. Defina claramente
variables, funcin objetivo y restricciones.
12. A una compaa de inversiones se le presentan cinco posibles inversiones, cuyos gastos y
rendimientos netos ( en miles de unidades monetarias ) se presentan en la tabla.
El capital total disponible para invertir es de $25.000. Si la cartera de inversiones de la compaa
incluye la inversin 2, deber seleccionar tambin la inversin 4. Por otra parte, las inversiones 2 y 3
son mutuamente excluyentes.
Inversin
Gastos
Rendimientos 32
21
24
15
16
Netos
Gasto y rendimiento neto de cada inversin.
Formule un modelo de programacin lineal binaria que permita determinar la combinacin de
inversiones que maximizan las utilidades de la compaa. Defina claramente variables, funcin
objetivo y restricciones.
13. En un problema de perforacin de pozos petroleros existen dos sitios de perforacin atractivos para
alcanzar cuatro posibles pozos de petrleo. El costo de preparacin para cada sitio i y el costo de
perforar la ruta desde el sitio i para llegar al posible pozo de petrleo j ( i = 1,2; j = 1, 2, 3, 4) se
presentan en la tabla. El objetivo es determinar los sitios a preparar y la ruta a perforar para llegar a
cada pozo de manera tal que el costo total se minimice.
Costo de perforacin para llegar a los pozos
Sitio
1
2
2
4
1
8
6
3
Costos de preparacin y perforacin.
4
5
1
Costo de
preparacin
5
6
Formule un modelo de programacin lineal binaria que permita determinar en qu sitios se debe
perforar de manera tal de minimizar el costo total asegurando que todos los posibles pozos sean
explorados. Defina claramente variables, funcin objetivo y restricciones.
14. El problema de asignacin considera la determinacin de la mejor distribucin 1 - 1 de un conjunto
de recursos para satisfacer un conjunto de demandas. Suponga que se dispone de 6 recursos, que
existen 4 demandas y que la ganancia por la asignacin de cada recurso "i" a cada demanda "j" puede
ser estimada como Gij.
(a) Formule un modelo de programacin lineal mixta que permita determinar la asignacin que
maximiza las ganancias.
(b) Agregue a su modelo las restricciones necesarias para representar las condiciones siguientes:
i.
El recurso 1 debe ser utilizado.
ii.
De los recursos 2 y 5, al menos uno debe ser utilizado.
iii.
La demanda 2 debe ser satisfecha con los recursos 2 5.
15. Grave City est considerando la construccin de nuevas poblaciones y la localizacin de nuevas
estaciones de polica para atacar problemas de criminalidad. Cada nueva poblacin podra tener un
mximo de 10.000 habitantes. La construccin de cada poblacin i tiene un costo de K i y la
construccin de la estacin de polica j tiene un costo de k j . Suponga que se debe ubicar un total de
45.000 habitantes estando cada uno de ellos protegido por al menos una estacin de polica. Las
estaciones de polica que se estn considerando, junto con las reas que cubriran, se presentan a
continuacin:
Sitios potenciales
para estaciones
A
B
C
D
E
F
G
Areas cubiertas
1, 5, 7
1, 2, 5, 7
1, 3, 5
2, 4, 5
3, 4, 6
4, 5, 6
1, 5, 6, 7
Formule un modelo de programacin lineal mixta que permita determinar donde construir las poblaciones
y las estaciones de polica satisfaciendo todas las necesidades.
