Modelos de Optimização de Redes

Vista previa del material en texto

Investigación
Operativa
MODELOS DE OPTIMIZACIÓN 
DE REDES
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Profesor: Ing. Carlos A. Martin
E-mail: ing_carlos_martin@hotmail.com
Unidad VIII: Modelos de Optimización de Redes
• Objetivos. 
• Terminología de Redes. 
• Problema del Árbol de Expansión Mínima. Algoritmo de Kruskal
• Problema de Flujo Máximo. Algoritmo de Ford-Fulkerson
• Problema de la Ruta más Corta. Algoritmo de Dijkstra
• Caminos Mínimos: Algoritmo de Ford
• Método Simplex de Redes: Problema del Flujo de Costo Mínimo
• Ejemplos. Práctica.
Ing. Carlos Martin
 Conocer los conceptos de redes y sus propiedades.
 Aplicar el algoritmo de Dijkstra en redes para obtener la ruta más
corta desde un nodo de inicio a un nodo destino.
 Reafirmar conocimientos del problema del flujo máximo entre un nodo
fuente y un nodo destino, los que están enlazados a través de una
red, con arcos con capacidad finita.
 Reconocer las propiedades del problema de flujo de costo mínimo.
 Aplicar el algoritmo de KRUSKAL para unir todos los nodos de una
red, tal que minimice la suma de las longitudes de los ramales
escogidos. Sin incluir ciclos en la solución del problema.
Objetivos
Ing. Carlos Martin
La modelación de redes permite la resolución de múltiples problemas de
programación matemática mediante la implementación de algoritmos
especiales creados para tal fin, conocidos como algoritmos de
optimización de redes.
Dentro de los problemas más comúnmente resueltos mediante la
modelación de redes se encuentran
• modelos de transporte, transbordo
• modelos de actividades para proyectos: PERT y el CPM.
Teoría de Redes
Ing. Carlos Martin
Terminología de Redes: Conceptos Básicos
Gráfica: Una gráfica es una serie de puntos llamados nodos que
van unidos por líneas llamadas ramales o arcos.
Red: Una red es una gráfica que presenta algún tipo de flujo en
sus ramales. Por ejemplo una gráfica cuyo flujo en sus ramales
sea la electricidad es una red eléctrica.
En las redes se usa una simbología específica para denotar su
tamaño y elementos que la constituyen, dicha notación es:
(N, A) 
Donde:
N: representa el número de nodos que contiene la red y
A: representa el número de arcos o ramales.
Ing. Carlos Martin
Cadena: Una cadena corresponde a una serie de elementos
ramales que van de un nodo a otro.
En el siguiente caso se resalta una cadena que va desde el nodo 1
hasta el nodo 7 y que se compone por los elementos [1-4, 4-7].
Ruta o Camino: Una ruta corresponde a los nodos que constituyen
una cadena, en el siguiente caso [1, 4, 7].
Ing. Carlos Martin
 Un camino es simple cuando sólo pasa una vez por cada arco.
 Un camino es hamiltoniano cuando además de ser simple, pasa
exactamente una sola vez por todos los nodos del grafo.
 Llamamos camino euleriano al camino que recorre todas las aristas de un
grafo una sola vez, pero que puede pasar por un mismo vértice varias
veces.
 Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo
mismo, en el siguiente ejemplo el ciclo está compuesto por la cadena [4-2,
2-5, 5-7, 7-4].
Ing. Carlos Martin
Ramal Orientado: Un ramal o arco orientado es aquel que tiene un 
sentido determinado, es decir que posee un nodo fuente y un nodo 
destino.
Gráfica Orientada: Una gráfica orientada es aquella en la cual todos sus 
ramales se encuentran orientados.
Ing. Carlos Martin
Árbol: Un árbol es una gráfica en la cual no existen ciclos
Árbol de Expansión: Un árbol de expansión es aquel árbol que enlaza 
todos los nodos de la red, de igual manera no permite la existencia de 
ciclos.
Ing. Carlos Martin
Grafos Conexos
• En teoría de grafos, un grafo conexo o conectado​ es 
un grafo en que todos sus vértices están conectados por un 
camino (si el grafo es no dirigido)​ o por un semicamino (si 
el grafo es dirigido). 
• Un grafo que no es conexo se denomina grafo disconexo o 
inconexo.
Ing. Carlos Martin
Nodo Fuente: El nodo fuente es aquel nodo en el cual todos sus ramales 
se encuentran orientados hacia afuera.
Nodo Destino: El nodo destino es aquel nodo en el cual todos sus 
ramales se encuentran orientados hacia él.
Ing. Carlos Martin
Investigación
Operativa
Problemas de Recorrido Mínimo
• Árbol de Expansión Mínima -
Algoritmo de Kruskal
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
 Un problema de recorrido mínimo involucra a un conjunto de nodos y a un
conjunto de ramas propuestas, ninguna de las cuales es orientada.
 Cada rama propuesta tiene un costo no negativo asociado a ella.
 El objetivo es construir una red conexa que contenga a todos los nodos y
que sea tal, que la suma de los costos asociados con las ramas realmente
empleadas, sea mínimo.
 Debe suponerse que hay suficientes ramas propuestas para asegurar la
existencia de una solución.
 No es difícil ver que un problema de recorrido mínimo se resuelve siempre
mediante un árbol.
 Si dos nodos en una red conexa están unidos mediante dos rutas, una de
