Chiziqli dasturlashtirish masalalari

8.4. Optimal yechimni topish.
Bazisga kirmay qolgan qatorga nolga teng bo’lgan ayrim o’zgaruvchilar optimal rejada bo’lishi mumkin. Bunday hollarda oddiy usullar yordamida shu o’zgaruvchini bazisga kiritib yangi rejani hosil qilish mumkin. Agar ikkita yoki bir nechta optimal rejalar mavjud bo’lsa, ulardan xoxlagan bittasini optimal reja deb qabul qilish mumkin.
Shuni eslatib utish kerakki, agar nisbatlarning eng kichigi bir nechta bo’lsa, u holda ularning ichidan hal qiluvchi elementiga ko’ra keyingi ustun elementlari eng kichig nisbatda bo’lgan qator tanlanadi. Agar yana bir xil eng kichig nisbatlar mavjud bo’lsa, unda , larning eng kichigidan faqat bittasini olib, shu jarayonni yana takrorlash kerak.
Chiziqli dasturlashtirish masalasini yechimini simpleks usuli bilan topish bir necha bosqichdan iborat ekanligini biz yuqorida ku’rib o’tdik. Bu usulning asosiy qiyinchiligi har bir bosqichda yangi bazisga nisbatan maqsad funksiya va cheklanish shartlarini kaytadan yozib chiqishdan iboratdir. Agar shu bosqichlarning hammasi Simpleks jadvallar yordamida bajarilsa chiziqli dasturlashtirish masalasini simpleks usulda yechish ancha osonlashadi.
Misol. Ushbu

х1+х2-2х5=1	(1)
х2-2х4+х5=2
х3+3х4+х5=3

sistemaning manfiy bo’lmagan yechimlari orasidan Z=0+х₄-х₅ (2) funksiyaga minimum qiymat beruvchi yechimini toping.
Yechish. Jadval tuzish uchun (1) va (2) ni

x1+x4-2x5=1

x2-2x4+x5=2

x3+3x4+x5=3

z-x4+x5=0

ko’rinishda yozib olamiz. (1) sistemani x₁,x₂,x₃ ga nisbatan osongina yechish mumkin. Shuning uchun bu noma‘lumlarni sistemaning bazis noma‘lumlari deb qabo’l qilamiz.
Bazis noma‘lumlar x₁,x₁,x₂ va z larni jadvalning 1 chi ustuniga, ozod xadlarni 2 chi ustuniga, x₁ ning koeffitsientlarini 3 chi ustunga va x₀,x₅ ning koeffitsientlarini oxirgi ustunga yozib quyidagi 1- jadvalga ega bo’lamiz.

Bazis noma‘lum.	Erkli noma‘lumlar		Ozod xadlar
	-X4	-X5
X1	1	-2	1
X2	-2	1	2
X3	3	1	3
Z	-1	1	0

Minimumni (maksimumni) topish talab etilayotganligi uchun Z satrdagi musbat (manfiy) koeffitsientlardan absolyut qiymat jixatidan eng kattasini tanlab olamiz. Bizning misolimizda x₅ ustundagi 1 soni bo’ladi. Ozod xadlar ustunidagi koeffitsientlari shu ustundagi mos musbat koeffitsientlar bo’lgan nisbatini eng kichigini tanlab olamiz.
min { 2/1;3/1} =2
Shu ustunni hal qiluvchi ustun qilib olamiz. Hal qiluvchi ustun va satr kesishmasida turgan element bosh element deyiladi. Keyingi jadval quyidagi tartibda to’ldiriladi.
1) х₂ va х₅ larning urni almashtirib yoziladi.
2) Bosh element o’ziga teskari miqdor bilan almashtiriladi.
3) Hal qiluvchi ustun bosh elementga bo’linib teskari ishora bilan yo’ziladi.
4) Hal qiluvchi satr elementlari bosh elementga bo’lib yoziladi.
5) Qolgan barcha elementlar to’rtburchak formulasi bilan topiladi.
2 - jadval.

Bazis noma‘lumlar	Erkli noma‘lumlar		Ozod xadlar
	-x4	-x2
X1	-3		5
X5	-2	1	2
X3	5	-1	1
Z	1	-1	-2

Z satrdagi barcha koeffitsientlar manfiy (musbat) chiqsa optimal yechim topilgan bo’ladi, ammo jadvalning bu satrida 1 musbat koeffitsient bor.

min {1/5} =1/5
3 - jadval

Bazis noma‘lumlar	Erkli noma‘lumlar		Ozod xadlar
	-x3	-x2
X1	-0,6	2,6	4,4
X5	0,4	0,6	2,4
X4	0,2	-0,2	0,2
Z	0,2	0,8	-2,2

Bu jadvalda optimal reja topildi. х₁=4,4, х₅=2,4, х₄=0,2, х₃=х₂=0 da

Z_min= -2,2 bo’ladi.
SAVOLLAR.
1.Chiziqli dasturlashtirish qanday masalalar.?
2.Bosh element qanday tanlab olinadi?
3.Hal qiluvchi ustun qanday tanlab olinadi?
4.Hal qiluvchi satr elementlari qanday topiladi?
5.Simpleks jadval usulida qachon masala optimal yechimga erishgan deyiladi?
6.Jadvalda ozod xad manfiy bo’lishi mumkinmi?
7.Erkli noma‘lumlar qanday qiymatga ega bo’ladi?
8.Bazis noma‘lumlar qiymati qanday topiladi?
9.Maqsad funksiyaning qiymati nimaga teng bo’ladi?