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

2-teorema. Nomanfiy kvadratik forma E_n Evklid fazosida qavariq funktsiyadir. Agar kvadratik forma musbat aniqlangan bo’lsa, u qat’iy qavariq funktsiya bo’ladi.
Isbot. Ixtiyoriy X₁,X₂ nuqtalar va sonni ( ) olib,
= X₂+(1- )X₁
nuqtani tuzamiz va bu nuqtada Z=XDX kvadratik formaning qiymatini tekshiramiz:
( 11 )
Teoremani shartiga ko’ra ixtiyriy X uchun (X≠ 0) XDX≥ 0. Shuning uchun
(12)
(9.10) ga asosan (9.9) dan quyidagi tengsizlikni hosil qilamiz:

, (13)
yoki

. (14)

(14) tengsizlik kvadratik formaning qavariq funktsiyasi ekanligini ko’rsatadi.

Endi kvadratik forma musbat aniqlangan deb faraz qilamiz. U holda ixtiyoriy 0< <1 uchun

(15)

tengsizlik o’rinli bo’ladi. Demak, (9.11) da ≤ ishorani < bilan almashtirish mumkin, ya’ni

. (16)
Bundan
(17)
(17) tengsizlik kvadratik formaning qat’iy qavariq ekanligini ko’rsatadi. Shu bilan teorema isbot bo’ldi.

Xuddi shunday mulohazalar yordamida quyidagi teoremani ham isbot qilish mumkin.

3–teorema. Nomusbat kvadratik forma E_n Evklid fazosida yuqoriga qavariq funktsiyadir. Agar kvadratik forma manfiy aniqlangan bo’lsa, u qat’iy yuqoriga qavariq funktsiya bo’ladi.


2. Kvadratik dasturlash masalalari uchun Kun-Takker shartlari
Kvadratik dasturlash masalasi ((1)-(3)) berilgan bo’lsin. Maqsad funktsiyaning minimumi qidiriladigan masalani uning maksimumi qidiriladigan maslaga keltirish mumkin bo’lgani sababli (3) ning o’rniga bundan keyin

(18)
funktsiyani yoki matritsali formadagi

(19)
funktsiyani ko’ramiz.
Bundan keyin f(X) funktsiyani yuqoriga qavariq funktsiya, ya’ni kvadratik formani yuqoriga qavariq ( -manfiy aniqlangan forma) deb faraz qilamiz. Bu holda (1)-(2) shartlarni qanoatlantiruvchi rejalar to’plami qavariq to’plam bo’lgani uchun kvadratik dasturlash masalasi yagona (global) optimal yechimga ega bo’ladi.
Masalaning (1) shartlarini qo’shimcha o’zgaruvchilar kiritish mumkin bo’lgani uchun (1)-(3) masalani quyidagi ko’rinishda ifodalaymiz:

(20)
(21)

(22 )
yoki matritsa formada

AX=B, (23)
X≥ 0, (24)
(25)
Bu masalaning yechimi optimal yechim bo’lishining zaruriy va etarlilik shartlarini aniqlaymiz. Buning uchun Lagranj funktsiyasini tuzamiz:
, (26)
yoki matritsali formada
. (27)
F(X, ) funktsiyadan x_j (j= ) _I (i= ) bo’yicha xususiy hosilalar olamiz:
, (28)
yoki

(29)
(30)

(31)
Endi (28)-(31) munosabatlarga asoslanib, Kun-Takkerning shartlarini yozamiz:

,

.

Bundan (28), (30) ga asosan:

, (32)
, (33)
(34)
(35)
(36)
(37)
(32)-(37) shartlar matritsali formada quyidagicha ifodalanadi:

(38)
(39)

(40)
(41)
(42)
(43)
Agar shunday vektor mavjud bo’lib, lar uchun (38)-(43) shartlar o’rinli bo’lsa, X⁰ vektor berilgan kvadratik dasturlash masalasi (23)-(25) ning optimal yechimi bo’ladi.
Endi (38) tengsizlikni qo’shimcha o’zgaruvchilar kiritish yordamida tenglamaga aylantiramiz

Bundan
. (44)

Bu holda kvadratik dasturlash masalasi yechimining optimal yechim bo’lishlik sharti quyidagicha bo’ladi:
(45)
X*V*=0, X*≥0, V*≥ 0. (46)
Berilgan masaladagi (9.21) shartlar tenglama ko’rinishda bo’lganligi sababli ga musbat bo’lishlik sharti qo’yilmaydi. Bundan tashqari, (41)-(42) shartlar ixtiyoriy bazis rejalar uchun o’rinli bo’lganligi sababli ularni tashlab yuborish mumkin. Demak, xulosa qilib shuni aytish mumkinki, quyidagi