ARTICULO flujo de costo minimo

APLICACIÓN DE LA TEORÍA DEL MÍNIMO COSTO EN REDES MPLS

PARA LA OPTIMIZACIÓN EN LA ASIGNACIÓN DEL FLUJO EN UN LSP.

INFORME

La MPLS es un mecanismo de transporte de datos estándar creado por la IET y definido en el RFC 3031. Opera entre la capa de enlace de datos y la capa de red del modelo OSI. Fue diseñado para unificar el servicio de transporte de datos para las redes basadas en circuitos y las basadas en paquetes la cual puede ser utilizado para transportar diferentes tipos de tráfico, incluyendo tráfico de voz y de paquetes IP.

El  artículo hace referencias de cómo aplicar la teoría del mínimo costo en redes MPLS,  más específicamente en minimizar el ancho de banda no utilizada, que representa durante una transmisión, una pérdida de costos para el operador y una pérdida de servicio para el cliente, la cual lleva a pensar en una minimización del ancho de banda del canal.  Si bien la teoría del costo mínimo  puede determinar el costo de un enlace en el parámetro que desee optimizar, como puede ser dinero, la asignación de flujos o como en el  caso la  utilización del ancho de banda.
El esquema del costo mínimo es el siguiente:

Donde la capacidad de cada nodo estará limitada entre 0 y 5 es decir que de un nodo a otro no habrá un flujo superior a 5, ni inferior a 0;  se asume que el costo de cada enlace es igual a 1.  Mirando la gráfica podemos apreciar que el flujo entrada es igual al consumo, es este uno de los requisitos de optimalidad. Las cantidades negativas representan consumo, razón por lo cual se asumen como negativas.

La  forma de plantear el modelo,  es el siguiente:

Para verificar la asignación de flujo, se empleo la versión libre de GAMS, el cual arrojo los

 Siguientes resultados:

Como podemos observar, en los datos obtenidos en GAMS, existen enlaces que están subutilizados, por que el flujo que por allí circula es cero, donde se están utilizando tres enlaces y los otros enlaces están totalmente desocupados, esto lleva a que los que se están utilizando utilicen el máximo de su capacidad tal como se puede ver en la tabla anterior, el valor Z de la función objetivo es igual a 20.

 Por lo que se puede deducir del artículo es que este resultado en comparación con el resultado arrojado por el método LIPSOL, es que este último arroja una distribución de flujos más equitativa. Entonces podemos concluir que la evaluación realizada por el algoritmo LIPSOL distribuye de manera uniforme el flujo del enlace entre todos los enlaces posibles de la
red, en cambio CPLEX a pesar de optimizar algunos enlaces tiende a sobrecargar algunos enlaces mientras otros se encuentran con poco uso.   

Ejercicio 9.7-3

Reconsidere el problema del flujo de costo mínimo formulado en el problema 9.6-2.

Una empresa fabricará el mismo producto nuevo en dos plantas y después lo mandará a dos almacenes. La fabrica 1 puede enviar una cantidad ilimitada por ferrocarril solo al almacén 1 mientras que la fábrica 2 puede mandar una cantidad ilimitada por ferrocarril solo al almacén 2. Sin embargo, se pueden usar camiones de carga independientes para enviar hasta 50 unidades a cada almacén. En la siguiente tabla se muestra el costo unitario de embarque para cada alternativa junto con las cantidades que se producirán en las fábricas y las cantidades que se necesitan en los almacenes.

A   De	Costo unitario de embarque			Producción
	Centro de distribución	Almacén
		1	2
Fábrica 1	3	7	-	80
Fábrica 2	4	-	9	70
Centro de distribución		2	4
Asignación		60	90

a)      Obtenga una solución BF inicial resolviendo el árbol de expansión factible que corresponde a usar sólo las dos vías y la fábrica 1 que manda unidades al almacén 2 a través del centro de distribución.

b)      Use el método simplex de redes (sin usar la rutina de la computadora) para resolver este problema.

Solución literal a)

Planteamiento

A = Fabrica 1

B = Fabrica 2

C = Centro de distribución

D = Almacén 1

E = Almacén 2

Maximizar

Z = 7x_AD + 3x_AC + 4x_CE + 9x_BE  + 4x_BC + 2x_CD    

Sujeto a

1.   X_AD + X_AC   = 80

2.   X_BE = 70

3.   –X_AC + X_CE = 0

4.  –X_AD = -60

5.  –X_CE – X_BE  =  -90

0 ≤ X_AC , X_BC , X_CD , X_CE  ≤ 50

Solución:

De ecuación 4 tenemos

X_AD = 60

Reemplazando en la ecuación 1

X_AD  +  X_AC  = 80

60  +  X_AC  = 80

X_AC  =  20

Reemplazando en la ecuación 3

-X_AC   +  X_CE  =  0

-20  +  X_CE  =  0

X_CE  =  20

Y de ecuación 2 tenemos que:

X_BE  =  70

Con estos datos podemos obtener una solución BF inicial resolviendo el árbol de expansión factible que corresponde a usar sólo las dos vías y la fábrica 1 que manda unidades al almacén 2 a través del centro de distribución.

Solución literal b)

Planteamiento:

Maximizar:

Z = 7X_AD  +  3X_AC  +  4X_CE  +  9X_BE  +  4X_BC  +  2X_CD

 

1.  X_CD  +  X_AC  =  80

2.  X_BC  +  X_BE  =  70

3  -X_AC  -  X_BC  -  X_CD  -  X_CE  = 0

4.  –X_AD  -  X_CD  =  - 60

5-  -X_CE  - X_BE  = - 90

0≤ X_AC , X_BC , X_CD, X_CE  ≤ 50

Solución:

Arcos básico  = Nodos – 1 = n-1 = 5-1 =  4

Podemos tomar los 4 arcos:

A→D,  B→C,  C→D,  B→E.

Esto para formar un árbol de expansión factible: 

Los arcos  A→C  y  C→E  No son arcos básicos y ambos alcanzan su cuota superior, entonces:

X_AC  = 50

X_AC  = 50  -  Y_AC

X_CE  = 50

X_CE  = 50  -  Y_CE

Reemplazando en ecuación 1

X_AD  +  X_AC  =  80

X_AD  +  50  -  Y_AC  = 80

X_AD  -  Y_AC  =  30    Donde   Y_AC  = 0

X_AD  =  30

Reemplazando en ecuación 4

-X_AD  -  X_CD  = -60

        -30  -  X_CD = - 60

        -X_CD =  - 30

        X_CD  =  30

Reemplazando en ecuación 5

-X_CE  -  X_BE  = - 90

-(50 -  Y_CE) – X_BE  = -90

-50  +  Y_CE  -  X_BE  = - 90

Y_CE  -  X_BE  = - 40

Donde  Y_CE  = 0

-X_BE  =  - 40

X_BE  =  40

Reemplazando en ecuación 2

X_BC  +  X_BE  =  70

X_BC  +  40  =  70

X_BC  =  30

Reemplazando en ecuación 3.

-X_AC  -  X_BC  +  X_CD  +  X_CE  =  0

-(50 – Y_AC) -  30  +  30  + (50 – Y_CE) =  0

-50 + Y_AC  +  50  -  Y_CE  =  0

+50  +  0  +  50  -  0  =  0

0  =  0   Entonces es redundante

Lo anterior nos permite obtener la siguiente solución BF

Prueba de optimaliad

ARCO  NO  BASICO	CICLO  CERRADO	∆Z   CON  Ѳ =  0
C→A	AC – CD – AC	∆Z  = -3  +  7  -  2 =  2
E→C	CE – BC - BE	∆Z  =  -4  -  4  +  9  =  1

Como los ∆Z  son positivos, la solución es óptima. Ahora solo debemos comparar el último gráfico con el del planteamiento, para reorientar los arcos C→A  y  E→C  , calcular las nuevas asignaciones, así:

Arco  C→A

X_AC  =  50  -  Y_AC

X_AC  =  50  -  0

X_AC  =  50

ARCO   E→C

X_CE  =  50  -  Y_CE

X_CE  =  50  -  0

X_CE  =  50

Para la solución final tenemos

Para hallar z reemplazamos los valores optenidos:

Z  =  7X_AD  +  3X_AC  +  4X_CE  +  9X_BE  +  4X_BC  +  2X_CD

Z  =  7(30)  +  3(50)  +  4(50)  +  9(40)  +  4(30)  +  2(30)

Z  =  1100

  

Ejercicio 9.6-4

Ejercicio 9.6-4
Makolson es una compañía integrada por completo que produce bienes y los vende en sus propias tiendas. Después de la producción los bienes se colocan en dos almacenes hasta que las tiendas los necesitan. Se usan camiones para transportar los bienes a los almacenes y luego a las tres tiendas. Utilice una carga completa de camión como unidad; la siguiente tabla muestra la producción mensual de cada planta, su costo de transporte por carga enviada a cada almacén y la cantidad máxima que se puede enviar al mes a cada uno.





Para cada tienda (T), la siguiente tabla contiene su demanda mensual, si el costo de transporte por carga desde cada almacén y la cantidad máxima que se puede enviar al mes desde cada uno.
 

La administración desea determinar un plan  de distribución (numero de cargas enviadas al mes de cada planta a cada almacén y de cada uno de estos a cada tienda) de modo que se minimice el costo total de transporte.

1. Trace una red que describa la red de distribución de la compañía. Identifique en ella los nodos fuente, transbordo y demanda.

Solución:

2. Formule este problema como un problema de del flujo de costo mínimo colocando todos los datos necesarios.

Solución:

Donde los en paréntesis representan unidades de capacidad de envió.
                                                      

                                                                        SOLUCION  EN  SOLVER


 

De	A	Envio		Capacidad	Costo unitario		Nodos	Flujo neto		Suministro o demanda
P1	A1	125	<=	125	$ 425		P1	200	=	200
P1	A2	75	<=	150	$ 560		P2	300	=	300
P2	A1	125	<=	175	$ 510		A1	0	=	0
P2	A2	175	<=	200	$ 600		A2	0	=	0
A1	T1	100	<=	100	$ 470		T1	-150	=	-150
A1	T2	50	<=	150	$ 505		T2	-200	=	-200
A1	T3	100	<=	100	$ 490		T3	-150	=	-150
A2	T1	50	<=	125	$ 390
A2	T2	150	<=	150	$ 410
A2	T3	50	<=	75	$ 440
	Costo minimo	$488,125