7-Ma’ruza chiziqsiz programmalash masalasining umumiy qo‘yilishi reja

Chiziqsiz programmalash masalalarining geometrik interpretatsiyasi

Chiziqli programmalash masalalarining xususiyatlaridan bizga ma’lumki, birinchidan uning mumkin bo‘lgan planlar to‘plami, ya’ni masalaning chegaraviy shartlarini va noma’lumlarning nomanfiylik shartlarini qanoatlantiruvchi nuqtalar to‘plami qavariq bo‘ladi. Ikkinchidan, maqsad funksiyani berilgan qiymatga erishtiradigan nuqtalar to‘plami o‘lchovli fazoning gipertekisligini tashkil qiladi. Bundan tashkari, maqsad funksiyaning qiymatlariga mos keluvchi gipertekisliklar o‘zaro parallel bo‘ladi. Uchinchidan, maqsad funksiyaning mumkin bo‘lgan planlar to‘plamidagi lokal minimumi (maksimumi) golabal (absolyut) minimumdan (maksimumdan) iborat bo‘ladi. To‘rtinchidan, agar maqsad funksiya chekli optimal qiymatga ega bo‘lsa, mumkin bo‘lgan planlar to‘plamini ifodalovchi ko‘pburchakning kamida bir uchi optimal yechimni beradi. Mumkin bo‘lgan planlar ko‘pburchagining uchlari (chetki nuqtalari) bazis yechim deb ataladi. Bazis yechimdagi hamma noma’lumlar (bazis o‘zgaruvchilar) qat’iy musbat bo‘lgan holdagi yechim xosmas bazis yechim va agar ulardan kamida bittasi nolga teng bo‘lsa, xos bazis yechim deyiladi.

Ixtiyoriy bazis yechimdan boshlab boshqa bazis yechimga birin-ketin o‘tib borib, chekli sondagi qadamdan so‘ng funksiyaga ekstremum qiymat beruvchi bazis yechim topiladi.
Bazis yechim optimal yechim bo‘lishi uchun maqsad funksiyaning bu yechimdagi qiymati boshqa bazis yechimlardagi qiymatlaridan kam (ko‘p) bo‘lmasligi kerak.
Chiziqsiz programmalash masalalarida esa yuqoridagi chiziqli programmalashga doir xususiyatlarning ayrimlari (yoki hammasi) bajarilmaydi. Masalan, chiziqsiz programmalash masalasining mumkin bo‘lgan planlar to‘plami qavariq to‘plam bo‘lmasligi ham mumkin. Buni chegaraviy shartlari

munosabatlardan iborat bo‘lgan masalada ko‘rish mumkin. Masalaning planlar to‘plami ikkita alohida qismlarga ajralgan bo‘lib, ularning birortasi ham qavariq emas (1 shakl).
Agar mumkin bo‘lgan planlar to‘plami qavariq bo‘lmasa, maqsad funksiya chiziqli bo‘lgan holda ham masalaning global optimal yechimlaridan farq qiluvchi lokal yechimlari mavjud bo‘ladi. Masalan, chegaraviy shartlari chiziqli va maqsad funksiyasi chiziqsiz bo‘lgan quyidagi masalani ko‘ramiz:



M

D

x₂

x₂

x₁

1 –shakl 2- shakl

Bu masalaning chegaraviy shartlarini qanoatlantiruvchi nuqtalar to‘plami qavariq to‘rtburchakdan iborat bo‘ladi. (2-shakl).
Masaladagi maqsad funksiya markazi (2, 2) nuqtadan iborat bo‘lgan ellipslar oilasidan iborat.
da ellips va nuqtalardan o‘tadi, nuqtada va
nuqtada bo‘ladi. Bundan ko‘rinadiki, nuqtada maqsad funksiyaning qiymati unga yaqin bo‘lgan va nuqtalardagi qiymatidan katta. Demak, nuqtada maqsad funksiya lokal maksimumga erishadi. S nuqtada funksiya eng katta qiymatga erishadi. Maqsad funksiyaning nuqtadagi qiymati to‘rtburchakka tegishli hamma nuqtalardagi qiymatlardan katta bo‘ladi. Demak, funksiya nuqtada global maksimumga erishadi.
Bu masalaning optimal yechimi mumkin bo‘lgan planlar to‘plamining uchidan (chetki nuqtasidan) iborat bo‘ladi. Lekin, umumiy holda, chiziqsiz programmalash masalasining maqsad funksiyasiga optimal qiymat beruvchi nuqta (azis yechim) mumkin bo‘lgan planlar to‘plamining chetki nuqtasi bo‘lishi shart emas. Ayrim hollarda bazis yechim mumkin bo‘lgan planlar to‘plamining ichki nuqtasidan ham, chegaraviy nuqtasidan ham iborat bo‘lishi mumkin. Masalan 3 –shaklda tasvirlangan masalada maqsad funksiya minimum qiymatga mumkin bo‘lgan planlar to‘plamining chegaraviy nuqtasi da erishadi.
4-shaklda esa maqsad funksiya o‘zining minimum qiymatga mumkin bo‘lgan planlar to‘plamining ichki nuqtasida erishadigan masala tasvirlangan.