Maksimālā tīkla plūsma. Algoritms maksimālās plūsmas noteikšanai

Mēs atkārtojam šo darbību, līdz tiek atzīmēta kanalizācija. Ja plūsma paliek nemarķēta, tad atrastā plūsma ir maksimālā, un loku kopa, kas savieno atzīmētās virsotnes ar nemarķētām, veido minimālu griezumu.

3. Ļaujiet krājumam būt marķētam (j+, ε(t)), Tad f(j,t) aizstāt ar f(j,t)+ε(t). Ja krājums ir marķēts (j-, ε(t)), Tas f(j,t) aizstāt ar f(j,t)-ε(t). Dosimies uz augšu j. Ja j ir atzīme (i+, ε(j)), tad nomainām f(i,j) ieslēgts f(i,j)+ε(t), un ja (i-, ε(j)), f(j,i) aizstāt ar f(j,i)-ε(t). Dosimies uz augšu i. Mēs atkārtojam šo darbību, līdz sasniedzam avotu s. Plūsmas maiņa apstājas, visas atzīmes tiek izdzēstas un pārejiet uz 2. darbību

PIEMĒRS 3.14.

M 4 K

UZDEVUMS. Atrodiet lielāko plūsmu tīklā

ALGORITMS

Apzīmēsim virsotni s= x 0 . Visi pārējie ir x i.

1. posms.

1. Izvēlieties jebkuru ceļu, kura visi loki nav piesātināti.

2. Mēs palielinām plūsmas apjomu pa šo ceļu par vienu, līdz tajā nav piesātināta loka.

Mēs turpinām plūsmas palielināšanas procesu, līdz tiek uzbūvēta pilna plūsma, t.i. jebkurā ceļā būs vismaz viens piesātināts loks.

2. posms.

2. Ja х i jau ir iezīmēta virsotne, tad atzīmējam (+i) visas nemarķētās virsotnes, uz kurām iet nepiesātinātie loki no х i, un ar indeksu (–i) visas nemarķētās virsotnes, no kurām iet loki ar plūsmu, kas nav nulle. uz х i.

3. Ja šī procesa rezultātā tiek atzīmēta virsotne t, tad starp s Un t ir ceļš, kura visas virsotnes ir apzīmētas ar iepriekšējo virsotņu numuriem. Mēs palielinām plūsmu visos šī ceļa lokos par vienu if, virzoties no s Uz t loka orientācija sakrīt ar kustības virzienu un tiek samazināta par vienu, ja lokam ir pretēja orientācija. Pāriesim uz 1. darbību.

4. Kad top t nav iespējams atzīmēt, ka process ir pārtraukts, un rezultātā plūsma ir lielākā tīkla plūsma.

PIEZĪME. Jūs varat pāriet uz 2. posmu, nepabeidzot pirmo posmu (skatiet 3.16. piemēru).

PIEMĒRS 3.15.

9

RISINĀJUMS:

Konkrētajā transporta tīklā ir atrasta pilnīga plūsma. Piesātinātie loki ir izcelti

Šajā tīklā jūs varat arī atzīmēt gala virsotni, un marķējuma rezultāts būs tāds pats. Mainot plūsmu, mēs iegūstam tīklu, kurā nav iespējams atzīmēt gala virsotni, tāpēc plūsma tajā ir lielākā un vienāda ar 10.

PIEMĒRS 3.16.

8 2 1

Konkrētajā transporta tīklā tika konstatēta nepilnīga plūsma

Atzīmēsim tīklu un palielināsim plūsmu tajā pēc algoritma. Mēs saņemam

Šajā tīklā var atzīmēt arī gala virsotni, un marķējuma rezultāts būs tāds pats. Mainot plūsmu, mēs iegūstam tīklu, kurā nav iespējams atzīmēt gala virsotni, tāpēc plūsma tajā ir lielākā un vienāda ar 6.

IV sadaļa. DINAMISKĀ PROGRAMMĒŠANA.

Lai atrastu optimālus daudzpakāpju risinājumus, tiek izmantota dinamiskā programmēšana. Piemēram, iekārtu nomaiņas plānošana ilgtermiņā; nozares darbību vairāku gadu garumā. Tas izmanto optimāluma principu, saskaņā ar kuru jebkuram jaunam daļējam risinājumam jābūt optimālam attiecībā pret sasniegto stāvokli.

Labāk ir atrisināt vienu vairākas reizes vienkāršs uzdevums nekā vienreiz sarežģīti.

