AUTOEVALUACIÓN

1. ¿Cuál técnica se utiliza para conectar todos los puntos de una red, minimizando la distancia entre ellos? a) flujo máximo
mínima d) ruta más corta e) mayor expansión
2. El primer paso de la técnica del árbol de expansión mínima es
a) seleccionar el nodo con la mayor distancia a otro nodo.
b) elegir el nodo con la menor distancia a otro nodo.
c) seleccionar el nodo más cercano al origen.
d) elegir el cualquier arco que conecte dos nodos.
e) seleccionar cualquier nodo

3. El primer paso de la técnica del flujo máximo es

a) seleccionar cualquier nodo.
b) elegir cualquier trayectoria de inicio a fin con algún flujo.
c) seleccionar la trayectoria con el flujo máximo.
d) elegir la ruta con el flujo mínimo. e) seleccionar la ruta donde el flujo que llega a cada nodo es mayor que el flujo que sale
4. ¿En qué técnica se conecta el nodo más cercano con la solución existente que aún no está conectada? a) árbol máximo b) r
mínima d) flujo máximo e) flujo mínimo
5. En la técnica de la ruta más corta, el objetivo es determinar la ruta de un origen a un destino que pase por el m
a) Verdadero b) Falso
6. ¿De cuál técnica es un paso importante ajustar los números de la capacidad del flujo en una trayectoria?
a) flujo máximo b) flujo mínimo c) árbol de expansión máxima d) árbol de expansión mínima e) ruta más corta
7. ¿Cuál de los siguientes se considera un problema de trasbordo donde tan solo hay un origen con oferta de 1?
problema del árbol de expansión mínima c) problema del flujo mínimo d) problema de la ruta más corta
8. Si el problema del flujo máximo se formula como un programa lineal, el objetivo es
a) maximizar el flujo del destino al origen. b) minimizar la distancia total. c) minimizar el flujo del destino al origen
origen al destino
9. Cuando se llega a la solución óptima con la técnica del flujo máximo, cada nodo estará conectado con al meno
a) Verdadero b) Falso
10. Una ciudad grande planea que haya retrasos durante las horas de máxima afluencia, cuando los caminos se
de la semana normal, viajan 160,000 vehículos en una vía rápida del centro a un punto 15 millas al oeste. ¿Cuál
ayudaría a los planeadores de la ciudad, a determinar si otras rutas cuentan con la capacidad suficiente para tod
expansión mínima b) la técnica del flujo máximo c) la técnica de la ruta más corta
11. El centro de cómputo en una universidad importante está instalando nuevos cables de fibra óptica para una
¿Cuál de las técnicas estudiadas ayudaría a determinar la menor cantidad de cable necesario para conectar 20 ed
expansión mínima b) flujo máximo c) ruta más corta
12. En un problema del árbol de expansión mínima, se encuentra la solución óptima cuando a) el nodo inicial y e
trayectoria continua. b) el flujo desde nodo inicial es igual al flujo que llega al nodo final. c) todos los arcos se selec
conectaron todos los nodos y son parte del árbol.
13. RUTA MÁS CORTA es una técnica que se utiliza para encontrar cómo una persona o un artículo puede viajar de
total recorrida.
14. La técnica que permite determinar la cantidad máxima de un material que puede fluir por una red se llama FLU
15. La técnica ÁRBOL DE EXPANSIÓN MÍNIMA sirve para conectar todos los puntos de una red minimizando la dist
cia entre ellos? a) flujo máximo b) flujo mínimo c) árbol de expansión

o es mayor que el flujo que sale de cada nodo.

conectada? a) árbol máximo b) ruta más corta c) árbol de expansión

un destino que pase por el menor número de otros nodos.

ujo en una trayectoria?

mínima e) ruta más corta
y un origen con oferta de 1? a) problema del flujo máximo b)
e la ruta más corta
es
ar el flujo del destino al origen. d) encontrar la distancia más corta del

stará conectado con al menos otro nodo.

ncia, cuando los caminos se cierran por mantenimiento. En un día
nto 15 millas al oeste. ¿Cuál de las técnicas estudiadas en el capítulo
apacidad suficiente para todo el tráfico? a) la técnica del árbol de
bles de fibra óptica para una red de cómputo en todo el campus.
necesario para conectar 20 edificios en el campus? a) árbol de
a cuando a) el nodo inicial y el nodo final están conectados por una
nal. c) todos los arcos se seleccionaron como parte del árbol. d) se
o un artículo puede viajar de un lugar a otro minimizando la distancia
fluir por una red se llama FLUJO MÁXIMO.
e una red minimizando la distancia entre ellos.
11-1¿Qué es la técnica del árbol de expansión mínima? ¿Qué clases de problemas se resuelven con esta técnica de análisis cu

