Transport masalasining boshlang‘ich bazis rejasini topish usullari
Boshqa chiziqli dasturlash masalalari singari transport masalasini yechish jarayoni boshlang‘ich bazis rejani topishdan boshlanadi. Transport masalasining bazis rejasini topish usullari ko‘p bo‘lib, quyida biz "shimoliy-g‘arb burchak" usuli va "minimal harajatlar" usuli bilan tanishamiz.
1. Shimoliy-g‘arb burchak usuli. Faraz qilaylik, transport masalasining shartlari quyidagi jadvalga joylashtirilgan bo‘lsin.
bj
ai
|
b1
|
b2
|
…
|
bn
|
a1
|
c11
|
c12
|
…
|
c1n
|
a2
|
cm1
|
c22
|
…
|
c2n
|
…
|
…
|
…
|
…
|
…
|
am
|
cm1
|
cm2
|
…
|
cmn
|
Shimoliy-g‘arb burchak usulning g‘oyasi quyidagilardan iborat. Eng avval shimoliy-g‘arbda joylashgan katakchadagi x11 noma’lumning qiymatini aniqlaymiz, x11=min (a1,b1). Agar a1 ≤ b1 bo‘lsa, x11= a1 va x1j=0, (j=2..n), agar b1 ≤ a1 bo‘lsa, x11=b1 va xi1=0, (i= 2..m ) bo‘ladi. Faraz qilaylik, birinchi hol bajarilsin. Bu holda 1-qadamdan so‘ng masalaning yechimlaridan tashkil topgan matritsa quyidagi ko‘rinishda bo‘ladi.
x11= a1
|
0
|
0
|
…
|
0
|
0
|
x21
|
x22
|
x23
|
|
x2n
|
a2
|
…
|
…
|
…
|
…
|
…
|
…
|
xm1
|
xm2
|
xm3
|
…
|
xmn
|
am
|
b1-a1
|
b2
|
b3
|
…
|
bn
|
|
Endi ikkinchi qatordagi birinchi elementning qiymatini topamiz:
Agar a2>b1-a1 bo‘lsa, x21=b1-a1 va xi1=0, (i=3..m, )
Agar a21-a1 bo‘lsa, x21=a2 va x2j=0, (j=2..n )
Faraz qilaylik, yangi matritsa uchun ham 1-hol bajarilsin, u holda 2-qadamdagi yechimlar matritsasi quyidagigacha bo‘ladi.
x11= a1
|
0
|
0
|
…
|
0
|
0
|
x21= b1-a1
|
x22
|
x23
|
|
x2n
|
a2
|
0
|
x32
|
x33
|
|
x3n
|
a3
|
…
|
…
|
…
|
…
|
…
|
…
|
0
|
xm2
|
xm3
|
…
|
xmn
|
am
|
0
|
b2
|
b3
|
…
|
bn
|
|
Xuddi shunday yo‘l bilan davom etib, har bir qadamda birorta xij ning qiymati topiladi. xij=min(ai,bj) va ai yoki bj nolga aylantiriladi.
Bu jarayon barcha ai va bj lar nolga aylanguncha takrorlanadi. Ma’lumki, har bir xij ning qiymati ai va bj larning turli kombinatsiyalarini ayirish yoki qo‘shish yordami bilan topiladi, shuning uchun ai va bj lar butun bo‘lganda topilgan bazis reja butun sonli bo‘ladi. Bundan tashqari, yuqoridagi 2-teoremaga asosan bazis yechimdagi noldan farqli xij noma’lumlar soni m+n-1 dan oshmaydi.
Minimal xarajatlar usuli.
Transport masalasining optimal yechimini topish uchun kerak bo‘ladigan iteratsiyalar soni boshlang‘ich bazis yechimini tanlashga bog‘liqdir. Optimal yechimga yaqin bo‘lgan bazis yechimni topish masalaning optimal yechimini topishni tezlashtiradi. Yuqoridagi «shimoliy-g‘arb burchak» usuli transport masalasining bazis yechimini ixtiyoriy ravishda, transport harajatlarini nazarga olmagan holda aniqlaydi. Bunday usul yordami bilan topilgan ko‘pgina bazis yechim optimal yechimdan yiroq bo‘lib, optimal yechimni topish uchun juda ko‘p iteratsiyalarni bajarishga to‘g‘ri keladi.
Adabiyotda transport masalasining boshlang‘ich bazis yechimini topish uchun transport xarajatlarini nazarga oluvchi ko‘p usullar ma’lum(ustundagi minimal element usuli, minimal xarajatlar usuli, ikki tomonlama tanlash usuli va hokazolar).Ularning hammasi transport xarajatlarini nazarga oluvchi usullaridir.
Minimal xarajatlar usulining g‘oyasi quyidagilardan iborat:
Transport masalasi xarajatlaridan tashkil topgan matritsa belgilab olinadi, ya’ni
Bu matritsaning minimal elementini topib belgilaymiz
U holda quyidagicha aniqlanadi
Bu erda ikki hol bo‘lishi mumkin:
1)
2)
Birinchi holda bo‘lganda qatorning barcha (j≠j1) elementlari 0 ga teng, ya’ni
bo‘ladi, bunday holda i1 qator o‘chiriladi deb aytamiz. Ikkinchi holda
va j1 ustunning barcha (i≠i1) elementlari 0 ga teng, ya’ni
tenglik o‘rinli bo‘ladi, bunday holda j1 ustun o‘chiriladi deb aytamiz.
2. Faraz qilaylik, C′ matritsa C matritsaning i1 qatorini (1-hol) yoki j1 ustunini (2-hol) o‘chirish natijasida hosil bo‘lgan matritsa bo‘lsin.
Yangi matritsa uchun
,
bo‘lsin.
Ma’lumki, C′ matritsadagi ustun va qatorlar soni C matritsanikidan bittaga kam bo‘ladi. Ikkinchi qadamda yuqoridagi C matritsa uchun bajarilgan ishlar C′ matritsa va , miqdorlar uchun bajariladi. Natijada rejalardan tashkil topgan X=(xij) matritsaning yana bir qatori yoki ustuni to‘ldiriladi. Bu jarayon C matritsaning hamma qator va ustunlari o‘chirilguncha, ya’ni X matritsaning hamma qator va ustunlari to‘ldirilguncha takrorlanadi.
m ta ishlab chiqaruvchi punktni n ta iste’mol qiluvchi punktga bog‘lovchi transport masalasining boshlang‘ich bazis rejasini topish uchun minimal xarajatlar usulida n+m-1 ta qadamdan iborat ishlarni bajarish kerak bo‘ladi.
Amaliy topshiriqlari va
ish davomida ishlab chiqiladigan dasturning to‘liq namunasi.
Amaliy topshirig‘i. Berilgan masalani yechish uchun algoritm va mos dasturni ishlab chiqing. Algoritmni blok-sxema shaklida ifodalang va zarur bo‘lsa algoritmik dekompozitsiyani amalga oshiring. Zarur hollarda qism masalalarni yechish uchun qism dasturlardan foydalaning.
Dastur namunasi. Biz quyida namuna sifatida transensent tenglamalarni taqribiy yechish bilan bog‘liq masalani qaraymiz. Masalani taqribiy usullaridan bo‘lgan to‘g‘ri to‘rtburchaklar, trapetsiyalar va Simpson usullari yordamida yechish algoritmini (psevdokod shaklida) ishlab chiqamiz va uni C++ tilidagi dasturga o‘tkazamiz.
Amaliy topshirig‘i sharti. Quyidagi transport masalasining boshlang‘ich bazis yechimini toping.
bj
ai
|
3
|
6
|
2
|
1
|
4
|
2
|
5
|
9
|
5
|
2
|
8
|
3
|
5
|
8
|
3
|
7
|
3
|
1
|
4
|
3
|
5
|
9
|
7
|
2
|
Masalani yechish algoritmi (Shimoliy-g‘arbiy burchak usuli).
1-qadam.
x11=min(4,3)=3
Shuning uchun b′1=0 va a1=4-3=1 , x21=x31=x41=0
2-qadam.
x12=min(1,6)=1.
Bunda a′1=0 va b′2=6-1=5 , x13=x14=0.
3-qadam.
x22=min(2,5)=2.
Bunda a′2=0 va b′2=5-2=3 , x23=x24=0.
4-qadam.
x32=min(3,3)=3.
Bunda a′′2=b′′2=0 bo‘ladi hamda x33=x34=0, x42 =0.
5-qadam.
x43=2, a′4=3-2=1.
6-qadam.
x44 =min (1,1)=1
Bunda a′4=b′4=0 bo‘ladi va masalani yechish jarayoni tugaydi. Topilgan boshlang‘ich bazis yechim quyidagi ko‘rinishda bo‘ladi:
bj
ai
|
3
|
6
|
2
|
1
|
4
|
2
3
|
5
1
|
9
|
5
|
2
|
8
|
3
2
|
5
|
8
|
3
|
7
|
3
3
|
1
|
4
|
3
|
5
|
9
|
7
2
|
2
1
|
Topilgan boshlang‘ich bazis yechimdagi noldan farqli bo‘lgan noma’lumlar soni 6 ta bo‘lib, u m+n-1=7 dan kichik. Agar masalaning bazis rejadagi noldan farqli bo‘lgan xij noma’lumlar soni m+n-1 dan kichik bo‘lsa, bunday rejani xos reja deb ataymiz.
Misol. Berilgan transport masalasining bazis rejasini minimal xarajatlar usulidan foydalanib toping.
bj
ai
|
5
|
9
|
9
|
7
|
11
|
7
|
8
3
|
5
1
|
3
7
|
11
|
2
5
|
4
6
|
5
|
9
|
8
|
6
|
3
|
1
8
|
2
|
Masalani yechish algoritmi (Minimal xarajatlar usuli)
1.
x33=min (a3 , b3)=min (8,9)=8.
Bu holda x3j=0, (j≠3) bo‘ladi. Boshqacha aytganda 3-qator o‘chiriladi va yangi C′ matritsa hosil bo‘ladi. Bu matritsada
a31=8-8=0,
b31=9-8=1
bo‘lib, C1 matritsa quyidagi ko‘rinishda bo‘ladi:
2. C1 matritsadagi elementlar ichida eng kichigini topamiz, ya’ni
U holda x21=min (a2, b1)=min (11,5)=5. Demak, x21=b1=5.
Shuning uchun xi1=0 (i≠2) bo‘ladi, ya’ni 1-ustun o‘chiriladi. Natijada yangi matritsa hosil bo‘ladi.
Bu matritsa uchun =5-5=0, =11-5=6.
3. CII matritsadagi elementlar ichida eng kichigini topamiz, ya’ni
Shuning uchun x14=min (a1, b4)=min (11,7)=7. Bu erda 4-ustun o‘chiriladi va =a1-x14=11-7=4 bo‘ladi. Natijada yangi
matritsa hosil bo‘ladi.
4. CIII matritsadagi elementlar ichida eng kichigini topiladi
Bu holda, x22=min( ,b2)=min(6,9)=6. Natijada 2-qator o‘chiriladi va b2 ning qiymati
=b2-x22=9-6=3
ga o‘zgaradi va yangi CIV matritsa-qator hosil bo‘ladi:
CIV=(8,5).
Shunday yo‘l bilan 5-qadamda x13=1 topilib, 3-ustun o‘chiriladi. hosil bo‘lgan X matritsa quyidagi ko‘rinishga ega bo‘ladi:
Bu matritsa berilgan transport masalasining bazis yechimidir.
Amaliy ishini bajarish tartibi. Amaliy ishini bajarishda quyidagi tartibga amal qiling:
Guruh jurnalidagi nomerga ko‘ra o‘z variantingizni aniqlang
Masalani yechish uchun algoritm va dastur quring.
Kichik hajmdagi ma’lumotlar uchun dasturning to‘g‘ri ishlayotganligiga ishonch hosil qiling.
Bajarilgan ishlar haqida hisobot tayyorlang.
Amaliy topshiriqlari variantlari
Berilgan masalalarning matematik modelini tuzing. Shimoliy-g‘arbiy burchak usuli yordamida basis rejasi tuzilsin. Minimal xarajatlar usuli yordamida bazis rejasini tuzing. Masalani yechishda n soni o‘rniga jurnaldagi tartib raqamni qo‘yib hisoblansin.
3 ta A, V, S temir yo‘l stantsiyalarida mos ravishda 80, 70 va 50 vagonlar zahirasi mavjud. Bu vagonlarni g‘alla ortishga shaylangan 4 ta punktga yuborish kerak. Jumladan, 1-punktga 60 ta, 2-punktga 45 ta, 3-punktga 65 va 4-punktga 30 ta vagon kerak. Vagonlarni taqsimlash uchun sarf qilinadigan xarajatlar matritsasi quyidagi ko‘rinishda berilgan:
|
