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

Ically mathematical programuvannya - Nakonechny S.І.

5.5.4. Butt rozv'yazuvannya transportation problem by potentsіalіv

Kompaniia kontrolyuє three factories A 1, A 2, A 3, zdatnі vigotovlyati vіdpovіdno 150, 60 is the 80 yew. od. produktsії schotizhnya. Vaughn UCLA dogovіr іz chotirma zamovnikami B 1, B 2, B 3, B 4, Yakima potrіbno schotizhnya dostavlyati vіdpovіdno 110, 40, 60 is the 80 yew. od. produktsії. Vartіst transportuvannya 1000 od. produktsії zamovnikam s kozhnoї factory is induced in the Table. 5.10.

table 5.10

Vartіst transportuvannya produktsії

Viznachiti optimal plan carried produktsії od kozhnoї factory to zamovnikіv scho mіnіmіzuє Total value poslug the agriculture.

Pobudova matematichnoї modelі. Nekhay xij - Quantity produktsії scho transported -ї s i to j-th factory zamovnika . Oskіlki transport problems for minds Je zbalansovanoyu, Closed- Then ically mathematical model zadachі matim viglyad:

Ekonomіchny zmіst obmezhen polyagaє information recorded in the fact scho all viroblena factories Produkciya Got vivozitisya to zamovnikіv povnіstyu.

Analogіchnі obmezhennya mozhna zapisati vіdnosno zamovnikіv: Produkciya scho Mauger nadhoditi to spozhivacha od troh factories Got povnіstyu zadovolnyati yogo popit. Ically mathematical tse zapisuєtsya as follows:

Zagalnі vitrati, pov'yazanі s transportuvannyam produktsії, viznachayutsya yak scrip dobutkіv obsyagіv perevezenoї produktsії on vartostі transportuvannya 1000 od. produktsії to vіdpovіdnogo zamovnika i minds of zadachі toil Buti mіnіmalnimi. Tom formally tse mozhna zapisati as follows:

min Z = 4 x 4 x 11 + 2 x 12 + 13 + 14 + 5 x 5 x 21 + 3 x 22 + x 23 + x 24 + 2 x 31 + 2 x 32 + 33 +4 x +2 x 34.

Zagalom ically mathematical model sformulovanoї zadachі Got viglyad:

min Z = 4 x 4 x 11 + 2 x 12 + 13 + 14 + 5 x 5 x 21 + 3 x 22 + x 23 + 2 x 24 + 2 x 31 + x 32 + x 33 + 4 +2 x 34

of minds:

Rozv'yazannya. Zapishemo minds zadachі in viglyadі transportnoї tablitsі (tab. 5.11) that sklademo її Purshia support program in tsіy tablitsі method mіnіmalnoї vartostі.

table 5.11

Total value of the transported produktsії zgіdno s Persha support program viznachaєtsya have Taqiy sposіb:

Z 1 = 110 x 4 + 5 x 40 + 1 x 60 + 1 x 40 + 2 x 40 = 820 (d. Od.).

Purshia reference transportnoї plan zadachі virodzheny, oskіlki Quantity zapovnenih klіtinok in tablitsі dorіvnyuє p'yati and (m + n - 1) = 3 + 4 - 1 = 6.

For further rozv'yazuvannya zadachі neobhіdno one s porozhnіh klіtinok zapisati "nulove transported" so dwellers are not porushiti opornostі plan tobto mozhna zaynyati whether yak Let klіtinku, yak not utvoryuє zamknenogo cycle іz zapovnenimi klіtinami. Napriklad, zapovnimo zero klіtinku A 2 4. Now Purshia plan transportnoї zadachі nevirodzhenim Yea, i yogo mozhna perevіriti on optimalnіst potentsіalіv method.

On osnovі pershoї minds optimalnostі ui + vj = cij sklademo rіvnyan system (for zapovnenih klіtin tablitsі) for viznachennya potentsіalіv Perche support program:

Recorded rіvnyan system neviznachenoyu Yea, i s one її rozv'yazkіv dіstanemo, uzyavshi, napriklad, v 4 = 0. Todі OAO All INSHI potentsіali uniquely viznachayutsya s tsієї Sistemi rіvnyan: u 1 = 5, u 2 = 2, u 3 = 2 v 1 = - 1, v 2 = - 1, v = 3 - 1. Tsі values potentsіalіv Perche support plan zapisuєmo in transport table.

Potіm zgіdno s algorithm method potentsіalіv perevіryaєmo vikonannya Druha minds optimalnostі ui + vj ≤ cij (for porozhnіh klіtinok tablitsі):

A B 1 2: u + v 1 2 = 5 + (-1) = 4 = 4 ;

A B 1 3: u 1 + v 3 = 5 + (-1) = 4 > 2;

A B 1 2: u 2 + v 1 = 2 + (-1) = 1 <5;

A 2 B 2: u 2 + v 2 = 2 + (-1) = 1 <3;

A 3 B 1: u 3 + v 1 = 2 + (-1) = 1 <2;

A 3 B 3: u 3 + v 3 = 2 + (-1) = 1 <4.

Umov optimalnostі not vikonuєtsya for klіtinki A 1 B 3. torn down D13 = (u 1 + v 3) - c = 13 4 - 2 = 2 zapisuєmo in lіvomu bottom codend vіdpovіdnoї klіtinki.

Otzhe, Purshia support program transportnoї zadachі suboptimal. Tom od Demba neobhіdno switch to another plan, zmіnivshi spіvvіdnoshennya zapovnenih i porozhnіh klіtinok tablitsі.

Potrіbno zapovniti klіtinku A 1 B 3, in yakіy Je єdine torn down optimalnostі minds. "+" Representable in nіy sign. For viznachennya klіtinki scho zvіlnyaєtsya, buduєmo cycle pochinayuchi s klіtinki A 1 B 3, that a cycle top poznachaєmo pochergovo signs "-" i "+". Teper neobhіdno peremіstiti produktsіyu in furrows pobudovanogo cycle. For tsogo have empty klіtinku A B 1 3 s less then portable numbers hij, SSMSC rozmіschenі in klіtinkah Zi sign "-". Odnochasno tse sama number hij dodaєmo to vіdpovіdnih numbers scho rozmіschenі in klіtinkah Zi "+" sign, that vіdnіmaєmo od numbers scho rozmіschenі in klіtinkah, poznachenih sign "-".

In danomu razі , tobto . Vikonavshi pererozpodіl transported produktsії zgіdno іz a recorded rules dіstanemo takі novі value: for klіtinki A 1 B 3 - 40 od. produktsії, and for A 2 B 3 - (60 - 40) = 20 odes and for A 2 B 4 -. (0 + 40) = 40 ML. Klіtinka A 1 B 4 zvіlnyaєtsya i in novіy tablitsі bude empty. Usі INSHI zapovnenі klіtinki pershoї tablitsі, SSMSC did not enter to cycle perepisuєmo at another table without the Change log. Quantity zapovnenih klіtinok in novіy tablitsі takozh Got vіdpovіdati umovі nevirodzhenostі plan tobto dorіvnyuvati (n + m - 1).

Otzhe, other support transportnoї plan zadachі matim Taqiy viglyad (Table 5.12.):

table 5.12

Rozrahuєmo values ​​tsіlovoї funktsії vіdpovіdno reference to another plan zadachі:

Z 2 = 4 x 110 + 2 x 40 + 1 x 20 + 2 x 40 + 1 x 40 + 2 x 40 = 740 (d. Od.).

Novi plan znovu perevіryaєmo on optimalnіst, tobto povtoryuєmo opisanі ranіshe dії. Other support transportnoї zadachі plan takozh suboptimal (Got Location torn down for klіtinki A 3 B 1). For Relief pobudovanogo cycle vikonavshi perehіd to third support plan transportnoї zadachі, otrimuєmo Table. 5.13:

table 5.13

Viznachimo Total value vitrat on transportuvannya produktsії zgіdno s tretіm support program:

The Z3 = 4 x 90 + 2 x 60 + 2 x 60 + 2 x 20 + 1 x 40 + 2 x 20 = 720 (d. Od.).

Perevіrka ostannogo plan for optimalnіst for Relief method potentsіalіv pokazuє scho vіn optimally. Tom:

.

For optimal plan carried Purshia zamovnik otrimuє 90 tis. od. produktsії pershoї s factory is the 20 yew. od. - S tretoї. Other spozhivach zadovolnyaє svіy popit for rakhunok virobnitstva that transported 40 tis. od. produktsії tretoї s factory t i. e. When tsomu Total value of transported vsієї produktsії Yea i naymenshoyu becoming 720 mind. od.