INVESTIGACIÓN OPERATIVA TAREA 5

Angie Lisbeth Palma Laz “A”

INVESTIGACIÓN OPERATIVA TAREA 5

1. Antonio conduce diariamente a su trabajo. Debido a que acaba de terminar un curso optimización de redes, él quiere determinar la ruta más corta a su trabajo conduciendo a alta velocidad, sin embargo, la ruta seleccionada está patrullada por la policía y él ya tiene muchas multas pagadas por exceso de velocidad, la ruta más corta no es la mejor elección. Por consiguiente, Antonio ha decidido elegir una ruta que maximice la probabilidad de no ser detenido por la policía.

 [pic 1]

Muestra las posibles multas entre su hogar y el trabajo, la probabilidad de que no lo multen en 1 3 5 7 es 0.9 x 0.3 x 0.25 = 0.0675.

Se formula como un modelo en la ruta más corta usando una transformación logarítmica que se convertirá el producto de probabilidad en la suma de los logaritmos de probabilidades, si p1k = p1 x p2 x pk es la probabilidad para que no lo detengan, entonces Log p1k = log p1 + log p2 + log p k, la maximización de p 1k es equivalente a la maximización de log p 1k.

Entonces log p1k < = 0, es la maximización de log p 1k, que equivale a la minimización de – log p 1k. Usando esta transformación, las probabilidades individuales de p la figura anterior la reemplazan con –log p, para todas las j en la red, por tanto, la red.

 [pic 2]

Usando el paquete de optimización se encuentra la ruta más corta en la figura anterior, definida por nodos 1, 3, 5 y 7, y una longitud de 1.1707 (= − log p 17), la probabilidad máxima de que no lo detengan es p17 = 0.0675. 220.  

1. Una empresa que proporciona servicio de rutas turísticas ha planeado un circuito turístico que trata de cubrir cinco nuevas áreas de desarrollo ecológico. La red del sistema se resume en la figura:

[pic 3] 

Los números asociados con cada rama representan la distancia en millas que se necesita para contactarse dos sitios cualesquiera. El nodo 1 representa el punto principal (de salida del circuito) y los restantes representan las cinco áreas de desarrollo.

Se requiere determinar los enlaces que originarán la ruta mínima que garantice que todas las áreas se conecten (directa o indirectamente) al punto de partida, pues se planea que el circuito debe iniciar en el nodo 1 y visitar por lo menos un lugar ecológico (no es necesario que los cinco lugares sean visitados lo que se desea, es obtener la mínima distancia para todos los nodos al nodo de inicio.)

Primera Iteración. 

El nodo 1 debe conectarse al nodo 2, que es el nodo más próximo en C’ = {2, 3, 4, 5, 6}.

Por lo tanto: C = {1, 2}, C’ = {3, 4, 5, 6} como se ve en la figura:

 [pic 4]

Segunda Iteración. 

Los nodos 1 y 2 (del conjunto C) ahora están unidos permanentemente. En la Iteración 2 seleccionamos un nodo en C’ = {3, 4, 5, 6} que esté más próximo a un nodo en C = {1, 2}. Como la distancia más corta ocurre entre 2 y 5, tenemos: C = {1, 2, 5}, C’ = {3, 4, 6} como se ve en la figura:

 [pic 5]

Tercera Iteración. 

La iteración 2 da las distancias de los nodos de C = {1, 2, 5} a todos los nodos de C’ = {3, 4, 6}. Por lo tanto, los nodos 2 y 4 están conectados, lo que produce: C = {1, 2, 4, 5}, C’ = {3, 6} como se ve en la figura:

 [pic 6]

Cuarta Iteración. 

La iteración 3 muestra que los nodos 4 y 6 deben estar conectados. Por lo tanto, obtenemos: C = {1, 2, 4, 5, 6}, C’ = {3}. Como se ve en la figura:

[pic 7] 

Quinta Iteración. 

En la iteración 5 tenemos un empate que podemos romper arbitrariamente, como se ve en la figura. Esto quiere decir que podemos conectar 1 y 3 ó 4 y 3. Ambas soluciones (alternativas) nos conducen a: C = {1, 2, 3, 4, 5, 6}, C’ = ø.

[pic 8]

                                      a = 1+3+4+3+5 = 16 millas 

1. Una agencia de viajes y turismo ha establecido varias rutas a seguir para llegar a un punto (6) considerado muy popular entre los turistas lo que se representa en la figura, (se toma a H como el lugar de partida de la excursión).

 [pic 9]

Se desea obtener la ruta más corta para llegar desde H hasta 6.

[pic 10] 

El resultante de usar el modelo a la ruta más corta siendo esta la mínima distancia que se necesita para ir desde H hasta 6.

[pic 11] 

1. Se desea encontrar la distancia más corta entre varios lugares para lo que tenemos un grafo de distancias el cual representa a varias ciudades unidas por los caminos que se representan en la figura. (Use el algoritmo Dijkstra).

 [pic 12]

Se representan:  [pic 13]

1. Sea el grafo de la figura, el que utilizaremos como ejemplo para aplicar el modelo de Floyd: [pic 14]

[pic 15] 

           Dij Inicial

           ∞          ∞       ∞        1                                 1     0        0        0        0 

...