1. Chiziqsiz dasturlash masalasining qo‘yilishi Shartsiz optimallash masalasini yechish usullari Lagranj aniqmas ko‘paytuvchilar usuli

Amaliy mashg‘ulot uchun misollar
Quyidagi masalaga Lagranj ko‘paytuvchilar usulini qo‘llab yeching.

1. 2.

3. 4.
f = x₁x₂ + x₂x₃ (max)

4. 6.
F_max= 4х₁+3х₂ F_min= x² + y²
1/2 х + 1/3 у = 1.


5. Gradient usullar
Chiziqsiz dasturlash masalalarini yechishda eng ko‘p qo‘llaniladigan usullardan biri gradient usullaridir. Funksiyalarning minimumini topishda qo‘llaniladigan gradient usullar dastlabki tanlab olingan X taqribiy yechimni tenglamaning aniq yechim yo‘nalashi bo‘yicha ketma-ket aniqligini oshirishga asoslangandir.
T a ' r i f. n o‘lchovli R fazoda berilgan F(X) funksiyaning X nuqtadagi gradienti grad deb, F(X₀+X) – F(X₀) chekli orttirmaning chiziqli qismiga aytiladi, ya'ni F(X₀+X) – F(X₀) = grad F(X₀)X+0(X).
Gradient usullar chiziqli bo‘lmagan masalalarni yechishning taqribiy usullariga kiradi, chunki ular aniq qiymatni faqatgina cheksiz (faqatgina alohida hollarda chekli) qadamda beradi.
Gradient usulda chiziqli bo‘lmagan dasturlashning ixtiyoriy masalasini yechish mumkin, buning uchun faqatgina lokal ekstremumni topish yetarli. Shuning uchun ularni qo‘llash qavariq dasturlash masalalarini yechishda ko‘proq samara beradi, chunki bu yerda lokal ekstremum bir vaqtning o‘zida global hamdir.
X ning o‘zgarish sohasida chegaralanmagan f(x) funksiyani maksimallashtirish masalasini ko‘rib chiqaylik. F(x) funksiyaning ekstremal qiymatini ixtiyoriy mavjud yechimdan, masalan nuqtadan boshlab qidirish mumkin.
F(x) funksiyaning nuqtadagi gradienti deb shunday vektorga aytiladiki, uning koordinatalari mos o‘zgaruvchi bo‘yicha olingan birinchi tartibli hosilalarning qiymatiga teng, ya'ni
.
Berilgan nuqtadagi funksiya gradienti f(x) funksiyaning tezroq o‘sish yo‘nalishini ko‘rsatadi. nuqtaning gradient bo‘ylab yangi nuqtaga ko‘chirilish tenglamasi
(5.1)
ga teng bo‘lgan to‘g‘ri chiziq orqali amalga oshiriladi. Bu yerda -shunday sonli o‘zgaruvchiki, unga qarab ko‘chish qadamining kattaligi o‘zgaradi. Funksiya eng katta qiymatga erishadigan kattaligi funksiya ekstremumining zaruriy shartidan topilishi mumkin:
(5.2)
parametrni hisoblagandan so‘ng ( ning qiymatini (5.1) ga qo‘yib) navbatdagi nuqta topiladi. nuqtada yana gradient topamiz, harakat esa to‘g‘ri chiziq orqali yangi gradient bo‘ylab funksiya ushbu yo‘nalishda eng katta qiymatga erishadigan nuqtagacha amalga oshiriladi va h.k. Yechish jarayoni funksiya gradienti nol'ga teng bo‘lgan nuqta topilguncha davom etadi. nuqtada f( ) maqsad funksiyaisi maksimal qiymatga erishadi.
Misol . funksiyaning masksimumini toping. Yechish jarayoni nuqtadan boshlansin.
Echish. f(x) funksiyaning har bir o‘zgaruvchisi bo‘yicha xususiy hosilalarni topamiz. ; . nuqtadagi funksiya gradientlari =(2-2*4; 4-2*4)=(-6;-4) ga teng bo‘ladi. nuqtadan gradient bo‘ylab yangi nuqtaga ko‘chiramiz:
nuqtadagi funksiya gradientlari

