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

Ically mathematical programuvannya - Nakonechny S.І.

5.5.5. Ugorsky method rozv'yazuvannya transportnoї zadachі

Іdeya tsogo method rozv'yazannya transportnoї zadachі Vpershe Bula zaproponovana ugorskim mathematician Je Egervarі 1931 roku, tobto slit to rozroblennya zagalnoї teorії lіnіynogo programuvannya. Spochatku Tsei method LUVs rozrobleny for rozv'yazuvannya spetsifіchnogo mind transportnoї zadachі and Zgoda uzagalneny. Ninі ugorsky method Yea one s nayposhirenіshih metodіv rozv'yazannya transport problems.

Vіn dosit Just Look obchislen s i Mauger zastosovuvatisya without uperedzhen navіt in razі virodzhenostі plan.

Іdeya method polyagaє in zdіysnennі poslіdovnogo transition od deyakogo unacceptable plan (not require OAO All zadovolenі i not all Produkciya vivaise) to an acceptable scho Yea rozv'yazkom zadachі. Tsey perehіd zdіysnyuєtsya for skіnchennu Quantity іteratsіy (Ale nevіdomu to kіntsya obchislen), scho s pov'yazanі peretvorennyami matritsі vartostey i-line plan .

Nazvemo umovno-optimal plans (pseudoprogram) transportnoї zadachі (5.1) - (5.4) Taku sukupnіst nevіd'єmnih numbers , Yak zadovolnyaє tasks nerіvnostey system:

(5.27)

(5.28)

i takі nastupnі minds for zmіnnih dvoїstoї zadachі - potentsіalіv:

, Yakscho ;

, Yakscho .

Mіroyu nedopustimostі (minds neoptimalnostі) umovno-optimal plan Mauger Buti nayavnіst rіznitsі mіzh sumoyu vsіh zapasіv (chi require those scho SAME) i sumoyu vsіh transported umovno-optimal plan tobto:

(5.29)

Zrozumіlo scho denote the D nev'yazka Mensch, Tim blizhche umovno-optimal plan to naykraschogo plan transportnoї zadachі, while razі, if D = 0, vіn zbіgaєtsya s optimal plan.

Zvіdsi easily zbagnuti іdeyu rozglyaduvanogo method rozv'yazuvannya transportnoї zadachі: pochinayuchi s deyakogo Pochatkova zadachі plan podvіynoї to transportnoї You can know poslіdovnіst optimally planіv dopomіzhnih number of tasks on mіnіmіzatsіyu (5.29) for obmezhen (5.27) i (5.28), the following plan of skin yakoї nadaє nev'yaztsі (5.29) smaller values ​​in zіstavlennі s poperednіm and ostannіy plan tsієї poslіdovnostі nadaє Neuve ' yaztsі nulovogo value zbіgayuchis have Taqiy sposіb s optimal plan transportnoї zadachі.

Otzhe, cutaneous іteratsіya method oznachatime rozv'yazuvannya dopomіzhnoї zadachі (5.27) - (5.28) i zmenshennya at tsomu values ​​tsіlovoї funktsії (5.29) porіvnyano s poperednіm rozv'yazkom tsієї zadachі.

Dwellers sformulyuvati dopomіzhnu task requires krіm vikoristannya values i Scho їh mіstit given transportation problem, pobuduvati slit deyaky plan dvoїstoї zadachі . . For cob pershoї іteratsії tse easily zrobiti, uzyavshi, napriklad:

. (5.30)

And Danian plan zadovolnyaє minds:

+ (5.31)

and takozh in cutaneous row matritsі transported unaslіdok such Vibor potentsіalіv vikonuvatimetsya Hoca used one rіvnіst form (5.31). Spravdі, taking to th row in pravіy chastinі (5.31) , Dіstanemo:

.

In the following іteratsіyah utvorenu system potentsіalіv zmіnyuєmo, ale so scho Won zavzhdi zalishaєtsya up podvіynoї zadachі.

Navedenі vische obmezhennya for zmіnnih dvoїstoї zadachі:

, Yakscho ;

, Yakscho

