7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
1/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
PROBLEMAS DE INVESTIGACION DE OPERACIONES
1. Una compaa petrolera quiere conectar distintas ciudades, cuyas distancias (km) aparece en
el cuadro siguiente, con tuberas que vayan directamente entre las ciudades. Cul es el
mnimo de kilmetros necesarios de tubera?
SOLUCION: Utilizando el algoritmo para hallar al rbol de mnima expansin, luego estos
resultados se contrastarn con los resultados del software:
{} {} Tomamos el arco que tiene menor distancia en todos lo
posibles arcos formado por los 2 conjuntos.
Arco de mnima distancia es ( )
{ } {} Arco de mnima distancia es ( )
{} {} Arco de minima distancia es ( )
{} {} Arco de minima distancia es ( )
{} { } Arco de minima distancia es ( )
{} {} Arco de minima distancia es ( )
D M N O P W
B 670 758 427 581 211 369
D 361 252 132 492 680
M 332 493 690 759
N 357 394 431
O 391 650
P 521
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
2/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
Entonces tenemos como resultado un rbol de mnima expansin cuya longitud es de: L = 1687
Tambin podemos comprobar este resultado en un programa que sigue el mismo algoritmo pero
estos resultados se pueden conseguir de manera inmediata ordenando al software:
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
3/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
2. Para irrigar las tierras bajas, el agua se transporta a travs de una red de acueductos desde la
presa hasta el valle. A continuacin se muestra una red en la que los arcos representa
acueductos y el nmero en cada arco representa el caudal mximo permitido en kilotoneladas
por hora. Se desea determinar el caudal mximo de la gran presa a las tierras bajas.
a) Formlelo como un modelo de programacin lineal
b) Resuelva el problema aplicando el algoritmo respectivo
SOLUCION: Bueno formulamos este problema de flujo mximo como uno de programacin lineal
para ello primero definimos las siguientes variables:
Presa
100
60 80
Valle
50307050
80 40
90
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
4/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
La solucin que proporciona el LINDO 6.5 es F = 150
Ahora procederemos a resolverlo con los algoritmos aprendidos en clase:
Tomamos como primer paso etiquetar el primer nodo con [ ].
Seleccionamos las ramas con mayores
flujos y luego hacemos la siguienteseleccin:
{ }
Entonces las nuevas ramas del
recorrido tienen los siguientes
valores: ( )
{ }
{ }
{ }
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
5/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
Vemos que en esta parte del
problema ya no se puede avanzar por lo
tanto nos quedamos con los dems
el flujo mximo q pasa por la red es:
DE A inicio final flujo
1 2 100 0 100
1 3 80 30 50
2 3 50 10 40
2 4 60 0 60
3 4 70 20 50
3 5 40 0 40
4 5 30 0 30
4 6 80 0 80
5 4 50 50 0
5 6 90 20 70
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
6/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
3. Un banco pronto empezar a conectar terminales de computadora en cada una de las
sucursales, con la computadora de su oficina principal, usando lneas telefnicas especiales
con dispositivos de telecomunicaciones.
La lnea telefnica que emana de una sucursal no necesita conectarse directamente a la
oficina principal; puede conectarse indirectamente, conectndola con otra sucursal que est
conectado (directa o indirectamente) con la oficina principal. El nico requerimiento es que
todas las sucursales estn conectadas por alguna ruta con la oficina principal.
La carga para las lneas telefnicas especiales es directamente proporcional al nmero de
millas involucradas, en donde la distancia (en millas) entre cada par de oficinas es:
DISTANCIA ENTRE PARES DE OFICINAS
Principal S1 S2 S3 S4 S5
Oficina Principal
Sucursal 1
Sucursal 2
Sucursal 3
Sucursal 4
Sucursal 5
----
160
270
115
70
190
160
----
310
80
220
50
270
310
----
175
120
215
115
80
175
----
140
240
70
220
120
140
----
100
190
50
215
240
100
----
SOLUCION:
Utilizando el algoritmo para hallar al rbol de
mnima expansin, luego estos resultados se
contrastarn con los resultados del software:
{}
{ }Tomamos el arco que tiene menor distancia en todos lo
posibles arcos formado por los 2 conjuntos.
Arco de mnima distancia es ( )
{ } { } Arco de mnima distancia es ( )
{ } { } Arco de minima distancia es ( )
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
7/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
{ } { } Arco de minima distancia es ( )
{ } {} Arco de minima distancia es ( )
Longitud del rbol de mnima Expansin L = 420 lo cual se puede comprobar con el TORA.
4. JARH tiene una gran refinera localizada en N. La gasolina refinada es enviada de all a tanques
de almacenamiento en P a travs de una red de oleoductos con estaciones de bombeo en S, E,
T, B y A. El oleoducto est construido en segmentos que conectan parejas de estas ciudades. A
lo largo de cada segmento existe un nmero mximo conocido de miles de galones por hora
que pueden enviarse. Estos segmentos y sus respectivas capacidades en miles de galones por
hora son:
En P se espera un aumento en la conduccin en los prximos meses de verano. Antes de
incrementar la tasa de produccin de la refinera, la administracin de JARH desea convencerel nmero mximo de miles de galones de gasolina por hora que pueden enviarse a travs de
la red de oleoductos a los tanques de almacenamiento de P.
De A Capacidad
N S 150
S T 125
T P 130
N B 80
S B 60
B E 100
E A 75
E T 50
A P 90
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
8/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
SOLUCION:
El problema mostrado se puede
representar como una red de oleoductos
que los arcos representen las distancias
que estn de estaciones de bombeo a otraestacin:
{}
{}
{}
DE A inicio final flujo
N S 150 20 130
N B 80 5 75
S T 125 0 125
B E 100 20 80
T P 130 0 130
E T 50 40 10
E A 75 0 75
A P 90 15 75
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
9/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
Solucin realizada en el TORA
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
10/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
5. Las eliminatorias para el mundial se acercan y la seleccin peruana te necesita! Tenemos un
esquema del equipo con 12 posiciones, una por cada jugador (el portero es el nmero 1) ms
una para la portera contraria (que es el nmero 12). Para cada par de jugadores (a, b),
tenemos la probabilidad, P[a, b] (0, 1), de que un pase desde a hasta b salga bien, es decir,
que no lo intercepte el equipo contrario. La matriz no es simtrica, y P[a, 12] indica la
probabilidad de que a marque un gol al patear.
A partir de esas probabilidades bsicas, se puede calcular la probabilidad de una secuencia de
pases, mediante el producto.
La probabilidad de que la secuencia de pases a b c salga bien ser: P[a, b]*P[b, c], y
as sucesivamente. Una estrategia de juego es una secuencia de pases que empieza en nuestro
portero y acaba en gol en la portera contraria.
Utilice algn algoritmo eficiente que encuentre la estrategia de juego ptima, es decir, la
secuencia de pases entre 1 y 12 que maximice la probabilidad de salir bien.
Aplicar el algoritmo, indicando la estrategia ptima y la probabilidad asociada.
SOLUCION:
Modelo de redes, formularemos como un problema de ruta corta aplicando una transformacin
logartmica que convierta la probabilidad en la suma de logaritmos de probabilidades; es decir
P1K = P1 x P2 x P3 x P4 x x Pk es la probabilidad de no ser detenido entonces
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
11/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
Como queremos la maximizacin de como 0 la maximizacin a su vez equivale a la
minimizacin de .
Transformando cada probabilidad a logartmica
Nodo 1 2 - = 0.04576
Nodo 1 3 - = 0.15490Nodo 2 3 - = 0.22185
Nodo 2 5 - = 1.00000
Nodo 3 4 - = 0.30103
Nodo 3 6 - = 1.00000
Nodo 3 12 - = 0.69897
Nodo 4 1 - = 0.04575
Nodo 4 3 - = 0
Nodo 4 6 - = 0.09691
Nodo 5 12 - = 0.15490
Nodo 6 5 - = 0.52289Nodo 6 12 - = 0.22185
Con el ltimo grafo podemos usar el INVOP para determinar la ruta ms corta entre el jugador 1 y
la portera contraria que es el nmero 12.
Si - = X
= = 0.168
sera la probabilidad ms alta
y el camino seria
1 3 4 6 12
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
12/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
6. Un taller de tractores se encuentra atendido nicamente por un empleado.
Supongamos que el cuadro de llegadas se corresponde a un proceso de Poisson, de modo que
los tiempos de servicio siguen distribuciones exponenciales. Consideremos que, despus de
observar la evolucin del taller, se estima que la tasa de llegada es de 10 vehculos por da y
que el tiempo de servicio es de 1 hora. Suponiendo que el empleado arregla los tractores por
estricto orden de llegadas y tomando una jornada laboral de 12 horas, se pide contestar a lo
siguiente:
a) Probabilidad de que al llevar el tractor a reparar no lo pueda arreglar en el momento.
b) Nmero medio de tractores en espera a ser reparados, en estado estacionario
c) Tiempo medio que debe esperar cada tractor para ser reparado.
d) Tiempo medio que un vehculo est en el sistema.
SOLUCION:
Datos:
10.vehculos/jornada
12 vehculos / jornada.
0.833
a) Probabilidad de que al llevar el tractor a reparar no lo pueda arreglar en el momento. Porcomplemento: (1- P0) (Probabilidad que sea arreglado en el momento) Siendo: P0 = (1- )
1- (1- ) = = 0.833
b) Nmero medio de tractores en espera a ser reparados, en estado estacionario
166.4
)1012(12
1022
Tractores
c) Tiempo medio que debe esperar cada tractor para ser reparado.
=
()= 0.416 x 12 horas = 4.992 horas
d) Tiempo medio que un vehculo est en el sistema. Siendo: Tiempo en el sistema= tiempode espera + tiempo de servicio
1S
W =
=
= 6 horas
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
13/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
7. Con rubes y zafiros la joyera Coronas fabrica dos tipos de anillos. Un anillo tipo 1 requiere 2
rubes, 3 zafiros y 1 hora de trabajo de un joyero. Un anillo tipo 2 requiere 3 rubes, 2 zafiros y
2 horas de trabajo de un joyero. Cada anillo tipo 1 se vende a 400 , y cada anillo tipo 2 a
500 Se pueden vender todos los anillos producidos por Coronas. Actualmente, Coronas
dispone de 100 rubes, 120 zafiros y 70 horas de trabajo de un joyero. Se pueden comprar msrubes a un costo de 100 el rub. La demanda del mercado requiere una produccin de por
lo menos 20 anillos tipo 1, y por lo menos 25 anillos tipo 2. Coronas desea maximizar la
ganancia.
Resuelva este problema con la ayuda de un software, por ejemplo LINDO, y conteste a las
siguientes cuestiones:
a) Formularlo como uno de programacin lineal.
b) Estandarizar el programa lineal.
c) Suponga que cada rub cuesta 190 , en lugar de 100 . Todava comprara Coronas
rubes? Cul sera la nueva solucin ptima para el problema?d) Suponga que Coronas solamente tuviera que producir 23 anillos tipo 2. Cul sera la
utilidad de Coronas ahora?
e) Cul es la mxima cantidad que tendra que estar dispuesto a pagar Coronas por otra
hora de trabajo de un joyero?
f) Cul es la mxima cantidad que tendra que estar dispuesto a pagar Coronas por otro
zafiro?
SOLUCION:
a) Formulando como una programacin Lineal la funcin objetivo y las restricciones son:
Definiendo las variables:
Las ganancias es la funcin a optimizar en este caso a maximizar.
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
14/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
Entonces la cantidad de rubs q se utilizaran ser 100 + donde representa la parte adicional
de lo que dispone.
b) la formulacin se puede estandarizar ingresando variables artificiales:
RESOLVIENDO EN PROBLEMA EN LINDO 6.5
LP OPTIMUM FOUND AT STEP 5
OBJECTIVE FUNCTION VALUE
1) 19000.00
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 25.000000 0.000000
X3 15.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 100.000000
3) 10.000000 0.000000
4) 0.000000 200.000000
5) 0.000000 0.000000
6) 0.000000 -200.000000
NO. ITERATIONS= 5
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
15/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 400.000000 INFINITY 100.000000
X2 500.000000 200.000000 INFINITY
X3 -100.000000 100.000000 100.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 100.000000 15.000000 INFINITY
3 120.000000 INFINITY 10.000000
4 70.000000 3.333333 0.000000
5 20.000000 0.000000 INFINITY
6 25.000000 0.000000 2.500000
c) Como los precios de rub aumentan a 190
Vemos que los coeficientes de la funcin objetivo han variado veamos si se encuentra en su rangoadmisible para que la solucin bsica no cambie.
[ ] []
La solucin ptima no cambia dado que los coeficientes de la funcin objetivo se encuentran en
sus rangos admisibles.
d) Si tuviera que producir 23 anillos del tipo 2 entonces cuanto veremos si el restriccin nmero 6
se encuentra en su rango admisible para que la solucin ptima no cambie.
[] [ ]
por lo tanto la solucin ptima sigue siendo la misma entonces la nueva funcin objetivo ser:
()()
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
16/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
8. Al comenzar un ao un especulador de pisos puede haber comprado o no un piso. Si
lo posee tiene tres alternativas cada ao: no hacer nada con el, venderlo y comprar
otro, o solamente vender el piso. Si no posee un piso puede no hacer nada o comprar
uno nuevo.
Si un piso esta un ao completo en posesin sin hacer cambios, existe un cargo por
gestin de 100 dlares.
En la tabla se dan los precios, en miles de dlares, estimados de compra y venta
durante los prximos cuatro aos.
Determinar la estrategia optima a adoptar en los prximos cuatro aos, sabiendo
que el especulador parte inicialmente con un piso y quiere poseer otro al finalizar el
plazo.
SOLUCION:
Formaremos una matriz de decisin con los acontecimientos y las estaciones los
acontecimientos sern:
NN: No hace Nada
VC: Vender y Comprar
V: Solo Vender
C: Solo Comprar
y lgicamente las estaciones que son los 4 aos respectivos. Las decisiones no necesariamente son
las mismas en los siguientes aos.
Tenemos como restriccin que al finalizar el cuarto ao el especulador termina con otro piso del
que tena inicialmente por lo tanto en el cuarto ao solo tenemos que descartar la posibilidad que
Vender por que se quedara sin piso y ese dato no se encuentra como parte del problema.
Usaremos esta matriz para que nos brinden datos, dibujado el grafo respectivo. ( )
Ao Precio de compra Precio de venta
1
2
3
4
10
12
22
14
15
16
17
15
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
17/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
Con estos datos podemos
formular nuestra programacin linear para maximizar la ganancia:
SUJETO A:
USANDO EL LINDO 6.5:
LP OPTIMUM FOUND AT STEP 8
OBJECTIVE FUNCTION VALUE1) 12000.00
VARIABLE VALUE REDUCED COST
NN1 0.000000 5100.000000
VC1 1.000000 0.000000
V1 0.000000 0.000000
NN2 0.000000 4100.000000
VC2 1.000000 0.000000
V2 0.000000 0.000000
C2 0.000000 18000.000000
NN3 0.000000 0.000000
VC3 0.000000 4900.000000
V3 1.000000 0.000000
C3 0.000000 27000.000000
VC4 0.000000 2100.000000
C4 1.000000 0.000000
NN2V1 0.000000 6000.000000
NN3V2 0.000000 5000.000000
Los resultados nos dicen que en el primerao deberamos de Vender y Comprar un
piso. Para el segundo ao tambin Vender y
comprar un piso, para el Tercer ao solo se
debe vender el piso para que al cuarto ao se
compre un piso.
Este sera el plan a seguir para el especulador
ya que as obtendr su mxima ganancia
este problema tambin se puede resolver
mediante rbol de decisiones pero es esta
ocasin decid plantear como una
programacin lineal para as evitar grandes
grficos como era formar el rbol de
decisiones ya que es extenso para poder
dibujarlo.
7/16/2019 PROBLEMA Terminado de Investigacion de Operaciones
18/18
UNIVERSIDAD NACIONAL DE INGENIERIA FIGMM
INVESTIGACION DE OPERACIONES 2013
UNIVERSIDAD NACIONAL DE INGENIERA
Facultad de Ingeniera Geolgica Minera y Metalrgica
CURSO : INVESTIGACION DE OPERACIONES
TEMA : Modelo de Redes, Programacin Lineal
Teora de Decisiones
PROFESOR : Rosales Jimmy
ALUMNOS : Vera Marques, Jos Rey (20100092I)
Reyes Ayala, Luis (20100258D)
FECHA : 04/03/2013
Top Related