4.1.

El modelo del camino ms corto

Se trata de un modelo de red (debido a la forma de diagrama de red usado para
su representacin), donde cada arco o rama que une dos nodos (elementos) que
forman dicha red, viene caracterizado por un valor que representa la distancia
(costo o tiempo) desde el nodo origen hasta el nodo destino. Si denominamos ruta
o camino, a cualquier secuencia de arcos que conecte el nodo origen con el
destino, la resolucin consiste en encontrar la ms corta posible. Usualmente los
arcos no estn orientados, es decir, se permite el trfico en ambos sentidos, salvo
que se indique lo contrario (por ejemplo en una calle de direccin.
Los problemas conocidos como problemas del camino mnimo o camino ms
corto, tratan como su nombre indica de hallar la ruta mnima o ms corta entre dos
puntos. Este mnimo puede ser la distancia entre los puntos origen y destino o
bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica
mucho para problemas de redes de comunicaciones.
Este tipo de problemas pueden ser resueltos por el mtodo del Simplex, sin
embargo existen otros mtodos ms eficientes como por ejemplo el algoritmo de
Hijastra o el de Bilman-Ford.
Ejemplo
Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Est
estudiando cual es el trayecto ms corto usando un mapa de carreteras. Las
carreteras y sus distancias estn representadas en la figura siguiente:

Se determinan las variables de decisin, en este caso:

Sij: accin de desplazarse del pueblo i al j (0 indica que no hay
desplazamiento y 1 que s hay desplazamiento)
Se determinan las restricciones y se expresan como ecuaciones o inecuaciones
de las variables de decisin. Dichas restricciones se deducen del balance entre los
posibles caminos que parten desde cada pueblo y los que llegan hasta l
(obviando los caminos que nos devuelvan al punto de partida y los que provengan
del punto de destino):
Balance de caminos del pueblo 1: X12 + X13 = 1
Balance de caminos del pueblo 2: X24 + X25 X12 X42 X52 = 0
Balance de caminos del pueblo 3: X34 + X36 X13 X43 X63 = 0
Balance de caminos del pueblo 4: X42 + X43 + X45 X24 X34 X54 = 0
Balance de caminos del pueblo 5: X52 + X54 + X57 X25 X45 =
Balance de caminos del pueblo 6: X63 + X67 X36 = 0
Balance de caminos del pueblo 7: X57 X67 = -1
Se expresan todas las condiciones implcitamente establecidas por la naturaleza
de las variables: que no puedan ser negativas, que sean enteras, que solo puedan
tomar determinados valores, En este caso las restricciones son que las
variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto
no pueden ser negativas:
Sij 0
Sij es booleano
Se determina la funcin objetivo:
Minimizar Z = 12X12 + 4X13 + 5X24 + 3X25 + 2X34 + 10X36 + 5X42 +
2X43 + 10X45 + 3X52 + 10X54 + 2X57 + 10X63 + 4X67

4.2. El modelo de flujo mximo

En teora de grafos, un grafo dirigido con pesos es tambin conocido como una
red.
En los problemas de flujo en redes, las aristas representan canales por los que
puede circular cierta cosa: datos, agua, coches, corriente elctrica, etc. Los pesos
de las aristas representan la capacidad mxima de un canal: velocidad de una
conexin, volumen mximo de agua, cantidad mxima de trfico, voltaje de una
lnea elctrica, etc.; aunque es posible que la cantidad real de flujo sea menor.
El problema del flujo mximo consiste en lo siguiente: dado un grafo dirigido con
pesos, G = (V, A, W), que representa las capacidades mximas de los canales, un
nodo de inicio s y otro de fin t en V, encontrar la cantidad mxima de flujo que
puede circular desde s hasta t. En la figura 5.33 se muestra un ejemplo de
problema y la solucin. El grafo de la izquierda, G, pintado con lneas continuas,
representa las capacidades mximas; sera la entrada del problema. El grafo de la
derecha, F, representado con lneas discontinuas, indica los flujos reales; es una
posible solucin para el problema.
La solucin del problema debe cumplir las siguientes propiedades:
La suma de los pesos de las aristas que salen de s debe ser igual a la suma de las
Aristas que llegan a t. Esta cantidad es el flujo total entre s y para cualquier nodo
distinto de s y de t, la suma de las aristas que llegan al nodo

Debe ser igual a la suma de las aristas que salen al mismo.

Los pesos de las aristas en F no pueden superar los pesos mximos indicados en
G. Es decir, si CG(a, b) es el peso de la arista <x, y> de G y CF (a, b) es el peso
de la misma arista en F, entonces CF (a, b) CG(a, b).
Una vez planteado el problema, vamos a estudiar la forma de resolverlo. En primer
lugar propondremos un algoritmo intuitivo, y a continuacin analizaremos si
garantiza la solucin optima o no. Un posible algoritmo para calcular el flujo
mximo La idea de los flujos, que van desde s hasta t, es muy prxima a la de un
camino por el que circula cierto fluido. Cada unidad de flujo que llega hasta un
nodo, debe salir por a una de sus aristas. Por lo tanto, un posible algoritmo podra
basarse en encontrar caminos (s, v1, v2,..., Vm, t) en G. Por ese camino podemos

mandar cierta cantidad de flujo. Cuanto? Pues todo lo que quepa. Por ejemplo, si
en el grafo G de la figura 5.33 tomamos el camino (s, a, b, t), vemos que las
aristas por las que pasa tienen pesos: 5, 2, 4. El mximo flujo que podemos
mandar por ese camino est limitado por el mnimo de las capacidades por las que
pasa el camino; en este caso 2. De esta forma, el algoritmo ira encontrando
caminos en G, aadiendo los flujos correspondientes al grafo F y quitndolos de
G. Y
As seguira hasta que no queden ms caminos para enviar flujo.
La estructura del algoritmo que lleva a cabo esta idea sera la siguiente:
1. Sea G = (V, A, CG) el grafo de capacidades mximas. Inicializar el grafo de
flujos
Reales, F, con los mismos nodos y aristas de G, pero con pesos 0. Es decir, CF (v,
w) = 0; <Vw> A. Este grafo guardar a el resultado del algoritmo.
2. Buscar un camino en G, desde s hasta t, pasando por aristas cuyo peso sea
mayor que 0. Este camino es denominado camino creciente. Supongamos que el
camino es (s, v1, v2,..., Vm, t). Tomamos m = min {CG(s, v1), CG (v1, v2),..., CG
(Vm, t)}. Es decir, por este camino pueden fluir hasta m unidades de flujo, como
mximo.
3. Para cada arista <Vw> del camino anterior, aadir m al coste de la arista
correspondiente en F y quitarlo en G. Es decir, CF (v, w) = CF (v, w) + m; CG (v, w)
= CG (v, w) m; para todo <Vw> del camino del paso 2.
4. Volver al paso 2 mientras siga existiendo algn camino creciente entre s y t en
G. Todava nos queda por determinar la forma de encontrar el camino creciente
del
Paso
2. Una vez ms, la bsqueda primero en profundidad puede sernos de utilidad.
Para encontrar un camino creciente, podramos iniciar una bsqueda en
profundidad en G a partir del nodo s. Cuando la bsqueda llegue a t ya tenemos
un camino de s a t 12. Adems, el procedimiento bps debera ser modificado para
tener en cuenta solo las aristas con peso
Mayor que cero. Por otro lado, est claro que entre s y t puede haber ms de un
camino creciente. Esta primera versin del algoritmo indica que se encuentre un
camino cualquiera. El algoritmo ser a optimo si, independientemente de los
caminos elegidos en el paso 2, siempre encuentra el flujo mximo. Vamos a ver
que no siempre ocurre as. Ejemplo 5.6 Vamos a aplicar la primera versin del
algoritmo del flujo mximo sobre el grafo G de la figura 5.33a). En la figura 5.34 se
muestra una ejecucin posible del algoritmo, donde no se alcanza la solucin