oznachayut scho klіtini in yakih for viznachenoї on the k-th krotsі Sistemi potentsіalіv vikonuєtsya strict nerіvnіst Not zapovnyuyut. Otzhe, rozv'yazuyuchi problem, we vikoristovuvati deprivation Ti klіtini for yakih .

Zauvazhimo scho mіnіmіzatsіya tsіlovoї funktsії (5.29) rіvnoznachna maksimіzatsії another її dodanka

(5.32)

when tіy samіy sistemі obmezhen. Zrozumіlo scho , While matimemo: .

Vihodyachi s guidance theoreticity ambushes rozglyanemo algorithm ugorskogo method:

1. Pobudova dopomіzhnoї zadachі s tsіlovoyu funktsієyu (5.32) is the minds of (5.27), (5.28).

2. Pobudova Pochatkova support plan dopomіzhnoї zadachі scho otrimana on poperednomu krotsі algorithm, one s vіdomih metodіv.

3. Vіdshukannya optimal plan dopomіzhnoї zadachі.

3.1. Zbіlshennya values . Viznachayut rows, de som transported by rows Mensch od zapasіv and Relief for them - stovptsі, SSMSC vibranomu toil in a row not to zaboronenі transported klіtini. Vibranі rows i stovptsі poznachayut as follows:

. (5.33)

that . (5.34)

Potіm . . (5.35)

3.2. Viznachennya klіtin, the value carried in yakih neobhіdno zmіniti. Poslіdovnіst Tsikh klіtin guilty utvoryuvati deyaky lantsyug, Elements yakogo Je poznachenih rows in that column for i Yakima can be transferred lishok stock deyakogo th row, scho LUVs poznacheny Perche, in -tu column poznachenu ostannoyu.
In zagalnomu vipadku poslіdovnіst Got viglyad:

.

In znaydenomu lantsyuzі poznachaєmo Perche yogo klіtinu s kіntsya "plus" and INSHI for Cherga signs "plus" i "mіnus". Znaydemo value:

. (5.36)

Yak can be seen s algorithm, dorіvnyuє menshіy s dvoh values: naymenshogo Elements lantsyuga scho poznacheny sign "mіnus" i nevikoristanogo stock in poznachenomu Perche point vіdpravlennі. value Je nezadovolenoyu required in poznachenomu naprikіntsі punktі delivery. Zsuvu on lantsyugu pіdlyagaє Mensch s Tsikh values, scho th lead to navedenoї of formulating rozrahunku q (5.36).

4. Perehіd to nastupnoї dopomіzhnoї zadachі optimally plan yakoї bude blizhchim to the optimal plan pochatkovoї transportnoї zadachі.

In kіntsevіy tablitsі rozv'yazanoї dopomіzhnoї zadachі poznachenі column toil balance sumi transported by kolontsі i require of vіdpovіdnih points. It's easy to pomіtiti scho zaboronu transported to slіd znіmati s quiet klіtin, SSMSC not nalezhat to poznachenih columns. Vodnochase in tіy samіy kіntsevіy tablitsі poperednoї dopomіzhnoї zadachі s-pomіzh poznachenih Je rows in yakih Absent balance sumi transported i zapasіv so scho Shuka klіtina mіstitimetsya Sered poznachenih ryadkіv in ostatochnіy tablitsі.

