Berdaq nomidagi qoraqalpoq davlat universiteti matematika fakulteti

1.4. Separabel funksiyali masalalarni taqribiy yechish usullari. Chiziqli emas programmalashtirish masalalarini taqribiy yechishning bir usulini qaraymiz.
funksiyasining maksimal qiymatini quyidagi chegaralovchi shartlarida, ya’ni
(1.13)
hisoblab toping.
Chegaralovchi sistemasidagi va maqsad funksiyasidagi barcha funksiyalari separabel funksiyasi.
Bu taqribiy usuli va funksiyalarini bo’laklab-chiziqli approksimatsiyalashga asoslangan. Bunda taqribiy masalasi paydo bo’lib, uning yechimini simpleks usuli yordamida topishga bo’ladi. Umumiy holda taqribiy masalaning lokal maksimumi aniqlanadi, demak bundan (1.13) masalasi uchun taqribiy lokal maksimumi aniqlanadi. Agarda mumkin bo’lgan yechimlar to’plami qavariq bo’lsa, esa-botiq funksiyasi bo’lsa, unda lokal maksimum qiymati bir vaqtda global maksimum qiymatida bo’ladi. Bu holda (1.13) masalani yechish uchun yaqinlashuvi bo’lgan, taqribiy masalaning global maksimum qiymatida topishga bo’ladi.
(1.13) masalasi uchun taqribiy masalani tuzishni qaraymiz. Mayli kesmasida aniqlangan, ixtiyoriy turdagi bir o’zgaruvchisiga ega bo’lgan uzluksiz funksiyasi(2- rasm) berilgan bo’lsin. Bu kesmada soni bo’lgan nuqtalarini saylab olamiz, bunda . Barcha qiymatlari uchun qiymatlarini hisoblaymiz. Juft juftdan va , nuqtalarini to’g’ri kesmalar bilan tutashtiramiz. Paydo bo’ladigan bo’lakli-chiziqli funksiyasi kesmasida funksiyasini approksimatsiyalaydi. Approksimatsiyalash aniqligini nuqtalarini mos turda saylab olish yo’li bilan boshqarishga bo’ladi. Mayli (1.13) masalasidagi barcha va funksiyalari uzluksiz bo’ladi deb faraz qilamiz. o’zgaruvchisi qiymat qabul qiladigan oralig’ini nuqtalari bilan bo’lib chiqamiz va yuqorida keltirilgan usulidan foydalanib va funksiyalarining bo’lakli-chiziqli va approksimatsiyalarini yasaymiz. Unda (1.13) masalasining o’rniga

(1.14)
taqribiy masalasini qaraymiz.
(1.14) bo’lakli-chiziqli funksiyalari uchun ularning analitik ifodasini topamiz. 2- rasmini qaraymiz. Agarda nuqtasi kesmasiga tegishli bo’lsa, unda funksiyasi ushbu quyidagi funksiyasi bilan approksimatsiyalanadi:
. (1.15)
kesmasida yotgan ning bu qiymatlarida uni turida ko’rsatishga bo’ladi, bunda shartidan ba’zi-bir saylab olamiz. ega bo’lamiz. (1.15) ga o’rniga keyingi ifodasini olib borib qo’yib, natijada

ega bo’lamiz.
Agarda deb belgilab olsak, unda aniq bir lar uchun
(1.16)
bo’ladigan va larning yagona bir qiymatlari bor bo’ladi deb tasdiqlashga bo’ladi.
Qabul qilingan belgilashlardan foydalanib, quyidagicha yozishga bo’ladi:
, (1.17)
, (1.18)
. (1.19)
Bunda bir yoki ikki qo’shni noldan o’zgacha bo’lishi mumkin. Bunday usul bilan ni bir ma’noli aniqlashga bo’ladi, shuning bilan birga (1.18) funksiyasi siniq chizig’i uchun analitik ifodasi bo’lib hisoblanadi.
(1.13) masalasini qaytadan qaraymiz. Mayli o’zgaruvchisi qabul qilishi mumkin bo’lgan ning maksimal qiymati aniqlangan bo’lsin. kesmasini bo’ladigandek qilib, soni bo’lgan nuqtalar yordamida kichik kesmalariga bo’lamiz. va funksiyalarini mos turda quyidagicha yozishga bo’ladi:
(1.19)
, (1.20)
bunda
, (1.21)
. (1.22)
Bu yerda barcha lar uchun bo’ladi. va funksiyalarini aniqlanganda kesmasini bir xil qilib bo’lib foydalanadi. (1.14) formulasiga bu funksiyalarning ifodasini olib borib qo’yib, quyidagiga ega bo’lamiz:

,
, (1.23)
bu yerda barcha lar uchun .
Paydo bo’lgan masalaning chiziqli programmalashtirishning qadimgi masalasidan farqi, bunda har uchun eng kamida ikki qo’shni joylashgan musbat qiymatdagi bor bo’lishi kerak. (1.21) munosabati (1.23) formulaga kiritilmagan, uni (1.23) masalani yechgandan keyin, ning taqribiy qiymatlarini aniqlash uchun foydalanishga bo’ladi. Masalani simpleks usuli bilan yechadi, bazisni saylab olish uchun chegaralovchi shartlarini hisobga olib va bunda ikki qo’shni emas mos keladigan ikki vektorni bazisga kiritishga bo’lmaydiganligini hisobga olish kerak. Masalani yechish jarayonida barcha vektorlari uchun bo’lishi mumkin yoki ba’zi ayirmalari . Biroq bazisni saylab olishiga qo’yiladigan chegaralovchi shartlari kelasi iteratsiyani bajarishga imkoniyat bermaydi. Unda - (1.23) masalaning eng keying bazis yechimiga mos keladigan qiymati va u taqribiy masalaning lokal maksimumi bo’ladi.