Sesión de teoría. Modelos de flujos sobre redes. …Para el problema de flujos sobre redes...
Transcript of Sesión de teoría. Modelos de flujos sobre redes. …Para el problema de flujos sobre redes...
U P C I.O.E. Diplomatura de Estadística U P C
• Sesión de teoría. Modelos de flujos sobre redes.• Sesión de laboratorio.
U P C I.O.E. Diplomatura de Estadística U P C
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
10
15
12
13
FLUJOS SOBRE REDES
i
+1
j
-1
MATRIZ DE INCIDENCIAS AVECTOR DEFLUJOS x
INYECCIONESb
U P C I.O.E. Diplomatura de Estadística U P C
=
CASO EQUILIBRADO
2
3 5
4 6
1 1
8
7
9
10
3 6
4 2 5
10
15
12
13
EN LA MATRIZ A HAY UNA FILAREDUNDANTE:
• LAS BASES SON DE (m-1)×(m-1)
• Deben escogerse m-1 arcospara formar la matriz base B;
• Debe eliminarse una filacualquiera.
PROCEDIMIENTO:A) Construir sobre el grafo no direccional asociado unárbol de recubrimiento.B) Los arcos de la red correspondientes al árbol derecubrimiento forman una base B de A.
A x = b, x≥0
BASES DEL PROBLEMA DE COSTE MÍNIMO
2
3 5
4 6
1
A) CONSTRUCCIÓN DEL GRAFO NO DIRECCIONAL Y DELÁRBOL DE RECUBRIMIENTO.
ÁRBOL DE RECUBRIMIENTO: m-1 arcos; Sin ciclos; Tomar un nodo como raíz
2
3 5
4 6
1 2
3 5
4 6
1 2
3 5
4 6
1
SI SI NO
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
2
3 5
4 6
1 2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
10
15
12
13
2
3 5
4 6
1
6
2
1
3
5
4
6
2
1
3
5
4
BASE NOFACTIBLE
6
2
1
3
5
4
6
2
1
3
5
4
10
10
10
10
12-2
13
10
-13
-13
-15-15
10
13
13
0
13
10
12
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
10
15
12
13
2
3 5
4 6
1
BASEFACTIBLE
λi = - Coste unitario raíz → i
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
10
15
12
13
U P C I.O.E. Diplomatura de Estadística U P C
=
CASO EQUILIBRADO
LENGUAJE AMPL: DECLARACIONES NODE, ARC
set CIUDADES;set ARCOS within (CIUDADES cross CIUDADES);
param oferta {CIUDADES} >= 0; # inyeccionesparam demanda {CIUDADES} >= 0; # extracciones
check: sum {i in CIUDADES} oferta[i] = sum {j in CIUDADES} demanda[j];param coste {ARCOS} >= 0; # costes de transp.
minimize Total_Coste;
node Nodo {k in CIUDADES}: net_in=demanda[k]-oferta[k];
arc enlace {(i,j) in ARCOS} >= 0, from Nodo[i], to Nodo[j], obj Total_Coste coste[i,j];
REDES MULTIARTÍCULO
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
10
10
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
15
12
3
U P C I.O.E. Diplomatura de Estadística U P C I.O.D. Diplomatura de Estadística
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
10
10
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
15
12
3
=
2
3 5
4 6
1 1
8 7
9
10
3 6
4 2 5
10
15
12
13
U P C I.O.E. Diplomatura de Estadística U P C
2
3 5
4 6
1 12
12
3
15
12
3
2
3 5
4 6
1 10
10
10
10
10 2
3 5
4 6
1 12
2
13
10
15
12
13
=
set CIUDADES;set ARCOS within (CIUDADES cross CIUDADES);set PRODS;param OFERTA {CIUDADES,PRODS} >= 0;param DEMANDA {CIUDADES,PRODS} >= 0; check {p in PRODS}:sum {i in CIUDADES} OFERTA[i,p]=sum{j inCIUDADES}DEMANDA[j,p];
param coste {ARCOS,PRODS} >= 0;param CAP_CONJ {ARCOS} >= 0;minimize Total_Coste;
node Nodo {k in CIUDADES, p in PRODS}: net_in = DEMANDA[k,p] - OFERTA[k,p];
arc ENLACE {(i,j) in ARCOS, p in PRODS} >= 0, from Nodo[i,p], to Nodo[j,p], obj Total_Coste coste[i,j,p];
subject to Multi {(i,j) in ARCOS}: sum {p in PRODS} ENLACE[i,j,p] <= CAP_CONJ[i,j];
Artículo 1: 400 unidades de 1 a 2Artículo 2: 400 unidades de 3 a 4
Para el problema de flujos sobre redes multiartículo quedescribe el código AMPL siguiente:
• Formula el problema utilizando la matriz de incidenciasnodos-arcos que contine el fichero de parámetros.
• Resuelve el problema y dibuja su solución.• Suponiendo que hay un único artículo con demanda de 400
unidades en los nodos 2 y 4 respectivamente y oferta de 400en cada nodo 1 y 3, escribe el fichero de parámetros y utilizael modelo AMPL visto en clase para hallar la solución.
set nusos;set centr within nusos;set links within ( nusos cross nusos );set origens within centr;set destins within centr;set odpair within ( origens cross destins );set destperorig { i in origens } := setof { (i1, j1) in odpair : i = i1 } j1;param g{odpair} >0;param t0{links};param Tdreta { i in nusos, k in origens }:= if i in destperorig[k] then -1.0*g[k, i]
else if i = k then sum {j in destperorig[k]} g[k, j] else 0;
node N {i in nusos, k in origens}: net_out = Tdreta[i, k];arc v_k { (i, j) in links, k in origens } >= 0, from N[i, k], to N[j, k] ;
var v { (i, j) in links };
subject to flux_total { (i, j) in links }: v[i, j] = sum { k in origens } v_k[i, j, k];
minimize Vg: sum { (i, j) in links } v[i, j]*t0[i, j];