optima.

En la primera ejecucin del paso 2, se encuentra el camino (s, c, b, t). Los costes
de las aristas son: 4, 4, 4; as que m = 4. Esta cantidad se aade en F (figura
5.34d) y se quita de G (figura 5.34c). Si intentamos buscar otro camino entre s y t,
en el grafo de la figura 5.34c), que pase por aristas con peso mayor que cero,
vemos que no existe ninguno. Por 12El camino estara en la pila de llamadas
recursivas. Lo ms adecuado sera ir almacenando en un arraya los nodos que
estn en la rama actual de la llamada a bpp.246 Capitulo 5. Grafos lo tanto, el
algoritmo acabara. El resultado del algoritmo es que el flujo total encontrado es 4.
En consecuencia, el algoritmo no encuentra el optimo, que como vimos en la
figura
5.33 es 6 unidades de flujo. No obstante, si los caminos hubieran sido elegidos en
otro orden s que se habra obtenido el optimo. En concreto, se puede comprobar
que el resultado de la figura 5.33 se alcanzara si seleccionamos los siguientes
caminos, por orden: (s, a, b, t)
Con peso 2; (s, c, d, t) con peso 2; (s, c, d, b, t) con peso 1; (s, c, b, t) con peso 1.
Algoritmo de flujo mximo deshaciendo caminos
La primera versin del algoritmo es no determinista: en el paso 2 se pueden elegir
Varios caminos y, dependiendo de cul se coja, el algoritmo alcanza la solucin
optima o no. Para solucionar el problema podemos hacer una pequea
modificacin en el algoritmo. El sentido de esta modificacin es que si se coge un
camino, pero que luego resulta ser una mala decisin, se pueda deshacer el flujo
enviado por ese camino.
En particular, la modificacin afecta a la forma de actualizar CG dentro del paso 3.
Cada vez que encontramos un camino creciente, quitamos m unidades de flujo de
G y las ponemos en F. Ahora, adems, vamos a indicar en G que se pueden

