Transport máselesi Joba : Transport máselesiniń matematikalıq modeli Transport máselesin sheshiw usılları

Transport máselesin sheshiw usılları

Transport máselesin sheshiw eki basqıshdan ibarat.
1. Baslanǵısh tayansh plandı tabıw.
2. Tayansh planlar ishinen optimal plandı tabıw.
Tayansh plandı dúziwdiń bir neshe usılları ámeldegi: " Arqa -batıs múyesh", " Kishi elementler", " Fogel'" hám basqalar.
" Arqa -batıs múyesh" usılı.
Júklerdi tasıwdıń baslanǵısh plandı dúziwde " arqa -batıs múyesh" usılınan paydalanıw tómendegishe ámelge asıriladı :

1. 
   Tarif kestesi dúziledi.
   

	b1	b2	. . . . .	bn
a1	с11	c12	. . . . .	c1n
a2	с21	c22	. . . . .	c2n
. . . . .	. . . . .	. . . . .	. . . . .	. . . . .
am	сm1	cm2	. . . . .	cmn

2. Shep tárepdegi joqarıdaǵı múyesh, yaǵnıy (arqa -batıs múyesh) den baslap qatar boyınsha yamasa ústin boyınsha jıljıymiz. (1, 1) ketekke a1 hám b1 dıń eń kichigini jaylastıramız, yaǵnıy x11=min (a1, b1).

3. Eger a1>b1 bolsa x11=b1 ni beremiz, birinshi ústin usınıń menen jabıladı, yaǵnıy xi1=0 (i=2, m). (Birinshi qabıl etiwshiniń talabı tolıq qánaatlantırıldı ).
4. Birinshi qatar boyınsha jıljıymiz (1;2) ketekke, bulmanǵa a1-b1, b2 dıń eń kichigini jaylastıramız, yaǵnıy x12=min (a1-b1, b2).
5. Eger b1>a1 bolsa 1-shi qatar jabıladı, yaǵnıy x1 j=0 (j=2, n).
6. Qońsılas kateklerdi toltırıwǵa ótemiz (2. 1), yaǵnıy x21=min (a2, b1-a1).
7. Ekinshi qatar yamasa ekinshi ústin kateklerin toltırıwǵa ótemiz hám taǵı basqa. Bul process tokı resurslar tugamaguncha dawam etedi.
" Kishi elementler" usılı.
" Kishi elementler" usılı járdeminde tayansh plandı tabıw tómendegishe ámelge asıriladı :
1. Júkler qabıl etiwshilerge tarif kesteindegi eń kishi cij tasıw bahasına uyqas ketekti toltırıwdan baslanadı.
2. Eń kishi tarif cij katagiga ai yamasa bj dıń eń kichigi jaylawtriladi.
3. Keyin to'lig'icha júk zapaslari sarp etiw etilgen qatar yamasa qabıllaw punkti talabı qandirilgach uyqas ústin joytıladı.
4. Eger jıberiw punktindegi júk zapaslari tolıq bólistirilgen bolsa hám qabıl etiwshi talabı tolıq qanatlantirilsa olarǵa uyqas qatar hám ústin joytıladı.
5. Qalǵan qatar hám ústinlerden taǵı kishi tariyp alınadı. Júk zapaslarini bólistiriw procesi, tokı júk zapasi tugaguncha hám talaplar qánaatlantirilguncha dawam etedi.
Potensiallar usılı.
Eger joqarıdaǵı usıllar járdeminde baslanǵısh tayansh plan tabılǵan bolsa optimal plandı tabıw potensiallar usılında atqarıladı.
Transport máselesi optimal plandı tabıwdıń potensiallar usılı tómendegilerden ibarat :
1. Joqarıdaǵı keltirilgen usıllar járdeminde júklerdi tasıwdıń tayansh planı anıqlanadı.
2. Uyqas túrde júklerdi qabıl etiwshi hám jiberiwshi punktler ushın ui hám vj potensialları anıqlanadı.
3. Bos kateklerde potensiallar jıyındısı esaplanadı s*ij = ui+vj.
4. Bos kateklerde cij hám s*ij tariflar parqı esaplanadı.
Sij = cij +s*ij= cij -( ui+vj ).
5. Eger hámme bos katekler degi fark Sij>0 bolsa alınǵan plan optimal boladı.
6. Eger bos kateklerden qandayda-birında Sij<0 bolıp qalsa, bos bolmaǵan kateklerge xij ózgeriwshi ma`nisi kiritiledi, yaǵnıy joqarıdaǵı parq minimal bolsın. Sol ketek ushın bos bolmaǵan katekler járdeminde jabıq kontur payda etiledi hám júkler sol konturda qayta bólistiriledi. Nátiyjede jańa tasıw planǵa iye bolamız.
Bul process tokı parq Sij>0 bo'lmaguncha dawam etedi hám aqırǵı alınǵan júklerdi tasıw planı optimal boladı.

Mısal.
Tómendegi kestede berilgen transport máselesin sheshiń

bk ai	40	25	20	50
60	5	4	1	2
40	4	2	6	3
35	7	3	5	4

Sheshiw: Baslanǵısh tayansh plandı " Arqa -batıs múyesh" hám " Kishi elementler" usılında tabamız. " Arqa -batıs múyeshi" usılı qaǵıydasına qaray kesteniń (1, 1) katagiga X1, 1=min (60, 40 ) =40 sanın jaylastıramız, keyingi X12=min (60 -40, 25) =20 sanın (1, 2) katagiga jaylaymız. Usınıń menen birinshi punktte júk tugadi hám keyingi katekler (1, 3) hám (1, 4) yopildi.
Keyingi punkt degi júklerdi bólistiriwdi baslaymız. (2, 2) ketekke X22=min (40, 5) =5 sanın jaylastıramız. Usınıń menen 1-shi hám 2-shi talabanlar talabı qandirildi, yaǵniy 1-shi hám 2-shi ústin yopildi. (2, 3) ketekke X23=min (35, 20 ) =20 jaylastırıladı. 3-shi talaban talabı atqarıldı. qalǵan júkti (2, 4) ketekke jaylastıramız, yaǵnıy X24=min (15, 50) =15 hám ekinshi jıberiw punktinde júk tugadi. 3-shi jıberiw punktindegi júkti bólistiriwdi baslaymız.
(3, 1), (3, 2), (3, 3) katekler jabılǵan, yaǵnıy 1, 2 hám 3 talabanlar talabı qandirilgan. (3, 4) ketekke X34=min (35, 35) =35 jazamız. Usınıń menen júkler tolıq bólistirildi, yaǵnıy tómendegi planǵa iye boldıq.

Maqset funksiyası ma`nisi Z=595 ni quraydı.
Qoyılǵan máseleniń tayansh planın endi " Eń kishi elementler" usılı menen tabamız.
Sheshiw: Ústin yamasa qatar boyınsha eń kishi ǵárejetti tabamız.
Qatar boyınsha bul element (1;3) ketekte jaylasqan, yaǵnıy c13 =1. Sol sebepli bul ketekke X13=min (60, 20 ) =20 júkti jaylaymız. Úshinshi talabandıń talabı qánaatlantırıldı. Sol sebepli keyingi esaplawlarda 3-shi ústin qaralmaydi. Keyingi eń kishi elementti tabamız. Bul element (1, 4) hám (2, 2) kateklerde jaylasqan, yaǵnıy s14=2 hám s22=2. Júklerdi bul kateklerge jaylaymız. X14=min (60 -20, 50) =40, X22=min (40, 25) =25. Ekinshi talaban talabı qánaatlantırıldı, sol sebepli keyingi esaplawlarda 2-shi ústin qaralmaydi.
Keyingi eń kishi elementler (2, 4) hám (3, 2) kateklerde jaylasqan, yaǵnıy s24=3 hám s32=3. Bul kateklerge júklerdi jaylastıramız X24=min (40 -25, 50-40 ) =10. (3, 2) ketek qaralmaydi, sebebi bul ústin esaptan shıǵarılǵan. Keyingi eń kishi elementti izleymiz, bul element s21=4. Júkti bul ketekke jaylaymız X21=min (15-10, 40 ) =5. Eń aqırǵı kishi element s31=7. Bul ketekke de júkti jaylaymız X31=min (35, 40 -5) =35. Nátiyjede júklerdi bóliwlab, baslanǵısh tayansh planǵa iye boldıq, yaǵnıy

