Pinakamataas na daloy.

Algorithm para sa pagkalkula ng maximum na daloy sa mga network

Pag-ulit ko. HAKBANG 2. Pagpili ng mga independiyenteng ruta sa network at pagtukoy ng mga daloy sa kanila. Bilang M 1 daanan ( v at =V 1 , V 2 , V 5 , v na may =V 7), isinasaalang-alang sa halimbawa 1. Para sa kanya A(M 1) = 10.

Madali ding ihiwalay ang independyente M 1 ruta M 2 = (v at =V 1 , V 3 , V 6 , v na may =V 7). Kalkulahin natin ang maximum throughput para dito at ayusin ang throughput ng mga arc: 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.

II pag-ulit. HAKBANG 2. Bilang ang tanging independiyenteng ruta na ating tinatahak M 3 = (v at =V 1 , V 4 , V 2 , V 5 , v na may =V 7). Para sa kanya:

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.

HAKBANG 4. Pagwawasto ng network.Pinakamataas na daloy A(M 3) ibawas mula sa mga arko ng ruta M 13 . Ang resulta ay ibinigay sa Fig. 1.16 b.

Kung ang ilang mga mapagkukunan ay tinukoy sa network, ito ay nakumpleto sa pamamagitan ng pagpapakilala ng isang bagong karaniwang mapagkukunan, na konektado sa mga orihinal na mapagkukunan sa pamamagitan ng mga arko na may walang limitasyong kapasidad. Pagkatapos ay malulutas ang problema gamit ang karaniwang algorithm. Ang mga kinakailangang daloy sa mga orihinal na mapagkukunan ay magiging mga daloy kasama ang mga bagong idinagdag na arko na pumapasok sa kanila mula sa isang bagong karaniwang pinagmulan. Gawin ang parehong kung mayroong ilang mga drains sa network.

Pagpaplano ng network

Anumang gawain ng pagdidisenyo o paggawa ng medyo kumplikadong bagay ( proyekto) ay maaaring hatiin sa ilang mas maliliit na hakbang sa bahagi. Ang timing ng buong proyekto ay nakasalalay sa tamang pagpili ng pagkakasunud-sunod ng mga hakbang na ito.

Ang buong hanay ng mga aksyon para ipatupad ang proyekto ay ipinakita bilang isang set mga pangyayari At gumagana. Ang mga kaganapan ay tinatawag na mga indibidwal na yugto ng isang proyekto. Ang trabaho ay ang proseso ng pagkumpleto nito. Ang buong kumplikado ng mga kaganapan at trabaho na kinakailangan upang makumpleto ang proyekto ay maaaring katawanin sa anyo ng isang dalawang-pol na network G =({v at, v z} , V, X), kung saan:

at lahat mga pangyayari minarkahan ng isang hanay ng mga vertex V, naka-highlight sa kanila paunang kaganapan v at(pagsisimula ng trabaho) at huling kaganapan v z(pagkumpleto ng buong proyekto), ang mga panloob na vertex ng network ay tumutukoy mga intermediate na kaganapan- mga yugto na kailangang kumpletuhin sa panahon ng proseso ng pagpapatupad ng proyekto,

b) lahat trabaho ay ipinahiwatig ng mga arko na nagkokonekta sa mga pares ng mga kaganapan - mga vertice.

Graphic na larawan ang network na ito ay tinatawag na diagram ng network. Upang ipahiwatig ang pagkakasunud-sunod ng mga aksyon, pumasok din sa diagram ng network gawa-gawa lamang, na hindi nauugnay sa pagsasagawa ng anumang mga aksyon. Ang kaukulang mga gawa ay ipinahiwatig ng mga dashed arc.

Bilang halimbawa, isaalang-alang ang organisasyon ng ilang produksyon. Ang proyekto ay nangangailangan ng sumusunod na gawain:

I) pananaliksik sa marketing, II) pre-project na pananaliksik sa kagamitan, III) pag-aayos ng isang network ng pagbebenta, IV) pagsasagawa ng isang kampanya sa advertising, V) pagbuo ng mga teknikal na pagtutukoy para sa mga kagamitan sa produksyon, VI) pagbuo ng teknikal na dokumentasyon para sa mga lugar ng produksyon at komunikasyon, VII) pagbili ng karaniwang kagamitan, VIII) disenyo at paggawa ng hindi pamantayang kagamitan, IX) pagtatayo ng mga pasilidad ng produksyon at pag-install ng mga komunikasyon, X) pag-install ng karaniwang kagamitan, XI) pag-install ng hindi pamantayang kagamitan, XII) pagkomisyon.

Ipapahiwatig namin ang mga gawang ito sa diagram ng network sa pamamagitan ng mga arko na may kaukulang mga numero.

Ang mga kaganapan sa proyektong ito ay ang mga sumusunod:

1) pagsisimula ng trabaho (paunang kaganapan), 2) pagkumpleto pananaliksik sa marketing, 3) pagkumpleto ng mga pag-aaral bago ang disenyo, 4) organisasyon ng isang network ng pagbebenta, 5) organisasyon ng isang kampanya sa advertising, 6) paghahanda ng mga teknikal na pagtutukoy para sa mga kagamitan sa produksyon, 7) pagkumpleto ng pagbuo ng teknikal na dokumentasyon para sa mga lugar ng produksyon at komunikasyon , 8) pagkumpleto ng pagbili ng mga karaniwang kagamitan, 9) pagkumpleto ng disenyo at paggawa ng mga hindi pamantayang kagamitan, 10) pagkumpleto ng pagtatayo ng mga pasilidad ng produksyon at pag-install ng mga komunikasyon, 11) pagkumpleto ng pag-install ng kagamitan at mga gawain sa pagkomisyon,

12) pagkumpleto ng proyekto (panghuling kaganapan).

Iniuugnay namin ang mga vertex sa mga katumbas na numero sa mga kaganapan. Diagram ng network Ang pagpapatupad ng proyekto ay ipinapakita sa Fig. 1.17:

Fig.1.17. Iskedyul ng network ng pagpapatupad ng proyekto

Kapag nagpaplano ng makatwirang pamamahagi ng mga produkto sa network ng pamamahagi, kinakailangan na i-coordinate ang kapasidad ng channel sa mga pangangailangan at kapangyarihan ng customer negosyong pagmamanupaktura. Ang klase ng mga problemang ito ay nalulutas sa pamamagitan ng paghahanap ng pinakamataas na daloy.

Isaalang-alang natin ang isang network ng pamamahagi (Larawan 4.21), kung saan ang mga puntos ay 0 (pasok, halimbawa, bodega ng isang tagagawa ng mga natapos na produkto) at P (exit, distribution centers, warehouses ng wholesale at retail organizations, consumer) at bawat arc (segment) connecting point i At j, ang numero dij > 0 ay nauugnay, tinatawag throughput mga arko. Tinutukoy ng throughput value ang maximum na pinahihintulutang dami ng daloy ng materyal na maaaring dumaan sa katumbas na arko bawat yunit ng oras.

kanin. 4.21.

Ang dami ng mga produkto na dumadaan sa isang arko mula sa i dati j , tatawagin natin itong daloy sa isang arko ( i ,j ) at tinutukoy ng . Obvious naman yun

Isinasaalang-alang na ang lahat daloy ng materyal, na pumasok sa isang intermediate point ng network, dapat na ganap na iwanan ito, nakukuha namin

Mula sa natural na pangangailangan ng pagkakapantay-pantay ng mga daloy sa input at output na mayroon tayo

Tatawagin namin ang halaga ng Z bilang halaga ng daloy sa network at ipoposisyon ang problema ng pag-maximize ng Z na napapailalim sa mga kundisyon sa itaas.

Ang paghahanap ng maximum na daloy ay bumababa sa paghahanap ng throughput ng minimum na hiwa.

Isaalang-alang natin ang isang pangkalahatang algorithm ng paghahanap sa anyo ng matrix.

Ang unang yugto ng algorithm ay binubuo ng pagbuo ng isang matrix D 0, kung saan ipinasok ang mga halaga ng throughput (para sa isang hindi naka-orient na arko ay kinukuha namin ang mga simetriko na halaga ng mga elemento ng matrix).

Ang mga pangunahing hakbang ng algorithm ay ang paghahanap ng isang tiyak na landas at itama ang daloy sa landas na ito.

Kapag naghahanap ng landas, gumagamit kami ng proseso ng pagmamarka. Minarkahan namin ng simbolo * ang zero row at column ng matrix (network input). Sa 0th line na hinahanap namin , markahan ang kaukulang mga column na may mga indeks

at ilipat ang mga label ng column sa mga row. Pagkatapos ay kunin namin ang ith na may markang hilera, maghanap ng isang hindi namarkahang column dito na may , kung saan kami ay tumutugma sa mga label ng index

Inilipat namin ang mga label ng column sa mga row, at ipagpatuloy ang prosesong ito hanggang sa mamarkahan ang ika-n column.

Pagkatapos, gamit ang mga indeks, nalaman natin ang landas na humantong sa η-th vertex gamit ang mga indeks, at bawasan ang kapasidad ng mga arko ng landas (mga elemento ng matrix) sa pamamagitan ng V n at dagdagan ang mga simetriko na elemento ng parehong halaga.

Ang pamamaraang ito ay nagpapatuloy hanggang sa pagmamarka n -itaas ay hindi magiging imposible.

