Probleme de transport

Probleme de transport

1. Retele de transport

Definitia 1. Un graf orientat ponderat G = (X, U, c) este o retea de transport daca este conex si exista un singur virf s fara predecesori si un singur virf t fara succesori:

- s I X este intrare in retea si G¹(s)    si G (s)

- t I X este iesire din retea astfel incit G¹(t)    si G (t)

- pentru orice alt virf x I X (x s si x t), G¹(x) si G (x)

Valoarea c(u) 0 este capacitatea arcului u I U.

Definitia 2. O functie j : U   R₊ defineste un flux in reteaua G daca:

a) pentru orice arc u I U avem j(u)   c(u) (fluxul este compatibil cu reteaua);

b) pentru orice virf x I X (x   s si x   t) se respecta legea conservarii fluxului:

unde am notat:

w (x) multimea arcelor incidente interior

virfului x;

w (x) multimea arcelor incidente exterior

virfului x;

Din b) se deduce relatia:

Valoarea comuna a celor doua sume este valoarea fluxului j si se noteaza v(j

Definitia 3. Un arc u I U pentru care j(u)   c(u) se numeste arc saturat.

Problema. In multimea fluxurilor compatibile cu o retea data, exista citeva fluxuri particulare:

- un flux de valoare zero, numit fluxul nul;

- unul sau mai multe fluxuri de valoare maxima, numite fluxuri maxime.

Se cere sa se determine un flux maxim intr-o retea.

Aplicatie. Fie o retea de cale ferata, unde se cunoaste capacitatea fiecarei linii. Care este cantitatea maxima care poate fi transportata de la o statie s la o alta statie t, respectindu-se definitia 2, si cum trebuie organizat transportul?

Exemple

(1) Problema ilustrata in figura 1 are mai multe solutii posibile, fiecare conducind la aceeasi valoare a fluxului maxim: cinci. Capacitatile arcelor exprimate in unitati sint: arcul (x₀, x₁) - cinci, arcele (x₀, x₂) si (x₂, x₃) - doi, si arcele (x₁, x₂) si (x₁, x₃) - trei.

In prima solutie se propune transportarea a patru unitati de la x₀ la x₁, apoi doua unitati se transporta de la x₁ la x₃, si celelalte doua unitati de la x₁ la x₂. Din x₀ se transporta o unitate la x₂, si de aici se preiau trei (doua plus una) unitati care se transporta la x₃. Astfel din x₀ pleaca cinci unitati care ajung in x₃.

Figura 1. O retea de transport si doua solutii posibile.

(2) Problema ilustrata in figura 2 are o singura solutie. Pe ruta (x₀, x₁, x₄, x₅) se transporta o unitate, si pe ruta (x₀, x₂, x₃, x₅) se transporta de asemenea o unitate (figura 5).

Aceasta problema va fi folosita ca exemplu in sectiunea 4 pentru implementarea algoritmului Edmonds-Karp.

Figura 2. Retea de transport, model pentru algoritmul Edmonds-Karp.

2. Determinarea unui flux maxim

Intr-o problema practica, inainte de a determina fluxul maxim, graful se ajusteaza astfel: se renunta la arcele care intra in virful s, si la arcele care ies din virful t. Inainte de a descrie un algoritm care determina un flux maxim intr-o retea definim notiunea de taietura in retea.

Definitia 4. Fie Y   X o submultime cu proprietatea ca s I Y si t   Y. Submultimea w (Y ) este o taietura in retea. Capacitatea taieturii este:

c(w (Y ))

Teorema 1. Pentru orice flux j si orice taietura w (Y) avem:

v j c(w (Y)) (Ford, Fulkerson)

Demonstratie Fiind data o taietura, orice flux trebuie sa o strabata pentru a ajunge de la s la t. Fluxul poate sa satureze unele arce ale retelei, pe altele nu. Daca toate arcele ar fi saturate, am avea v(j c(w (Y)), altfel v(j < c(w (Y)). n

Algoritmul Ford-Fulkerson

Se porneste initial cu fluxul nul. Un flux compatibil oarecare se majoreaza folosind urmatorul procedeu de marcare a virfurilor, virful s fiind intotdeauna marcat:

a) daca x este marcat si (x,y) I U, iar j(x,y) < c(x,y), atunci se marcheaza virful y cu x

b) daca x este marcat si (y,x) I U, iar j(y,x) > 0, atunci se marcheaza virful y cu x

c) daca x este marcat si j(x,y)   c(x,y) sau j(y,x) 0, atunci virful y nu se poate marca.

Daca prin acest procedeu se ajunge sa se marcheze virful t, exista un lant m de la s la t cu toate virfurile marcate. Notam cu A submultimea arcelor sale din categoria a) si cu B submultimea arcelor sale din categoria b). Punem:

wa min ;

wb min

w min (wa, wb)

Definim un flux nou j' astfel: j'(u)

care are proprietatea ca v(j v(j)   w

Pentru obtinerea unui flux maxim se repeta aceasta procedura pina cind virful t nu se mai poate marca.

Ramine sa demonstram ca ultimul flux este maxim. Fie acesta y si fie Y submultimea virfurilor care au putut fi marcate in retea dupa introducerea acestui flux. Deoarece s I Y si t   Y, se poate defini o taietura w (Y). Avem:

v(y

Dar c(u) deoarece altfel s-ar putea continua marcajul in Y prin arce de categoria a).

De asemenea 0 deoarece altfel s-ar putea continua marcajul in Y prin arce de categoria b).

Deci v(y)   c(w (Y)) si, conform teoremei 1, fluxul y este maxim, iar capacitatea taieturii w (Y ) este minima. Rezulta

Teorema 2 (Ford-Fulkerson, 1956). Intr-o retea de transport, valoarea maxima a fluxului este egala cu capacitatea minima a taieturilor.

In lucrarea Introducere in algoritmi (Cormen et al) sint descrisi in detaliu mai multi algoritmi care determina fluxul maxim. Cei mai eficienti algoritmi folosesc conceptul de preflux. Intr-o prima faza se parcurge reteaua de la s la t si se obtine un pseudoflux, care nu respecta legea conservarii, deoarece are proprietatea:

pentru orice x s si x t

Cantitatea care intra in virful t coincide cu valoarea fluxului maxim. In faza a doua se parcurge reteaua de la t la s pentru a elimina surplusurile si astfel se obtine un flux maxim.

3. Algoritmul Edmonds-Karp

Algoritmul Ford-Fulkerson nu precizeaza cum se determina lanturile pe care se va mari fluxul - daca se iau in considerare toate lanturile posibile, complexitatea algoritmului poate deveni exponentiala. De aceea au fost elaborate metode de accelerare a acestuia, care conduc la un ordin polinomial de complexitate. O astfel de tehnica a fost elaborata de Edmonds si Karp.

Pentru a determina un lant pe care urmeaza sa se mareasca fluxul se construieste graful ecart al retelei de transport curente. Acest graf are aceeasi multime de virfuri X, si multimea U' a arcelor este definita astfel:

arce de tip (a): daca j(x,y) < c(x,y) atunci (x,y) I U

arce de tip (b): daca j(x,y) > 0 atunci (y,x) I U

Fie un drum de lungime minima de la s la t in graful ecart, (,, , ). Acest drum corespunde unui lant in reteaua curenta, pe care se poate obtine marirea fluxului. Pe lantul corespondent L(, , , ), care nu este neaparat un drum, se determina:

wa min

wb min

