7-mavzu. Chiziqsiz dasturlash masalalari 1-ma’ruza rejasi
Chiziqsiz dasturlash masalalarining geometrik talqini. Grafik usul
Yüklə 111,74 Kb.
|
- Bu səhifədəki naviqasiya:
- ............................... ...
|
2. Chiziqsiz dasturlash masalalarining geometrik talqini. Grafik usul
Chiziqli dasturlash masalalarining xossalaridan bizga ma’lumki, birinchidan, uning joiz rejalari to’plami, ya’ni masalaning chegaraviy shartlarini va noma’lumlarning nomanfiylik shartlarini qanoatlantiruvchi X=(x1, x2,...,xn) nuqtalar to’plami qavariq bo’ladi. Ikkinchidan, f(x1, x2,...,xn) maqsad funktsiyasini berilgan qiymatga erishtiradigan X=(x1, x2,...,xn) nuqtalar to’plami n-o’lchovli fazoning gipertekisligini tashkil qiladi. Bundan tashqari, maqsad funktsiyaning turli qiymatlariga mos keluvchi gipertekisliklar o’zaro parallel bo’ladi. Uchinchidan, maqsad funktsiyaning mumkin bo’lgan rejalari to’plamidagi mahalliy minimumi (maksimumi) global (absolyut) minimumdan (maksimumdan) iborat bo’ladi. To’rtinchidan, agar maqsad funktsiya chekli optimal qiymatga ega bo’lsa, joiz rejalar to’plamini ifodalovchi qavariq ko’pburchakning kamida bir uchi optimal yechimni beradi. Mumkin bo’lgan rejalar ko’pburchagining uchlari (burchak nuqtalari) bazis yechimni ifodalaydi. Bazis yechimdagi hamma noma’lumlar 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 o’tib borib, chekli sondagi qadamdan so’ng funktsiyaga ekstremum qiymat beruvchi bazis yechim topiladi. Bazis yechim optimal yechim bo’lishi uchun maqsad funktsiyaning bu yechimdagi qiymati boshqa bazis yechimdagi qiymatlaridan kam (ko’p) bo’lmasligi kerak. Chiziqsiz dasturlash masalalarida esa yuqoridagi chiziqli dasturlashga doir xossalarning ayrimlari (yoki hammasi) bajarilmaydi. Masalan, chiziqsiz dasturlash masalasining mumkin bo’lgan rejalar to’plami qavariq to’plam bo’lmasligi ham mumkin. Buni chegaraviy shartlari munosabatlardan iborat bo’lgan masalada ko’rish mumkin. Masalaning rejalar to’plami ikkita alohida qismlarga ajratilgan bo’lib, ularning birortasi ham qavariq emas (1 – shakl). Agar joiz rejalar to’plami qavariq bo’lmasa, maqsad funktsiya chiziqli bo’lgan holda ham masalaning global optimal yechimidan farq qiluvchi mahalliy yechimlari mavjud bo’ladi. Masalan, chegaraviy shartlari chiziqli va maqsad funktsiyasi chiziqsiz bo’lgan quyidagi masalani ko’ramiz: x1 + x2 2, x1 - x2 -2, x1 + x2 6, x1 - 3x2 2, x1 0, x2 0, Z =f (x1, x2,) = 25(x1 –2)2 + (x2 –2)2 max. Bu masalaning chegaraviy shartlarini qanoatlantiruvchi nuqtalari to’plami qavariq ABCD to’rtburchakdan iborat bo’ladi (2- shakl). Masaladagi maqsad funktsiya markazi (2,2) nuqtadan iborat bo’lgan elipslar oilasidan iborat. x2
3.5
0 3.5 x1 1-shakl 2 – shakl Z=4 da ellips B va D nuqtalardan o’tadi, A nuqtada Z=100 va C nuqtada Z=226 bo’ladi. Bundan ko’rinadiki, A nuqtada maqsad funktsiyaning qiymati unga yaqin bo’lgan B va D nuqtalardagi qiymatidan kichik. Demak, A nuqtada maqsad funktsiya mahalliy minimumga erishadi. C nuqtada Z =f (x1, x2,) funktsiya eng katta Z=226 qiymatga erishadi. Maqsad funktsiyaning C nuqtadagi qiymati ABCD to’rtburchakka tegishli hamma nuqtalardagi qiymatidan katta bo’ladi. Demak, Z =f (x1, x2,) funktsiya C nuqtada global maksimumga erishadi. Bu masalaning optimal yechimi joiz rejalar to’plami C uchining koordinatalaridan iborat bo’ldi. Lekin umumiy holda, chiziqsiz dasturlash masalasining maqsad funktsiyasiga optimal qiymat beruvchi nuqta joiz rejalar to’plamining burchak nuqtasi bo’lishi shart emas. Ayrim hollarda optimal reja joiz rejalar to’plamining ichki nuqtasidan ham, chegaraviy nuqtasidan ham iborat bo’lishi mumkin. Masalan, 3-shaklda tasvirlangan masaladagi Z=f (x1, x2,) maqsad funktsiya minimum qiymatga mumkin bo’lgan rejalar to’plamining chegaraviy nuqtasida erishadi. Umumiy holda (8) - (10) ko’rinishda berilgan chiziqsiz dasturlash masalasini ko’ramiz va bu masalaning geometrik talqini bilan tanishamiz. . Masaladagi (8), (9) cheklamalarni qanotlantiruvchi nuqtalar to’plami Evklid fazosida joiz rejalar to’plamini beradi. Bu to’plamning nuqtalari orasidan maqsad funktsiyaga minimum qiymat beruvchi nuqtani topish kerak. Buning uchun joiz rejalar to’plamining eng past saviyali f(x1, x2,...,xn)=Q gipersirti bilan kesishgan nuqtasini topish kerak. Bu nuqta berilgan (8) - (10) masalaning optimal yechimini beradi.(8)-(10) masalaning optimal yechimini geometrik talqinidan foydalanib topish uchun quyidagi ishlarni bajarish kerak: Masalaning (8), (9) chegaraviy shartlarini qanoatlantiruvchi nuqtalar to’plamini, ya’ni joiz rejalar to’plamini yasash kerak (agar bu to’plam bo’sh bo’lsa, masala yechimga ega bo’lmaydi). f(x1, x2,...,xn)=Q gipersirtni yasash kerak. ............................... ...x2.. Z=Q2 x x2. Z=Q1. . Z=Q2 . ........ ZZZZ Z . . Z=Q1 . . . / . / . . AA F . . vi aiva.. 0 x1 x1 3-shakl 4-shakl Q ning qiymatini o’zgartirib borib, eng past saviyali gipersirt topiladi yoki uning quyidan chegaralanmaganligi aniqlanadi. Mumkin bo’lgan rejalar to’plamining eng past saviyali gipersirt bilan kesishgan nuqtasi aniqlanadi va maqsad funktsiyaning bu nuqtadagi qiymati topiladi. Quyidagi masalalarni geometrik talqinidan foydalanib yechamiz: 1-misol. x1 + x2 8, 2x1 + x2 15, x1 + x2 1, x1 0, x2 0, Z = f(x1, x2,) = (x1 –6)2 + (x2 –2)2 max(min). x2 S V (6,2)
0 x1 A E 5-shakl Masalaning chegaraviy shartlarini qanoatlantiruvchi nuqtalar to’plami ABCDE beshburchakdan iborat bo’ladi (5 - shakl). Agar Z=Q (Q>0) deb qabul qilsak, (x1 - 6)2 + (x2 - 2)2 =Q tenglama markazi M (6.2) nuqtada va radiusi ga teng bo’lgan aylanani ifoda etadi. Q ning qiymatini orttirib yoki kamaytirib borish natijasida Z ning qiymati ham ortib yoki kamayib boradi. M nuqtadan turli radiusli aylanalar (parallel gipersirtlar) o’tkazib borib, Z funktsiyaga eng kichik yoki eng katta qiymat beruvchi nuqtani topish mumkin. Yüklə 111,74 Kb. Dostları ilə paylaş:
|