Chiziqli programmalashda ikkilangan masala

2. Simmetrik bo‘lmagan ikkilangan masalalar

Simmetrik bo‘lmagan ikkilangan masalalarda berilgan masaladagi chegaralovchi shartlar tenglamalardan, ikkilangan masaladagi chegaralovchi shartlar esa tengsizliklardan iborat bo‘ladi. Masalan, simmetrik bo‘lmagan ikkilangan masalalarning matritsali ifodasi quyidagicha bo‘ladi.

Berilgan masala.
(6)
(7)
(8)
ya’ni (6) va (7) shartlarni qanoatlantiruvchi shunday vektor ustunni topish kerakki, u (8) chiziqli funksiyaga minimal qiymat bersin.
Ikkilangan masala.
(9)
(10)
ya’ni (9) shartlarni qanoatlantiruvchi shunday vektor qatorni topish kerakki, u (10) chiziqli funksiyaga maksimal qiymat bersin.
Ikkala masalada ham vektor - qator, vektor – ustun, - chegaralovchi shartlarning koeffitsiyentlaridan tashkil topgan matritsa. Bu masalalarning optimal yechimlari o‘zaro quyidagi teorema asosida bog‘langan.
Teorema. Agar berilgan masala yoki unga ikkilangan masaladan birortasi optimal yechimga ega bo‘lsa, u holda ikkinchisi ham yechimga ega bo‘ladi hamda bu masalalardagi chiziqli funksiyalarning ekstremal qiymatlari o‘zaro teng bo‘ladi, ya’ni
(11)
agar bu masalalardan birining chiziqli funksiyasi chegaralanmagan bo‘lsa, u holda ikkinchi masala hech qanday yechimga ega bo‘lmaydi.
1 – m i s o l .
Berilgan masala.
(12)
(13)
(14)
Bu yerda ustun matritsa.
,

matritsa matritsaga transponirlangan.
Ikkilangan masala.
(15)
(16)
Berilgan masalani simpleks usul bilan yechamiz.
I.

B.v	S		0	1	-3	0	2	0
	0	7	1	3	-1	0	2	0
	0	12	0	-2	[ 4 ]	1	0	0
	0	10	0	-4	3	0	8	1
		0	0	-1	[ 3 ]	0	-2	0

II.

	0	10	1		0		2	0
	-3	3	0		1		0	0
	0	1	0		0		8	1
		-9	0		0		-2	0

III.

B.v	S		0	1	-3	0	2	0
	1	5		1	0			0
	-3	4		0	1			0
	0	11	1	0	0		10	1
		-11		0	0			0

III iteratsiyadan so‘ng berilgan masalaning optimal yechimi

topildi. Bu yechimdagi (14) chiziqli funksiyaning qiymati

Ikkilangan masalaning yechimini

formula orqali topamiz. Oxirgi simpleks jadvaldan: - vektor qator va

teskari matritsani aniqlaymiz. ( matritsa oxirgi simpleks jadvalda birinchi simplek jadvaldagi birlik matritsa o‘rnida hosil bo‘ladi). Demak,

Shunday qilib, ikkilangan masalaning optimal yechimi:

ya’ni

bo‘lib, unga mos keluvchi (16) chiziqli funksiyaning qiymati


3. Simmetrik ikkilangan masalalar

Simmetrik ikkilangan masalalarning simmetrik bo‘lmagan ikkilangan masalalardan farqi shundan iboratki, berilgan va ikkilangan masaladagi chegaralovchi shartlar tengsizliklardan iborat bo‘ladi va ikkilangan masaladagi ma’lumotlarga manfiy bo‘lmaslik sharti qo‘yiladi.

Berilgan masala.
(17)
(18)
(19)
(17) va (18) shartlarni qanoatlantiruvchi shunday vektor ustunni topish kerakki, u (19) chiziqli funksiyaga minimal qiymat bersin.
Ikkilingan masala.
(20)
(21)
(22)
(20) va (21) shartlarni qanoatlantiruvchi shunday vektorni topish kerakki, u (22) chiziqli funksiyaga maksimal qiymat bersin. Tengsizliklar sistemasini qo‘shimcha o‘zgaruvchilar yordami bilan tenglamalar sistemasiga aylantirish mumkin. Shuning uchun simmetrik ikkilangan masalalarni simmetrik bo‘lmagan ikkilangan masalaga aylantirish mumkin. Demak, simmetrik bo‘lmagan ikkilangan masalalarning yechimlari haqidagi teorema simmetrik ikkilangan masalalar uchun ham o‘z kuchini saqlaydi.
Simmetrik ikkilangan masalalarni yechish uchun ulardan qulay bo‘lgan ixtiyoriy birini yechib, ikkinchisining yechimini yuqorida ko‘rgan usul bilan aniqlash mumkin.
M i s o l .
Berilgan masala.
(23)
(24)
(25)
Bu masalaga ikkilangan masalani tuzishdan avval chegaralovchi shartlarni bir xil ko‘rinishdagi tengsizliklarga keltiramiz. Buning uchun ikkinchi tengsizlikning belgisini almashtiramiz:



Hosil bo‘lgan masalaga ikkilangan masalaning ko‘rinishi quyidagicha bo‘ladi:



Ikkilangan masalani kanonik formaga keltirib, simpleks usul bilan yechamiz:
I.

B.v.	C		-2	-3	-6	-3	0	0	0
	0	1	2	-1	1	2	1	0	0
	0	2	2	1	1	1	0	1	0
	0	3	-1	4	-2	-2	0	0	1
		0	2	3	[ 6 ]	3	0	0	0

II.

	-6	1	2	-1	1	2	1	0	0
	0	1	0	2	0	-1	-1	1	0
	0	5	3	2	0	2	2	0	1
		-6	-10	[ 9 ]	0	-9	-6	0	0

III.

	-6		2	0	1	3/2	1/2	1/2	0
	-3		0	1	0	-1/2	1/2	1/2	0
	0	4	3	0	0	3	3	-1	1
			-10	0	0	-9/2	-3/2	-9/2	0

III iteratsiyadan so‘ng ikkalangan masalaning optimal yechimi, ya’ni topiladi. Bu yechimdagi chiziqli funksiyaning qiymati:

oxirgi simpleks jadvaldan ko‘rinadiki


Demak, berilgan masalaning optimal yechimi:

ya’ni

bo‘ladi.
Bu yechimdagi chiziqli funksiyaning qiymati:
ga teng bo‘ladi.

8-Ma’ruza. Ikkilangan simpleks usul

Bu paragrafda biz chiziqli programmalash masalasining ikkilanish nazariyasiga asoslangan va ikkilangan simpleks usul deb ataluvchi usul bilan tanishamiz.

Ikkilangan simpleks usul oddiy simpleks usulga nisbatan ba’zi qulayliklarga ega:
1) ikkilangan simpleks usul bo‘yicha yechilayotgan masala shartlaridagi ozod hadlar musbat bo‘lmasligi ham mumkin;
2) ikkilangan simpleks usul bilan bir vaqtning o‘zida ham berilgan masalaning hamda ikkilangan masalaning yechimi topiladi yoki ikkala masalaning yechimi mavjud emasligi aniqlanadi;
3) berilgan masalaning chegaralovchi shartlari belgi bilan bog‘langan yoki uning ba’zi ozod hadlari manfiy bo‘lgan masalalarni, ikkilangan simpleks usul bilan yechganda bajariladigan hisoblash ishlarining soni kamayadi;
4) ikkilangan simpleks usul bilan ishlab chiqarishning ba’zi zarur tavsiflarini aniqlash mumkin. Masalan, bir vaqtning o‘zida ham ishlab chiqarish planini, ham ishlab chiqarishga sarf qilinadigan hamma vositalarning bahosini hisoblash mumkin.
Oddiy simpleks usul singari ikkilangan simpleks usulning har bir iteratsiyasida - o‘lchovli vektor almashib boradi. Faqat, shunga e’tibor berish kerakki, simpleks usuldan farqli ravishda, ikkilangan simpleks usul bilan topilgan - o‘lchovli vektor tayanch plan bo‘lmasligi mumkin, ya’ni yoyilmadagi musbat koeffitsiyentlar bilan kiruvchi vektorlar chiziqli bog‘liq bo‘lib qolishi mumkin.
Bunday planni chala tayanch plan deb ataymiz.
Ikkilangan simpleks usul bo‘yicha chala tayanch planlarni almashtirish protsessi tayanch plan topilguncha takrorlanadi. Topilgan tayanch plan esa masalaning optimal plani bo‘ladi.
Geometrik nuqtai nazaridan chala tayanch planlar ketma-ketligi berilgan chiziqli programmalash masalasi planlaridan tashkil topgan qavariq sohaning tashqarisida yotuvchi chiziqlardan iborat bo‘ladi va har bir plan ga nisbatan to‘plamga yaqinroq joylashgan bo‘ladi (1 - shakl).

