Berdaq nomidagi qoraqalpoq davlat universiteti matematika fakulteti

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
BERDAQ NOMIDAGI QORAQALPOQ DAVLAT UNIVERSITETI
MATEMATIKA FAKULTETI
Amaliy matematika kafedrasi
«Amaliy matematika va informatika»
ta’lim yo’nalishi IV kurs talabasi
Ametova Yulduzning


BITIRUV
MALAKAVIY ISHI
Mavzu: Сhiziqli emas programmalashtirish masalasini shtraf-funktsiyalar usuli bilan yechish


Ilmiy rahbar: f.-m.f.n., dots. R.Mustafaeva
Kafedra mudiri: f.-m.f.d., dots. D.Utebaev




Nukus_2020

Mundarija:

KIRISH 2
1- §. Chiziqli emas programmalashtirish masalasi 6
2-§. Chiziqli emas programmalashtirish masalasini yechishning shtraf funksiyalar usuli 18
3-§. Sonli misol 27
Foydalanilgan adabiyotlar 39

KIRISH

Umumiy ma’noda optimizatsiyalash nazariyasi – bu fundamental matematik natijalarning va sonli usullar yig’indisi ko’rinishida bo’ladi. Bunda usullari alternativ yechimlar to’plamidan eng yaxshi variantlarini topishga va identifikatsiyalashga yo’naltirilgan bo’lib, ular qo’yilgan masalaning mumkin bo’lgan yechimlar variantlarini to’liq ko’rib chiqishdan va ularni baholash ishlaridan bizlarni qutqaradi.Barcha injenerlik faoliyati asosida optimizatsiyalash jarayonlari yotibdi[9].
Optimizatsiyalash nazariyasining ahamiyatliligi va baholiligi shundan iborat bo’ladi, bunda analiz qilish va ko’p sonli masalalarni yechish uchun mos keluvchi tushunchaga oid chegarasini aniqlab beradi:
-operatsiyalarni tadqiqotlashda: texnik-iqtisodiy sistemalarni, transport masalalarni, zaxiralar bilan boshqarish ishlarini optimizatsiyalash uchun va h.k. ;
-sonli analiz yasashda: approksimatsiya, regressiya, chiziqli va chiziqli emas sistemalarni yechish, sonli usullari va h.k.;
-avtomatikada: obrazlarni aniqlashda, optimal boshqarishlar, ishlab chiqarishni boshqarishda, robototexnikada va h.k. ;
matematik iqtisodda: katta makroiqtisodiy modellarini yechishda, ishbilarmonlik modellarida, yechim qabullash nazariyasida va o’yinlar nazariyasida.
Ko’plab ilmiy-texnik va amaliy masalalari, ulardagi qatnashadigan o’zgaruvchilariga cheklovlar qo’yilgan chiziqli emas programmalashtirish masalalarini yechishga olib kelinadi. Bunday cheklovlar qaralayotgan masalaning optimal yechimi izlanayotgan sohaning o’lchamlarini ancha kichraytadi. Shuning uchun, masalaning mumkin bo’lgan sohasining o’lchamlarining kichrayishi, uning yechimini topishni yengillashtiradigandek bo’lib ko’rinadi. Haqiqatdan ham,shartli chiziqli emas programmalashtirish masalalarini yechish, shartsiz masalani yechish bilan solishtirganda ancha qiyinlashadi. Sababi, shartsiz ekstremum masalasining optimal bo’lishining zaruriy va yetarli shartlarini, doimo cheklovlari bor masalalarga qo’llanishga bo’lmaydi. Sababi, shartli minimum masalalarining lokal optimal yechimi mumkin bo’lgan sohasining ichki nuqtasi bo’lgandagina shartsiz minimumning zaruriy va yetarli shartlaridan foydalanishga bo’ladi. Lekin ko’pchilik shartli minimum masalalarining minimum nuqtalari mumkin bo’lgan sohasining chegarasida yotadi. Bunday ChEP masalalari uchun analizning klassik natijalarini qo’llanish mumkin bo’lmaydi, sababi, masalaning optimal yechimiga, uning maqsad funksiyasining gradienti nolga teng bo’ladigan statsionar nuqtasida erishadi degan asosiy shart buzilishi mumkin[1, 2, 5,8].
Shartli minimum masalalari holatida ham bunday masalalarning yechimining optimal bo’lishining zaruriy va yetarli shartlari juda katta ahamiyatga ega bo’ladi. Sababi ular ChEP masalalarining xususiyatlarini o’rganish usullarining asosida yotadi, bunday masalalarni yechishning sonli usullarini yasaganda va asoslaganda qo’llaniladi va oddiy shartli optimizatsiyalash masalalarining aniq yechimlarini aniqlashga imkoniyat beradi[8].
Ko’p o’lchamli shartli optimizatsiyalash masalalarini sonli yechish usullarining ichida, shtraf funksiyalar usuli bilan chegaralovchi shartlariga ega bo’lgan dastlabki masaladan, uning optimal kriteriyalar strukturasini yangidan tuzish yo’li bilan shartsiz ekstremum masalasiga o’tishga imkoniyat beradi. Yangidan tuzilgan masalaning optimal yechimi dastlabki qo’yilgan masalaning yechimi bilan tengdek bo’ladi va dastlabki berilgan sohaga tegishli bo’ladi[1, 5].
Bitiruv malakaviy ishida chiziqli emas programmalashtirish masalasini yechishning shtraf funksiyalar usuli qaraladi[5].
Shtraf funksiyalar usulining asosiy g’oyasi bo’yicha, bunda berilgan funksiyaning argumentlariga mos qo’yilgan cheklovlarida, bu funksiyaning eng kichik(minimum) qiymatini topish masalasi, cheklovlari yo’q funksiyaning eng kichik(minimum) qiymatini topish masalasiga akslandirishdan iborat bo’ladi.
Shtraflarni yasashda ikki usuldan foydalanadi, shuning uchun shtraf funksiyalar usulining ikki turi bor. Ularning birinchisi ichki shtraf funksiyalar yoki ichki nuqtalar usuli deb ataladi, bu usuldan foydalanganda, berilgan chiziqli emas programmalashtirish masalasining maqsad funksiyasiga usulning ketma-ket yaqinlashuvlarining mumkin bo’lgan sohasining tashqi sohasiga chiqishga yo’l qo’yilmaydigan funksiya qo’shiladi. Shuning uchun bu usulda dastlabki masalaning optimal yechimiga yaqinlashuvchi bo’ladigan, mumkin bo’lgan nuqtalarning ketma-ketligi yasaladi. Lekin bu usul faqat cheklovlari tengsizliklar bo’lgan chiziqli emas programmalashtirish masalalarini yechish uchun qo’llanilishi mumkin.
Ularning ikkinchisi tashqi shtraf funksiyalar yoki tashqi nuqtalar usuli deb ataladi, bunda berilgan masalaning maqsad funksiyasiga, uning har bir bajarilmagan cheklovi uchun shtraf hisobida, ba’zi-bir funksiya qo’shiladi va kelib chiqqan yordamchi funksiyaning shartsiz ekstremum nuqtasi topiladi. Bu nuqtasi kelasi shartsiz ekstremum masalasi uchun boshlang’ich yaqinlashish bo’lib hisoblanadi. Bunday yasalgan nuqtalari berilgan chiziqli emas programmalashtirish masalasining mumkin bo’lgan to’plamiga tegishli bo’lmaydi, biroq uning optimal nuqtasiga yaqinlashuvchi bo’ladi[8].
Bu bitiruv malakaviy ishi kirish bo’limidan, uch paragrafdan, xulosa bo’limidan, adabiyotlar ro’yxatidan va qo’shimchalardan iborat.
Bitiruv malakaviy ishining birinchi paragrafida chiziqli emas programmalashtirish masalasining qo’yilishi qaraladi. Bunda ChEP masalalarini yechishning Lagranj ko’paytuvchilar usuli qaraladi. Berilgan masaladagi cheklovlar tenglama turida berilgan bo’lib, shuning uchun uni yechish uchun ko’p o’zgaruvchiga ega funksiyaning shartli ekstremum topishning klassik usullaridan foydalanamiz. Qo’yilgan masalani yechish uchun Lagranj funksiyasini yasaymiz va uning xususiy hosilalarini nolga tenglab, statsionar nuqtalarini aniqlaymiz. Biroq bu yerda global minimum yoki maksimum nuqtalarini aniqlash usuli noma’lum, shuning uchun global minimum(maksimum) ni aniqlash uchun mos statsionar nuqtalarida funksiyaning qiymatlarini hisoblash yetarli bo’ladi. Agarda berilgan funksiyasi va chegaralovchi funksiyalari uchun ularning ikkinchi tartibli xususiy hosilalari bor bo’lib va ular uzluksiz bo’lsa, unda statsionar nuqtalarda funksiyaning lokal ekstremum bor bo’ladiganligining yetarli shartlarini keltirishga bo’ladi[4].
Bu bitiruv malakaviy ishida qavariq va botiq deb ataluvchi funksiyalaridan ko’proq foydalanamiz, shuning uchun ular haqida ma’lumot keltirib ketdik. Chiziqli emas programmalashtirish guruhiga tegishli bo’lgan separabel funksiyalariga ega masalalarni taqribiy yechish usullarini qarab o’tildi[4,5].
Bitiruv malakaviy ishining ikkinchi paragrafida chiziqli emas programmalashtirish masalasini yechishning shtraf funksiyalar usuli haqida bayonet yasadik[5,8].
Bitiruv malakaviy ishining uchinchi paragrafida shartli chiziqli emas programmalashtirish masalasini shtraf-funksiyalar usuli bilan yechishga misollar keltirilgan.