deshacer m unidades de flujo a travs de las aristas del camino. El flujo que se
deshace tendr el sentido opuesto al de aadir; es decir, si se aade m unidades
en <Vw> en F, entonces se quitan m de <Vw> en G y se aaden m unidades de
deshacer para la arista <x, y> en G.
En definitiva, este cambio solo implica modificaciones dentro del paso 3 del
algoritmo, que ahora debera decir:
3 Para cada arista <Vw> del camino anterior, aadir m al coste de la arista
correspondiente en F, quitarlo en G y ponerlo en G en sentido contrario. Es decir,
CF (v, w) = CF (v, w) + m; CG (v, w) = CG (v, w) m; CG (w, v) = CG (w, v) + m
Para todo <Vw> del camino del paso 2.
Hay que tener en cuenta que aqu estamos suponiendo que el peso de una arista
Inexistente es 0. De esta forma, cuando sumamos m a CG (w, v), pero <Vw> no
est en G, sera equivalente a crear una nueva arista con peso m.
Esta nueva versin del algoritmo no deja de ser no determinista, pero garantiza
siempre la solucin optima. Aunque no lo vamos a demostrar, vamos a ver que se
resuelve correctamente el problema que vimos en el ejemplo 5.6.
Ejemplo 5.7 Vamos a aplicar la segunda versin del algoritmo del flujo mximo la
que permite deshacer caminos sobre el grafo G de la figura 5.33a). Un posible
resultado del algoritmo se muestra en la figura 5.35.
Igual que en el ejemplo 5.6, consideramos que en la primera ejecucin del paso 2
se encuentra el camino (s, c, b, t), con m = 4. Esta cantidad se aade en F (figura
5.35d). Ahora, en G se quita esa cantidad en sentido directo y se aade en sentido
contrario (figura 5.35c).
A continuacin podemos encontrar un nuevo camino, que pasa por la arista de
deshacer <x, y>. El camino es (s, a, b, c, d, t), con pesos: 5, 2, 4, 3, 2. Por lo
tanto,

m = 2. Se aade a F13 (figura 5.35f) y se actualiza G (figura 5.35e). En el

siguiente paso, ya no existe ningn camino creciente, luego acaba el algoritmo.
Si comparamos la solucin obtenida con la mostrada en la figura 5.33, vemos que
no coinciden. No obstante, ambas tienen el mismo valor de flujo total, 6, y ambas
son ptimas. En perfectamente posible, como en este ejemplo, que la solucin
ptima no sea nica.

4.3. El modelo del rbol de expansin mnima

El algoritmo del rbol de expansin mnima es un modelo de optimizacin de
redes que consiste en enlazar todos los nodos de la red de forma directa y/o
indirecta con el objetivo de que la longitud total de los arcos o ramales sea mnima
(entindase por longitud del arco una cantidad variable segn el contexto
operacional de minimizacin, y que puede bien representar una distancia o unidad
de medida).
Sean
N = {1, 2,3,..., n} el conjunto de nodos de la red.
Cok= Conjunto de nodos que se han enlazado de forma permanente en la
iteracin k
Cok= Conjunto de nodos que hacen falta por enlazarse de forma permanente.
PASO CERO (0): CONCEPTUALIZACIN DEL ALGORITMO
Definir los conjuntos C0 = {} y 0 = {N}, es decir que antes del paso 1 no se han
enlazado de forma permanente nodo alguno, y por ende el conjunto que
representa a los nodos que hacen falta por enlazarse de forma permanente es
igual a la cantidad de nodos que existen en la red.
PASO 1:
Se debe de escoger de manera arbitraria un nodo en el conjunto 0 llamado i el
cual ser el primer nodo permanente, a continuacin se debe de actualizar el
conjunto C1 = {i}, que significa que al tiempo en que el conjunto C 1 gana el
elemento i el conjunto 0 pierde el elemento i por ende ahora ser igual a 1 = N {i}, adems se debe actualizar el subndice de los conjuntos k, el cual ahora ser
igual a 2.
PASO 2: PASO GENERAL "K"
Se debe de seleccionar un nodo j del conjunto K-1 ("k-1" es el subndice que
indica que se est haciendo referencia al conjunto de la iteracin inmediatamente
anterior) el cual tenga el arco o ramal con menor longitud con uno de los nodos
que se encuentran en el conjunto de nodos de enlace permanente C K-1. Una vez
seleccionado se debe de enlazar de forma permanente lo cual representa que
pasa a formar parte del conjunto de enlaces permanentes y deja de formar parte
del conjunto que todava se debe conectar para lograr la expansin. Al actualizar
el algoritmo en este paso los conjuntos deben de quedar de la siguiente forma.

CK = CK-1 + {j} mientras que K = K-1 - {j}

El paso general que define k que al mismo tiempo representa a las iteraciones
debe de ejecutarse toda vez que el conjunto K no sea vaco, cuando este
conjunto sea igual a vaco se tendr el rbol de expansin mnima.
El entendimiento del algoritmo desde el punto de vista algebraico no es quiz el
ms simple, sin embargo mediante el ejemplo grfico se ver que es un algoritmo
muy sencillo de elaborar.
RESOLUCIN DE UN PROBLEMA DE RBOL DE EXPANSIN MNIMA
EL PROBLEMA
La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contar con
la urbanizacin de ms de 7 proyectos habitacionales que se ubicarn a las
afueras de la ciudad. Dado que el terreno en el que se construir no se encontraba
hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal
no cuenta con la infraestructura necesaria para satisfacer las necesidades de
servicios pblicos en materia de suministro de agua. Cada uno de los proyectos de
vivienda inici la construccin de un nodo de acueducto madre, el cual cuenta con
las conexiones de las unidades de vivienda propias de cada proyecto (es decir que
cada nodo madre solo necesita estar conectado con un ducto madre del
acueducto municipal para contar con su suministro). El acueducto municipal al ver
la situacin del plan parcial debe de realizar las obras correspondientes a la
instalacin de ductos madres que enlacen todos los nodos del plan con el nodo
Melndez (nodo que se encuentra con suministro de agua y que no pertenece al
plan parcial de vivienda, adems es el ms cercano al mismo), la instalacin de
los ductos implica obras de excavacin, mano de obra y costos de los ductos
mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las
distancias existentes (dadas en kilmetros) correspondientes a las rutas factibles
capaces de enlazar los nodos del plan parcial se presentan a continuacin.
Adems la capacidad de bombeo del nodo Melndez es ms que suficiente para
satisfacer las necesidades de presin que necesita la red madre.

