Drum de valoare minimă într-un graf, folosind algoritmul FORD. Modelul matematic general al

problemelor de tip transport

Student: Maura TrocanProfesor Coordonator: Dan Deac

Facultatea de Ştiinţe EconomiceUniversitatea de Vest “Vasile Goldiş” din Arad

 Drum de valoare minimă într-un graf, folosind

algoritmul FORD. Algoritmul Ford-Fulkerson este unul din algoritmii cei mai simpli care rezolvă problema

„Debitului maxim”. Constă în identificarea succesivă a unor drumuri de creștere până în momentul în care nu mai există nici un astfel de drum. După identificarea unui drum de creștere se determină valoarea acestuia, iar aceasta se scade din costurile fiecărui arc (i, j) de pe drumul respectiv și se adună la costurile arcelor corespunzătoare de forma (j,i). De asemenea, valoarea respectivă se adună la fluxul maxim determinat până în momentul respectiv. Datorită faptului că un drum de creștere conține arce care au costuri pozitive, valoarea sa va fi întotdeauna un număr pozitiv. Ca urmare, pentru fiecare drum de creștere determinat, valoarea fluxului va crește cu cel puțin o unitate. Datorită faptului că avem capacități finite, fluxul maxim este un număr finit. Din aceste motive suntem siguri că, mai devreme sau mai târziu, algoritmul se va încheia. Determinarea unui drum de creștere se poate realiza prin orice metodă dar, din motive de eficiență, trebuie utilizată una al cărei ordin de complexitate este Θ(M + N). Din nefericire, algoritmul ne asigură doar faptul că la fiecare pas valoarea fluxului va crește cu cel puțin o unitate. Așadar, dacă fluxul maxim este F, există posibilitatea de a efectua F pași.

Ca urmare, ordinul de complexitate al algoritmului Ford-Falkerson este Θ(F • (M + N)). Se observă că, în cazul în care valoarea fluxului este foarte mare, acest ordin de complexitate este inacceptabil.

Algoritmul Ford (Fulkerson): - caută drumurile de cost minim- - nodul rădăcină ( fie A) este considerat ca destinație - rularea algoritmului este gata după etichetarea tuturor nodurilor

cu dist. față de A și cu eticheta nodului următor pe drumul minim către A

 - construcția tab. rutare = repetarea alg. pentru fiecare nod destinație.

Eticheta are aceeași formă ca la algritmulo Dijkstra. Ex B(5, D) este eticheta nodului B care arată că distanță până la A este 5, via nodul vecin D

Inițializare

Fie nodul A = destinație, D(A) = 0. Se etichetează toate celelalte noduri cu (-,∞).

Etichetarea tuturor nodurilor cu distantele minime până la A. Pentru ∀ nod v≠ A execută: actualizează distanțele D(v) până la destinația A, pentru fiecare

nod, prin utilizarea valorilor curente D(w) ale tuturor vecinilor w ai lui v, adică pentru toti w∈V(v). Se face atribuirea:

D(v) = min{D(w) + l(w,v)} w∈ V(v) - se actualizează eticheta de nod cu nr. nodului vecin care

minimizează expresia de mai sus și cu noua distanță D(v).3. Repetă etapa 2 până când nu mai apar modificări.

Fig. 1- Actualizarea distanțelor lui v față de A

Exemplu: 1. Să se determine arborele drumurilor minime în raport cu nodul A pentru rețeaua din fig.1.1. Să se scrie tab de rutare din nodul A pentru host-urileHi, I < > 1 2. Folosind drumurile de lungime minimă să se aloce numere de circuite virtuale pentru conexiunile (solicitate temporal în ordinea dată) H1 - H7, H3 - H7, H2 - H6, H1 – H6, H1 – H5

Fig. 2 – Configurația rețelei. Nodul A este destinația

Repetând pasul 2 se constată că nu mai apar modificări

Fig. 3 – Arborele drumurilor minime până la nodul A

Tabelul de rutare pentru nodul A este:

Algoritmul se construiește pentru fiecare nod pentru care se construiește tabelul de rutare.

Modelul matematic general al problemelor de tip transport

În forma sa generală, modelul problemei transporturilor se referă la o problemă echilibrată în care totalul necesarului la cei n consumatori este egal cu totalul disponibilului la cei m furnizori, adică: ∑a i =∑bj .Impunând condiția de a satisface integral necesarul bj al fiecăruia dintre cei j consumatori, se pot formula o serie de restricții de formă: ∑xij = bj (j = 1 ,2 . .. , n). Similar, impunând condiția epuizării disponibilului existent la fiecare furnizor se ajunge la m restricții de forma : ∑xij =ai (i = 1,2 . . , m) . Modelul mai trebuie completat cu condițiile de nenegativitate: xij ≥ 0 ( i = 1,2,…,m) și (j =1,2,…,n) și cu funcția obiectiv: f(x) = ∑ ∑ cijxij (min) sau (max). Problema clasică de transport este de minimizare. În raport cu semnificația valorilor c ij, funcția obiectiv poate fi însă și de minimizare.

