Flujos De Redes

FLUJOS SOBRE REDES

Los modelos de redes y los programas de números enteros son aplicables para una gran variedad de modelos decisión. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto gerencial. Estos problemas son ilustrados fácilmente utilizando los arcos de redes, y los nodos.

Los programas lineal estándar asumen que las variables de decisión son continuas. Sin embargo, en muchas aplicaciones, los valores de fracciones podrían ser de poco uso así como es mostrado en algunas aplicaciones útiles.

Los modelos de redes son aplicables a una extensa variedad de problemas de decisión, los cuales pueden ser modelados como problemas de optimización de redes que pueden ser eficiente y efectivamente resueltos. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Sin embargo, muchos problemas de redes son mas que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto gerencial.

La familia de redes de los problemas de optimización incluye los siguientes prototipos de modelos: Problemas de asignación, camino crítico, flujo máximo, camino mas corto, transporte y costo mínimo de flujos. Los problemas son establecidos fácilmente mediante el uso de arcos de redes y de los nodos.

¿Que es un Nodo? Es usualmente llamado vértice, o punto. Es usualmente representado por un circulo. En las redes de transporte, estos deberían ser las localidades o las ciudades en un mapa.

¿Que es un Arco? Es usualmente llamado borde o flecha. Este podría ser directo o indirecto. La cabeza es el destino, y la cola el origen. La cabeza y la cola son nodos que pueden estar tanto al origen como al final. En las redes de transporte, los arcos podrían ser los caminos, los canales de navegación en un río, o los patrones de vuelo de un avión. Los arcos proporcionan la conectividad entre los nodos. Una calle de una sola dirección podría ser representada por un arco, mientras que una calle de dos direcciones podría representada por un arco sin dirección o por dos arcos que apuntan a direcciones opuestas.

Una red con n nodos podría tener tantos arcos como n! /[(n-2)! 2!] = n(n-1)/2. Si están dirigidos, este número pudiese ser doble. Este enorme número de arcos posibles es una de las razones del porque existen soluciones de algoritmos especiales para problemas de redes particulares.

Problemas de Transporte

Los modelos de transporten juegan un papel importante en la gerencia logística y en la cadena de insumos para reducir costos y mejorar servicios. Por lo tanto, el objetivo es encontrar la manera más efectiva en termino de costos para transportar bienes.

Un distribuidor que tiene m depósitos con un abastecimiento de productos ai ith en ellos, debe enviar dichos productos a n centros minoristas geográficamente dispersos, cada uno con una demanda de clientes dada ej, la cual debe ser cubierta. El objetivo es determinar el mínimo costo posible de transporte dados los costos por unidad de transportar entre el ith depósito y el jth centro minorista, el cual es Cij.

En el problema siguiente el objetivo es encontrar la forma mas efectiva de transportar los productos. Tanto como la oferta y la demanda en cada fuente se encuentra determinada. Por ejemplo, la fuente (u origen) 3 tiene 800 unidades disponibles mientras que el destino 1 necesita por lo menos 1100 unidades. Cada ruta desde un origen a un destino se le asigna una unidad de costo de transporte.

Utilizando el paquete de programación lineal, la solución proporciona la cantidad a ser enviada desde una fuente de origen a un destino. Los resultados son::

Enviar 850 unidades desde la fuente 1 al destino 1

Enviar 350 unidades desde la fuente 1 al destino 2

Enviar 250 unidades desde la fuente 2 al destino 1

Enviar 750 unidades desde la fuente 2 al destino 4

Enviar 50 unidades desde la fuente 3 al destino 2

Enviar 750 unidades desde la fuente 3 al destino 3

El costo total de envío es $84000.

El Problema Dual de Transporte:

El problema dual para el ejemplo numérico anterior es:

Max 1200U1 + 1000U2 + 800U3 + 1100V1 + 400V2 + 750V3 + 750V4

sujeto a:

U1 + V1 £ 35, U1 + V2 £ 30, U1 + V3 £ 40, U1 + V4 £ 32

U2 + V1 £ 37, U2 + V2 £ 40, U2 + V3 £ 42, U2 + V4 £ 25

U3 + V1 £ 40, U3 + V2 £ 15, U3 + V3 £ 20, U3 + V4 £ 28

Ninguna de las Ui y Vj tiene restricción en el signo.

La formulación dual sugiere que intentemos cada envió de bienes de forma tal que la diferencia en los precios unitarios Ui al i-ésimo origen, y el precio por unidad de Vj al j-ésimo destino no exceda el costo de transporte por unidad entre el i-ésimo origen y el j-ésimo destino.

La interpretación de las restricciones duales como el objetivo de que el la diferencia de precios de origen-destino no excede el precio del transporte, es equivalente al principio de equilibrio con un significado económico. Adicionalmente, se puede interpretar el objetivo dual como el propósito de un transportista en maximizar su utilidad cuando compra en un origen y vende en un destino.

Para resolver el problema dual, a usted podría gustarle intentar el Método Algebraico.

Problema de Transportación Discreto: En el problema de transportación discreto toda la oferta de una fuente de origen dada debe ser enviada a solo uno de los destinos disponibles, por lo tanto, es una instancia del Problema de Asignación Generalizado(PAG). El modelo de PAG puede ser formulado como un problema discreto (0-1) generalizado de red con ofertas de en el origen, y multiplicadores conocidos como los factores de ganancia sobre los arcos. Cada arco puede llevar un flujo de solo 0 o 1, pero el monto de flujos transportados a los destinos es igual al numero de multiplicadores de los arcos.

Problema de Asignación

Normalmente,

...