|
3.2.Transport masalasini boshlang’ich tayanch yechimini topish usullari
Transport masalasi umumiy ko’rinishda berilgan bo’lsin.
(3.7)
(3.8)
(3.9)
(3.10)
Masalaning (3.7) va (3.8) shartlari birgalikda ta noma’lumli ta tenglamalar sistemasidan iborat. Yuqoridagi 3.2-teoremaga asosan bu sitema koeffitsientlaridan tuzilgan matritsaning rangi ga teng bo’ladi.
Shunday qilib, transport masalasining boshlang’ich tayanch yechimidan iborat bo’lgan matritsaning komponentlari musbat bo’lib, qolganlari nolga teng bo’ladi.
Transport masalasi quyidagi jadval ko’rinishida berilgan bo’lsin.
Ishlab chiqarish
korxonalari
|
Korxonada
ishlab
chiqarilgan
mahsulotlar
(tonna
hisobida )
|
Iste’molchilar
|
|
|
…
|
|
|
|
|
|
…
|
|
|
|
|
|
…
|
|
…
|
…
|
…
|
…
|
…
|
…
|
|
|
|
|
…
|
|
Talablar
|
|
|
|
…
|
|
Shimoliy-g’arb burchak usuli. Dastlabki qilinadigan amal jadvalni shimliy-g’arbida joylashgan nomalumni qiymatini aniqlaymiz: .
Bu yerda, uch hol bo'lishi mumkin:
1) bo’lsa, va ( )
2) bo’lsa, va
3) bo’lsa, bo’lib, satr ustun keyin qaralmaydi, bu variant maxsus rejaga olib keladi. Oxirgi qadamda bitta satr va bitta ustun qolib, u to’ldirilib jarayon tamom bo’ladi. Ma’lumki olingan yechimda to’ldirilgan katakchalar soni bo’lishi kerak, shuning uchun ham bu rejada uni tekshirib ko’rish kerak bo’ladi. Agar bu shart bajarilmasa, ya’ni to’ldirilgan katakchalar soni dan kam bo’lsa, olingan reja maxsus bo’lib, bunda eng kam baholi katakchalarga 0 qo’yish bilan ular sonini ga yetkaziladi.
Misol. Quyidagi jadval asosida berilgan transport masalasini shimoliy-g’arb usuli bilan boshlang’ich tayanch yechimini toping.
-
Ta’minlovchilar
|
Zahiralar
|
Iste’molchilar
|
|
|
|
|
|
|
200 t
|
5
|
7
|
4
|
2
|
5
|
|
175 t
|
7
|
1
|
3
|
1
|
10
|
|
225 t
|
2
|
3
|
6
|
8
|
7
|
Talablar
|
600 t
|
100 t
|
130 t
|
80 t
|
190 t
|
100 t
|
Yechish. Bu masalada taminlovchilarning zahiralar miqdori iste’molchilarni talablari yig’indisiga teng. Demak, masala yopiq transport masalasidir. Birinchi rejani shimoliy-g’arbiy burchak usulidan foydalanib tuzamiz.
. iste’molchi talabi qondirildi. .
, . iste’molchi talabi qondirilmadi. 1-ta’minotchining zahirasida yuk qolmadi. Qolgan 30t yukni iste’molchiga 2- ta’minotchidan ajratamiz. . iste’molchini ham talabi to’liq qondirildi. Shu ko’rinishda davom ettiramiz.
, ;
, ;
, .
Bu topilgan qiymatlarini jadvalga joylashtirib chiqamiz.
-
Ta’minlovchilar
|
Zahiralar
|
Iste’molchilar
|
|
|
|
|
|
|
200 t
|
5
100
|
7
100
|
4
|
2
|
5
|
|
175 t
|
7
|
1
30
|
3
80
|
1
65
|
10
|
|
225 t
|
2
|
3
|
6
|
8
125
|
7
90
|
Talablar
|
600 t
|
100 t
|
130 t
|
80 t
|
190 t
|
100 t
|
Topilgan boshlang’ich yechimdagi 0 dan farqli bo’lgan nomalumlar soni 7 ta bo’lib, u dan kichik.
Minimal harajatlar usuli. Transport masalasining yechimini topish uchun kerak bo’lgan qadamlar soni boshlang’ich tayanch yechimni tanlashga bog’liq. Optimal yechimga yaqin bo’lgan tayanch masalaning optimal yechimini topishni tezlashtiradi. Shimoliy-g’arbiy burchak usuli transport masalasini yechimini ixtiyoriy ravishda, transport xarajatlarini nazarga olmagan holda aniqlaydi. Bunday usul yordami bilan topilgan taanch yechim optimal yechimdan ancha yiroq bo’lib, optimal yechimni topish uchun juda ko’p amallarni bajarishga to’g’ri keladi.
Endi transport masalasini boshlang’ich yechimini topishning transport harajatlarini nazarga oluvchi minimal xarajatlar usuli bilan tanishamiz.
Minimal xarajatlar usulining qoidasi quyidagicha:
Transport masalasi xarajatlaridan tashkil topgan ta’rif matritsasi belgilab olinadi:
C matritsaning minimal elementini topamiz:
Faraz qilaylik, bu element
bo'lsin. U holda
Berilganlarga asosan quyidagi ikki hol bo'lishi mumkin:
1) , 2) .
Birinchi holda satrning barcha elementlari bo'ladi, bunday holda satr elementlarini o'chiramiz. Ikkinchi holda ustunning barcha elementlari va bu holda barcha ustun elementlari o'chiriladi.
Ustun yoki satr elementlarini o'chirish natijasida hosil bo'lgan yangi matritsaning ustun yoki satrlari soni matritsaga nisbatan bittaga kamayadi. Ikkinchi qadamda yuqoridagi jarayon yangi matritsa uchun yana bajariladi. Shunday qilib, qo'yilgan masalaning boshlang'ich optimal rejasini topish uchun minimal xarajatlar usulida qadamni bajarish kerak.
Misol. Quyidagi transport masalasini minimal xarajatlar usuli bilan boshlang’ich yechimni topamiz.
|
80
|
60
|
170
|
80
|
110
|
8
|
1
|
9
|
7
|
190
|
4
|
6
|
2
|
12
|
90
|
3
|
5
|
10
|
11
|
Bu masalaning transport xarajatlaridan tuzilgan matritsasi
dan iborat.
1) , .
Demak, 2-ustun o’chiriladi va ning qiymati 110-60=50 ga o’zgaradi. Jadvalni quyidagicha o’zgartiramiz.
|
80
|
0
|
170
|
80
|
50
|
8
|
1
60
|
9
|
7
|
190
|
4
|
6
|
2
|
12
|
90
|
3
|
5
|
10
|
11
|
2) C matritsanining 2-ustunini o’chirish natijasida hosil bo’lgan
matritsaning elementlari ichida eng kichigini ,bunga mos bazis o’zgaruvchi
ni aniqlaymiz. Bu holda 2-ustun o’chiriladi va ni qiymati 190-170=20 ga o’zgaradi.
|
80
|
0
|
0
|
80
|
50
|
8
|
1
60
|
9
|
7
|
20
|
4
|
6
|
2
170
|
12
|
90
|
3
|
5
|
10
|
11
|
3) matritsaning 2- ustunini o’chirish natijasida quyidagi
matritsaga ega bo’lamiz. Bu matritsaning elementlari orasida eng kichigini topamiz. . Demak , . Bu holda C matritsani 1- ustuni o’chiriladi va ning qiymati 90-80=10 ga o’zgaradi.
|
0
|
0
|
0
|
80
|
50
|
8
|
1
60
|
9
|
7
|
20
|
4
|
6
|
2
170
|
12
|
10
|
3
80
|
5
|
10
|
11
|
4) C matritsaning 1,2,3-ustunlari o’chirilishi natijasida ustun matritsaga ega bo’lamiz.
Bu matritsaning komponentlarini o’sish tartibida qarab chiqib, ularga mos keluvchi larni aniqlaymiz:
|
0
|
0
|
0
|
80
|
110
|
8
|
1
60
|
9
|
7
50
|
190
|
4
|
6
|
2
170
|
12
20
|
90
|
3
80
|
5
|
10
|
11
10
|
Berilgan masalani bazis yechimi
matritsadan iborat bo’ladi.
Do'stlaringiz bilan baham: | 