PROBLĒMA 1. Par izdevīgāko maršrutu starp diviem punktiem.

Jāizbūvē ceļš, kas savieno divus punktus A un B, no kuriem otrais atrodas uz ziemeļaustrumiem no pirmā. Vienkāršības labad pieņemsim, ka ceļa izkārtojums sastāv no virknes soļu, un katrā solī mēs varam virzīties vai nu uz ziemeļiem, vai uz austrumiem. Tad jebkurš ceļš ir pakāpeniska lauzta līnija, kuras segmenti ir paralēli vienai no koordinātu asīm. Katras šīs sadaļas būvniecības izmaksas ir zināmas.

PIEMĒRS 4.1. Atrodiet minimālo ceļu no A līdz B.

Pēdējais solis ir sasniegt T.V. Pirms pēdējā soļa mēs varējām atrasties punktos, no kuriem vienā solī varētu sasniegt TV. Ir divi šādi punkti (sistēma varētu būt vienā no diviem stāvokļiem). Katram no tiem ir tikai viena iespēja sasniegt t.V: vienam - virzīties uz austrumiem; otram - uz ziemeļiem. Rakstīsim izmaksas 4 un 3 katrā gadījumā.

4

Tagad optimizēsim priekšpēdējo soli. Pēc iepriekšējās darbības mēs varētu nonākt vienā no trim punktiem: C 1, C 2, C 3.

Punktam C 1 ir tikai viena vadīkla (atzīmēsim to ar bultiņu) - virzieties uz austrumiem, un izmaksas būs 2 (šajā solī) + 4 (nākamajā solī) = 6. Līdzīgi C 3. pozīcijai izmaksas būs 2+3=5. T.C 2 ir divas vadības ierīces: virzīties uz austrumiem vai ziemeļiem. Pirmajā gadījumā izmaksas būs 3+3=6, bet otrajā – 1+4=5. Tas nozīmē, ka nosacītā optimālā kontrole ir doties uz ziemeļiem. Atzīmēsim to ar bultiņu un ievadīsim atbilstošās izmaksas.

Atbilde: x 1 =1; x 3 =0; x 3 = 4; W=3,5

VISPĀRĪGS ALGORITMS

1. Aprakstiet sistēmu. Tas ir, noskaidrojiet, kādi parametri raksturo vadāmās sistēmas stāvokli pirms katra soļa. Svarīgi ir spēt pareizi un “pieticīgi” uzstādīt uzdevumu, nepārslogojot to ar liekām detaļām, maksimāli vienkāršojot vadāmās sistēmas aprakstu.

2. Sadaliet darbību soļos (posmos). Šeit jāņem vērā visi vadībai noteiktie saprātīgie ierobežojumi. Solim jābūt pietiekami mazam, lai soļa vadības optimizācijas procedūra būtu diezgan vienkārša; un solis tajā pašā laikā nedrīkst būt pārāk mazs, lai neveiktu liekus aprēķinus, kas sarežģī optimālā risinājuma atrašanas procedūru, bet neizraisa būtiskas izmaiņas optimālajā mērķa funkcija.

3. Noskaidrojiet soļu vadīklu komplektu x i katram solim un tiem noteiktos ierobežojumus.

4. Nosakiet, kādu pastiprinājumu dod kontrole x i i-solī, ja pirms tam sistēma bija stāvoklī S, t.i. pierakstiet izmaksas funkcijas:

w i =f i (S, x i)

5. Noteikt, kā mainās sistēmas stāvoklis vadības x i iedarbībā 1. solis, t.i. rakstīt stāvokļa maiņas funkcijas.

S / =φ i (S, x i)

6. Pierakstiet galveno atkārtotās dinamiskās programmēšanas vienādojumu, izsakot nosacīto optimālo pastiprinājumu caur jau zināmu funkciju

W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))

7. Ražot nosacījuma optimizācija pēdējais solis, izdarot dažādus pieņēmumus par to, kā beidzās priekšpēdējais solis, un katram no šiem pieņēmumiem atrast nosacīto (izvēlēts, pamatojoties uz nosacījumu, ka solis beidzās ar kaut ko) optimālo kontroli pēdējā solī.

W m (S) = maks (f m (S, x m))

8. Veikt nosacītu optimizāciju, sākot no priekšpēdējā soļa un beidzot ar pirmo soli (backing back).

9. Ražot beznosacījumu optimizācija kontrole, atbilstošo ieteikumu “nolasīšana” katrā solī: pirmajā solī veikt atrasto optimālo vadību un mainīt sistēmas stāvokli, otrajā solī atrast optimālo vadību atrastajam stāvoklim utt. līdz pēdējam solim.

OPTIMĀLITĀTES PRINCIPS. Neatkarīgi no sistēmas stāvokļa pirms nākamā posma, šajā solī ir jāizvēlas vadība, lai pastiprinājums šajā solī plus optimālais pastiprinājums visos turpmākajos posmos būtu maksimāls.

Dinamiskās programmēšanas princips nenozīmē, ka katrs solis tiek optimizēts atsevišķi, neatkarīgi no pārējiem. Kāda jēga izvēlēties kontroli, kuras efektivitāte ir maksimāla vienā konkrētā solī, ja šis solis mums atņems iespēju gūt labus panākumus nākamajos soļos?

Praksē ir gadījumi, kad operācija jāplāno uz nenoteiktu laiku. Šāda gadījuma modelis ir bezgalīgu soļu kontrolēts process, kurā visi soļi ir vienādi. Šeit uzvarošā funkcija un stāvokļa maiņas funkcija nav atkarīga no soļa numura.

V sadaļa. SIMULĀCIJAS MODELĒŠANA

Šī rokasgrāmata ir paredzēta studentiem, kuri apgūst diskrētās matemātikas un/vai grafu teorijas kursus.

Ar tās palīdzību jūs apgūsit tēmu "Maksimālā plūsma un minimālais griezums tīklā".

• Tieši no šīs rokasgrāmatas jūs varat aprēķināt savu ID, pat ja jūsu datorā nav MATLAB.=|Ja jums ir MATLAB, dodieties uz šo lapu: tur jums ir iespēja iejaukties aprēķina skriptā (programmā). Šeit tiek atrisināta maksimālās plūsmas problēma tīklā, samazinot to līdz lineārai programmēšanas problēmai. Ieviesīsim šādu apzīmējumu:
• n=|V| − grafa lielums (virsotņu skaits);
• m E Tieši no šīs rokasgrāmatas jūs varat aprēķināt savu ID, pat ja jūsu datorā nav MATLAB.× n| − grafa kardinalitāte (malu skaits); A− izmēra tīkla digrafa sastopamības matrica i; katrs tā elements a ik=1 ja no A- top ārā i k a ik-i loka; A=−1, ja ir
• s ieiet th virsotne
• t-i loka; Un
• =0 citos gadījumos; katrā šādas matricas kolonnā ir tieši viens, viens mīnus viens, un pārējās ir nulles;− tīkla avota virsotnes numurs; no šīs virsotnes vajadzētu parādīties tikai lokiem, un jebkurai citai virsotnei jābūt sasniedzamai no avota; − s m − tīkla izlietnes mezgla numurs; šajā virsotnē jāievada tikai loki, un no jebkuras citas virsotnes jābūt sasniedzamai aizplūšanai;
• =0 citos gadījumos; katrā šādas matricas kolonnā ir tieši viens, viens mīnus viens, un pārējās ir nulles; a − t s m ;
• m tajā vajadzētu būt tikai tiem, jo no avota vajadzētu parādīties tikai lokiem; t m -tīkla digrafa sastopamības matricas rinda s; t tajā drīkst būt tikai mīnus vieninieki, jo kanalizācijā vajadzētu iekļūt tikai lokiem;
• st − tīkla digrāfa sastopamības matrica n ar tiem, kas izmesti no tā un th līnijas; a ik e
• − kolonnas garuma vektors − tīkla digrāfa sastopamības matrica n ar tiem, kas izmesti no tā ; katrā tās elementā e k a ik būs plūsmas lielums

th loka;

c

c k

• ≥0 iestata caurlaidspēju un th loka. un = ; katrā tās elementā Tad maksimālās tīkla plūsmas problēmu var formulēt kā lineāras programmēšanas problēmu:
• Kopējā plūsma, kas iziet no avota (1), tiek maksimāli palielināta. Turklāt jebkurā starpvirsotnē ienākošā plūsma ir vienāda ar izejošo plūsmu (2), un loku jauda ir ierobežota (3).
• ja ir divi šādi komponenti, tad izmesti loki dod minimālu griezumu;
• ja parādās vairāk nekā divi savienoti komponenti, tad tīkla digrāfam ir vairāki minimāli izgriezumi (atbilstošā lineārās programmēšanas problēma ir deģenerēta).

Deģenerētas problēmas gadījumā šajā lapā tiek izveidots pirmais minimālais griezums, kas ir vistuvāk avotam.

Lai pareizi izmantotu šo lapu, jūsu pārlūkprogrammai ir jāatbalsta skripti Java skripts. Ieslēdziet tos.

Ievadiet sākotnējos datus zemāk esošajos ievades apgabalos. Pirmajā apgabalā, kas jums nepieciešams (precīzāk, jūs varat) ievadīt virsotņu koordinātas, lai uzzīmētu tīkla digrāfu. Tie ir norādīti matricas veidā Tieši no šīs rokasgrāmatas jūs varat aprēķināt savu ID, pat ja jūsu datorā nav MATLAB.×2: pirmajā kolonnā − x th koordinātas, otrajā − y-e. Skaitļus var norādīt kā veselus skaitļus, ar decimālzīmi vai eksponenciālā formā. Atdaliet ciparus ar atstarpēm. Kopējais daudzums līnijas šajā ievades apgabalā nosaka digrāfa lielumu Tieši no šīs rokasgrāmatas jūs varat aprēķināt savu ID, pat ja jūsu datorā nav MATLAB.− virsotņu skaits. Šie sākotnējie dati (virsotņu koordinātas) nav obligāti: ja tie nav norādīti, tīkla digrāfs tiks uzzīmēts kā pareizs Tieši no šīs rokasgrāmatas jūs varat aprēķināt savu ID, pat ja jūsu datorā nav MATLAB.-gon, un virsotņu skaits tiks noteikts pēc maksimālā virsotņu skaita nākamajā ievades apgabalā.

Nākamajā ievades apgabalā kreisā puse− obligāti jāaizpilda. Tas nosaka tīkla digrāfa struktūru. n Katrs digrāfa loks savieno divas virsotnes. Šo virsotņu skaitļi ir norādīti matricas veidā ×2 otrā ievades apgabala kreisajā pusē. Katrā līnijā vispirms tiek norādīta loka 1. virsotne (aste, avots), un pēc tam caur atstarpi tiek norādīta loka otrā virsotne (smaile, notece).Šajās kolonnās vajadzētu būt Tieši no šīs rokasgrāmatas jūs varat aprēķināt savu ID, pat ja jūsu datorā nav MATLAB. naturālie skaitļi n no 1 līdz

Kopējais skaitļu skaits katrā no šīm kolonnām nosaka digrāfa jaudu − loku skaits. , Aprēķināt Dots virzīts grafiks G= kurā katra loka virziens vÎV V nozīmē plūsmas virzienu (piemēram, automašīnu plūsma), katra loka jauda ir vienāda ar t Un s d(v). t Daudzās virsotnēs s ir izceltas divas virsotnes t. Virsotne s .

ir plūsmas avots, - notecēt. Ir nepieciešams noteikt maksimālo plūsmu, ko var izlaist no virsotnes V Apzīmēsim ar x(v)

plūsmas apjoms, kas pārvietojas pa loku (6. 1)

v . Ir skaidrs, ka 0 £ x(v) £ d(v) , vÎV .

Katrā virsotnē)iÎE\(t,s)

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

Virsotnei t

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

virsotnei s

(x(v)| iО V + (i)) -(x(v)¦ i О V - (i))= Q.(6.4)

Lielums J ir plūsmas lielums, kas atstāj virsotni t un ieiet augšpusē s.

Nepieciešams noteikt

Q ® maks(6.5)

saskaņā ar ierobežojumiem (6.1.-6.4.).

Daudzumi Q, x(v) , vÎV, atbilst ierobežojumiem (6.1-6.4), mēs izsauksim plūsmu tīklā, un, ja tie maksimāli palielina vērtību J, tad maksimālā plūsma. Ir viegli redzēt, ka vērtības Q=0, x(v)=0, vÎV, ir plūsma tīklā.

Problēma (6.1-6.5) ir lineāras programmēšanas uzdevums, un to var atrisināt, izmantojot vienkāršās metodes algoritmus.

Sadalīsim virsotņu kopu E divās nesavienotās daļās E1 un E2 tā, ka tÎE1, sÎE2. Pēc griezuma V(E1,E2), atdalot t Un s mēs izsauksim komplektu V(E1,E2)ÌV tāds, ka katram lokam v О V(E1,E2) vai h1(v)ОE1 Un h2(v)ОE2, vai h1(v)ОE2 Un h2(v)ОE1.

Sadalīsim komplektu V(E1,E2) divās daļās V(E1,E2,+),V(E1,E2,-)šādi:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1 Un h2(v)ОE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1 Un h1(v)ОE2)

Mēs sauksim griezuma caurlaidspēju

Q(E1,E2) = (x(v)| vÎV(E1,E2,+))-(x(v)| vÎV(E1,E2,-))

Tālāk teiktais ir patiess

1. teorēma. (Par maksimālo plūsmu un minimālo griezumu).

Jebkurā tīklā maksimālā plūsma no avota ir a uz krājumiem s vienāds ar minimālo caurlaidspēju Q(E1,E2) starp visiem griezumiem V(E1,E2), atdalot virsotnes t Un s.

Ņemiet vērā, ka maksimālajā plūsmā

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

Ļaujiet Q, x(v), vÎV, - kāda tīkla plūsma, secība

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

ir ķēde, kas savieno virsotnes t Un s. Nosakīsim šajā ķēdē kustības virzienu no virsotnes t Uz s. Arc v(j) no šīs ķēdes sauc par taisnu līniju, ja tās virziens sakrīt ar kustības virzienu no t Uz s, un otrādi citādi. Mēs šo ķēdi sauksim par ceļu palielinot plūsmu, ja taisniem lokiem Apzīmēsim arķēdes x(v)< d(v) un atpakaļgaitā x(v) > 0. Caur šo ķēdi var izvadīt papildu plūsmu q no t Uz s izmērs q = min(q1,q2), Kur q1 = min (d(v) -x(v)), minimums tiek pārņemts visos ķēdes taisnajos lokos, q1=min (x(v)), minimums tiek pārņemts visos ķēdes apgrieztajos lokos.

2. teorēma.

Plūsma Q, x(v) , vÎV, ir maksimālais tad un tikai tad, ja nav iespējas palielināt plūsmu.

Piedāvātais algoritms maksimālās plūsmas problēmas risināšanai tīklā ir balstīts uz veidu, kā palielināt plūsmu no t. Virsotne s, kas savukārt balstās uz virsotņu etiķešu kārtošanas procesu. Teiksim tā

virsotne i atzīmēts ar atzīmi q(i)>0, un ir zināms arī taisnā loka loks v(i), caur kuru šī plūsma nāca, vai ir atzīmēta ar , ja kāda lieluma papildu plūsma q(i)>0, un ir zināms arī apgrieztais loks v(i), caur kuru šī plūsma ienāca;

virsotne i tiek apskatīta, ja ir atzīmētas visas tai blakus esošās virsotnes.

Ja ir atzīmēta virsotne s, tad ir atrasts ceļš, kas palielina plūsmu par lielumu q, kas tiek nodots pa šo ceļu. Lai aprakstītu algoritmu, mums ir nepieciešams arī masīvs SPW, kas satur atzīmēto virsotņu numurus tādā secībā, kādā tās tika atzīmētas. C1- numurs masīvā SPW skatītā virsotne, C2- pēdējās atzīmētās virsotnes numurs šajā masīvā.

Šī algoritma ideja ir atrast ceļus no gala līdz galam ar pozitīvām plūsmām no avota līdz izlietnei.

Apsveriet malu (i, j) ar (sākotnējo) ietilpību. Algoritma izpildes laikā plūsmas, kas iet caur doto malu, tiek “atņemtas” daļas no šīs kapacitātes, kā rezultātā katrai malai būs atlikušā jauda. Rakstīt — atlikušais joslas platums. Tīkls, kurā visām malām ir atlikušā jauda, ​​tiks saukts par atlikušo.

Patvaļīgam mezglam j, kas saņem plūsmu no mezgla i, mēs definējam etiķeti, kur ir plūsmas vērtība, kas plūst no mezgla j uz mezglu i. Lai atrastu maksimālo plūsmu, mēs veicam šādas darbības.

Visām malām mēs iestatām atlikušo jaudu, kas vienāda ar sākotnējo jaudu, t.i. pielīdzināsim =. Piešķirsim un atzīmēsim mezglu 1 ar etiķeti. Mēs pieņemam, ka i = 1.

Mezglu j kopa, uz kuru var doties no mezgla I pa malu ar pozitīvu atlikušo jaudu >0 visiem j. Ja mēs veicam 3. posmu, pretējā gadījumā mēs ejam uz 4.

