Ii-bob. Chiziqli programmalashtirish masalasining simpleks algoritmi

Yechish. Standart masalani kanonik ko‘rinishga keltiramiz.

_{Simpleks jadvalni tuzamiz.}

BU							OH
	-1	-1	-2	1	0	0	5
	2	-3	1	0	1	0	3
	2	-5	0	0	0	1	5
	1	-3	-2	0	0	0	0

BU							OH
	0			1		0
	1			0		0
	0	-2	5	0	-1	1	2
	0			0		0

<sub>BU – bazis o‘zgaruvchilar
OH – ozod hadlar
Simpleks jadvaldan foydalanib masalaning optimal yechimini aniqlaymiz.

Minimum masalasini izlashda optimallik kriteriyasini bayon qilamiz:
Agar maqsad funksiya ifodasida bazis bo‘lmagan o‘zgaruvchilar oldidagi koeffitsiyentlar ichida manfiy bo‘lmaganlari bo‘lmasa, yechim optimal bo‘ladi. Bizning misolda
.


Simpleks metod algoritmi


1. Yordamchi o‘zgaruvchilarni kiritib chiziqli tenglamalar sistemasini kengaytirilgan sistema ko‘rinishida yozib olamiz:

Bu yerda yordamchi o‘zgaruvchilar ishorasi ozod hadlar ishorasi bilan bir xil bo‘ladi, aks holda sun’iy bazis usulidan foydalaniladi.
2. Kengaytirilgan sistemani dastlabki simpleks jadvaliga joylashtiramiz. Jadvalning oxirgi satrida maqsad funksiya koeffit­siyentlari joylashtirilgan. Masalani optimal yechimini, masalan maksi­mumini topishda, optimallik kriteriyasini bajarilishini tekshira­miz, agar jadvalning oxirgi satrida manfiy koeffitsiyentlar bo‘lmasa, u holda yechim optimal bo‘lib, uning qiymati jadvalning oxirgi ustuni va oxirgi satri kesishgan joyda bo‘ladi.
3. Agar optimallik kriteriyasi bajarilmasa, u holda oxirgi satrdagi manfiy koeffitsiyentni modul bo‘yicha eng katta hal qiluvchi ustun S ni aniqlaydi.
Har bir satr uchun baholash chegaralarini tuzamiz:</sub>

1. 
   agar va turli ishorali bo‘lsa, ;
   
2. 
   agar va bo‘lsa, ;
   
3. 
   agar bo‘lsa, ;
   
4. 
   agar va bo‘lsa, 0;
   
5. 
   agar va bir xil ishoraga ega bo‘lsa,
   

ni aniqlaymiz. Agar chekli minimum bo‘lmasa, u holda chekli minimum bo‘lmasa, u holda chekli optimumga ega bo‘lmaydi . Agar minimum chekli bo‘lsa, u holda q satrni tanlaymiz va uni ham hal qiluvchi satr deb ataymiz. Hal qiluvchi ustun va hal qiluvchi satr kesishmasida element hal qiluvchi element bo‘ladi.
4. Navbatdagi jadvalga quyidagi qoida bo‘yicha o‘tamiz: chap ustunda yangi bazisni kiritamiz:
a) bazis o‘zgaruvchi o‘rniga ni kiritamiz;
b) bazis o‘zgaruvchiga mos ustunlarda nollar va 1 qo‘yamiz. O‘zining qarshisida 1, boshqa o‘zgaruvchilar qarshisida nollar qo‘yiladi;
d) q nomerli yangi satrni hal qiluvchi elementga bo‘lish yo‘li bilan aniqlaymiz;
e ) qolgan barcha elementlarni to‘g‘ri to‘rtburchak qoidasiga ko‘ra hisoblaymiz:




va shu yo‘sinda algoritmga o‘tamiz.


2.3. Sun’iy bazis usuli


_{Kanonik holga keltirilgan chiziqli programmalashtirish masala­sining o‘zgaruvchilariga qo‘yilgan cheklovlar sistemasining boshlan­g‘ich yechimi joiz bo‘lmasa, bunday holda masalani simpleks jadval yordamida yechganda M – metod yoki sun’iy bazis usulidan foydalanish qo‘llay bo‘ladi. Bu metodni bayon qilamiz.
Bazis yechimda manfiy yechim beradigan har bir tenglamaga nomanfiy} sun’iy o‘zgaruvchilarni ozod hadlar qanday ishorada bo‘lsa xuddi shunday ishorada kiritamiz. Yangi chiziqli funksiyani kiritamiz, bunday M – ixtiyoriy katta son va uning maksimumini izlaymiz (1-masala). ifodani M – funksiya deb yuritamiz. Quyidagi teorema o‘rinli (isbotini keltirmaymiz).
1. Agar f –masalaning optimal yechimida barcha sun’iy o‘zgaruvchilar nolga teng bo‘lsa, u holda unga mos boshqa o‘zgaruvchilar dastlabki masalaning optimal yechimini beradi agar , ya’ni M –funksiyaning minimumi 0 ga teng.
2. Agar f masalaning optimal yechimida hech bo‘lmaganda bitta sun’iy o‘zgaruvchi noldan farqli bo‘lsa, u holda dastlabki masalaning cheklovlar sistemasi ham joyni bo‘lmaydi.
3. Agar bo‘lsa, u holda dastlabki masala yechimga ega emas, yo , yoki masalaning sharti ziddiyatga ega bo‘ladi.
Teorema shartidan kelib chiqadiki, dastlab M – funksiyaning minimumi topiladi. Agar u nolga teng bo‘lsa va barcha sun’iy o‘zgaruvchilar nolga aylansa, u holda bu o‘zgaruvchilar tashlab yuboriladi va joiz bazis yechimlar hosil bo‘ladi. Hosil bo‘lgan masalani optimal yechimi topiladi. Amaliyotda M –funksiyani minimumi emas, balki funksiyaning maksimumi topiladi.