7-mavzu. Chiziqsiz dasturlash masalalari 1-ma’ruza rejasi
Shartlari tenglamalardan iborat bo’lgan shartli ekstremum masalasi va uni yechish uchun Lagranj usuli
Yüklə 111,74 Kb.
|
|
4. Shartlari tenglamalardan iborat bo’lgan shartli ekstremum masalasi va uni yechish uchun Lagranj usuli
Faraz qilaylik (2), (4) masalani yechish talab qilinsin, ya’ni gi(x1, x2, ..., xn)=bi i= tenglamalar sistemasini qanoatlantiruvchi va Z=f(x1, x2, ..., xn) funktsiyaga maksimum (minimum) qiymat beruvchi X=( x1, x2, ..., xn) nuqtani topish kerak bo’lsin. gi(x1, x2, ..., xn) va f(x1, x2, ..., xn) funktsiyalar va ularning hammasi x1, x2, ..., xn noma’lumlar bo’yicha olingan xususiy hosilalari uzluksiz deb faraz qilamiz. Noma’lumlarga nomanfiylik sharti qo’yilmaganda masalani Lagranjning aniqmas ko’paytiruvchilar usulini qo’llab yechish mumkin. Lagranj usulining g’oyasini quyidagi xususiy holda ko’ramiz. Faraz qilaylik, quyidagi masala berilgan bo’lsin g(x1, x2)=b, Z=f(x1, x2) . (25) g(x1, x2) va f(x1, x2) funktsiyalar uzluksiz va differentsiallanuvchi funktsiyalar. X0= nuqta g(x1,x2)=b tenglamani qanoatlantirib, Z=f(x1,x2) funktsiyaga mahalliy maksimum (minimum) qiymat berish uchun qanday zaruriy shartni qanoatlantirish kerak ekanligini ko’ramiz. X0= nuqtada g(X0)/dx1, g(X0)/x2 xususiy hosilalardan kamida biri noldan farqli, masalan, g(X0)/ x2 0 bo’lsin. U holda oshkormas funktsiyalar haqidagi teoremaga asosan x10 ning kichik >0 atrofi mavjud bo’ladiki, bu atrofda g(x1,x2)=b tenglamani x2 ga nisbatan yechish mumkin, ya’ni x2= (x1), bu yerda funktsiya (x10, (x10)) nuqta atrofida uzluksiz differentsiallanuvchidir. Har bir (x1, (x1)) nuqta masalaning joiz yechimlar to’plami G ga tegishli. Shuning uchun f(x1, x2) funktsiyadan ham x2 ni yuqotish mumkin, ya’ni Z=F(x1)=f(x1, (x1)), /x1-x10/< . Lekin, X0 nuqtada f funktsiya g(x)=b shartni qanoatlantiruvchi mahalliy maksimumga (minimumga) ega bo’lsa, x10 ning 0(0< 0< ) atrofidagi har qanday x1 uchun F (x1) F (x10) [F (x1) F (x10)] tengsizlik o’rinli bo’ladi. Bu holda F(x1) funktsiya x10 da shartsiz maksimum (minimum) ga erishadi. F(x1) funktsiya x10 ning 0 atrofida differentsiallanuvchi va x10 da shartsiz ekstrimumga erishgani uchun bo’ladi. F funktsiyani murakkab funktsiya sifatida differentsiallab, quyidagini hosil qilamiz: bunda oshkormas funktsiyalarga doir teoremaga asosan:
belgilash kiritsak, X0 nuqtaning ekstremal nuqta bo’lishi uchun quyidagi zaruriy shartlarni hosil qilamiz: (26) Hosil bo’lgan sistema uchta noma’lumli uchta tenglamalar sistemasidan iborat. Bu sistemaning yechimidan iborat bo’lgan X G nuqtada f funktsiya mahalliy maksimumga (minimumga) erishmasligi ham mumkin, lekin f funktsiyaga g(x)=b shart bajarilganda mahalliy maksimum (minimum) qiymat beruvchi nuqta albatta (26) sistemaning yechimi bo’lishi kerak. Demak, (25) masalaning yechimini topish uchun (26) sistemaning hamma yechimlarini topish kerak. Bu sistema X0 nuqtaning tenglamalari berilgan (25) shaklda bo’lgan masala yechimi bo’lishining zaruriy shartlaridir. Bu shartlarni quyidagi formal usul bilan ham hosil qilish mumkin. Buning uchun funktsiyani tuzamiz. Bu funktsiyadan x1, x2 va lar bo’yicha xususiy hosilalar olib ularni 0 ga tenglaymiz: Hosil bo’lgan sistema (26) sistemaning o’zidan iborat. Bu yerda F- Lagranj funktsiyasi, - Lagranj ko’paytuvchilari deb ataladi. Endi umumiy holni, ya’ni noma’lumlar soni n ta va tenglamalar soni m (m
tenglamalar sistemasiga ega bo’lamiz. Bu sistemaning yechimi esa X=(0,0) nuqtani bermaydi. Bunday hollarning oldini olish va Lagranj usulini kengroq qo’llashga imkon yaratish uchun Lagranj funktsiyasini quyidagi (28) ko’rinishda yozish maqsadga muvofiq ekanligi aniqlangan. Bu holda (27) sistemani yechishdagi formal qiyinchiliklar engillashadi va da berilgan masala xos chegaraviy shartli bo’ladi. Yuqoridagi misolda bunga ishonch hosil qilish mumkin. Agar f(X) funktsiya X0 nuqtada ekstremumga erishsa, u , j= gi(X0)=bi, (29) tenglamalar sistemasini qanoatlantirish kerak. ( lardan kamida bittasi noldan farqli). Bu m+n ta tenglamalar sistemasi shartli optimallashtirish masalasining yechimi mavjudligining zaruriy sharti hisoblanadi. Bu shartni (28) Lagranj funktsiyasining xj(j= ) va lar buyicha xususiy hosilalarni 0 ga tenglab hosil qilish mumkin. Umumiylikni buzmasdan (29) da 0 ni 0 yoki 1 ga teng deb qabul qilish mumkin. Bu o’rinda quyidagilarga e’tibor berish kerak: Agar X0 nuqtada Q= matritsaning r (Q) rangi va Qf=(Q/f) matritsaning rangi r(Qf) [r(Qff) bajarilsa, berilgan masala normal masala bo’ladi va 0=1 deb qabul qilish mumkin. X0 nuqtada r(Qf) > r(Q) tengsizlik, bajarilganda (29) shartni qanoatlantiruvchi lar orasida 0 dan farqlilari bo’lishi uchun 0=0 deb qabul qilish mumkin. Agar X0 nuqtada r(Qf) = r(Q) = m tenglik bajarilsa, bir qiymatli aniqlanadi. X0 nuqtada r(Qf) > r(Q) yoki r(Qf) = r(Q) Lagranj ko’paytuvchilari iqtisodiy ma’noga ega ekanini ko’rsatish uchun (7.4) tenglamalar sistemasining ozod hadlari ma’lum bir intervalda o’zgaruvchan bo’lsin deb faraz qilamiz. U holda f(X) funktsiyaga ekstremal qiymat beruvchi nuqta ham o’zgaradi. Bu nuqtaning koordinatlari b(b1, . . .,bn) vektorning funktsiyasidan iborat, ya’ni xj(b)=xj(b1,b2, . . .bm), j= . Buni nazarga olib tuzilgan Lagranj funktsiyasi ham b vektorining funktsiyasidan iborat bo’ladi, ya’ni F(b)=f(X(b))+ (b)[bi-gi(X(b))] Bu funktsiyadan bi bo’yicha hosila olib . ega bo’lamiz. Bundan (7.27) ga asosan . F(X*, )=f(X*) tenglik o’rinli bo’lganligi sababli . Bu tenglikka asosan bi ozod hadlarning (resurslaring) o’zgarishi maqsad funktsiyasiga qanday ta’sir ko’rsatishini bildiradi. ning miqdoriga qarab har bir bi parametrni optimal yechimga qo’shgan hissasini aniqlash mumkin yoki Agar b=1 bo’lsa f= i, ya’ni bi parametrni bir birlikka o’zgartirish natijasida maqsad funktsiyaning qiymati i birlikka o’zgaradi. Shunday qilib, i larning 10, 20, ... , 0m qiymatlari ma’lum bo’lsa, masalaning har bir chegaraviy shartining optimal yechimi f(X0) ga qo’shgan hissasini aniqlash mumkin. Jumladan, i0=0 bo’lganda tegishli tenglama masala uchun ahamiyatsiz bo’ladi. Bunday tenglamani tashlab yuborish ham mumkin. Agar i0>0 bo’lsa, u holda gi (X)=bi tenglamadagi ozod hadni bir birlikka o’zgartirsak, Z=f(X) funktsiyaning qiymati i0 miqdorga o’zgarishini ko’rsatadi. Klassik optimallashtirish masalasi (2)-(4) uchun yaratilgan Lagranj usulini noma’lumlarga nomanfiylik sharti qo’yilgan hol uchun hamda shartlari tengsizliklardan iborat bo’lgan shartli optimallashtirish masalalari uchun ham umumlashtirish mumkin. Faraz qilaylik, (2)-(4) masalada noma’lumlarga nomanfiylik sharti kiritilgan bo’lsin, ya’ni quyidagi masalani yechish talab qilinsin: g1(x1,x2, . . .,xn)=bi, , mxj 0, j= , (31) Z=f(x1,x2, . . .,xn) (32) Bu yerda f va gi funktsiyalar uzluksiz va birinchi tartibli uzluksiz hosilaga ega. Maqsad funktsiya xj0 shart bajariladigan sohaning ichki nuqtalarida yoki chegarasida ekstremumga erishishi mumkin. Ekstremum nuqtani X* bilan belgilaymiz. Agar X* mumkin bo’lgan rejalar to’plamining ichki nuqtasi bo’lsa, u holda ekstremum mavjudligining zaruriy sharti (29) dan iborat bo’ladi. Demak, birinchi qadamda (29) sistemaning xj0 sohada yotuvchi hamma yechimlarini topib, ular uchun Z funktsiyaning qiymatini aniqlash, so’ngra xj0 sohaning chegarasini tekshirish kerak. Chegarada kamida bitta xj=0 bo’ladi. Faraz qilaylik faqat bitta xj, masalan xk=0 bo’lsin. bu holda m ta tenglamali va n-1 o’zgaruvchili masalani ko’ramiz. Bu masala uchun (29) sistemani yechib, xj0 sohaning ichida yotuvchi hamma yechimlarini topamiz va har bir yechimdagi Z funktsiyaning qiymatini aniqlaymiz. har bir noma’lumni 0 ga tenglash mumkin bo’lganlik uchun n-1 o’zgaruvchili va m ta tenglamali sistemani yechish kerak. So’ngra 2 ta o’zgaruvchini 0 ga teng deb qabul qilamiz va n-2 o’zgaruvchili m ta tenglamali masalani yechamiz. Bunday masalalar soni C ga teng. Bundan so’ng 3 ta o’zgaruvchini 0 ga teng deb qabul qilamiz va hokazo, oxirida n-m ta noma’lumga 0 qiymat beramiz va m o’zgaruvchili m ta tenglamalar sistemasidan iborat masalani yechamiz va qolgan m ta noma’lumning qiymatlarini topamiz. Bu nuqtalarning har birida Z funktsiyaning qiymatini hisoblaymiz. U qiymatlar ichida eng kattasi Z funktsiyaning global maksimumini, eng kichigi esa global minimumini beradi. Endi no’malumlarga nomanfiylik shartlari qo’yilmagan, lekin chegaraviy shartlarning bazilari tengsizliklardan iborat bo’lgan quyidagi masalani ko’ramiz: gi(x1,x2, . . . ,xn) bi,i= gi(x1,x2, . . . ,xn) bi,i= gi(x1,x2, . . . ,xn) bi,i= Z=f(x1,x2, . . . ,xn) Masaladagi tengsizliklarga xsi(i= ) qo’shimcha o’zgaruvchilarni kiritib, quyidagi tenglamlar sistemasini hosil qilamiz: gi(x1,x2, . . . ,xn)+ xsi=bi, i= gi(x1,x2, . . . ,xn)-xsi=bi, i= gi(x1,x2, . . . ,xn)= bi, i= xsi 0, i= f(x1,x2, . . . ,xn) . Berilgan masaladagi gi(x1,x2, . . . ,xn) bi shart xsi 0, i= shartga, gi(x1,x2, . . . ,xn) bi, shart esa i= shartga teng kuchlidir. Z funktsiyaning global ekstremumini topish uchun En fazodagi nomanfiy oktantning hamma ichki nuqtalarini (xsi 0) va chegaraviy nuqtalarini (bunda ba’zi xsi=0) tekshirishimiz kerak bo’ladi: xsi>0(i=1,m) bo’lgan holni ko’ramiz. Bu holda Lagranj funktsiyasi quyidagi ko’rinishda bo’ladi: (7.29) ga asosan bu funktsiyadan va lar bo’yicha olingan barcha xususiy hosilalar 0 ga teng bo’lishi kerak. Jumladan, bu funktsiyadan lar bo’yicha olingan xususiy hosilalarni 0 ga tenglab, qo’yidagiga ega bo’lamiz: .
Yüklə 111,74 Kb. Dostları ilə paylaş:
|