Ang pinakamataas na daloy ay matatagpuan sa pamamagitan ng pagbabawas mula sa orihinal na matris D 0, nakuha pagkatapos ng pagwawasto sa itaas ng capacity matrix:

Halimbawa 4.4

Ang produksyon ay matatagpuan sa Moscow. Upang ipamahagi ang mga produkto, ang kumpanya ay umaakit ng mga tagapamagitan na nagtatrabaho sa kumpanya sa pamamagitan ng mga sentro ng pamamahagi sa iba't ibang antas. Sa European na bahagi ng Russia mayroong isang pakyawan na negosyo 1, na sineserbisyuhan ng isang sentral na sentro ng pamamahagi. Ang wholesale enterprise 2 ay tumatakbo sa malapit sa ibang bansa(Ukraine, Belarus) at pinaglilingkuran ng isang sentro ng pamamahagi ng rehiyon. Ang kumpanya ay may sariling mga kliyente sa lokal na merkado (Moscow at Moscow rehiyon) - mga nagtitingi na tumatanggap ng mga produkto mula sa sentro ng pamamahagi ng lungsod. Ang mga sentro ng pamamahagi ng rehiyon at lungsod ay nire-restock mula sa sentro ng pamamahagi.

I-highlight natin ang isang fragment ng distribution network:

• bodega ng mga natapos na produkto ng isang manufacturing enterprise;
• sentro ng pamamahagi;
• sentro ng pamamahagi ng rehiyon;
• sentro ng pamamahagi ng lungsod;
• dalawang pakyawan na negosyo;
• retail outlet na pag-aari ng kumpanya;
• mga mamimili.

kanin. 4.22.

Italaga natin ang bawat link ng distribution network na may numero, at ilagay ang kapasidad sa itaas ng mga arko. Ang kapasidad, depende sa uri ng link, ay maaaring ipahayag sa mga tuntunin ng lakas ng tunog kapasidad ng produksyon, nakaplanong pangangailangan (demand) ng mga mamimili at kapasidad sa pamilihan.

Ang graph ng network ng pamamahagi ng produkto ay ipinapakita sa Fig. 4.23. Bumuo tayo ng matrix D 0, kung saan ipinasok namin ang mga halaga ng mga kapasidad ng throughput ng mga link sa network ng pamamahagi (Larawan 4.24).

kanin. 4.23.

kanin. 4.24.

Mula sa zero row ay minarkahan namin ang vertices (rows-column) 1, 2 at 3 na may mga indeks μ = 0 at V, katumbas ng 30.10 at 10.

Mula sa minarkahang linya 1, markahan ang mga vertice 4 at 5 na may mga indeks na μ = 1 at V4 = min (30,15) = 15, V5 = min (30,10) = 10.

Mula sa linya 3 minarkahan namin ang vertex 6 at, sa wakas, mula sa linya 4 - vertex 7 (Fig. 4.25).

kanin. 4.25.

Sa pagbabalik sa kahabaan ng μ makikita natin ang landas: sa vertex 7 mula sa 4, sa vertex 4 mula sa 1, sa vertex 1 mula sa 0; mga elemento ng pagsasaayos D 0 bawat halaga ng daloy V7 = 15.

Ang susunod na hakbang ay nagbibigay ng landas na may daloy 5 (Larawan 4.26).

kanin. 4.26.

Ang susunod na hakbang ay nagbibigay ng resulta na ipinapakita sa Fig. 4.27.

kanin. 4.27.

Walang karagdagang pagmamarka ang posible. Mula dito nakuha namin ang maximum na flow matrix (Larawan 4.28).

kanin. 4.28.

Bilang resulta ng paglalapat ng algorithm para sa paghahanap ng pinakamataas na daloy sa network, ang mga resulta na ipinakita sa Fig. 4.29. Ang mga pares ng mga numero sa mga bracket na ipinapakita sa mga arko ng graph ay nagpapahiwatig ng maximum na throughput ng arko at ang inirerekomendang dami ng mga kalakal na ibinibigay sa network.

Gawain sa transportasyon
Maaaring lumitaw sa pisika, ekonomiya, atbp.
Sa mga indibidwal na bahagi ng network ng transportasyon
(network ng mga riles, kalsada, atbp.
mga landas; pipeline network, atbp.) superimposed
mga paghihigpit - ang kanilang pinakamataas na pinahihintulutan
load.
Ito ay kinakailangan upang matukoy ang maximum
posibleng bilang ng mga pasahero, kalakal,
produkto, atbp., na maaaring dalhin sa pamamagitan nito
network at kung paano.
Bubuo kami ng discrete graph model
itong problema sa transportasyon at lutasin ito dito
mga modelo.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.