Unidad 4

INSTITUTO TECNOLGICO DE VILLAHERMOSA
Ingeniera Civil
INSTITUTO TECNOLGICO DE VILLAHERMOSA
Departamento:
CIENCIAS DE LA TIERRA
Asignatura:
MODELOS DE OPTIMIZACIN DE RECURSOS
Unidad:
4
Tema:
MODELO DE FLUJOS EN REDES
Autores:
Alejo Flix Samuel Arturo

Carrillo Alfonso Eduardo
Ramn Hernndez Nallely
Catedrtico:
Ing. Juan Sols Hernndez
VILLAHERMOSA, TABASCO, 02 DE MAYO DEL 2017

NDICE
INTRODUCCIN ................................................................................................... 1
4. MODELOS DE FLUJOS EN REDES.................................................................. 2
4.1 EL MODELO DEL CAMINO .......................................................................... 4
4.2 EL MODELO DE FLUJO MXIMO ............................................................. 10
4.3 EL MODELO DEL RBOL DE EXPANSIN MNIMA ................................. 18
4.4 USO DE SOFTWARE ................................................................................. 21
CONCLUSIN ..................................................................................................... 23
GLOSARIO DE TRMINO ................................................................................... 24
ANEXOS .............................................................................................................. 27
BIBLIOGRAFA .................................................................................................... 41
INTRODUCCIN
Las tcnicas de flujo de redes estn orientadas a optimizar situaciones vinculadas
a las redes de transporte, redes de comunicacin, sistema de vuelos de los
aeropuertos, rutas de navegacin de los cruceros, estaciones de bombeo que
transportan fluidos a travs de tuberas, rutas entre ciudades, redes de conductos y
todas aquellas situaciones que puedan representarse mediante una red donde los
nodos representan las estaciones o las ciudades, los arcos los caminos, las lneas
areas, los cables, las tuberas y el flujo lo representan los camiones, mensajes y
fluidos que pasan por la red. Con el objetivo de encontrar la ruta ms corta si es una
red de caminos o enviar el mximo fluido si es una red de tuberas.
Cuando se trata de encontrar el camino ms corto entre un origen y un destino, la
tcnica, algoritmo o el modelo adecuado es el de la ruta ms corta; aunque existen
otros modelos de redes como el rbol de expansin mnima, flujo mximo y flujo de
costo mnimo cada uno abarca un problema en particular. En este trabajo se
mencionan los modelos de redes existentes y los problemas que abarca cada uno
de ellos, adems se describen los algoritmos que aplican estos modelos para
encontrar la solucin ptima al problema. Utilizando la terminologa utilizada para
representarlos como una red.
1
4. MODELOS DE FLUJOS EN REDES
MODELOS DE REDES
Los problemas de optimizacin de redes se pueden representar en trminos

generales a travs de uno de estos cuatro modelos:
Modelo de minimizacin de redes (Problema del rbol de mnima expansin).
Modelo de la ruta ms corta.
Modelo del flujo mximo.
Modelo del flujo del costo mnimo.
MODELO DE MINIMIZACIN DE REDES

El modelo de minimizacin de redes o problema del rbol de mnima expansin
tiene que ver con la determinacin de los ramales que pueden unir todos los nodos
de una red, tal que minimice la suma de las longitudes de los ramales escogidos.
No se deben incluir ciclos en la solucin del problema.
Para crear el rbol de expansin mnima tiene las siguientes caractersticas:
1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se

proporcionan las ligaduras potenciales y la longitud positiva para cada una si se
inserta en la red. (Las medidas alternativas para la longitud de una ligadura
incluyen distancia, costo y tiempo.)
2. Se desea disear la red con suficientes ligaduras para satisfacer el requisito de
que haya un camino entre cada par de nodos.
3. El objetivo es satisfacer este requisito de manera que se minimice la longitud
total de las ligaduras insertadas en la red.
Una red con n nodos requiere slo (n-1) ligaduras para proporcionar una trayectoria
entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal manera que las
redes resultantes formen un rbol de expansin. Por tanto, el problema es hallar el
rbol de expansin con la longitud total mnima de sus ligaduras.
Algoritmo para construir el rbol de expansin mnima:
2
1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir, se
agrega una ligadura) al nodo distinto ms cercano.
2. Se identifica el nodo no conectado ms cercano a un nodo conectado y se
conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este
paso se repite hasta que todos los nodos estn conectados.
Empates: los empates para el nodo ms cercano distinto (paso 1) o para el nodo
no conectado ms cercano (paso 2), se pueden romper en forma arbitraria y el
algoritmo debe llegar a una solucin ptima. No obstante, estos empates son
seal de que pueden existir (pero no necesariamente) soluciones optimas
mltiples. Todas esas soluciones se pueden identificar si se trabaja con las dems
formas de romper los empates hasta el final.
LA IMPORTANCIA DE LOS MODELOS DE REDES
Muchos problemas comerciales pueden ser resueltos a travs de modelos rede
El resultado de un problema de redes garantiza una solucin entera, dada su

