5-ma’ruza. Transport masalasining qo’yilishi. Balans modeli va uni transport masalasi yordamida yechish

(6)
va
(7)
(6) sistemadan (8)
ekani va (7) sistemadan
(9)
kelib chiqadi. Bundan (8) ga asosan bo‘ladi. Demak matritsaning ta qatori o‘zaro chiziqli bo‘lmagan sistemani tashkil qiladi va demak, bo‘ladi.
3 -teorema. Agar masaladagi barcha va lar butun sonlardan iborat bo‘lsa, transport masalasinig yechimi butun sonli bo‘ladi
Teoremaning isbotini transport masalasining boshlang‘ich tayanch planlarini topish usullarida ko‘rish mumkin.
4 -teorema. Ixtiyoriy transport masalasining optimal plani mavjuddir.
Isbot. 1-teoremaga asosan masalaning kamida bitta plani mavjuddir. (1), (2) shartlardagi koeffitsiyentlar va barcha va lar musbat butun son bo‘lganligi sababli ham yuqoridan chegaralangan bo‘ladi va uning qiymati mos va larning qiymati oshmaydi.
Shunday qilib transport masalasi planlaridan tashkil topgan to‘plam bo‘sh to‘plam bo‘lmaydi. U chegaralangan to‘plam bo‘ladi. Demak transport masalasi optimal planga ega.


2. Transport masalasining boshlang‘ich tayanch planini topish usullari

Boshqa chiziqli programmalash masalalari singari transport masalasini yechish jarayoni boshlang‘ich tayanch planni topishdan boshlanadi. Transport masalasining boshlang‘ich planini topish usullari ko‘p bo‘lib, quyida biz «shimoliy-g‘arb burchak» usuli va «ustundagi minimal element» usuli bilan tanishamiz.

1. Shimoliy – g‘arb burchak usuli. Faraz qilaylik, transport masalasining shartlari quyidagi jadvalga joylashtirilgan bo‘lsin.

			…
			…
			…
			… …
			…

«Shimoliy-g‘arb burchak» usulining g‘oyasi quyidagilardan iborat. Eng avval shimoliy g‘arbda joylashgan noma’lum qiymatini aniqlaymiz, . Agar bo‘lsa, va , agar bo‘lsa, va bo‘ladi. Faraz qilaylik, birinchi hol bajarilsin. Bu holda 1-qadamdan so‘ng masalaning yechimlaridan tashkil topgan matritsa quyidagi ko‘rinishda bo‘ladi.

1-q a d a m
(10)

Endi ikkinchi qatordagi birinchi elementning qiymatini topamiz:

Agar bo‘lsa, va ,
Agar bo‘lsa, va ,
Faraz qilaylik, yangi matritsa uchun ham 1-hol bajarilsin, u holda
2 – q a d a m

Xuddi shunday yo‘l bilan davom etib, har bir qadamda birorta ning qiymati topiladi. va yoki nolga aylantiriladi.

Bu jarayon barcha va lar nolga aylanguncha takrorlanadi. Ma’lumki, har bir ning qiymati va larning turli kombinatsiyalarini ayirish yoki qo‘shish yordami bilan topildi, shuning uchun va lar butun bo‘lganda topilgan tayanch plan butun sonli bo‘ladi. Bundan tashqari, yuqoridagi 2-teoremaga asosan tayanch plandagi noldan farqli noma’lumlar soni dan oshmaydi.
M i s o l. Quyidagi transport masalasining boshlang‘ich planini toping.

	3	6	2	1
4	2	5	9	5
2	8	3	5	8
3	7	3	1	4
3	5	9	7	2

1-qadam.
.

Shuning uchun va ga o‘zgaradi. .
2-qadam.

Bunda va ga o‘zgaradi,
3-qadam.

Bunda va ga o‘zgaradi hamda bo‘ladi.
4-qadam.

Bunda bo‘ladi hamda bo‘ladi.
5-qadam.
ga o‘zgaradi.
6-qadam.

