Metodo del simplesso per distribuzione single commodity
by user
Comments
Transcript
Metodo del simplesso per distribuzione single commodity
Claudio Arbib Università dell’Aquila Ricerca Operativa Metodo del simplesso per problemi di distribuzione single-commodity Scenario • Un insieme di produttori (consumatori) offre (richiede) determinati quantitativi di un medesimo bene rappresentati da un vettore di domanda d • Ipotesi single commodity: non ha importanza da quali produttori ciascuno dei consumatori ottenga la quantità richiesta • La distribuzione avviene mediante una rete conservativa, dove produttori e consumatori sono rappresentati da nodi e la distribuzione avviene attraverso un insieme di archi che li collega gli uni agli altri (grafo connesso G = (V, E)) • Attraversare l’arco ij comporta un costo cij per unità di bene trasportato (costi lineari) • Il flusso nel generico arco ijE dev’essere compreso fra una soglia lij e una capacità uij Problema • Calcolare una distribuzione di flusso che attribuisca a ciascun arco ij di G un flusso reale xij compreso tra lij e uij e in tal modo soddisfi il vettore di domanda d al costo più basso possibile: min c l u 2 0 3 a d = –10 0 0 –1 –2 7 6 1 2 3 4 5 6 7 10 8 0 0 9 6 b c cx Ax = d l<x<u –10 1 b 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 d e f g h i j 5 0 9 0 –1 3 2 c 4 e g f i 6 7 0 d h k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 a 5 –2 k j 7 6 Basi • Una base è un insieme massimale di colonne di A linearmente indipendenti Teorema: k colonne di A sono linearmente indipendenti se e solo se gli archi corrispondenti non formano cicli Dimostrazione: se C è un ciclo corrispondente a colonne di A, scegliamo un verso di percorrenza e moltiplichiamo per +1 1 ogni colonna associata a un arco concorde col b a verso e per –1 ogni colonna associata a un arco discorde. Sommando si ottiene la colonna 0. 3 2 c –1 a 1 2 3 4 5 6 7 +1 +1 –1 b c d d 4 h e f g h i j e g k –11 –1 0 0 0 0 0 0 0 0 0 –1 1 0 0 –1 1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 –1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 f i 6 k 5 j 7 Basi • Una base è un insieme massimale di colonne di A linearmente indipendenti Teorema: k colonne di A sono linearmente indipendenti se e solo se gli archi corrispondenti non formano cicli Dimostrazione: Viceversa, sia B un insieme massimale di archi di G che non formano cicli (albero ricoprente T). Si visitino i 1 nodi e gli archi di di T in post-ordine permutando a b le righe (nodi) e le colonne (archi) della matrice via via che si visitano. Con una colonna unitaria, 3 2 c d la matrice è triangolare e ha determinante 1 4 h b 1 3 4 6 7 5 2 c d i j e g e –1 0 0 0 0 0 0 1 –1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 –1 –1 –1 0 0 0 –1 0 0 1 1 f i 6 5 j k 7 Soluzioni di base • In una soluzione di base, le variabili in base (archi di T ) assumono valori compresi tra lij e uij • Una variabile fuori base invece è fissata o al valore di soglia lij oppure al valore della capacità uij • Siano B, L, U gli insiemi di archi corrispondenti a variabili in base oppure fuori base dei due tipi. Il problema min cBxcx B + cLxL + cUxU ABxAx dLxL + AUxU = d si riscrive (eliminando una riga B +=A l < lx<<xu< u in modo che AB sia quadrata) • • • Sostituendo nella funzione obiettivo xB = AB–1(d – ALxL – AUxU) questa diventa cBAB–1d + (cL – AB–1AL)xL + (cU – AB–1AU)xU Per i costi ridotti fuori base si ha quindi cL’ = (cL – AB–1AL) cU’ = (cU – AB–1AU) Poiché le variabili fissate alla soglia (alla capacità) possono solo aumentare (diminuire) il loro valore, la base corrente sarà ottima se cL’ > 0, cU’ < 0 (criterio di ottimalità) Calcolo di una prima soluzione Trasformare il problema ponendo x’ = x – l > 0 e quindi sostituendo x = x’ + l minmin cx’ + cxcl Ax’Ax = (d= –d Al) = d’ 0 < lx’<<x u’ =u–l <u c l u’ 2 0 3 a –10 0 0 d’ = 0 0 4 6 1 2 3 4 5 6 7 10 8 0 0 9 6 b c 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 9 9 9 5 d e f g h i j 5 0 9 –10 1 b 0 3 0 c 0 d e g f i 6 4 2 4 h k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 a k 5 j 7 6 0 Calcolo di una prima soluzione Aggiungere i nodi s e t, collegarli alle sorgenti e ai pozzi k con capacità pari a |dk|, trovare il max (s, t)-flusso; se è < kP dk non c’è soluzione s Altrimenti, ricavare x = x’ + l (ammissibile) x’ 2 8 1 2 0 0 3 7 0 0 6 x 2 8 1 2 0 0 4 7 2 0 6 c l u’ 2 0 3 10 8 0 0 9 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 9 9 9 5 5 0 9 a –10 0 0 d’ = 0 0 4 6 1 2 3 4 5 6 7 b c d e f g h i j 10 1 b 8 0 3 1 c 0 0 e g 3 f i 6 4 2 2 d 4 7 h k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 a 2 k6 j 7 t 5 6 0 Calcolo di una prima soluzione Aggiungere i nodi s e t, collegarli alle sorgenti e ai pozzi k con capacità pari a |dk|, trovare il max (s, t)-flusso; se è < kP dk non c’è soluzione –10 Altrimenti, ricavare x = x’ + l (ammissibile) 1 b8 x c l u 2 2 0 3 a d= –10 0 0 –1 –2 4 6 1 2 3 4 5 6 7 8 1 10 8 0 0 8 6 b c 2 0 0 4 7 2 0 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 d e f g h i j a 2 6 5 0 9 0 3 1c 0 e g f 4 i2 6 7 2 4 7 h k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –1 d2 5 –2 6k j 7 6 Calcolo di una prima base Una soluzione di base ha almeno m – n + 1 variabili fissate ai valori di soglia o capacità (variabili fuori base); se quindi vi sono più di n – 1 variabili con valori strettamente compresi tra lij e uij la x trovata non è di base –10 lij < xij < uij per 7 > n – 1 variabili n = 7, m = 11 1 b8 x c l u 2 2 0 3 a d= –10 0 0 –1 –2 4 6 1 2 3 4 5 6 7 8 1 10 8 0 0 9 6 b c 2 0 0 4 7 2 0 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 d e f g h i j a 2 6 5 0 9 0 3 1c 0 e g f 4 i2 6 7 2 4 7 h k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –1 d2 5 –2 6k j 7 6 Calcolo di una prima base Gli archi associati a queste variabili formano 2 cicli, da eliminare con operazioni di pivot. Nella prima, = min{9 – 8, 6 – 1, 2 – 0, 2 – 0} = 1 lij < xij < uij per 7 > n – 1 variabili n = 7, m = 11 b8 x 2 1 8 9 c l u 2 0 3 10 8 0 0 9 6 a d= –10 0 0 –1 –2 4 6 1 2 3 4 5 6 7 b 1 2 c 2 0 1 2 0 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 d e 0 4 f g 7 h i j 3 2– a 2 1c + d2 – 2 4 7 h e g k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 + 1 f 4 i2 6 6k 5 j 7 Calcolo di una prima base Gli archi associati a queste variabili formano 2 cicli, da eliminare con operazioni di pivot. Nella seconda, = min{2 – 0, 9 – 7, 4 – 1} = 2 lij < xij < uij per 7 > n – 1 variabili n = 7, m = 11 1 b9 8 x 1 9 c l u 2 0 3 10 8 0 0 9 6 a d= –10 0 0 –1 –2 4 6 1 2 3 4 5 6 7 b 2 0 c 1 0 2 0 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 d e 0 24 f g 97 h i j 3 1 1c – 2 2 2 d1 4 h 7 +7 e g f 4– k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 a 2 i2 6 6k 5 j 7 Calcolo di una prima base Nella soluzione ottenuta gli archi (viola) associati alle variabili strettamente comprese tra lij e uij non formano cicli, ma sono meno di n – 1 e quindi non ricoprono il grafo. Un albero ricoprente (base degenere) si ottiene aggiungendo archi associati a variabili fuori base che non formino cicli con gli archi viola 1 b9 8 x 1 9 c l u 2 0 3 10 8 0 0 9 6 a d= –10 0 0 –1 –2 4 6 1 2 3 4 5 6 7 b 0 c 1 0 2 0 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 d e 0 2 f g 9 h i j 3 1 1 0c 2 2 d1 4 h 97 e g k –1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0 0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0 0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 a 2 f 4 2 i2 6 6k 5 j 7 Calcolo dei costi ridotti Per ottenere il costo ridotto c’ = (c – cBAB–1A) non è necessario invertire AB. Sia y = cBAB–1, cioè y risolve il sistema di n – 1 equazioni in n incognite – yi + yj = cij ij B Siccome righe e colonne di B possono essere permutate con una visita in postordine ricavando una matrice triangolare, il 1 b a sistema è di facile risoluzione cB 7 3 1 2 4 6 5 5 8 2 5 10 4 k c a d g 3 1 0 0 0 0 0 0 –1 0 0 0 0 0 0 –1 0 0 0 0 0 1 –1 0 0 0 1 0 1 –1 0 –1 0 0 0 1 1 0 0 0 0 0 –1 2 c i y7 = – y19 6= 5 y34 = – –y34= 8 y12 = – –y13= 2 y24 = – –y21= 5 y46 = – y44= 10 y6 = – y14 5= 4 d 4 h e g f i 6 k 5 j 7 Per il potenziale d’ingresso y5 si sceglie un valore arbitrario (es., y5 = 10) Calcolo dei costi ridotti Servendosi di y si calcola ora il costo ridotto c’ = (c – yA) delle variabili fuori base ij L U cij’ = cij + yi – yj cb’ = ch ’ = ce’ = cf ’ = cj ’ = cb + y1 – y3 ch + y3 – y6 ce + y5 – y2 cf + y4 – y5 cj + y5 – y7 = = = = = Si ha xb = xh = 9 xe = xf = xj = 0 Quindi xb e xj sono candidate a entrare in base: scegliamo xb 10 – 3 + 4 12 – 4 – 14 7 + 10 + 1 6 + 4 – 10 3 + 10 – 19 y7 = 19 y3 = – 4 y1 = – 3 y2 = – 1 y4 = 4 y6 = 14 = = = = = 11 –6 18 0 –6 1 bb a 3 2 c d 4 h e g f i 6 k 5 j 7 Per il potenziale d’ingresso y5 si sceglie un valore arbitrario (es., y5 = 10) Calcolo della nuova base L’aggiunta dell’arco b genera un ciclo. Lo si elimina con un pivot cercando di far diminuire il flusso su b c l u 2 0 3 10 8 0 0 9 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 a b d k c e f g h i j –10 9b– Dalla tabella risulta = min{3 – 1, 9 – 0, 0 – 0, 5 – 1} = 0 Si ha xb = xh = 9 xe = xf = xj = 0 Quindi xb e xj sono candidate a entrare in base: scegliamo xb 3 1 1+ a –1 0c– 1d+ 4 9h e g f 2 i2 6 7 2 5 –2 6k j 7 6 Calcolo della nuova base L’aggiunta dell’arco b genera un ciclo. Lo si elimina con un pivot cercando di far diminuire il flusso su b c l u 2 0 3 10 8 0 0 9 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 a b d k c e f g h i j –10 1 9b Dalla tabella risulta = min{3 – 1, 9 – 0, 0 – 0, 5 – 1} = 0 La variabile xb è entrata in base con valore 9, la variabile xc è uscita dalla base con valore 0 I flussi non sono stati alterati, perché le basi coinvolte nell’operazione sono degeneri 7 Proviamo allora a far entrare in base xj, il cui flusso può crescere con costo ridotto –16 a 1 1 –1 3 c0 2 11 d 4 9h e g f 2 i2 6 5 –2 6k j 7 6 Calcolo della nuova base Il flusso nell’arco i deve decrescere, e così quello nell’arco k. c l u 2 0 3 10 8 0 0 9 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 a b d k c e f g h i j –10 1 9b Dalla tabella di soglie e capacità si ha = min{2 – 2, 5 – 0, 6 – 0} = 0 a 1 1 –1 3 c 11 d 4 9h L’arco i ha infatti soglia 2, pari al flusso attuale: ancora una volta la distribuzione è inalterata e g f 2 i2 6 7 2 6k – 5 j 0+ 7 6 – –2 Calcolo della nuova base Il flusso nell’arco i deve decrescere, e così quello nell’arco k. c l u 2 0 3 10 8 0 0 9 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 a b d k c e f g h i j –10 1 9b Dalla tabella di soglie e capacità si ha = min{2 – 2, 5 – 0, 6 – 0} = 0 L’arco i ha infatti soglia 2, pari al flusso attuale: ancora una volta la distribuzione è inalterata Il calcolo dei costi ridotti offre ora cf’ = –6 con xf fissata alla soglia uf = 0 a 1 1 –1 3 c 11 d 4 9h e g f 2 i2 6 7 2 5 –2 6k 0j 7 6 Calcolo della nuova base Il flusso nell’arco i deve decrescere, e così quello nell’arco k. c l u 2 0 3 10 8 0 0 9 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 a b d k c e f g h i j –10 1 9b Il ciclo introdotto coinvolge f, g, j, k Il flusso in f e j aumenta, quello in g e k diminuisce di = min{4 – 0, 2 – 1, 5 – 0, 6 – 0} = 1 a 1 1 –1 3 c 11 d 4 9h e 2 –2 0+ g f i2 6 7 2 6 6–k 5 0 j+ 7 6 –2 Calcolo della nuova base Il flusso nell’arco i deve decrescere, e così quello nell’arco k. c l u 2 0 3 10 8 0 0 9 6 5 7 6 10 12 4 3 0 0 0 1 0 2 0 5 10 4 10 9 11 5 5 0 9 a b d k c e f g h i j –10 1 9b Il ciclo introdotto coinvolge f, g, j, k Il flusso in f e j aumenta, quello in g e k diminuisce di = min{4 – 0, 2 – 1, 5 – 0, 6 – 0} = 1 a 1 1 –1 3 c 11 d 4 9h i2 6 7 e 1f 1g L’arco g esce di base fissando il proprio flusso al valore di soglia 1 2 5 –2 5k 1j 7 6