Redes

Universidad de Chile
Economía & Negocios

Miércoles 17, Junio 2009
Investigación Operativa

Pauta Ayudantía N°9
Problema Transporte / Ruta Más Corta / Flujo Máximo Profesores: M. Morales – J. Miranda – A. Cataldo

Problema 1 (Transporte)
Tres súper computadores deben enviar información a tres servidores que lo solicitan. La información la pueden recibir en forma segmentada, es decir,una vez realizada la planificación del envío, un servidor puede recibir la totalidad de la información desde uno o más súper computadores. Cada computador está limitado por su capacidad de procesamiento por lo que solo pueden enviar 30, 30 y 10 T/seg (terabytes por segundo). Los usuarios solicitan 15, 15 y 10 Teras de información en un segundo. El costo de enviar información está asociado al plan deconecci_on web que se establece entre computador-usuario, y se detalla a continuación: Super Computador Tasa de Envío 1 30 2 10 3 30 Usuario 1 2 3 Tamaño Solicitud 15 10 15

Usuario 1 Usuario 2 Usuario 3 4 $/T 4 $/T Súper PC 1 5 $/T 5 $/T 5 $/T Súper PC 2 4 $/T 4 $/T Súper PC 3 Puesto que la demanda en los súper computadores es muy alta, la información procesada que no se envía debe sereliminada, para permitir que nuevas consultas sean procesadas. a) Escriba la decisión de la planificación del envío de información en un segundo como un modelo de transporte. ¿Qué elementos debe agregar para que se cumplan las hipótesis de transporte? Agréguelos. b) Encuentre una solución factible a través del método de esquina nor-oeste. c) Resolver el problema a partir de esta solución. d) Interpretarla solución encontrada en el problema original (aquel sin los elementos agregados). e) Propuesto: Hacer b): con método de saturación de arcos de mínimo costo.

Universidad de Chile
Economía & Negocios

Miércoles 17, Junio 2009
Investigación Operativa

SOLUCION Problema 1

“RECORDAR EL SIGNIFICADO DE LAS DUALES u,v: Dual de las restricciones asociadas a la fuente i & destino j”Universidad de Chile
Economía & Negocios

Miércoles 17, Junio 2009
Investigación Operativa

Universidad de Chile
Economía & Negocios

Miércoles 17, Junio 2009
Investigación Operativa

Universidad de Chile
Economía & Negocios

Miércoles 17, Junio 2009
Investigación Operativa

Universidad de Chile
Economía & Negocios

Miércoles 17, Junio 2009
Investigación Operativa

Problema 2(Ruta Más Corta)
Considere ahora que el gobierno desea diseñar y definir para cada comuna las mejores rutas de acceso para llegar a los distintos hospitales que se encuentren dentro de su radio de cobertura. La Figura 1 muestra la red de caminos posibles para la comuna de Estación Central, entre uno de los sectores más poblados de la comuna y dos hospitales ya instalados (dentro del radio).Considere que cada nodo es un punto de transbordo y que cada arco de esta red tiene asociado un tiempo de viaje en minutos y una dirección.

Determine la ruta que tenga el menor tiempo de viaje desde el sector más poblado a cada uno de los hospitales en cuestión. Utilice el algoritmo Dijkstra siendo muy claro en cada paso de las iteraciones del algoritmo
SOLUCION Problema 2

Ruta más corta: Setiene una red donde cada arco tiene un costo cij de recorrerlo (tiempo, distancia, dinero, etc) El problema consiste en llegar desde un nodo denominado origen (nodo s) a un nodo denominado destino (nodo t) al menor costo posible. Algoritmo Dijkstra: Un algoritmo existente para resolver el problema de la ruta más corta es el algoritmo Dijkstra. El algoritmo necesita un grafo orientado (con dirección)y el valor de los costos positivo para entregar un árbol de caminos mínimos de modo de ir del nodo inicial a cualquier otro nodo.
Para la resolución de este problema tenemos los siguientes parámetros Vector  , el cual tiene el costo mínimo de llegar desde el nodo origen al nodo indicado Vector C, el cual representa desde cual llego al nodo indicado Conjunto R; corresponde al conjunto con los...