FLUJO CON COSTO MINIMO

Vista previa del material en texto

Luis Medina Aquino
INVESTIGACION DE OPERACIONES II
1
2
El problema del flujo con costo mínimo
Luis Medina Aquino
3
Definición del problema
Definición del problema: Una red compuesta por n nodos, a los que se asocia un valor ki que indica el nivel ofertado o demanda por el nodo i. 
Si ki>0, existe una oferta en el nodo i denominándose fuente u origen .
Si ki<0, existe una demanda en el nodo i denotándose por sumidero o destino. 
Si ki=0, el nodo i denomina intermedio o de transbordo.
A cada arco (i,j) se asociará una variable xij>= 0 que representa el flujo que circula por él y un costo unitario de transporte cij. 
El flujo está limitado por el limite inferior lij y el limite superior uij. 
Todos los nodos tienen que cumplir las leyes de conservación de Kirchhoff. 
j
kj
j
i
xij
cij
4
Formulación matemática del problema.
La formulación matemática del problema de
 flujo con costo mínimo queda como:
5
Ejemplo: 
1
2
4
5
3
2
1
1
-2
3
2
6
0
k1=1
k4=-3
k5=6
k2=-4
k3=0
6
Propiedades del problema
	El problema puede reescribirse, en forma matricial, como: 
	Matriz de incidencia, A=[aij], [aij]=ei-ej
	y ei es el vector unitario i-ésimo. 
7
Propiedades del problema
Adicionando todas las filas de la matriz A se tiene que 	 para que el problema tenga solución, es decir las restricciones deben ser combinaciones lineales; y por consiguiente, el rango de la matriz A es como máximo rango (A)<= n-1, donde n define el número de nodos de la red.
Propiedades importantes:
El rango de la matriz A es n-1
Las soluciones del problema son siempre enteras para valores de ki enteros. 
	
8
Propiedades del problema
El rango de la matriz A es n-1
	
Tantas columnas como arcos
Tantas filas como nodos
(i,j)
Dimensiones de A: 
nodos (n) x arcos 
i
j
xij
xij aparece en la ecuación del nodo i con signo + y en la ecuación del nodo j con signo - 
aij es la columna de A que corresponde al arco que une los nodos i y j
9
Ciclos y Dependencia Lineal
	Dos teoremas de gran valor para la definición del algoritmo que permitirá resolver el problema formulado:
Teorema 1. Un conjunto de columnas de la matriz A serán linealmente dependientes si y solo si existe un ciclo entre sus nodos. 
	Demostración: Supongamos un subgrafo del grafo original, cuyos nodos unidos por arcos definen un ciclo, tal y como se muestra en la siguiente figura: 
i
j
k
l
m
n
	Asignando una orientación arbitraria a dicho ciclo, a los arcos en dicha dirección un coeficiente +1 y a los arcos orientados en sentido opuesto un coeficiente -1, se tiene:	[aij]+[ajk ]-[ alk ]+[ alm ]-[ anm]+…
					=(ei-ej)+(ej-ek)-(el-ek)+(el-em)-(en-em)+…=0
	por lo que las columnas de A correspondientes los arcos no son linealmente independientes.
	Corolario: Las variables básicas no podrán formar un ciclo y, por tanto, definen un árbol compuesto por n-1 arcos y n nodos. 
10
Ciclos y Dependencia Lineal
	Teorema 2. Cualquier arco no básico cuya columna es [alm] puede representarse como combinación lineal de las columnas de los n-1 arcos básicos. Así, el conjunto definido por las columnas que representan los vectores básicos y el no básico [alm] definirán el ciclo. 
	
	Corolario: para obtener la representación correcta de un arco no básico dado, simplemente se localiza el ciclo único en el subgrafo de la base que contiene el arco asociado. Definiendo una orientación acorde con el arco no básico, cualquier arco en el ciclo que posea la misma orientación, tendrá asignado un coeficiente de -1, mientras que los que presenten sentido opuesto tendrán asignado coeficiente +1. 
	
