14-mavzu. Optimallashtirish masalalari. Transport masalasi. Ma’ruza mashg’uloti rejasi

14.4. IKKI KARRA AFZALROQ USUL
14.4.1. Bu usulning mohiyati quyidagicha. Avval har bir satrda eng kichik harajatli katak (kataklar) tanlab olinib V-bilan belgilanadi.

Ta’minot chilar	Iste’molchilar					bor mahsulot
	B1	B2	B3	B4	B5	miqdori
A1	5	6	9	8	VV 3 100	100
A2	9	V 4 40	VV 3 110	4	5	150
A3	8	7	9	VV 2 180	5 20	200
A4	VV 3 80	V 4 20	5	4	8 50	150
talab	80	60	110	180	170	600

4-jadval

Keyingi har bir ustunda eng kichik harajatli katak (kataklar) ham V-bilan belgilanadi.

Shundan so‘ng, VV belgili kataklarga mos ravishda taqsimlangan mahsulot miqdori yoziladi. Ikki belgili kataklarga taqsimlangan mahsulot miqdorlari yozib bo‘lingandan keyin, bir belgili kataklarga o‘tiladi. Undan so‘ng, qolgan kataklardan eng kichik harajatlisi tanlab olinadi va bundan keyin minimal baholi usul qo‘llaniladi.
Bu yerda ham, avvalgi usuldagidek maqsad funksiyaning qiymati 1970 chiqadi. (Lekin, bu, umuman har vaqt ham teng chiqadi, degani emas). Endi boshlang‘ich reja yordamida optimal rejani topish usullaridan ayrimlarini ko‘rib chiqamiz.


14.4.2. POTENSIALLAR USULI
Teorema 1. reja transport masalasining optimal yechimi bo‘lishligi uchun shunday ta , sonlari mavjud bo‘lib, ular quyidagi
, agar ,
, agar , (5)
.
shartlarni qanotlantirishi zarur va yetarlidir. Bunda va lar mos ravishda ta’minotchi va iste’molchilarning p o t ye n s i a l l a r i deyiladi.
Chiziqli programmalash nazariyasida ko‘rsatiladiki to‘g‘ri va unga ikkilamchi bo‘lgan masalalarning maqsad funksiyalarining optimal rejadagi qiymatlari bir-biriga teng va shu bilan birga quyidagi teorema o‘rinli bo‘ladi (uning isbotini keltirmaymiz).
Teorema 2. Agar to‘g‘ri masalaning -sharti optimal rejada tengsizlik ko‘rinishda bo‘lsa, unga mos ikkilamchi masalaning optimal rejasining -komponentasi nolga teng bo‘ladi. Agar ikkilamchi masalaning optimal rejasi -komponentasi musbat bo‘lsa, unga mos to‘g‘ri masalaning -chegarasi optimal rejada tenglik holda bo‘ladi.
Bu teoremadan kelib chiqadiki a) mahsulot soni ( ) yozilgan kataklar uchun potensiallar yig‘indisi shu katakka mos kelgan harajatga teng bo‘lishi kerak, ya’ni
, (6)
b) mahsulot soni yozilmagan ( ) kataklar uchun potensiallar yig‘indisi shu katakka mos kelgan harajatdan kichik yoki teng bo‘lishi kerak, ya’ni
(7).
Endi, bevosita topilgan boshlang‘ich rejalarni yaxshilash- optimal yechimni aniqlashni ko‘rib chiqamiz.
Agar biror to‘ldirilmagan katak (7)-shartni qanoatlantirmasa, topilgan reja optimal emas, uni yaxshilash kerak bo‘ladi.