w min (wa, wb

Pe acest lant se mareste fluxul:

j(u)

Daca nu exista nici un drum intre s si t, algoritmul se incheie si fluxul obtinut este maxim.

Algoritmul de determinare a unui drum de lungime minima reuseste sa marcheze citeva virfuri din graful ecart, cel putin virful s. Cu ajutorul algoritmului Edmonds-Karp se poate determina si taietura de capacitate minima, daca se iau toate arcele cu virfuri initiale din multimea celor marcate si cu virfuri finale din multimea celor nemarcate.

Algoritmul Edmonds-Karp are complexitate teoretica de ordin O(n m²

Tehnici de implementare

Reteaua de transport din figura 2 este folosita ca exemplu pentru a arata cum lucreaza algoritmul Edmonds-Karp. Aceasta retea se reprezinta astfel:

Hr 0 2 4 5 6 7 7

Sr 1 2 3 4 3 5 5

C 1 2 3 2 3 1 3

(0) (1) (2) (3) (4) (5) (6)

Pentru a usura citirea corespondentei dintre reteaua originala si graful ecart am pus in evidenta indicii in masivul Sr.

In figura 3 se marcheaza fluxul nul (stinga) si se construieste graful ecart (dreapta). In graful ecart este marcat un drum de lungime minima - (x₀, x₁, x₃, x₅) - cu linie continua, si celelalte arce cu linie intrerupta.

Figura 3. Algoritmul Edmonds-Karp dupa initializare.

Pe acest drum se determina valoarea cu care va fi marit fluxul:

(x₀, x₁): c(x₀,x₁) - j(x₀,x₁) 1 - 0 1

(x₁, x₃): c(x₁,x₃) - j(x₁,x₃) 3 - 0 3

(x₃, x₅): c(x₃,x₅) - j(x₃,x₅) 1 - 0 1

Fluxul va fi marit pe acest drum cu valoarea 1.

Graful ecart din figura 3 se reprezinta astfel:

He 0 2 4 5 6 7 7

Se 1 2 3 4 3 5 5

P 0 1 2 3 4 5 6

(0) (1) (2) (3) (4) (5) (6)

Masivul P are urmatoarea semnificatie. (x,y) este un arc in graful ecart, si succesorul y se afla pe pozitia j in masivul Se: Se[j]   y. P[j] indica pozitia arcului corespondent din graful original. In aceasta faza P[j]   j (j   0, 1, , n-1) deoarece exista o corespondenta unu la unu intre arcele celor doua grafuri, si orientarile arcelor corespondente coincid.

Figura 4. Algoritmul Edmonds-Karp dupa prima iteratie.

In figura 4 se marcheaza fluxul obtinut dupa marire (stinga), si se construieste graful ecart (dreapta). Drumul de lungime minima este (x₀, x₂, x₃, x₁, x₄, x₅). In aceasta figura exista un arc de tip (b) - (x₃, x₁). Initial fluxul de pe arcul (x₀, x₁) a fost directionat spre arcul (x₁, x₃) si apoi spre arcul (x₃, x₅). La pasul urmator se constata ca de fapt un flux care pleaca pe ruta (x₀, x₂, x₃) nu poate ajunge in x₅, si de aceea fluxul care a avut ruta (x₀, x₁, x₃, x₅) trebuie redirectionat pe o alta ruta - (x₀, x₁, x₄, x₅). Astfel se explica de ce la a doua iteratie drumul determinat in graful ecart este (x₀, x₂, x₃, x₁, x₄, x₅).

Pe acest drum se determina valoarea cu care va fi marit fluxul:

(x₀, x₂): c(x₀,x₂) - j(x₀,x₂) 2 - 0 2

(x₂, x₃): c(x₂,x₃) - j(x₂,x₃) 3 - 0 3

(x₃, x₁): j(x₁,x₃) 1 (arcele corespondente au orientari opuse)

(x₁, x₄): c(x₁,x₄) - j(x₁,x₄) 2 - 0 2

(x₄, x₅): c(x₄,x₅) - j(x₄,x₅) 3 - 0 3

Fluxul va fi marit pe acest drum cu valoarea 1.

Graful ecart din figura 4 se reprezinta astfel:

He 0 1 3 4 5 6 6

Se 2 3 4 3 1 5

P 1 2 3 4 2 6

(0) (1) (2) (3) (4) (5)

Sa analizam doua corespondente de arce pentru acest caz.

Arcul (x₁, x₄) din graful ecart, care corespunde arcului (x₁, x₄) din retea, este memorat astfel. Pe pozitia j   2 este memorat virful final x₄: Se[j]   4. P[j]   k   3 indica faptul ca arcul corespondent din retea este memorat pe pozitia k: Sr[k]   4. Ambele arce au acelasi virf final, deci au aceeasi orientare.

Arcul (x₃, x₁) din graful ecart, care corespunde arcului (x₁, x₃) din retea, este memorat astfel. Pe pozitia j   4 este memorat virful final x₁: Se[j]   1. P[j]   k   2 indica faptul ca arcul corespondent din retea este memorat pe pozitia k: Sr[k]   3. Cele doua arce nu au acelasi virf final, deci au orientari opuse.

In figura 5 se observa ca dupa ce s-a marcat fluxul obtinut dupa marire (stinga), si s-a construit graful ecart (dreapta), nu mai exista drumuri de la x₀ la x₅. In concluzie algoritmul se incheie in aceasta faza, obtinindu-se fluxul maxim de valoare doi.

Figura 5. Algoritmul Edmonds-Karp dupa a doua iteratie.

Algoritmul de determinare a unui drum de la x₀ la x₅ reuseste sa marcheze doar virfurile x₀, x₂ si x₃. Se obtine astfel o taietura formata din arcele (x₀, x₁) si (x₃, x₅), care are capacitate doi.

Sinteza. Pentru fiecare arc din graful ecart se memoreaza adresa unde este localizat arcul corespondent din graful original, pentru a putea vedea la examinarea drumului daca doua arce corespondente sint identice sau au orientari opuse.

Arcul (x, y) este memorat pe pozitia k in retea: Sr[k]   y. Cele doua situatii posibile se trateaza astfel:

- daca j(x,y) < c(x,y), si y este memorat ca succesor al lui x pe pozitia j, atunci Se[j] y si P[j] k;

- daca j(x,y) > 0, si y este memorat ca succesor al lui x pe pozitia j, atunci Se[j] x si P[j] k.

Pentru a imbunatati performantele algoritmului, graful ecart se reprezinta astfel incit sa fie posibila stergerea unui arc u', care are ca si corespondent in graful original arcul u, in urmatoarele situatii:

- daca u si u' au aceeasi orientare si j(u) c(u) dupa actualizare;

- daca u si u' au orientari opuse si j(u) > 0 dupa actualizare.

Cind nu se mai poate determina un drum intre s si t in graful ecart, acesta se reconstruieste dupa regulile precizate mai sus. Algoritmul se incheie daca dupa reconstruire se obtine un graf ecart in care nu exista nici un drum de la s la t.

Pentru a obtine un graf ecart cu strictul necesar de arce, acesta nu va avea arce care intra in s si nici arce care ies din t.

4. Flux minim intr-o retea de transport

Problema. Fie G   (X, U, c) o retea de transport pentru care definim o alta lege a compatibilitatii fluxului: j(u)   c(u)

Se cere sa se determine unui flux minim compatibil cu capacitatile arcelor din retea.

Deoarece fluxul nul nu este compatibil, dar respecta legea conservarii fluxului, este nevoie ca intr-o prima faza sa se obtina un flux compatibil.

Se determina un drum m de la s la t care contine cel putin un arc u astfel incit j(u) < c(u). Pe acest drum fluxul se corecteaza astfel:

j'(u) j'(u) w,unde w   max

Aceasta procedura se repeta pina cind j(u)  c(u) pentru orice arc u I U

Identificarea unor drumuri care sa acopere in final toate arcele retelei este o procedura complexa, deoarece daca reteaua are circuite este nevoie sa se ia in considerare toate arcele aflate pe aceste circuite.

In faza a doua fluxul compatibil se micsoreaza dupa un algoritm asemanator celui care determina un flux maxim. Multimea U' a arcelor grafului ecart se defineste astfel:

a) daca (x,y) I U si j(x,y) > c(x,y), atunci (x,y) I U

b) daca (x,y) I U atunci (y,x) I U

Pe orice arc din categoria (a) fluxul ar putea scadea. Pe de alta parte, pe orice arc fluxul ar putea creste, cu conditia sa existe arce vecine pe care fluxul sa scada in compensatie.

Fie un drum de la s la t in graful ecart, (,, , ). Acest drum corespunde unui lant in reteaua curenta, pe care se poate obtine micsorarea fluxului. Pe lantul corespondent L(, , , ), care nu este neaparat un drum, se determina:

w min

Pe acest lant se micsoreaza fluxul:

j(u)

Pentru problema fluxului minim nu se cunosc algoritmi de complexitate polinomiala, aceasta fiind NP-completa.

5. Problema de transport pentru graf bipartit

min c_ij 0

a_i                   1 i m

= b_j 1 j n

x_ij 0                           1 i m, 1 j n

unde = a_i 0, b_j 0

Acestei probleme i se asociaza un graf bipartit G (S, D, U, c) unde |S|   m, |D|   n, si c este o functie cost.

Grafului bipartit i se asociaza un tabel de transport care are m linii si n coloane. Fiecare celula (i, j) contine costul c_ij si valoarea variabilei x_ij. Tabelul mai contine o coloana suplimentara in care sint inscrise valorile a_i (1   i   m), si o linie suplimentara in care sint inscrise valorile b_j (1   j   n).

Determinarea unei solutii initiale de baza. O solutie a sistemului de m+n ecuatii cu mn necunoscute este o solutie de baza daca masivele coloana ale matricei sistemului corespunzatori componentelor nenule ale solutiei sint liniar independente. Deci o solutie de baza are cel mult m+n-1 componente nenule (acesta este rangul matricei sistemului).

Metoda generala de obtinere a unei solutii initiale de baza este urmatoarea. Se fixeaza o celula (i,j) si se atribuie variabilei x_ij valoarea _ij min(a_i,b_j). Daca _ij a_i se suprima linia i din tabelul de transport si se inlocuieste b_j cu b_j a_i. Daca _ij b_j se suprima coloana j din tabelul de transport si se inlocuieste a_i cu a_i b_j. Daca _ij a_i b_j se suprima la alegere linia i sau coloana j. Daca, de exemplu, se suprima linia i, atunci b_j se inlocuieste cu 0.

Procedeul se continua pe toate tabelele reduse care se pot obtine in acest mod. Numarul variabilelor care primesc componente nenule prin aceasta metoda este cel mult m n 1.

Metode particulare de obtinere a unei solutii initiale de baza:

a) Metoda coltului de nord-vest. Se alege pentru introducerea in baza a variabilei corespunzatoare celulei situate in prima linie si prima coloana (coltul de nord-vest) a tabelelor reduse.

b) Metoda costului minim. La fiecare pas al metodei generale se selecteaza celula (i,j) corespunzatoare costului minim c_ij din tabelele reduse.

Notam cu B multimea celulelor (i,j) corespunzatoare variabilelor initializate, si cu S multimea celorlalte celule din tabelul de transport. Graful partial care contine muchiile corespunzatoare celulelor din B este un arbore.

Teorema. Pentru fiecare celula (i,j)IS exista un ciclu elementar unic format de celula (i,j) cu o parte din celulele multimii B. Acest ciclu are proprietatea urmatoare: orice doua celule consecutive se afla pe aceeasi linie sau coloana a tabelului de transport, fara ca trei celule sa se afle pe aceeasi linie sau coloana.

Demonstratie. Teorema este evidenta deoarece:

- daca se adauga o muchie intr-un arbore, se formeaza un ciclu elementar unic;

- un ciclu elementar nu trece de doua ori prin acelasi virf. n

Determinarea unei solutii optime de baza. In aceasta faza fiecare pas al algoritmului de transport efectueaza urmatoarele operatii:

a) Pentru fiecare celula (i,j)IS se determina ciclul m corespunzator. Se marcheaza celulele din ciclu alternativ cu si , incepind cu celula (i,j) care se marcheaza cu . Se determina suma algebrica a costurilor din celulele marcate, avind ca semn marcajul celulelor.

b) Se retine celula (k,l)IS pentru care suma algebrica calculata este minima. Daca suma este pozitiva sau zero, algoritmul se opreste: solutia obtinuta este optima. In caz contrar se determina valoarea w = min .

Fie (p,q) celula pentru care w x_pq.

c)         Pentru (i,j) celula din ? marcata cu se calculeaza x_ij x_ij w.

Pentru (i,j) celula din ? marcata cu se calculeaza x_ij x_ij w.

In acest moment variabila x_kl intra in baza si variabila x_pq iese din baza. Se trece la punctul a).

Daca la sfirsitul pasului b suma algebrica calculata este strict pozitiva, problema de transport are solutie optima unica.

Determinarea tuturor solutiilor optime. Se retine tabelul de transport din momentul obtinerii unei solutii optime. Daca in acest tabel suma algebrica calculata pentru celula (k,l) este 0, se poate obtine o alta solutie optima prin introducerea in baza a variabilei x_kl, variabila care iese din baza fiind determinata cu criteriul obisnuit.

Pentru determinarea tuturor solutiilor optime de baza, se cauta in tabelul retinut mai sus toate celulele (k,l)IS pentru care suma algebrica calculata este zero.

Orice solutie optima a problemei de transport este o combinatie liniara convexa a solutiilor optime de baza. Un vector x este combinatie liniara convexa a vectorilor x₁, x₂, x_k daca exista numerele reale l₁, l₂, l_k astfel incit:

0 l_i 1 pentru 1 i k si =1, x =