11
Ejemplo
En el grafo donde los arcos continuos son los básicos, el arco a45 puede representarse como:
[a45]=[a35]+[a13 ]-[a14 ]=(e3-e5)+(e1-e3)-(e1-e4)=e4-e5
1
3
5
4
2
12
Algoritmo simplex para redes
El algoritmo consiste en partir de una solución básica factible y aplicar el criterio de optimalidad a todos los arcos no básicos. 
Si los costos relativos de las variables no básicas son no negativos, se ha alcanzado el óptimo.
 En caso contrario es necesario introducir la base el nuevo arco básico con costo relativo más negativo y sacar de la base el arco cuya variable básica se anule en el proceso de compensación del ciclo al que pertenece el nuevo arco básico. 
13
Algoritmo simplex para redes
Físicamente, los costos relativos de un arco representan el costo unitario adicional en que se incurre al enviar un flujo unidad a lo largo de otra cadena que une los mismos nodos que el arco no básico. 
En la figura, el costo de enviar una unidad de flujo desde el nodo 3 al 4 es c34 si se utiliza el arco no básico (3,4), o bien 
 –c13+c15+c54 si se utiliza la cadena básica.
El costo relativo r34 será la diferencia entre el costo absoluto y el costo sintético, éste último es el costo en el que se incurre cuando se hace uso de la cadena básica que une los mismos nodos que el arco no básico, o sea:
1
3
4
5
2
r34 = c34 – (–c13+c15+c54 )
14
Algoritmo simplex para redes
Este proceso de compensación consiste en, una vez identificado el nuevo arco básico y el ciclo al que pertenece, se asigna al ciclo el sentido del nuevo arco básico:
Si envio e por el arco 34, tendré que aumentar el flujo en e en el arco 13 y decrementar en e en los arcos 15 y 54 -> todos los arcos en la dirección del sentido en el ciclo incrementarán su flujo
Análogamente, los arcos orientados en sentido contrario verán decrementados los valores. 
El máximo incremento posible vendrá limitado por el mínimo decremento en el ciclo que se denotará por e.
Este mínimo decremento vendrá determinado por el valor de la variable básica más pequeña de entre los arcos orientados en sentido opuesto al definido en el ciclo. 
Esta variable básica, con valor más pequeño, se bloqueará alcanzando el valor cero y dejando de ser básica. 
1
3
4
5
2
-e
-e
+e
+e
15
Algoritmo simplex para redes
Para conocer, de entre todos los arcos no básicos, aquel arco que entra en la base, se aplica el criterio de optimalidad del Simplex, 
que consistirá en calcular todos los costos relativos no básicos.
Considerando como nuevo arco básico aquél con costo relativo más negativo. 
Para calcular el costo relativo de un arco no básico, se identifica el ciclo formado por el y otros arcos que sean básicos; 
se le asocia un sentido que coincidirá con la orientación del arco no básico. 
El costo relativo de dicho arco vendrá definido por la diferencia entre su costo absoluto y la suma algebraica de los costos de los arcos básicos del ciclo 
multiplicados por +1 si están orientados en sentido contrario al ciclo 
multiplicados por -1 si lo esta a favor. 
Para el ciclo de la figura, se tiene: 
1
3
4
5
2
-e
-e
+e
+e
16
Ejemplo
Obtener el flujo máximo con costo mínimo en la siguiente red, donde a cada arco se le asocia el costo absoluto unitario cij, a cada nodo su nivel de oferta/demanda ki y no existen restricciones de cota máxima para los flujos que circulan por cada arco. 
Una solución básica factible puede obtenerse definiendo un árbol tal como:
Donde en cada arco se define el flujo que circula y que es factible ya que cumple las leyes de Kirchhoff en cada nodo.
1
2
4
5
3
2
1
1
-2
3
2
6
0
k1=1
k4=-3
k5=6
k2=-4
k3=0
1
2
4
5
3
1
1
1
6
3
3
6
3
k1=1
k4=-3
k5=6
k2=-4
k3=0
17
Ejemplo
Los costos relativos de los arcos no básicos serán:
1
2
4
5
3
1
1
1
6
3
3
6
3
k1=1
k4=-3
k5=6
k2=-4
k3=0
1
2
4
5
3
1
1
1
6
3
2
6
2
k1=1
k4=-3
k5=6
k2=-4
k3=0
Introduciendo el arco r14 en la base:
Habiéndose alcanzado el óptimo.
18
Obtención de una solución básica factible inicial.
Para la definición del algoritmo Simplex para un problema de redes es imprescindible partir de una solución básica factible con la que iniciar el proceso de iteración. La obtención de esta solución básica factible puede realizarse haciendo uso de variables de holgura y resolviendo la Fase I del sistema de ecuaciones asíobtenido. 
Para aplicar la Fase I al problema: 
	Minimizar 		cx
		s.a. 		Ax = k,
				x>= 0
19
Obtención de una solución básica factible inicial.
se amplía el sistema de ecuaciones de restricciones con variables de holgura w ; dichas variables serán positivas en las ecuaciones donde k > O y negativas en las ecuaciones donde k < O , a fin de obtener una solución básica que sea factible para el problema primal. Por consiguiente, el problema a resolver será:
Fase I:
Minimizar 	w
		 s.a. 	Ax ± w = k,
			(x,w) >= 0
Su optimización definirá una base inicial.
20
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
donde a cada arco se le asocia el costo absoluto unitario cij, a cada nodo su nivel de oferta/demanda ki y no existen restricciones de cota máxima para los flujos que circulan por cada arco. 
1
3
4
2
2
4
3
-5
-1
6
k2=2
k4=-5
k3=-1
k1=4
21
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
la matriz de incidencia nodo-arco es:
1
3
4
2
2
4
3
-5
-1
6
k2=2
k4=-5
k3=-1
k1=4
22
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
Para la obtención de una solución básica factible, se resuelve el problema en la Fase I:
23
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
La tabla de simplex es: 
	x12	x13	x23	x24	x32	x34	w1	w2	w3	w4	k
	1	1	0	0	0	0	1	0	0	0	4
	-1	0	1	1	-1	0	0	1	0	0	2
	0	-1	-1	0	1	1	0	0	-1	0	-1
	0	0	0	-1	0	-1	0	0	0	-1	-5
	0	0	0	0	0	0	1	1	1	1	
x (-1)
24
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
La tabla de simplex es: 
	x12	x13	x23	x24	x32	x34	w1	w2	w3	w4	k
	1	1	0	0	0	0	1	0	0	0	4
	-1	0	1	1	-1	0	0	1	0	0	2
	0	1	1	0	-1	-1	0	0	1	0	1
	0	0	0	1	0	1	0	0	0	1	5
	0	0	0	0	0	0	1	1	1	1	
25
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
Aplicando Simplex se tiene: 
	x12	x13	x23	x24	x32	x34	w1	w2	w3	w4	k	ki/aij
	1	1	0	0	0	0	1	0	0	0	4	4
	-1	0	1	1	-1	0	0	1	0	0	2	
	0	1	1	0	-1	-1	0	0	1	0	1	1
	0	0	0	1	0	1	0	0	0	1	5	
	0	0	0	0	0	0	1	1	1	1		
	0	-2	-2	-2	2	0	0	0	0	0		
26
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
Aplicando Simplex se tiene: 
	x12	x13	x23	x24	x32	x34	w1	w2	w3	w4	k	ki/aij
	1	0	-1	0	1	1	1	0	-1	0	3	
	-1	0	1	1	-1	0	0	1	0	0	2	2
	0	1	1	0	-1	-1	0	0	1	0	1	
	0	0	0	1	0	1	0	0	0	1	5	5
												
	0	0	0	-2	0	-2	0	0	2	0		
27
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
Aplicando Simplex se tiene: 
	x12	x13	x23	x24	x32	x34	w1	w2	w3	w4	k	ki/aij
	1	0	-1	0	1	1	1	0	-1	0	3	3
	-1	0	1	1	-1	0	0	1	0	0	2	 
	0	1	1	0	-1	-1	0	0	1	0	1	
	1	0	-1	0	1	1	0	-1	0	1	3	3
												
	-2	0	2	0	-2	-2	0	2	2	0		
28
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
Aplicando Simplex se tiene: 
	x12	x13	x23	x24	x32	x34	w1	w2	w3	w4	k	ki/aij
	1	0	-1	0	1	1	1	0	-1	0	3	 
	0	0	0	1	0	1	1	1	-1	0	5	 
	0	1	1	0	-1	-1	0	0	1	0	1	
	0	0	0	0	0	0	-1	-1	1	1	0	 
	0	0	0	0	0	0	2	2	0	0		
Se ha alcanzado el final de la fase I y la solución básica factible es: 
x12=3
x13=1
x24=5
29
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
1
3
4
2
3
5
1
k2=2
k4=-5
k3=-1
k1=4
Aplicando el criterio de optimalidad: 
r23=c23-(c13-c12)= -1-(-5-2)=7
r32=c32-(c12-c13)=6-(2+5)=-1
r34=c34-(-c13+c12+c24)=3-(--5+2+4)=-8
Introduciendo x34 en la base, se tiene:
30
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
1
3
4
2
3
5-3=2
1+3=4
k2=2
k4=-5
k3=-1
k1=4
Aplicando el criterio de optimalidad: 
r12=c12-(c13+c34-c24)= 2-(-5+3-4)=8
r23=c23-(c24-c34)=-1-(4-3)=-2
r32=c32-(c34-c24)=6-(3-4)=7
Introduciendo x34 en la base, se tiene:
Introduciendo x23 en la base, se tiene:
r12=c12-(c13-c23)= 2-(-5+1)=6
r24=c24-(c23+c34)=-1-(-1+3)=2
r32=c32-(-c23)=6-(1)=5
1
3
4
2
3
5-3=2
1+3=4
k2=2
k4=-5
k3=-1
k1=4
Todos positivos  Óptimo
11
()()
Minimizar 
s.a. 1,2,...,
 ,1,2,...,
nn
ijij
ij
jkijj
kDjiAj
ijijij
cx
xxkjn
lxuijn
==
ÎÎ
-="=
££"=
åå
åå
12131423354552
121314
122352
13233435
143445
354552
Minimizar23262
s.a.1,
4,
0,
3,
6,
0.
ij
xxxxxxx
xxx
xxx
xxxx
xxx
xxx
x
+++++-
++=
-+-=-
--++=
--+=-
--+=
££¥
Minimizar
s.a.
lxu
££
cx
Ax=k
1
0
n
j
j
k
=
=
å
0
0
1
0
0
1
0
ijij
aee
æö
ç÷
ç÷
ç÷
ç÷
éùéù
===-
ç÷
ëûëû
ç÷
ç÷
-
ç÷
ç÷
èø
A
3434131554
()
rcccc
=--++
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
1414342312
13131223
35355223
4545342352
10223
3221
6226
10221
rcccc
rccc
rccc
rcccc
=-++=-++=-
=-+=-+=-
=---=--=
=----=---+=
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
1212143423
13131434
35355223
4545342352
21023
3102
6226
10221
rcccc
rccc
rccc
rcccc
=---=---=
=--=--=
=---=--=
=----=---+=
(
)
(
)
(
)
(
)
(
)
(
)
1,21,32,32,43,23,4
1110000
2101110
3011011
4000101
æö
ç÷
--
ç÷
=
ç÷
--
ç÷
--
èø
A
(
)
Minimizar 
..,
,0
donde viene dada por:
11000010004
10111001002
01101100101
00010100015
sa
x
w
w
w
w
±=
³
±=
æö
æö
ç÷
ç÷
--
ç÷
ç÷
=
ç÷
ç÷
----
ç÷
ç÷
ç÷
----
èø
èø
Axk
Axk
x
1
3
4
2
2
4
3
-5
-1
6
k
2
=2
k
4
=-5
k
3
=-1
k
1
=4
1
3
4
2
2
4
3
-5
-1
6
k
2
=2
k
4
=-5
k
3
=-1
k
1
=4