Berdaq nomidagi qoraqalpoq davlat universiteti matematika fakulteti

2.2. Ichki shtraf funksiyalar usuli. Mayli bizga shartli ekstremum masalasi berilgan bo’lsin:

,

. (2.2)

Bunda to’plami tengsizliklar turida berilgan uzluksiz funksiyalari yordamida chegaralangan. Shuning bilan birga bu to’plamda ba’zi-bir nuqtalari bor bo’lib va bu nuqtalarda bo’ladi. Shuning uchun aniq bir farazlarda indikator funksiyasiga yaqinlashadigan va nuqtasi to’plamning chegarasiga yaqinlashgan sari cheksiz o’suvchi shtraflar ketma-ketligini yasash(3-rasm) juda bir qiyin masala emas bo’ladi. Bu holatda dastlabki qo’yilgan masalaning barcha chegaralovchi shartlari qat’iy tengsizlik turida bajariladigan nuqtalardan boshlab,

(2.3)

shtraf funksiyaning minimum qiymatini izlashni boshlash kerak. Izlash jarayonini to’g’ri tashkillashtirilgan holatda bu aytilgan shartlari avtomat turda saqlanib qoladi va bundan buyon: yig’indining minimum qiymatini topish masalasini yechish uchun shtraf funksiyasi cheksiz bo’ladigan to’plamining chegarasiga chiqish ma’noga ega bo’lmay qoladi. Demak (2.3) funksiyaning minimum qiymatiga yaqinroq jarayoni to’plamidan hech vaqtda chiqib keta olmaydi. Shuning uchun bu usulning nomini "ichki nuqtalar usuli" deb ataydi.

Ko’pincha qo’yilgan (2.2) masalasi uchun shtraf sifatida quyida berilgan funksiyalardan foydalanadi:

(2.4)

. (2.5)

Bu yerda -shtraf parametri deb ataladigan musbat son. Agarda qo’yilgan (2.2) masalasi qavariq programmalashtirish masalasi bo’lsa, ya’ni botiq funksiya bo’lsa, unda berilgan shtraf funksiyalarning ikkalasi ham qavariq bo’ladiganligini atab o’tish ahamiyatli bo’ladi. Agarda bo’lganda intilsa, unda (2.1) munosabati (2.4) va (2.5) shtraf funksiyalari uchun bajariladi. (2.4) shtraf funksiyasini foydalanib (2.2) masalani yechish algoritmi quyidagicha bo’ladi:

1) sharti bajariladigan nuqtasini va monoton kamayuvchi, nol qiymatiga yaqinlashadigan musbat sonlarning ketma-ketligini saylab olamiz;

2) oldingi iteratsiyadan olingan nuqtasidan boshlab, da

,

funksiyasidan bo’yicha shartsiz minimum topish masalasi yechiladi. Natijada navbatdagi nuqtasi aniqlanadi.

Agarda algoritmning har bir qadamida funksiyasidan bo’yicha global minimum nuqtalarini topish imkoniyati bo’lsa, unda chegaralovchi shartlarida ketma-ketligi funksiyasining global minimum qiymatiga yaqinlashadi. Agarda nuqtasi esa funksiyasining shartsiz lokal minimum nuqtalari bo’lsa, unda yetarli oddiy taxminlar yuritib, bu nuqtalarning chegarasi (2.3) masalaning lokal yechimi bo’ladiganligini aniqlashga bo’ladi. Birinchi tasdiqlashning dalillanishini 2.3 kelasi bo’limida dalillab ko’rsatamiz. Xususiy holda qavariq programmalashtirish masalalari uchun yaqinlashuvchi bo’ladiganligining boshqa bir dalillanishlarini keltirishning keragi yo’q, sababi bunda funksiyasi bo’yicha qavariq bo’lib va shunga mos ular faqatgina global minimum qiymatlariga ega bo’ladi.