Programación lineal. Flujo de redes

3. Modelos de
   redes
4. Notación y
   terminología
5. Vista general de algunas
   aplicaciones prácticas de la optimización de
   redes
6. Ejemplos de
   términos
7. Otras
   Definiciones
8. Problema del flujo de coste
   mínimo
9. Formulación del
   ejemplo
10. Aplicación practica del
    problema de flujo de costo mínimo
11. Problema de trasporte
    (datos útiles)
12. Formulación de un
    programa lineal
13. Ejercicios
14. Conclusión
15. Bibliografía

INTRODUCCION

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.

MODELOS DE
REDES

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:

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 diseñar 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 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:

1. Se selecciona, de manera arbitraria, cualquier nodo y
   se conecta (es decir, se agrega una ligadura) al nodo distinto
   más cercano.
2. 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.
3. 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:

1. Todo flujo a través 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.
3. 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.
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 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:

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 patrón del
   flujo óptimo).
2. 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.
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 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:

1. 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.)
2. 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.)
3. 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.)
4. 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.

NOTACIÓN Y
TERMINOLOGÍA

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
(OBDT), 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

1. Diseño de redes de telecomunicación
   (redes de fibra
   óptica, de computadores, telefónicas, de
   televisión por cable, etc.)
2. Diseño de redes de transporte para minimizar
   el costo total de proporcionar las ligaduras (vías
   ferroviarias, carreteras, etc.)
3. Diseño de una red de líneas de
   transmisión de energía
   eléctrica de alto voltaje.
4. Diseño de una red de cableado en equipo
   eléctrico (como sistemas de
   computo) para minimizar la longitud total del
   cable.
5. Diseño de una red de tuberías para
   conectar varias localidades.
6. 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.
7. Determinación de la ruta más corta que
   une dos ciudades en una red de caminos existentes.
8. 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.)
9. 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.

EJEMPLOS DE
TERMINOS

Se tiene la red de distribución para Distribution
Unlimited Co.

OTRAS
DEFINICIONES

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:

1. La red es una red dirigida conexa.
2. Al menos uno de los nodos es nodo fuente.
3. Al menos uno de los nodos es nodo
   demanda.
4. El resto de los nodos son nodos de
   trasbordo.
5. 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.)
6. La red tiene suficientes arcos como suficiente
   capacidad para permitir que todos lo flujos generados por los
   nodos fuente lleguen a los nodos demanda.
7. El costo del flujo a través del arco es
   proporcional a la cantidad de ese flujo, donde se conoce el
   costo por unidad.
8. 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.)

FORMULACION DEL
EJEMPLO

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 (ACE, ABCE y
ADE) para mandar bienes a E. La
fábrica B tiene solo una ruta a E (BCE) y una a D (BCED).
El costo por unidad enviada a través de cada canal se
muestra al lado de la flecha. También, junto a AB y CE 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:

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:

1. Cada variable corresponde a un arco.
2. 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.

EJERCICIOS

1. 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:

ADCEF

Trayectorias No Dirigidas de A a F:

ACEF

ADF

ABDF

• 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.

1. Algoritmo de la ruta más
   corta:

   N	Nodos resueltos conectados con nodos no resueltos	Nodo no resuelto más cercano conectado	Distancia total involucrada	n-ésimo nodo mas cercano	Distancia mínima	Última conexión
   1	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
   16

   Ruta 1: OABEDT
   distancia total: 4+1+4+1+6=16

   Ruta 2: OABDT
   distancia tota: 4+1+5+6=16

   Modelo de PL del problema de la ruta más
   corta:

   Minimizar

   Sujeto a:

   

   

   

   

   

   

   

   

   CONCLUSIONES

2. 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.
3. 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.
4. 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.

BIBLIOGRAFÍA

• 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