estas rutas debe contener una rama cuya eliminación no desconecte a la
red. El eliminar la rama puede solamente abatir el costo total.
Ing. Carlos Martin
1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (se pone
una ligadura) al nodo más cercano (menor costo).
2. Se identifica el nodo no conectado más cercano (menor costo) a un nodo
conectado, y se conectan estos dos nodos (es decir, se agrega una ligadura
entre ellos).
Este paso se repite hasta que se hayan conectado todos los nodos.
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 todavía debe llevar a una solución óptima.
No obstante, estos empates son señal de que pueden existir (pero no
necesariamente) soluciones óptimas múltiples.
Todas esas soluciones se pueden identificar si se buscan las demás formas de
romper los empates hasta el final.
Ing. Carlos Martin
Sean:
N = {1,2,3,...,n} el conjunto de nodos de la red.
Ck= Conjunto de nodos que se han enlazado de forma permanente en la
iteración k
Čk= Conjunto de nodos que hacen falta por enlazarse de forma permanente.
Ing. Carlos Martin
PASO CERO (0): Conceptualización 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 continuación se debe de actualizar el conjunto C1 = {i}, que significa
que al tiempo en que el conjunto C1 gana el elemento i el conjunto Č0
pierde el elemento i por ende ahora será igual a Č1 = N - {i}, además se
debe actualizar el subíndice de los conjuntos k, el cual ahora será igual
a 2.
Ing. Carlos Martin
PASO 2: Paso General "K"
Se debe de seleccionar un nodo j del conjunto ČK-1 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 CK-1. ("k-1" es el subíndice que indica que se está
haciendo referencia al conjunto de la iteración inmediatamente anterior)
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 todavía se debe conectar para lograr la
expansión.
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 vacío, cuando este
conjunto sea igual a vacío se tendrá el árbol de expansión mínima.
El entendimiento del algoritmo desde el puntode vista algebraico no es quizá el
más simple, sin embargo mediante el ejemplo gráfico se verá que es un
algoritmo muy sencillo de elaborar.
Ing. Carlos Martin
Resolución de un Problema a Través del 
Algoritmo de Kruskal
Ing. Carlos Martin
• Una ciudad cuenta con un nuevo plan de vivienda que 
contará con la urbanización de 7 proyectos habitacionales 
que se ubicarán a las afueras de la ciudad.
• Dado que el terreno en el que se construirá no se 
encuentra dentro de las zonas urbanizables de la ciudad, la 
red actual no cuenta con la infraestructura necesaria para 
satisfacer la demanda de servicios en materia de 
suministro de agua. 
• Cada uno de los proyectos de vivienda inició la 
construcción de un nodo, el cual cuenta con las conexiones 
de las unidades de vivienda propias de cada proyecto
• Cada nodo solo necesita estar conectado con un ducto de 
enlace al acueducto principal para contar con su 
suministro. 
• El municipio al ver la situación del plan parcial debe de 
realizar las obras correspondientes a la construcción de 
ese ducto de enlace de todos los nodos del plan con el 
Acueducto Principal (Meléndez)
• La construcción del ducto de enlace implica obras de 
excavación, mano de obra y de instalación de cañería, por 
lo cual optimizar su longitud total es fundamental.
• Las distancias existentes (dadas en kilómetros) 
correspondientes a las rutas factibles capaces de enlazar 
los nodos del plan parcial se presentan a continuación. 
• Además la capacidad de bombeo del Acueducto Principal 
es más que suficiente para satisfacer las necesidades de 
presión que necesita el ducto de enlace.
Ing. Carlos Martin
Ing. Carlos Martin
El municipio le contacta a usted para que mediante sus conocimientos en teoría de
redes construya una red de expansión que minimice la longitud total de cañería y que
enlace todos los nodos del plan parcial de vivienda.
PASO 0:
Se definen los conjuntos iniciales C0 = {ø} que corresponde al conjunto de nodos
enlazados de forma permanente en la iteración indicada en el subíndice 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 iteración indicada en el subíndice.
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).
Ing. Carlos Martin
Ing. Carlos Martin
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 iteración.
Ahora se seleccionará un nuevo nodo j del conjunto Č2 que presente el enlace (ramal
o arco) de menor longitud con los nodos que se encuentran en el conjunto C2.
Ing. Carlos Martin
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 elección 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
iteración.
Ing. Carlos Martin
Lo que representan los arcos naranja y verde es ya conocido, ahora la línea
azul interrumpida irá trazando nuestro árbol de expansión 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
iteración.
Ing. Carlos Martin
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
iteración.
Ing. Carlos Martin
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
iteración.
Ing. Carlos Martin
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
iteración.
Ing. Carlos Martin
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 
expansión mínima
Ing. Carlos Martin
Investigación
Operativa
Problemas de Flujo Máximo
• Algoritmo de Ford - Fulkerson
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
El objetivo es desarrollar un programa de embarque que maximice la
cantidad de cualquier artículo o información que podemos transportar
desde un origen hasta un destino.
 Al punto de origen se le denomina fuente,
 Al punto final se le denomina destino.
 Existen varias vías de embarque que unen a la fuente con el destino,
directamente o pasando por lugares intermedios denominados
empalmes.
 Se considera que no es posible almacenar material en los empalmes,
es decir, que cualquier material que llega a un empalme es embarcado
inmediatamente a otro sitio.
 La fuente, el destino y los empalmes se representan mediante nodos
 Las ramas representan los conductos a través de las cuales se
transportan materiales.
 Asociado a cada nodo N y a cada rama NM que salga de N, hay un
