Investigacion De Operaciones

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 número de enlaces en un árbol de expansión siempre es uno menos que el número de

nodos . Además , cada nodo está conectado directamente por un único enlace a al menos

otro nodo .

Ver que esta descripción se ajusta a la del árbol de expansión en la Figura 2 , donde hay seis

enlaces y siete nodos ( todos directamente conectados a al menos otro nodo ). Eliminar cualquiera

de estos vínculos y asunción 2 anterior serían violados (sin árbol de expansión ) . ( Check

esto. ) Incurrir el costo adicional innecesario de añadir otro eslabón en su lugar ( sin quitar uno)

y de nuevo ya no tiene un árbol de expansión . (Verifique que la adición de estos vínculos no utilizado de

Figura 1 en la Figura 2 crearía un camino que comienza y termina en el mismo nodo sin

retroceso , lo cual viola la definición de un árbol. )

Por último, cabe señalar que , en contraste con el transporte, asignación,

flujo máximo, y problemas de ruta más corta , un árbol de expansión mínimo problema no es un

tipo especial de problema de flujo de coste mínimo . ( Ni siquiera es un tipo especial de lineal

problema de programación . ) Por otra parte , no puede ser resuelto fácilmente por el Excel Solver.

Esa es la mala noticia . La buena noticia es que se puede resolver muy fácilmente por el

algoritmo se describe a continuación sin necesidad de utilizar un ordenador.

Un algoritmo muy simple

A partir de enlaces en la red, cada paso del algoritmo selecciona un nuevo enlace a

insertar en la lista de enlaces potenciales. Como se describe a continuación , el algoritmo continúa en este

manera hasta que cada nodo es tocado por un enlace , momento en el que se forman los nodos seleccionados

...