Pinakamataas na daloy ng network. Algorithm para sa paghahanap ng maximum na daloy

Ulitin namin ang operasyong ito hanggang sa mamarkahan ang alisan ng tubig. Kung ang daloy ay nananatiling walang label, kung gayon ang daloy na natagpuan ay pinakamataas, at ang hanay ng mga arko na nagkokonekta sa mga may markang vertice na may mga hindi namarkahan ay bumubuo ng isang minimal na hiwa.

3. Hayaang may label ang stock (j+, ε(t)), Pagkatapos f(j,t) palitan ng f(j,t)+ε(t). Kung ang stock ay minarkahan (j-, ε(t)), Iyon f(j,t) palitan ng f(j,t)-ε(t). Punta tayo sa taas j. Kung j may marka (i+, ε(j)), pagkatapos ay papalitan namin f(i,j) sa f(i,j)+ε(t), at kung (i-, ε(j)), f(j,i) palitan ng f(j,i)-ε(t). Punta tayo sa taas i. Ulitin namin ang operasyong ito hanggang sa maabot namin ang pinagmulan s. Huminto ang pagbabago ng daloy, mabubura ang lahat ng marka at pumunta sa hakbang 2

HALIMBAWA 3.14.

M 4 K

GAWAIN. Hanapin ang pinakamataas na daloy sa network

ALGORITHM

Tukuyin natin ang vertex s= x 0 . Lahat ng iba ay x i.

Stage 1.

1. Pumili ng anumang landas na ang lahat ng mga arko ay hindi puspos.

2. Pinapataas namin ang dami ng daloy sa landas na ito ng isa hanggang sa walang puspos na arko dito.

Ipinagpapatuloy namin ang proseso ng pagtaas ng daloy hanggang sa mabuo ang buong daloy, i.e. anumang landas ay maglalaman ng hindi bababa sa isang saturated arc.

Stage 2.

2. Kung ang х i ay isa nang may markang vertex, minarkahan namin ang (+i) lahat ng walang label na vertices kung saan napupunta ang mga unsaturated arc mula sa х i, at kasama ang index (–i) lahat ng walang markang vertices kung saan napupunta ang mga arc na may non-zero flow. sa х i.

3. Kung bilang resulta ng prosesong ito ay minarkahan ang isang vertex t, pagkatapos ay sa pagitan s At t mayroong isang landas na ang lahat ng mga vertice ay minarkahan ng mga numero ng nakaraang mga vertex. Pinapataas namin ang daloy sa lahat ng mga arko ng landas na ito ng isa kung, kapag lumilipat mula s Upang t ang oryentasyon ng arko ay tumutugma sa direksyon ng paggalaw, at nababawasan ng isa kung ang arko ay may kabaligtaran na oryentasyon. Lumipat tayo sa hakbang 1.

4. Kapag ang tuktok t imposibleng markahan na ang proseso ay natapos na at ang resultang daloy ay ang pinakamalaking daloy ng network.

TANDAAN. Maaari kang pumunta sa yugto 2 nang hindi kinukumpleto ang unang yugto (tingnan ang halimbawa 3.16).

HALIMBAWA 3.15.

9

SOLUSYON:

Ang isang kumpletong daloy ay natagpuan sa isang partikular na network ng transportasyon. Ang mga saturated arc ay naka-highlight

Sa network na ito, maaari mo ring markahan ang huling vertex, at ang resulta ng pagmamarka ay magiging pareho. Sa pamamagitan ng pagpapalit ng daloy, nakakakuha tayo ng isang network kung saan imposibleng markahan ang huling vertex, kaya ang daloy sa loob nito ang pinakamalaki at katumbas ng 10.

HALIMBAWA 3.16.

8 2 1

May nakitang hindi kumpletong daloy sa isang partikular na network ng transportasyon

Markahan natin ang network at dagdagan ang daloy dito ayon sa algorithm. Nakukuha namin

Sa network na ito, maaari mo ring markahan ang huling vertex, at ang resulta ng pagmamarka ay magiging pareho. Sa pamamagitan ng pagbabago ng daloy, nakakakuha tayo ng isang network kung saan imposibleng markahan ang huling vertex, kaya ang daloy sa loob nito ang pinakamalaki at katumbas ng 6.

Seksyon IV. DYNAMIC PROGRAMMING.

Dynamic na programming ay ginagamit upang mahanap ang pinakamainam na multi-stage na solusyon. Halimbawa, pangmatagalang pagpaplano para sa pagpapalit ng kagamitan; aktibidad ng industriya sa loob ng ilang taon. Ginagamit nito ang prinsipyo ng optimality, ayon sa kung saan ang anumang bagong bahagyang solusyon ay dapat na pinakamainam na nauugnay sa nakamit na estado.

Mas mahusay na malutas ang isa nang maraming beses simpleng gawain kaysa minsan kumplikado.

PROBLEMA 1. Tungkol sa pinakakapaki-pakinabang na ruta sa pagitan ng dalawang punto.

Kinakailangan na bumuo ng isang landas na nagkokonekta sa dalawang puntong A at B, kung saan ang pangalawa ay nasa hilagang-silangan ng una. Para sa pagiging simple, sabihin natin na ang paglalagay ng isang landas ay binubuo ng isang serye ng mga hakbang, at sa bawat hakbang ay maaari tayong lumipat sa alinman sa hilaga o dahil sa silangan. Kung gayon ang anumang landas ay isang stepped broken line, ang mga segment na kung saan ay parallel sa isa sa mga coordinate axes. Ang mga gastos sa paggawa ng bawat isa sa mga seksyong ito ay kilala.

HALIMBAWA 4.1. Hanapin ang pinakamababang landas mula A hanggang B.

Ang huling hakbang ay upang makamit ang T.V. Bago ang huling hakbang, maaari tayong makarating sa mga punto kung saan maaari nating maabot ang T.V. sa isang hakbang. Mayroong dalawang ganoong mga punto (ang sistema ay maaaring nasa isa sa dalawang estado). Para sa bawat isa sa kanila mayroong isang solong pagpipilian upang maabot ang t.V: para sa isa - lumipat sa silangan; para sa isa pa - sa hilaga. Isulat natin ang mga gastos 4 at 3 sa bawat kaso.

4

Ngayon, i-optimize natin ang penultimate na hakbang. Pagkatapos ng nakaraang hakbang, maaari tayong mapunta sa isa sa tatlong puntos: C 1, C 2, C 3.

Para sa punto C 1, mayroon lamang isang kontrol (markahan natin ito ng isang arrow) - lumipat sa silangan, at ang mga gastos ay magiging 2 (sa hakbang na ito) + 4 (sa susunod na hakbang) = 6. Katulad nito, para sa item C 3 ang mga gastos ay magiging 2+3=5. Para sa t.C 2 mayroong dalawang kontrol: pumunta sa silangan o hilaga. Sa unang kaso, ang mga gastos ay magiging 3+3=6, at sa pangalawang kaso – 1+4=5. Nangangahulugan ito na ang kondisyon na pinakamainam na kontrol ay pumunta sa hilaga. Markahan natin ito ng isang arrow at ilagay ang kaukulang mga gastos.

Sagot: x 1 =1; x 3 =0; x 3 =4; W=3.5

GENERALIZED ALGORITHM

1. Ilarawan ang sistema. Iyon ay, alamin kung anong mga parameter ang nagpapakilala sa estado ng kinokontrol na sistema bago ang bawat hakbang. Mahalagang maitakda nang tama at "mahinhin" ang gawain, nang hindi pinapabigat ito ng mga hindi kinakailangang detalye, na pinapasimple ang paglalarawan ng kinokontrol na sistema hangga't maaari.

2. Hatiin ang operasyon sa mga hakbang (mga yugto). Ang lahat ng makatwirang paghihigpit na ipinataw sa pamamahala ay dapat isaalang-alang dito. Ang hakbang ay dapat sapat na maliit upang ang pamamaraan ng pag-optimize ng kontrol sa hakbang ay medyo simple; at ang hakbang, sa parehong oras, ay hindi dapat masyadong maliit upang hindi makagawa ng mga hindi kinakailangang kalkulasyon na nagpapalubha sa pamamaraan para sa paghahanap ng pinakamainam na solusyon, ngunit hindi humantong sa isang makabuluhang pagbabago sa pinakamabuting kalagayan layunin function.

3. Alamin ang hanay ng mga hakbang na kontrol x i para sa bawat hakbang at ang mga paghihigpit na ipinataw sa kanila.

4. Tukuyin kung ano ang nakuha ng kontrol x i na dinadala sa i-step, kung bago iyon ang sistema ay nasa estado S, i.e. isulat ang mga function ng kabayaran:

w i =f i (S, x i)

5. Tukuyin kung paano nagbabago ang estado ng system sa ilalim ng impluwensya ng control x i on 1st step, ibig sabihin. isulat ang mga function ng pagbabago ng estado.

S / =φ i (S, x i)

6. Isulat ang pangunahing paulit-ulit na dynamic programming equation, na nagpapahayag ng conditional optimal gain sa pamamagitan ng isang kilala nang function

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

7. Gumawa kondisyonal na pag-optimize ang huling hakbang, na gumagawa ng iba't ibang mga pagpapalagay tungkol sa kung paano natapos ang penultimate na hakbang, at para sa bawat isa sa mga pagpapalagay na ito, hanapin ang kondisyon (pinili batay sa kondisyon na ang hakbang ay natapos sa isang bagay) na pinakamainam na kontrol sa huling hakbang.

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

8. Magsagawa ng conditional optimization, simula sa penultimate step at nagtatapos sa unang hakbang (backing back).

9. Gumawa walang kondisyong pag-optimize kontrol, "pagbabasa" ng kaukulang mga rekomendasyon sa bawat hakbang: kunin ang nahanap na pinakamainam na kontrol sa unang hakbang at baguhin ang estado ng system, para sa nahanap na estado mahanap ang pinakamainam na kontrol sa pangalawang hakbang, atbp. hanggang sa huling hakbang.

PRINSIPYO NG OPTIMALIDAD. Anuman ang estado ng system bago ang susunod na hakbang, kinakailangang pumili ng kontrol sa hakbang na ito upang ang pakinabang sa hakbang na ito kasama ang pinakamainam na pakinabang sa lahat ng kasunod na hakbang ay pinakamataas.

Ang prinsipyo ng dynamic na programming ay hindi nagpapahiwatig na ang bawat hakbang ay na-optimize nang hiwalay, nang hiwalay sa iba. Ano ang punto ng pagpili ng isang kontrol na ang pagiging epektibo ay pinakamataas sa isang partikular na hakbang, kung ang hakbang na ito ay mag-aalis sa atin ng pagkakataong manalo nang maayos sa mga susunod na hakbang?

Sa pagsasagawa, may mga kaso kapag ang isang operasyon ay kailangang planuhin para sa isang walang katiyakang mahabang panahon. Ang modelo para sa naturang kaso ay isang walang katapusang hakbang na kinokontrol na proseso, kung saan ang lahat ng mga hakbang ay pantay. Dito ang panalong function at ang state change function ay hindi nakadepende sa step number.

Seksyon V. PAGMOMODEL NG SIMULASYON

Ang manwal na ito ay inilaan para sa mga mag-aaral na kumukuha ng mga kurso sa discrete mathematics at/o graph theory. Sa tulong nito ay makabisado mo ang paksang "Maximum flow at minimum cut sa network." Direkta mula sa manwal na ito, maaari mong kalkulahin ang iyong ID, kahit na wala kang MATLAB sa iyong computer. Kung mayroon kang MATLAB, pumunta sa pahinang ito: doon mayroon kang pagkakataong makialam sa script ng pagkalkula (program). Dito, ang problema ng maximum na daloy sa network ay nalutas sa pamamagitan ng pagbabawas nito sa isang linear programming problem.

Ipakilala natin ang sumusunod na notasyon:

• n=|V| − laki ng graph (bilang ng mga vertices);
• m=|E| − graph cardinality (bilang ng mga gilid);
• A − incidence matrix ng isang network digraph ng laki n× m; bawat elemento nito isang ik=1 kung mula sa i-lumabas ang tuktok k-i arc; isang ik=−1, kung sa i pumapasok ang th vertex k-i arc; At isang ik=0 sa ibang mga kaso; sa bawat haligi ng naturang matrix ay may eksaktong isa, isang minus one, at ang natitira ay mga zero;
• s− numero ng source vertex ng network; mga arko lamang ang dapat lumabas mula sa tuktok na ito, at anumang iba pang tuktok ay dapat maabot mula sa pinagmulan;
• t− numero ng sink node ng network; ang mga arko lamang ang dapat pumasok sa vertex na ito, at ang isang drain ay dapat maabot mula sa anumang iba pang vertex;
• a s − s A ; ito ay dapat maglaman lamang ng ilan, dahil mga arko lamang ang dapat lumabas mula sa pinagmulan;
• a t − t-ika-row ng incidence matrix ng network digraph A ; dapat ay naglalaman lamang ito ng mga minus, dahil ang mga arko lamang ang dapat pumasok sa alisan ng tubig;
• A st− incidence matrix ng network digraph A kasama ang mga itinapon dito s ika at t ika linya;
• e − column vector ng haba m; sa bawat elemento nito e k ang magiging magnitude ng daloy sa k ika-arko;
• c − column vector ng haba m; sa bawat elemento nito c k Itinatakda ng ≥0 ang throughput k ika-arko.

Kung gayon ang pinakamataas na problema sa daloy ng network ay maaaring mabuo bilang isang linear na problema sa programming:

Ang kabuuang daloy na umaalis sa pinagmulan (1) ay na-maximize. Bukod dito, sa anumang intermediate vertex ang papasok na daloy ay katumbas ng papalabas na daloy (2), at ang kapasidad ng mga arko ay limitado (3).

Ang dalawahang problema hanggang sa maximum na problema sa daloy ay ang problema sa minimum na hiwa. Upang makabuo ng isang minimal na hiwa, maaari mong gamitin ang duality theorems. Kailangang:

• alisin ang lahat ng walang laman sa digraph ng network ( e k= 0) at puspos ( e k = c k) mga arko;
• hanapin ang mga konektadong bahagi ng natitirang graph;
• kung mayroong dalawang tulad na mga bahagi, kung gayon ang mga itinapon na arko ay nagbibigay ng kaunting hiwa;
• kung higit sa dalawang konektadong bahagi ang lilitaw, kung gayon ang network digraph ay may ilang kaunting mga pagbawas (ang kaukulang problema sa linear programming ay bumababa).

Para sa isang lumalalang problema, ang unang minimal na hiwa na pinakamalapit sa pinagmulan ay itinayo sa pahinang ito.

Upang magamit nang tama ang page na ito, dapat na suportahan ng iyong browser ang mga script Java Script. I-on ang mga ito.

Ilagay ang paunang data sa mga lugar ng pag-input sa ibaba. Sa unang lugar, kailangan mo (mas tiyak, maaari mong) ipasok ang mga coordinate ng vertices upang gumuhit ng isang digraph ng network. Ang mga ito ay tinukoy sa anyo ng isang matrix n×2: sa unang hanay − x ika-coordinate, sa pangalawang − y-e. Maaaring tukuyin ang mga numero bilang mga integer, na may decimal point, o sa exponential form. Paghiwalayin ang mga numero na may mga puwang. Kabuuan Tinutukoy ng mga linya sa lugar ng pag-input na ito ang laki ng digraph n− bilang ng mga vertex. Ang mga paunang data na ito (vertex coordinates) ay opsyonal: kung hindi tinukoy ang mga ito, ang network digraph ay iguguhit bilang isang tama n-gon, at ang bilang ng mga vertex ay matutukoy ng pinakamataas na numero ng vertex sa susunod na lugar ng pag-input.

Sa susunod na lugar ng pag-input kaliwang bahagi− kinakailangang punan. Tinutukoy nito ang istraktura ng network digraph. Ang bawat arko sa isang digraph ay nag-uugnay sa dalawang vertice. Ang mga numero ng mga vertex na ito ay tinukoy sa anyo ng isang matrix m×2 sa kaliwang bahagi ng pangalawang lugar ng pag-input. Sa bawat linya, ang 1st vertex (buntot, pinagmulan) ng arc ay unang tinukoy, at pagkatapos, sa pamamagitan ng isang espasyo, ang 2nd vertex (tip, drain) ng arc ay tinukoy. Dapat ay mayroon ang mga column na ito mga integer mula 1 hanggang n kasama. Paghiwalayin ang mga numero na may mga puwang. Sa kanang bahagi, ang mga kapasidad ng mga arko ay tinukoy - mga positibong tunay na numero. Kung hindi tinukoy ang column na ito, ang lahat ng kapasidad ay ituturing na pareho (isa). Tinutukoy ng kabuuang bilang ng mga numero sa bawat isa sa mga column na ito ang cardinality ng digraph m− bilang ng mga arko.

Hayaang magbigay ng nakadirekta na graph G= , kung saan ang direksyon ng bawat arko vÎV ay nangangahulugan ng direksyon ng daloy (halimbawa, ang daloy ng mga sasakyan), ang kapasidad ng bawat arko ay katumbas ng d(v). Sa maraming mga taluktok E dalawang vertex ang naka-highlight t At s. Vertex t ang pinagmulan ng daloy, s- alisan ng tubig. Ito ay kinakailangan upang matukoy ang pinakamataas na daloy na maaaring maipasa mula sa tuktok t V s .

Ipahiwatig natin sa pamamagitan ng x(v) ang dami ng daloy na gumagalaw sa isang arko v. Obvious naman yun

0 £ x(v) £ d(v) , vÎV . (6. 1)

Sa bawat rurok iÎE\(t,s) ang dami ng papasok na daloy ay katumbas ng dami ng papalabas na daloy, i.e. ang pagkakapantay-pantay ay totoo

(x(v)|i О V + (i))= (x(v)| iО V - (i))

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

Para sa tuktok t

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

para sa vertex s

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

Magnitude Q ay ang magnitude ng daloy na umaalis sa vertex t at pumasok sa tuktok s.

Kailangang matukoy

Q ® max(6.5)

sa ilalim ng mga paghihigpit (6.1-6.4).

Dami Q, x(v), vÎV, kasiya-siyang mga paghihigpit (6.1-6.4) tatawag tayo ng daloy sa network, at kung ma-maximize nila ang halaga Q, pagkatapos ay ang maximum na daloy. Ito ay madaling makita na ang mga halaga Q=0, x(v)=0, vÎV, ay isang daloy sa network.

Ang Problema (6.1-6.5) ay isang linear programming problem at maaaring lutasin gamit ang simplex method algorithm.

Hatiin natin ang hanay ng mga vertices E sa dalawang magkahiwalay na bahagi E1 at E2 sa paraang tÎE1, sÎE2. Sa pamamagitan ng hiwa V(E1,E2), naghihiwalay t At s tatawagin natin ang set V(E1,E2)ÌV na para sa bawat arko v О V(E1,E2) o h1(v)ОE1 At h2(v)ОE2, o h1(v)ОE2 At h2(v)ОE1.

Hatiin natin ang set V(E1,E2) sa dalawang bahagi V(E1,E2+),V(E1,E2,-) sa sumusunod na paraan:

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

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

Tatawagin natin ang throughput capacity ng cut

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

Ang sumusunod ay totoo

Teorama 1. (Tungkol sa maximum flow at minimum cut).

Sa anumang network, ang maximum na daloy mula sa pinagmulan ay t sa stock s katumbas ng pinakamababang throughput Q(E1,E2) sa lahat ng mga hiwa V(E1,E2), na naghihiwalay sa mga vertex t At s.

Tandaan na sa pinakamataas na daloy

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

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

Hayaan Q, x(v), vÎV, - ilang daloy ng network, pagkakasunud-sunod

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

ay isang kadena na nagdudugtong sa mga vertex t At s. Itakda natin sa chain na ito ang direksyon ng paggalaw mula sa vertex t Upang s. Arc v(j) mula sa kadena na ito ay tinatawag na isang tuwid na linya kung ang direksyon nito ay tumutugma sa direksyon ng paggalaw mula sa t Upang s, at ang reverse kung hindi man. Tatawagin nating landas ang kadena na ito pagtaas ng daloy, kung para sa mga tuwid na arko v mga tanikala x(v)< d(v) at para sa kabaligtaran x(v) > 0. Ang isang karagdagang daloy ay maaaring maipasa sa circuit na ito q mula sa t Upang s laki q = min (q1,q2), saan q1=min (d(v) -x(v)), ang minimum ay kinuha sa lahat ng tuwid na arko ng chain, q1=min (x(v)), ang minimum ay kinukuha sa lahat ng reverse arc ng chain.

Teorama 2.

Daloy Q, x(v) , vÎV, ay maximum kung at tanging kung walang paraan upang mapataas ang daloy.

Ang iminungkahing algorithm para sa paglutas ng problema ng maximum na daloy sa isang network ay batay sa paghahanap ng paraan upang mapataas ang daloy mula sa t V s, na nakabatay naman sa proseso ng pag-aayos ng mga vertex label. Sabihin na natin

kaitaasan i minarkahan ng marka q(i)>0, at kilala rin ang straight arc arc v(i), kung saan dumating ang daloy na ito, o minarkahan ng , kung ilang karagdagang daloy ng magnitude q(i)>0, at kilala rin ang reverse arc v(i), kung saan pumasok ang daloy na ito;

ang vertex i ay tinitingnan kung ang lahat ng mga kalapit na vertex nito ay minarkahan.

Kung minarkahan ang vertex s, may nakitang landas na magpapalaki ng daloy ayon sa magnitude q, na dinadaanan sa landas na ito. Upang ilarawan ang algorithm kailangan din namin ng isang array SPW, na naglalaman ng mga bilang ng mga minarkahang vertice sa pagkakasunud-sunod kung saan sila minarkahan. C1- numero sa array SPW tiningnan ang tuktok, C2- ang bilang ng huling minarkahang vertex sa array na ito.

Ang ideya ng algorithm na ito ay upang makahanap ng mga end-to-end na landas na may positibong daloy mula sa pinagmulan hanggang sa lababo.

Isaalang-alang ang isang gilid (i, j) na may (paunang) kapasidad. Sa panahon ng pagpapatupad ng algorithm, ang mga bahagi ng kapasidad na ito ay "tinatanggal" ng mga daloy na dumadaan sa isang naibigay na gilid, bilang isang resulta, ang bawat gilid ay magkakaroon ng natitirang kapasidad. Sumulat - Natitirang Bandwidth. Ang isang network kung saan ang lahat ng mga gilid ay may natitirang kapasidad ay tatawaging tira.

Para sa isang arbitrary na node j na tumatanggap ng daloy mula sa node i, tinukoy namin ang isang label, kung saan ang halaga ng daloy na dumadaloy mula sa node j hanggang sa node i. Upang mahanap ang maximum na daloy, ginagawa namin ang mga sumusunod na hakbang.

Para sa lahat ng mga gilid, itinakda namin ang natitirang kapasidad na katumbas ng paunang kapasidad, i.e. equate natin =. Italaga at markahan natin ang node 1 ng label. Ipinapalagay namin na i=1.

Ang hanay ng mga node j kung saan maaari kang pumunta mula sa node I kasama ang isang gilid na may positibong natitirang kapasidad >0 para sa lahat ng j. Kung, isinasagawa namin ang yugto 3, kung hindi man ay pupunta kami sa 4.

Sa nakita namin node k tulad na. Ilagay natin at markahan ang node k na may label. Kung k=n, may makikitang end-to-end na path at pupunta tayo sa stage 5, kung hindi, itatakda natin ang i=k at bumalik sa stage 2.

Rollback. Kung i=1, walang end-to-end na landas ang posible, at pumunta sa 6. Kung, makikita natin ang may label na node r kaagad na nauuna sa node i at alisin ito mula sa hanay ng mga node na katabi ng node r. Itinakda namin ang i=r at bumalik sa stage 2.

Kahulugan ng isang natitirang network. Tukuyin natin sa pamamagitan ng hanay ng mga node kung saan natagpuan ng p_th ang end-to-end na landas mula sa source node (node ​​1) hanggang sa sink node (node ​​​​n) pagkatapos ay dumaan ang maximum na daloy sa landas na ito

Ang natitirang kapasidad ng mga gilid na bumubuo sa end-to-end na landas ay bumababa ng isang halaga sa direksyon ng daloy at tumataas ng parehong halaga sa kabaligtaran na direksyon.

yun. para sa isang gilid (i, j) na kasama sa isang end-to-end na landas, nagbabago ang kasalukuyang mga natitirang kapasidad:

1) kung ang daloy ay napupunta mula sa node i hanggang j,

2) kung ang daloy ay napupunta mula sa node j hanggang sa i.

a) na may m nahanap na mga end-to-end na landas, ang maximum na daloy ay ipinahayag ng

b) Ang pagkakaroon ng mga halaga ng paunang at panghuling mga kapasidad ng gilid (i, j), maaari naming kalkulahin ang pinakamainam na daloy sa gilid na ito tulad ng sumusunod. Ilagay natin. Kung >0, ang daloy na dumadaan sa gilid (i, j) ay pantay. Kung >0, pantay ang daloy. (ang kaso kapag ang parehong >0 at >0 ay imposible).

Halimbawa 1. Hanapin ang pinakamataas na daloy sa network Fig. 1

Pag-ulit 1. =

3) k=3, dahil. Nagtatalaga kami at minarkahan ang node 3 na may label. i=3 at bumalik sa 2)

5) k=5 at. Minarkahan namin ang node 5 na may label. Kumuha kami ng isang through path.

6) tinutukoy namin ang end-to-end na path sa pamamagitan ng mga label, simula sa node 5 at nagtatapos sa node 1: . At. Kinakalkula namin ang mga natitirang kapasidad sa landas:

Pag-ulit 2.

1) at markahan ang node 1 na may label. i=1

2") (kaya hindi kasama ang node 5 sa

3") k=4, at markahan ang node 4 na may label. i=4 at bumalik sa 2)

2""") (dahil ang mga node 1 at 3 ay minarkahan, hindi sila kasama sa)

3""") k=5 at. Minarkahan namin ng label ang node 5. May nakuhang end-to-end path. Pumunta sa 5)

Pag-ulit 3.

1) at markahan ang node 1 na may label. i=1

3) k=2, at markahan ang node 2 na may label. i=2 at bumalik sa 2)

3") k=3 at. Markahan ang node 3 ng label. i=3 at bumalik sa 2)

2") (mula) pumunta sa 4)

4) ang label ng node 3 ay nagpapakita ng bilang ng nakaraang node. Sa pag-ulit na ito, ang node 3 ay hindi isinasaalang-alang sa hinaharap; at bumalik sa 2)

2""") (dahil ang node 3 ay inalis mula sa posibleng end-to-end path)

3""") at. Minarkahan namin ng label ang node 5. May nakuhang end-to-end path. Pumunta sa 5)

5) i. Kinakalkula namin ang mga natitirang kapasidad sa landas:

Pag-ulit 4. Sa pag-ulit na ito, ang landas na may

Pag-ulit 5. Sa pag-ulit na ito, ang landas na may

Pag-ulit 6: Walang posibleng mga bagong end-to-end na path dahil ang lahat ng mga gilid na nagmula sa node 1 ay may zero na natitirang kapasidad. Pumunta sa 6) upang matukoy ang solusyon

6) ang maximum na dami ng daloy sa network ay katumbas ng mga yunit.

Ang mga halaga ng daloy sa iba't ibang mga gilid ay kinakalkula sa pamamagitan ng pagbabawas ng pinakabagong mga natitirang halaga ng kapasidad mula sa mga paunang halaga ng kapasidad.

Mga resulta ng pagkalkula: talahanayan. 1

Graphical sequential execution ng algorithm para sa paghahanap ng maximum flow (halimbawa 1)

e) f) Walang mga through path

kanin.

Paunang data sa sistema ng transportasyon, halimbawa, in-plant, na ipinapakita sa Fig. 2, ay maaari ding tukuyin ng isang talahanayan (Talahanayan 2).

Talahanayan 2. Paunang data para sa maximum na problema sa daloy

Malinaw, ang maximum na kapasidad ng sistema ng transportasyon ay hindi lalampas sa 6, dahil hindi hihigit sa 6 na yunit ng kargamento ang maaaring ipadala mula sa panimulang punto 0, ibig sabihin, 2 mga yunit sa punto 1, 3 mga yunit sa punto 2 at 1 yunit sa punto 3 . Susunod, kinakailangan upang matiyak na ang lahat ng 6 na yunit ng kargamento na umaalis sa punto 0 ay umabot sa huling punto 4. Malinaw, ang 2 yunit ng kargamento na dumating sa punto 1 ay maaaring direktang ipadala sa punto 4. Ang kargamento na dumating sa punto 2 ay kailangang hatiin: 2 unit ay agad na ipinadala sa point 4, at 1 unit - sa intermediate point 3 (dahil sa limitadong kapasidad ng seksyon sa pagitan ng mga puntos 2 at 4). Ang sumusunod na kargamento ay naihatid sa punto 3: 1 yunit mula sa punto 0 at 1 yunit mula sa punto 3. Ipinapadala namin sila sa punto 4. Kaya, ang pinakamataas na throughput ng sistema ng transportasyon na pinag-uusapan ay 6 na yunit ng kargamento. Sa kasong ito, ang mga panloob na seksyon (mga sanga) sa pagitan ng mga punto 1 at 2, pati na rin sa pagitan ng mga punto 1 at 3, ay hindi ginagamit isang throughput ng 3 unit. Ang solusyon ay maaaring iharap sa anyo ng isang talahanayan (Talahanayan 3)

Talahanayan 3. Paglutas ng maximum na problema sa daloy

Problema sa linear programming para sa pag-maximize ng daloy. Bumalangkas tayo ng pinakamataas na problema sa daloy sa mga tuntunin ng linear programming. Hayaang X KM ang dami ng transportasyon mula sa punto K hanggang sa punto M. Ayon sa Fig. 2 K = 0,1,2,3, M = 1,2,3,4, at ang transportasyon ay posible lamang sa puntong may mas mataas na numero. Nangangahulugan ito na mayroong kabuuang 9 na variable X KM, ibig sabihin, X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Ang problema sa linear programming na naglalayong i-maximize ang Ang daloy ay may anyo:

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

Dito ang F ay ang layunin na pag-andar, ang kondisyon (0) ay naglalarawan sa pagpasok ng mga kalakal sa sistema ng transportasyon. Ang mga kundisyon (1) - (3) ay nagtakda ng mga relasyon sa balanse para sa mga node 1-3 ng system. Sa madaling salita, para sa bawat panloob na node, ang papasok na daloy ng mga kalakal ay katumbas ng papalabas na daloy ng mga kalakal sa loob ng sistema at hindi "ipinanganak" dito. Ang kondisyon (4) ay ang kondisyon para sa "paglabas" ng mga load mula sa system. Kasama ng kundisyon (0), ito ay bumubuo ng balanseng relasyon para sa sistema sa kabuuan ("input" ay katumbas ng "output"). Ang sumusunod na siyam na hindi pagkakapantay-pantay ay nagtakda ng mga paghihigpit sa kapasidad ng mga indibidwal na "sangay" ng sistema ng transportasyon. Pagkatapos ay ipinahiwatig ang hindi negatibong dami ng trapiko at ang layunin na pag-andar. Malinaw na ang huling hindi pagkakapantay-pantay ay sumusunod mula sa anyo ng layunin ng function (relasyon (0) o (4)) at ang hindi negatibong dami ng trapiko. Gayunpaman, ang huling hindi pagkakapantay-pantay ay nagdadala ng ilan Pangkalahatang Impormasyon- alinman sa isang positibong dami ng kargamento ay maaaring maipasa sa system, o zero (halimbawa, kung ang paggalaw ay nangyayari sa isang bilog sa loob ng system), ngunit hindi negatibo (hindi ito makatuwiran sa ekonomiya, ngunit pormal matematikal na modelo"hindi alam" tungkol dito).

Sum of flows through arcs incident v, ay katumbas ng kabuuan ng mga daloy sa pamamagitan ng insidente ng arko w; ang kabuuan na ito ay tinatawag na halaga ng flux. Pangunahing magiging interesado tayo sa mga daloy na may pinakamalaking posibleng halaga - ang tinatawag na pinakamataas na daloy. SA pangkalahatang kaso ang isang network ay maaaring magkaroon ng maraming iba't ibang mga maximum na daloy, ngunit ang kanilang mga halaga ay dapat na pareho. (4)

Ang pag-aaral ng pinakamataas na daloy sa pamamagitan ng isang network N = (V,D,a) ay malapit na nauugnay sa konsepto ng isang hiwa, i.e. tulad ng isang set A ng mga arko ng isang digraph D na may ari-arian na anumang simpleng chain ng v V dumadaan sa arko na kabilang sa A. Ang kapasidad ng isang hiwa ay ang kabuuan ng mga kapasidad ng mga arko na kabilang dito. Ang mga pagbawas na may pinakamaliit na posibleng throughput ay tinatawag na minimal cut.

Ang magnitude ng anumang daloy ay hindi lalampas sa throughput capacity ng anumang hiwa, at, samakatuwid, ang magnitude ng anumang maximum na daloy ay hindi lalampas sa throughput ng anumang minimum na hiwa. Gayunpaman, hindi agad malinaw na ang dalawa huling mga numero laging pantay sa isa't isa; Ang resultang ito ay nakuha ng mga Amerikanong mathematician na sina Ford at Fulkerson noong 1955 at tinawag na maximum flow at minimum cut theorem.

Theorem (tungkol sa maximum flow at minimum cut). Sa anumang network, ang laki ng anumang maximum na daloy ay katumbas ng kapasidad ng anumang minimum na hiwa.

Ang maximum flow at minimum cut theorem ay nagbibigay-daan sa iyo upang suriin kung ang isang naibigay na daloy ay maximum o hindi, ngunit para lamang sa medyo simpleng mga network. Siyempre, sa pagsasanay kailangan nating harapin ang malaki at kumplikadong mga network, at sa pangkalahatan ay mahirap hanapin ang maximum na daloy sa pamamagitan ng simpleng pagpili. Ilarawan natin ang isang algorithm para sa paghahanap ng maximum na daloy sa anumang network na may integer throughput.

Hakbang 1. Una, pipili kami ng isang daloy na may hindi zero na halaga (kung may ganoong daloy). Halimbawa, kung ang N ay ang network na ipinapakita sa Fig. 29.3, pagkatapos ay ang daloy na ipinapakita sa Fig. 29.4. Kapansin-pansin na mas malaki ang halaga ng paunang daloy na aming pinili, mas madali ang mga susunod na hakbang.

Hakbang 2. Batay sa N, bumuo kami ng bagong network na N’ sa pamamagitan ng pagbabago ng direksyon ng daloy sa kabaligtaran. Mas tiyak, anumang arko a kung saan ang (a) = 0 ay nananatili sa N' kasama ang orihinal na kapasidad nito, at anumang arko a kung saan , ay pinapalitan ng isang arko a na may kapasidad at isang kabaligtaran na arko na may kapasidad (a). Ang Network N' sa aming halimbawa ay ipinapakita sa Fig. 29.5. Vertex v ay hindi na pinagmumulan, kundi isang lababo.

Hakbang 3. Kung sa network N’ makakahanap tayo ng non-zero flow mula sa v c, pagkatapos ay maaari itong idagdag sa orihinal na daloy at makakuha ng bagong daloy ng mas malaking halaga sa N. Ngayon ay maaari mong ulitin ang hakbang 2, gamit ang bagong thread na N' sa halip na N' kapag gumagawa ng network. Sa pamamagitan ng pag-uulit ng pamamaraang ito, sa kalaunan ay makakarating tayo sa isang network na N' na naglalaman ng walang mga di-zero na daloy; kung gayon ang katumbas na daloy ay ang pinakamataas na daloy. Halimbawa, sa Fig. 29.5 mayroong isang di-zero na daloy kung saan ang daloy sa pamamagitan ng mga arko ( v,u), (u,z), (z,x), (x,y) At ( y,) ay katumbas ng isa, at ang mga flux sa mga natitirang arko ay katumbas ng zero. Ang pagdaragdag ng daloy na ito sa daloy sa Fig. 29.4, nakuha namin ang daloy na ipinapakita sa Fig. 29.6; inuulit ang hakbang 2, madaling ipakita na ito ang pinakamataas na daloy.

Mga Ginamit na Aklat:

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

(2) Asanov M.O., Baransky V.A., Rasin V.V. Discrete mathematics: mga matroid graph, algorithm

(3) Basaker R., Saati T. May hangganang mga graph at network.

(4) Wilson R. Panimula sa Teoryang Graph