Minimum Cost Flow Problem

Question 1

Definisci il MCFP

Answer 1

Consiste nel mandare un certo ammontare di flusso attraverso una rete capacitata con costo minimo

Question 2

Assunsioni del MCFP

Answer 2

1) Tutti i dati sono interi
2) G=(N,A) è una rete orientata
3) Sum _ {i \in N} b(i) =0

Question 3

Cos’è una Circolazione?

Answer 3

Un qualsiasi vettore di flow x’ con entrate (xij’) tale che b(i)=0 for all i in N è chiamato Circolazione

Question 4

Quali sono le condizioni di ottimalità del MCFP?

Answer 4

Negative cycle, reduced cost, complementary slackness

Question 5

Negative cycle optimality

Answer 5

Una soluzione ammissibile per l’MCFP x° è ottimale se e soltanto se G(X°) non contiene cicli orientanti negativi.

Question 6

Reduced cost optimality

Answer 6

Sia pi(i) il potenziale del nodo i.Il che rappresenta il duale LP della mass balance constraints.
Per un insieme di nodi potenziali definiamo  i costi ridotti di un arco (i,j) come : cij^{pi}=cij- pi(i) + pi(j)

Question 7

Proprietà dei costi ridotti

Answer 7

1) Sum_(i,j) in p cij^pi ) Sum_(i,j) in p cij - pi(k) + p(l)

2) Sum_(i,j) in W cij^pi = Sum_(i,j) in W cij

Question 8

Complementary slackness condition

Answer 8

Una soluzione ammisibile x* di un MCFP è ottimale se e soltanto se esiste un insieme di variaibli duali (o potenziali) pigreco, tali che le seguenti condizioni si mantengono per ogni arco:

1) se cij^p>0,allora xij*=0
2) se 0

Question 9

Definizione di arco LIBERO e RISTRETTO

Answer 9

Per ogni vettore di flow x ammissibile un arco (i,j) si dice LIBERO se 0

Question 10

Quando una soluzione è cycle-free

Answer 10

Una soluzione del MFCP è cycle free se tutti i cicli hanno almeno un arco ristretto.