Bunda va masalani yechilish jarayoni tugaydi. Topilgan boshlang‘ich plan quyidagi ko‘rinishda bo‘ladi:

	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 plandagi noldan farqli bo‘lgan noma’lumlar soni 6 ta bo‘lib, u dan kichik. Agar masalaning tayanch planidagi noldan farqli bo‘lgan noma’lumlar soni dan kichik bo‘lsa, bunday planni xos plan deb ataymiz. Xos planni to‘g‘rilash usullari bilan keyinroq tanishamiz.
II. M i n i m a l x a r a j a t l a r u s u l i. transport masalasining yechimini topish uchun kerak bo‘ladigan iteratsiyalar soni boshlang‘ich tayanch planni tanlashga bog‘liqdir. Optimal planga yaqin bo‘lgan tayanch planni topish masalasining optimal yechimini topishni tezlashtiradi. Yuqoridagi «shimoliy-g‘arb burchak» usuli transport masalasining tayanch planini ixtiyoriy ravishda, transport harajatlarini nazarga olmagan holda aniqlaydi. Bunday usul yordami bilan topilgan ko‘pgina tayanch plan optimal plandan yiroq bo‘lib, optimal yechimni topish uchun juda ko‘p iteratsiyalarni bajarishga to‘g‘ri keladi.
Adabiyotda transport masalasining boshlang‘ich masalasini topish uchun transport harajatlarini nazarga oluvchi ko‘p usullari ma’lum (ustundagi minimal element usuli, minimal harajatlar usuli, ikki tomonlama tanlash usuli va hokazolar). Ularning hammasi shimoliy-g‘arb burchak usulining trasport harajatlarini nazarga oluvchi modifitsirlangan holidir.
Minimal harajatlar usulining g‘oyasi quyidagilardan iborat:

1. 
   Trasport masalasi harajatlaridan tashkil topgan matritsa belgilab olinadi, ya’ni
   

Bu matritsaning minimal elementini topib belgilaymiz:

U holda quyidagicha aniqlanadi:

Bu yerda ikki hol bo‘lishi mumkin:
1)
2)
Birinchi holda qatorning barcha elementlari

bo‘ladi, bunday holda qator o‘chiriladi deb ataymiz. Ikkinchi holda esa, ustunning barcha elementlari

bo‘ladi, bu holda ustun o‘chiriladi deb ataymiz.
2. Faraz qilaylik, matritsa matritsaning qatorini (1-hol) yoki ustunini (2-hol) o‘chirish natijasida hosil bo‘lgan matritsa bo‘lsin. Yangi matritsa uchun

bo‘lsin.
Ma’lumki, matritsadagi ustun yoki qatorlar soni matritsanikidan bittaga kam bo‘ladi. Ikkinchi qadamda yuqoridagi matritsa uchun bajarilgan ishlar matritsa va miqdorlar uchun bajariladi. Natijada planlardan tashkil topgan matritsaning yana bir qatori yoki ustuni o‘chiriladi. Bu jarayon matritsaning hamma qator va ustunlari o‘chirilguncha, ya’ni matritsaning hamma qator va ustunlari to‘ldirilguncha takrorlanadi. ta ishlab chiqaruvchi punktni ta iste’mol qiluvchi punktga bog‘lovchi transport masalasining boshlang‘ich tayanch planini topish uchun minimal harajatlar usulida ta qadamdan iborat ishlarni bajarish kerak bo‘ladi.
M i s o l. Berilgan transport masalasining tayanch planini minimal harajatlar usulidan foydalanib toping.

	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

1.

Bu holda bo‘ladi. Boshqacha aytganda, 3-qator o‘chiriladi va yangi matritsa hosil bo‘ladi. Bu matritsa uchun

bo‘lib, matritsa quyidagi ko‘rinishda bo‘ladi:
.
2. matritsadagi elementlar ichida eng kichigini topamiz, ya’ni

U holda
.
Demak,
Shuning uchun bo‘ladi, ya’ni 1-ustun o‘chiriladi. Natijada yangi

matritsa hosil bo‘ladi. Bu matritsa uchun