Poznachimo mnozhinu poznachenih ryadkіv through And mnozhinu poznachenih columns - by J (y kіntsevіy tablitsі scho mіstit rozv'yazok dopomіzhnoї zadachі). Znaydemo value:

(5.37)

tobto naymenshe values ​​rіznitsі scho stoїt at bow Sered zaboronenih klіtin, SSMSC mіstyatsya poznachenih in rows i nepoznachenih columns; strictly bіlshe od zero oskіlki in іnshomu razі vіdpovіdna klіtina not bula b zaboronenoyu transported to, i її speakers can Bulo Used for Relief of poznachiti poznachenogo row, Money Does nalezhit klіtina tsya, scho superechit umovі . Zrozumіlo, scho, zbіlshivshi, napriklad, potentsіal , Yaky come from the formula (5.37), the value of Tim himself peretvoryuyut vіdpovіdnu klіtinu (in yakіy ) Have to vіlnu transported. Zvichayno such klіtin scho zadovolnyayut Minds (5.26), Mauger Buti bіlshe, nіzh one. Tom poznachenih access in all rows zbіlshuєmo potentsіali on And dwellers zberegti poperednyu mnozhinu klіtin vіlnih for transported, the amount of vіdnіmaєmo od potentsіalіv poznachenih columns . Rasht potentsіalіv zalishaєmo nezmіnnoyu. Here slіd pіdkresliti scho zgіdno s algorithm rozv'yazannya dopomіzhnoї zadachі OAO All vіlnі transported to klіtini, SSMSC Je poznachenih in rows, obov'yazkovo mіstyatsya i in poznachenih columns. Otzhe, nova system potentsіalіv znahodimo, zmіnyuyuchi poperednyu for formulas:

(5.38)

Nova potentsіalіv system viznachaє nova mnozhinu klіtin, zaboronenih transported to .

. .

Viznachivshi , I znovu formulyuєmo rozv'yazuєmo dopomіzhnu task.

5. Repetition krokіv 2-4 to vіdshukannya optimal plan pochatkovoї transportnoї zadachі.

Sformulyuєmo rules rozv'yazuvannya dopomіzhnoї zadachі, odnochasno demonstruyuchi їh on vіdpovіdnomu prikladі, i dayuchi in razі vіdpovіdnі require clarification.

Rozv'yazhemo ugorskim by transport problems, the guidance in the table. 5.14:

table 5.14

Rozv'yazannya. Viznachaєmo Pochatkova potentsіalіv system pobudovi pershoї dopomіzhnoї zadachі, vikoristovuyuchi (5.23):

. .

Maєmo:

.

.

.

.

.

.

.

.

Rozrahovuєmo quantities i have zapisuєmo їh viglyadі tablitsі:

Klіtini pobudovanoї tablitsі s Some of the elements (rіznitsyami) vіdmіnnimi od zero, will be transported to zaboronenimi, denote garantuєtsya vikonannya minds stosovno potentsіalіv and klіtini s zeros mozhna vikoristati for znahodzhennya plan dopomіzhnoї zadachі.

Pobuduєmo Pochatkova plan dopomіzhnoї zadachі, napriklad, by pіvnіchno-zahіdnogo Kuta vrahovuyuchi obmezhennya, nakladenі zaboronoyu zaznachenih transported (vіdpovіdnі klіtini Table. 5.15 vidіlenі sіrim kolorom).

table 5.15

Zagalny obsyag transported for up Pochatkova Mensch 50 odinits od obsyagu vsіh zapasіv (required): .

Sprobuєmo zmіniti viznacheny plan zbіlshennya values . Tse deprivation mozhna zrobiti for rakhunok quiet ryadkіv de stock zalishivsya nevikoristanim. Otzhe, poznachimo Ti rows, de som transported by rows zgіdno s Pochatkova up Mensch od vіdpovіdnogo stock: . Poznachaєmo їh EYAD numbers. Odne s values ​​are vіdpovіdaє i poznachaєtsya symbol And other zero Yea i poznachaєtsya symbol De i - number vibranogo row. In Nashomu prikladі so bude deprivation one - the fourth row. Otzhe, i, oskіlki zero vіdpovіdatime fourth row, then maєmo: .

Vzagalі such ryadkіv Mauger Buti kіlka. For the Relief of skin poznachenogo row (in the fourth Nashomu prikladі) poznachaєmo column SSMSC poznachenomu toil in a row not to zaboronenі transported klіtini, EYAD symbols (5.31): that .

In the fourth row are not transported to zaboronenі klіtini nalezhat drugіy that tretіy columns, SSMSC poznachaєmo vіdpovіdnimi symbols: . ; that . . Poznachenі speakers (other i-thirds) vikoristovuyutsya for poznachennya slit not poznachenih ryadkіv, SSMSC toil in danіy poznachenіy kolontsі klіtini s vіdmіnnimi od zero transported ( ).

Poznachennya vіdpovіdayut umovі (5.35): . .

In Taqiy sposіb Dali poznachaєmo Purshia row numbers:

. .

and tretіy . .

table 5.16

Znovu poznachenі rows vikoristovuєmo for poznachennya of formulas (5.36) novih, not slit poznachenih columns Pokey abo not znaydetsya column scrip transported yakoї Mensch od require vіdpovіdnogo delivery point, abo processes poznachen not mozhna bude prodovzhiti. Other vipadok oznachaє scho zmіniti not mozhna plan tobto vіn optimally. In Persha razі prodovzhuєmo algorithm.

In Nashomu prikladі znaydeno column scrip transported yakoї Mensch od require vіdpovіdnogo item. Tse fourth column, yak i poznachaєmo numbers:

. .

Viznachaєmo poslіdovnіst klіtin, the value carried in yakih slіd zmіniti. Tsya poslіdovnіst Got utvoryuvati deyaky lantsyug, Elements yakogo Musial Buti poznachenih rows in that column, i can be transferred for Yakima lishok stock deyakogo th row, scho LUVs poznacheny Perche, in -tu column poznachenu ostannoyu.

In Nashomu prikladі with such a poslіdovnіstyu klіtin Je: A 4 B 2 A 1 2 A 1 4,

a .

Dali vikoristovuєmo formula:

Otzhe until transported x 42 x 14 dodaєmo i q = 40, and transported od x 12 vіdnіmaєmo qiu the value itself. Matimemo Table. 5.17:

table 5.17

Povtoryuyuchi processes poznachen, pochinayuchi s fourth row, easily pomіtiti scho vіn zakіnchuєtsya znovu on chetvertіy kolontsі de dosyagnuta rіvnіst sumi transported require speakers. Otzhe plan dopomіzhnoї zadachі optimally.

Zauvazhimo scho optimal value lіnіynoї funktsії zadachі 40 odinits bіlshe od Pochatkova; zbіlshennya lіnіynoї funktsії zabezpechuєtsya atsiklіchnіstyu lantsyuga i bіlshoyu on odinitsyu kіlkіstyu dodatnih (poznachenih "plus") in klіtin nomu.

Pereydemo to novoї dopomіzhnoї zadachі optimally plan yakoї bude blizhchim to the optimal plan zadanoї transportnoї zadachі; tsіlova funktsіya dopomіzhnoї zadachі , Yak viznachaє zagalny obsyag transported vantazhіv at tsomu zbіlshuєtsya. For nashogo butt tsіlkom zrozumіlo scho rіvnostі (tobto Povny transported Vantage) You can Bulo b dosyagti, yakbi, napriklad, znyati s A 4 1 abo s yakoїs іnshoї klіtini pershoї zaboronu column carried on i zdіysniti transported (I = 1, 3, 4). Oskіlki zgadana zaborona loser poperednoyu system potentsіalіv Then znyati її possible, deprivation zamіnivshi poperednyu system potentsіalіv a new, with such a ale, dwellers zberіgalasya sukupnіst nezaboronenih transported to klіtin, znaydena on poperednomu etapі.

For guidance butt mnozhina klіtin (i, j), for yakih . , Such: A 1 B 1, A 1 3, A 1 4, wherein dosyagaєtsya in klіtinі A 3 1.

Znaydemo nova potentsіalіv system:

.

.

.

.

.

.

.

.

Otzhe now zaboronenimi transported to klіtinami will Ti, de Scho zapishemo in the table below:

Viznachaєmo Pochatkova i plan rozv'yazuєmo nova dopomіzhnu task (Table 5.18.):

table 5.18

Zroby zsuv 40 odinits by lantsyugu A 4 B 2 A 1 2 A 1 4, matimemo Taqiy plan:

.

Tsei plan optimally oskіlki , tobto .

Zauvazhimo scho Danian algorithm zastosovuєtsya i for rozv'yazuvannya vіdkritih transport problems without introducing fіktivnih punktіv. For tsogo dosit zadovolniti the grupu obmezhen, yak Got vikonuvatis in viglyadі strict rіvnostey, so i pіdіbrati system potentsіalіv on ostannomu krotsі, Tim obmezhennyam dwellers, SSMSC for znaydenogo plan Je strict nerіvnostyami, vіdpovіdali nulovі potentsіali.