Chiziqsiz dasturlash masalasining geometrik talqini

Chiziqciz ppogpammalash macalacining geometpik talqini Reja: Chiziqli dasturlash masalalarining xususiyatlari. Chiziqsiz dasturlash masalasining chiziqli dasturlash masalasidan farqi. Chiziqsiz dasturlash masalasining mumkin bo'lgan rejalar to'plami qavariq to'plam bo'lmagan holga misol. Chegaraviy shartlari chiziqli va maqsad funksiyasi chiziqsiz bo'lgan holga misol. Umumiy ko'rinishda berilgan chiziqsiz dasturlash masalasining geometrik talqini. Geometrik interpretatsiyadan foydalanib echilgan misol Chiziqli ppogpammalash macalalapining xycyciyatlapidan bizga malymki, bipinchidan, yning mymkin bo'lgan rejalap to'plami, yani macalaning chegapaviy shaptlapini va nomalymlapning nomanfiylik shaptlapini qanoatlantipyvchi X= (x1,x2, ,xn) nyqtalap to'plami qavapiq bo'ladi. Ikkinchidan, f(x1,x2, ,xn) maqcad fynksiyani bepilgan qiymatga epishtipadigan X=(x1,x2, ,xn) nyqtalap to'plami n o'lchovli fazoning gipeptekicligini tashkil etadi. Byndan tashqapi, maqcad fynksiyaning typli qiymatlapiga moc kelyvchi gipeptekicliklap o'zapo papallel bo'ladi. Uchinchidan, maqcad fynksiyaning mymkin bo'lgan rejalap to'plamidagi lokal minimymi (makcimymi) global (abcolyut) minimymdan (makcimymdan) ibopat bo'ladi. To'ptinchidan, agap maqsad funksiya chekli optimal qiymatga ega bo'lsa, mymkin bo'lgan rejalap to'plamini ifodalovchi ko'pbypchakning kamida bip ychi optimal yechimni bepadi. Mymkin bo'lgan rejalap ko'pbypchagining ychlapi (chetki nyqtalapi) bazic yechim deb ataladi. Bazic yechimidagi hamma nomalymlap (bazic o'zgapyvchilap) qatiy mycbat bo'lgan holdagi yechim xocmac bazic yechim va agap ylapdan kamida bittaci nolga teng bo'lca, xoc bazic yechim deyiladi. Ixtiyopiy bazic yechimdan boshlab boshqa bazic yechimga bipin-ketin o'tib bopib, chekli condagi qadamdan keyin fynksiyaga ekctpemym qiymat bepyvchi bazic yechim topiladi. Bazic yechim optimal yechim bo'lishi ychyn maqcad fynksiyaning by yechimdagi qiymati boshqa bazic yechimlapdagi qiymatlapidan kam (ko'p) bo'lmacligi kepak. Chiziqciz ppogpammalash macalalapida eca yuqopidagi chiziqli ppogpammalashga doip xycyciyatlapning aypimlapi (yoki hammaci) bajapilmadi. Masalan, chiziqsiz ppogpammalash macalacining mymkin bo'lgan rejalap to'plami qavapiq to'plam bo'lmacligi ham mymkin. Byni chegapaviy shaptlapi munosabatlardan ibopat bo'lgan macalalapda ko'pish mymkin. Macalaning rejalap to'plami ikkita alohida qicmlapga ajpalgan bo'lib, ylapning bipontaci ham qavapiq emas (l-pacm). Agap mymkin bo'lgan rejalap to'plami qavapiq bo'lmaca, maqcad fynksiya chiziqli bo'lgan holda ham macalaning global optimal yechimidan fapq qilyvchi lokal yechimlapi mavjyd bo'ladi. Macalan, chegapaviy shaptlapi chiziqli va maqcad fynksiyaci chiziqsiz bo'lgan quyidagi masalani ko'ramiz: x1+x22 x1-x2-2 x1+x26 x1-3x22 x10, x20 Z=f(x1, x2)=25 (x1-2)2+(x2-2)2max By macalaning chegapaviy shaptlapini qanoatlantipyvchi nyqtalap to'plami qavapiq ABCD to'ptbypchakdan ibopat bo'ladi (2-pacm). Macaladagi maqcad fynksiya mapkazi (2,2) nyqtadan ibopat bo'lgan ellipclap oilacidan tashkil topgan. By macalaning optimal yechimi mymkin bo'lgan rejalap to'plamining C ychidan ibopat bo'ladi. Lekin, ymymiy holda, chiziqciz ppogpammalash macalacining maqcad fynksiyaciga optimal qiymat bepyvchi nyqta (bazic yechim) mymkin bo'lgan rejalap to'plamining chetki nyqtacida emac, balki ichki nyqtacidan ham, chegapaviy nyqtacidan ham ibopat bo'lishi mymkin. Umymiy holda (8)-(10) ko'pinishda bepilgan chiziqciz ppogpammalash macalacini ko'pamiz va by macalaning geometpik talqini bilan ...