Chiziqli programmalash masalasini simpleks usulida yechish

Sun’iy bazis vektor usuli

Yuqorida biz chiziqli programmalash masalasining boshlang‘ich tayanch plani mavjud va boshlang‘ich planni tuzish mumkin bo‘ladigan m-o‘lchovli birlik matritsa masala shartida qatnashadi deb faraz qildik. Bu birlik matritsa yordami bilan optimal planga o‘tishga yordam beradigan planni tuzish mumkin. Agar chiziqli programmalash masalasining chegaraviy shartlari ko‘rinishda berilgan bo‘lsa, qo‘shimcha o‘zgaruvchilar kiritish yo‘li bilan birlik matritsani masala shartiga kiritish mumkin.

Amalda uchraydigan ko‘p chiziqli programmalash masalalari planga ega bo‘lgan holda birlik matritsani o‘z ichiga olmaydi. Bunday masalalarni yechish uchun «sun’iy bazis vektor» usul qo‘llaniladi.
Umumiy holda berilgan chiziqli programmalash masalasini ko‘ramiz:
(40)
. (41)
, (42)
bu yerda , ( ) va sistema birlik matritsani o‘z ichiga olmaydi. Masalaning shartiga birlik matritsani kiritish uchun sistemadagi har bir tenglamaga sun’iy o‘zgaruvchi deb ataluvchi , ( ) no’malumni mos ravishda qo‘shamiz hamda
funksiyani minimallashtirish bilan bog‘liq bo‘lgan qo‘yidagi kengaytirilgan masalani hosil qilamiz:
(43)
(44)
(45)
bu yerda M soni larga nisbatan katta musbat son. sun’iy o‘zgaruvchilarga mos keluvchi vektorlar sun’iy bazisni tashkil qiladi. Berilgan (40), (42) masalaning optimal yechimini topish uchun quyidagi teoremadan foydalanamiz.
Teorema. Agar kengaytirilgan (40)-(45) masalaning

optimal planida

bo‘lsa, plan berilgan (40)-(42) masalaning optimal plani bo‘ladi.

Misol .



Bu masalaning shartida birlik vektor qatnashganligi uchun ikki va sun’iy vektorni kiritamiz va ni ga aylantirib quyidagi kengaytirilgan masalani yechamiz:



Masalaning berilganlarini simpleks jadvalga joylashtiramiz:
1-i t ye r a s i ya

	B. v	S		-1	-2	-3	1	M	M
1 2 3		M M 1	15 20 10	1 2 1	2 1 2	3 5 1	0 0 1	1 0 0	0 1 0
4			10	2	4	4	0	0	0
5			35	3	3	8	0	0	0

va larning qiymatini hisoblaymiz, bu yerda chiziqli funksiyaning boshlang‘ich plandagi qiymati:




soni oldindan tayinlangan bo‘lmasa, har bir ni ning chiziqli funksiyasi, ya’ni ko‘rinishda ifodalash mumkin. Jadvalning - qatoriga ning ga bog‘liq bo‘lmagan qismi, ya’ni ni va katoriga ning ga bogliq bulgan qismi, ya’ni ni joylashtiramiz. Bazisga qatorning eng katta musbat elementi (8) ga mos kelgan vektor kiritilib, bazisdan

nisbatga mos keluvchi vektor chiqariladi. Ikkinchi qator uchinchi qator ustunning kesishgan joyida joylashgan son (5) ni aniqlovchi element deb qabul qilamiz va simpleks jadvalni (37), (8) va (39) formulalar orqali almashtiramiz. Natijada u quyidagi ko‘rinishga keladi:

2-i t ye r a s i ya

	B. v	S		-1	-2	-3	1	M	M
1		M	3			0	0	1
2		-3	4			1	0	0
3		1	6			0	1	0
4			-6			0	0	0
5			3			0	0	0

Bu interatsiyada bazisga beshinchi qatorning eng katta musbat elementi ga mos keluvchi vektor kiritilib, bazisdan

nisbatni beruvchi vektor chiqariladi. soni aniqlovchi element bo‘ladi. Yana qaytadan (38) – (39) formulalarni qo‘llab, simpleks jadvalni almashtirib quyidagi ko‘rinishga keltiramiz:

3 - iteratsiya

	B. v	S		-1	-2	-3	1	M	M
1		-2			1	0	0
2		-3			0	1	0
3		1			0	0	1
4					0	0	0
5					0	0	0	-1	-1

Agar matritsaga teskari matritsa ni topish kerak bo‘lmasa, bazisdan chiqarilgan sun’iy vektorlarni simpleks jadvaldan tashlab yuborish mumkin.

Uchinchi iteratsiyadagi simpleks jadvalning 5-qatorida musbat elementlar qolmadi, demak sun’iy vektorlar bazisdan chiqarilib, masalaning tayanch plani

topildi. Bu planga mos kelgan chiziqli funksiyaning qiymati:

lekin ko‘rinib turibdiki bu tayanch plan optimal plan emas, chunki jadvalning -qatorida ham musbat elementlar bor. Endi bazisga kiritiladigan vektorni 4-qator bo‘yicha tanlaymiz. U holda ga mos keluvchi vektorni bazisga kiritib, aniqlovchi elementga to‘g‘ri keluvchi ni bazisdan chiqaramiz va simpleks jadvalni almashtiramiz. Natijada u quyidagi ko‘rinishga keladi:

4 - iteratsiya

	B. v	S		-1	-2	-3	1	M	M
1		-2		0	1	0
2		-3		0	0	1			0
3		1		1	0	0
4			-15	0	0	0	-1	-1	0

4-iteratsiyada

optimal yechim topiladi, chunki 4-qatordagi barcha . Topilgan plandagi chiziqli funksiyaning qiymati:

va


Nazorat savollari:
1. Simpleks usulining moxiyati.
2. Optimallik kriteriysi. Optimal yechimni topish.
3. Simpleks usuli algoritmi.
4. Sun’iy bazis vektor usulini tushuntiring.