Maqset funksiyasın esaplaymiz Z=415.
Endi máseleniń optimal planın tabamız. Optimal plandı tabıw ushın potensiallar usılınan paydalanamız. Baslanǵısh tayansh plan " Eń kishi elementler" usılında tabılǵan deylik. Onı tómendegi keste kórinisinde jazamız.

bk ai	40	25	20	50	u
60	5	4	1 20	2 40	0
40	+ 4 5	- 2 25	6	3 10	1
35	- 7 35	+ 3	5	4	4
V	3	1	1	2

Kestede bos bolmaǵan katekler tómendegi shártni qanoanlantiradi.
r=3+4-1=6
Júkti jiberiwshi hám talabanlar potensialın anıqlaymız hám tómendegi teńlemelerge iye bolamız.
u1+v3=1; u1+v4=2 ; u2+v1=4; u2+v2=2; u2+v4=3 ; u3+v1=7
Ekenin aytıw kerek teńlemeler sanı belgisizler sanınan 1 kem, yaǵnıy belgisizler 1 tasi azat hám ol qálegen baha alıwı múmkin. Mısal ushın aytaylik u1=0. Ol halda qalǵan potensiallar tómendegishe anıqlanadı
u1=0, v3=1, v4=2, u2=1, v2=1, v1=3, u3=4.

Bos kateklerde sij ma`nisin tómendegi formula menen anıqlaymız Sij=cij-(ui+vj). Ol halda

S11=5-(0+3) =2; S12=4-(0+1) =3; S23=6 -(1+1) =4;
S32=3-(4+1) =-2; S11=5-(4+1) =0; S34=4-(4-+2) =-2.
Alınǵan plan optimal bola almaydı, sebebi sij lar ishinde kerileri da ámeldegi S32=S34==-2. Bul katekler ushın jabıq kontur (cikl) payda etemiz. (3, 2) ketek ushın kontur (3, 2), (3, 1), (2, 1), (2, 2). Konturdı saat strelkası boyınsha yamasa oǵan keri baǵıtda (3, 2) ketekten baslap izbe-iz + hám - belgilerin qoyıp shıǵamız. Teris kateklerden eń kichigini tańlaymiz min (25;35) =25, yaǵnıy x22=25. Kateklerde júklerdi qayta bóliwleymiz. Bólistiriliwde ulıwma balans bul kateklerde buzılmasin hám ǵárejetler minimal bolsın. Minusli ketek (2, 2) dagi júkti keyingi oń ketektegi yukga qosamız. Ol halda (2, 1) ketekte júk 5+25=30 boladı. Balans buzılmaslıq ushın (3, 1) ketektegi yukdan 25 birligin (3, 2) ketekke júkleymiz. Sonday etip jańa planǵa iye boldıq. Bul keste ushın potensiallardı anıqlaymız hám bos kateklerde sij larni esaplaymiz:
S₁₁=5-(0+3)=2; S₁₂=4-(0+1)=3; S₂₃=6-(1+1)=4;
S₂₂=2-(2+1)=0; S₃₃=5-(4+1)=0; S₃₄=4-(4-+2)=-2;

bk ai	40	25	20	50	u
60	5	4	1 20	2 40	0
60	5	4	1 20	2 40	0
40	+ 4 30	2 0	6	- 3 10	1
35	- 7 10	3 25	5	+ 4	4
v	3	1	1	2

Jańa alınǵan plan da optimal emes, sebebi S34=-2. Jabıq kontur dúzemiz hám júklerdi bul kontur ishinde qayta bóliwleymiz hám nátiyjede tómendegi planǵa iye bolamız.

bk ai	40	25	20	50	u
60	5	4	1 20	2 40	0
40	4 40	2 0	6	3	1
35	7	3 25	5	4 10	2
V	3	1	1	2

Alınǵan plan optimal plan, sebebi barlıq bos kateklerde Sij lar oń. Sonday eken, optimal plan tómendegishe boladı.

Maqset funksiyasınıń ma`nisi zmin=375.