Este considerată o rețea cu un nod de intrare (sursă) și un nod de ieșire (chiuveta). Care este valoarea maximă a fluxului (numărul de mașini, mesaje, lichide etc.) care pot intra în sistemul de rețea și îl pot ieși dintr-o anumită perioadă de timp? În acest caz, presupunem că fluxul care curge din nod este egal cu fluxul care curge în nod.
Sub capacitatea (puterea) arcului, înțelegem limita superioară a curgerii în acest arc. Puterea fluxului poate depinde de direcția sa. Condiționată imagine de rețea
Aceasta înseamnă că puterea debitului de la nodul 1 la nodul 2 este 6, iar puterea de la 2 la 1 este egală cu 0.
Algoritmul pentru determinarea debitului maxim:
- Găsiți orice cale de la sursă la scurgere, care este formată din arce, fiecare având o putere diferită de zero în direcția fluxului. Dacă nu există un astfel de mod, atunci se găsește o soluție optimă.
- Găsiți cea mai mică valoare a puterii arcului P în calea selectată din pasul 1. Creșteți fluxul prin rețea cu suma P
- Pe drumul de la pasul 1, reduceți puterea fluxurilor pe toate arcele în direcția fluxului cu P și măriți puterea fluxurilor pe toate arcele în P în direcția opusă. Mergeți la pasul 1.
Un exemplu. Sistemul de autostrăzi Nord-Sud, care trece prin regiunea Pskov, poate oferi capacitatea prezentată în diagrama de mai jos (mii de mașini pe oră).
Care este debitul maxim prin acest sistem (mii de mașini pe oră)? Câte mașini ar trebui să conducă de-a lungul rutei 5-6 pentru a asigura fluxul maxim?
Valoarea dorită a debitului maxim este setată la zero.
Alegeți calea 1-3-6. P = min (6.2) = 2. Prin urmare, fluxurile de putere pe calea 1-3-6 în direcția fluxului sunt reduse cu o sumă P = 2, iar puterea curge în direcția opusă pe traseul 1-3-6 crescând cu P = 2. Fluxul total va fi 0 + 2 = 2. Avem:
Alegeți calea 1-4-6. P = min (3,3) = 3. Toate fluxurile pe drumul 1-4-6 în direcția fluxului total sunt reduse cu 3, iar în direcția opusă se mărește cu 3. Debitul total este mărit cu 3. Total, 2 + 3 = 5. Avem:
Alege calea 1-2-5-6. P = min (2,4,6) = 2. Toate firele pe drumul 1-2-5-6 în direcția fluxului general se reduc cu 2, în contrast crescând cu 2. Debitul total este de asemenea mărit cu 2. Total 5 + 2 = 7. Avem:
Alegeți calea 1-3-4-5-6. P = min (4,3,1,4) = 1. Toate fluxurile pe drum 1-3-4-5-6 în direcția debitului total (4,3,1,4) sunt reduse cu suma P = 1, iar toate fluxurile în acest sens în direcția opusă sunt mărite cu P = 1. Total, debitul total 7 + 1 = 8. Avem:
Alegeți calea 1-3-4-2-5-6. P = min (3,2,1,2,3) = 1. În direcția înainte, scade cu 1, în direcția opusă creștem cu 1. Debitul total este egal cu 8 + 1 = 9. Avem:
Nu mai există căi de la nodul 1 la nodul 6 cu o putere mai mare de 0 pe întreaga cale (P = 0). Prin urmare, 9 mii este debitul maxim prin rețea.
Să determinăm acum amploarea și direcția fluxului pe fiecare arc pentru a obține debitul maxim de 9 mii de mașini. Debitul trece de-a lungul unui arc cu o valoare egală cu diferența dintre puterile inițiale și cele finale ale curgerii. Astfel, puterea inițială a arcului 1-2 este 2, iar puterea finală este 0. Apoi, în direcția de la nodul 1 la nodul 2, fluxul are o putere de 2-0 = 2. Comparând puterea finală și cea inițială a fluxului pentru toate arcele rețelei, obținem un model finit de fluxuri.
Care este fluxul maxim de vehicule pentru sistemul rutier? Se ia în considerare posibilitatea introducerii secțiunii 3-4 cu o capacitate de 3 mii de vehicule pe oră. Cât va crește fluxul maxim de vehicule?
Tabelul R.R. Set. Logic. Teoriile axiomatice. - M. Enlightenment, 1968.
Articole similare
Trimiteți-le prietenilor: