Reja: Nochiziqli dasturlash masalalarining xususiyatlari chiziqsiz dasturlash masalalarining grafik usulda geometrik talqini chiziqsiz programmalashtirish masalalarining turlari va geometrik talqini Xulosa Foydalanilgan Adabiyotlar


Download 38.04 Kb.
bet1/4
Sana26.09.2023
Hajmi38.04 Kb.
#1687952
  1   2   3   4
Bog'liq
Chiziqsiz programmalashtirish.111111


Mavzu: Chiziqsiz programmalashtirish
REJA:

  1. Nochiziqli dasturlash

  2. Nochiziqli dasturlash masalalarining xususiyatlari

  3. CHIZIQSIZ DASTURLASH MASALALARINING GRAFIK USULDA GEOMETRIK TALQINI

  4. Chiziqsiz programmalashtirish masalalarining turlari va geometrik talqini


Xulosa
Foydalanilgan Adabiyotlar


  1. 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.

Chiziqli dasturlash masalalari

Nochiziqli dasturlash muammolari

1. Ruxsat etilgan rejalarning Ō mintaqasi chekli sonli burchak (ekstremal) nuqtalarga ega bo'lgan qavariq to'plamdir .

1. Ruxsat etilgan rejalarning to'plami Ō konveks bo'lmagan, ajratilgan va cheksiz ko'p ekstremal nuqtalarga ega bo'lishi mumkin.

2. Chiziqli maqsad funksiyasi z(X) ekstremal nuqtalardan birida ( mumkin yechimlar Ō hududi chegarasida) ekstremal qiymatga etadi.

2. Ekstremumga nafaqat chegarada , balki mumkin bo'lgan echimlar Ō mintaqasida ham erishish mumkin.

3. Maqsad funksiyasining ekstremal qiymati z(X) ham global qiymatdir.

3. Ō sohadagi z(X) maqsad funksiyasi bir nechta mahalliy ekstremallarga ega bo'lishi 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:

  1. 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)

  2. 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





  1. Download 38.04 Kb.

    Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling