Berdaq nomidagi qoraqalpoq davlat universiteti matematika fakulteti

2-§. Chiziqli emas programmalashtirish masalasini yechishning shtraf funksiyalar usuli

Chiziqli emas programmalashtirish masalasining shartli ekstremum qiymatini
topish uchun har xil yondashish tashkillashtirilgan. Shu yondashishlarning birida ba’zi bir yordamchi funksiyalarni, mahsus turda birlashtirib, chiziqli emas shartli ekstremum masalasini shartsiz optimizatsiyalash masalalarining ketma ketligiga olib kelish amali ishga oshirilgan. Bunday yordamchi funksiyalarni shtraf funksiyalar deb ataydi, ulardan foydalanadigan algoritmlarni esa shtraf funksiyalar usuli deb ataydi.
2.1. Algoritmlarni yasashning umumiy sxemasi. Mayli quyidagi shartli chiziqli emas programmalashtirish masalasi qo’yilgan bo’lsin:
,
,
bunda , - uzluksiz differensiallanuvchi funksiyalar.
Ba’zi-bir to’plamida funksiyaning minimum qiymatini topish masalasini qaraymiz. Formal turda bu masalasi quyidagi yig’indisining
,
shartsiz minimumini topish masalasiga ekvivalent bo’ladi, bu yerda indikator funksiyasi deb ataluvchi quyidagicha aniqlanadi:

Agarda to’plamining chegarasi tenglik yoki tengsizliklar turida berilgan bo’lsa, unda bu to’plamdagi funksiyalardan foydalanib barcha lar uchun ma’lum bir shtraflarini tuzishga bo’ladi, ya’ni
(2.1)
Unda dastlabki qo’yilgan masalasiga ekvivalent bo’lgan masalasi quyidagicha yoziladi:

.
Agarda minimum qiymatini va limitni topish amallarini o’rnini almashtirib yozishga mumkin bo’lsa, unda qadimgi shartsiz minimum topish masalalarining quyidagicha turdagi

ketma-ketligiga ega bo’lamiz. to’plamida bo’lganda, bu masalaning chegarasi bo’lib funksiyasining minimum nuqtasi bo’ladi.
shtraflarini tuzishning ikki usuli bor bo’lib hisoblanadi: ichki nuqtalar usuli(ichki shtraf usuli) va tashqi nuqtalar usuli(tashqi shtraf usuli).
Chiziqli emas programmalashtirish masalasining shartli ekstremum qiymatini
topish uchun har xil yondashish tashkillashtirilgan. Shu yondashishlarning birida ba’zi bir yordamchi funksiyalarni, mahsus turda birlashtirib, chiziqli emas shartli ekstremum masalasini shartsiz optimizatsiyalash masalalarining ketma ketligiga olib kelish amali ishga oshirilgan. Bunday yordamchi funksiyalarni shtraf funksiyalar deb ataydi, ulardan foydalanadigan algoritmlarni esa shtraf funksiyalar usuli deb ataydi.
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.