número no negativo, o capacidad, que representa la cantidad
máxima de material que puede embarcarse de N a través de NM
Ing. Carlos Martin
Algunas Aplicaciones
• Maximizar el flujo a través de la red de distribución de una compañía desde 
sus fábricas hasta sus clientes.
• Maximizar el flujo a través de la red de suministros de una compañía de 
proveedores a las fábricas.
• Maximizar el flujo de agua a través de un sistema de acueductos.
• Maximizar el flujo de vehículos por una red de transporte.
• Maximizar el flujo de petróleo por tuberías.
Un ejemplo es la situación donde un número de refinerías se conectan a 
terminales de distribución a través de una red de oleoductos. 
En los oleoductos están montadas unidades de bombeo que impulsan los 
productos derivados del petróleo hasta las terminales de distribución. 
oEl objetivo consiste en maximizar el flujo entre las refinerías y las 
terminales de distribución dentro de los límites de capacidad de las 
refinerías y los oleoductos.
Ing. Carlos Martin
PROBLEMA DEL FLUJO MAXIMO – ALGORITMO DE FORD-
FULKERSON
Lester Randolph Ford Jr. al continuar los pasos de su padre Ford 
también hizo una enorme contribución al campo de las matemáticas. 
Su trabajo con Delbert Ray Fulkerson ha puesto la base de casi toda 
la investigación en flujos de grafos. 
El artículo de Ford y de Fulkerson (1956) con el problema de flujo 
máximo estableció el famoso teorema del flujo máximo - mínimocorte
Lester Randolph Ford Jr.
(23 de septiembre de 1927 -
26 de febrero de 2017)
Delbert Ray Fulkerson
(14 agosto de 1924 -
10 Enero de 1976)
Ing. Carlos Martin
• El flujo máximo de la fuente al destino en una red se obtiene 
mediante la Programación Lineal o con el método de Ford-Fulkerson.
• Pasos a seguir :
Primer paso: Elegir una ruta arbitraria en sentido positivo (de la fuente 
al destino).
Segundo paso: En dicha ruta escoger aquel ramal de menor flujo en 
ese sentido y transportar por esa ruta la cantidad escogida.
Tercer paso: Hacer esto repetitivamente hasta que no sea posible 
encontrar una ruta con capacidad de flujo. 
Ing. Carlos Martin
La figura es una red que tiene a A como fuente, a D como destino y a B y C
como empalmes.
Cerca de los extremos de cada rama se indican las capacidades de flujo en
ambas direcciones.
Ejemplo
Ing. Carlos Martin
Pueden embarcarse 10 unidades de A
a B a lo largo de AB,
De B a A (en la dirección opuesta)
sólo pueden embarcarse 0 unidades;
esta asimetría permite, de desearse,
definir una orientación para AB.
En contraste, los flujos a lo largo de
BC pueden moverse en ambas
direcciones, con una capacidad de 5
unidades en ambos sentidos.
Ing. Carlos Martin
Consideraremos la situación cuando se enlazan un nodo
fuente y un nodo destino, a través de una red de ramas o
arcos de capacidad finita.
 La red es unidireccional, en el sentido que el flujo comienza
en el nodo fuente y llega al nodo destino.
 Una rama (i, j) puede tener dos capacidades distintas,
dependiendo de si el flujo es de i a j o bien de j a i.
Ing. Carlos Martin
 Por ejemplo, si la red trata el flujo de tránsito en las
calles de una ciudad, una calle de un solo sentido
tendrá una capacidad positiva en una dirección y una
capacidad cero en la otra.
 Por otra parte, una calle de dos sentidos puede tener
capacidades diferentes en las direcciones opuestas, si
ambas direcciones no incluyen el mismo número de
carriles de circulación.
Ing. Carlos Martin
Obtención del Flujo Máximo Mediante el 
Algoritmo de Ford-Fulkerson
PASO 1. Encuéntrese una ruta que permita el flujo positivo de material
de la fuente al destino. Si no existe alguna, continúese en el paso 5.
PASO 2. Determínese el flujo máximo que puede embarcarse a lo largo
de esta ruta y denótese k.
PASO 3.
Disminúyase la capacidad directa (es decir, la capacidad en la dirección de
flujo de las k unidades) de cada rama de esta ruta en k .
Auméntese la capacidad en sentido inverso en k.
Agréguense k unidades a la cantidad enviada al destino.
PASO 4. Continúese en el paso 1.
PASO 5. El flujo máximo es la cantidad total de material entregada en el
destino.
El programa óptimo de embarque se determina comparando la red
original con la red final. Cualquier reducción en capacidad significa un
embarque.
Ing. Carlos Martin
DETERMINACIÓN DE UNA RUTA DE FLUJO POSITIVO
 El aspecto difícil del algoritmo de flujo máximo es el Paso 1: “Identificación