1-shakl
to‘plamning bo‘sh to‘plam ekanligi aniqlanadi yoki chekli sondagi iteratsiyadan so‘ng, shunday nuqta topiladiki, u berilgan masalaning tayanch plani va demak, optimal plani bo‘ladi.

Faraz qilaylik, kanonik formadagi chiziqli programmalash masalasi berilgan bo‘lsin
(26)
(27)
(28)
Bu masalaga ikkilangan masala quyidagicha bo‘ladi:
(29)
(30)
Berilgan masalaning (26) shartini qanoatlantiruvchi chala tayanch plan berilgan bo‘lsin deb faraz qilamiz. vektorning noldan farqli bo‘lgan elementlariga mos keluvchi vektorlar o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar bo‘ladi. O‘zaro chiziqli bog‘liq bo‘lmagan ta vektorlar sistemasini berilgan chala tayanch plandagi bazis deb ataymiz.
Chala tayanch plan uchun
(31)
tengsizlik o‘rinli bo‘lsin. U holda

vektor ikkilangan masalaning tayanch plani bo‘ladi. Bu plandagi (30) chiziqli funksiyaning qiymati

formula orqali aniqlanadi. (31) shartni qanoatlantiruvchi chala tayanch plan uchun quyidagi teoremani isbotlaymiz.
1 – teorema. Agar chala tayanch plan (26) – (28) masalaning tayanch plani bo‘lsa, u optimal plan ham bo‘ladi.
Isbot. Teoremaning shartiga ko‘ra barcha hamda - tayanch plan. Demak uning barcha elementlari 5-ma’ruzadagi ko‘rilgan 2-teoremaga asosan plan optimal plan bo‘ladi. Shu bilan teorema isbot qilindi.
Endi chala tayanch plan ni yangi chala tayanch plan ga almashtirish protsessii bilan tanishamiz.
Faraz qilaylik, vektorga mos keluvchi bazis

bo‘lsin. Bu matritsaga teskari bo‘lgan matritsaning qatorlarini bilan belgilaymiz. U holda vektorning elementlari

formula orqali aniqlanadi. Agar barcha lar uchun bo‘lsa, - tayanch plan bo‘ladi. Faraz qilaylik bo‘lsin. U holda vektorni bazisdan chiqarish kerak. Bazisga kirmagan vektorlar uchun o‘rinli bo‘ladi. Endi kamida bitta deylik. Barcha lar uchun ni hisoblaymiz.
Agar

bo‘lsa, vektor bazisga kiritiladi. Natijada yangi

bazis matritsa kelib chiqadi.
Bu bazisga mos keluvchi yangi

chala tayanch planning komponentalari ma’lumki
(*)
formulalar orqali topiladi. Bu formulalar

formulaga ekvivalentdir. Yangi bazisga mos keluvchi ikkilangan masalaning yechimi

formula orqali topiladi. planga mos keluvchi chiziqli funksiyaning qiymati quyidagiga teng bo‘ladi:
.
Agar planning barcha elementlari musbat bo‘lsa, u optimal plan ham bo‘ladi. Aks holda, yana bazisdan chiqariladigan vektor aniqlanadi. Agar barcha bo‘lsa, berilgan masala va unga ikkilangan masala yechimga ega bo‘lmaydi. Agar ba’zi lar uchun bo‘lsa u holda

shartni qanoatlantiruvchi vektor bazisga kiritiladi. Simpleks jadval bizga ma’lum bo‘lgan (*),
(**),
(***),
(****)
formulalar orqali almashtiriladi. Shunday qilib, chala tayanch planlarni almashtirish protsessi berilgan va ikkilangan masalaning optimal plani topilguncha takrorlanadi.
Ikkilangan simpleks usulga doir bo‘lgan quyidagi teoremalarni isbotsiz keltiramiz.
2-teorema. Agar (26) – (28) masalaning chala tayanch planining komponentlaridan kamida bittasi, masalan bo‘lib, barcha lar uchun bo‘lsa, berilgan masala tayanch planga ega bo‘lmaydi.
3-teorema. Agar topilgan chala tayanch plan uchun bo‘lganda, bo‘lib, kamida bitta bo‘lsa, u holda ni yangi chala tayanch plan ga almashtirish natijasida chiziqli funksiyaning qiymati kamayadi. vektorni ga almashtirish uchun bazisdan vektor chiqarilib, bazisga quyidagi shartlarni qanoatlantiruvchi vektor kiritiladi:

va



Nazorat savollari
1. Simmetrik bo‘lmagan ikkilangan masalalar.
2. Simmetrik ikkilangan masalalar.
3. Ikkilangan simpleks usul.