In mēs atrodam mezglu k tādu, ka. Novietosim un atzīmēsim mezglu k ar etiķeti. Ja k=n, tiek atrasts ceļš no gala līdz galam, un mēs pārejam uz 5. posmu, pretējā gadījumā iestatām i=k un atgriežamies 2. posmā.

Atcelšana. Ja i=1, ceļš no gala līdz galam nav iespējams, un pārejiet uz 6. Ja mēs atrodam apzīmēto mezglu r tieši pirms mezgla i un noņemam to no mezglu kopas, kas atrodas blakus mezglam r. Mēs iestatām i=r un atgriežamies 2. posmā.

Atlikušā tīkla definīcija. Apzīmēsim ar mezglu kopu, caur kuru iet p_th atrastais ceļš no avota mezgla (mezgls 1) uz izlietnes mezglu (mezgls n) Tad maksimālā plūsma, kas iet pa šo ceļu

Malu atlikušā jauda, ​​kas veido ceļu no gala līdz galam, samazinās par noteiktu daudzumu plūsmas virzienā un palielinās par tādu pašu daudzumu pretējā virzienā.

Tas. malai (i, j), kas iekļauta maršrutā no gala līdz galam, mainās pašreizējās atlikušās jaudas:

1) ja plūsma iet no mezgla i uz j,

2) ja plūsma iet no mezgla j uz i.

a) ja atrasti m ceļi no gala līdz galam, maksimālā plūsma tiek izteikta ar

b) Ņemot vērā malas sākotnējās un galīgās ietilpības vērtības (i, j), mēs varam aprēķināt optimālo plūsmu caur šo malu šādi. Liekam. Ja >0, plūsma, kas iet caur malu (i, j), ir vienāda. Ja >0, tad plūsma ir vienāda. (gadījums, kad gan >0, gan >0 nav iespējams).

Piemērs 1. Atrodiet maksimālo plūsmu tīklā Fig. 1

Iterācija 1. =

3) k=3, kopš. Mēs piešķiram un atzīmējam mezglu 3 ar etiķeti. i=3 un atgriezties pie 2)

5) k=5 un. Mēs atzīmējam mezglu 5 ar etiķeti. Mēs iegūstam cauri ceļu.

6) mēs nosakām ceļu no gala līdz galam ar etiķetēm, sākot no 5. mezgla un beidzot ar mezglu 1: . Un. Mēs aprēķinām atlikušās jaudas ceļā:

2. atkārtojums.

1) un atzīmējiet 1. mezglu ar etiķeti. i=1

2") (tātad mezgls 5 nav iekļauts

3") k=4 un atzīmējiet 4. mezglu ar etiķeti. i=4 un atgriezties pie 2)

2""") (tā kā 1. un 3. mezgli ir atzīmēti, tie nav iekļauti)

3""") k=5 un. Mēs atzīmējam mezglu 5 ar etiķeti. Tiek iegūts ceļš no gala līdz galam. Pārejiet uz 5)

3. atkārtojums.

1) un atzīmējiet 1. mezglu ar etiķeti. i=1

3) k=2, un atzīmējiet 2. mezglu ar etiķeti. i=2 un atgriezties pie 2)

3") k=3 un. Atzīmējiet 3. mezglu ar etiķeti. i=3 un atgriezieties pie 2)

2") (kopš) pārejiet uz 4)

4) Node 3 etiķete parāda iepriekšējā mezgla numuru. Šajā iterācijā 3. mezgls turpmāk netiek ņemts vērā; un atgriezties pie 2)

2""") (tā kā 3. mezgls ir noņemts no iespējamā ceļa līdz galam)

3""") un. Mēs atzīmējam mezglu 5 ar etiķeti. Tiek iegūts ceļš no gala līdz galam. Pārejiet uz 5)

5) i. Mēs aprēķinām atlikušās jaudas ceļā:

4. iterācija. Šajā iterācijā ceļš ar

5. iterācija. Šajā iterācijā ceļš ar

6. iterācija: nav iespējami jauni ceļi no gala līdz galam, jo ​​visām malām, kas nāk no 1. mezgla, atlikušā jauda ir nulle. Pārejiet uz 6), lai noteiktu risinājumu

6) maksimālais plūsmas apjoms tīklā ir vienāds ar vienībām.

Plūsmas vērtības gar dažādām malām tiek aprēķinātas, no sākotnējām jaudas vērtībām atņemot jaunākās atlikušās jaudas vērtības.

Aprēķinu rezultāti: tabula. 1

Maksimālās plūsmas noteikšanas algoritma grafiska secīga izpilde (1. piemērs)

