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

4. Kvadratik dasturlash masalalarini yechish uchun Bil usuli.


Tayanch iboralar:
Kvadratik dasturlash, kvadratik forma, musbat aniqlangan kvadratik forma, manfiy aniqlangan kvadratik forma, nomusbat aniqlangan kvadratik forma, nomanfiy aniqlingan kvadratik forma, aniqmas kvadratik forma; kanonik ko’rinishdagi kvadratik forma, Kun-Takker shartlari

Kvadratik dasturlash masalasi chiziqsiz (qavariq) dasturlash masalasining xususiy holidan iboratdir. Uning matematik modelidagi chegaraviy shartlar chiziqli tenglama va tengsizliklardan, maqsad funktsiyasi umumiy holda chiziqli va kvadratik formalarning yig’indisidan iborat bo’ladi:

, (1)
, (2)
(3)
yoki matritsa formada:
(4)
(5)
, (6)
bu yerda A mxn o’lchovli matritsa, D n o’lchovli kvadrat matritsa, B m o’lchovli, X, C n o’lchovli vektorlar. Shunday qilib, (1)-(3) yoki (4)-(6) ko’rinishda berilgan masalani kvadratik dasturlash masalasi deb ataymiz.
Bu masala chiziqli dasturlash masalasidan shunisi bilan farq qiladiki, uning maqsad funktsiyasida kvadratik forma XDX qatnashadi. Bu kvadratik formaga bog’liq ravishda f(X) maqsad funktsiya pastga yoki yuqoriga qavariq bo’lishi mumkin. Ana shunday hollar uchun, ya’ni kvadratik dasturlash masalasi yagona optimal (global) yechimiga ega bo’lgan hollar uchun masalani yechish usullari yaratilgan.
Kvadratik formalar va ularning xossalari va bu xossalarning f(X) maqsad funktsiyasiga ta’siri, kvadratik dasturlash masalasini yechish usullari keltiramiz.
Kvadratik formalar va ularning kanonik shakli quyidagicha bo’lsin. U holda
(7)
ko’rinishdagi funktsiyaga kvadratik forma deyiladi, bu yerda


(3) kvadratik funktsiyaning pastga (yuqoriga) qavariq bo’lishi (7) kvadratik formaning pastga (yuqoriga) qavariq bo’lishligiga bog’liqdir. Bu esa o’z navbatida XDX formaning manfiy yoki musbat, nomanfiy yoki nomusbat aniqlanganligiga, yoki umuman, ishorasi aniqlanmaganligiga bog’liqdir.