El acueducto municipal le contacta a usted para que mediante sus conocimientos

en teora de redes construya una red de expansin que minimice la longitud total
de ductos y que enlace todos los nodos del plan parcial de vivienda.
PASO 0:
Se definen los conjuntos iniciales C 0 = {} que corresponde al conjunto de nodos
enlazados de forma permanente en la iteracin indicada en el subndice y 0 = {N
= 1, 2, 3, 4, 5, 6, 7,8} que corresponde al conjunto de nodos pendientes por
enlazar de manera permanente en la iteracin indicada en el subndice.
PASO 1:
Se debe definir de manera arbitraria el primer nodo permanente del conjunto 0,
en este caso escogeremos el nodo 1 (puede ser cualquier otro), que
algebraicamente se representa con la letra i, se procede a actualizar los conjuntos
iniciales, por ende C1 = {i} = {1} y 0 = {N - i} = {2, 3, 4, 5, 6, 7,8},
actualizamos k por ende ahora ser igual a 2.
PASO 2:
Ahora se debe seleccionar el nodo j del conjunto K-1 (es decir del conjunto del
paso 1) el cual presente el arco con la menor longitud y que se encuentre
enlazado con uno de los nodos de enlace permanente del conjunto Ck-1 en el cual

ahora solo se encuentra el nodo 1 (es decir que se debe de encontrar un nodo que
tenga el arco de menor longitud enlazado al nodo 1).

