7-mavzu. Chiziqsiz dasturlash masalalari 1-ma’ruza rejasi

AX=B (47)

2DX- ⁰+V+ =0, (48)
X V=0, (49)
X≥ 0, V≥ 0. (50)
shartlarni qanoatlantiruvchi har qanday X ≥ 0, V 0 vektorlar berilgan (23)-(24) masalaning yechimini bildiradi. Agar bu (47)-(50) sistema yagona yechimga ega bo’lsa, berilgan kvadratik dasturlash masalasi ham yagona (global) optimal yechimga ega bo’ladi. Agar (47)-(50) sistema birgalikda bo’lmasa, berilgan kvadratik dasturlash masalasi ham yechimga ega bo’lmaydi. Shunday qilib, berilgan (23)-(25) kvadratik dasturlash masalasini yechimini (47)-(50) sistemaning yechimi orqali topish mumkin. Bu sistemaning yechimini topish masalasi quyidagicha quyiladi: (47)-(48) tenglamalar sistemasining shunday nomanfiy (X≥0, ≥0) bazis yechimini topish kerakki, u X’V ko’paytmani nolga aylantirsin. Demak, xulosa qilib aytish mumkinki, agar kvadratik dasturlash masalasi ((23)-(25)) optimal yechimga ega bo’lsa, bu yechim (47)-(48) tenglamalar sistemasining bazis yechimlarining biridan iborat bo’ladi.
3-misol. Quyidagi kvadratik dasturlash masalasining yechimini Kun-Takker shartlaridan foydalanib toping:
x₁+2x₂≤ 13,
2x₁+x₂≤ 9,
x₁≥0, x₂≥0, (51)

Yechish. Lagranj funktsiyasini tuzamiz:


Bu funktsiyadan x₁, x₂, va lar bo’yicha xususiy hosilalar olamiz:

Endi Kun-Takker shartlarini yozamiz:
(52)


(53)

(52) sistemaning yechimlari orasidan (53) ni qanoatlantiruvchisini aniqlash kerak. (52) sistemaga o’zgaruvchilar kiritib, uni quyidagi tenglamalar sistemasiga keltiramiz:

(54)
(53) ga asosan v₁, v₂, v₃, v₄ qo’shimcha o’zgaruvchilar quyidagi shartlarni qanoatlantirishi kerak:
x₁v₁ = 0, x₂v₂ = 0, ₁v₃ = 0, ₂v₄ = 0 (55)


(54) sistemaga w₁, w₂ sun’iy bazis o’zgaruvchilarni kiritb, uni quyidagi chiziqli dasturlash masalasi ko’rinishda ifodalaymiz:
(56)


. (57)
(56)-(57) masalani simpleks jadvalga joylashtiramiz (1-jadval). Buning uchun quyidagi belgilashlarni kiritamiz:


bu belgilashlarda hamma noma’lumlar simpleks jadvalga tartibda joylashtirilgan. Masalani simpleks usulda yechib, quyidagiga ega bo’lamiz:
.
Topilgan yechim (56)-(57) masalaning bazis yechimi bo’ladi. Bu yechim (55) shartlarni qanoatlantiradi:
,
shuning uchun u berilgan (51) kvadratik dasturlash masalasining yechimidan iborat.
1-jadval

B.B.	c^b	P0	0	0	0	0	0		0	0	0		M		M
			P1	P2	P3	P4	P5		P6	P7		P8		P9		P10
		8 44 13 9	8 -2 1 2	-2 12 2 1	1 2 0 0	2 1 0 0	-1 0 0 0	0 -1 0 0		0 0 1 0	0 0 0 1		1 0 0 0		0 1 0 0
		52M	6M	10M	3M	3M	-M	-M		0	0		0		0
P9 P2 P7 P8	M 0 0 0			0 1 0 0			-1 0 0 0			0 0 1 0	0 0 0 1		1 0 0 0
	0			0			-M			0	0		0
P1 P2 P7 P8	0 0 0 0	2 4 3 1	1 0 0 0	0 1 0 0						0 0 1 0	0 0 0 1
		0	0	0	0	0	0	0		0	0

3. Kvadratik dasturlash masalasini yechish uchun Barankin-Dorfman usuli

Barankin-Dorfman usuli (23)-(25) masalaning yechimini (40)-(43) sistemasini yechish orqali topishga mo’ljallangan bo’lib, uning g’oyasi quyidagidan iborat. Eng avval (40)-(41) sistemaning ixtiyoriy bazis rejasi topiladi. Bu bazis reja asosida qator simpleks almashtirishlar bajarib X B ko’paytmaning bazis qiymati kamaytirib boriladi. Natijada X B=0 tenglikka mos keluvchi bazis yechim topiladi. Faraz qilaylik, (40)-(43) sistemaning ixtiyoriy bazis yechimi topilgan bo’lsin. Bu holda bazis o’zgaruvchilar ozod o’zgaruvchilarning funktsiyasi sifatida ifoda qilinadi. Qulaylik uchun bazis o’zgaruvchilarni y_j bilan ( ), ozod o’zgaruvchilarni esa t_k lar bilan belgilaymiz. U holda quyidagilarga ega bo’lamiz:

