Reja: Nochiziqli dasturlash masalalarining xususiyatlari chiziqsiz dasturlash masalalarining grafik usulda geometrik talqini chiziqsiz programmalashtirish masalalarining turlari va geometrik talqini Xulosa Foydalanilgan Adabiyotlar
Yüklə 38,04 Kb.
|
- Bu səhifədəki naviqasiya:
- Xulosa Foydalanilgan Adabiyotlar Nochiziqli dasturlash Nochiziqli dasturlash
- , chiziqli bolmagan dasturlash muammosi
- Lagrange multiplikator usuli
- Nochiziqli dasturlash masalalarining xususiyatlari
|
Mavzu: Chiziqsiz programmalashtirish REJA: Nochiziqli dasturlash Nochiziqli dasturlash masalalarining xususiyatlari CHIZIQSIZ DASTURLASH MASALALARINING GRAFIK USULDA GEOMETRIK TALQINI Chiziqsiz programmalashtirish masalalarining turlari va geometrik talqini Xulosa Foydalanilgan Adabiyotlar Nochiziqli dasturlash Nochiziqli dasturlash - bu matematik dasturlashning bo'limi bo'lib, maqsad funksiya va cheklovlar umumiy xarakterga ega bo'lgan (chiziqli deb hisoblanmaydi) vaziyatda cheklovlar mavjud bo'lganda qo'zg'almas (maqsadli) funktsiyaning global ekstremumini topish muammosini o'rganadi. . Umuman olganda , chiziqli bo'lmagan dasturlash muammosi quyidagicha tuzilgan: shaklning maqsad funktsiyasining ekstremumini ta'minlaydigan noma'lum o'zgaruvchilar qiymatlarini toping. va cheklovlar tizimini qondiris o'zgaruvchilar qayerda ; – n ta o‘zgaruvchining berilgan funksiyalari ; - berilgan raqamlar. Cheklovlar tizimi, agar bunday shartlar mavjud bo'lsa, o'zgaruvchilarning manfiy bo'lmasligi uchun shartlarni ham o'z ichiga olishi mumkin. Matematik tahlilda bunday turdagi masala funksiyaning shartli ekstremumidagi masala deyiladi . Funktsiyaning shartli ekstremumi - bu argumentlari cheklovlar yoki ulanish tenglamalari deb ataladigan qo'shimcha shartlarni qondiradigan funktsiyaning ekstremumidir . Nochiziqli dasturlash muammolari amalda yuzaga keladi, masalan, 1) xarajatlar sotib olingan yoki ishlab chiqarilgan tovarlar miqdoriga mutanosib ravishda o'zgarmasa; 2) xom ashyo va resurslarning ayrim turlarini iste'mol qilish chiziqli bo'lmagan, ammo spazmodik (ishlab chiqarish hajmiga qarab) sodir bo'lganda. Optimal yechim faqat amalga oshirilishi mumkin bo'lgan echimlar sohasining cho'qqilarida joylashgan chiziqli dasturlash muammolaridan farqli o'laroq, chiziqli bo'lmagan dasturlash muammolarida optimal echim amalga oshirilishi mumkin bo'lgan echimlar sohasi ichida , uning chetida yoki tepasida joylashgan bo'lishi mumkin . . Natijada, chiziqli dasturlash masalalariga qaraganda chiziqli bo'lmagan dasturlash masalalari murakkabroq va ular uchun umumiy universal echim usuli mavjud emas (simpleks usuliga o'xshash). Maqsad funksiyasi turi va cheklovlar tizimi bilan farq qiluvchi turli xil chiziqli bo'lmagan dasturlash muammolarini hal qilish uchun maxsus echim usullari ishlab chiqilgan. Asosiylariga quyidagilar kiradi: 1) Lagrange multiplikator usuli , hollarda qo'llaniladi a) o‘zgaruvchilarning salbiy bo‘lmasligi sharti yo‘q; b) cheklashlar tizimi faqat tenglikdan iborat; v) maqsad funksiya va cheklovlar uzluksiz funksiyalardir uning qisman hosilalari bilan birga; 2) qavariq dasturlash - chiziqli bo'lmagan dasturlashning qavariq yopiq to'plamlarda (qavariq funktsiyalarni maksimallashtirish) muammolarini o'rganadigan bo'limi (qavariq nuqtalar to'plami - bu har qanday ikkita nuqta bilan birga o'z ichiga olgan nuqtalar to'plami. ularni birlashtiruvchi segment; yopiq to'plam - barcha chegara nuqtalarini o'z ichiga olgan nuqtalar to'plami); 3) kvadratik dasturlash - chiziqli bo'lmagan dasturlashning ko'p burchakli to'plamdagi kvadratik funktsiyaning global ekstremumini topish zarur bo'lgan muammolarni o'rganadigan bo'limi (qavariq ko'pburchak - chekli sonli burchakka ega bo'lgan qavariq yopiq cheklangan nuqtalar to'plamidir. cho'qqilar; agar to'plamning istalgan nuqtasida bu to'plamni to'liq o'z ichiga olgan markaz bilan chekli uzunlikdagi radiusli to'p bo'lsa, nuqtalar to'plami chegaralangan deb ataladi ); 4) ajratiladigan dasturlash - matematik dasturlashning chiziqli bo'lmagan dasturlash masalalarini o'rganadigan bo'limi bo'lib, unda maqsad funktsiyasi va cheklovlar ajratiladigan funktsiyalar bilan belgilanadi , ya'ni har biri faqat bitta haqiqiy o'zgaruvchiga bog'liq bo'lgan funktsiyalar yig'indisi sifatida ifodalanadigan funktsiyalar. Bundan tashqari, har qanday chiziqli bo'lmagan dasturlash muammosini gradientni optimallashtirish usullari - gradientdan foydalanish bilan bog'liq bo'lgan ko'plab o'zgaruvchilarning silliq funktsiyalarini maksimallashtirish yoki minimallashtirish usullari yordamida hal qilish mumkin ( silliq funktsiya ta'rif sohasida farqlanadigan funktsiya sifatida tushuniladi). ya'ni uzluksiz hosilaga ega bo'lish). Chiziqli bo'lmagan dasturlash masalalarining eng oddiy turi ikkita o'zgaruvchili va tenglik ko'rinishidagi bitta cheklovli masalalardir. Ular o'xshaydi Ikki o'zgaruvchi va bitta tenglik cheklovi bilan chiziqli bo'lmagan dasturlash masalalari almashtirish usuli, Lagrange ko'paytma usuli va grafik usul bilan echilishi mumkin. 2.Nochiziqli dasturlash masalalarining xususiyatlari Nochiziqli dasturlash q i (x) cheklovlar yoki Z(X) maqsad funksiyasi yoki ikkalasi ham chiziqli bo‘lmagan muammoli modellarni optimallashtirish bilan shug‘ullanadi. R - tartib munosabati (=, ≥, ≤), Ō - amalga oshirilishi mumkin bo'lgan echimlar mintaqasi bo'lgan mintaqada max (min)=Z=z(X) ni toping ; b i – doimiy, i= 1,m ; X=(x 1 ,…,x n )={x j }, j=1..n – boshqaruv rejasi yoki vektor. Nochiziqlilik tufayli yuzaga kelgan ushbu sinf muammolarini yechishdagi qiyinchiliklarni aniqlash uchun chiziqli va chiziqli bo'lmagan dasturlash masalalarini solishtiramiz. Har bir sinf uchun uchta xarakterli xususiyatni aniqlash mumkin.
Rasmda chiziqli bo'lmagan dasturlash masalalari va usullarining tasnifi ko'rsatilgan. Chiziqli bo'lmagan dasturlashda mavjud bo'lgan ko'pgina usullarni ikkita katta sinfga bo'lish mumkin: To'g'ridan-to'g'ri usullar - bu asl muammoni bevosita hal qilish usullari. To'g'ridan-to'g'ri usullar nuqtalar ketma-ketligini hosil qiladi - maqsad funktsiyasining monotonik pasayishini ta'minlaydigan cheklovlarni qondiradigan echimlar. Kamchilik: global konvergentsiya xususiyatini olish qiyin. Tenglik ko'rinishidagi cheklovlar bilan bog'liq muammolar. O'zgaruvchan almashtirish usuli (SVM) Dual usullar ikkilik tushunchasidan foydalanadigan usullardir. Bunday holda, global konvergentsiyaga erishish oson. Kamchilik: ular yechim davomida asl muammoning yechimini ta'minlamaydi - u faqat takroriy jarayonning oxirida amalga oshiriladi. Lagrange multiplikator usuli (LMM) Penalti usullari Multiplikator usuli Cheklangan optimallashtirish muammolari uchun lineerizatsiya usullari Zeutendijk usulida ruxsat etilgan yo'nalishlar Shartli gradient usuli Gradient proyeksiyalash usuli Ajraladigan dasturlash. Kvadrat dasturlash Yüklə 38,04 Kb. Dostları ilə paylaş:
|