|
1.5 Nilder- Mid simpleks usuli
Qirralari n+1 nuqtada kesishadigan n-o‟lchovli geometrik figura (shakl)
simpleks deb ataladi.2-o‟lchovli fazoda uchburchak, 3 o‟lchovli fazoda tetraedr
simpliksni aniqlaydi. Simpleks usuli deb ataluvchi to‟g‟ri qidiruv usullari maqsad
funksiyasining qiymatlarini simpleksning qirralarida tekshirishga va markazi
minimum nuqtasiga qarab siljuvchi simplekslar ketma ketligini qurishga
asoslanadi.
Simpleks usullari guruhidan Nilder-Mid usuli keng tarqalgan usuldir.U
bo‟lganda funksiyani minimallashtirish uchun eng samarali usullardan biri
hisoblanadi.
Nilder-Mid usulida simpleks fazoda 3 ta amal yordamida deformatsiyalanadi
va siljitiladi: akslantirish, kengaytirish va qisish. Bu amallarning ma‟nosini
algoritm qadamlarini ko‟rib chiziqda aniqlashtiramiz:
1.
Maqsad funksiyasi qiymatlarini simpleks uchlarida hisoblaymiz:
2.
Simpleks uchlari orasidan funksiya qiymati
eng kichik bo‟lgan
nuqtani, qiymati
dan keyin keladigan
qiymatni qabul qiladigan
nuqtani,
funksiya qiymati
eng katta bo‟ladigan
nuqtani topamiz.
-nuqta eng yaxshi nuqta,
-nuqta yaxshi nuqta,
-eng yomon nuqta
deb ataladi.(5-chizmaga qarang)
3.
Eng yomon nuqtadan tashqari barcha simpleks uchlarining og‟irlik
markazini topamiz:
va
qiymatni hisoblaymiz
5-chizma.2-o’lchovli simpleksni almashtirish.
4.
nuqtaga nisbatan
nuqtaning aksi
ni topamiz va
ni hisoblaymiz. Akslantirish formulasi quydagicha bo‟ladi:
(9)
Eslatma. Usulning ikki o‟lchovli varyantida akslantirish operatsiyasini
asoslab ko‟rsatamiz. Bu holda akslantirish operatsiyasi 5.b-chizmada ko‟rsatilgan.
Maqsad funksiyasi uchburchak tomoni bo‟ylab
uchidan
ga harakatlanganda
kamayuvchi bo‟ladi, xuddi shunday
dan
ga harakatlanganda kamayuchi
bo‟ladi.Natijada funksiya eng kichik qiymatini
nuqtadan uzoqda simpleksning
qarama-qarshi
tomonida
qabul
qilishi
ehtimoli
katta
bo‟ladi.
koeffisenti
vektor uzulishining o‟zgarishini aniqlaydi:
Bu yerdan (9) formula kelib chiqadi.
5.
va
qiymatlarni taqqoslaymiz. Agarda
bo‟lsa u holda
tanlangan yo‟nalish bo‟yichakengaytirishni o‟tkazamiz va
nuqtani hosil
qilamiz. Uning radius vektori
(10)
formula bilan ifodalanadi.
qiymatni hisoblaymiz.
Eslatma. Kengaytirish operatsiyasi shuning uchun ham o‟tkaziladiki,
shart bajarilganda akslantirish mumkin tomonga qarab to‟g‟ri yo‟nalishnni
beradi. Minimum
nuqtadan biroz uzoqroqda bo‟lishi ham mumkin.Shuning
uchun ham tanlangan yo‟nalish bo‟yicha
nuqtadan nariroqqa harakat qilishi
maqsadga muvofiq.(5 b-chizma).
koeffisent
vektorning
akslantirishdahosil bo‟lgan kengayishini aniqlaydi.
6.
va
qiymatlarni taqqoslaymiz.
Agarda
bo‟lsa u holda
nuqtani
bilan almashtiramiz va
funksiyaning qiymati
ni
bilan almashtiramiz. So‟ngra minimumga
yaqinlashish shartini tekshirib ko‟ramiz va iteratsion jarayonni yakunlaymiz yoki
2-qadamga qaytamiz.
Agar
bo‟lsa
nuqtani e‟tiborga olmaymiz va
nuqtani
nuqta
bilan va
ni
bilan almashtiramiz. So‟ngra iteratsion jarayonning
yaqinlashishini tekshiramiz va uni yakunlaymiz yoki 2-qadamga qaytamiz.
7.
Agar 4-qadamda topilgan
nuqta uchun
bo‟lsa, u holda
va
nuqtalarni taqqoslaymiz.
Agar
bo‟lsa 8-qadam – qisqartirish qadadmiga o‟tamiz.
Agar
bo‟lsa
nuqtani
nuqta bilan va
ni
bilan
almashtiramiz, so‟ngra simpleksni qisqartirishga o‟tamiz.
8.
nuqtaning radius – vektorini
(11)
formulabilan hisoblab qisqartirish operatsiyasini o‟tkazamiz, va maqsad
funksiyasining qiymatini qisish nuqtasida hisoblaymiz.
Eslatma.Akislantirish natijasida
nuqtani hosil qilib va
ni o‟rnatib
shunday xulosaga kelamiz:
nuqtadan ancha uzoqqa siljiganmiz va vaziyatni
o‟zgartirish uchun
nuqtadan eng yaxshi va yaxshi nuqtalarga yaqinroq bo‟lgan
nuqtaga simpleksning uchini o‟rnatamiz. (5 v-chizma).
9.
va
qiymatlarni taqqoslaymiz.
Agar
bo‟lsa
nuqtani
nuqta bilan va
ni
bilan almashtiramiz.
Yaqinlashishni tekshirib ko‟ramiz, agar u ta‟minlanmagan bo‟lsa 2-qadamga
qaytamiz.
Agar
bo‟lsa maqsad funksiyasining
dan kichik qiymatini toppish
muvofaqiyatsiz bo‟lgan bo‟ladi, shuning uchun simpleksni qisqartirishga o‟tamiz.
10. Barcha
nuqtalarni radius-vektorlari
bo‟lgan yangi nuqtalarga
ko‟chirish yordamida simpleksda qisqartirish (tortilish) o‟tkazamiz, ya‟ni simpleks
qirralarining o‟rtalarida yotgan nuqtalarga o‟tamiz (5-chizmaga qarang). So‟ngra
simpleksning barcha yangi uchlarida funksiya qiymatlarini hisoblaymiz va
yaqinlashishni tekshiramiz. Agarda yaqinlashish ta‟minlanmasa 2-qadamga
qaytamiz.
Simpleks usulida yaqinlashishni tekshirish maqsad funksiyasining simpleks
uchlaridagi standart chetlanishi
ni hisoblashga asoslangan. Bu yerda
funksiyaning simpleks uchlaridagi o‟rta qiymati. Agar
bo‟lsa funksiyasining
barcha qiymatlari bir-biriga juda yaqin bo‟ladi va shuning uchun ular
eng
yaxshi nuqtaning yaqinida joylashgan minimumning atrofida bo‟lishi mumkin.
Nilder va Midlar juda ko‟p tajribalarga asosan
,
va
koeffisentlarni
quydagicha tanlashni tavsiya qiladi:
. Boshlang‟ich simpleks ixtiyoriy bo‟lishi
mumkin.
Bayon qilingan algoritmning qadamlari quyidagi blok sxema orqali ko‟rinadi:
6-chizma.Simpleks usuli algoritmining blok-sxemasi.
Do'stlaringiz bilan baham: | 