(58)
yoki
(59)
Agar y_j o’zgaruvchi ozod o’zgaruvchi t_k ga mos qo’yilgan bo’lsa, u quyidagi ko’rinishda bo’ladi:


(60)

(59) belgilashlar yordamida noma’lumlarni quyidagi tartibda joylashtirish mumkin:

Bu holda bazis yechim uchun quyidagi munosabatlar o’rinli bo’ladi:
(61)
Endi faraz qilaylik, bazisga yangi o’zgaruvchi kiritilsin. U holda, agar qolgan o’zgaruchilarni nolga teng deb qaraganda bazis o’zgaruvchilarning qiymati quyidagiga teng bo’ladi:

t_k o’zgaruvchining qiymati quyidagicha tanlanadi:

Bunda yangi bazis yechim topilgan bo’ladi va bu yechim uchun quyidagi qiymatni qabul qiladi:

(62)
bu yerda
(63)
(64)
(65)
. (66)
Simpleks almashtirishlar natijasida T=X V ning qiymati kamaya borishi kerak. Shuning uchun bazisga R_k<0 ga mos keluvchi t_k o’zgaruvchi kiritiladi. Agar manfiy R_k lar bir nechta bo’lsa, u holda bazisga ga mos keluvchi t_k vektor kiritiladi.
Ma’lumki, ifoda T dan t_k bo’yicha olingan ikkkinchi tartibli hosilidan iborat. T qavariq bo’lganligi sababli har doim bo’ladi. Demak, R_k ishorasi a_k ning ishorasiga bog’liq bo’ladi. Shuning uchun a_k≥0 bo’lganda larni hisoblamaslik mumkin. Agar barcha t_k lar uchun T>0, R_k>0 bo’lsa, Barankin-Dorfman usulini qo’llab bo’lmaydi.
4-misol.

Bu masala uchun (40)-(43) sistema quyidagicha yoziladi:

Bu sistemaning boshlang’ich bazis yechimini aniqlaymiz. Buning uchun birinchi tenglamadan x₃ ni, ikkinchisidan x₄ ni, to’rtinchisidan v₂, beshinchisidan v₄ ni ajaratamiz hamda uchinchi tenglamani ga nisbatan yechamiz:
(67)
qiymatini v_2, v₄ larga mos keluvchi ifodalarga qo’yamiz.
Natijada quyidagilarga ega bo’lamiz:
(68)
(68) sistemaga

tenglamalarni qo’shib to’ldiramiz va 9.2-jadvalga joylashtiramiz. Jadvalga bazisga kiritiladigan noma’lumni aniqlashga ko’maklashuvchi qo’shimcha qism kiritilgan. Bu qo’shimcha jadvalning elementlari yuqoridagi (59),(61),(63)-(66) formulalar orqali aniqlanadi. 2-jadval

tk yj	x0	x1	x2	v1	1
x1	0	1	0	0	0
x2	0	0	1	0	0
x3	10	-1	-2	0	0
x4	6	-1	-1	0	0
v1	0	0	0	1	0
v2	10	-4	6	1	1
v3	0	0	0	0	1
v4	10	-2	2	1	-1
2	10	-2	2	1	-1
	60	-22	12	6	4
		2
k		2,5
Rk		-17

(63) va (65) formulalarga ko’ra:

2-jadvaldan ko’rinadiki, ning faqat bitta qiymati manfiy ( ). Demak, x₁ noma’lumni bazisga kiritish natijasida T ning qiymatini kamaytirish mumkin. Shuning uchun larni faqat x₁ ga mos keluvchi ustun uchun hisoblash kerak:

Bu yerda T₁ 0. Shuning uchun x₁ noma’lumni bazisga kiritib, ni bazisdan chiqaramiz.

Natijada 3-jadvalni hosil qilamiz.
3-jadvaldan (63),(65) formulalarga asosan ning qiymatlarini hisoblaymiz:




3- jadval.

	x0		x2
x1
x2	0	0	1	0	0
x3
x4			-
	0	0	0	1	0
	0	1	0	0	0
	0	0	0	0	1
	5		-1		-
	5		-1		-
		3	-16	3	1
Rk			-

Bulardan ko’rinadiki, faqat bitta manfiy qiymatga ega. Shuning uchun bu yerda ham larni ga mos keluvchi ustun uchun hisoblaymiz:

T₂ = 0 bo’lganligi sababli bazis o’zgaruvchilarning qiymatini (60) ga asosan topamiz:

bu holda berilgan kvadratik dasturlash masalasining optimal yechimi quyidagidan iborat bo’ladi: