- Modelos de
redes - Notación y
terminología - Vista general de algunas
aplicaciones prácticas de la optimización de
redes - Ejemplos de
términos - Otras
Definiciones - Problema del flujo de coste
mínimo - Formulación del
ejemplo - Aplicación practica del
problema de flujo de costo mínimo - Problema de trasporte
(datos útiles) - Formulación de un
programa lineal - Ejercicios
- Conclusión
- Bibliografía
Las técnicas
de flujo de redes están
orientadas a optimizar situaciones vinculadas a las redes de
transporte,
redes de comunicación, sistema de vuelos
de los aeropuertos, rutas de navegación de los cruceros,
estaciones de bombeo que transportan fluidos a través de
tuberías, 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 líneas aéreas, los cables, las tuberías
y el flujo lo representan los camiones, mensajes y fluidos que
pasan por la red. Con el objetivo de
encontrar la ruta mas corta si es una red de caminos o enviar el
máximo fluido si es una red de tuberías.
Cuando se trata de encontrar el camino más corto
entre un origen y un destino, la técnica, algoritmo o el
modelo
adecuado es el de la ruta más corta; aunque existen otros
modelos de
redes como el árbol de expansión mínima,
flujo máximo y flujo de costo
mínimo 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, además se describen los algoritmos que
aplican estos modelos para encontrar la solución optima al
problema. Utilizando la terminología utilizada para
representarlos como una red.
Los problemas de optimización de redes se pueden
representar en términos generales a través de uno
de estos cuatro modelos:
- Modelo de minimización de redes (Problema del
árbol de mínima expansión). - Modelo de la ruta más corta.
- Modelo del flujo máximo.
- Modelo del flujo del costo mínimo.
Modelo de minimización de redes
El modelo de minimización de redes o problema del
árbol de mínima expansión tiene que ver con
la determinación 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 al
solución del problema.
Para crear el árbol de expansión
mínima tiene las siguientes
características:
- 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 diseñar 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 sólo (n-1) ligaduras
para proporcionar una trayectoria entre cada par de nodos. Las
(n-1) ligaduras deben elegirse de tal manera que la red
resultante formen un árbol de expansión. Por tanto
el problema es hallar el árbol de expansión con la
longitud total mínima de sus ligaduras.
Algoritmo para construir el árbol de
expansión mínima:
- Se selecciona, de manera arbitraria, cualquier nodo y
se conecta (es decir, se agrega una ligadura) al nodo distinto
más cercano. - Se identifica el nodo no conectado más 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 están conectados. - Empates: los empates para el nodo más cercano
distinto (paso 1) o para el nodo no conectado más
cercano (paso 2), se pueden romper en forma arbitraria y el
algoritmo debe llegar a una solución optima. No
obstante, estos empates son señal de que pueden existir
(pero no necesariamente) soluciones
optimas múltiples. Todas esas soluciones se pueden
identificar si se trabaja con las demás formas de romper
los empates hasta el final.
Modelo de Flujo Máximo
Se trata de enlazar un nodo fuente y un nodo destino a
través de una red de arcos dirigidos. Cada arco tiene una
capacidad máxima de flujo admisible. El objetivo es el de
obtener la máxima capacidad de flujo entre la fuente y el
destino.
Características:
- Todo flujo a través de una red conexa dirigida
se origina en un nodo, llamado fuente, y termina en otro nodo
llamado destino. - Los nodos restantes son nodos de
trasbordo. - Se permite el flujo a través de un arco
sólo en la dirección indicada por la flecha, donde
la cantidad máxima de flujo está dad por la
capacidad del arco. En la fuente, todos los arcos
señalan hacia fuera. En el destino, todos señalan
hacia el nodo. - 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 máximo se puede formular
como un problema de programación
lineal, se puede resolver con el método
símplex y usar cualquier software. Sin embargo, se
dispone de un algoritmo de trayectorias aumentadas mucho
más 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 máximo:
- 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 patrón del
flujo óptimo). - Se identifica la capacidad residual c* de esta
trayectoria de aumento encontrando el mínimo de las
capacidades residuales de los arcos sobre esta trayectoria. Se
aumenta en c* el flujo de esta trayectoria. - 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 dirección opuesta en esta
trayectoria. Se regresa la paso 1.
Modelo de la ruta más 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 más corta (la trayectoria con la
mínima 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 más corta a cada uno de los nodos en
orden ascendente de sus distancias (más cortas), desde el
origen; el problema queda resuelto en el momento de llegar al
nodo destino.
Algoritmo de la ruta más corta:
- Objetivo de la n-ésima
iteración: encontrar el n-ésimo nodo
más cercano al origen. (Este paso se repetirá
para n=1,2,… hasta que el n-ésimo nodo más
cercano sea el nodo destino.) - Datos para la n-ésima iteración:
n-1 nodos más cercanos al origen (encontrados en las
iteraciones previas), incluida su ruta más corta y la
distancia desde el origen. (Estos nodos y el origen se llaman
nodos resueltos, el resto son nodos no resueltos.) - Candidatos para el n-ésimo nodo más
cercano: Cada nodo resuelto que tiene conexión
directa por una ligadura con uno o más nodos no
resueltos proporciona un candidato, y éste es el nodo no
resuelto que tiene la ligadura más corta. (Los empates
proporcionan candidatos adicionales.) - Cálculo del n-ésimo nodo más
cercano: para cada nodo resuelto y sus candidatos, se suma
la distancia entre ellos y la distancia de la ruta más
corta desde el origen a este nodo resuelto. El candidato con la
distancia total más pequeña es el n-ésimo
nodo más cercano (los empates proporcionan nodos
resueltos adicionales), y su ruta más corta es la que
genera esta distancia.
Red: Una red consiste en un conjunto de puntos y
un conjunto de líneas que unen ciertos pares de puntos.
Los puntos se llaman nodos (o vértices). Las
líneas 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 lo nodos
A Y B.
En un problema de programación lineal, las redes pueden
representar un conjunto de estaciones, campos
petrolíferos, almacenes,
fabricas, sucursales, ciudades, interconectadas entre si a
través de caminos, conductos, tuberías que permiten
fluir productos para
la comercialización o la distribución.
Arcos Dirigidos: Se dice que un arco es dirigido
cuando el arco tiene flujo en una dirección (como en una
calle de un sentido). La dirección se indica agregando una
cabeza de flecha al final de la línea 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
después 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 AB.
Arcos No Dirigidos: Si el flujo a través
de un arco se permite en ambas direcciones (como una
tubería que se puede usar para bombear fluido en ambas
direcciones), se dice que es un arco no dirigido.
También se les llama ligadura. Aunque se
permita que el flujo a través de un arco no dirigido
ocurra en cualquier dirección, se supone que ese flujo
será en una dirección, en la seleccionada, y no se
tendrá flujos simultáneos en direcciones
opuestas.
Trayectoria: Una trayectoria entre dos nodos es
una sucesión 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 sucesión de arcos OB-BD-DT
(OB
D
T), y viceversa.
Cuando algunos o todos los arcos de una red son arcos
dirigidos, se hace la distinción entre trayectorias
dirigidas y trayectorias no dirigidas.
Trayectoria Dirigida: Una trayectoria dirigida
del nodo i al nodo j, es una sucesión de arcos cuya
dirección (si la tienen) es hacia el nodo j, de manera que
el flujo del nodo i al nodo j, a través de esta
trayectoria es factible.
Trayectoria No Dirigida: Una trayectoria no
dirigida del nodo i al nodo j es una sucesión de arcos
cuya dirección (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
están 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 Expansión: es una red
conexa para los n nodos, que contiene ciclos no dirigidos. Todo
árbol de expansión tiene justo n-1 arcos, ya que
este es el número mínimo de arcos necesarios para
tener una red conexa y el máximo numero 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 expansión. En cada 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 expansión.
Capacidad de Arco: Es la cantidad máxima
de flujo (quizás 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 Demanda:
(o nodo destino) es el caso contrario al nodo fuente, donde el
flujo que llega excede al que sale de él.
Nodo de Trasbordo: (o nodo intermedio) satisface
la conservación del flujo, es decir, el flujo que entra es
igual al que sale.
REDES DIRIGIDAS Y NO DIRIGIDAS
Red Dirigida: Es una red que tiene solo arcos
dirigidos.
En una red dirigida, un ciclo puede ser dirigido o no
dirigido, según si la trayectoria en cuestión es
dirigida o no dirigida. (Como una trayectoria dirigida
también es no dirigida, un ciclo dirigido es un ciclo no
dirigido, pero en general el inverso no es cierto.) Por ejemplo
en la figura 9 DE-ED es un ciclo dirigido. Por contrario,
AB-BC-CA no es un ciclo dirigido puesto que la dirección
del arco AC es opuesta a la de los arcos AB y BC. Por otro lado,
AB-BC-AC no es un ciclo dirigido porque ABCA es una trayectoria
no dirigida.
Red No Dirigida: Es una red donde todos sus arcos
son no dirigidos. La figura 10 representa una red no
dirigida.
VISTA GENERAL DE
ALGUNAS APLICACIONES PRÁCTICAS DE LA OPTIMIZACIÓN
DE REDES
- Diseño de redes de telecomunicación
(redes de fibra
óptica, de computadores, telefónicas, de
televisión por cable, etc.) - Diseño de redes de transporte para minimizar
el costo total de proporcionar las ligaduras (vías
ferroviarias, carreteras, etc.) - Diseño de una red de líneas de
transmisión de energía
eléctrica de alto voltaje. - Diseño de una red de cableado en equipo
eléctrico (como sistemas de
computo) para minimizar la longitud total del
cable. - Diseño de una red de tuberías para
conectar varias localidades. - Diseño de una red de tuberías de
gas natural
mar adentro que conecta fuentes del
golfo de México con un punto de entrega en
tierra con
el objetivo de minimizar el costo de construcción. - Determinación de la ruta más corta que
une dos ciudades en una red de caminos existentes. - Determinar la capacidad anual de máxima en
toneladas de una red de conductos de pasta aguada de
carbón que enlaza las minas carboneras de Wyoming con
las plantas
generadoras de electricidad
Houston. (Los conductos de pasta aguada de carbón
transportan éste bombeando agua a
través de tubos adecuadamente diseñados que
operan entre las minas de carbón y el destino
deseado.) - Determinación del programa de
costo mínimo de los campos petrolíferos a
refinerías y finalmente a los campos de
distribución. Se pueden enviar petróleo crudo y productos derivados de
la gasolina en buques tanque, oleoductos y/o camiones.
Además de la disponibilidad de la oferta
máxima en los campos petrolíferos y los
requisitos de demanda mínima en los centros de
distribución, deben tomarse en cuenta restricciones
sobre la capacidad de las refinerías y los modos de
transporte.
Se tiene la red de distribución para Distribution
Unlimited Co.
Nodos | A, B, C, D , E |
Arcos | AB, AC, AD, BC, CE, DE, ED |
Arco Dirigido | A |
Trayectoria | Entre A y D: A A A |
Trayectoria Dirigida | Entre A y E A |
Trayectoria No Dirigida | Entre B y D B |
Ciclo | DE-ED (ciclo dirigido) AB-BC-CA (ciclo no dirigido) |
Red Conexa | Si es red conexa |
Capacidad de Arco | 3, 2, 5, 3, 4, 2, 1 |
Nodo Fuente | A |
Nodo Demanda | C, D |
Nodo de Trasbordo | B |
Red Residual: Una red residual
muestra las capacidades restantes (llamadas capacidades
residuales) para asignar flujos adicionales.
Trayectoria de Aumento: Una trayectoria de
aumento es una trayectoria dirigida del nodo fuente al nodo
destino en la red residual, tal que todos los arcos en ese
trayectoria tienen capacidad residual estrictamente positiva. El
mínimo de estas capacidades residuales se llama capacidad
residual de la trayectoria de aumento porque representa la
cantidad de flujo que es factible agregar en toda la trayectoria.
Por lo tanto, cada trayectoria de aumento proporciona una
oportunidad de aumento más el flujo a través de la
red original.
PROBLEMA DEL
FLUJO DE COSTO MÍNIMO
El problema de flujo de costo mínimo tiene una
posición medular entre los problemas de
optimización de redes; primero, abarca una clase amplia
de aplicaciones y segundo, su solución es muy eficiente.
Igual que el problema del flujo máximo, toma en cuenta un
flujo en una red con capacidades limitadas en sus arcos. Igual
que el problema de la ruta más corta, considera un costo
(o distancia) para el flujo a través de un arco. Igual que
el problema de transporte o el de asignación, puede
manejar varios orígenes (nodos fuente) y varios destinos
(nodos demandas) para el flujo, de nuevo con costos asociados.
De hecho, estos cuatro problemas son casos especiales del
problema de flujo de costo mínimo.
A continuación se describe el problema del flujo
de costo mínimo:
- La red es una red dirigida conexa.
- Al menos uno de los nodos es nodo fuente.
- Al menos uno de los nodos es nodo
demanda. - El resto de los nodos son nodos de
trasbordo. - Se permite el flujo a través de un arco
sólo en la dirección indicada por la flecha,
donde la cantidad máxima de flujo está dada por
la capacidad del arco. (Si el flujo puede ocurrir en ambas
direcciones, debe representarse por un par de arcos con
direcciones opuestas.) - La red tiene suficientes arcos como suficiente
capacidad para permitir que todos lo flujos generados por los
nodos fuente lleguen a los nodos demanda. - El costo del flujo a través del arco es
proporcional a la cantidad de ese flujo, donde se conoce el
costo por unidad. - El objetivo es minimizar el costo total de enviar el
suministro disponible a través de la red para satisfacer
la demanda dada. (Un objetivo alternativo es maximizar la
ganancia total del envío.)
Problema del flujo de costo mínimo
(Ejemplo)
La DISTRIBUTION UNLIMITED CO. Fabricará el mismo
nuevo producto en
dos plantas distintas y después tendrá que enviarlo
a dos almacenes. La red de distribución disponible para el
envío de este producto se muestra en la figura, donde A y
B son las fábricas, D y E son los almacenes y C es el
centro de distribución. Las cantidades que deben enviarse
desde A y B se muestran a la izquierda, y las cantidades que
deben recibirse en D y E se muestran a la derecha. Cada flecha
representa un canal factible de envío. A puede enviar
directamente a D y tiene tres rutas posibles (AC
E, A
B
C
E y
AD
E) para mandar bienes a E. La
fábrica B tiene solo una ruta a E (BC
E) y una a D (B
C
E
D).
El costo por unidad enviada a través de cada canal se
muestra al lado de la flecha. También, junto a AB
y C
E se muestran las cantidades máximas que se
pueden enviar por estos canales. Los otros canales tienen
suficiente capacidad para manejar todo lo que las fábricas
pueden enviar.
La decisión que debe tomarse se refiere a
cuánto enviar a través de cada canal de
distribución. El objetivo es minimizar el costo total de
envío.
Formulación:
Minimizar
Sujeto a:
APLICACIÓN
PRÁCTICA DEL PROBLEMA DEL FLUJO DE COSTO
MÍNIMO
El tipo más importante de aplicación del
problema del flujo de costo mínimo es en la
operación de la red de distribución de una
compañía. En la siguiente tabla se muestran algunos
tipos de aplicaciones comunes del problema de del flujo de costo
mínimo:
Tipo de Aplicación | Nodos Fuentes | Nodos de Trasbordo | Nodos de Demanda |
Operación de una red de | Fuentes de bienes | Almacenes intermedios | Consumidores |
Administración de desechos | Fuente de desechos sólidos | Instalaciones de procesamiento | Rellenos |
Operación de una red de | Agentes de ventas | Almacenes intermedios | Instalaciones de procesamiento |
Coordinación de mezcla de productos en | plantas | Producción de u artículo | Mercado del producto específico |
Administración de flujo de | Fuentes de efectivo en tiempos | Opciones de inversión a corto plazo | Necesidades de efectivo en tiempos |
PROBLEMA
DE TRANSPORTE (DATOS
ÚTILES)
Se proporciona un nodo de recursos para
cada origen y un nodo de demanda para cada destino pero no se
incluyen nodos de trasbordo en la red. Todos los arcos son
dirigidos, desde el nodo de recursos hasta el nodo de demanda, en
donde distribuir unidades del origen i al destino j corresponde a un flujo
a través
del arco . El
costo por unidad
distribuida se convierte en el costo por unidad de flujo.
FORMULACIÓN COMO UN PROBLEMA
LINEAL
Formulación como un PL del problema de flujo
de costo mínimo
Considere una red conexa dirigida en la que los n nodos
incluyen al menos un nodo origen y al menos un nodo destino. Las
variables de
decisión son:
=flujo a
través del arco , y la información dad incluye:
=
costo por unidad de flujo a través del arco,
=capacidad del arco
,
= flujo neto generado en el nodo i.
El valor de
depende de la
naturaleza del
nodo i, en donde
, si
i es un nodo fuente,, si
i es un nodo demanda,
, si i es un nodo de trasbordo.
El objetivo es minimizar el costo total de mandar los
recursos disponibles a través de la red para satisfacer la
demanda dada.
Usando la convención de que las sumas se toman
sólo sobre arcos existentes, la formulación de
programación lineal de este problema es
Minimizar
Sujeta a,
para
cada nodo i,
y
para
cada arco .
La primera suma en las restricciones de los nodos
representa el flujo total que sale del nodo i mientras que la
segunda representa el flujo total que entra al nodo i,
así, la diferencia es el flujo neto generado en este
nodo.
En lagunas aplicaciones, es necesario tener una cota
inferior para el
flujo que pasa para cada arco . Cuando esto ocurre se hace una conversión de
variables, ,
donde se
sustituye por en
todo el modelo, a fin de ajustar el modelo al formato anterior
con restricciones de no negatividad.
No se garantiza que el problema tenga soluciones
factibles, esto depende en parte de qué arcos están
presentes en la red y de sus capacidades. De cualquier manera,
para una red diseñada razonablemente, la condición
necesaria más importante es la siguiente.
Propiedad de soluciones factibles: una condición
necesaria para que un problema de flujo de costo mínimo
tenga soluciones factibles es que
.
Es decir, el flujo total generado en los nodos origen es
igual al flujo total absorbido por lo nodos destinos.
Formulación como un PL de problema de la ruta
más corta
El modelo de PL de la ruta más corta se construye
de la siguiente manera:
- Cada variable corresponde a un arco.
- Cada restricción corresponde a un
nodo.
Por lo tanto, si representa la cantidad de flujo en el arco (i,j), el
modelo de la ruta más corta con n nodos está dado
como:
Minimizar
Sujeto a:
(fuente)
para
toda k1 o
n
(destino)
para
toda i y j.
La primera y última restricción
señala que el flujo total (suma de variables) que sale del
nodo 1 es igual a 1 y que flujo total que se recibe en el nodo n
también es igual a 1. En cualquier nodo intermedio, el
flujo total que entra al nodo es igual al flujo total que sale
del mismo nodo. La función
objetivo requiere que se minimice la distancia total que recorre
la unidad del flujo.
- Considere la siguiente red dirigida.
- Encuentre una trayectoria dirigida del nodo A al
nodo F y después identifique otras tres trayectorias
no dirigidas del nodo A al F.
Trayectoria Dirigida de A a F:
AD
C
E
F
Trayectorias No Dirigidas de A a F:
AC
E
F
AD
F
AB
D
F
- Encuentre tres ciclos dirigidos, después
identifique un ciclo no dirigido que incluya todos los
nodos.
Ciclos Dirigidos:
CE-EF-FD-DC
AD-DC-CA
DC-CE-ED
Ciclo No Dirigido:
AC-CE-EF-FD-DB-BA
- Identifique un conjunto de arcos que formen un
árbol de expansión.
Algoritmo de la ruta más
corta:N
Nodos resueltos conectados con nodos no
resueltosNodo no resuelto más cercano
conectadoDistancia total
involucradan-ésimo nodo mas
cercanoDistancia mínima
Última
conexión1
O
A
4
A
2
OA
2
O
A
C
B
5
4+1=5
C
B
5
5
OC
AB
3
A
B
C
D
E
E
4+7=11
4+1+4=9
5+5=10
E
9
BE
4
A
B
E
D
D
D
4+7=11
4+1+5=10
4+1+4+1=10
D
D
10
10
BD
ED
5
D
E
T
T
4+1+5+6=16
5+5+6=16
T
T
16
16
DT
ET
Se identificaron dos opciones como las rutas
más cortas, ambas con distancia total igual a
16Ruta 1: O
A
B
E
D
T
distancia total: 4+1+4+1+6=16Ruta 2: O
A
B
D
T
distancia tota: 4+1+5+6=16Modelo de PL del problema de la ruta más
corta:Minimizar
Sujeto a:
- Utilice el algoritmo adecuado para encontrar la
ruta más corta a través de la red que se
muestra a continuación, en donde los números
representan las distancias reales entre los nodos
correspondientes. Formule el problema de la ruta más
corta como uno de PL. - Los modelos de optimización de redes
constituyen una herramienta muy sencilla para la encontrar la
solución óptima a los problemas de flujo de
redes, porque proporcionan algoritmos fáciles de
comprender y aplicar que comparados con el método
simplex disminuyen el número de iteraciones que
resuelven el problema. Si se aplicara el método
simplex en un problema de distribución o de redes,
tendríamos muchas variables y restricciones en el
modelo y se tendría que utilizar herramientas computacionales para encontrar la
solución optima de una forma rápida, ahora con
los modelos de redes solo habría que aplicar las
iteraciones al grafo que origina la representación de
la red del problema y luego aplicar el algoritmo que
corresponde, que puede ser el algoritmo de la ruta más
corta, algoritmo para encontrar el árbol de
expansión mínima, algoritmo de la trayectoria
de aumento o el algoritmo de flujo máximo. - Aunque los problemas de flujo de costo
mínimo y el de la ruta más corta pueden
formularse como modelos de programación lineal para
luego aplicar el método simplex, no es conveniente su
utilización. Por otro lado solucionar el problema
utilizando redes mejora la eficiencia de
los cálculos.
- Frederick S. Hiller y Gerald J. Liberman.
Investigación De Operaciones. McGraw-Hill.
Séptima Edición. 2002. - Hamdy A. Taha. Investigación De
Operaciones. Ediciones Alfaomega. Cuarta Edición.
1991.
Autor:
Carlos Muñoz
ESTUDIOS REALIZADOS: UNIVERSITARIO