Los arcos o ramales de color naranja representan los arcos que enlazan
el conjunto K-1(es decir del conjunto del paso 1, recordemos que K en este paso
es igual a 2, por ende K-1= 1) con los nodos de enlace permanente del conjunto
Ck-1 en el cual ahora solo se encuentra el nodo 1, por ende ahora solo falta
escoger el de menor longitud, que en este caso es el arco cuya longitud es 2, que
enlaza de forma permanente ahora el nodo 2.
Al actualizar los conjuntos quedan as:
C2 = {1,2} y 2 = {3, 4, 5, 6, 7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteracin. Ahora se seleccionar un nuevo nodo j del conjunto 2que presente el
enlace (ramal o arco) de menor longitud con los nodos que se encuentran en el
conjunto C2.

Los arcos de color naranja representan los enlaces posibles y dado que existe
empate entre las menores longitudes se elige de manera arbitraria, en este caso
se representa nuestra eleccin con un arco de color verde, enlazando de forma
permanente ahora el nodo 4.
Al actualizar los conjuntos quedan as:
C3 = {1, 2,4} y 3 = {3, 5, 6, 7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteracin.

Lo que representan los arcos naranja y verde es ya conocido, ahora la lnea azul
interrumpida ir trazando nuestro rbol de expansin final. Dado a que el arco
menor es el de longitud 3, ahora se enlazar de manera permanente el nodo 5.
Al actualizar los conjuntos quedan as:
C4 = {1, 2, 4,5} y 4 = {3, 6, 7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteracin.

Ahora se enlazar de manera permanente el nodo 7.

Al actualizar los conjuntos quedan as:
C5 = {1, 2, 4, 5,7} y 5 = {3, 6,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteracin.

www.in
genieriaindustrialonline.com
Ahora se enlazar de manera permanente el nodo 6.
Al actualizar los conjuntos quedan as:
C6 = {1, 2, 4, 5, 7,6} y 6 = {3,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteracin.

www.in
genieriaindustrialonline.com
Se rompen los empates de forma arbitraria, ahora se enlazar de manera
permanente el nodo 3.
Al actualizar los conjuntos quedan as:
C7 = {1, 2, 4, 5, 7, 6,3} y 7 = {8}
Ahora se procede a actualizar k ya que se procede a efectuar la ltima iteracin.

Ahora se enlazar de manera permanente el nodo 8.

Al actualizar los conjuntos quedan as:

C8 = {1, 2, 4, 5, 7, 6, 3,8} = {N} y 8 = {}
Por ende se ha llegado al rbol de expansin mnima

rbol que presenta una longitud total minimizada de 21 kilmetros de ductos.

RESOLUCIN DEL PROBLEMA DEL RBOL EXPANSIN MNIMA MEDIANTE

4.4. Uso de software

WINQSB
Como hemos mencionado en mdulos anteriores la existencia de herramientas de
resolucin de problemas de programacin matemtica como Wons dejan que el
aprendizaje de la resolucin manual de los algoritmos de redes se justifique solo
para fines acadmicos o de profundizacin. Por ende una vez vista la metodologa
manual de resolucin del algoritmo atinente al rbol de expansin mnima se hace
necesario en aras de eficiencia mostrar la resolucin de este tipo de problemas
mediante Wons.

El primer paso para resolver un problema de transporte mediante Wons es

ingresar al mdulo Network Modelan.
EL PROBLEMA
La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contar con
la urbanizacin de ms de 7 proyectos habitacionales que se ubicarn a las
afueras de la ciudad. Dado que el terreno en el que se construir no se encontraba
hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal
no cuenta con la infraestructura necesaria para satisfacer las necesidades de
servicios pblicos en materia de suministro de agua. Cada uno de los proyectos de
vivienda inici la construccin de un nodo de acueducto madre, el cual cuenta con
las conexiones de las unidades de vivienda propias de cada proyecto (es decir que
cada nodo madre solo necesita estar conectado con un ducto madre del
acueducto municipal para contar con su suministro). El acueducto municipal al ver
la situacin del plan parcial debe de realizar las obras correspondientes a la
instalacin de ductos madres que enlacen todos los nodos del plan con el nodo
Melndez (nodo que se encuentra con suministro de agua y que no pertenece al

plan parcial de vivienda, adems es el ms cercano al mismo), la instalacin de

los ductos implica obras de excavacin, mano de obra y costos de los ductos
mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las
distancias existentes (dadas en kilmetros) correspondientes a las rutas factibles
capaces de enlazar los nodos del plan parcial se presentan a continuacin.
Adems la capacidad de bombeo del nodo Melndez es ms que suficiente para
satisfacer las necesidades de presin que necesita la red madre.

INGRESANDO A WINQSB
El primer paso para resolver un problema de transporte mediante Wons es
ingresar al mdulo Network Modelan.

Luego debemos seleccionar la opcin Mnima Spinning Trae (rbol de Expansin

Mnima). Adems en este submen debemos de especificar el nombre del
problema y el nmero de nodos. En nuestro caso el nmero de nodos es igual a 8,
luego clic en OK.
Una vez se realiza el paso anterior se abrir una ventana en la cual aparecer la
siguiente matriz:

En esta matriz se deben de consignar los valores de los ramales que unen las
conexiones entre los nodos correspondientes, segn el contexto de nuestro
problema se deben de consignar las distancias entre los nodos si es que dichas
conexiones existen de lo contrario en caso que la conexin no exista se debe dejar
la celda en blanco. Hay que tener en cuenta que las distancias entre los nodos en
este caso son exactamente conmutativas, es decir que si el nodo fuente es 2 y el
destino es 4 la distancia existente entre estos es exactamente igual a la distancia
existente entre un nodo fuente 4 y un nodo destino 2, sin embargo esta propiedad
debe de especificarse en la matriz consignando los valores correspondientes a
una conexin dos veces, es decir en la celda [Fromm 1 - To 4] se debe de
consignar la distancia 6, adems debe de consignarse la misma distancia en la
celda [Fromm 4 - To 1].

Luego damos clic en Salve and Analice y tendremos la siguiente ventana solucin
inmediatamente.

Podemos cotejar los resultados con los obtenidos de manera manual, 21

kilmetros de ductos es la distancia total una vez ejecutado el algoritmo del rbol
de Expansin Mnima.
ALGORITMO DE LA RUTA MS CORTA
El nombre que distingue este conjunto de problemas de por s es bastante
sugestivo, existen de forma manual algoritmos capaces de resolver tanto
problemas de redes que presentan ciclos como de redes que no, entre los ms
conocidos se encuentran los algoritmos de Hijastra y Floyd siendo el segundo ms
general que el primero. Sin embargo la complejidad de los algoritmos, en la
prctica la complejidad que alcanzan las redes a ser resueltas mediante el

algoritmo de la ruta ms corta, y las herramientas de resolucin de problemas de

programacin matemtica hacen que la enseanza de dichos algoritmos manuales
sea muy ineficiente.
Ya en un mdulo anterior Problema de Transbordo se ha planteado la resolucin
del algoritmo de la ruta ms corta mediante programacin lineal, por esta razn en
este espacio nos enfocaremos en efectuar la solucin mediante Wons con la
facilidad que caracteriza al software.
RESOLUCIN DEL ALGORITMO DE LA RUTA MS CORTA MEDIANTE
WINQSB
El mdulo del Wons que permite la resolucin del algoritmo de la ruta ms corta es
el Network Modelan, el cual utiliza una interfaz muy sencilla en forma de matriz en
la cual hay que ingresar el valor de los ramales (dependiendo del contexto este
valor puede representar distancias, tiempo, costos etc...) correspondiente a cada
relacin de un nodo con otro.
EL PROBLEMA
Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra
ubicada en el nodo 1, se conoce de antemano que el minero permanece atrapado
en el nodo 9, para llegar a dicho nodo hay que atravesar una red de tneles que
van conectados entre s. El tiempo de vida que le queda al minero sin recibir
auxilio es cada vez menor y se hace indispensable hallar la ruta de acceso al nodo
9 ms corta. Las distancias entre nodos de la mina se encuentran en la siguiente
grfica dadas en cientos de metros. Resuelva mediante cualquier paquete de
herramientas de investigacin operativa que permita establecer la ruta ms corta
para poder as auxiliar al minero.

PASO A PASO
Primero se debe ingresar al mdulo Network Modelan del paquete Wons, una vez
nos encontremos en este aparecer el men que se muestra en la siguiente
grfica, men en el cual tendremos que seleccionar la opcin Shorts Pat
Problema (Problema de la ruta ms corta).

Adems en este men emergente debemos de ingresar la cantidad de nodos que

conforman la red del problema y tenemos la posibilidad de asignarle un nombre al
mismo, en nuestro caso la cantidad de nodos de la red es igual a 9; clic en OK y
aparecer la siguiente ventana.

En esta ventana se debe ingresar la magnitud de cada ramal correspondiente a

cada relacin entre los nodos, tal como veremos a continuacin.

Damos clic en Salve and Analice y tendremos un men emergente en el cual

tendremos que seleccionar el nodo fuente y el nodo destino, tal como se muestra
en la siguiente grfica.

Una vez efectuada la seleccin tendremos la opcin de ver el tabulado final y la

opcin de ver un paso a paso grfico; para el tabulado final clic en SOLVE y para
el paso a paso clic en SOLVE AND DISPLAY STEPS.

Podemos cotejar la solucin que obtuvimos al plantear este problema como un

modelo de transbordo con esta solucin. La eficiencia se encuentra determinada
en escoger la herramienta adecuada para resolver el problema planteado.