Ii-bob. Chiziqli programmalashtirish masalasining simpleks algoritmi

Teorema. Tenglamalar sistemasining barcha ozod hadlari nomanfiy bo‘lsa, u holda simpleks almashtirishdan so‘ng ham sistemaning ozod hadlari nomanfiy bo‘lib qoladi.
Isbot. Aytaylik, (2.2.2) ning j – nchi ustunida musbat element bo‘lsin. Bu element bo‘lsin va nisbat ozod hadlarni o‘zlariga mos musbat elementlariga nisbati ichida eng kichigi bo‘lsin. ni aniqlovchi element sifatida qabul qilamiz. Keyingi jadvalga o‘tamiz (2.2.3):

Bazis o‘zgaruchilar		Ozod hadlar
			(2.2.3)

Bunda . Ammo , shuning uchun . Har qanday boshqa elementni qaraymiz.

Agar bo‘lsa, u holda . Agar bo‘lsa, u holda ni quyidagicha qaraymiz.
.

Teorema shartiga ko‘ra , demak va demak, .

Shuni isbotlash talab etilgan edi. Shunday qilib, agar ozod hadlari musbat bo‘lgan chiziqli tenglamalar sistemasini yechishda simpleks almashtirish bajarilsa, u holda hosil qilingan bazis yechim nomanfiy bo‘ladi (agar sistemaning nomanfiy bazis yechimi mavjud bo‘lsa). Aslida simpleks almashtirishni ketma-ket amalga oshirish natijasida biz quyidagi sistemaga kelamiz.

Bu yerdan ma’lumki, larni nolga teng deb olib bazis yechimga ega bo‘lamiz.

Agar hech bo‘lganda bitta nomanfiy bazis yechim topilgan bo‘lsa, u holda simpleks almashtirish yordamida boshqa nomanfiy bazis yechimga o‘tiladi (agar u bor bo‘lsa).
2.1-masala. Ushbu chiziqli tenglamalar sistemasining barcha nomanfiy yechimlarini toping:





<sub>Yechish. Barcha ozod hadlarni nomanfiy holga keltiramiz.





Dastlabki jadvalni tuzamiz. Hal qiluvchi element sifatida 4-nchi ustundan 3 ni tanlaymiz:</sub>

Bazis o‘zgaruvchilar		Ozod hadlar		(1)
		3 8 7
Bazis o‘zgaruvchilar			Ozod hadlar	(2)
			1 6 2

Bazis o‘zgaruvchilar		Ozod hadlar	(3)

<sub>Nomanfiy bazis yechimga ega bo‘ldik.

qolgan nomanfiy bazis yechimlarni topamiz.</sub>
(3) nchi jadvaldan 5-nchi ustunning elementini olish yoki 3-chi ustundan 1 ni olish ham mumkin.

Bazis o‘zgaruvchilar		Ozod hadlar	(4)

Bazis yechim: .

Keyingi bazis yechimni topish uchun (3) jadvaldan 1 ni hal qiluvchi element qilib olamiz.

Bazis o‘zgaruvchilar		Ozod hadlar	(5)

Bazis yechim: .
(4) va (5) jadvaldan ko‘rinib turibdiki, boshqa bazis yechim yo‘q.
2.2-masala. Ushbu chiziqli tenglamalar sistemasining barcha nomanfiy bazis yechimlarini toping.

_Yechish.

Bazis o‘zgaruvchilar		Ozod hadlar
Bazis o‘zgaruvchilar		Ozod hadlar

Bazis o‘zgaruvchilar		Ozod hadlar

Bazis o‘zgaruvchilar		Ozod hadlar

_{boshqa bazis yechim yo‘q.}

2.2. Standart ko‘rinishdagi masalani simpleks usulda yechish

Simpleks metodni birinchi bo‘lib 1949-yilda amerikalik olim D.Dansig tomonidan kiritilgan. Uning asosiy g‘oyasi 1939-yilda sovet olimi L.V.Kantorovich tomonidan ishlab chiqilgan.

Simpleks metod yordamida har qanday chiziqli program­malashtirish masalasini yechish mumkin, ya’ni bu metod universal metod hisoblanadi. Hozirgi paytda bu metoddan kompyuter hisoblarda foydalaniladi, ba’zan oddiy masalalarni qo‘lda, simpleks usulni qo‘llab yechish mumkin.
Simpleks metodni amalga oshirishda uchta asosy elementni o‘zlashtirish lozim:

1. 
   Boshlang‘ich joiz bazis yechimni topish usulini aniqlash;
   
2. 
   Yaxshi yechimga o‘tish (yomon bo‘lmagan) qoidasini o‘zlashtirish;
   
3. 
   Topilgan yechimni optimallik kriteriyasini tekshirish.
   

