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

4. Kvadratik dasturlash masalalarini yechish uchun Bil usuli
Faraz qilaylik, yuqoridagi (23)-(25) masala berilgan bo’lsin. Bu masalada XDX kvadratik forma manfiy aniqlangan, ya’ni f(X) yuqoriga qavariq funktsiya deb faraz qilamiz.
AX=B,X≥0 sistema berilgan m ta o’zgaruvchiga nisbatan yechilgan bo’lsin. U holda bu sistemani quyidagicha yozish mumkin:
(69)

(70)
Endi (69) ga asoslanib, masalaning maqsad funktsiyasini

formadan quyidagi ko’rinishga keltiramiz:

yoki bundan

(71)

(bu yerda barcha i va j lar uchun ). (71) dagi har bir x_j noma’lum oldidagi qavs ichida yozilgan ifoda f(x) funktsiyadan

x_j noma’lum bo’yicha olingan xususiy hosilaning yarmiga teng bo’ladi, ya’ni masalan, j=1 da

. (72)
Ma’lumki, bazis o’zgaruvchilar uchun

tenglik to’g’ridir. Shuning uchun berilgan masala rejasining optimalligini ko’rsatuvchi Kun-Takker shartlarini qo’yidagicha ifodalash mumkin:

(73)
Endi (9.62) da ozod o’zgaruvchilarning nolga tenglab,

bazis yechimni hosil qilamiz. Agar

shart barcha j = m+1,…,n uchun o’rinli bo’lsa, topilgan

bazis yechim masalaning yechimi bo’ladi.
Faraz qilaylik,

shartni qanoatlantiruvchi kamida bitta j, masalan, mavjud bo’lsin. U holda noma’lumning qiymatini orttira borib, funktsiyani qiymatini orttira borish mumkin, lekin ning qiymatini cheksiz ravishda orttirish mumkin emas, chunki uning ma’lum qiymatlarida noma’lumlardan birortasi yoki

ifoda nolga aylanishi mumkin. Bularning qaysi biri birinchi bo’lib nolga aylanishiga bog’liq ravishda o’zgaruvchi qo’yidagi ikki usul bilan bazisga kiritiladi.

1-usul. ning qiymati orttirib borilganda noma’lumlardan birortasi, masalan x_k birinchi bo’lib nolga aylansin. Bunda x_k uchun

o’rinli bo’ladi. U holda

ifodadan ni ajratamiz (x_k ning o’rniga ni bazisga kiritamiz).
Topilgan ning qiymatini (69) sistemaga qo’yamiz. Yuqorida ko’rgan almashtirishlarni bajarib, funktsiyani (71) ko’rinishda ifodalaymiz. Natijada yangi bazis yechim

topiladi.