de una ruta de la fuente al destino que tenga una capacidad de flujo
positiva”.
 Para descubrir tal ruta, conéctense primero a la fuente todos los nodos que
puedan ser alcanzados por una sola rama y que tengan capacidad de flujo
positiva (dirección saliendo de la fuente).
 Conéctense estos nodos a todos los nuevos nodos que puedan ser alcanzados
por ramas únicas que tengan capacidades positivas de avance.
 Continúese este proceso hasta que:
 o se haya llegado al destino: se ha identificado la ruta apropiada-
 o no puedan alcanzarse nuevos nodos a partir de los ya existentes y no se haya
alcanzado el destino, -en cuyo caso no existe ruta apropiada-
Ing. Carlos Martin
Ejemplo 1 : Calcular el flujo máximo en la red de la figura. 
Determínese el flujo máximo de material que puede ser enviado de la
fuente A al destino D, a través de la red que se muestra en la figura.
 Una ruta que va de la fuente al destino es la rama AD, la cual une a
estos nodos directamente. Puede permitir 8 unidades.
 Embarcando esta cantidad, se envían 8 unidades a D, disminuyendo en 8
la capacidad de AD y aumentando en 8 la capacidad de DA.
 La red resultante se muestra en la figura (a)
Ing. Carlos Martin
 Otra ruta de la fuente al destino que puede permitir el flujo positivo es (AC,
CB, BD).
 La cantidad máxima de material que puede ser enviado a lo largo de esta ruta es
de 4 unidades, es decir, la capacidad de BD.
 Haciendo este embarque, se incremento en 4 unidades el suministro en D, con lo
cual se tiene 8 + 4 = 12.
 Simultáneamente, se disminuyen en 4 unidades las capacidades de AC, CB y BD
y se incrementan en esta misma cantidad las capacidades de CA, BC y DB.
 Entonces, la figura (a) se vuelve la figura (b).
Ing. Carlos Martin
 La ruta (AC, CD), en la figura (b), puede permitir 3 unidades de A a D.
 Haciendo este embarque, se aumenta en 3 unidades el suministro en D,
teniéndose 12 + 3 = 15, y se disminuyen en 3 las capacidades de A C y
CD.
 También se incrementan en 3 unidades las capacidades de CA y DC. La
nueva red es la figura (c).
Ing. Carlos Martin
 La ruta (AB, BC, CD) de la fig.(c) puede permitir 7 unidades.
 Haciendo este embarque, se aumenta el suministro en 15 + 7 = 22
unidades y se disminuyen en 7 las capacidades de AB, BC y CD.
 También se incrementan en 7 unidades las capacidades de BA, CB y DC.
El resultado es la figura (d).
 No hay ninguna otra ruta de la fuente al destino, en la figura (d), que 
permita un flujo positivo. 
 Por lo tanto, la cantidad máxima de material que puede enviarse de 
A a D es de 22 unidades.
Ing. Carlos Martin
Para determinar el programa óptimo de embarque, se compara la figura (d) con (a).
Se notan las siguientes reducciones en capacidad:
 7 unidades de A a B,
 8 unidades de A a D,
 7 unidades de A a C,
 4 unidades de B a D,
 3 unidades de B a C, y
 10 unidades de C a D.
Estas reducciones, consideradas como embarques, constituyen el programa óptimo
de embarque.
Ing. Carlos Martin
Investigación
Operativa
Distancia mínima entre dos puntos de un grafo 
Algoritmo de Dijkstra
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Edsger Dijkstra (1930 -2002 ) . Nació en Alemania, su
padre era Químico y su madre Matemática. es uno de
los padres de la informática.
Éste físico teórico realizó contribuciones
fundamentales al campo de la informática actual:
los semáforos, el algoritmo del banquero o la notación
polaca inversa. En 1956, Dijkstra anunció su
algoritmo.
“El algoritmo de Dijkstra” es una de las contribuciones de Dijkstra que más
se ha popularizado en los últimos tiempos gracias al uso de los GPS.
El algoritmo de Dijkstra se aplica sobre un grafo ponderado y calcula la
distancia desde un vértice inicial al resto de vértices del grafo.
Los GPS tratan el mapa de carreteras como un grafo ponderado (cuyos
pesos son o bien la distancia o el tiempo) y utilizan este algoritmo para
calcular el camino más corto entre dos puntos.
Ing. Carlos Martin
ALGORITMO DE DIJKSTRA
Este procedimiento va a calcular la distancia mínima entre dos puntos
de un grafo.
En algunas ocasiones particulares puede dar la distancia mínima de un
nodo al resto de los nodos de la red.
a) Definimos dos conjuntos:
 V: valor de la distancia mínima entre el nodo origen y el
nodo que se tiene en cuenta.
 M: conjunto de nodos elegidos.
b) Definimos una variable "p", que será el último nodo elegido.
Ing. Carlos Martin
1) Inicialización: 
a) Identifique el nodo inicial.
b) Marque el nodo inicial con la etiqueta permanente 0.
c) Después ponemos, a cada nodo i conectado al nodo inicial mediante un
solo arco, una etiqueta de temporal igual a la longitud del arco que
une el nodo inicial y el nodo i.
d) El resto de los nodos (menos, por supuesto, el nodo inicial) tendrá una
etiqueta temporal igual a .
NODO i … … … j
V: 0 ∞ ∞ ∞ ∞
La variable “P”, corresponderá con el último nodo elegido, o sea, el
nodo inicial.
M:NODO 
INICIAL
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
2) Para obtener el camino mas corto del nodo inicial A al nodo E, se
procede hacia atrás, desde el nodo E, encontrando los nodos que tienen
etiquetas que difieren exactamente en la longitud del arco que los conecta.
En este caso V(E) – V(C) = 8 – 4 = 4 ; Longitud del arco (C,E): d(C,E) = 4
V(C) – V(A) = 4 – 0 = 4 ; Longitud del arco (A,C): d(A,C) = 4
Ing. Carlos Martin
1) Escoja el nodo con la etiqueta temporal más pequeña y haga esta
etiqueta permanente.
2) Tomamos los sucesores de “P” que no están en M.
 Supóngase que el nodo i es el (k+1)-ésimo nodo que recibe una etiqueta
permanente.
 Entonces el nodo i es el k-ésimo nodo mas cercano al nodo inicial.
 En este momento, la etiqueta temporal de cualquier nodo es la
longitud del camino mas corto del nodo inicial a este nodo que pasa
solamente por los nodos incluidos en los k-1 nodos mas cercanos al
nodo inicial.
Resumen
Ing. Carlos Martin
 Para cada nodo j que ahora tiene una etiqueta temporal y que esta conectado al
nodo i mediante un arco, la nueva etiqueta temporal es la longitud del camino mas
corto del nodo inicial al nodo j.
 Se cambia la etiqueta temporal del nodo j por:
Min {etiqueta temporal actual del nodo j , (etiqueta permanente del nodo i) + (longitud del arco (i,j))}.
1) Convertimos la etiqueta temporal más pequeña en una permanente. El nodo con
esta nueva etiqueta permanente es el (k+1)-esimo nodo mas cercano al inicial.
2) Se continúa con este proceso hasta que todos los nodos tengan etiquetas
permanentes.
3) Para obtener el camino mas corto del nodo inicial al nodo j, proceda hacia atrás,
desde el nodo j, encontrando los nodos que tienen etiquetas que difieren exactamente
en la longitud del arco que los conecta.
Si se quiere obtener el camino más corto del nodo inicial al nodo j , termine con
el proceso del etiquetado al recibir el nodo j una etiqueta permanente
Ing. Carlos Martin
Investigación
Operativa
Distancia mínima entre 2 puntos en una red
Algoritmo de Ford
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
 Este algoritmo nos va a permitir calcular la distancia mínima que existe
entre 2 puntos en una red y, desde luego, el camino mínimo que los une.
 Utilizamos una representación del grafo un poco particular, que facilita la
resolución de problemas de este tipo y que describimos a continuación.
Los nodos van a estar representados como vemos en la figura, donde n
representa el valor del nodo y A (N°) el identificador del nodo.
Los arcos aij estarán orientados y valuados con la distancia entre el i y el j.
Mediante un proceso iterativo daremos a cada nodo Xi un valor, n, igual a la
longitud del camino más corto que vaya desde el nodo origen al nodo Xi.
 
Ing. Carlos Martin
1) Asignamos el valor 0 al nodo origen.
2) Para valuar un nodo Xi es necesario conocer el valor de todos los nodos predecesores del
nodo Xi.
El valor asignado a Xi será el mínimo del conjunto de valores obtenidos mediante la suma
del valor de cada nodo predecesor de Xi con el valor del arco que lo une con el nodo Xi.
3) Repetimos el punto 2 hasta valuar el nodo final.
 Si no podemos asignar un valor al nodo final, es que no existe un camino que los una.
 Si lo podemos valuar el valor asignado al nodo final será la longitud del camino
mínimo.
4) Obtención del camino mínimo:
I. Partiendo del valor del nodo final restamos este valor a cada arco que le llega y
entonces aquel predecesor cuyo valor coincida con dicha resta formará parte del
camino.
II. Elegimos el último nodo del camino encontrado y repetimos el punto I.
III. El algoritmo finalizará cuando lleguemos al nodo de partida, obteniendo la secuencia
de nodos que forman el camino mínimo
Ing. Carlos Martin
Ejemplo: Calcular el camino mínimo entre A y F del grafo de la figura
Ing. Carlos Martin
La distancia mínima será 11 y el camino será la secuencia de
nodos: c = [A,D,C,F]
Investigación
Operativa
Método Simplex de Redes
• Problema de flujo de costo 
mínimo
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
A continuación se describe el problema de flujo de costo mínimo.
a) La red es red dirigida y conexa
b) Al menos uno de los nodos es un nodo fuente
c) Al menos uno de los nodos es un nodo destino.
d) El resto de los nodos son nodos de transbordo.
e) 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.
f) La red tiene suficientes arcos con suficiente capacidad para permitir que
todos los flujos generados por los nodos fuente lleguen a los nodos
demanda.
g) El costo del flujo a través del arco es proporcional a la cantidad de ese
flujo, donde se conoce el costo por unidad.
h) 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)
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Bibliografía
Ing. Carlos Martin
 Prawda Witenberg J. “Métodos y Modelos de Investigación de Operaciones 
– Vol. 1 Modelos Determinísticos”. Editorial Limusa. ©1999
 Taha Hamdy A. “Investigación de Operaciones”. Editorial Alfa Omega. ©1998
 Winston Wayne L.. “Investigación de Operaciones. Editorial. Grupo Editorial 
Iberoamericana. ©2005
 Hillier Frederick S. “Introducción a la Investigación de Operaciones. 
Editorial. Mc Graw Hill. ©2001
 Eppen G.D. “Investigacion de Operaciones En la Ciencia Administrativa. 
Editorial Prentice. ©2000
 Mathur-Solow – Investigación de Operaciones – Ed. Prentice Hall 1996.
 MARIN, Isidoro. “Investigación Operativa”. UBA. Centro de Estudiantes 
Universidad Nacional de Buenos Aires. © 1970
 LEVIN, Richard I.. “Enfoques Cuantitativos a la Administración”. CECSA
 Anderson, David R. “Métodos Cuantitativos para los Negocios”. 11a. ed. 
Cengage Learning
 Bronson, Richard. “Investigación de Operaciones”. Editorial Mc Graw Hill.
Preguntas
Ing. Carlos Martin
Investigación
Operativa
Muchas Gracias
Profesor: Ing. Carlos A. Martin
E-mail: ing_carlos_martin@hotmail.com
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR