home Other disciplines books Ically mathematical programuvannya - Nakonechny S.І.

Ically mathematical programuvannya - Nakonechny S.І.

5.9.2. potentsіalіv method for MEREZHI

Rozglyanemo without bringing rozv'yazuvannya transportnoї zadachі on MEREZHI potentsіalіv method. Zobrazimo task at viglyadі MEREZHI (Figure 5.2.)., De kozhnіy duzі on figures from a mug poznachenі vartostі transported odinitsі produktsії; for sproschennya vvazhatimemo tsі vartostі odnakovimi in oboh napryamkah ribs, and ribs propusknі zdatnostі neobmezhenimi zverhu. Zauvazhimo scho .

Paragraph vіdpravlennya i stocks in their poznachimo vіdpovіdnimi digits (scho dorіvnyuyut reserves) іz "plus" sign, and the point of delivery - the figures scho dorіvnyuyut require іz sign "mіnus" (stand at the bow).

In Persha etapі skladaєmo Pochatkova transported plan: eg vantazhopotokіv pokazuєmo strіlkami and Quantity vantazhіv - numbers above (pid) vіdpovіdnoyu strіlkoyu.

Fig. 5.3

Yak can be seen in Fig s. 5.3 Pochatkova plan utvoryuyut zmіnnі:

.

.

Yakscho sіt mіstit m peaks, the system (5.42) skladaєtsya h m rіvnyan and її Rank Got dorіvnyuvati . In Nashomu prikladі plan mіstit rіvno vіdmіnnih od scratch the basal zmіnnih, otzhe, vіn nevirodzheny.

Skoristaєmosya without bringing theorem [28]: for dwellers deyaka Chastina Count vіdpovіdala zmіnnim zadachі of basis (5.42) - (5.44) neobhіdno i dostatno, dwellers Won bula tree.

In Nashomu prikladі Pochatkova plan does not utvoryuє konturіv, tobto vіdpovіdaє mnozhinі the basal zmіnnih, otzhe, Je support program zadachі.

On the other etapі for kozhnoї top of viznachaєmo potentsіal. Purshia potentsіal vibiraєmo dovіlno, naychastіshe s Pevnyi mіrkuvan zruchnostі in the on obchislennyah pov'yazuєmo yogo s dovіlnoyu top, napriklad, Perche. Potentsіali іnshih tops viznachaєmo, vihodyachi s Persha potentsіalu and the Same: potentsіali vertices z'єdnanih arcs s Perche, Perche prirіvnyuєmo to rіznitsі potentsіalu i od pershoї vartostі transported to the top of zadanoї, Yakscho Vantage іde in tsomu napryamі, i, vіdpovіdno, sumі potentsіalu pershoї vertices i vartostі transported susіdnoї s vertices in the Perche, in tsomu Yakscho sama napryamі carried Vantage. Otzhe, potentsіali vsіh tops rozglyaduvanoї MEREZHI viznachatsya such figures:

;

;

;

.

Tretіy Etap polyagaє in perevіrtsі plan for optimalnіst, and vikoristovuєtsya zvichayna Find our optimalnostі plan transportnoї zadachі, yak formulyuєtsya in termіnah i poznachennyah transportnoї zadachі on MEREZHI. For ribs MEREZHI, vіlnih od transported, for tobto , Nevіd'єmna rіznitsya potentsіalіv vertices SSMSC їh obmezhuyut (stand їh kіntsyah) Got Buti Mensch od vіdpovіdnoї vartostі carried abo dorіvnyuvati їy. Skladaєmo vіdpovіdnі spіvvіdnoshennya:

;

;

;

;

.

For the basic ribs vіdpovіdnі rіznitsі exactly dorіvnyuyut vartostyam transported scho Yea odnієyu s minds optimalnostі plan transportnoї zadachі. Otzhe, Umov optimalnostі Porush deprivation once on rebrі (4, 3). Yakscho such torn down bіlshe nіzh odne, the edge vibiraєmo s naybіlshim torn down. Utvorimo s cycle of basis ribs i nonbasic edges (4, 3), scho pass through the vertices (4, 3, 1, 5, 6, 2, 4). Eg bypass zbіgaєtsya s direct flow yaky planuєtsya carry on lantsі (4, 3) - 4 od top of it to the top 3, oskіlki maєmo nerіvnіst . Otzhe, necessary to cycle proti Ruhu strіlki godinnika. Obmezhennya (5.42) will not be porushenі, Yakscho mi, vibrat in tsomu tsiklі naymenshy zustrіchny potіk in lantsі (2; 6), vіdnіmatimemo yogo value od zustrіchnih potokіv Lanka in cycle i dodavatimemo to potokіv eg yakih s zbіgayutsya directly bypass. Todі Lanka (2; 6) staє vіlnoyu od flow and Lanka (4, 3) - basic (Figure 5.4).

Fig. 5.4

Perevіrimo plan optimalnіst. For tsogo viznachimo nova potentsіalіv system vipravivshi poperednyu:

.

Perevіrku slіd zrobiti deprivation for quiet vіlnih ribs for yakih Hoca used in odnіy s tops zmіnilosya potentsіalu values ​​and the Same - for (1, 2), (2, 6):

;

.

Otzhe, OOO All minds optimalnostі zadovolnyayutsya i optimal plan znaydeno:

.

Zauvazhimo, scho at rozv'yazuvannі navedenoї sіtovoї zadachі method potentsіalіv mozhut traplyatisya vipadki virodzhennya. Find our virodzhennya Je plan scho skladaєtsya s dvoh abo bіlshe okremih wooden ribs of basis, not z'єdnanih mіzh him. For tsogo usunennya want to enter into the basis vіlnu Lanka, yak b z'єdnuvala oznachenі the basal tree lanok mіzh him.

Otzhe, by potentsіalіv rozv'yazano sіtovu transportation problem s promіzhnimi paragraphs i zaboronami transported to mіzh deyakimi points tobto vіdsutnіstyu in MEREZHI vіdpovіdnih ribs (shlyahіv). Mi vvazhali scho propusknі zdatnostі ribs neobmezhenі zverhu, what zaznacheny algorithm pridatny deprivation in addition razі, if found for the optimal plan is not carried perevischuyut throughput zdatnostey real lanok transportnoї MEREZHI, ale stink zavzhdi obmezhenі zverhu.

In lіteraturі [28], we can know detalnіshy Opis rozv'yazannya sіtovih transport problems.