La técnica del árbol de expansión mínima determina el camino a través de la red que conecta todos los puntos, al tiempo que minim
para determinar la mejor forma de conectarlas a la energía eléctrica, al sistema de agua, etcétera, de modo que se minimice la distan

11-2 Describa los pasos de la técnica del flujo máximo.

1. Elegir cualquier ruta del inicio (origen) al final (destino) con algún flujo. Si no existe una trayectoria con flujo, entonces, se encon
disponible. Llamar C a tal capacidad, lo cual representa la capacidad adicional máxima que puede asignarse a esta ruta. 3. Para cada
Para cada nodo en esta ruta, incrementar la capacidad del flujo en la cantidad C en la dirección contraria. 4. Repetir los pasos anterio

11-3 Dé varios ejemplos de problemas que se resuelvan con la técnica del flujo máximo.
diseño de redes de telecomnicaciones como: redes de firba optica
redes de computador, redes fetelfoncias, diseños de redes de transporte, de vias ferroviarias, carreteras, tuberías.

11-4 ¿Cuáles son los pasos de la técnica de la ruta más corta?

Pasos de la técnica de la ruta más corta 1. Encontrar el nodo más cercano al origen (planta). Colocar la distancia en un cuadro al lad
en un cuadro al lado del nodo. En algunos casos, deberán revisarse varias rutas para encontrar el nodo más cercano. 3. Repetir este p
la distancia de la ruta más corta. Debería observar que la distancia colocada en el cuadro al lado de cada nodo será la distancia de la
el siguiente nodo más cercano.

11-5 Describa un problema que se resuelva con la técnica de la ruta más corta.
Si observa la figura 11.10, verá que el nodo más cercano a la planta es el nodo 2, con una distancia de 100 millas. Se conectan enton
siguiente nodo más cercano al origen. Verificamos los nodos 3, 4 y 5. El nodo 3 es el más cercano, pero existen dos trayectorias pos
la figura 11.12). Repetimos el proceso. El siguiente nodo más cercano es el nodo 4 o el 5. El nodo 4 está a 200 millas del nodo 2, y e
dos trayectorias para el nodo 5, 2–5 y 3–5, desde el origen. Advierta que no tenemos que regresar hasta el origen, porque ya conocem
cuadros al lado de estos nodos. La ruta 2–5 tiene 100 millas y el nodo 2 está a 100 millas del origen. Entonces, la distancia total es d
nodo 3 tiene 190 millas (40 entre el nodo 5 y el 3 más 150 del nodo 3 al origen). Así, elegimos el nodo 5 que pasa por el nodo 3 desd
los últimos nodos que quedan. El nodo 4 está a 300 millas del origen (300 200 del 4 al 2 más 100 del 2 al origen). El nodo 6 está a 2
final, el proceso termina (véase la figura 11.14). La ruta más corta es 1–2–3–5–6, con una distancia mínima de 290 millas. Este prob
11.3A. La solución se muestra en el programa 11.3B. Se dispone de información adicional para la solución óptima, si se hace clic en

11-6 ¿Es posible obtener soluciones óptimas alternativas con la técnica de la ruta más corta? ¿Hay una forma automática de

11-7 Describa cómo se modela el problema del flujo máximo como un problema de trasbordo.
Para poder resolver un problema de transbordo mediante programación lineal, basta con conocer una nueva familia de restricciones,
nodos, los nodos de oferta pura, los de demanda pura y los nodos transitorios que posibilitan el transbordo y que deben de balancear
nodo sean iguales a las que salgan del mismo (unidades que salen + unidades que conserve el nodo).
11-8 Describa cómo se modela el problema de la ruta más corta como un problema de trasbordo.
El problema de la ruta más corta se puede ver como un tipo especial de problema de trasbordo con un origen que tiene oferta de 1, u
como un programa lineal con variables 0-1. Las variables indicarán si se elige un arco específico como parte de la ruta tomada. Para
Las variables se definen como: Xij 1 si se elige el arco del nodo i al nodo j y Xij 0 de otra manera Como el punto de inicio es el nod
como el nodo 6 es el destino final, no se incluyen variables que comiencen en el nodo 6.
n con esta técnica de análisis cuantitativo?

s los puntos, al tiempo que minimiza la distancia total. Cuando los puntos representan casas en una sección, esta técnica es útil
e modo que se minimice la distancia total o la longitud de los cables o las tuberías.

toria con flujo, entonces, se encontró la solución óptima. 2. Determinar el arco en esta ruta con la menor capacidad de flujo
asignarse a esta ruta. 3. Para cada nodo en esta ruta, disminuir en la cantidad C la capacidad del flujo en la dirección del flujo.
ntraria. 4. Repetir los pasos anteriores hasta que no sea posible aumentar el flujo.

eras, tuberías.

ar la distancia en un cuadro al lado del nodo. 2. Encontrar el siguiente nodo más cercano al origen (planta) y poner la distancia
odo más cercano. 3. Repetir este proceso hasta que se haya revisado la red completa. La última distancia en el nodo final será
e cada nodo será la distancia de la ruta más corta a ese nodo. Tales distancias se usan como resultados parciales para encontrar

de 100 millas. Se conectan entonces los dos nodos. Esta primera iteración se muestra en la figura 11.11. Ahora se busca el
pero existen dos trayectorias posibles. La ruta 1–2–3 es la más cercana al origen, con una distancia total de 150 millas (véase
4 está a 200 millas del nodo 2, y el nodo 2 está a 100 millas del nodo 1. Entonces, el nodo 4 está a 300 millas del origen. Hay
hasta el origen, porque ya conocemos la ruta más corta de los nodos 2 y 3 al origen. Las distancias mínimas se colocan en
n. Entonces, la distancia total es de 200 millas. De manera similar, determinamos que la trayectoria del nodo 5 al origen por el
nodo 5 que pasa por el nodo 3 desde el origen (véase la figura 11.13). El siguiente nodo más cercano será el nodo 4 o el 6, como
del 2 al origen). El nodo 6 está a 290 millas del origen (290 100 190). El nodo 6 tiene la menor distancia y como es el nodo
a mínima de 290 millas. Este problema se resuelve en QM para Windows. La ventana de entrada se ilustra en el programa
solución óptima, si se hace clic en Window una vez resuelto el problema.

¿Hay una forma automática de saber si se tiene otra solución óptima?

o.
na nueva familia de restricciones, las llamadas  restricciones de balanceo. En un problema de transbordo existen 3 clases de
nsbordo y que deben de balancearse para hacer que el sistema sea viable, es decir, que todas las unidades que ingresen a un
o).
rdo.
un origen que tiene oferta de 1, un destino con demanda 1 y varios puntos de trasbordo. Esta clase de problemas se modela
omo parte de la ruta tomada. Para el ejemplo de Ray Design, el objetivo es minimizar la distancia total (costo) de inicio a fin.
Como el punto de inicio es el nodo 1, no se incluye una variable que vaya del nodo 2 o 3 de regreso al 1. De manera similar,
écnica es útil

ad de flujo
ión del flujo.

r la distancia
do final será
ra encontrar

e busca el
millas (véase
origen. Hay
ocan en
origen por el
4 o el 6, como
es el nodo
rograma

3 clases de
esen a un

se modela
inicio a fin.
era similar,
Minimizar la Longitud=
4X12+X13+2X14+5X25+3X34+2X36+4X45+5X47+6X57+7X510+3X67+7X68+6X79+3X89
+7X812+4X910+5X912+6X913+3X1011+3X1112+4X1214+5X1214

solución
Con el método de expansión mínima podemos concluir que la distancia mínima total del ca
Las medidas están en cientos de pies por lo cual.
45 x 100(pies)=4,500 pies
 Las distancias entre cada casa se
indican mediante sus respectivos
nodos. La distancia entre los
nodos 1 y 2. Los números al lado
de los nodos indican el número
máximo de pies (en cientos) que
pueden existir entre los diferentes
nodos y así sucesivamente.

distancia mínima total del cable sería de 45.

se recomienda la ruta marcada en la red, que comprende d
ada en la red, que comprende desde nodo 1 a 3, 3 a 5, 5 a 7, 7 a 10, 10 a 13.
 solución
R/ La distancia mínima es de 47 (4,700 pies). Como se pued
olución
e 47 (4,700 pies). Como se puede ver, la solución final ha cambiado, ya que en el problema 11.9 la solución era 4500 pies.
ón era 4500 pies.
 solución
R/ La única solución óptima es: 177 unidades de l
las cámaras de video de seguridad, desde cinco lu
potenciales hasta el centro de control principal.
óptima es: 177 unidades de longitud para conectar
de seguridad, desde cinco lugares de problemas
centro de control principal.
Transworld Moving, al igual que otras compañías de mudanzas, sigue de
cerca la influencia de la construcción de carreteras, para asegurarse de
que las rutas mantienen su eficiencia. Por desgracia, hay una
construcción inesperada debido a la falta de planeación del
mantenimiento de caminos en las cercanías de New Haven,
representada por el nodo 9 en la red (véase el problema 11-11).
Ninguno de los caminos que llevan al nodo 9, excepto el del nodo 9 al
nodo 11, se puede usar.
¿Tiene esto influencia en la ruta que debería usarse para enviar el
mobiliario y el equipo de Cohen Properties a su nueva oficina?

no hay nigun cambio sigue pasando por la ruta

ambio sigue pasando por la ruta de 1,3,3,5,5,7,7,10
 11
Resuelva el problema del árbol de expansión mínima de la red mostrada en la
figura 11.26. Suponga que los números representan distancia en cientos de
yardas.
11-18 Consulte el problema 11-17. ¿Qué impacto tendría cambiar el
valor del arco 6-7 a 500 yardas sobre la solución al problema y la
distancia total?

R/ Si la distancia entre los nodos

 solución

/ Si la distancia entre los nodos 6 y 7 se convierte en 5, la distancia mínima aumenta cambiando a 23 (2,300 yardas).
300 yardas).
11-25 .Resuelva el problema de la ruta más corta presentado en la red de la figura
11.29, del nodo 1 al nodo 16. Todos los números representan kilómetros entre pueblos
de Alemania cerca de Black Forest.
11-26 Debido al mal tiempo, los caminos que van por los nodos 7 y 8 están
cerrados (véase el problema 11-25). No pasa el tráfico de entrada ni de salida
de estos nodos. Describa su impacto (si lo hay) sobre la ruta más corta de
esta red.

impacta en dos kilometros más(76 km) cuando no se pu

ya que anteriormente si pasaban por ahí y se ahorraba,
tuvo que bordear.se cambiaría la ruta en 5 lugares entre
os más(76 km) cuando no se pueden utilizar los nodos 6 y 7
pasaban por ahí y se ahorraba, porque iba directo, ahora
biaría la ruta en 5 lugares entre los pueblos de Alemania.
 11-27 Consulte el problema 11-25 y modélelo con programación lineal.
Resuélvalo con cualquier software.

MIN Z 20X12+15X13+18X14+10X25+10X26+11X37+12X48+8X56+16X59+12X69+12X67+
18X710+18X711+22X78+20X812+16X913+17X1013+16X1114+15X1215+10X1314+18X1316+14X1416+
25X1516
S.A
X12+X13+X14=1
X12-X25-X26=0
X12-X37=0
X12-X48=0
X25-X59-X56=0
X26+X56-X69-X67=0
X67+X37-X78-X710-X711=0
X78+X48-X812=0
X59+X69-X913=0
X710-X1013=0
X711+X1211-X1114=0
X812+X1112-X1215=0
X913+X1013-X1314-X1316=0
X1114+X1314-X1416=0
X1215-X1516=0
X1516+X1416+X1316=1
+18X1316+14X1416+
En el problema 11-27, se desarrolló un programa lineal para el problema de la ruta más
corta. Modifique este programa lineal para hacer los cambios detallados en el problema
11-26. Resuélvalo y compárelo con la solución antes de los cambios
Grey Construction quiere determinar la forma menos costosa de conectar las casas que
está construyendo con TV por cable. Ha identificado 11 ramas o rutas posibles para
conectar las casas. El costo en cientos de dólares y las ramas se resumen en la siguiente
tabla.
a) ¿Cuál es la manera menos costosa de cablear las casas?

solución

para conectar las casas las mejores ramas o rutas son las siguientes:
1 2 con un total de 340 dolares
1 3
1 4
1 5
3 7
5 8
6 7
8 9
b)Después de revisar los costos del cable y la instalación, Grey Construction
desea alterar los costos para instalar el cable de TV entre las casas. Necesita
cambiar las primeras ramas. Los costos se resumen en la siguiente tabla.
¿Cuál es el impacto sobre los costos totales?

respuesta para b)
se reduce el costo a 200 dólares
solución
rutas más corta: co un total de 12 millas(cientos)
 SOLUCIÓN

MINIMIZA LA DISTANCIA EN 2 MILLAS(CIENTOS ) CON UN TOTAL DE 10 MILLAS EN CIENTOS

 2

1 3 4

5 6
 solución

A) La ruta más corta es de 4900 pies que está conformada desde el 1-3-7-12- 16-20-23-25.
B) Si se instala el cableado telefónico (sea un ejemplo) tendría varias redes saturadas y lo más
recomendable seria tomar otras rutas más complicadas y largas para el cableado, pero si no se
opta por saturar las líneas con el cableado del teléfono quedaría bien la red.
C) La mejor ruta para el segundo cable de red es desde 1-3-6-11-15-19-23-25 con una distancia de
50 pies.
0-23-25.
das y lo más
pero si no se
una distancia de