Simpleks metoddan foydalanganda chiziqli programmalashtirish masalasi kanonik holga keltirilishi kerak, ya’ni o‘zgaruvchilarga qo‘yilgan cheklov shartlari tenglamalar ko‘rinishida bo‘lishi lozim.
Simpleks usulda hisoblash algoritmini misollarda ko‘ramiz.


Chiziqli funksiyani maksimumini izlash

2.1-misol. Ushbu masalani simpleks usulda yeching.

_{Yechish. Nomanfiy qo‘shimcha o‘zgaruvchilarni kiritib, standart ko‘rinishdagi masalani kanonik ko‘rinishida yozib olamiz.}
Bu masalada barcha tengsizliklar ko‘rinishda bo‘lganligi uchun yordamchi o‘zgaruvchilarning barchasi “plyus” ishorada kiritiladi.
Cheklov tengsizliklarini quyidagi ko‘rinishda yozamiz:

_{Boshlang‘ich bazis yechimlarni topish uchun o‘zgaruvchilarni ikki guruhga ajratamiz – bazis va bazis bo‘lmagan o‘zgaruvchilar.}
Bizning misolda larni bazis o‘zgaruvchi qilib olamiz, chunki bu o‘zgaruvchilar faqat bitta tenglamada ishtirok etmoqda.
Simpleks jadvalini tuzamiz.
2.2.1-jadval

BU							OH
	1	3	1	0	0	0	18
	2	1	0	1	0	0	16
	0	1	0	0	1	0	5
	3	0	0	0	0	1	21
	-2	-3	0	0	0	0	0

_{BU – bazis o‘zgaruvchi, OH – ozod had.}
Boshlang‘ich bazis yechim bu yechim joiz yechim.
F ning qiymatini oshirish uchun va o‘zgaruvchilarning katta koeffitsiyentlarini tanlaymiz. Demak, koeffitsiyenti tanlanadi. Aniqlovchi elementni belgilaymiz.

ni bazisdan chiqaramiz va bazisga ni kiritamiz.

2.2.2-jadval

BU							OH
	1	0	1	0	-3	0	3
	2	0	0	1	-1	0	11
	0	1	0	0	1	0	5
	3	0	0	0	0	1	21
	-2	0	0	0	3	0	15

Aniqlovchi elementi o‘rnida 1 hosil qilib, undan boshqa shu ustundagi barcha elementar nolga aylantiriladi. 2.2.2-jadvalning oxirgi satri, birinchi ustunda – 2 bo‘lganligi uchun, shu ustun aniqlovchi ustun bo‘ladi.

o‘zgaruvchi o‘rniga bazisga kiradi.
2.2.3-jadval

BU							OH
	1	0	1	0	-3	0	3
	0	0	-2	1	5	0	5
	0	1	0	0	1	0	5
	0	0	-3	0	9	1	12
	0	0	2	0	-3	0	21

Hosil qilingan yechim ham optimal emas, chunki maqsad funksiya koeffitsiyentlarida bitta manfiy element – 3 bor.
Keyingi jadvalga o‘tamiz,

bazisga kiradi. Aniqlovchi element 5 uning o‘rnida 1 hosil qilamiz va shu ustun elementlarini (aniqlovchi elementdan boshqa) nolga aylantiramiz.

2.2.4-jadval

BU							OH
	1	0			0	0	6
	0	0			1	0	1
	0	1			0	0	4
	0	0			0	1	3
	0	0			0	0	24

Optimallik sharti bajarildi, oxirgi satrda maqsad funksiya o‘zgaruvchilari oldidagi koeffitsiyentlar ichida manfiylari qolmadi. (2.2.4-jadval)

Maqsad funksiya bazis bo‘lmagan o‘zgaruvchilar orqali bog‘landi. Optimal yechim

Demak, optimallik kriteriyasini umumiy holda bayon qilish mumkin. Agar masalada chiziqli funksiyaning maksimum izlanayotgan bo‘lsa, chiziqli funksiya bazis bo‘lmagan o‘zgaruvchilar orqali ifoda etilganda ularning koeffitsiyentlari ichida musbat elementlar, u holda bazis yechim optimal bo‘ladi.


_{Chiziqli funksiyani minimumini izlash}


Z chiziqli funksiyaning minimumini izlashning ikki yo‘li mavjud:
1. deb olib va ekanligini hisobga olib F funksiyaning maksimumini izlash.
2. Har bir qadamda maqsad funksiya qiymatini chiziqli funksiya ifodasiga kiruvchi manfiy koeffitsiyentli bazis bo‘lmagan o‘zgaruvchi hisobiga kamaytirib borish yo‘li bilan.
Buni quyidagi misolda ko‘ramiz.
2.2-misol. Ushbu masalani simpleks usulda yeching.

_{shartlarni qanoatlantiruvchi F funksiya minimumini toping, ya’ni}