estructura matemtica. No se necesitan restricciones adicionales para obtener este
tipo de solucin.
Problemas de redes pueden ser resueltos por pequeos algoritmos, no importando

el tamao del problema, dada su estructura matemtica.
3
4.1 EL MODELO DEL CAMINO
Definicin del Problema
Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.
Arcos bi-direccionales conectan los nodos i y j con distancias mayores que cero, dij
Se desea encontrar la ruta de mnima distancia que conecta el nodo 1 con el nodo
n.
MODELO DE LA RUTA MS CORTA
Considere una red conexa y no dirigida con dos nodos especiales llamados origen
y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa.
El objetivo es encontrar la ruta ms corta (la trayectoria con la mnima distancia
total) del origen al destino.
Se dispone de un algoritmo bastante sencillo para este problema. La esencia del
procedimiento es que analiza toda la red a partir del origen; identifica de manera
sucesiva la ruta ms corta a cada uno de los nodos en orden ascendente de sus
distancias (ms cortas), desde el origen; el problema queda resuelto en el momento
de llegar al nodo destino.
El mtodo de la ruta ms corta es un mtodo de programacin lineal, que permite

buscar la solucin a un problema de optimizacin que resulte de una combinatoria
y de diferentes aplicaciones, el objetivo de este mtodo esta en encontrar rutas
cortas o de menor costo, segn sea el caso, que va desde un nodo especifico
hasta cada uno de los dems nodos de la red. En este sentido un nodo es una
representacin grfica en forma de circulo, este nodo es muy importante ya que
denota los orgenes y destinos del problema que se realice, asimismo una red
representa un conjunto de puntos y lneas que conectan pares de puntos, estos
puntos son los que llamaremos nodos y las lneas seran las aristas., por ejemplo:
4
FIGURA1. Ejemplo De NODOS Y ARCOS
Un ejemplo simple para aplicar a este tipo de problemas sera el viaje de una
persona desde un estado a ciudad el cual pudiese tener varias alternativas, segn
el inters de la persona, bien sea para ir ms rpido o llegar de manera econmica
segn sus recursos, para el primer caso se minimizara la distancia y para el
segundo caso el costo, en cualquier caso el objetivo consistira en encontrar la
ruta ms eficiente a un menor costo, y por lo tanto tendramos que los estados
estarn representados como los nodos y las carreteras como los arcos.
IMPORTANCIA
Este mtodo es muy importante ya que por medio de este modelo se pueden
resolver de manera rpida, ya que pueden formularse como modelos de redes
obteniendo soluciones enteras sin necesidad de restricciones (aunque en algunos
casos pudieran tenerlas), asimismo se puede decir que no importa que tan grande
sea el problema se puede resolver por pequeos algoritmos. Por otra parte segn
la pgina www.ptolomeo.unam.mx en sus conceptos bsicos, capitulo 1 seala la
importancia de este mtodo:
5
El problema de la Ruta ms Corta es fundamental en muchas reas, como son:
investigacin de operaciones, ciencia de la computacin e ingeniera. Algunas de
las razones son:
I. La amplia variedad de aplicaciones prcticas como es el envo de algn

material entre dos puntos especficos de la forma ms eficiente, econmica o
rpida.
II. Existen mtodos de solucin eficientes, los cuales al ser aplicados a una
red con caractersticas especficas (a cclica y con costos no negativos), proveen
una solucin exacta a un tiempo y costo razonables.
III. Se puede utilizar como inicio en el estudio de modelos complejos de

redes, esto es, cuando no se conoce la estructura de la red se pueden aplicar
algoritmos para conocer algunas caractersticas de la red (presencia de ciclos
negativos).
IV. Se utiliza frecuentemente como sub-problemas (subrutinas) en la solucin

de problemas combinatorios y redes, as en el caso de problemas para los cuales
no existe un algoritmo de solucin exacto (p. e. problemas NP-completos), la
aplicacin de algoritmos de ruta ms corta, resultan auxiliares para encontrar una
buena solucin.
APLICACIONES
En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la vida

prctica, dentro de las que podemos mencionar:
Transporte,
Horarios de operadores telefnicos,
Planeacin de trfico urbano,
Trasbordo,
En las redes elctricas,
6
Diseo de rutas de vehculos
Telecomunicaciones,
Planeacin de inventarios,
Planeacin de produccin, entre otros.
ALGORITMO DE LA RUTA MS CORTA:
1. Objetivo de la n-sima iteracin: encontrar el n-simo nodo ms cercano al

origen. (Este paso se repetir para n=1,2, hasta que el n-simo nodo ms
cercano sea el nodo destino.)
2. Datos para la n-sima iteracin: n-1 nodos ms cercanos al origen (encontrados
en las iteraciones previas), incluida su ruta ms corta y la distancia desde el
origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos
no resueltos.)
3. Candidatos para el n-simo nodo ms cercano: Cada nodo resuelto que tiene
conexin directa por una ligadura con uno o ms nodos no resueltos proporciona
un candidato, y ste es el nodo no resuelto que tiene la ligadura ms corta. (Los
empates proporcionan candidatos adicionales.)
4. Clculo del n-simo nodo ms cercano: para cada nodo resuelto y sus
candidatos, se suma la distancia entre ellos y la distancia de la ruta ms corta
desde el origen a este nodo resuelto. El candidato con la distancia total ms
pequea es el n-simo nodo ms cercano (los empates proporcionan nodos
resueltos adicionales), y su ruta ms corta es la que genera esta distancia.
Anexo 1
El Problema del Camino ms Corto

El problema es determinar la mejor manera de cruzar una red para encontrar la forma
ms econmica posible desde un origen a un destino dado. Suponga que en una red
dada existen m nodos y n arcos (bordes) y un costo Cij asociado con cada arco (i a j)
7
en la red. Formalmente, el problema del camino ms corto (CC) es encontrar el camino
ms corto (menor costo) desde el nodo de comienzo 1 hasta el nodo final m. El costo
del camino es la suma del costo de cada arco recorrido. Defina las variables binarias
Xij, donde Xij =1 si el arco (i a j) es sobre el CC y Xij = 0 de lo contrario. Existen dos
nodos especiales llamados origen y destino. El objetivo es encontrar el camino ms
corto entre el origen y el destino.
En la red siguiente, varios costos son asignados para el camino que va de un nodo
a otro. Por ejemplo, el costo de ir desde el nodo 2 al 4 es 6. La funcin objetivo
considera los costos de moverse de un nodo a otro, o de un origen a un destino. Las
restricciones estn divididas en tres grupos. La restriccin del nodo de origen dice que
debe dejar el nodo 1 para ir al 2 o 3. La restriccin del nodo intermedio dice que si
siempre que se dirija a un nodo usted deber dejar ese nodo. El nodo de destino es
similar al nodo de origen dado que se puede alcanzar este nodo solo desde los nodos
vecinos.
Considere la siguiente red dirigida (para una red indirecta, haga que los arcos estn
dirigidos en ambas direcciones, luego aplique la misma formulacin. Note que en este
caso usted tiene Xij y Xji variables). El objetivo es encontrar el camino ms corto desde
el nodo 1al nodo 7.
8
Luego de correr el problema en cualquier paquete que solucione programacin lineal,
los resultados son:
Ir desde 1 hasta el 3
Este es el camino ms corto con un total de 22 unidades de longitud.
Anexo 2
9
4.2 EL MODELO DE FLUJO MXIMO
Modelo de Flujo Mximo

Existe un flujo que viaja desde un nico lugar de origen hacia un nico lugar de
destino a travs de arcos que conectan nodos intermediarios. Los arcos tienen
una capacidad mxima de flujo y se trata de enviar desde la fuente al destina la
mayor cantidad posible de flujo.
Hay problemas donde lo importante es la cantidad de flujo que pasa a travs de la

red como por ejemplo: en las lneas de oleoductos, redes elctricas o de transmisin
de datos. Por esta razn en dichos problemas se determina el flujo mximo que
pasa a travs de una red.
Se trata de enlazar un nodo fuente y un nodo destino a travs de una red de arcos
dirigidos. Cada arco tiene una capacidad mxima de flujo admisible. El objetivo es
el de obtener la mxima capacidad de flujo entre la fuente y el destino.
Caractersticas:
1. Todo flujo a travs de una red conexa dirigida se origina en un nodo, llamado
fuente, y termina en otro nodo llamado destino.
2. Los nodos restantes son nodos de trasbordo.
10
3. Se permite el flujo a travs de un arco slo en la direccin indicada por la flecha,
donde la cantidad mxima de flujo est dado por la capacidad del arco. En la
fuente, todos los arcos sealan hacia fuera. En el destino, todos sealan hacia
el nodo.
4. El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta
cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la
cantidad que sale de la fuente o la cantidad que entra al destino.
El problema de flujo mximo se puede formular como un problema de programacin

lineal, se puede resolver con el mtodo simplex y usar cualquier software. Sin
embargo, se dispone de un algoritmo de trayectorias aumentadas mucho ms
eficientes. El algoritmo se basa en dos conceptos intuitivos, el de red residual y el
de trayectoria aumentada.
Algoritmo de la trayectoria de aumento para el problema de flujo mximo:
1. Se identifica una trayectoria de aumento encontrando alguna trayectoria

dirigida del origen al destino en la red residual, tal que cada arco sobre esta
trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los
flujos netos asignados constituyen un patrn del flujo ptimo).
2. Se identifica la capacidad residual c* de esta trayectoria de aumento
encontrando el mnimo de las capacidades residuales de los arcos sobre esta
trayectoria. Se aumenta en c* el flujo de esta trayectoria.
3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de
aumento. Se aumenta en c* la capacidad residual de cada arco en la direccin
opuesta en esta trayectoria. Se regresa la paso 1.
Problema del Flujo Mximo
En una red con flujo de capacidades en los arcos, el problema es determinar el flujo
mximo posible proveniente de los orgenes de forma tal de ahogar las capacidades
de flujos de los arcos.
11
Considere una red con m nodos y n arcos con un flujo simple de bienes. Denote el
arco de flujo (i a j) como Xij. Asociamos cada arco a una capacidad de flujo, kij. En esta
red, deseamos encontrar el flujo total mximo en la red, F, del nodo 1 al nodo m.
En la formulacin de la programacin lineal, el objetivo es maximizar F.
El monto que parte del origen por varias rutas.
Para cada nodo intermedio, lo que entra debe ser igual a lo sale.
En algunas rutas los flujos pueden tomar ambas direcciones.
La capacidad que puede ser enviada a una direccin en particular tambin es

mostrada en cada ruta.
12
Luego de resolver este problema de PL mediante el uso de LINDO (entre otros
software), obtenemos los siguientes resultados:
Enviar 10 unidades de 1 a 2
13
El flujo mximo es F= 17 unidades.
El Problema Dual de Flujo Mximo:
El problema dual para el ejemplo numrico anterior es:
Min 10Y12 + 10Y13 + Y23 + Y32 + 6Y26 + 4Y36 + 4Y63 + 8Y24

3Y64 + 3Y46 + 12Y35 + 2Y65 + 2Y56 + 8Y75 + 7Y47 + 2Y67
sujeto a:
X2 - X1 + Y12 0, X3 - X1 + Y13 0, X3 - X2 + Y23 0,

X3 - X2 + Y32 0, X6 - X2 + Y26 0, X6 - X3 + Y36 0,
X3 - X6 + Y63 0, X4 - X2 + Y24 0, X4 - X6 + Y64 0
X6 - X4 + Y46 0, X5 - X3 + Y35 0, X5 - X6 + Y65 0,
X6 - X5 + Y56 0, X5 - X7 + Y75 0, X7 - X4 + Y47 0,
X7 - X6 + Y67 0, X1 - X7 1, y
Yij 0, y todos los Xi son variables libres.
La formulacin dual sugiere que se intente asignar flujos a arcos de misma manera
que para cada arco, la diferencia en valores en el nodo inicial y el nodo final excede
el valor agregado.
14
Ejemplo
Nos permite conocer (calcular) la mxima cantidad de cualquier artculo o

informacin que podemos transportar desde un origen hasta un destino.
Pasos a seguir:
Primer paso: Elegir una ruta arbitraria.
Segundo paso: En dicha ruta escoger aquel ramal de menor flujo en ese sentido y
transportar por esa ruta la cantidad escogida.
Hacer esto repetitivamente hasta que no sea posible encontrar una ruta con
capacidad de flujo.
15
16
Ejemplo: El origen puede despachar 28 unidades y el destino puede recibir 22
unidades, pero por las restricciones, el destino solo puede recibir 19 unidades en la
ruta AB- BC CD DF FG
17
4.3 EL MODELO DEL RBOL DE EXPANSIN MNIMA
Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin
formar un loop.
El rbol de expansin mnima es apropiado para problemas en los cuales la redundancia es

expansiva, o el flujo a lo largo de los arcos se considera instantneo.
REDES (ARBOL DE EXPANSION MINIMA)
Modelo de minimizacin de redes
El modelo de minimizacin de redes o problema del rbol de mnima expansin

tiene que ver con la determinacin de los ramales que pueden unir todos los nodos
de una red, tal que minimice la suma de las longitudes de los ramales escogidos.
No se deben incluir ciclos en la solucin del problema.
Para crear el rbol de expansin mnima tiene las siguientes caractersticas:
Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan
las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red.
(Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo
y tiempo.)
Se desea disear la red con suficientes ligaduras para satisfacer el requisito de que
haya un camino entre cada par de nodos.
El objetivo es satisfacer este requisito de manera que se minimice la longitud total

de las ligaduras insertadas en la red.
Una red con n nodos requiere slo (n-1) ligaduras para proporcionar una
trayectoria entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal
manera que las redes resultantes formen un rbol de expansin. Por tanto, el
problema es hallar el rbol de expansin con la longitud total mnima de sus
ligaduras.
Algoritmo para construir el rbol de expansin mnima:
18
Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir, se
agrega una ligadura) al nodo distinto ms cercano.
Se identifica el nodo no conectado ms cercano a un nodo conectado y se

conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso
se repite hasta que todos los nodos estn conectados.
Empates: los empates para el nodo ms cercano distinto (paso 1) o para el nodo
no conectado ms cercano (paso 2), se pueden romper en forma arbitraria y el
algoritmo debe llegar a una solucin ptima.
No obstante, estos empates son seal de que pueden existir (pero no

necesariamente) soluciones optimas mltiples.
Todas esas soluciones se pueden identificar si se trabaja con las dems formas de
romper los empates hasta el final.
EJEMPLO
La ciudad de Vancouver est planificando el desarrollo de una nueva lnea en

sistemas de trnsito. El sistema debe unir 8 residencias y centros comerciales. El
distrito metropolitano de trnsito necesita seleccionar un conjunto de lneas que
conecten todos los centros a un mnimo costo. La red seleccionada debe permitir:
Factibilidad de las lneas que deban ser construidas. Mnimo costo posible por lnea.
19
Solucin - Analoga con un problema de redes
El algoritmo que resuelve este problema es un procedimiento muy fcil (trivial).
Corresponde a una categora de algoritmos vidos.
Algoritmo:
Comience seleccionando el arco de menor longitud.
En cada iteracin, agregue el siguiente arco de menor longitud del conjunto de arcos
disponibles, tomando la precaucin de no formar ningn loop.
El algoritmo finaliza cuando todos los nodos estn conectados.
20
4.4 USO DE SOFTWARE
Anlisis de Sensibilidad para los Modelos de Redes
La familia de un clsico problema de optimizacin de redes incluye los siguientes
prototipos de modelos: asignacin, camino crtico, flujo mximo, camino ms corto, y
transporte. A pesar de que es bien conocido que este tipo de problemas se pueden
modelar como programacin lineal, normalmente nunca se hace. Debido a la
ineficiencia y complejidad relativa del mtodo simplex (primal, dual y otras variaciones)
para modelos de redes, este problema es tratado por uno de ms de 400 algoritmos
especiales.
Esto conlleva a muchas dificultades. Las soluciones de los algoritmos no estn

unificadas y cada algoritmo usa una estrategia diferente para explorar la estructura
especial de un problema especfico. Adicionalmente, pequeas variaciones en el
problema tales como la adicin de una restriccin aparte, o ndices mltiples, destruye
la estructura especial y obliga a re comenzar el algoritmo. Adems, estos algoritmos
obtienen soluciones eficientes al costo de la astucia gerencial, como la solucin final
de estos algoritmos que no tienen la informacin suficiente para realizar un anlisis de
sensibilidad.
Otro acercamiento es adoptar el simplex para los problemas de optimizacin de

redes a travs del simplex de redes. Esto proporciona la unificacin de varios
problemas, pero mantiene todas las ineficiencias del simplex as como tambin la
mayora de las inflexibilidades de las redes para manejar problemas tales como las
restricciones aparte. Al igual que el anlisis ordinario de sensibilidad (AOS),
ampliamente disponible en la tabular simplex, ha sido recientemente transferido a
redes simplex.
Advertencia: las soluciones de computadoras para problemas de redes son vlidas,

sin embargo, los resultados de sensibilidad producidos podran no ser vlidos. Esto
se debe al hecho de que, entre otras cosas, estos problemas son PL de enteros, y
cualquier restriccin en cualquiera de estos modelos es una restriccin redundante.
21
Dado que el camino tomado por la rama- atadura (Branch-and-bound), la rama-
corte (Branch-and-cut) y otros mtodos pueden ser muy diferentes para los pequeos
cambios en el valor de los parmetros, hemos desarrollado, vea las referencias,
nuevas soluciones algortmicas, las cuales nos permiten realizar varias formas de
anlisis de sensibilidad.
Anlisis de Perturbacin de Costos: : Conjunto de Perturbacin General, Anlisis

de Sensibilidad Paramtrico, Anlisis de Sensibilidad Ordinario, Regla del 100%,
Anlisis de Tolerancia.
Anlisis de la Capacidad de Perturbacin del Arco: Conjunto de Perturbacin

General, Anlisis de Sensibilidad Paramtrico, Anlisis de Sensibilidad Ordinario,
Regla del 100%, Anlisis de Tolerancia.
Anlisis de Perturbacin de Oferta y Demanda: Conjunto de Perturbacin

General, Anlisis de Sensibilidad Paramtrico, Anlisis de Sensibilidad Ordinario,
Regla del 100%, Anlisis de Tolerancia.
22
CONCLUSIN
Utilice el algoritmo adecuado para encontrar la ruta ms corta a travs de la red que
se muestra a continuacin, en donde los nmeros representan las distancias reales
entre los nodos correspondientes. Formule el problema de la ruta ms corta como
uno de PL.
Los modelos de optimizacin de redes constituyen una herramienta muy sencilla

para la encontrar la solucin ptima a los problemas de flujo de redes, porque
proporcionan algoritmos fciles de comprender y aplicar que comparados con el
mtodo simplex disminuyen el nmero de iteraciones que resuelven el problema. Si
se aplicara el mtodo simplex en un problema de distribucin o de redes, tendramos
muchas variables y restricciones en el modelo y se tendra que utilizar herramientas
computacionales para encontrar la solucin ptima de una forma rpida, ahora con
los modelos de redes solo habra que aplicar las iteraciones al grafo que origina la
representacin de la red del problema y luego aplicar el algoritmo que corresponde,
que puede ser el algoritmo de la ruta ms corta, algoritmo para encontrar el rbol
de expansin mnima, algoritmo de la trayectoria de aumento o el algoritmo de flujo
mximo.
Aunque los problemas de flujo de costo mnimo y el de la ruta ms corta pueden
formularse como modelos de programacin lineal para luego aplicar el mtodo
simplex, no es conveniente su utilizacin. Por otro lado solucionar el problema
utilizando redes mejora la eficiencia de los clculos.
23
GLOSARIO DE TRMINO
Red: Una red consiste en un conjunto de puntos y un conjunto de lneas que unen
ciertos pares de puntos. Los puntos se llaman nodos (o vrtices). Las lneas se
llaman arcos (o ligaduras, aristas o ramas).
Los arcos se etiquetan para dar nombres a los nodos en sus puntos terminales, por
ejemplo, AB es el arco entre los nodos A Y B.
En un problema de programacin lineal, las redes pueden representar un conjunto

de estaciones, campos petrolferos, almacenes, fabricas, sucursales, ciudades,
interconectadas entre s a travs de caminos, conductos, tuberas que permiten
fluir productos para la comercializacin o la distribucin.
Arcos Dirigidos: Se dice que un arco es dirigido cuando el arco tiene flujo en una
direccin (como en una calle de un sentido). La direccin se indica agregando una
cabeza de flecha al final de la lnea que representa el arco.
Al etiquetar un arco dirigido con el nombre de los nodos que une, siempre se coloca
primero al nodo de donde viene y despus el nodo a donde va, esto es, un arco
dirigido del nodo A al nodo B debe etiquetarse como AB y no como BA. Otra Manera
es A B.
Arcos No Dirigidos: Si el flujo a travs de un arco se permite en ambas direcciones

(como una tubera que se puede usar para bombear fluido en ambas direcciones),
se dice que es un arco no dirigido.
Tambin se les llama ligadura. Aunque se permita que el flujo a travs de un arco
no dirigido ocurra en cualquier direccin, se supone que ese flujo ser en una
direccin, en la seleccionada, y no se tendr flujos simultneos en direcciones
opuestas.
Trayectoria: Una trayectoria entre dos nodos es una sucesin de arcos distintos
que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan los
nodos O y T en la figura 1 es la sucesin de arcos OB-BD-DT (O B D T), y
viceversa.
24
Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la
distincin entre trayectorias dirigidas y trayectorias no dirigidas.
Trayectoria Dirigida: Una trayectoria dirigida del nodo i al nodo j, es una sucesin
de arcos cuya direccin (si la tienen) es hacia el nodo j, de manera que el flujo del
nodo i al nodo j, a travs de esta trayectoria es factible.
Variables binarias: Las variables binarias son un artificio matemtico que permite
que modelos de programacin no lineal se resuelvan como tal. El buen uso de las
variables binarias se convierte en una poderosa herramienta matemtica para
plantear problemas ms complejos que los que habitualmente se resuelven
acudiendo a las variables continuas.
Trayectoria No Dirigida: Una trayectoria no dirigida del nodo i al nodo j es una

sucesin de arcos cuya direccin (si la tienen) pueden ser hacia o desde el nodo j.
Con frecuencia alguna trayectoria no dirigida tendr algunos arcos dirigidos hacia el
nodo j y otros desde l (es decir, hacia el nodo i).
Ciclo: Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En la

red no dirigida que se muestra en la figura 5 existen muchos ciclos, OA-AB-BC-CO.
Red Conexa: Una red conexa es una red en la que cada par de nodos est
conectado. Se dice que dos nodos estn conectados si la red contiene al menos
una trayectoria no dirigida entre ellos. Se debe resaltar que no es necesario que
la trayectoria sea dirigida aun cuando la red sea dirigida. La figura 1 representa una
red conexa.
rbol de Expansin: es una red conexa para los n nodos, que contiene ciclos no
dirigidos. Todo rbol de expansin tiene justo n-1 arcos, ya que este es el nmero
mnimo de arcos necesarios para tener una red conexa y el mximo nmero posible
para que no haya ciclos no dirigidos.
La figura 6 representa una red conexa, la figura 7 muestra los cinco nodos de la red
conexa de la figura 6, ahora la figura 8 muestra el proceso para hacer crecer un
rbol colocando una rama a la vez, hasta obtener un rbol de expansin. En cada
25
etapa del proceso se tienen varias alternativas para el nuevo arco, por lo que la
figura 8 muestra solo una de las muchas formas de construir un rbol de expansin.
Capacidad de Arco: Es la cantidad mxima de flujo (quizs infinito) que puede

circular en un arco dirigido.
Nodo Fuente: (o nodo de origen) tiene la propiedad de que el flujo que sale del
nodo excede al flujo que entra a l.
Nodo de Trasbordo: (o nodo intermedio) satisface la conservacin del flujo, es

decir, el flujo que entra es igual al que sale.
Flujo: Circulacin de unidades homogneas de un lugar a otro.

Capacidad de flujo: es la capacidad de unidades que pueden entrar por el nodo
fuente y salir por el nodo destino.
Origen o fuente de flujo: nodo por el cual el flujo ingresa.
Destino o Sumidero de flujo: nodo por el cual el flujo sale.
26
ANEXOS
Anexo 1. EJERCICIO DE LA RUTA MS CORTA
Considere la siguiente red dirigida (para una red indirecta, haga que los arcos
estn dirigidos en ambas direcciones, luego aplique la misma formulacin. Note
que en este caso usted tiene Xij y Xji variables. El objetivo es encontrar el camino
ms corto desde el nodo 1 al nodo 7. La red sera:
Para encontrar la funcin objetivo para los costos se plantea:
MinZ(x) = 15X12+10X13+8X32 +4X35+6X24+17X27+4X45+5X47+2X56+6X67
Para hacer las ecuaciones hay que tomar en cuenta:
Entra al nodo es +
Sale del nodo es -
S.A.:
Nodo 1: X12+X13 = 1
Nodo 2: X12+X32-X24-X27 = 0
Nodo 3: X13-X32-X35 = 0
Nodo 4: X24-X47-X45 = 0
Nodo 5: X35+X45 X56 = 0
27
Nodo 6: X56-X67 = 0
Nodo 7: X27+X47+X67 = 1
WinQSB
1. Cliquear la opcin New Problem, del men File
28
2. Activar la casilla Shortest Path Problem
29
3. Llenar las casillas con los datos del problema
4. Darle clic a Solve, y mostrar el resultado.
30
Anexo 2
31
Anexo 3. EJEMPLO DEL PROBLEMA DE FLUJO MAXIMO
El nodo de origen como se puede observar es el numero 1 de color amarillo, y el

nodo de destino es el numero 5 de color azul.
Se escoge desde el nodo de origen aquel flujo que sea el mayor, en este caso es
30, y va dirigido al nodo numero 3.
32
Se identifica el nodo de transbordo como [30,1], 30 es la capacidad, y 1 es el nodo
del cual proviene la capacidad y luego repetimos todo el proceso, como si el nodo
intermediario fuese el nodo de origen. Se tiene como flujo mayor 20 del nodo
numero 3 al nodo numero 5, con el nodo de transbordo como [20,5].
Ahora que hemos llegado al nodo de destino, procedemos a calcular "k" y las
capacidades nuevas.
33
K=min(,30,20)
K=20
C13,31 =(30-20, 0+20)
C13,31 =(10, 20)
C35,53 =(20-20, 0+20)
C35,53 =(0, 20)
Luego de haber calculado las nuevas capacidades, es necesario reemplazarlas.
34
Se realiza el proceso otra vez, haciendo la ruta con los mayores flujos.
K=min(,20,40,10,20)
K=10
C12,21 =(20-10, 0+10)
C12,21 =(10, 10)
35
C23,32 =(40-10, 0+10)
C23,32 =(30, 10)
C34,43 =(10-10, 5+10)
C34,43 =(0, 15)
C45,54 =(20-10, 0+10)
C45,54 =(10, 10)
Volvemos a hacer el proceso y escogemos el camino 1,2. Como se puede

observar si se tomara rumbo del nodo 2 al nodo
3 terminara trancado, obligndose a volver al nodo origen, por lo que se toma el
camino 2,5.
K=min(,10,20)
K=10
36
C12,21 =(10-10, 10+10)
C12,21 =(0, 20)
C25,52 =(20-10, 0+10)
C25,52 =(10, 10)
Se actualizan las capacidades y procedemos a resolver de nuevo. Esta vez

agarraremos el camino de 1,3.
K=min(,10,10,10)
K=10
C13,31 =(10-10, 20+10)
C13,31 =(0, 30)
37
C32,23 =(10-10, 30+10)
C32,23 =(0, 40)
C25,52 =(10-10, 10+10)
C25,52 =(0, 20)
Y por ultimo escogemos el camino 1,4.
K=min(,10,10)
K=10
C14,41 =(10-10, 0+10)
C14,41 =(0, 10)
C45,54 =(10-10, 10+10)
C45,54 =(0, 40)
38
Reemplazando las nuevas capacidades, nos queda de la siguiente forma, las
capacidades del nodo de origen quedan como 0, por lo cual seguimos a sumar a
todas las K y ahi conseguimos el flujo mximo.
Flujo Mximo = K
Flujo Mximo = 20+10+10+10+10
Flujo Mximo = 60
El flujo mximo que puede pasar del nodo origen 1 hasta el nodo destino es de 60.
Anexo 4. EJEMPLO DE MODELO DEL ARBOL DE EXPANSION.
EJEMPLO
N= {1, 2, 3, 4, 5}
A= {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}
39
Un rbol es una red conectada que puede consistir solo en un subconjunto de
todos los nodos en ella, donde no se permiten ciclos.
Un rbol de expansin es un rbol que enlaza todos los nodos de la red, tambin
sin permitir ciclos.
40
BIBLIOGRAFA
Frederick S. Hiller y Gerald J. Liberman. Investigacin De Operaciones.

McGraw-Hill. Sptima Edicin. 2002.
Hamdy A. Taha. Investigacin De Operaciones. Ediciones Alfaomega.
Cuarta Edicin. 1991.
http://profmgodoy.wordpress.com/2013/01/02/modelo-de-redes-la-ruta-mas-
corta/
www.ptolomeo.unam.mx
http://www.slideshare.net/luenfajardo/el-problema-de-la-ruta-mas-corta
Revenga, Juana M.Alonso. (2008). Flujo en Redes y Gestin de Proyectos,

Teora y ejercicios resueltos (1era ed.). Espaa.Editorial Netbiblo. Pginas
87-89.
Marcel Ruiz (2012).Problema de flujo mximo
p1/3. http://www.youtube.com/watch?v=a697qlRsLIk, recuperado
el da 31/03/2013
41
42

Unidad 4

Cargado por

Copyright:

Formatos disponibles

Unidad 4

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Unidad 4

Cargado por

Copyright:

Formatos disponibles

INSTITUTO TECNOLGICO DE VILLAHERMOSA

INSTITUTO TECNOLGICO DE VILLAHERMOSA

Alejo Flix Samuel Arturo

VILLAHERMOSA, TABASCO, 02 DE MAYO DEL 2017

4. MODELOS DE FLUJOS EN REDES.................................................................. 2

4.1 EL MODELO DEL CAMINO .......................................................................... 4

4.2 EL MODELO DE FLUJO MXIMO ............................................................. 10

4.3 EL MODELO DEL RBOL DE EXPANSIN MNIMA ................................. 18

4.4 USO DE SOFTWARE ................................................................................. 21

GLOSARIO DE TRMINO ................................................................................... 24

Los problemas de optimizacin de redes se pueden representar en trminos

MODELO DE MINIMIZACIN DE REDES

1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se

LA IMPORTANCIA DE LOS MODELOS DE REDES

Muchos problemas comerciales pueden ser resueltos a travs de modelos rede

El resultado de un problema de redes garantiza una solucin entera, dada su

Problemas de redes pueden ser resueltos por pequeos algoritmos, no importando

Definicin del Problema

Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.

MODELO DE LA RUTA MS CORTA

El mtodo de la ruta ms corta es un mtodo de programacin lineal, que permite

I. La amplia variedad de aplicaciones prcticas como es el envo de algn

III. Se puede utilizar como inicio en el estudio de modelos complejos de

IV. Se utiliza frecuentemente como sub-problemas (subrutinas) en la solucin

En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la vida

Horarios de operadores telefnicos,

Planeacin de trfico urbano,

En las redes elctricas,

Planeacin de produccin, entre otros.

ALGORITMO DE LA RUTA MS CORTA:

1. Objetivo de la n-sima iteracin: encontrar el n-simo nodo ms cercano al

El Problema del Camino ms Corto

Este es el camino ms corto con un total de 22 unidades de longitud.

Modelo de Flujo Mximo

Hay problemas donde lo importante es la cantidad de flujo que pasa a travs de la

El problema de flujo mximo se puede formular como un problema de programacin

1. Se identifica una trayectoria de aumento encontrando alguna trayectoria

Problema del Flujo Mximo

En la formulacin de la programacin lineal, el objetivo es maximizar F.

El monto que parte del origen por varias rutas.

En algunas rutas los flujos pueden tomar ambas direcciones.

La capacidad que puede ser enviada a una direccin en particular tambin es

El flujo mximo es F= 17 unidades.

El Problema Dual de Flujo Mximo:

El problema dual para el ejemplo numrico anterior es:

Min 10Y12 + 10Y13 + Y23 + Y32 + 6Y26 + 4Y36 + 4Y63 + 8Y24

X2 - X1 + Y12 0, X3 - X1 + Y13 0, X3 - X2 + Y23 0,

Yij 0, y todos los Xi son variables libres.

Nos permite conocer (calcular) la mxima cantidad de cualquier artculo o

Primer paso: Elegir una ruta arbitraria.

El rbol de expansin mnima es apropiado para problemas en los cuales la redundancia es

REDES (ARBOL DE EXPANSION MINIMA)

Modelo de minimizacin de redes

El modelo de minimizacin de redes o problema del rbol de mnima expansin

Para crear el rbol de expansin mnima tiene las siguientes caractersticas:

El objetivo es satisfacer este requisito de manera que se minimice la longitud total

Algoritmo para construir el rbol de expansin mnima:

Se identifica el nodo no conectado ms cercano a un nodo conectado y se