Investigacion De Operaciones
Enviado por ericlopba92 • 23 de Mayo de 2014 • 3.392 Palabras (14 Páginas) • 159 Visitas
CD S Ch 6-1
SUPLEMENTO DEL CAPÍTULO 6 :
MÍNIMOS PROBLEMAS spanning-tree
Capítulo 6 se centra en los problemas de optimización de la red. Estos son problemas que pueden ser
descrito en términos de una red completa que tiene ambos nodos y enlaces (o arcos ) y el
objetivo es optimizar la operación de la red .
Ahora dirigimos nuestra atención a otro tipo de problema en el que el objetivo es
el diseño de la red . Los nodos se dan , pero tenemos que decidir que une para dar a la
red . Específicamente, cada relación potencial tiene un costo ( diferente para los distintos enlaces) para
insertarlo en la red . Tenemos la obligación de proporcionar suficientes vínculos para proporcionar una ruta de acceso
entre cada par de nodos . El objetivo es hacer esto de una manera que minimiza el total de
coste de los enlaces.
Tal problema se conoce como un problema de expansión mínimo - árbol, como se ilustra
por el siguiente ejemplo .
Un ejemplo: El Problema Modern Corp.
Gestión de la Corporación moderna ha decidido tener un estado - of-the -art de fibra óptica
red instalada para proporcionar comunicaciones de alta velocidad (datos , voz y video) entre
sus principales centros.
Los nodos en la Figura 1 muestran la distribución geográfica de las principales de la corporación
centros (que incluyen oficinas corporativas , servicio de superordenador , y una investigación
aparcar , así como centros de producción y distribución ) . Las líneas de trazos son el potencial
ubicaciones de los cables de fibra óptica. (También son posibles otros cables entre pares de centros
pero se han descartado como poco económico . ) El número al lado de cada línea de puntos da la
costo ( en millones de dólares ) en caso de que el cable en particular es elegido como uno que se instalará.
Figura 1 : Una pantalla de grandes centros Modern Corp. ' s (los nodos) , las posibles ubicaciones
para cables de fibra óptica (las líneas discontinuas) , y el costo en millones de dólares para
los cables ( los números) .
CD S Ch 6-2
Cualquier par de centros no se necesita tener un cable de conexión directa en
Para sacar el máximo provecho de la tecnología de fibra óptica para comunicaciones de alta velocidad
entre estos centros. Todo lo que es necesario es tener una serie de cables que conectan el
centros .
El problema es determinar qué se deben instalar cables para minimizar el
coste total de proporcionar comunicaciones de alta velocidad entre cada par de centros . Esto es ,
de hecho, un problema mínimo spanning-tree .
La solución óptima para este problema se muestra en la Figura 2 , donde los vínculos de este
red corresponden a los posibles cables de la Figura 1 que deben ser elegidos para
instalación. ( Tenga en cuenta que en efecto, hay un camino entre cada par de centros. ) La resultante
costo de esta red de fibra óptica es
Costo total = 2 + 2 + 1 + 3 + 1 + 5 = 14 ($ 14 millones).
Cualquier otro diseño de la red que conecta cada par de centros costaría al menos $ 1
millones más.
Figura 2 : La red de fibra óptica que proporciona la solución óptima para Modern
problema mínimo spanning-tree .
¿Cuál es la razón del nombre extraño, problema mínimo spanning-tree ? aquí
es la explicación .
En la terminología de la teoría de la red , la red en la Figura 2 es un árbol porque
no tiene caminos que comienzan y terminan en el mismo nodo sin dar marcha atrás
(es decir , no hay caminos que ciclo). También es un árbol de expansión , ya que es un árbol que
proporciona un camino entre cada par de nodos ( por lo que " abarca " todos los nodos ) . Finalmente ,
es un árbol de expansión mínimo , ya que minimiza el coste total entre todos
árboles de expansión.
CD S Ch 6-3
Características generales
Al igual que para el problema de Modern , cada problema mínimo spanning-tree satisface la
siguientes supuestos.
Supuestos de una Spanning -Tree mínimo problema
1 . Se le da los nodos de una red , pero no los enlaces. En su lugar , se le da
los vínculos potenciales y el costo positivo ( o una medida similar) para cada uno si es
insertado en la red .
2 . Usted desea diseñar la red mediante la inserción de enlaces suficientes para satisfacer la
requisito de que haya un camino entre cada par de nodos .
3 . El objetivo es cumplir con este requisito de una manera que minimiza el total de
costo de hacerlo .
Una solución óptima para este problema siempre es un árbol de expansión . Aquí es un fácil
manera de reconocer un árbol de expansión .
El
...