|
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:
Maqsad funksiyasi qiymatlarini simpleks uchlarida hisoblaymiz:
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)
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: |
