Explotación del Transporte Aéreo, 5º Ing. Aeronáutico Profesor: Jose Mª del Castillo Granados 1 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 Granados1

TEMA 5: El problema del flujo con costo mínimoTEMA 5: El problema del flujo con costo mínimo


Definición del problemaDefinició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.

j

kj

jixij

cij


Formulación matemática del problema.Formulación matemática del problema.

1 1

( ) ( )

Minimizar

s.a. 1, 2,...,

, 1, 2,...,

n n

ij iji j

jk ij jk D j i A j

ij ij ij

c x

x x k j n

l x u i j n

La formulación matemática del problema de flujo con costo mínimo queda como:


Ejemplo: Ejemplo:

12 13 14 23 35 45 52

12 13 14

12 23 52

13 23 34 35

14 34 45

35 45 52

Minimizar 2 3 2 6 2

s.a. 1,

4,

0,

3,

6,

0 .ij

x x x x x x x

x x x

x x x

x x x x

x x x

x x x

x

1 2

4 5

3

2

1

1

-2

3 2

60

k1=1

k4=-3k5=6

k2=-4

k3=0


Propiedades del problemaPropiedades 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.

Minimizar

s.a.

l x u

cx

Ax = k


Propiedades del problemaPropiedades 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:1. El rango de la matriz A es n-1

2. Las soluciones del problema son siempre enteras para valores de ki enteros.

10

n

jjk


Propiedades del problemaPropiedades del problema1. El rango de la matriz A es n-1

0

0

1

0

0

1

0

ij i ja e e

A

Tantas columnas como arcos

Tantas filas como nodos

(i,j)

Dimensiones de A: nodos (n) x arcos

i jxij

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


Ciclos y Dependencia LinealCiclos y Dependencia LinealDos 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 lm

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)+…=0por 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.


Ciclos y Dependencia LinealCiclos 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.


EjemploEjemplo

• 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


Algoritmo simplex para redesAlgoritmo 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.



• 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 )



• 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 por el arco 34, tendré que aumentar el flujo en en el arco 13 y decrementar enen 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 .

– 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



• 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:

34 34 13 15 54( )r c c c c

1

3 4

5

2


EjemploEjemplo

• 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

60

k1=1

k4=-3k5=6

k2=-4

k3=0

1 2

4 5

3

1

1

1

6

3 3

63

k1=1

k4=-3k5=6

k2=-4

k3=0


EjemploEjemplo

• Los costos relativos de los arcos no básicos serán:

1 2

4 5

3

1

1

1

6

3 3

63

k1=1

k4=-3k5=6

k2=-4

k3=0

14 14 34 23 12

13 13 12 23

35 35 52 23

45 45 34 23 52

1 0 2 2 3

3 2 2 1

6 2 2 6

1 0 2 2 1

r c c c c

r c c c

r c c c

r c c c c

1 2

4 5

3

1

1

1

6

3 2

62

k1=1

k4=-3k5=6

k2=-4

k3=0

• Introduciendo el arco r14 en la base:

12 12 14 34 23

13 13 14 34

35 35 52 23

45 45 34 23 52

2 1 0 2 3

3 1 0 2

6 2 2 6

1 0 2 2 1

r c c c c

r c c c

r c c c

r c c c c

• Habiéndose alcanzado el óptimo.


Obtención de una solución básica factible inicial.

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


Obtención de una solución básica factible inicial.

Obtención de una solución básica factible inicial.• se amplía el sistema de ecuaciones de restricciones con

variables de holgura ; 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. Ax ± = k,

(x,) >= 0

Su optimización definirá una base inicial.


Ejemplo: Obtener el flujo máximo con costo mínimo en la red.Ejemplo: Obtener el flujo máximo con costo mínimo en la red.

• donde a cada arco se le asocia el costo absoluto unitario ccijij, 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

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4



• la matriz de incidencia nodo-arco es:

1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4

1,2 1,3 2,3 2,4 3,2 3,4

1 1 1 0 0 0 0

2 1 0 1 1 1 0

3 0 1 1 0 1 1

4 0 0 0 1 0 1

A



• Para la obtención de una solución básica factible, se resuelve el problema en la Fase I:

Minimizar

. . ,

, 0

donde viene dada por:

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

s a

x

Ax k

Ax k

x

1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4



• La tabla de simplex es:

1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4

x12 x13 x23 x24 x32 x34 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)



• La tabla de simplex es:

1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4

x12 x13 x23 x24 x32 x34 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



• Aplicando Simplex se tiene: 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4

x12 x13 x23 x24 x32 x34 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




3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4

x12 x13 x23 x24 x32 x34 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




3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4

x12 x13 x23 x24 x32 x34 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




3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4 1

3

4

22 4

3-5

-16

k2=2

k4=-5

k3=-1

k1=4

x12 x13 x23 x24 x32 x34 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=3x13=1x24=5


Ejemplo: Obtener el flujo máximo con costo mínimo en la red.


1

3

4

23 5

1

k2=2

k4=-5

k3=-1

k1=4

Aplicando el criterio de optimalidad:

r23=c23-(c13-c12)= -1-(-5-2)=7r32=c32-(c12-c13)=6-(2+5)=-1r34=c34-(-c13+c12+c24)=3-(--5+2+4)=-8

Introduciendo x34 en la base, se tiene:




1

3

4

2

3

5-3=2

1+3=4

k2=2

k4=-5

k3=-1

k1=4Aplicando el criterio de optimalidad:

r12=c12-(c13+c34-c24)= 2-(-5+3-4)=8r23=c23-(c24-c34)=-1-(4-3)=-2r32=c32-(c34-c24)=6-(3-4)=7



r12=c12-(c13-c23)= 2-(-5+1)=6r24=c24-(c23+c34)=-1-(-1+3)=2r32=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

Documents

Explotación del Transporte Aéreo, 5º Ing. Aeronáutico Profesor: Jose Mª del Castillo Granados 1 TEMA 5: El problema del flujo con costo mínimo