TEMA 5: El problema del flujo con costo mínimo
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
1
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 coste 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.
kj
j
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
i
xij
cij
j
Profesor: Jose Mª del Castillo Granados
2
Formulación matemática del problema.
La formulación matemática del problema de
flujo con costo mínimo queda como:
n
Minimizar
n
 c x
i 1 j 1
s.a.

kD ( j )
ij ij
x jk 

iA ( j )
lij  xij  uij
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
xij k j
j  1, 2,..., n
i, j  1, 2,..., n
Profesor: Jose Mª del Castillo Granados
3
Ejemplo:
k1=1
1
1
k4=-3
Minimizar
s.a.
2
3
0
4
2
3
k2=-4
2
-2
6
k3=0
1
5
k5=6
2 x12  3x13  x14  2 x23  6 x35  x45  2 x52
x12  x13  x14  1,
 x12  x23  x52  4,
 x13  x23  x34  x35  0,
 x14  x34  x45  3,
 x35  x45  x52  6,
0  xij  .
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
4
Propiedades del problema
El problema puede reescribirse, en forma matricial,
como:
Minimizar cx
s.a. Ax = k
l  xu
Matriz de incidencia, A=[aij], [aij]=ei-ej
y ei es el vector unitario i-ésimo.
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
5
Propiedades del problema
• Adicionando todas las filas de la matriz A se
tiene que  k  0 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.
n
j 1
j
• Propiedades importantes:
1. El rango de la matriz A es n-1
2. Las soluciones del problema son siempre enteras para valores
de ki enteros.
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
6
Propiedades del problema
1. El rango de la matriz A es n-1
Tantas columnas como arcos
(i,j)





A





0
0
1
0
0
1
0
Tantas filas como nodos


aij es la columna de A que corresponde

al arco que une los nodos i y j


   aij   ei  e j 

xij

j
i


xij aparece en la ecuación del

Dimensiones de A:
nodos (n) x arcos
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
nodo i con signo + y en la
ecuación del nodo j con signo -
Profesor: Jose Mª del Castillo Granados
7
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
n
j
m
k
l
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.
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
8
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.
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
9
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
4
1
3
5
2
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
10
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.
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
11
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:
5
1
3
2
4
r34 = c34 – (–c13+c15+c54 )
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
12
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
e
5
e
e
3
2
e
4
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
13
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
e
– multiplicados por -1 si lo esta a favor.
5
1
– Para el ciclo de la figura, se tiene:
e
r34  c34  (c13  c15  c54 )
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
e
3
2
e
4
Profesor: Jose Mª del Castillo Granados
14
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:
k1=1
1
1
k4=-3
1
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
4
5
1
1
3
3
k3=0
k5=6
k2=-4
2
3
1
-2
6
k3=0
3
k2=-4
2
2
3
4
k1=1
k4=-3
3
0
1
• Donde en cada arco se define
el flujo que circula y que es
factible ya que cumple las
leyes de Kirchhoff en cada
nodo.
2
6
6
5
k5=6
Profesor: Jose Mª del Castillo Granados
15
Ejemplo
• Los costos relativos de los
arcos no básicos serán:
k1=1
1
r14  c14   c34  c23  c12   1   0  2  2   3
r13  c13   c12  c23   3   2  2   1
r35  c35   c52  c23   6   2  2   6
1
1
3
3
k4=-3
4
k1=1
1
3
3
k2=-4
2
6
6
k3=0
k5=6
5
1
r45  c45   c34  c23  c52   1   0  2  2   1
• Introduciendo el arco r14
en la base:
r12  c12   c14  c34  c23   2  1  0  2   3
r13  c13   c14  c34   3  1  0   2
r35  c35   c52  c23   6   2  2   6
r45  c45   c34  c23  c52   1   0  2  2   1
• Habiéndose
el óptimo.
1
k4=-3
1
3
2
4
2
3
k3=0
1
k2=-4
2
6
6
5
k5=6
alcanzado
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
16
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
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
17
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
s.a.
w
Ax ± w = k,
(x,w) >= 0
Su optimización definirá una base inicial.
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
18
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
4
2
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
• 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.
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
19
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
4
2
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
• la matriz de incidencia nodo-arco es:
1, 2  1,3  2,3  2, 4   3, 2  3, 4 
1 1

2  1
A
3 0

4 0
1
0
1
0
0
1
1
0
0
1
0
1
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
0
1
1
0
0

0
1

1
Profesor: Jose Mª del Castillo Granados
20
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
k =2
resuelve el problema en la Fase I:
2
2
4
2
k1=4
w
Minimizar
s.a.
6
1
-1
-5
4 k4=-5
3
3
k3=-1
Ax  w  k ,
 x, w   0
donde Ax  w  k viene dada por:
1

 1
0

0
1
0
1
0
0
1
1
0
0
1
0
1
0
1
1
0
0
0
1
1
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
1
0
0
0
0 0 0
4

 
1 0 0
2

x

 1 
0 1 0

 
0 0 1
 5 
Profesor: Jose Mª del Castillo Granados
21
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
• La tabla de simplex es:
4
2
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
x (-1)
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
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
22
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
• La tabla de simplex es:
4
2
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
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
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
23
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
4
2
• Aplicando Simplex se tiene:
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
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
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
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
1
Profesor: Jose Mª del Castillo Granados
24
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
4
2
• Aplicando Simplex se tiene:
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
x12
x13
x23
x24
x32
x34
w1
w2
w3
w4
k
1
0
-1
0
1
1
1
0
-1
0
3
-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
-2
0
-2
0
0
2
0
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
ki/aij
2
5
Profesor: Jose Mª del Castillo Granados
25
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
4
2
• Aplicando Simplex se tiene:
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
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
-2
0
2
0
-2
-2
0
2
2
0
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
3
Profesor: Jose Mª del Castillo Granados
26
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
4
2
• Aplicando Simplex se tiene:
k1=4
6
1
-1
-5
4 k4=-5
3
3
k3=-1
x12
x13
x23
x24
x32
x34
w1
w2
w3
w4
k
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
ki/aij
Se ha alcanzado el final de la fase I y la solución básica factible es:
x12=3
x13=1
x24=5
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
27
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
k2=2
2
5
3
k1=4
4 k4=-5
1
1
3
k3=-1
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:
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
Profesor: Jose Mª del Castillo Granados
28
Ejemplo: Obtener el flujo máximo con costo mínimo en la red.
Introduciendo x34 en la base, se tiene:
k2=2
2
5-3=2
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
k1=4
1+3=4
Explotación del Transporte Aéreo, 5º Ing. Aeronáutico
3
5-3=2
k1=4
4 k4=-5
1
1+3=4
Todos positivos  Óptimo
3
k3=-1
k2=2
2
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
4 k4=-5
1
3
k3=-1
3
Profesor: Jose Mª del Castillo Granados
29
Descargar

Linear Programming