Aprēķinu algoritms maksimālā plūsma tīklos
1. SOLIS. Sākotnējie uzdevumi. Pašreizējā vērtība A t Maksimālajai plūsmai tīklā tiek piešķirta vērtība 0. 2. SOLIS. Neatkarīgu maršrutu atlase tīklā un plūsmu noteikšana tajos. No visa iespējamo maršrutu kopuma tīklā no avota līdz izlietnei mēs izvēlamies neatkarīgus maršrutus M 1 , … , M k, kam nav kopējās virsotnes, izņemot sākotnējo (avots v un) un galīgais (iztukšošana v ar). Katram izvēlētajam maršrutam M i(1 £ i£ k) nosaka maksimālo plūsmu A(M i).SOLIS 3. Tīkla maksimālās plūsmas pašreizējās vērtības korekcija. Mēs pievienojam atrastos 2. SOLIS maksimālo plūsmu vērtības neatkarīgos maršrutos M 1 , … , M k uz pašreizējo kopējo maksimālo tīkla plūsmu: A t:= A t + A(M 1)+ A(M 2)+…+ A(M k)4. SOLIS. Tīkla korekcija. Atrasts uz 2. SOLIS maksimālās plūsmas A(M 1), … , A(M k)atņemts no atbilstošo tīkla loku kapacitātes. Tiek noņemti loki ar nulles atlikušo jaudu. 5. SOLIS. Algoritma pabeigšanas pārbaude. Ja pēc labošanas tīklā nav palicis neviens maršruts no avota v un uz krājumiem v ar, tad nepieciešamā maksimālā plūsma tīklā ir vienāda ar atrasto strāvu A:= A t, algoritms tiek pārtraukts, jo visa tīkla jauda ir izsmelta. Ja pielāgotajā tīklā ir maršruti no avota v un uz krājumiem v ar, pēc tam dodieties uz 2. SOLIS un algoritma izpildes turpināšana . 2. piemērs. Izmantojot šo algoritmu, atrodiet maksimālo plūsmu tīklā 1.15. attēlā. Risinājums.SOLIS 1. Sākotnējie uzdevumi. A t: = 0.I iterācija. 2. SOLIS. Neatkarīgu maršrutu atlase tīklā un plūsmu noteikšana tajos. Kā M 1 izvēlēties maršrutu ( v un =V 1 , V 2 , V 5 , v s = V 7), aplūkots 1. piemērā. Viņam A(M 1) = 10.
Ir arī viegli izolēt neatkarīgu M 1 maršruts M 2 = (v un =V 1 , V 3 , V 6 , v s = V 7). Aprēķināsim tam maksimālo caurlaidspēju un noregulēsim loku caurlaidspēju: A(M 2)=min{d 13 , d 36 , d 67 } =min{45, 40, 30} = 30. d 13 ¢ = d 13 - 30 = 15, d 36 ¢ = d 36 - 30 = 10, d 67 ¢ = d 67 - 30 = 0.
3. SOLIS. Tīkla maksimālās plūsmas pašreizējās vērtības korekcija. A t:= A t + A(M 1)+ A(M 2) = 0 + 10+ 30 = 40.4. SOLIS. Tīkla korekcija. Atrasts uz 2. SOLIS maksimālās plūsmas A(M 1), A(M 2) maršrutos M 1 , M 2 tiek atņemts no to loku ietilpības. Tiek noņemti loki ar nulles atlikušo jaudu. Rezultāts dots 1.16. a attēlā. a) b) 1.16.att. Tīkla korekcijas rezultāts pēc iterācijām es Un IISTEP 5. Algoritma pabeigšanas pārbaude. Pielāgotajā tīklā (1.16. att. a) ir maršruti no avota v un uz krājumiem v ar, Piemēram M 3 = (v un =V 1 , V 4 , V 2 , V 5 , v s = V 7). Turpinot algoritma izpildi .II atkārtojums. 2. SOLIS. Kā vienīgais neatkarīgais maršruts, ko ejam M 3 = (v un =V 1 , V 4 , V 2 , V 5 , v s = V 7). Viņam:
A(M 3)=min{d 14 , d 42 , d 25 , d 57 } =min{15, 10, 10, 15} = 10.
d 14 ¢ = d 14 - 10 = 5, d 42 ¢ = d 42 - 10 = 0, d 25 ¢ = d 25 - 10 = 0, d 57 ¢ = d 57 - 10 = 5.
3. SOLIS. A t:= A t + A(M 3) = 40 + 10= 50.4. SOLIS. Tīkla korekcija. Maksimālā plūsma A(M 3) atņem no maršruta lokiem M 13. Rezultāts ir dots 1.16. b attēlā.
5. SOLIS. Pielāgotajā tīklā nav palicis neviens maršruts no avota līdz izlietnei. A:= A t:= 50, algoritma pabeigšana. Atbilde: maksimālā plūsma tīklā 1.15.att. ir 50.Ja tīklā ir norādīti vairāki avoti, tas tiek pabeigts, ieviešot jaunu kopīgu avotu, kas ir savienots ar oriģinālajiem avotiem ar neierobežotas jaudas lokiem. Tad problēma tiek atrisināta ar pēc parastā algoritma. Nepieciešamās plūsmas caur sākotnējiem avotiem būs plūsmas pa tikko pievienotajiem lokiem, kas tajos ienāks no jauna kopīga avota. Dariet to pašu, ja tīklā ir vairākas notekcaurules.
Tīkla plānošana
Jebkurš uzdevums projektēt vai konstruēt diezgan sarežģītu objektu ( projektu) var sadalīt vairākos mazākos komponentos. No pareizā izvēleŠo darbību secība ir atkarīga no visa projekta laika.
Viss projekta īstenošanas pasākumu klāsts tiek prezentēts kā kopums notikumiem Un darbojas. Notikumi tiek saukti par atsevišķiem projekta posmiem. Darbs ir tā pabeigšanas process. Visu projekta pabeigšanai nepieciešamo pasākumu un darbu kompleksu var attēlot divu polu tīkla veidā G =({v un v z} , V, X), kurā:
a) viss notikumiem apzīmētas ar virsotņu kopu V, izcelts starp tiem sākotnējais notikums v un(darba sākums) un noslēguma pasākums v z(visa projekta pabeigšana), nosaka tīkla iekšējās virsotnes starpposma notikumi- darbības, kas šajā procesā jāpabeidz projekta īstenošana,
b) viss strādāt tiek apzīmēti ar lokiem, kas savieno notikumu pārus – virsotnes.
Šī tīkla grafisko attēlojumu sauc tīkla diagramma. Lai norādītu darbību secību, ievadiet arī tīkla diagrammu fiktīvi darbi, kas nav saistīti ar kādu darbību veikšanu. Atbilstošie darbi ir apzīmēti ar punktētām lokām.
Kā piemēru apsveriet kādas ražošanas organizēšanu. Projektam ir nepieciešams šāds darbs:
I) mārketinga pētījumi, II) aprīkojuma pirmsprojektēšanas pētījumi, III) tirdzniecības tīkla organizēšana, IV) vadīšana reklāmas kampaņa, V) ražošanas iekārtu tehnisko specifikāciju izstrāde, VI) izstrāde tehnisko dokumentāciju ražošanas telpām un komunikācijām, VII) standarta aprīkojuma iegāde, VIII) nestandarta aprīkojuma projektēšana un izgatavošana, IX) ražošanas telpu izbūve un komunikāciju ierīkošana, X) standarta aprīkojuma uzstādīšana, XI) nestandarta aprīkojuma uzstādīšana , XII) nodošana ekspluatācijā.
Šos darbus tīkla diagrammā apzīmēsim ar lokiem ar atbilstošiem skaitļiem.
Notikumi šajā projektā būs šādi:
1) darba uzsākšana (sākotnējais notikums), 2) pabeigšana mārketinga pētījumi, 3) pirmsprojektēšanas pētījumu pabeigšana, 4) tirdzniecības tīkla organizēšana, 5) reklāmas kampaņas organizēšana, 6) ražošanas iekārtu tehnisko specifikāciju sagatavošana, 7) ražošanas telpu un komunikāciju tehniskās dokumentācijas izstrādes pabeigšana. , 8) standarta aprīkojuma iegādes pabeigšana, 9) nestandarta iekārtu projektēšanas un izgatavošanas pabeigšana, 10) ražošanas telpu būvniecības un komunikāciju ierīkošanas pabeigšana, 11) iekārtu uzstādīšanas un nodošanas ekspluatācijā darbu pabeigšana,
12) projekta pabeigšana (nobeiguma pasākums).
Mēs saistām virsotnes ar atbilstošiem notikumu skaitļiem. Tīkla diagramma Projekta īstenošana ir parādīta attēlā. 1.17:
1.17.att. Projekta īstenošanas tīkla grafiks
Hamiltona cikli
Grafiks ir dots matricas veidā, kur šūnās ir norādītas kustības izmaksas starp punktiem. Simbols ∞ ir novietots uz galvenās diagonāles, lai novērstu bezjēdzīgu ceļu uz sevi.
Jo Ja iegūtajā matricā ir kolonna bez nulles elementiem, tad mēs tajā atradīsim minimālo elementu un atņemsim to no visiem šīs kolonnas elementiem.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Apkoposim visus atņemtos elementus un iegūsim cikla apakšējo robežu in= 2+2+3+2+1=10
1.2. Novērtēsim visus matricas nulles elementus.
Nulles aplēses ir ērti uzrādīt tabulā.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
θ=max γ=γ A C =2
1.3. Sadalīsim ceļu kopu divās apakškopās: Q A.C.– ceļi, kas satur loku (AC) un Q A.C.– ceļi, kas nesatur loku (AC). Otrajai apakškopai apakšējā robeža būs: in / = iekšā + θ =10+2=12.
Lai aprēķinātu pirmās apakškopas robežu, mēs pārejam uz matricu par vienu lieluma pakāpi zemāku, izsvītrojot A rindu un C kolonnu. Jaunajā matricā, lai novērstu apgriezto ceļu (CA), mēs ievietojam zīmi ∞ attiecīgajā šūnā.
Aprēķināsim iegūtās matricas robežu 2+0=2
un pievienojiet to cilpas apakšējai robežai. Šī summa in // =10+2=12 un būs pirmās apakškopas robeža.
1.4. Salīdzināsim visu piekārto virsotņu robežas un atlasīsim virsotni ar mazāko robežu. Ja ir divas no šīm virsotnēm, izvēlieties jebkuru no tām. Šī ir Q augšdaļa A.C., kuras apakšējā robeža =12.
Izvēlēsimies maksimālo no tāmēm θ=max γ=γ BD =3
in / =12+3=15.
1.6. Visus nākamos punktus veicam līdzīgi kā iepriekšējie.
Izvēlēsimies maksimālo no tāmēm θ=max γ=γ C B =∞
in / =in+ θ=∞
| A | |
| D |
Visas šīs matricas rindas un kolonnas satur nulles. Tāpēc ierobežojums paliek vienāds ar 12.
UZDEVUMS. Atrodiet maksimālās plūsmas vērtību transporta tīklā.
PROBLĒMAS PAZIŅOJUMS.
Apsveriet transporta problēmu tīklā ( Es, D, G) ar doto loka jaudu c(i,j).
Izvēlēsimies divas fiksētas virsotnes: s- avots un t– notecēt. Straumējiet tīklā s→t sauksim skaitlisko funkciju f, kas definēts uz loku kopas un atbilst tālāk norādītajām prasībām lineārie vienādojumi un nevienlīdzības:
0≤ f(i,j) ≤c(i,j) jebkuram (i, j)
Nepieciešams, lai palielinātu mainīgo x
Izgriezt L tīklā, kas atdala virsotnes s t
sauc par loku kopu 
Jebkurā veidā s→t satur vismaz vienu nogrieztu loku.
OPTIMĀLITĀTES KRITĒRIJI: reālā tīklā patvaļīgas plūsmas vērtība nepārsniedz griezuma caurlaidspēju, un maksimālās plūsmas vērtība ir vienāda ar griezuma minimālo caurlaidspēju.
PIEMĒRS 3.12.
M 9 K
M 8 K
PIEMĒRS 3.13.
M 2 K
RISINĀJUMS :
Izejošā loka kapacitāte (T,B) pārsniedz attiecīgajā virsotnē ienākošo loku kopējo kapacitāti. Lai tīkls kļūtu reāls, mēs aizstājam c(T,B)=5.
Atradīsim un aprēķināsim visu griezumu caurlaides jaudu vērtību. (K,V) – (T,V) griešana ar minimālo caurlaidspēju =6. Tāpēc maksimālā plūsma =6.
Tīklu ar vairākiem avotiem un izlietnēm var reducēt līdz tīklam ar vienu avotu un izlietni.
PIEMĒRS. Lai ir vairāki avoti S un izlietnes T ( transporta problēma). Paplašināsim tīklu, pievienojot divus mezglus s*, t* un visus lokus (s*, S) , (T,t*). Definēsim jaudas funkciju, iestatot
ATZĪMJU IZVIETOŠANAS METODE.
1. Sākotnējā plūsma f(i,j) = 0.
Piešķirsim etiķetes šī tīkla virsotnēm, kurām būs forma (i+, ε) vai
(i - , ε). Atzīmēsim avotu (-, ∞),
tie . ε(s)= ∞.
2. Jebkurai atzīmētai virsotnei i
atlasiet visas nemarķētās virsotnes j
priekš kam f(i,j)
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
| 1 solis | A → (-, ∞) M → (A+,8) P → (A+,3) K → (P+,3) T → (P+,3) B → (T+,3) | f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(A,M)=0 f(M,P)=0 f(M,K)=0 f(M,T)=0 f(K,T)=0 f( K,B)=0 |
| 2. darbība | A → (-, ∞) M → (A+,8) P → (M+,1) K → (M+,4) T → (M+,2) | f(K,B)=3 f(M,K)=3 f(A,M)=3 f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,T)=0 f(M,P)=0 f(K,T)=0 |
| 3. darbība | A → (-, ∞) M → (A+,5) P → (M+,1) K → (M+,1) T → (M+,2) B → (T+,2) | f(T,B)=5 f(M,T)=2 f(A,M)=5 f(K,B)=3 f(M,K)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,P)=0 f(K,T)=0 |
| 4. darbība | A → (-, ∞) M → (A+,3) P → (M+,1) K → (M+,1) T → (P+,1) B → (T+,1) | f(A,M)=6 f(T,B)=6 f(P,T)=4 f(M,P)=1 f(M,T)=2 f(K,B)=3 f(M,K)=3 f(A,P)=3 f(P,K)=0 f(K,T)=0 |
| 5. darbība | A → (-, ∞) M → (A+,2) P → (M-,1) K → (M+,1) T → (K+,1) B → (T+,1) | f(A,M)=7 f(M,K)=4 f(K,T)=1 f(T,B)=7 f(P,T)=4 f(M,P)=1 f( M,T)=2 f(K,B)=3 f(A,P)=3 f(P,K)=0 |
| 6. darbība | A → (-, ∞) M → (A+,1) | Plūsma ir optimāla f=10 Minimālais griezums: M→T-M→R-M→UZ |
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 no х i iet nepiesātinātie loki, 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 ja, 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
Noteiktā 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ā 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 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.
| |
| |
| |
| UZDEVUMS 2. Par automašīnas iekraušanu (par mugursomu). Ir N vienumi. Zināms svars a i un vērtību φi katru vienumu. Nepieciešams, lai piepildītu mugursomu, kas spēj noturēt svaru ≤ R , tāds priekšmetu kopums, kam būtu vislielākā vērtība.
Mugursomas ielādes procesu var iedalīt N soļos. Katrā solī mēs izlemjam jautājumu: ņemt šo preci vai neņemt to? Katrā solī ir tikai 2 vadīklas: kontrole = 1, ja ņemam šo vienumu; un 0 – ja mēs to neņemam. Sistēmas stāvokli pirms nākamā soļa raksturo svars S, kas joprojām paliek mūsu rīcībā līdz pilnas iekraušanas beigām pēc iepriekšējo darbību pabeigšanas (daži priekšmeti jau ir ielādēti), t.i. brīvās vietas daudzums mugursomā. ALGORITMS. 1. Sāksim no pēdējā soļa. Izdarīsim dažādus pieņēmumus par brīvo vietu mugursomā: S=0,1,…R. Ieliksim pēdējo lietu mugursomā, ja tai ir pietiekami daudz vietas. 2. Katrā iepriekšējā solī visiem iespējamajiem stāvokļiem S apsveram 2 variantus: ņemt vai neņemt objektu. Atradīsim katrā gadījumā ieguvumu kā pašreizējā soļa un nākamā jau optimizētā soļa ieguvumu summu. Rezultātus ievadīsim palīgtabulā. 3. Pirmajā solī mēs ņemam vērā tikai vienīgo iespējamo stāvokli S=R. 4. Meklēsim risinājumu, “virzoties atmuguriski”, t.i. Veicot optimālu kontroli pirmajā solī, mēs mainām sistēmas stāvokli otrajā solī: S=R– x 1 a 1 un izvēlieties šim stāvoklim optimālo vadību x 2. utt. PIEMĒRS 4.2. Sākotnējie dati
Galvenā tabula
Palīggalds.
Atbilde: x 4 =0; x 3 =1; x 2 =0; x 1 = 1; W=15 Uzdevums 3. Par resursu sadali. Ir N uzņēmumu P 1, P 2,… P N, no kuriem katrs rada ienākumus φ k (x), ja tam tiek piešķirts resurss x apmērā. Nepieciešams A daudzumā pieejamo resursu sadalīt starp objektiem tā, lai kopējie ienākumi būtu maksimāli. Pieņemsim, ka x k ir k-tam uzņēmumam piešķirtā resursa apjoms. Tad izskatāmā problēma tiek reducēta uz parasto problēmu lineārā programmēšana.
Formulēsim problēmu kā dinamiskas programmēšanas problēmu. Pirmajā solī mēs veiksim līdzekļu ieguldīšanu uzņēmumā P 1, otrajā - P 2 utt. Pārvaldītā sistēma iekšā šajā gadījumā– līdzekļi, kas tiek sadalīti. Sistēmas stāvokli pirms katra soļa raksturo viens parametrs – pieejamais vēl neieguldīto līdzekļu krājums. Šajā problēmā soļu kontrole ir uzņēmumiem piešķirtie līdzekļi. Nepieciešams atrast optimālo kontroli (x 1, x 2,...x N), pie kuras kopējie ienākumi ir maksimāli: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| i=1 S=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
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 kontrole x i dod 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, atrastajam stāvoklim atrast optimālo vadību otrajā solī 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
Šī 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 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
|
Plūsmas daudzums |
virziens |
||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(30,0) - (0,30)=(30, - 30) |
|||
|
(10,0) - (0,10)=(10, - 10) |
|||
|
(40,0) - (40,0)=(0,0) |
|||
|
(30,0) - (10,20)=(20, - 20) |
|||
|
(10,5) - (0,15)=(10, - 10) |
|||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(20,0) - (0,20)=(20, - 20) |
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
|
Izbraukšanas vieta |
Galamērķis |
Transporta plāns |
Joslas platums |
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 līdzsvara attiecību 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ānojot racionālu produkcijas izplatīšanu izplatīšanas tīklā, ir nepieciešams saskaņot kanāla jaudu ar klientu vajadzībām un ar ražotnes jaudu. Šīs klases problēmas tiek atrisinātas, atrodot maksimālo plūsmu.
Apskatīsim sadales tīklu (4.21. att.), kurā punkti 0 (ieeja, piemēram, ražotāja gatavās produkcijas noliktavā) un. n (izeja, sadales centri, vairumtirdzniecības un mazumtirdzniecības organizāciju noliktavas, patērētājs) un katra loka (segmenta) savienojuma punkti i Un j, skaitlis dij > 0 ir saistīts, tiek saukts caurlaidspēja loki. Caurlaides vērtība raksturo maksimumu pieļaujamais daudzums materiāla plūsma, kas var iet pa atbilstošo loku laika vienībā.
Rīsi. 4.21.
Produktu daudzums, kas iet pa loku no i uz j , mēs to sauksim par plūsmu pa loku ( i ,j ) un apzīmē ar . Ir skaidrs, ka
Ja ņemam vērā, ka visai materiālu plūsmai, kas nonāk tīkla starppunktā, ir pilnībā jāiziet no tā, mēs iegūstam
No dabiskās prasības par plūsmu vienādību pie ieejas un izejas, kas mums ir
Mēs nosauksim Z vērtību par plūsmas vērtību tīklā un radīsim problēmu, kā palielināt Z, ievērojot iepriekšminētos nosacījumus.
Maksimālās plūsmas atrašana nozīmē minimālā griezuma caurlaides atrašanu.
Apskatīsim universālu meklēšanas algoritmu matricas formā.
Algoritma sākuma posms sastāv no matricas konstruēšanas D 0, kurā tiek ievadītas caurlaides vērtības (neorientētam lokam mēs ņemam matricas elementu simetriskas vērtības).
Algoritma galvenie soļi ir atrast noteiktu ceļu un koriģēt plūsmu pa šo ceļu.
Meklējot ceļu, mēs izmantojam marķēšanas procesu. Ar simbolu * atzīmējam matricas (tīkla ievade) nulles rindu un kolonnu. 0. rindā mēs meklējam , atzīmējiet atbilstošās kolonnas ar indeksiem
un pārvietojiet kolonnu etiķetes uz rindām. Pēc tam ņemam i-to atzīmēto rindu, meklējam tajā neatzīmētu kolonnu ar , kurai pieskaņojam indeksa etiķetes
Mēs pārnesam kolonnu etiķetes uz rindām un turpinām šo procesu, līdz tiek atzīmēta n-tā kolonna.
Tad " otrādi"izmantojot indeksus, noskaidrojam ceļu, kas veda uz η-to virsotni, samazinām ceļa loku (matricas elementu) kapacitāti par V n un palieliniet simetriskos elementus par tādu pašu summu.
Šī procedūra turpinās līdz marķējumam n -topi nekļūs neiespējami.
Maksimālo plūsmu var atrast, atņemot no sākotnējās matricas D 0, iegūts pēc iepriekš minētās jaudas matricas korekcijas:
Piemērs 4.4
Ražošana atrodas Maskavā. Lai izplatītu produktus, uzņēmums piesaista starpniekus, kas strādā ar uzņēmumu, izmantojot dažādu līmeņu izplatīšanas centrus. Krievijas Eiropas daļā ir vairumtirdzniecības uzņēmums 1, kuru apkalpo centrālais izplatīšanas centrs. Vairumtirdzniecības uzņēmums 2 darbojas tuvākajās ārzemēs (Ukrainā, Baltkrievijā), un to apkalpo reģionālais izplatīšanas centrs. Uzņēmumam ir savi klienti vietējā tirgū (Maskavas un Maskavas apgabalā) - mazumtirgotāji, kas saņem produkciju no pilsētas izplatīšanas centra. Reģionālie un pilsētas sadales centri tiek papildināti no centrālā sadales centra.
Izcelsim sadales tīkla fragmentu:
- ražošanas uzņēmuma gatavās produkcijas noliktava;
- centrālais sadales centrs;
- reģionālais sadales centrs;
- pilsētas izplatīšanas centrs;
- divi vairumtirdzniecības uzņēmumi;
- uzņēmumam piederoša mazumtirdzniecības vieta;
- patērētājiem.
Rīsi. 4.22.
Apzīmēsim katru sadales tīkla saiti ar numuru un novietosim jaudu virs lokiem. Caurlaides jauda, atkarībā no savienojuma veida, var tikt izteikta kā ražošanas jaudas apjoms, plānotā patērētāju nepieciešamība (pieprasījums) un tirgus kapacitāte.
Preču izplatīšanas tīkla grafiks ir parādīts attēlā. 4.23. Veidosim matricu D 0, kurā ievadām sadales tīkla saišu caurlaides kapacitātes vērtības (4.24. att.).
Rīsi. 4.23.
Rīsi. 4.24.
No nulles rindas atzīmējam virsotnes (rindas-kolonnas) 1, 2 un 3 ar indeksiem μ = 0 un V, vienāds ar 30,10 un 10.
No atzīmētās 1. līnijas atzīmējiet virsotnes 4 un 5 ar indeksiem μ = 1 un V4 = min (30,15) = 15, V5 = min (30,10) = 10.
No 3. līnijas atzīmējam virsotni 6 un, visbeidzot, no 4. līnijas – virsotni 7 (4.25. att.).
Rīsi. 4.25.
Atgriežoties pa μ, mēs atrodam ceļu: uz virsotni 7 no 4, uz virsotni 4 no 1, uz virsotni 1 no 0; regulēšanas elementi D 0 uz plūsmas vērtību V7 = 15.
Nākamais solis dod ceļu ar plūsmu 5 (4.26. att.).
Rīsi. 4.26.
Nākamais solis dod rezultātu, kas parādīts attēlā. 4.27.
Rīsi. 4.27.
Turpmāka marķēšana nav iespējama. No šejienes iegūstam maksimālās plūsmas matricu (4.28. att.).
Rīsi. 4.28.
Pielietojot algoritmu maksimālās plūsmas noteikšanai tīklā, rezultāti, kas parādīti att. 4.29. Diagrammas lokos parādītie skaitļu pāri iekavās norāda loka maksimālo caurlaidspēju un ieteicamo tīklam piegādāto preču apjomu.
Plūsmu summa cauri lokiem, kas krīt v, 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ākais iespējamais lielums - 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 v V 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 līdzvērtīgi viens otram; Š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 v vairs nav avots, bet gan izlietne.
3. darbība. Ja tīklā N’ mēs varam atrast plūsmu, kas nav nulle no v 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ā