e) f) Nav caurejošu ceļu

Rīsi.

Sākotnējie dati par transporta sistēmu, piemēram, rūpnīcā, parādīti attēlā. 2, var norādīt arī tabulā (2. tabula).

2. tabula. Sākotnējie dati maksimālās plūsmas problēmai

Acīmredzot transporta sistēmas maksimālā ietilpība nepārsniedz 6, jo no sākuma punkta 0 var nosūtīt ne vairāk kā 6 kravas vienības, proti, 2 vienības uz punktu 1, 3 vienības uz punktu 2 un 1 vienība uz punktu 3 Tālāk ir jānodrošina, lai visas 6 kravas vienības, kas iziet no punkta 0, sasniedz galapunktu 4. Acīmredzot 2 kravas vienības, kas ieradās 1. punktā, var tieši nosūtīt uz 4. punktu. Krava, kas ieradās 2. punktā, tiks nosūtīta. ir jāsadala: 2 vienības nekavējoties tiek nosūtītas uz 4. punktu, bet 1 vienība - uz starppunktu 3 (sakarā ar ierobežoto ietilpību posmā starp 2. un 4. punktu). Uz punktu 3 tika nogādātas sekojošas kravas: 1 vienība no punkta 0 un 1 vienība no 3. Nosūtām tās uz punktu 4. Tātad attiecīgā transporta sistēmas maksimālā caurlaidspēja ir 6 kravas vienības. Šajā gadījumā netiek izmantotas iekšējās sekcijas (atzari) starp 1. un 2. punktu, kā arī starp 1. un 3. punktu Atzars starp 1. un 4. punktu nav pilnībā noslogots - kopā ar to tiek nosūtītas 2 kravas vienības caurlaidspēja 3 vienības. Risinājumu var attēlot tabulas veidā (3. tabula)

3. tabula. Maksimālās plūsmas problēmas risināšana

Lineārās programmēšanas problēma plūsmas maksimizēšanai. Formulēsim maksimālās plūsmas problēmu lineārās programmēšanas izteiksmē. Pieņemsim, ka X KM ir transportēšanas apjoms no punkta K uz punktu M. Saskaņā ar att. 2 K = 0,1,2,3, M = 1,2,3,4, un transportēšana iespējama tikai līdz punktam ar lielāku skaitli. Tas nozīmē, ka pavisam ir 9 mainīgie X KM, proti, X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Lineārās programmēšanas problēma ir vērsta uz maksimālu plūsmai ir šāda forma:

X 01 + X 02 + X 03 = F (0)

X 01 + X 12 + X 13 + X 14 = 0 (1)

X 02 - X 12 + X 23 + X 24 = 0 (2)

X 03 - X 13 - X 23 + X 34 = 0 (3)

X 14 - X 24 - X 34 = - F (4)

X km? 0, K, M = 0, 1, 2, 3, 4

Šeit F ir mērķa funkcija, nosacījums (0) apraksta preču ienākšanu transporta sistēmā. Nosacījumi (1) - (3) nosaka bilances attiecības sistēmas mezgliem 1-3. Citiem vārdiem sakot, katram iekšējam mezglam ienākošā preču plūsma ir vienāda ar izejošo plūsmu, preces neuzkrājas sistēmas iekšienē un tajā “nedzimst”. Nosacījums (4) ir nosacījums slodžu “izejai” no sistēmas. Kopā ar nosacījumu (0) tas veido bilances attiecības visai sistēmai (“ievade” ir vienāda ar “izeju”). Sekojošās deviņas nevienlīdzības nosaka atsevišķu transporta sistēmas “nozaru” kapacitātes ierobežojumus. Tad tiek norādīts satiksmes apjomu un mērķa funkcijas nenegatīvums. Ir skaidrs, ka pēdējā nevienlīdzība izriet no mērķa funkcijas formas (attiecības (0) vai (4)) un satiksmes apjomu nenegatīvuma. Tomēr pēdējā nevienlīdzība nes dažus vispārīga informācija- caur sistēmu var izlaist vai nu pozitīvu kravas apjomu, vai nulle (piemēram, ja sistēmā notiek kustība pa apli), bet ne negatīvu (nav ekonomiska jēga, bet formāla matemātiskais modelis"nezina" par to).

Plūsmu summa cauri lokiem, kas krīt Apzīmēsim ar, ir vienāds ar plūsmu summu cauri krītošajiem lokiem w; šo summu sauc par plūsmas vērtību. Mūs galvenokārt interesēs plūsmas, kurām ir vislielākā iespējamā vērtība – tā sauktās maksimālās plūsmas. IN vispārējs gadījums tīklam var būt vairākas dažādas maksimālās plūsmas, taču to vērtībām jābūt vienādām. (4)

Maksimālo plūsmu izpēte caur tīklu N = (V,D,a) ir cieši saistīta ar griezuma jēdzienu, t.i. tāda digrāfa D loku kopa A, kurai ir tāda īpašība kā jebkurai vienkāršai ķēdei Apzīmēsim ar. Virsotne iet cauri lokam, kas pieder pie A. Griezuma kapacitāte ir tai piederošo loku kapacitātes summa. Izcirtņus, kuriem ir vismazākā iespējamā caurlaidspēja, sauc par minimālajiem griezumiem.

Nevienas plūsmas lielums nepārsniedz neviena griezuma caurlaides jaudu, un tāpēc jebkuras maksimālās plūsmas lielums nepārsniedz jebkura minimālā griezuma caurlaidspēju. Tomēr uzreiz nav skaidrs, ka abi pēdējie cipari vienmēr vienādi viens ar otru; Šo rezultātu 1955. gadā ieguva amerikāņu matemātiķi Fords un Fulkersons un sauca par maksimālās plūsmas un minimālās griezuma teorēmu.

Teorēma (par maksimālo plūsmu un minimālo griezumu). Jebkurā tīklā jebkuras maksimālās plūsmas lielums ir vienāds ar jebkura minimālā griezuma jaudu.

Maksimālās plūsmas un minimālā griezuma teorēma ļauj pārbaudīt, vai dotā plūsma ir maksimālā vai nē, bet tikai diezgan vienkāršiem tīkliem. Protams, praksē nākas saskarties ar lieliem un sarežģītiem tīkliem, un kopumā ar vienkāršu atlasi ir grūti atrast maksimālo plūsmu. Aprakstīsim vienu algoritmu maksimālās plūsmas atrašanai jebkurā tīklā ar veselu skaitļu caurlaidspēju.

1. darbība. Vispirms atlasīsim plūsmu, kuras vērtība nav nulle (ja tāda pastāv). Piemēram, ja N ir tīkls, kas parādīts attēlā. 29.3, tad plūsma, kas parādīta attēlā. 29.4. Ir vērts atzīmēt, ka jo lielāku sākotnējās plūsmas vērtību esam izvēlējušies, jo vieglāk būs turpmākās darbības.

2. darbība. Pamatojoties uz N, mēs veidojam jaunu tīklu N', mainot plūsmas virzienu uz pretējo. Precīzāk, jebkurš loks a, kuram (a) = 0, paliek N' ar sākotnējo jaudu, un jebkurš loks a, kuram , tiek aizstāts ar loku a ar kapacitāti un pretēju loku ar kapacitāti (a). Mūsu piemērā tīkls N ir parādīts attēlā. 29.5. Virsotne Apzīmēsim ar vairs nav avots, bet gan izlietne.

3. darbība. Ja tīklā N’ mēs varam atrast plūsmu, kas nav nulle no Apzīmēsim ar c, tad to var pievienot sākotnējai plūsmai un iegūt jaunu plūsmu ar lielāku vērtību N. Tagad varat atkārtot 2. darbību, veidojot tīklu, izmantojot jauno pavedienu N’, nevis N’. Atkārtojot šo procedūru, mēs galu galā nonāksim pie tīkla N', kurā nav plūsmas, kas atšķiras no nulles; tad atbilstošā plūsma būs maksimālā plūsma. Piemēram, attēlā. 29.5 ir plūsma, kas atšķiras no nulles, kurā plūsmas caur lokiem ( v,u), (u,z), (z,x), (x,y) Un ( y,) ir vienādi ar vienu, un plūsmas caur atlikušajiem lokiem ir vienādas ar nulli. Pievienojot šo plūsmu plūsmai attēlā. 29.4, mēs iegūstam plūsmu, kas parādīta attēlā. 29,6; atkārtojot 2. darbību, ir viegli parādīt, ka tā ir maksimālā plūsma.

Izmantotā literatūra:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Asanovs M.O., Baranskis V.A., Rasins V.V. Diskrētā matemātika: matroīdu grafiki, algoritmi

(3) Basaker R., Saati T. Galīgie grafiki un tīkli.

(4) Vilsons R. Ievads grafu teorijā