Sistemul de ecuații liniare conține m x n necunoscute și m + n - 4 ecuații liniar independente deoarece se respectă și condiția ∑ai =∑bj. Se ajunge astfel la un sistem compatibil nedeterminat care admite în principiu un număr foarte mare de soluții posibile obținute prin rezolvarea sistemelor determinate identificate prin atribuirea de valori arbitrare unui număr de (m-1) (n-1) necumoscute. Se poate dovedi că cel puțin o soluție care minimizează valoarea funcției obiectiv se găsește prin rezolvarea unuia din sistemele determinate ce se obțin din sistemul nedeterminat prin anularea a m x n -(m + n -1) necunoscute. O soluție de bază nedegenerată are un nr m + n - 1 componente strict pozitive și (m-1 )(n-1) componente nule. Dacă numărul componentelor strict pozitive e < de m + n - 1 spunem că soluția este degenerată.

Metode de determinare a unei soluții de bază

O soluție de bază se poate obține prin utilizarea unui algoritm ce constă în alegera întâmplătoare la fiecare pas a unei variabile strict pozitive xij, căreia i se atribuie valoarea maximă definită de relațiile: ∑xij = bj (j= 1 ,2 . . , n) . ∑xij =ai (i = 1,2 . . , m), adică xij =min. Toate celelalte variabile de pe linia i sau coloana j vor lua valoarea xij = 0 după cum ai≤bj sau bj≤ai. Valorile ai sau bj se recalculează și devin: a'i=ai - bj, dacă bj<ai; b'j=bj - ai, dacă ai<bj. Această metodă poate fi particularizată prin alegerea anumitor criterii de introducerea în soluția de bază a valorilor xij strict pozitive.

Procedeul coltului de nord vest

Criteriul de alegere la fiecare pas a variabilelor strict pozitive care să participe în soluția de bază este poziționarea lor în celula din colțul de nord vest fie în tabelul inițial fie în tabelele reduse ce rezultă prin eliminarea unei linii sau a unei coloane, cu m ai<bj

sau bj < ai. .Totuși procedeul colțului de NV prezintă avantajul că aplicarea lui are un caracter mecanic ceea ce permite realizarea unui program de calcul simplu în ipoteza prelucrării electronice a datelor.

Procedeul elementului minim pe linie

Pentru introducerea variabilelor strict pozitive în soluția de bază se alege la fiecare pas al prelucrării algoritmului poziția corespunzătoare elementului minim din fiecare linie. Dacă ai>bj se trece la poziția corespunzătoare elementului imediat următor ca valoare de pe aceeași linie; astfel se trece la o altă linie până la atribuirea de valori tuturor celor m x n variabile. Dacă apar două sau mai multe valori minime egale se preferă mai întâi poziția ce permite realizarea pe ruta respectivă a unui volum mai mare de transport. Având la bază un criteriu economic soluția inițială obținută e de obicei mai apropiată de cea optimă comparativ cu celelalte două procedee menționate.

Procedeul elementului minim pe coloană

Se aplică în mod similar cu observația că analiza se realizează de data aceasta pe coloane.

Procedeul elementului minim din tabel

Are drept criteriu de introducere al variabilelor strict pozitive în soluția de bază elementul minim din tabelul inițial sau din tabelele reduse obținute prin eliminarea la fiecare pas a unei linii (daca ai<bj) sau a unei coloane (daca bj<aj). Analiza făcându-se pe ansamblu, soluția astfel obtțnută este de obicei mai avantajoasă decât cele furnizate prin procedeele prezentate anterior. Variabilele strict pozitive s-au introdus în ordinea x22,x14,x21. Se constată că în această aplicație soluția obtinută coincide cu cea furnizată prin procedeul elementului minim pe linie.

Procedeul diferențelor maxime

Pentru fiecare linie și coloană se face diferența dintre elementul imediat următor ca valoare elementului minim și elementul minim. La fiecare pas se identifică diferența maximă repartizându-se în soluția de bază variabilă corespunzătoare elementului minim care a generat diferența maximă. Dacă două sau mai multe diferențe maxime sunt egale se ia în considerare mai întâi diferența care provine din numere mai mici; dacă și acestea sunt egale, se preferă poziția care permite realizarea unui volum mai mare de transport. Diferențele se recalculează la fiecare pas, fie pe linie, fie pe coloană. Deși ceva mai laborios, procedeul duce la soluții inițiale mai apropiate de cea optimă. Datorită caracterului obligat al repartizării la ultimul pas se poate întâmpla ca uneori soluția astfel obținută să fie mai dezavantajoasă decât cea obținută printr-un alt procedeu. Observația este valabilă și pentru celelalte procedee prezentate, ierarhia lor apreciată pe baza valorii funcției obiectiv, schimbându-se de la o aplicație la alta.

Algoritmi de optimizare

Reprezintă numai soluții inițiale, pornind de la care, prin algoritmul de optimizare ales (metoda distributivă sau metoda distributivă modificată) se obține în mod iterativ, prin îmbunătățiri succesive, soluția optimă.

Bibliografie

Deac D. - Teoria Grafurilor cu Aplicaţii în Economie – Suport Curs

Bellman, Richard (1958) - "On a routing problem". Quarterly of Applied Mathematics 16: 87–90. MR 0102435.

Ford Jr., Lester R. (August 14, 1956) - Network Flow Theory. Paper

Opriş D. Silberberg Gh.- Optimizări liniare,discrete convexe. Aplicaţii, Ed. Mirton Timişoara 1999

Owen G. – Teoria jocurilor, Ed. Tehnică Bucureşti 1974 Yidăroiu C. – Programarea liniară , Ed. tehnică Bucureşti

1983

Vă mulţumesc!