ejercicios de investigacion operativa
DESCRIPTION
Ejercicios resueltos de investigación operativa para desarrollar y practicar a su gusto suerte.TRANSCRIPT
-
www.investigaciondeoperaciones.net
Ejercicios Propuestos de Investigacin de operaciones Resueltos
1. Con motivo del 5 centenario del nacimiento de un clebre pintor, un
importante museo ha decidido restaurar cinco de sus obras, para lo cual ha
contratado tres equipos de restauracin. Cada equipo ha presentado el
presupuesto de restauracin para cada una de las obras, como se recoge en
el siguiente cuadro, en miles de
euros.
O1 O2 O3 O4 O5
R1 60 -- 90 -- 120
R2 70 90 80 100 80
R3 -- 70 120 90 100
(Donde -- significa que dicho equipo no restaurar en ningn caso la obra
correspondiente)
E l primer equipo restaurador est compuesto por seis personas, el segundo por
cuatro y el tercero por tres. En la restauracin de cada una de las obras son
necesarias dos personas. Cada persona de un equipo slo restaura una obra.
a) A qu tabla se debe aplicar el Mtodo Hngaro para realizar las cinco
restauraciones, con el menor coste posible, teniendo en cuenta que cada una
de ellas debe ser realizada por un nico equipo restaurador, y que los tres
equipos deben participar en dichas restauraciones?
b) Dado que el coste de restauracin de las cinco obras es muy elevado, la
directiva del museo decide restaurar nicamente tres, asignando una nica
obra a cada equipo. Determinar, aplicando el Mtodo Hngaro, todas las
posibles asignaciones que minimicen el coste total.
-
www.investigaciondeoperaciones.net
Solucin:
a) Aplicaremos el Mtodo Hngaro a la siguiente tabla:
O1 O2 O3 O4 O5 F
R1 60 M 90 M 120 0
R1 60 M 90 M 120 0
R1 60 M 90 M 120 0
R2 70 90 80 100 80 0
R2 70 90 80 100 80 0
R3 M 70 120 90 100 M
Con M positivo suficientemente grande.
b) Aplicamos el Mtodo Hngaro a la siguiente tabla:
O1 O2 O3 O4 O5
R1 60 M 90 M 120
R2 70 90 80 100 80
R3 M 70 120 90 100
F1 0 0 0 0 0
F2 0 0 0 0 0
Con M positivo suficientemente grande.
-
www.investigaciondeoperaciones.net
-
www.investigaciondeoperaciones.net
2. La compaa Ordenata S.A. desea planificar el ensamblaje de dos nuevos
modelos de ordenador el Core Duo KS500 y el Core Duo KS600. Ambos
modelos precisan del mismo tipo de carcasa y lector ptico. En el modelo KS500
se ensambla la carcasa con 2 lectores pticos. En el modelo KS600 se ensambla
la carcasa con un lector ptico y adems se aade un lector de tarjetas. Se
dispone semanalmente de 1000 lectores pticos, 500 lectores de tarjetas y de
600 carcasas. El ensamblaje de un KS500 lleva una 1 hora de trabajo y
proporciona un beneficio
de 200 euros y el del KS600 lleva 1.5 horas de trabajo y su beneficio es de 500
euros.
Teniendo en cuenta las restricciones anteriores, el director de la compaa
desea alcanzar las siguientes metas en orden de prioridad:
Prioridad 1. Producir semanalmente al menos 200 ordenadores KS500.
Prioridad 2. Ensamblar al menos 500 ordenadores en total a la semana.
Prioridad 3. Igualar el nmero de horas totales de trabajo dedicadas al
ensamblaje de los dos tipos de ordenador.
Prioridad 4. Obtener un beneficio semanal de al menos 250000 euros.
Obtener e interpretar la solucin ptima del problema relajado, planteando
y resolviendo grficamente cada una de las metas.
Solucin:
Definimos las variables de decisin siguientes:
x1 = unidades ensambladas semanalmente del ordenador Core Duo KS500
x2 = unidades ensambladas semanalmente del ordenador Core Duo KS600
La modelizacin queda como sigue:
Min L( y1 , y2 , y3 y3 , y4 )
-
www.investigaciondeoperaciones.net
2 x1 x2 1000 (1)
x2 500 (2)
x1 x2 600 (3)
x1 y1 y1 200 (4)
s.a x1 x2 y2 y2 500 (5)
x1 1.5x2 y3 y3 0 (6)
200 x1 500x2 y4 y4 250000 (7)
x1 0, x2 0 y enteras
yi 0, yi 0 i 1, 2, 3,4
-
www.investigaciondeoperaciones.net
-
www.investigaciondeoperaciones.net
-
www.investigaciondeoperaciones.net
3. Roperos S.AC produce dos tipos de roperos: roperos modelo A y, roperos modelo
B.lo mximo a vender de escritorios modelo A son 600 unidades y modelo B son
400 unidades .Fabricar un escritorio modelo A requiere 1 hora y fabricar un
escritorio modelo B requiere 2 horas. la capacidad de produccin es 1300 horas en
total por los dos modelos, cabe resaltar que no es posible trabajar horas extras.
Cada ropero modelo A entrega una utilidad de $15.Todo lo que se fabrica se
vende.
La gerencia, adems, ha establecido las siguientes metas
Meta 1: Alcanzar una utilidad semanal por lo menos de $11000.
Meta 2: Que no exista capacidad de produccin ociosa.
Meta 3: Que se produzcan 600 de 2 cajones.
Meta 4: Que se produzcan 400 escritorios de 3 cajones.
La meta 1 es de primera prioridad; la meta 2, de segunda; la 3, de tercera y la meta 4 tiene
la ltima prioridad de cumplimiento.
1) Defina las variables de decisin y formule el modelo de programacin lineal por
metas correspondiente.
2) Presentar un informe administrativo de la solucin ptima, indicando que metas se
cumplen o no, es necesario realizar la grfica.
Solucin:
Parte 1:
X: Numero de roperos Modelos A a producir
Y: Numero de roperos Modelos B a producir
Metas:
1)Min Z=P1(d1)
10X+15Y+d1-e1=11000(>=)
2) Min Z=P2(d2)
1X+2Y+d1=1300(=)
3) Min Z=P3(d3)
1X+d3=600(=)
-
www.investigaciondeoperaciones.net
4) Min Z=P4(d4)
Y+d4=400(=)
NO HAY RESTRICCIONES DURAS
Objetivo:
Min Z=P1d1+P2+d2+P3d3+P4d4
Parte 2:
Grfica:
Puntos de interseccion:
A(500,400)
B(600,350)
C(600,333.33)
-
www.investigaciondeoperaciones.net
Metas:
1) P1d1 =La Regin ABC Cumple
2) P2d2 =Recta AB
3) P3d3 =Punto B
4) P4d4 =No Cumple
Se Toma el punto B(600,350)
Metas
X=600
Y=350 Cumplen?
1
d1=0
e1=250 si
2 d2=0 si
3 d3=0 si
4 d4=50 NO
Se debe producir 600 roperos A y 350 roperos B Para que se llegue a una utilidad de
$ 11,250, Donde se cumplen las metas 1,2 y 3.
4. En un hospital comarcal se pueden realizar operaciones de rin, de corazn y
de vescula. Por problemas de personal cada da se realizan operaciones como
mucho de dos clases. Debido al gran nmero de operaciones pendientes se deben
realizar al menos tantas operaciones de vescula como de rin. Por otra parte, no
se pueden realizar ms de 50 operaciones de vescula diarias. Cada
operacin de rin requiere la presencia de dos mdicos y se realiza en una
hora. Las operaciones de corazn requieren 3 mdicos y se realizan en 5 horas.
Cada operacin de vescula slo requiere un mdico y se realiza en una hora Para
estos tipos de operaciones el hospital tiene asignados 20 mdicos y cuenta con 60
horas diarias de quirfano.
-
www.investigaciondeoperaciones.net
a) (6 puntos) Modelizar el problema como un problema de programacin lineal
entera para maximizar el nmero de operaciones diarias.
b) (4 puntos) El hospital recibe una subvencin y se plantea o bien modernizar el
hospital y, as, poder realizar tambin operaciones de cataratas, o bien contratar
dos nuevos mdicos. Las operaciones de cataratas requieren un mdico y una
hora de quirfano, adems, si se opera de cataratas se deben realizar como
mnimo 5 operaciones al da y no ms de 10. Modelizar el problema como un
problema de programacin lineal entera para maximizar el nmero de
operaciones.
Solucin:
a) Definimos las variables de decisin siguientes:
x1 = nmero de operaciones de rin al da
x2 = nmero de operaciones de corazn al da
x3 = nmero de operaciones de vescula al da
1 si se realizan operaciones de rin
y1 0 en caso contrario
1 si se realizan operaciones de corazn
y2 0 en caso contrario
-
www.investigaciondeoperaciones.net
2 2
1 2 3
1 si se realizan operaciones de vescula
y3 0 en caso contrario
La modelizacin queda como sigue:
Max ( x1 x2 x3 )
2 x1 3x2 x3 20
s.a
x1 5x2 x3 60
y y y 2
x1 x3
x1 My1
x My
x3 50 y3
xi 0
i 1, 2, 3 y enteras
yi 0, 1 i 1, 2, 3
Con M positivo suficientemente grande.
b) Sea definen adems de las variables del apartado anterior:
1 si se decide realizar operaciones de cataratas
z
0 en caso contrario
x4 = nmero de operaciones de cataratas al da
La modelizacin queda como sigue:
-
www.investigaciondeoperaciones.net
2 2
1 2 3
Max ( x1 x2 x3 x4 )
2x1 3x2 x3 x4 20 2(1 z)
s.a
x1 5x2 x3 x4 60
y y y z 2
x1 x3
x1 My1
x My
x 50 y
3 3
5z x4 10z
xi 0 i 1, 2, 3,4 y entera
z 0, 1
Con M positivo suficientemente grande.
0, 1 i 1, 2
-
www.investigaciondeoperaciones.net
5. Un ayuntamiento tiene previsto construir cuatro instalaciones deportivas
diferentes dentro del municipio. El ayuntamiento se compone de cuatro distritos
A, B, C y D y quiere asegurar la construccin de un polideportivo en los
distritos ms grandes: A y B. Adems, cabra la posibilidad de construir
dos polideportivos en el distrito B. La siguiente tabla muestra el nmero de
usuarios semanales (en centenas) que se estiman para cada tipo de
instalacin deportiva
segn en el distrito en que se construya.
Polideportivo
Distrito
P1
P2
P3
P4
A 12 14 17 19
B 16 19 24 17
C 10 12 18 15
D 13 9 20 17
Resolver mediante el Mtodo Hngaro el problema de dnde se deben construir
los
4 polideportivos si el ayuntamiento desea maximizar el nmero de
usuarios semanales.
Solucin:
-
www.investigaciondeoperaciones.net
Aplicamos el Mtodo Hngaro a la siguiente tabla:
P1 P2 P3 P4 F1
A -12 -14 -17 -19 M
B -16 -19 -24 -17 M
B -16 -19 -24 -17 0
C -10 -12 -18 -15 0
D -13 -9 -20 -17 0
Con M positivo suficientemente grande.
P1 P2 P3 P4 F1
A -12 -14 -17 -19 M
B -16 -19 -24 -17 M
B -16 -19 -24 -17 0
C -10 -12 -18 -15 0
D -13 -9 -20 -17 0
+16 +19 +24 +19
Con M positivo suficientemente grande.
P1 P2 P3 P4 F1
A 4 5 7 0 M
B 0 0 0 2 M
B 0 0 0 2 0
C 6 7 6 4 0
D 3 10 4 2 0
Con M positivo suficientemente grande.
-
www.investigaciondeoperaciones.net
C
o
n
M positivo suficientemente grande.
+3
+3
P1 P2 P3 P4 F1
A 4 5 7 0 M -3
B 0 0 0 2 M
B 0 0 0 2 0
C 6 7 6 4 0 -3
D 3 10 4 2 0 -3
-
www.investigaciondeoperaciones.net
P1 P2 P3 P4 F1
A 1 2 4 0 M
B 0 0 0 5 M
B 0 0 0 5 3
C 3 4 3 4 0
D 0 7 1 2 0
Con M positivo suficientemente grande.
Se obtiene la siguiente asignacin ptima: A Polideportivo 4, B
Polideportivos 2 y 3, D Polideportivo 1.
Valor ptimo, 7500 usuarios semanales.
-
www.investigaciondeoperaciones.net
6. Una empresa realiza dos tipos de bombones, de calidad excelente y de
primera calidad. Para producirlos utiliza cacao y almendras, de los que dispone
semanalmente de 48 kilos y 4.5 kilos respectivamente. Para realizar una caja de
bombones de calidad excelente se necesita 600 gramos de cacao y 50 gramos
de almendras mientras que para una caja de primera calidad se necesita 400
gramos de cacao y 50 gramos de almendras. Por cada caja de calidad excelente
se obtiene un beneficio de 70 y por cada una de primera calidad de 40 y
adems se vende sin problemas todo lo que se produce.
a) Determinar, resolviendo el problema relajado, las producciones semanales
eficientes de cajas de bombones de modo que la empresa maximice sus
beneficios y el volumen de ventas.
b) Si la empresa considera cada venta como 10 de beneficio, modelizar el
problema relajado correspondiente.
c) Si la empresa necesita 7 horas de produccin para obtener una caja de calidad
excelente y 4 horas para una caja de primera calidad, determinar al menos
dos producciones semanales eficientes del problema relajado de modo que la
empresa maximice sus beneficios, y el volumen de ventas y minimice las
horas de produccin.
Solucin:
a) Definimos las variables de decisin siguientes:
x1 = cajas de bombones de calidad excelente producidas semanalmente
x2 = cajas de bombones de primera calidad producidas semanalmente
La modelizacin queda como sigue:
-
www.investigaciondeoperaciones.net
Max (70x1 40 x2 ,
x1 x2 )
s.a
600x1 400x2 48000
50 x1 50 x2 4500
x1 0, x2 0 y enteras
Resolveremos el problema relajado:
Max (70x1 40 x2 ,
x1 x2 )
s.a
600x1 400x2 48000 (1)
50 x1 50 x2 4500 (2)
x1 0, x2 0
-
www.investigaciondeoperaciones.net
Vrtices
X
Vrtices
f( X )
(0, 0)
(80, 0)
(60, 30)
(0, 90)
(0, 0)
(5600, 80)
(5400, 90)
(3600, 90)
Soluciones eficientes: 80, 060, 30
-
www.investigaciondeoperaciones.net
b) La modelizacin queda como sigue:
Max
70x1 40x2 10 x1 x2
c) La modelizacin queda como sigue:
Max 70x1 40x2 , x1 x2 , 7 x1 4x2
s.a X
Por el teorema de Zadeh si damos pesos positivos a las funciones objetivo, la solucin
ptima del problema ponderado ser una solucin eficiente del problema multiobjetivo
Asignando: l1 =1, l2 =1, l3 =10 el modelo lineal ponderado tiene como
Soluciones ptimas(0,90)(60,30) . Estas sern soluciones eficientes del modelo multiobjetivo.