Shartli va shartsiz optimallashtirish, qo'llash sohalari. Shartsiz va shartli optimallashtirish usullari Ekspert baholash usullari
variantlarning umumiy to'plamidan siz gistogramma yaratishingiz, yaxshi variantlar qanchalik tez-tez sodir bo'lishini baholashingiz va nihoyat, siz qaror qabul qilishingiz mumkin - qidiruvni davom ettirish yoki topilgan yechim bilan cheklanish.
Tasodifiy zondlash protsedurasining universalligi va soddaligiga qaramay, hisoblashning sezilarli murakkabligi tufayli uni cheklab bo'lmaydi. Shuning uchun usullar yanada keng tarqaldi yo'naltirilgan qidiruv yechimlar.
4.5.3. Cheklanmagan optimallashtirish usullari
Yuqorida muhokama qilingan barcha shakllarda ekstremumga erishish uchun zarur shart-sharoitlar chiziqli bo'lmagan tenglamalar tizimini - juda murakkab va ko'p vaqt talab qiladigan vazifani echishga olib keladi (hatto hisoblash matematikasida ham chiziqli bo'lmagan tenglamalarni echish ko'pincha qandaydir turdagi tenglamalarga qisqartiriladi). optimallashtirish muammosi). Shuning uchun amalda funktsiyalarni optimallashtirishning boshqa yondashuvlari qo'llaniladi, ularni ko'rib chiqish to'g'ridan-to'g'ri usullar deb ataladigan usullardan boshlanadi. Kelajakda biz minimallashtirish haqida gapiramiz, shuning uchun ekstremum minimaldir.
Hozirgi vaqtda ham shartsiz, ham shartli optimallashtirish masalalari uchun ko'plab raqamli usullar ishlab chiqilgan. Raqamli usulning sifati ko'plab omillar bilan tavsiflanadi: konvergentsiya tezligi, bir iteratsiyaning bajarilish vaqti, usulni amalga oshirish uchun zarur bo'lgan kompyuter xotirasi hajmi, echilayotgan masalalar sinfi va boshqalar. Yechishdagi masalalar ham juda xilma-xil: ular yuqori va past o'lchamlarga ega bo'lishi mumkin, unimodal va ko'p ekstremal va hokazo. Bir turdagi muammolarni hal qilish uchun samarali bo'lgan bir xil usul boshqa turdagi masalalar uchun mutlaqo nomaqbul bo'lib chiqishi mumkin.
Quyida nochiziqli dasturlash masalalarini yechishning asosiy usullari haqida umumiy ma’lumot berilgan. Shuni yodda tutish kerakki, bunday usullarning butun ro'yxati juda keng va ochiq qolmoqda. Bundan tashqari, ko'rib chiqilayotgan bir qator usullar uchun turli xil modifikatsiyalar ma'lum. Ko'proq batafsil ma'lumot dan olish mumkin
misol, ichida.
Hech qanday cheklovlar mavjud bo'lmaganda, cheksiz optimallashtirishning to'g'ridan-to'g'ri usullarini ko'rib chiqishdan boshlaylik.
To'g'ridan-to'g'ri shartsiz optimallashtirish usullarining ma'nosi X, X, ..., X nuqtalar ketma-ketligini qurishdir.
f (X )>f (X )>… …>f (X ). Sifatda boshlang'ich nuqtasi X, ixtiyoriy nuqta tanlanishi mumkin, lekin uni minimal nuqtaga iloji boricha yaqinroq tanlashga intiladi. X nuqtadan X nuqtaga o'tish (iteratsiya), k =0,1,2,... ikki bosqichdan iborat:
– nuqtadan harakat yo'nalishini tanlash X ;
– bu yo'nalishdagi qadamni aniqlash.
Bunday ketma-ketliklarni qurish usullari ko'pincha tushish usullari deb ataladi, chunki funktsiyaning katta qiymatlaridan kichikroq qiymatlarga o'tish amalga oshiriladi.
Matematik jihatdan kelib chiqish usullari munosabat bilan tavsiflanadi
X =X +a k p, k =0,1,2,...,
bu erda p - tushish yo'nalishini belgilovchi birlik vektor;
a k - qadam uzunligi.
Turli xil tushish usullari bir-biridan p va a k ni tanlash usuli bilan farqlanadi. Amalda faqat birlashtiruvchi usullar qo'llaniladi. Ular sizga minimal nuqtani olish yoki cheklangan miqdordagi qadamlarda unga yaqinlashish imkonini beradi. Konvergent iterativ usullarning sifati yaqinlashish tezligi bilan baholanadi.
Nazariy jihatdan, tushish usullarida muammo cheksiz ko'p takrorlashda hal qilinadi. Amalda, iteratsion jarayonni to'xtatishning ma'lum mezonlari (shartlari) bajarilganda hisob-kitoblar to'xtatiladi. Misol uchun, bu kichik o'sish sharti bo'lishi mumkin
dalil |
X[ k] − X[ k − 1 ] |
||||||
f (X [ k ]) − f (X [ k − 1])< γ . Здесь k – номер итерации; ε , γ – задан-
muammoni hal qilishning aniqligining har xil qiymatlari.
Minimal nuqtani topish usullari, agar X dan X ga o'tishning ikkala parametri (harakat yo'nalishi va qadam o'lchami) X nuqtada mavjud bo'lgan ma'lumotlarga asoslanib, yagona tanlansa, deterministik deb ataladi. Agar o'tish jarayonida biron bir tasodifiy mexanizm qo'llanilsa, u holda qidiruv algoritmi tasodifiy minimal qidiruv deb ataladi.
Deterministik cheklanmagan minimallashtirish algoritmlari ishlatiladigan axborot turiga qarab sinflarga bo'linadi. Agar har bir iteratsiyada faqat minimallashtirilgan funksiyalarning qiymatlari ishlatilsa, u holda usul nol tartibli usul deb ataladi. Agar qo'shimcha ravishda minimallashtirilayotgan funktsiyaning birinchi hosilalarini hisoblash kerak bo'lsa, u holda birinchi tartibli usullar amalga oshiriladi,
agar ikkinchi hosilalarni qo'shimcha hisoblash zarur bo'lsa, ikkinchi tartibli usullardan foydalaning.
Shuni ta'kidlash kerakki, so'zsiz minimallashtirish masalalarini echishda birinchi va ikkinchi tartibli usullar, qoida tariqasida, nol tartibli usullarga qaraganda yuqori yaqinlashish tezligiga ega. Biroq, amalda ko'p sonli o'zgaruvchilar funksiyasining birinchi va ikkinchi hosilalarini hisoblash juda mashaqqatli. Ba'zi hollarda ularni analitik funktsiyalar shaklida olish mumkin emas. Turli xil hosilalar raqamli usullar Bunday usullardan foydalanishni cheklashi mumkin bo'lgan xatolar bilan aniqlanadi. Bundan tashqari, optimallik mezonini aniq emas, balki tenglamalar tizimi bilan belgilash mumkin. Bunday holda, hosilalarni analitik yoki raqamli tarzda topish juda qiyin va ba'zan imkonsiz bo'ladi. Shuning uchun, nol tartibli usullar bu erda batafsilroq muhokama qilinadi.
Bir o'lchovli qidiruv usullari. Bir o'lchovli qidiruv usullari ro'yxati - bitta argument funktsiyasining ekstremumini raqamli qidirish f(x ) – ancha keng va adabiyotda yaxshi yoritilgan. Shuning uchun, bu erda biz faqat bitta usulni ko'rib chiqish bilan cheklanamiz, mualliflarning tajribasiga ko'ra, eng samarali usullardan biri - "oltin qism" usuli.
Usulning g'oyasi noaniqlik oralig'ini - kerakli minimal nuqtani o'z ichiga olgan x argumentining qiymatlari oralig'ini - dan oshmaydigan uzunlikka ketma-ket kamaytirishdir.
natijaning ruxsat etilgan xatosi e. Dastlabki intervalni hisobga olish mumkin shartlar bilan beriladi muammo, argument qiymatlarining ruxsat etilgan diapazoni yoki agar ikkinchisi chap va (yoki) o'ng chegaralarga ega bo'lmasa, ruxsat etilgan chegara ichidagi ma'lum bir maydon, dastlabki tahlil talab qilinadigan minimal qiymat tegishli ekanligini ko'rsatadi. .
Har qanday oraliq ichida uning "oltin qismi" ni bajaradigan ikkita x =y 0 va x =z 0 nuqtalari mavjud - ikkita teng bo'lmagan qismga bo'linish, shuning uchun katta qismning butun oraliq uzunligiga nisbati nisbati bilan mos keladi. kichikroq qismidan kattasiga. Shubhasiz, bu nuqtalar intervalning markaziga nisbatan nosimmetrik tarzda joylashgan (26-rasm). "Oltin qism" nuqtalarining koordinatalarini tegishli nisbatlardan topish mumkin:
b−y0 |
y0 − a |
= δ , |
z0 − a |
b − z0 |
= δ, |
||||
b−a |
b−y |
b−a |
− a |
||||||
bu yerdan d = (1–d )/d ni olish va tenglamaga kelish oson: d 2 +d –1=0. Natijada, biz intervalning "oltin kesimini" aniqlaydigan nisbiy ulushlarni olamiz: d =0,618, 1-d =0,382. " Oltin nisbat"egadir muhim mulk: y 0 nuqtasi intervalning “oltin kesim” nuqtalaridan biri, z 0 nuqtasi intervalning “oltin kesimi” nuqtalaridan biridir. Bunda
Oddiy hisob-kitob kutmoqda: 0,382 / 0,618 = 0,618 va (0,618-0,382) / 0,618 = 0,382.
"Oltin qism" usuli asosida qurilgan minimalni topish algoritmi har bir iteratsiyada "oltin qism" ning chap yoki o'ng nuqtasini qisqartirilgan intervalning chegaralaridan biri sifatida tanlashni ta'minlaydi. Izlangan minimumni uning ichida saqlab qolish usuli:
1. k =0 o'rnating, dastlabki noaniqlik oralig'i, natijaning ruxsat etilgan xatosi e.
2. "Oltin qism" nuqtalarining koordinatalarini hisoblang:
y k =a k +0,382(b k –a k ), z k =a k +0,618(b k –a k ).
3. Topilgan nuqtalarda maqsad funksiyasining qiymatlarini hisoblang
f (y k) va f (z k).
4. Agar f (y k)≤f (z k) (26-rasm, a), a k + 1 =a k, b k + 1 =z k, z k + 1 =y k, y k + 1 =a k +z k –y k, k ni belgilang. =k +1. Aks holda (26-rasm, b) a k + 1 =y k, b k + 1 =b k, y k + 1 =z k, z k + 1 =y k +b k –z k, k =k +1.
5. Qidiruvni yakunlash shartining bajarilishini tekshiring
b k + 1 - a k + 1 ≤ e. Agar u bajarilsa, yechim sifatida x = (y k + 1 + z k + 1 ) 2 nuqta tanlanadi. Aks holda, 2-bosqichga o'ting.
"Oltin qism" usulining hisoblash samaradorligi har bir iteratsiyada maqsad funktsiyasi qiymatini faqat bitta hisoblashni talab qilishi bilan bog'liq.
To'g'ridan-to'g'ri qidirish usuli (Hooke-Jeves usuli). Biroz
ikkinchi boshlanish nuqtasi X. X vektorining komponentlarini muqobil ravishda o'zgartirib, bu nuqtaning qo'shnisi tekshiriladi, natijada minimallashtirilgan f (X) funktsiyaning kamayish yo'nalishini aniqlaydigan nuqta (yangi asos) topiladi. Tanlangan yo'nalish bo'yicha pasayish amalga oshiriladi, bu funktsiya qiymatining pasayishiga ishonch hosil qiladi. Qabul qilingan to'xtash shartini hisobga olgan holda tushish yo'nalishini topish mumkin bo'lgunga qadar protsedura tsiklik takrorlanadi.
To'g'ridan-to'g'ri qidirish usulining algoritmi eng umumiy shaklda quyidagicha shakllantirilishi mumkin:
1. X i, i= 1,2,…n koordinatalarining qiymatlari, boshlang'ich nuqtasi (k = 0), koordinatalarning boshlang'ich bosqichlari vektori bo'yicha o'rnatiladi.
∆ X = (∆ x 1, ∆ x 2,…, ∆ x n) tevarak-atrofni tekshirish jarayonida e komponentlarining ruxsat etilgan eng kichik qiymati ∆ X, tezlashuvchi omil l ≥ 1, tushish tezligini belgilaydi, masshtab. omil d >1.
2. X ni “eski asos” sifatida oling: X b = X. Hisoblash
f(X b) qiymati.
3. X b i, i= 1,2,…n, har bir koordinatani navbat bilan o‘zgartiring,
X b nuqtasini ∆ x i qiymatiga, ya'ni x i = x b i + ∆ x i ni qabul qilamiz, keyin
x i =x b i –∆ x i. Olingan sinov nuqtalarida f (X) qiymatlarini hisoblang va ularni f (X b) qiymati bilan solishtiring. Agar f(X)< < f
(X
б
), то соответствующая координата х
i
приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n
-й координаты f
(X
) 4. Oxirgisi orqali "eski" dan "yangi" asosga yo'nalishda tushish, ya'ni yangi nuqtaning koordinatalarini hisoblash. X: x i = x i + l (x i – x bi), i= 1,2,...n. f(X) ning qiymatini hisoblang. Agar f(X) shart bajarilsa "Yangi" asos "eski" sifatida qabul qilinadi (X b = X, f (X b) = f (X)) va 5-bosqichga o'ting. Aks holda, x i = x i, i = 1,2, ni qabul qiling. ..n . 5.
3-bosqichda bo'lgani kabi, nuqtaning har bir koordinatasini navbat bilan o'zgartiring X, f (X) funktsiyasining mos qiymatlarini 4-bosqichda olingan f (X) qiymati bilan solishtirish. Oxirgi koordinatani o'zgartirgandan so'ng, mos keladigan qiymatni solishtiring. 4-bandda olingan f (X b) qiymatiga ega f (X) funktsiyalari. Agar f (X) 6. Agar hamma uchun i ∆ x i bo'lsa<ε
, вычисления прекращаются. В противном случае уменьшают значения ∆
х
i
в d
раз и переходят к п. 3. Algoritmning ishlashi rasmda ko'rsatilgan. 27. Ko'rsatilgan chiziqlar minimallashtirilgan f (x 1 ,x 2 ) funksiya darajasi, ya'ni f (x 1 ,x 2 )=f 1 =const, f (x 1 ,x 2 )=f 2 =const va hokazo shartlardan olingan chiziqlar. Keyinchalik. Bu yerda f 1 >f 2 >f 3 . Qattiq chiziqlar - paragraflarning bitta bajarilishi natijalari. 3...5 (funksiya va pasayish yo'nalishini izlash), nuqta chiziq keyingi tushishdir. To'g'ridan-to'g'ri qidirish usulining afzalligi - uni kompyuterda dasturlashning qulayligi. Bu maqsad funktsiyasi haqida aniq bilimni talab qilmaydi, shuningdek, alohida o'zgaruvchilar bo'yicha cheklovlarni, shuningdek qidiruv maydonidagi murakkab cheklovlarni osongina hisobga oladi. To'g'ridan-to'g'ri qidirish usulining kamchiligi shundaki, maqsad funktsiyasi darajasining yuqori cho'zilgan, egri yoki o'tkir burchakli chiziqlarida tahlil qilinadigan yo'nalishlarning cheklanganligi sababli minimal nuqtaga borishni ta'minlay olmaydi. Deformatsiyalanadigan ko'pburchak usuli (Nelder-Mead usuli) funktsiyani minimallashtirish uchun n o'lchamli f(X) o'zgaruvchilari bo'shliq, o'z ichiga olgan ko'pburchak qurilgan n +1 cho'qqi. Shubhasiz, har bir tepalik ma'lum bir vektorga mos keladi Xi . Maqsad funksiyasining qiymatlarini hisoblang f(Xi ), i=1,2,…, n +1, ko'pburchakning har bir cho'qqisida ushbu qiymatlarning maksimalini va mos keladigan cho'qqini aniqlang Xh . Ushbu cho'qqi va qolgan cho'qqilarning og'irlik markazi orqali nuqta joylashgan proyeksiya chizig'ini torting. Xq cho'qqisiga qaraganda kichikroq maqsad funktsiyasi qiymati bilan Xh (28-rasm, a ). Keyin tepalikni olib tashlang Xh . Qolgan cho'qqilar va nuqtalardan Xq tasvirlangan protsedura takrorlanadigan yangi ko'pburchak qurish. Bunday operatsiyalarni bajarish jarayonida poliedr o'zining o'lchamlarini o'zgartiradi, bu usulning nomini belgilaydi. Quyidagi yozuvni kiritamiz: X – ko‘pburchakning i-cho‘qqisining k-qidiruv bosqichidagi koordinatalar vektori, i= 1,2,…n +1, k= 1,2,…; h – maqsad qiymati bo'lgan cho'qqi raqami shinalar, X dan tashqari. Og'irlik markazining koordinatalari hisoblanadi xj [n + 2, k] = n+1 formula bo'yicha ∑ xj [ i, k] − xj [ h, k] J= 1,2,…n. j= 1 Deformatsiyalanuvchi ko‘pburchak usulining taxminiy algoritmi quyidagicha: 1.
Ko'zgu koeffitsientlari bilan belgilanadi a, taranglik g >1, siqilish b<1
, допустимой погрешностью определения координат minimal ball e. Dastlabki ko‘pburchak X, i= 1,2,…n +1, k= 1 cho‘qqilarining koordinatalarini tanlang. 2.
Maqsad funksiyasining barcha burchaklardagi qiymatlarini hisoblang f (X), i= 1,2,…n +1 va X, X nuqtalarni toping (28-rasmda b, mos ravishda X 2 va X 1 nuqtalari), shuningdek X. 3.
Nuqta proyeksiyasini bajaring X markazi orqali qalay: X =X +a (X –X). 4. Agar f (X)≤ X bo'lsa, cho'zish operatsiyasini bajaring tion: X =X +g (X –X ). Aks holda, 6-bosqichga o'ting. 5.
Yangi ko'pburchak qurilmoqda: agar f(X) X ni X bilan almashtirish orqali, aks holda X ni X bilan almashtirish orqali. k =k +1 bilan 2-bosqichdan boshlab hisob-kitoblarni davom ettiring. 6. Barcha i uchun X >f (X)>X h ga teng bo‘lmasa, siqish amalini bajaring: X =X +b (X – X). X ni X bilan almashtirib, yangi ko‘pburchak tuzing va 2-bosqichdan boshlab k =k +1 bilan hisoblashni davom ettiring. 7. Agar f (X)>X bo'lsa, X cho'qqisini saqlab, barcha qirralarning uzunliklarini ikki baravar qisqartirgan holda, hozirgiga o'xshash yangi ko'pburchak quring: X =X +0,5(X –X) va hisoblarni davom ettiring. 2-bosqichdan k =k +1 da. Paragraflarda 6, 7 2-bosqichga o'tishdan oldin, minimal qidirishni yakunlash shartining bajarilishini tekshirish kerak, masalan, shart bo'yicha Men max n ∑ + 1 (x j [ i ,k ] − x j [ n + 2,k ] ) 2 ni ko‘raman< ε
2
. i j = 1 BILAN Cho'zish va siqish operatsiyasidan foydalanib, deformatsiyalanadigan ko'pburchakning o'lchamlari va shakli maqsadli funktsiyaning topografiyasiga moslashtiriladi. Natijada, ko'pburchak uzun qiya yuzalar bo'ylab cho'ziladi, egri chuqurliklarda yo'nalishni o'zgartiradi va minimumga yaqin joyda qisqaradi, bu ko'rib chiqilgan usulning samaradorligini belgilaydi. a =1, 2≤ g ≤3, 0,4≤b ≤0,6. Aylanadigan koordinata usuli (Rozenbrok usuli). Uning mohiyati maqsad funktsiyasining eng tez kamayish yo'nalishining o'zgarishiga muvofiq koordinata tizimining ketma-ket aylanishidan iborat (29-rasm). Boshlanish nuqtasidan X nuqtaga tushish X koordinata o'qlariga parallel yo'nalishlarda. Keyingi iteratsiyada o'qlardan biri yo'nalishda harakatlanishi kerak x’1 = X– X, qolganlari - perpendikulyar yo'nalishlarda x’1 . Ushbu o'qlar bo'ylab tushish nuqtaga olib keladi X , bu yangi vektorni qurish imkonini beradi x’’1 = X– X va uning asosida qidiruv yo'nalishlarining yangi tizimi minimal ball X. IN Boshqa nol tartibli usullardan farqli o'laroq, Rozenbrok usuli faqat barcha yo'nalishlarda qat'iy siljishga emas, balki har bir yo'nalishda optimal nuqtani topishga qaratilgan. Qidiruv jarayonidagi qadam o'lchami tekis sirt topografiyasiga qarab doimiy ravishda o'zgarib turadi. Koordinatalarni aylantirish va qadamlarni boshqarish kombinatsiyasi Rosenbrock usulini murakkab optimallashtirish muammolarini hal qilishda samarali qiladi. IN Xususan, bu usul, boshqalardan farqli o'laroq, "jarlik" deb ataladigan funktsiyalarni (yuqori darajada cho'zilgan tekis yuzalar bilan) minimallashtirishda samarali, chunki natijada qidiruv yo'nalishi "jar" o'qi bo'ylab joylashgan. Parallel tangens usuli (Pauell usuli). Uning mohiyati quyidagilarga muvofiq maqsad funktsiyasining minimalini bir o'lchovli qidirishni ketma-ket amalga oshirishdir. har qanday yo'nalishda n+1 ma'lum bir o'lchovli usullardan. Birinchi iteratsiyada, birinchisi kabi n kabi koordinata yo'nalishlari tanlanadi(n+1)-chi yo'nalishlari, ulardan birinchisi qo'llaniladi (30-rasm). Har bir keyingi iteratsiyada qidiruv avvalgi iteratsiyaning ikkinchi yo'nalishidan boshlanadi, mos ravishda yo'nalishlar soni bittaga kamayadi;(n+1)-chi keyingi iteratsiya yo'nalishi vektor tomonidan beriladi X– X[n+1] - oldingi iteratsiyaning birinchi bosqichida topilgan minimal nuqtadan, oxirgi bosqichda topilgan minimal nuqta orqali. 5.
Ko'p o'lchovli optimallashtirish
Chiziqli dasturlash
Optimallashtirish
tegishli sharoitlarda eng yaxshi natija olishga qaratilgan maqsadli faoliyatdir. Optimallashtirilayotgan sifatni miqdoriy baholash deyiladi optimallik mezoni
yoki maqsadli funktsiya
.Uni quyidagi shaklda yozish mumkin: (5.1)
bu erda x 1, x 2, …, x n- optimallashtirish ob'ektining ba'zi parametrlari. Optimallashtirish muammolarining ikki turi mavjud - shartsiz va shartli. Shartsiz vazifa
optimallashtirish haqiqiy funktsiyaning (5.1) maksimal yoki minimalini topishdan iboratnreal o'zgaruvchilar va tegishli argument qiymatlarini aniqlash. Shartli optimallashtirish muammolari
, yoki cheklovlar bilan bog'liq muammolar - bu argumentlarning qiymatlariga tenglik yoki tengsizlik ko'rinishidagi cheklovlar qo'yiladigan muammolar. Optimallik mezoni mustaqil o'zgaruvchilarning chiziqli funktsiyasi bo'lgan (ya'ni, ushbu o'zgaruvchilarni birinchi darajagacha o'z ichiga oladi) ular bo'yicha chiziqli cheklovlar bilan optimallashtirish masalalarini hal qilish. chiziqli dasturlash.
Bu erda "dasturlash" so'zi tadqiqotning yakuniy maqsadini - optimal rejani yoki optimal dasturni aniqlashni aks ettiradi, unga ko'ra o'rganilayotgan jarayon uchun ko'plab mumkin bo'lgan variantlardan qaysidir mezon asosida eng yaxshi, optimal variant tanlanadi. Misol
shunday vazifa xom ashyoni optimal taqsimlash muammosi
ishlab chiqarishning maksimal qiymatida turli tarmoqlar o'rtasida. Ikki xil xom ashyodan ikki xil mahsulot tayyorlansin. Belgilaymiz: x 1 , x 2 – mos ravishda birinchi va ikkinchi turdagi mahsulotlar birliklari soni; c 1 , c 2 – mos ravishda birinchi va ikkinchi turdagi mahsulotlar birligi narxi. Keyin barcha mahsulotlarning umumiy qiymati bo'ladi:
(5.2)
Ishlab chiqarish natijasida ishlab chiqarishning umumiy tannarxini maksimal darajada oshirish maqsadga muvofiqdir.R (x 1 , x 2 ) bu masaladagi maqsad funksiyasi. b 1, b 2 – mavjud bo‘lgan birinchi va ikkinchi turdagi xom ashyo miqdori;a ij- birliklar soni i
-birlik ishlab chiqarish uchun zarur bo'lgan xom ashyo turij- mahsulot turi. Berilgan resurs iste'moli uning umumiy miqdoridan oshmasligini hisobga olib, biz resurslar uchun cheklovchi shartlarni yozamiz: (5.3)
O'zgaruvchilar haqida x 1 , x 2 ular manfiy emas va cheksiz deb ham aytishimiz mumkin: (5.4)
Tengsizliklar tizimining (5.3) va (5.4) ko'plab yechimlari orasidan shunday yechim topish talab etiladi ( x 1 , x 2 ), bu funksiya uchunReng katta qiymatiga etadi. Transport muammolari (tovarlar, xom ashyo yoki mahsulotlarni turli omborlardan bir nechta manzillarga minimal transport xarajatlari bilan etkazib berishni optimal tashkil etish muammolari) va boshqa bir qator shunga o'xshash shaklda tuzilgan. Chiziqli dasturlash masalalarini echishning grafik usuli.
Uni topish talab qilinsin x 1 va x 2 , qoniqarli Tengsizliklar tizimi: (5.5)
va shartlar salbiy bo'lmaganlik:
(5.6)
Uchun kimning vazifasi (5.
7
)
maksimal darajaga etadi. Yechim.
To'g'ri to'rtburchaklar koordinatalar sistemasida quramiz x 1 x 2 muammoning mumkin bo'lgan echimlari maydoni (11-rasm). Buning uchun (5.5) tengsizliklarning har birini tenglik bilan almashtirib, tuzamiz muvofiq uning chegara chizig'i: (i = 1, 2, … ,
r)
Guruch. o'n bir Bu to'g'ri chiziq butun tekislikni ikkita yarim tekislikka ajratadi. Koordinatalar uchun x 1 , x 2 har qanday nuqta A bir yarim tekislikda quyidagi tengsizlik amal qiladi: va har qanday nuqtaning koordinatalari uchun IN boshqa yarim tekislik - qarama-qarshi tengsizlik: Chegara chizig'idagi istalgan nuqtaning koordinatalari tenglamani qanoatlantiradi: Berilgan tengsizlikka mos keladigan yarim tekislik chegara chizig'ining qaysi tomonida joylashganligini aniqlash uchun bitta nuqtani "sinov" qilish kifoya (eng oson yo'l - nuqta HAQIDA(0;0)). Agar uning koordinatalarini tengsizlikning chap tomoniga qo‘yganda, qanoatlansa, yarim tekislik tekshirilayotgan nuqta tomon buriladi, agar tengsizlik bajarilmasa, mos keladigan yarim tekislik teskari tomonga buriladi. . Yarim tekislikning yo'nalishi chizmada lyuk bilan ko'rsatilgan. Tengsizliklar: ordinata o'qining o'ng tomonida va abscissa o'qi ustida joylashgan yarim tekisliklarga mos keladi. Rasmda biz barcha tengsizliklarga mos keladigan chegara to'g'ri chiziqlar va yarim tekisliklarni quramiz. Ushbu yarim tekisliklarning umumiy qismi (kesishmasi) ushbu muammoni hal qilishning mumkin bo'lgan mintaqasini ifodalaydi. O'zgaruvchilar bo'yicha cheklovlar (tengsizliklar) tizimining o'ziga xos turiga qarab, mumkin bo'lgan echimlar mintaqasini qurishda quyidagi to'rtta holatdan biri sodir bo'lishi mumkin: Guruch. 12. Mumkin yechimlar mintaqasi bo'sh, bu tengsizliklar tizimining nomuvofiqligiga mos keladi; yechim yo'q Guruch. 13. Mumkin yechimlar mintaqasi tizimning yagona yechimiga mos keladigan bitta A nuqta bilan ifodalanadi. Guruch. 14. Mumkin echimlar maydoni cheklangan va qavariq ko'pburchak sifatida tasvirlangan. Mumkin bo'lgan echimlarning cheksiz soni mavjud Guruch. 15. Mumkin bo'lgan yechimlar mintaqasi cheksiz, qavariq ko'pburchakli mintaqa shaklida. Mumkin bo'lgan echimlarning cheksiz soni mavjud Maqsad funksiyasining grafik tasviri belgilangan qiymatdaRto'g'ri chiziqni belgilaydi va o'zgartirgandaR- parametrli parallel chiziqlar oilasiR. Chiziqlardan birida yotgan barcha nuqtalar uchun funksiya R ma'lum bir qiymatni oladi, shuning uchun ko'rsatilgan to'g'ri chiziqlar chaqiriladi darajali chiziqlar
R funktsiyasi uchun. Gradient vektori:
perpendikulyardarajali chiziqlarga, o'sish yo'nalishini ko'rsatadiR.
Tengsizliklar sistemasining optimal yechimini topish masalasi (5.5), buning uchun maqsad funksiyasi.R(5.7) maksimal darajaga etadi, ruxsat etilgan eritmalar hududida parametrning eng katta qiymatiga mos keladigan sath chizig'i o'tadigan nuqtani aniqlashga geometrik ravishda qisqartiradi.R Guruch. 16 Agar amalga oshirilishi mumkin bo'lgan yechimlar mintaqasi qavariq ko'pburchak bo'lsa, u holda funktsiyaning ekstremumiR
Ushbu ko'pburchakning hech bo'lmaganda bir cho'qqisiga erishiladi. Agar haddan tashqari qiymat bo'lsaRikki uchida erishiladi, keyin bir xil ekstremal qiymat bu ikki cho'qqilarni bog'laydigan segmentning istalgan nuqtasida erishiladi. Bunday holda, vazifa borligi aytiladi alternativ optimal
.
Cheklanmagan mintaqada funksiyaning ekstremumRyo mavjud emas yoki mintaqaning cho'qqilaridan birida erishiladi yoki muqobil optimalga ega. Misol.
Aytaylik, biz qiymatlarni topishimiz kerak x 1 va x 2 , tengsizliklar tizimini qanoatlantiruvchi: va shartlar salbiy bo'lmaganlik:
Uchun kimning vazifasi: maksimal darajaga etadi. Yechim.
Keling, har bir tengsizlikni tenglik bilan almashtiramiz va chegara chiziqlarini tuzamiz: Guruch. 17 Bu tengsizliklarga mos keladigan yarim tekisliklarni (0;0) nuqtani “test” qilib aniqlaylik. Hisob bilan salbiy bo'lmaganlik x 1 va x 2 bu masalaning mumkin bo'lgan yechimlari mintaqasini qavariq ko'pburchak shaklida olamiz OAVDE.
Mumkin echimlar hududida biz gradient vektorini qurish orqali optimal echimni topamiz ko'rsatisho'sish yo'nalishiR.
Optimal yechim nuqtaga mos keladi IN, koordinatalarini grafik yoki AB va VD chegaraviy toʻgʻri chiziqlarga mos keladigan ikkita tenglamalar tizimini yechish yoʻli bilan aniqlash mumkin: Javob:
x 1 = 2; x 2 = 6; Rmax = 22.
Vazifalar.
Ekstremum nuqtaning o'rnini va maqsad funktsiyasining ekstremal qiymatini toping berilgan cheklovlar ostida. 9-jadval Ekstremum M bolta Maks ;
;
;
;
Optimallashtirish - bu ma'lum bir funktsiyaning ekstremumini (global maksimal yoki minimal) topish yoki mumkin bo'lganlar to'plamidan eng yaxshi (optimal) variantni tanlash jarayoni. Topishning eng ishonchli usuli eng yaxshi variant barcha mumkin bo'lgan variantlarni (alternativlarni) qiyosiy baholashdir. Agar muqobillar soni ko'p bo'lsa, eng yaxshisini topish uchun odatda matematik dasturlash usullari qo'llaniladi. Agar muammoning qat'iy formulasi mavjud bo'lsa, ushbu usullarni qo'llash mumkin: o'zgaruvchilar to'plami ko'rsatilgan, ularning mumkin bo'lgan o'zgarish maydoni belgilanadi (cheklovlar ko'rsatilgan) va maqsad funktsiyasining turi (ekstremumi funktsiya). topish kerak) bu o'zgaruvchilardan aniqlanadi. Ikkinchisi maqsadga erishish darajasini baholashning miqdoriy ko'rsatkichi (mezoni) hisoblanadi. Cheklanmagan optimallashtirish muammosi hech qanday cheklovlar bo'lmaganda funktsiyaning minimal yoki maksimalini topishdir. Ko'pchilik bo'lishiga qaramay amaliy muammolar optimallashtirish cheklovlarni o'z ichiga oladi, cheklanmagan optimallashtirish usullarini o'rganish bir necha nuqtai nazardan muhimdir. Cheklangan muammoni hal qilishning ko'pgina algoritmlari uni cheklanmagan optimallashtirish muammolari ketma-ketligiga qisqartirishni o'z ichiga oladi. Boshqa usullar klassi mos yo'nalishni topishga va keyin bu yo'nalish bo'ylab minimallashtirishga asoslangan. Cheklanmagan optimallashtirish usullarini asoslash tabiiy ravishda cheklovlar bilan muammolarni hal qilish protseduralarini asoslash uchun kengaytirilishi mumkin. Cheklangan optimallashtirish muammosi n o‘lchamli vektor argumentlarining f(x) skalar funksiyasining minimal yoki maksimal qiymatini topishdan iborat. Masala yechimi maqsad funksiyaning chiziqli yoki kvadratik yaqinlashuviga asoslanadi, har bir iteratsiyada x1, ..., xn o‘sishlar aniqlanadi. Nochiziqli masalalarni echishning taxminiy usullari ham mavjud. Bular qismli chiziqli yaqinlashish usuliga asoslangan usullardir. Yechimlarni topishning to'g'riligi chiziqli muammoning echimini topadigan intervallar soniga bog'liq bo'lib, u chiziqli bo'lmagan masalaga iloji boricha yaqinroqdir. Bu usul simpleks usuli yordamida hisob-kitoblarni amalga oshirish imkonini beradi. Odatda, chiziqli modellarda maqsad funktsiyasi koeffitsientlari doimiy bo'lib, o'zgaruvchilar qiymatlariga bog'liq emas. Biroq, xarajatlar hajmiga nochiziqli bog'liq bo'lgan bir qator muammolar mavjud. Yechim algoritmi: Vazifa: quvvatni optimallashtirish. Qumni saqlash uchun 2750 litr hajmli idishni ishlab chiqarish uchun minimal xarajatlarga erishing. Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5 min; bu erda: X1 - kerakli metall miqdori, kg; C1 - metallning narxi, rub / kg; X2 - talab qilinadigan elektrodlar massasi, kg; C2 - elektrodlarning narxi, rub / kg; X3 - iste'mol qilingan elektr energiyasi miqdori, kVt soat; C3 - elektr energiyasining narxi, rub / kVt soat; X4 - payvandchining ish vaqti, soat; C4 - payvandchi tarif stavkasi, rub / soat; X5 - liftning ish vaqti, h; C5 - ko'tarish to'lovi, rub / soat. 1. Idishning optimal sirt maydonini toping: F = 2ab+2bh+2ah min (1) bu erda V=2750 litr. x1=16,331; x2=10,99 Funktsiyaning minimal qiymati Box usuli yordamida optimallashtirish jarayonida olingan - 1196,065 dm2 GOST 19903 - 74 ga muvofiq biz quyidagilarni qabul qilamiz: h=16,50 dm, b=10,00 dm. Keling, (1) dan ani ifodalaymiz va quyidagilarni olamiz: Keling, metall qatlamning optimal qalinligini hisoblaylik Keling, oddiy karbonli po'lat St2sp ni tanlaylik Ushbu po'lat uchun 320 MPa, ; Qum massasi. Eng katta maydonga ega bo'lgan idishning devoriga yuklang: 100 sm kenglikdagi varaqning 1 chiziqli santimetri uchun yukni hisoblaylik: Devor qalinligini shartga qarab aniqlaymiz: bu erda: l - varaqning uzunligi (yaxshisi eng kattasi qo'shimcha zaxira kuch); q - 1 chiziqli santimetr uchun yuk, kg / sm; Metall qatlam qalinligi, m Maksimal ruxsat etilgan metall kuchlanish, N / mm2. Devor qalinligini (2) dan ifodalaymiz: 320 MPa = 3263 kg/sm2 ekanligini hisobga olsak, Metall og'irligi bu erda: F - idishning sirt maydoni, m2; Metall devor qalinligi, m; Metall zichligi, kg/m3. St2sp po'latining narxi taxminan 38 rubl / kg ni tashkil qiladi. 2. Payvand choki uzunligi: Biz elektrodlardan foydalanamiz zanglamaydigan po'latdan"UONI-13/45" Narxi 88,66 rub/kg; bu erda: Shish - payvand chokining ko'ndalang kesimi maydoni, m2; l - payvand choki uzunligi, m; Cho'kma metallning zichligi, kg/m3. 3. Payvandlash vaqti: bu erda l - payvand choki uzunligi, m; v - payvandlash tezligi, m / soat. Umumiy quvvat sarfi: Rsum = 5 17 = 85 kVt soat; Elektr narxi - 5,7 rubl / kVt. 4. Qo'lda boshq payvandlash uchun ish joyiga xizmat ko'rsatish uchun yordamchi, tayyorgarlik va yakuniy vaqt va vaqt xarajatlari o'rtacha 40 - 60%. Keling, o'rtacha 50% qiymatidan foydalanamiz. Umumiy vaqt: VI toifali payvandchi uchun to'lov 270 rubl / soat. Bundan tashqari, cheklangan, yomon gazlangan xonada ishlash uchun 17% tarif koeffitsienti: Yordamchining to'lovi payvandchi to'lovining 60% ni tashkil qiladi: 8055 0,6 = 4833 rub. Jami: 8055+4833 = 12888 rubl. 5. Metall varaqlarni va tayyor idishning o'zini payvandlash, yuklash va tushirish vaqtida metall plitalarni ushlab turish uchun kran kerak. Butun strukturani "ushlash" uchun payvandchi tikuvlarning taxminan 30% ni qo'llashi kerak. Kran uchun to'lov 1000 rubl / soat. Konteynerning umumiy qiymati. SAPRda nol tartibli optimallashtirish usullari orasida Rosenbrock, konfiguratsiyalar, deformatsiyalanadigan ko'pburchak va tasodifiy qidiruv usullari qo'llaniladi. Losmalar qo'llaniladigan usullarga eng tik tushish, konjugat gradient va o'zgaruvchan metrik usullar kiradi. Rozenbrok usuli koordinata tushishining takomillashtirilgan versiyasidir. Koordinatali tushish usuli barcha koordinata o'qlari bo'ylab qidiruv yo'nalishlarini navbatma-navbat tanlash bilan tavsiflanadi, qadam bir o'lchovli optimallashtirish asosida hisoblanadi, qidiruvni tugatish mezoni , bu erda mahalliy ekstremumni aniqlashning belgilangan aniqligi, o'lchami. boshqariladigan parametrlar maydoni. Boshqariladigan parametrlarning ikki o'lchovli fazosining misoli uchun koordinatali tushish traektoriyasi rasmda ko'rsatilgan. 1, bu erda qidiruv traektoriyasidagi nuqtalar va boshqariladigan parametrlar. Maqsad funksiyasi uning teng darajali satrlari bilan ifodalanadi va har bir satr yonida tegishli qiymat yoziladi. Shubhasiz, minimal nuqta bor. Guruch. 1. Koordinatalarning tushish traektoriyasi Koordinatali tushish usulidan foydalanganda qidiruvning ekstremal nuqtadan uzoqda joylashgan jar tubida qolib ketish ehtimoli yuqori. Shaklda. 2 jarlikning pastki qismida joylashgan nuqtaga urilgandan so'ng, keyingi qadamlar faqat yo'nalishlarda mumkin yoki , lekin ular maqsad funktsiyasining yomonlashishiga olib kelishini ko'rsatadi. Shunday qilib, qidiruv nuqtada to'xtaydi. Eslatma 1 Dara - boshqariladigan parametrlar makonining bir qismi bo'lib, unda maqsad funksiya hosilalarida ba'zi yo'nalishlarda zaif o'zgarishlar va boshqa yo'nalishlarda belgining o'zgarishi bilan sezilarli o'zgarishlar kuzatiladi. Hosilning belgisi jar tubiga tegishli nuqtalarda o'zgaradi. Guruch. 3. Koordinata o'qlarining qulay yo'nalishi bilan koordinata tushishi traektoriyasi Rozenbrok usuli koordinata o'qlarini shunday aylantirishdan iboratki, ulardan biri jar tubiga kvazparallel bo'lib chiqadi. Ushbu aylanish koordinata tushishining bir qator bosqichlaridan so'ng olingan ma'lumotlar asosida amalga oshiriladi. Yangi o'qlarning pozitsiyasini oldingi o'qlarni chiziqli o'zgartirish orqali olish mumkin: eksa vektor bilan yo'nalish bo'yicha mos keladi; qolgan o'qlar bir-biriga va ortogonallik shartidan tanlanadi. Koordinata tushishining yana bir muvaffaqiyatli modifikatsiyasi konfiguratsiya usuli(Huk-Jivs). Ushbu usulga muvofiq, birinchi navbatda, koordinata tushishining odatiy bosqichlari amalga oshiriladi, so'ngra vektor yo'nalishi bo'yicha qo'shimcha qadam qo'yiladi, rasmda ko'rsatilgan. 4, bu erda vektor yo'nalishi bo'yicha qo'shimcha qadam bajariladi, bu nuqtaga olib keladi. Guruch. 4. Konfiguratsiya usulining tasviri Ekstremumni qidiring deformatsiyalanadigan ko'pburchak usuli(Nelder-Mead) har bir qidiruv bosqichida uchlari bo'lgan ko'pburchakni qurishga asoslangan, bu erda boshqariladigan parametrlar maydonining o'lchami. Qidiruv boshida bu cho'qqilar tasodifiy tanlanadi, keyingi bosqichlarda tanlov usul qoidalariga bo'ysunadi. Ushbu qoidalar rasmda tasvirlangan. 5 ikki o'lchovli optimallashtirish muammosi misolidan foydalanib. Asl uchburchakning uchlari tanlangan: , , . Yangi cho'qqi eng yomon cho'qqidan (cho'qqidan) olingan nurda joylashgan. eng yuqori qiymat maqsad funktsiyasi) ko'pburchakning og'irlik markazi orqali va teng masofada tanlash tavsiya etiladi. Yangi cho'qqi eng yomon cho'qqi o'rnini bosadi. Agar u ko'pburchakning uchlari orasida maqsad funktsiyasining eng yaxshi qiymatiga ega ekanligi aniqlansa, u holda masofa oshiriladi. Rasmda aynan shu holat yuzaga keladi va o'sish nuqta beradi . Cho'qqilari bo'lgan yangi ko'pburchakda, eng yomoni cho'qqi, xuddi shunday cho'qqi, keyin cho'qqi va hokazo. Agar yangi cho'qqi yomonroq bo'lib chiqsa, u holda ko'pburchakda eng yaxshi cho'qqi saqlanishi kerak va barcha qirralarning uzunligi, masalan, yarmiga qisqartirilishi kerak (poliedrni eng yaxshi cho'qqigacha qisqartirish). Ko'pburchakning o'lchamini ma'lum chegaraga kamaytirish sharti bajarilganda qidiruv to'xtaydi. optimal qadam bir o'lchovli optimallashtirish yordamida tanlanadi. Eng tik tushish usulidan foydalanganda, boshqa ko'plab usullar singari, chuqurlikdagi vaziyatlarda qidiruv samaradorligi sezilarli darajada kamayadi. Qidiruv traektoriyasi jarlikning tubi bo'ylab ekstremal tomon sekin harakatlanadigan zigzag shaklini oladi. Gradient usullarining samaradorligini oshirish uchun bir nechta texnikalar qo'llaniladi. Amaldagi texnikalardan biri konjugat gradient usuli(Fletcher-Rives usuli deb ham ataladi) vektorlarning konjugatsiya kontseptsiyasiga asoslanadi. Vektorlar va agar -konjugat deyiladi, bu erda vektorlarning o'lchami bilan bir xil tartibdagi musbat aniq kvadrat matritsa va (konjugatsiyaning alohida holati vektorlarning ortogonalligi, qachon tartibning o'ziga xos matritsasi bo'lsa), qator bo'ladi. vektor ustun vektoridir. Kvadrat maqsad funksiyali masalalarda Gess matritsasi qayerda bo'lsa, uchun konjugat yo'nalishlarining o'ziga xos xususiyati quyidagicha: konjugat yo'nalishlari bo'yicha ketma-ket bir o'lchovli minimallashtirish ekstremal nuqtani qadamlardan ko'p bo'lmagan holda topishga imkon beradi. Eslatma 2 Hessian matritsasi - bu boshqariladigan parametrlarga nisbatan maqsad funktsiyasining ikkinchi qisman hosilalari matritsasi. -conjugate qidiruvidan foydalanishning sababi, funktsiyalar uchun () umumiy ko'rinish Kvadrat yaqinlashuv qo'llanilishi mumkin, bu amalda qidiruvni bir necha bosqichda bajarishga olib keladi. Ekstremumni qidirish formulaga muvofiq amalga oshiriladi Qadam bir o'lchovli optimallashtirish sharti asosida hisoblanganligi sababli, birinchi navbatda, quyidagi munosabat to'g'ri bo'ladi: Qidiruv algoritmi hisob-kitoblarni bajarish sharti bajarilgunga qadar (3) formulani qo'llashgacha qisqartiriladi. Koeffitsientni aniqlash uchun (2)-(7) tenglamalar tizimini (4) ga (3) va (2) dan qiymatlarni qo'yish orqali eching: Agar jarayon bir-biriga yaqinlashsa, u holda yechimga kam sonli iteratsiyalarda erishiladi, uning oxiri shartning bajarilishi hisoblanadi. Shunung uchun Ko'rsatish mumkinki, , - qachon ga moyil bo'ladi, bu erda boshqariladigan parametrlar maydonining o'lchami. Qadamlardan so'ng, dan qayta boshlashingiz kerak.
Cheklovlar
; 
;
; ;
;
;
;
;
;
;
;
;
;
;
;
;
koeffitsient qayerda. Bundan tashqari, konjugatsiya holati hisobga olinadi
yoki
qayerda
va (6) va (7) ni hisobga olgan holda
(10) ifoda chiziqli algebraik tenglamalar sistemasidir. Uning ildizi yechimning yana bir yaqinlashuvidir
Qayerda
