Qavariq programmalashtirish

Qavariq programmalashtirish Reja: Qavariq to'plamlar va qavariq funksiyalar. Chiziqli va chiziqsiz programmalashtirish masalalarining bir-biridan farqi. Qavariq programmalashtirish masalalari Tayanch so'zlar Qavariq to'plam, qavariq chiziqli kombinatsiya, qavariq ko'pburchak, tayanch to'g'ri chiziq, qavariq ko'pyoqli, gipertekislik, yopiq yarim fazo, Lagranj funksiyasining egar nuqtasi Qavariq to'plamlar 1-ta'rif. n o'lchovli fazoda berilgan X to'plam va nuqta bilan birga shu nuqtalarni birlashtiruvchi kesmani ham o'z ichida saqlasa, yani bo'lib, bo'lsa, qavariq to'plam deyiladi. Agar va deb belgilasak, (1) 2-ta'rif. (1) shartni qanoatlantiradigan nuqta va nuqtalarning qavariq chiziqli kombinatsiya deyiladi. 3-ta'rif. Qavariq ko'pburchak deb, bir necha kesmalar bilan chegaralangan qavariq figuraga aytiladi. 4-ta'rif. Agar qavariq ko'pburchak birorta to'g'ri chiziqning bir tomonida yotgan bo'lsa, va ko'pburchak Bilan to'g'ri chiziq hech bo'lmaganda bita umumiy nuqtaga ega bo'lsa, bu to'g'ri chiziq tayanch to'g'ri chiziq deyiladi. 5-ta'rif. Shunday figuraga chegaraviy figura deyiladiki, agar uning ixtiyoriy nuqtasini markaz qilib olib doira o'tkazsak, bu doira hamma vaqt shu figuraga tegishli va tegishli bo'lmagan nuqtalarni o'z ichiga saqlaydi. 6-ta'rif. Qavariq ko'pburchaklar bilan chegaralangan jism qavariq ko'pyoqli deyiladi. 7-ta'rif. n o'lchovli fazoda , (2) shartni qanoatlantiruvchi nuqtalar to'plami gipertekislik deyiladi. 8-ta'rif. Quyidagi shartni qanoatlantiruvchi nuqtalar to'plami yopiq yarim fazo deyiladi. Bu ta'rifdan chekli son yarim fa'zolar kesishmasi, aniqrog'i, quyidagi (3) tengsizliklar sistemasini qanoatlantiradigan nuqtalar to'plami ko'p yoqli ekanligi yoki chiziqliprogrammalashtirish masalasi o'rinli yechimlar to'plamining mavjudlik sohasi ekanligi kelib chiqadi. Haqiqatan ham, chiziqli programmalashtirishning asosiy maqsadi chiziqli (4) funksiyaning chiziqli cheklanish shartlari (3) ni qanoatlantiradigan minimumini topishdan iboratdir. Chiziqli va chiziqsiz programmalashtirish masalalarining bir-biridan farqi. Tushunarli bo'lishi uchun yana bir bor chiziqli va chiziqsiz programmalashtirish masalalarining bir-biridan farqi haqida hamda maqsad funksiya (4) cheklanishshartlari (3) chiziqsiz funksiyalar bo'lganda qo'yilgan masalani yechishda uchraydigan qiyinchiliklar ustida qisqacha to'xtalib o'tamiz. Agar cheklanish shartlarida qatnashadigan funksiyalar chiziqli bo'lsa, o'rinli yechimlar sohasi hamma vaqt qavariq bo'lib, chekli son uchki nuqtalarga ega bo'ladi. O'rinli yechimlar sohasi V quyidagi chiziqli tengsizliklar sistemasi bilan berilgan bo'lsin: V coha 2 o'lchovli qavariq figura, yani uchburchak bo'lib, uchki nuqtalaring soni 3 ta chekli songa tengdir. Bu chiziqli programmalashtirish masalasidir. V soha quyidagi chiziqsiz tengsizliklar bilan aniqlangan bo'lsin: Bu cheklanish shartlarining birinchisi - markazi (1,1) nuqtada bo'lib, radiusi birdan kichik bo'lgan aylanadan, 2-chisi esa giperboladan iboratdir. Birinchidan, V soha qavariq emas, ikkinchidan bu sohaning chegaraviy nuqtalari aylana va giperbolalarda yotganligi uchun bu soha cheksiz ko'p uchki nuqtalarga ega. Bu chiziqsiz programmalashtirish masalasidir. Shunday qilib, agar chiziqli programmalashtirish masalalarining optimal yechimlari qavariq V sohaning chekli son uchki nuqtalar to'plami ichidan topilsa, chiziqsiz programmalashtirish masalalarining optimal yechimlari esa umumiy ...