Ekstremumning zaruriy sharti quyidagi tenglamani beradi

Bu yerdan kelib chiqadiki bo‘lgani uchun, topilgan qiymat funksiyaning maksimum nuqtasi bo‘ladi.
Qidiruv traektoriyasidagi navbatdagi nuqta va =(2-2*1; 4-2*2)=(0;0). Demak shunday nuqtaki, unda funksiya o‘zining maksimal qiymatiga erishadi (boshlang‘ich nuqtada . 5.3 rasmda berilgan masalaning grafik ko‘rinishi keltirilgan.

rasm

Endi chiziqli bo‘lmagan dasturlashning chegaralangan masalalarini yechishga o‘taylik. Masalaning mazmuni quyidagicha: quyidagi
(5.3)
chegarali f(x) funksiyaning maksimumi topilsin. Bu erda f(x) funksiya differensiallanuvchi botiq funksiyadir.
Bu kabi masalalarni yechishda ikkita hol uchraydi: 1) maqsad funksiyasi yagona eksremumga ega va u mavjud yechimlar sohasining ichida joylashgan. Bu holda masalani yechish jarayoni ( optimal nuqtani qidirish) yuqorida bayon etilgandan mutlaqo farq qilmaydi; 2) maqsad funksiyasi mavjud sohaning chegarasida joylashgan nuqtada ekstremal qiymat qabul qiladi. Bu holda masalani yechish ketma-ketligi quyidagicha bo‘ladi: Agar boshlang‘ich nuqta mavjud sohaning ichida joylashsa (hamma cheklanishlar qat'iy tengsizlik ko‘rinishida tasvirlansa), ko‘chishni gradient bo‘ylab amalga oshirish darkor. Lekin navbatdagi nuqtaning koordinatalari (5.3) dagi shartlarni qanoatlantirishi kerak, ya'ni quyidagi tengsizliklar bajarilishi shart
(5.4)
(5.4) tenglamalar tizimini yechish natijasida nuqta mavjud oraliqqa tegishli bo‘lgan o‘zgaruvchining mavjud qiymatlar oralig‘i topiladi. , (5.2) tenglamalarni yechish natijasida topilgan qiymat oraliqqa tegishli bo‘lishi kerak. Agar qiymat oraliqdan tashqarida yotsa, sifatida olinadi. Jumladan qidiruv traektoriyasining navbatdagi nuqtasi (5.4) tizimning tengsizligiga mos keluvchi chegaraviy gipertekislikda yotadi, shuni hisobga olib, tizimni yechishda topiladi.
Agar boshlang‘ich nuqta chegaraviy gipertekislikda yotsa (yoki qidiruv traektoriyasining navbatdagi nuqtasi chegaraviy traektoriyada yotib qolsa), yo‘nalish matematik dasturlashning
(5.5)
tengliklar bajariladigan i lar uchun quyidagi yordamchi masalasini yechish orqali aniqlanadi:
(5.6
bu yerda (5.6) va (5.5) shart nuqtaning mavjud soha cherasiga tegishli bo‘lish yoki bo‘lmasligini, ((5.6) shart nuqtadan vektor bo‘yicha ko‘chirish mavjud sohaning ichiga yoki chegarasi bo‘ylab yo‘nalganligini aniqlaydi, (5.5) shart esa kattalikni chegaralash uchun zarur). Qidiruv trayoktoriyasining keyingi nuqtasi uchun o‘zgaruvchining qiymati topiladi. Bunda ekstremumning zaruriy sharti hisobga olinadi.
Yechish jarayoni bo‘lishini ta'minlovchi nuqta olinganda to‘xtaydi.