2.3 PROBLEMA DE LA RUTA MAS CORTA

PROBLEMA DE LA RUTA MAS CORTA:

Se trata de encontrar la ruta de menor distancia, o costo, a entre el punto de partida o nodo inicial y el destino o nodo terminal.

DEFINICIÓN DEL PROBLEMA:

** Se tiene 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 mínima distancia que conecta el nodo 1 con el nodo n.

*** 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 (A C E, A B C E y A D E) para mandar bienes a E. La fábrica B tiene solo una ruta a E (B C 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 A B 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

Z=2XAB + AXAC + 9XAD + 3XBC + XCD + 3XDE +2XED

Sujeto a:

XAB + XAC +XAD = 50

-          XAB + XBC = 40

-          XAC – XBC + XCE = 0

-          XAD + XDE – XED = -30

-          XCE  - XDE + XED = -60

      XAB <= 10

      XCE <= 80

       XIJ =>0

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 distribución Fuentes de bienes Almacenes intermedios Consumidores
Administración de desechos sólidos Fuente de desechos sólidos Instalaciones de procesamiento Rellenos
Operación de una red de suministros Agentes de ventas Almacenes intermedios Instalaciones de procesamiento
Coordinación de mezcla de productos en plantas plantas Producción de u artículo específico Mercado del producto específico
Administración de flujo de efectivo Fuentes de efectivo en tiempos específicos Opciones de inversión a corto plazo Necesidades de efectivo en tiempos específicos

 

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:

Z= ∑IJi8 [dijxij]

Minimizar

Sujeto a:

(ij)[xij]=1                         (fuente)

(ik)[xik] = ∑(kj)[xkj]              para toda k 1 o n

(in)[xin]=1                       (destino)

Xij =>0                             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.

  

Trayectoria Dirigida de A a F:

A D C E F

  

Trayectorias No Dirigidas de A a F:

A C E F

A D F

A B D F

  

Ciclos Dirigidos:

CE-EF-FD-DC

AD-DC-CA

DC-CE-ED

  

Ciclo No Dirigido:

AC-CE-EF-FD-DB-BA

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 OA CB 54+1=5 CB 55 OCAB
3 ABC DEE 4+7=114+1+4=95+5=10 E 9 BE
4 ABE DDD 4+7=114+1+5=104+1+4+1=10 DD 1010 BDED
5 DE TT 4+1+5+6=165+5+6=16 TT 1616 DTET

Se identificaron dos opciones como las rutas más cortas, ambas con distancia total igual a 16

Ruta 1: OèA B E D T distancia total: 4+1+4+1+6=16

Ruta 2: Oè A B D T distancia tota: 4+1+5+6=16

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

Minimizar

Z=4XOA + 6XOB + 5XOC + XAB + 7XAD + 2XBC + 4XBE + 5XBD +6XDT + XDE +6XFT

Sujeto a:

XOA + XOB + XOC =1

XOA – XAB  - XAD =0

XOB + XAB – XBD – XBE – XBC =0

XOC + XBC – XCE =0

XAD + XDB – XDT – XDE =0

XBE + XCE  - XFT  =0

è   XOA , XOB , XOC , XAB, XAD, XBC, XBF, XBD, XCE, XDT, XDF, XFT => 0

CONCLUSIONES

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.

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: