Cheklanmagan optimallashtirishning klassik usullari. Shartsiz va shartli optimallashtirish usullari Operatsion tadqiqot usullarining mohiyati

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 aks ettiradi - ko'pchilik orasidan optimal reja yoki optimal dasturni aniqlash. mumkin bo'lgan variantlar o'rganilayotgan jarayonning eng yaxshi, optimal varianti qaysidir mezondan kelib chiqqan holda 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 deb ataladigan muammolar (tovarlar, xom ashyo yoki mahsulotlarni turli omborlardan bir nechta yo'nalishlarga minimal transport xarajatlari bilan etkazib berishni optimal tashkil etish vazifalari) 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 echimlar 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

Variant raqami.

Ekstremum
Cheklovlar

M bolta

; ;

; ;

Maks

; ; ;

;

; ;

; ;

; ;

; ; ;

;

; ;

Vazifa 1. Toping

1-masala tenglamalar tizimini yechish uchun keladi:

va ikkinchi differentsialning qiymatini o'rganing:

(8.3) tenglamalarning yechim nuqtalarida.

Agar (8.4) kvadrat shakl bir nuqtada manfiy aniqlangan bo'lsa, u holda u maksimal qiymatiga, musbat aniqlangan bo'lsa, minimal qiymatiga etadi.

Misol:

Tenglamalar tizimi yechimlarga ega:

Nuqta (- 1/3,0) maksimal nuqta, nuqta (1/3,2) esa minimal nuqtadir.

Vazifa 2. Toping

shartlarda:

2-masala Lagrange multiplikator usuli bilan yechiladi. Buning uchun tizimga yechim toping (t + p) tenglamalar:

Misol. Aylana ichiga chizilgan maydoni maksimal bo'lgan to'rtburchakning tomonlarini toping:. To'rtburchakning A maydonini quyidagicha yozish mumkin: A = 4 soat, Keyin

Vazifa 3. Toping:

shartlarda:

Bu vazifa funksiyalar bilan belgilangan vazifalarning keng doirasini qamrab oladi f Va .

Agar ular chiziqli bo'lsa, muammo chiziqli dasturlash masalasidir.

Vazifa3 A.

sharoitlarda

Simpleks usuli yordamida hal qilinadi, bu chiziqli algebra apparati yordamida (8.13) bilan aniqlangan ko'pburchakning uchlarini maqsadli qidirishni amalga oshiradi.

Simpleks usuli (ikki bosqichdan iborat):

1-bosqich. Etakchi yechim x (0) ni topish.

Etakchi eritma ko'p yuzli nuqtalardan biri (8.13).

2-bosqich. Optimal yechim topish.

Optimal yechim ko‘pburchakning (8.13) uchlarini ketma-ket sanash yo‘li bilan topiladi, bunda z maqsad funksiyasining qiymati har bir qadamda kamaymaydi, ya’ni:

Chiziqli dasturlash muammosining alohida holati transport muammosi deb ataladi.

Transport muammosi. Tovarlar tegishli miqdorda saqlanadigan punktlarda omborlar bo'lsin. Nuqtalarda ushbu tovarlarni tegishli miqdorda etkazib berishi kerak bo'lgan iste'molchilar mavjud. belgilaylik c ij punktlar o'rtasida yuk birligini tashish narxi

Biz iste'molchilarning ehtiyojlarini qondirish uchun etarli miqdorda iste'molchilar tomonidan tovarlarni tashish operatsiyalarini o'rganamiz. Nuqtadan tashilgan tovarlar miqdori bilan belgilaymiz A i ishora qilish b j .

Iste'molchi talablarini qondirish uchun qiymatlar zarur X ij shartlarga javob berdi:

Shu bilan birga a omboridan; Siz u erda mavjud bo'lgandan ko'proq oziq-ovqat eksport qila olmaysiz. Bu shuni anglatadiki, kerakli miqdorlar tengsizliklar tizimini qondirishi kerak:

Shartlarni (8.14), (8.15) qondirishning son-sanoqsiz usullari mavjud, ya'ni iste'molchi talablariga javob beradigan transport rejasini tuzish. Amaliyot tadqiqotchisi ma'lum bir yechimni tanlashi, ya'ni ma'lum bir qarorni belgilashi uchun X ij, ba'zi tanlov qoidasi shakllantirilishi kerak, maqsad haqidagi sub'ektiv fikrimizni aks ettiruvchi mezon yordamida aniqlanishi kerak.

Mezon muammosi operatsiyani o'rganishdan mustaqil ravishda hal qilinadi - mezon operatsion tomon tomonidan belgilanishi kerak. Ushbu muammoda mumkin bo'lgan mezonlardan biri transport xarajatlari bo'ladi. U quyidagicha aniqlanadi:

Keyin transport masalasi chiziqli dasturlash masalasi sifatida shakllantiriladi: (8.14), (8.15) cheklovlarni qanoatlantiradigan va (8.16) funktsiyaga minimal qiymat beradigan miqdorlarni aniqlang. Cheklov (8.15) - muvozanat sharti; (8.14) shartni operatsiya maqsadi deb atash mumkin, chunki operatsiyaning ma'nosi iste'molchilarning ehtiyojlarini qondirishdir.

Ushbu ikki shart asosan operatsiya modelini tashkil qiladi. Operatsiyani amalga oshirish operatsiya maqsadiga erishish mezoniga bog'liq bo'ladi. Mezon turli rollarda paydo bo'lishi mumkin. U maqsadni rasmiylashtirish usuli sifatida ham, ruxsat etilganlar, ya'ni cheklovlarni qondiradigan harakatlarni tanlash printsipi sifatida ham harakat qilishi mumkin.

Transport muammosini hal qilishning mashhur usullaridan biri bu potentsiallar usulidir.

Muammoni hal qilishning birinchi bosqichida qoniqtiradigan dastlabki tashish rejasi tuziladi

cheklovlar (8.14), (8.15). Agar (ya'ni, umumiy ehtiyojlar omborlardagi mahsulotlarning umumiy zaxiralariga to'g'ri kelmasa), u holda xayoliy iste'mol nuqtasi yoki transport xarajatlari nolga teng bo'lgan xayoliy ombor hisobga olinadi. Yangi vazifa uchun omborlardagi tovarlarning umumiy soni ularning umumiy talabiga to'g'ri keladi. Keyin, qandaydir usul bilan (masalan, eng kichik element yoki shimoli-g'arbiy burchak), asl reja topiladi. Olingan rejaning keyingi bosqichida maxsus xususiyatlar tizimi - potentsiallar tuziladi. Optimal rejaning zarur va yetarli sharti uning salohiyatidir. Rejani takomillashtirish tartibi u potentsial (optimal) bo'lgunga qadar amalga oshiriladi.

Muammo 3b. Umumiy holatda (8.10 – 8.11) muammo chiziqli bo‘lmagan dasturlash masalasi deb ataladi. Keling, uni yanada qabul qilingan shaklda ko'rib chiqaylik:

sharoitlarda

Ushbu muammoni hal qilish uchun gevşeme deb ataladigan usullar qo'llaniladi. Nuqtalar ketma-ketligini qurish jarayoni relaksatsiya deb ataladi, agar:

Tushish usullari (umumiy sxema). Cheklanmagan optimallashtirish masalasini hal qilish uchun barcha tushish usullari (8.17) tushish yo'nalishini tanlashda yoki tushish yo'nalishi bo'ylab harakatlanish usulida farqlanadi. Tushilish usullari quyidagi ketma-ketlik qurilish protsedurasidan iborat { x k }.

Dastlabki yaqinlashish sifatida ixtiyoriy nuqta tanlanadi x 0 . Ketma-ket taxminlar quyidagi sxema bo'yicha tuziladi:

Nuqta x k tushish yo'nalishi tanlangan - s k ;

Formula yordamida (k + 1) – e ga yaqinligini toping:

bu yerda miqdor tengsizlikni qanoatlantiradigan istalgan son sifatida tanlanadi

bu yerda raqam istalgan raqam qachon

Ko'pgina tushirish usullarida  k qiymati birlikka teng tanlanadi. Shunday qilib,  k ni aniqlash uchun bir o'lchovli minimallashtirish masalasini hal qilish kerak.

Gradientni tushirish usuli. Chunki antigradient funktsiyaning eng tez pasayish yo'nalishini ko'rsatadi f(x), keyin nuqtadan harakat qilish tabiiydir X k bu yo'nalishda. Descent usuli, bu gradient tushish usuli deb ataladi. Agar bo'lsa, bo'shashish jarayoni eng tik tushish usuli deb ataladi.

Konjugatsiya yo'nalishlari usuli. Chiziqli algebrada bu usul chiziqli algebraik tenglamalar tizimini echish uchun konjugat gradient usuli sifatida tanilgan. AX=b, va shuning uchun kvadratik funktsiyani minimallashtirish usuli sifatida

Usul diagrammasi:

Agar = 0 bo'lsa, bu sxema eng tik tushish usuli sxemasiga aylanadi. Qiymatni to'g'ri tanlash t k konjugat yo'nalish usulining gradient tushish usullaridagi kabi tezlik bilan yaqinlashishini kafolatlaydi va kvadratik tushishda takrorlanishlar soni chekli bo'lishini ta'minlaydi (masalan).

Koordinatali tushish. Har bir iteratsiyada, tushish yo'nalishi sifatida - s k koordinata o'qlaridan biri bo'ylab yo'nalish tanlanadi. Usul 0(1/m) darajasidagi minimallashtirish jarayonining yaqinlashuv tezligiga ega. Bundan tashqari, bu kosmosning o'lchamiga sezilarli darajada bog'liq.

Usul diagrammasi:

koordinata vektori qayerda

Agar nuqtada x k funktsiya gradientining xatti-harakati haqida ma'lumot mavjud f(x), Masalan:

keyin tushish yo'nalishi sifatida s k koordinata vektorini olishingiz mumkin e j . Bunday holda, usulning yaqinlashish tezligi gradient tushishiga qaraganda n marta kamroq.

Yoniq dastlabki bosqich minimallashtirish jarayonida siz tushish birinchi yo'nalishda amalga oshirilganda, tsiklik koordinata tushish usulidan foydalanishingiz mumkin. e 1 , keyin e 2 bo'ylab va hokazo gacha e P , shundan so'ng butun tsikl yana takrorlanadi. Avvalgisidan ko'ra ko'proq istiqbolli koordinatali tushish bo'lib, unda tushish yo'nalishlari tasodifiy tanlanadi. Yo'nalishni tanlashda ushbu yondashuv bilan, funktsiyani kafolatlaydigan aprior taxminlar mavjud f(x) Bilan da birlikka moyil bo'lgan ehtimollik, jarayon 0(1/m) darajasida yaqinlashadi.

Usul diagrammasi:

Jarayonning har bir bosqichida n ta raqamdan tasodifiy raqam tanlanadi (1, 2, ..., n) j(k) va kabi s k birlik koordinata vektori tanlanadi e j ( k ) , shundan keyin tushish sodir bo'ladi:

Tasodifiy tushish usuli.s k, bu sferada bir xil taqsimlanish sharti bilan, so'ngra jarayonning k-bosqichida hisoblangan elementga muvofiq X Kimga belgilangan:

Tasodifiy tushish usulining konvergentsiya tezligi gradient tushish usulidan n marta past, lekin tasodifiy koordinata tushish usulidan n marta yuqori. Ko'rib chiqilayotgan tushirish usullari har doim ham konveks bo'lmagan va ularga nisbatan juda kichik cheklovlar (masalan, mahalliy minimallarning yo'qligi) ostida ularning yaqinlashishini kafolatlaydigan funktsiyalarga ham tegishli.

Matematik dasturlashning relaksatsiya usullari. 36-masalaga qaytaylik ((8.17) – (8.18)):

sharoitlarda

Cheklovlar bilan optimallashtirish muammolarida, tushish yo'nalishini tanlash yangi qiymatni doimiy ravishda tekshirish zarurligini o'z ichiga oladi. X k +1 avvalgisi bilan bir xil bo'lishi kerak x k cheklovlar tizimini qondirish X.

Shartli gradient usuli. Ushbu usulda tushish yo'nalishini tanlash g'oyasi quyidagicha: nuqtada X Kimga funktsiyani lineerlashtiring f(x), chiziqli funktsiyani qurish va keyin minimallashtirish f(x) to'plamda X, nuqta toping y k . Shundan so'ng, ular taxmin qiladilar va keyin bu yo'nalish bo'ylab tushadilar, shunday qilib

Shunday qilib, yo'nalishni topish uchun - s k to'plamdagi chiziqli funktsiyani minimallashtirish masalasini hal qilish kerak. X. Agar X o'z navbatida chiziqli cheklovlar bilan berilgan bo'lsa, u chiziqli dasturlash muammosiga aylanadi.

Mumkin yo'nalishlar usuli. Usulning g'oyasi: bir nuqtada barcha mumkin bo'lgan yo'nalishlar orasida X Kimga qaysi funktsiyani tanlang f(x) eng tez pasayadi va keyin shu yo'nalish bo'ylab pastga tushadi.

Yo'nalish - s nuqtada XX hamma uchun shunday raqam mavjud bo'lsa, mumkin deb ataladi. Mumkin bo'lgan yo'nalishni topish uchun chiziqli dasturlash masalasini yoki eng oddiy kvadratik dasturlash masalasini hal qilish kerak:

Shartlar ostida:

Keling, bu muammoning yechimi bo'lsin. Shart (8.25) yo'nalishning mumkin bo'lishini kafolatlaydi. Shart (8.26) maksimal qiymatni ta'minlaydi (ya'ni barcha mumkin bo'lgan yo'nalishlar orasida - s, yo'nalish - funktsiyaning eng tez pasayishini ta'minlaydi f(x). Shart (8.27) masala yechimining cheksizligini bartaraf qiladi. Mumkin yo'nalishlar usuli mumkin bo'lgan hisoblash xatolariga chidamli. Biroq, umumiy holatda uning yaqinlashish tezligini baholash qiyin va bu muammo hal qilinmagan.

Tasodifiy qidiruv usuli. Yuqoridagi minimallashtirish usullarini amalga oshirish, odatda, juda ko'p mehnat talab qiladi, cheklashlar to'plami oddiy geometrik tuzilishga ega bo'lgan eng oddiy holatlar bundan mustasno (masalan, u ko'p o'lchovli parallelepiped). Umuman olganda, tasodifiy qidirish usuli, tushish yo'nalishi tasodifiy tanlangan bo'lsa, juda istiqbolli bo'lishi mumkin. Bunday holda, biz konvergentsiya tezligida sezilarli darajada yo'qotamiz, ammo yo'nalishni tanlashning soddaligi minimallashtirish muammosini hal qilish uchun umumiy mehnat xarajatlari nuqtai nazaridan ushbu yo'qotishlarni qoplashi mumkin.

Usul diagrammasi:

Koordinata boshida joylashgan n o'lchovli birlik sharida tasodifiy nuqta tanlanadi r k, bu sohada bir xil taqsimotga bo'ysunadi, keyin esa tushish yo'nalishi s k shartlardan,

. boshlang'ich yaqinlashish sifatida tanlanadi. Har bir iteratsiyada hisoblangan nuqta asosida x k qurilish ishlari olib borilmoqda ( k+ 1) nuqta x k +1 :

= dan tengsizlikni qanoatlantiradigan istalgan raqam sifat sifatida tanlanadi:

Ushbu usulning yaqinlashishi funktsiyaga nisbatan juda erkin cheklovlar ostida isbotlangan f (qavariq) va ko'plab cheklovlar X (qavariqlik va yopilish).

Muammo 1. Toping

bu erda x = (x 1 .. x p) e E p

Bu masala tenglamalar tizimini yechish bilan bog'liq

va ikkinchi differentsialning qiymatini o'rganing

nuqtalarda (a-|, (*2, a n) (7.3) tenglamalar yechimlari.

Agar (7.4) kvadratik shakl bir nuqtada manfiy aniqlangan bo'lsa, u holda u maksimal qiymatiga, musbat aniqlangan bo'lsa, minimal qiymatiga etadi.

Misol:

Tenglamalar tizimi yechimlarga ega:

Nuqta (-1; 3,0) maksimal nuqta, nuqta (1; 3,2) esa minimal nuqta hisoblanadi.

Vazifa 2. Toping

shartlarda:

Bu masala 2 Lagranj multiplikator usuli bilan yechiladi, buning uchun tizim yechimi topiladi (t + p) tenglamalar:

2-misol. Aylana ichiga chizilgan maksimal maydoni bo‘lgan to‘rtburchakning tomonlarini toping To'rtburchakning L maydoni

quyidagicha yozilishi mumkin: A= 4xy, keyin

qayerda

Vazifa 3. Shartlar ostida toping:

Bu muammo funksiyalar tomonidan aniqlangan sozlamalarning keng doirasini qamrab oladi f va chorshanba Agar ular chiziqli bo'lsa, muammo chiziqli dasturlash masalasidir.

Vazifa uchun.

sharoitlarda

Simpleks usuli yordamida hal qilinadi, bu chiziqli algebra apparati yordamida (7.13) bilan aniqlangan ko'pburchakning uchlarini maqsadli qidirishni amalga oshiradi.

Simpleks usuli ikki bosqichdan iborat.

Bosqich 1. Etakchi yechimni topish x^ 0). Etakchi eritma ko'pburchakning nuqtalaridan biri (7.13).

2-bosqich. Optimal yechim topish. U ko'pburchakning (7.13) uchlarini ketma-ket sanab topiladi, bunda z maqsad funksiyasining qiymati har bir qadamda kamaymaydi, ya'ni:

Chiziqli dasturlash muammosining alohida holati transport muammosi deb ataladi.

Transport muammosi. a-1, a 2, .... a l nuqtalarda mos ravishda x 1, x 2, ..., x l miqdorda tovarlar saqlanadigan omborlar bo'lsin. b-|, b 2,..., b t nuqtalarida ushbu tovarlarni y- miqdorda yetkazib berishi kerak bo'lgan iste'molchilar mavjud. y 2, y t mos ravishda. belgilaylik Cjj a-| punktlari orasida yuk birligini tashish narxi va tomonidan.

Biz iste'molchilarning ehtiyojlarini qondirish uchun etarli miqdorda iste'molchilar tomonidan tovarlarni tashish jarayonini tekshiramiz. bilan belgilaymiz Hu a nuqtadan nuqtaga tashiladigan tovarlar miqdori.

Iste'molchi ehtiyojlarini qondirish uchun x, y qiymatlari quyidagi shartlarni qondirishi kerak:

Shu bilan birga, ombordan u yerdagidan ko‘proq mahsulotni eksport qilishning iloji yo‘q. Bu shuni anglatadiki, kerakli miqdorlar tengsizliklar tizimini qondirishi kerak:

Shartlarni qondirish (7.14), (7.15), ya'ni. Iste'molchi ehtiyojlarini qondiradigan transport rejasini yaratishning son-sanoqsiz usullari mavjud. Operatsiya tadqiqotchisi ma'lum bir optimal echimni tanlashi uchun, ya'ni. aniq belgilang Xjj, ba'zi tanlov qoidasi shakllantirilishi kerak, maqsad haqidagi sub'ektiv fikrimizni aks ettiruvchi mezon yordamida aniqlanishi kerak.

Mezon muammosi operatsiyani o'rganishdan mustaqil ravishda hal qilinadi - mezon operatsion tomon tomonidan belgilanishi kerak. Ko'rib chiqilayotgan muammoda mumkin bo'lgan mezonlardan biri transport xarajatlari bo'ladi. ga teng

Keyin transport masalasi chiziqli dasturlash muammosi sifatida shakllantiriladi: (7.14), (7.15) cheklovlarni qanoatlantiradigan x,y > O qiymatlarini aniqlang va (7.16) funktsiyaga minimal qiymat bering. Cheklov (7.15) - muvozanat sharti; (7.14) shartni operatsiya maqsadi deb atash mumkin, chunki operatsiyaning ma'nosi iste'molchilarning ehtiyojlarini qondirishdir.

Ikkita shartni belgilash asosan operatsiya modelini tashkil qiladi. Operatsiyani amalga oshirish operatsiya maqsadiga erishish mezoniga bog'liq bo'ladi. Mezon turli rollarda paydo bo'lishi mumkin. U maqsadni rasmiylashtirish usuli sifatida ham, ruxsat etilganlar orasidan harakatlarni tanlash printsipi sifatida ham harakat qilishi mumkin, ya'ni. cheklovlarni qondirish.

Transport muammosini hal qilishning mashhur usullaridan biri potentsial usul bo'lib, uning sxemasi quyidagicha.

Muammoni hal qilishning birinchi bosqichida (7.14), (7.15) cheklovlarni qondiradigan dastlabki tashish rejasi tuziladi. Agar

(ya'ni, umumiy ehtiyojlar omborlardagi mahsulotlarning umumiy zaxiralariga to'g'ri kelmaydi), keyin iste'molning xayoliy nuqtasi hisobga olinadi. yoki xayoliy ombor

nolga teng transport xarajatlari bilan. Yangi vazifa uchun omborlardagi tovarlarning umumiy soni ularning umumiy talabiga to'g'ri keladi. Keyin, qandaydir usul bilan (masalan, eng kichik element yoki shimoli-g'arbiy burchak) asl reja topiladi. Keyingi bosqichda, natijada olingan rejaning protseduralari maxsus xususiyatlar tizimini - potentsialni quradi. Optimal rejaning zarur va yetarli sharti uning salohiyatidir. Rejani takomillashtirish protsedurasi reja potentsial (optimal) bo'lgunga qadar takrorlanadi.

Vazifa 36. Umumiy holatda (7.10-7.11) masala nochiziqli dasturlash masalasi deyiladi. Keling, uni shaklda ko'rib chiqaylik

sharoitlarda

Ushbu muammoni hal qilish uchun gevşeme deb ataladigan usullar qo'llaniladi. Nuqtalar ketma-ketligini qurish jarayoni relaksatsiya deb ataladi, agar:

Tushilish usullari (umumiy sxema). Cheklanmagan optimallashtirish masalasini hal qilishda barcha tushish usullari (7.17) tushish yo'nalishini tanlashda yoki tushish yo'nalishi bo'yicha harakat qilish usulida farqlanadi. Tushilish usullari quyidagi ketma-ketlik qurilish protsedurasidan iborat (x k).

Dastlabki yaqinlashish sifatida ixtiyoriy Xq nuqta tanlanadi. Ketma-ket taxminlar quyidagi sxema bo'yicha tuziladi:

  • nuqta x k tushish yo'nalishi tanlangan - S k ;
  • toping (To+ 1) formula bo'yicha taxminan

bu erda miqdor sifatida $k tengsizlikni qanoatlantiradigan istalgan sonni tanlang

raqam qayerda X k - 0 X k min f(x k - $ Sk) bo'ladigan istalgan son.

Ko'pgina tushish usullarida qiymat X k birga teng tanlanadi. Shunday qilib, (3^) aniqlash uchun bir o'lchovli minimallashtirish masalasini hal qilish kerak.

Gradientni tushirish usuli. Anti-gradient bo'lgani uchun G(x k) funktsiyaning eng tez kamayish yo'nalishini ko'rsatadi f(x), keyin nuqtadan harakat qilish tabiiydir x dan tomonidan bu yo'nalish. Bunda tushish usuli S k = f"(x k) gradient tushish usuli deb ataladi. Agar X k= 1, keyin gevşeme jarayoni eng tik tushish usuli deb ataladi.

Konjugatsiya yo'nalishlari usuli. IN Chiziqli algebrada bu usul chiziqli algebraik tenglamalar tizimini echish uchun konjugat gradient usuli sifatida tanilgan. OH= b va shuning uchun kvadrat funktsiyani minimallashtirish usuli sifatida f(x) =((Dx - b)) 2 .

Usul diagrammasi:

Agar f k = 0, keyin bu sxema eng tik tushish usuli sxemasiga aylanadi. Qiymatni to'g'ri tanlash tk konjugat yoʻnalishi usulining gradient tushish usullaridagi kabi tezlik bilan yaqinlashishini kafolatlaydi va kvadratik tushishda takrorlanishlar soni chekli boʻlishini taʼminlaydi (masalan,

Koordinatali tushish. Har bir iteratsiyada, tushish yo'nalishi sifatida S k koordinata o'qlaridan biri bo'ylab yo'nalish tanlanadi. Usul 0 (1 //77) tartibidagi minimallashtirish jarayonining yaqinlashuv tezligiga ega va u sezilarli darajada bo'shliqning o'lchamiga bog'liq.

Usul diagrammasi:

Qayerda koordinata vektori,

Agar nuqtada x k funktsiya gradientining xatti-harakati haqida ma'lumot mavjud f(x), Masalan,

keyin tushish yo'nalishi sifatida S k ey koordinata vektorini olishimiz mumkin. Bunday holda, usulning yaqinlashuv tezligi P gradient tushishiga nisbatan marta kamroq.

Minimallashtirish jarayonining dastlabki bosqichida siz tsiklik koordinatalar bo'yicha tushish usulidan foydalanishingiz mumkin, bunda dastlab e-| yo'nalishi bo'yicha, keyin b2 yo'nalishi bo'yicha va hokazo. qadar e p, shundan keyin butun tsikl takrorlanadi. Ta'riflanganidan ko'ra ko'proq istiqbolli koordinatali tushish bo'lib, unda tushish yo'nalishlari tasodifiy tanlanadi. Yo'nalishni tanlashda ushbu yondashuv bilan, funktsiyani kafolatlaydigan aprior taxminlar mavjud f(x) jarayon 0(1) tezlikda yaqinlashganda birlikka moyil bo'lish ehtimoli bilan 1t).

Usul diagrammasi:

Jarayonning har bir bosqichida P raqamlar (1, 2, ..., P) raqam tasodifiy tanlanadi j(k) va kabi s k birlik koordinata vektori tanlanadi vsch, shundan keyin tushish sodir bo'ladi:


Tasodifiy tushish usuli. Koordinata boshida joylashgan n o'lchovli birlik sharida tasodifiy nuqta tanlanadi S k, ushbu sohada yagona taqsimotga bo'ysunish, keyin esa / bo'yicha hisob-kitoblarga ko'ra st qadam jarayon elementi x k belgilangan x k+]:


Tasodifiy tushish usulining konvergentsiya darajasi P gradient tushish usulidan marta kamroq, lekin P tasodifiy koordinatalarni tushirish usulidan ko'ra ko'proq. Ko'rib chiqilayotgan tushirish usullari har doim ham konveks bo'lmagan va ularga nisbatan juda kichik cheklovlar (masalan, mahalliy minimallarning yo'qligi) ostida ularning yaqinlashishini kafolatlaydigan funktsiyalarga ham tegishli.

Matematik dasturlashning relaksatsiya usullari. 36-masalaga qaytaylik ((7.17) - (7.18)):

sharoitlarda

Cheklovlar bilan optimallashtirish muammolarida, tushish yo'nalishini tanlash yangi qiymatni doimiy ravishda tekshirish zarurligini o'z ichiga oladi. x k +" avvalgisi bilan bir xil bo'lishi kerak x k, X cheklovlar tizimini qanoatlantiring.

Shartli gradient usuli. IN Ushbu usulda tushish yo'nalishini tanlash g'oyasi quyidagicha: nuqtada x k funktsiyani lineerlashtiring

f(x), chiziqli funktsiyani qurish f(x) = f(x k) + (y"(x k), x-x k), va keyin minimallashtirish f(x) to'plamda X, nuqta toping da k. Shundan keyin ular ishonadilar S k = y k - x k va keyin bu yo'nalish bo'ylab pastga tushing Xk+ 1= x k - $ k (x k -y k), shuning uchun g X.

Shunday qilib, yo'nalishni topish uchun S k X to'plamdagi chiziqli funktsiyani minimallashtirish masalasini hal qilish kerak.Agar X o'z navbatida chiziqli cheklovlar bilan aniqlansa, u chiziqli dasturlash masalasiga aylanadi.

Mumkin yo'nalishlar usuli. Usulning g'oyasi: xk nuqtasidagi barcha mumkin bo'lgan yo'nalishlar orasidan qaysi funktsiyani tanlang f(x) eng tez pasayadi va keyin shu yo'nalish bo'ylab pastga tushadi.

Yo'nalish s nuqtada X e X Agar shunday raqam bo'lsa (3 > O, ya'ni). X- (3s e X hamma uchun (3 g. Mumkin bo'lgan yo'nalishni topish uchun chiziqli dasturlash masalasini yoki eng oddiy kvadratik dasturlash masalasini hal qilish kerak: ha?=>min sharoitlarda

Mayli d k Va s k- bu muammoni hal qilish. Shart (7.25) yo'nalishni kafolatlaydi s k mumkin. Shart (7.26) maksimal qiymatni ta'minlaydi (/"( x k), s), bular. barcha mumkin bo'lgan yo'nalishlar orasida s, yo'nalishi s k eng tez pasayuvchi funksiyani ta'minlaydi f(x). Shart (7.27) masala yechimining cheksizligini bartaraf qiladi. Mumkin yo'nalishlar usuli mumkin bo'lgan hisoblash xatolariga chidamli. Biroq, umumiy holatda uning yaqinlashish tezligini baholash qiyin va bu muammo hal qilinmagan.

Tasodifiy qidiruv usuli. Oldin tasvirlangan minimallashtirish usullarini amalga oshirish, odatda, juda ko'p mehnat talab qiladi, cheklashlar to'plami oddiy geometrik tuzilishga ega bo'lgan eng oddiy holatlar bundan mustasno (masalan, bu ko'p o'lchovli parallelepiped). Umuman olganda, tasodifiy qidirish usuli, tushish yo'nalishi tasodifiy tanlangan bo'lsa, juda istiqbolli bo'lishi mumkin. Bunday holda, konvergentsiya tezligida sezilarli yo'qotish bo'ladi, ammo yo'nalishni tanlashning soddaligi minimallashtirish muammosini hal qilish uchun umumiy mehnat xarajatlari nuqtai nazaridan ushbu yo'qotishlarni qoplashi mumkin.

Usul diagrammasi:

bosh markazida joylashgan n o'lchovli birlik sharida tasodifiy nuqta tanlanadi gu bu sohada bir xil taqsimlangan holda, keyin esa tushish yo'nalishi - s^ shartlardan

Dastlabki taxmin sifatida biz tanlaymiz xc e X. Har bir iteratsiyada hisoblangan nuqta asosida X? qurilish ishlari olib borilmoqda (k + 1) nuqta x^+ y:

dan istalgan raqam tengsizlikni qondirish

Ushbu usulning yaqinlashishi funktsiya / (qavariqlik) va cheklovlar to'plami bo'yicha juda qattiq bo'lmagan cheklovlar ostida isbotlangan. X(qavariqlik va yopilish).

Optimallashtirish usullari orasida nol tartib SAPRda Rosenbrock, konfiguratsiya, deformatsiyalanadigan poliedr va tasodifiy qidirish 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-Jives). 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 borligi aniqlansa eng yaxshi qiymat ko'pburchakning cho'qqilari orasidagi ob'ektiv funktsiya, keyin 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

koeffitsient qayerda. Bundan tashqari, konjugatsiya holati hisobga olinadi

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:

yoki

qayerda

va (6) va (7) ni hisobga olgan holda


(10) ifoda chiziqli algebraik tenglamalar sistemasidir. Uning ildizi yechimning yana bir yaqinlashuvidir

Agar jarayon bir-biriga yaqinlashsa, u holda yechimga kam sonli iteratsiyalarda erishiladi, uning oxiri shartning bajarilishi hisoblanadi.
Qayerda


Shunung uchun

Ko'rsatish mumkinki, , - qachon ga moyil bo'ladi, bu erda boshqariladigan parametrlar maydonining o'lchami. Qadamlardan so'ng, dan qayta boshlashingiz kerak.

Har qanday masala bo'yicha boshqaruv darajasida qabul qilinadigan qarorning eng maqbul varianti optimal deb hisoblanadi va uni izlash jarayoni optimallashtirish hisoblanadi.

Hozirgi vaqtda ishlab chiqarishni boshqarishning tashkiliy, ijtimoiy-iqtisodiy, texnik va boshqa jihatlarining o'zaro bog'liqligi va murakkabligi boshqaruv qarorini qabul qilish bilan bog'liq. katta miqdorda Bir-biri bilan chambarchas bog'liq bo'lgan har xil turdagi omillar, shuning uchun an'anaviy tahlil usullari yordamida har birini alohida tahlil qilish imkonsiz bo'lib qoladi.

Ko'pgina omillar qaror qabul qilish jarayonida hal qiluvchi rol o'ynaydi va ularni (tabiiy ravishda) miqdoriy aniqlash mumkin emas. Bundan tashqari, amalda o'zgarmaganlari ham bor. Shu munosabat bilan muhimlarni tanlashni ta'minlaydigan maxsus usullarni ishlab chiqish zarurati tug'ildi boshqaruv qarorlari murakkab tashkiliy, iqtisodiy, texnik muammolar (ekspert baholashlari, operatsion tadqiqotlar va optimallashtirish usullari va boshqalar) doirasida.

Operatsion tadqiqotlarga yo'naltirilgan usullar ishlab chiqarish va transport jarayonlarini tashkil etish, yirik ishlab chiqarishni rejalashtirish, moddiy-texnik ta'minot kabi boshqaruv sohalarida optimal echimlarni topish uchun ishlatiladi.

Yechimlarni optimallashtirish usullari bir qator omillarning raqamli baholarini solishtirish orqali tadqiqotlarni o'z ichiga oladi, ularning tahlili an'anaviy usullar amalga oshirish mumkin emas. Iqtisodiy tizimning mumkin bo'lgan variantlari orasida eng yaxshisi optimal echimdir va tizimning alohida elementlariga nisbatan eng maqbuli suboptimaldir.

Operatsion tadqiqot usullarining mohiyati

Yuqorida aytib o'tilganidek, ular boshqaruv qarorlarini optimallashtirish usullarini shakllantiradi. Ularning asosini jarayonni, faoliyat turini yoki o'rganilayotgan tizimni ifodalovchi matematik (deterministik), ehtimollik modellari tashkil etadi. Bu turdagi modellar tegishli muammoning miqdoriy tavsifini beradi. Ular optimal variantni izlash jarayonida muhim boshqaruv qarorlarini qabul qilish uchun asos bo'lib xizmat qiladi.

To'g'ridan-to'g'ri ishlab chiqarish menejerlari uchun muhim rol o'ynaydigan va ko'rib chiqilayotgan usullardan foydalanish jarayonida hal qilinadigan muammolar ro'yxati:

  • tanlangan qaror variantlarining haqiqiyligi darajasi;
  • ular muqobillardan qanchalik yaxshi;
  • aniqlovchi omillarni hisobga olish darajasi;
  • tanlangan yechimlarning optimalligi mezoni qanday.

Qarorlarni optimallashtirishning ushbu usullari (boshqaruv) iloji boricha ko'proq firmalar, kompaniyalar yoki ularning bo'linmalari uchun optimal echimlarni topishga qaratilgan. Ular statistik, matematika va iqtisodiy fanlar (o'yin nazariyasi, navbat, grafika, optimal dasturlash, matematik statistika) bo'yicha mavjud yutuqlarga asoslanadi.

Ekspert baholash usullari

Boshqaruv qarorlarini optimallashtirishning ushbu usullari muammo qisman yoki to'liq rasmiylashtirishga tobe bo'lmaganda qo'llaniladi va uning echimini matematik usullar yordamida topib bo'lmaydi.

Ekspertiza - bu xulosalar, tavsiyalar, fikrlar va baholashlarni olish uchun maxsus bilim bazasi va ta'sirchan tajribaga ega bo'lgan tegishli shaxslar tomonidan muayyan boshqaruv qarorini ishlab chiqish bosqichida murakkab maxsus masalalarni o'rganishdir. Ekspert tadqiqotlari jarayonida ular foydalanadilar so'nggi yutuqlar va ekspertning ixtisosligi doirasidagi fan va texnologiya.

Bir qator boshqaruv qarorlarini (ekspert baholashlarini) optimallashtirishning ko'rib chiqilgan usullari ishlab chiqarish sohasidagi quyidagi boshqaruv vazifalarini hal qilishda samarali hisoblanadi:

  1. Norasmiy, sifat xususiyatlari bilan ajralib turadigan murakkab jarayonlar, hodisalar, vaziyatlar, tizimlarni o'rganish.
  2. Ishlab chiqarish tizimining ishlashi va rivojlanishida hal qiluvchi ahamiyatga ega bo'lgan muhim omillarni ma'lum bir mezon bo'yicha tartiblash va aniqlash.
  3. Ko'rib chiqilayotgan optimallashtirish usullari ishlab chiqarish tizimining rivojlanish tendentsiyalarini, shuningdek uning tashqi muhit bilan o'zaro ta'sirini bashorat qilishda ayniqsa samaralidir.
  4. Malakali mutaxassislarning fikr-mulohazalarini o'rtacha hisoblash orqali, asosan, miqdoriy va sifat xarakterga ega bo'lgan maqsadli funktsiyalarni ekspert baholashning ishonchliligini oshirish.

Va bu bir qator boshqaruv qarorlarini optimallashtirishning ba'zi usullari (ekspert bahosi).

Ko'rib chiqilayotgan usullarning tasnifi

Parametrlar soniga qarab optimallashtirish muammolarini hal qilish usullarini quyidagilarga bo'lish mumkin:

  • Bir o'lchovli optimallashtirish usullari.
  • Ko'p o'lchovli optimallashtirish usullari.

Ular, shuningdek, "raqamli optimallashtirish usullari" deb ataladi. Aniqroq aytganda, bular uni qidirish algoritmlari.

Sanoatlardan foydalanishning bir qismi sifatida usullar quyidagilardir:

  • to'g'ridan-to'g'ri optimallashtirish usullari (nol tartib);
  • gradient usullari (1-tartib);
  • 2-tartib usullari va boshqalar.

Ko'p o'lchovli optimallashtirish usullarining aksariyati ikkinchi guruh usullari (bir o'lchovli optimallashtirish) muammosiga yaqin.

Bir o'lchovli optimallashtirish usullari

Har qanday raqamli optimallashtirish usullari maqsad funktsiyasi va ruxsat etilgan to'plamni va ularning hosilalarini belgilaydigan funktsiyalarning qiymatlari kabi xususiyatlarni taxminiy yoki aniq hisoblashga asoslanadi. Shunday qilib, har bir alohida vazifa uchun hisoblash uchun xususiyatlarni tanlash masalasi ko'rib chiqilayotgan funktsiyaning mavjud xususiyatlariga, ma'lumotlarni saqlash va qayta ishlashda mavjud imkoniyatlar va cheklovlarga qarab hal qilinishi mumkin.

Optimallashtirish masalalarini hal qilishning quyidagi usullari mavjud (bir o'lchovli):

  • Fibonachchi usuli;
  • dixotomiyalar;
  • oltin nisbat;
  • qadamni ikki barobarga oshirish.

Fibonachchi usuli

Birinchidan, intervaldagi x nuqtaning koordinatalarini farqning (x - a) farqiga (b - a) nisbatiga teng son sifatida belgilashingiz kerak. Shuning uchun a ning oraliqga nisbatan koordinatasi 0 ga, b esa 1 ga, o‘rta nuqtasi esa ½ ga teng.

Agar F0 va F1 bir-biriga teng deb faraz qilsak va 1 qiymatini olsak, F2 2 ga teng bo'ladi, F3 - 3, ..., keyin Fn = Fn-1 + Fn-2. Shunday qilib, Fn - bu Fibonachchi raqamlari va Fibonachchi qidiruvi ular bilan chambarchas bog'liq bo'lganligi sababli, maksimalni ketma-ket qidirish deb ataladigan optimal strategiyadir.

Optimal strategiyaning bir qismi sifatida xn - 1 = Fn-2: Fn, xn = Fn-1: Fn ni tanlash odatiy holdir. Har biri toraytirilgan noaniqlik oralig'i rolini o'ynashi mumkin bo'lgan har qanday ikkita interval (yoki) uchun yangi intervalga nisbatan nuqta (meros) yoki koordinatalariga ega bo'ladi yoki . Keyinchalik, yangi intervalga nisbatan taqdim etilgan koordinatalardan biriga ega bo'lgan nuqta xn - 2 sifatida olinadi. Agar siz F(xn - 2) funksiya qiymatidan oldingi intervaldan meros bo'lib foydalansangiz, noaniqlik oralig'ini qisqartirish va bitta funktsiya qiymatini meros qilib olish mumkin bo'ladi.

Yakuniy bosqichda noaniqlik oralig'iga o'tish mumkin bo'ladi, masalan, o'rta nuqta oldingi bosqichdan meros bo'lib qoladi. X1 sifatida nisbiy koordinatasi ½+e bo'lgan nuqta o'rnatiladi va yakuniy noaniqlik oralig'i ga nisbatan yoki [½, 1] bo'ladi.

1-bosqichda bu intervalning uzunligi Fn-1 ga qisqartirildi: Fn (birdan). Tugatish bosqichlarida mos keladigan intervallarning uzunligini qisqartirish Fn-2: Fn-1, Fn-3: Fn-2, ..., F2: F3, F1: F2 (1 + 2e) raqamlari bilan ifodalanadi. ). Shunday qilib, oxirgi versiya kabi intervalning uzunligi (1 + 2e) qiymatini oladi : Fn.

Agar e ni e'tiborsiz qoldiradigan bo'lsak, u holda asimptotik tarzda 1: Fn n →∞ bilan rn ga teng bo'ladi va r = (√5 - 1) : 2, bu taxminan 0,6180 ga teng.

Shuni ta'kidlash kerakki, muhim n uchun asimptotik tarzda, Fibonachchi qidiruvining har bir keyingi bosqichi yuqoridagi koeffitsient bilan ko'rib chiqilgan intervalni sezilarli darajada toraytiradi. Bu natija 0,5 bilan solishtirish kerak (funksiyaning nolini topish uchun biseksiya usulida noaniqlik oralig'ini toraytirish koeffitsienti).

Dixotomiya usuli

Agar siz ma'lum bir maqsadli funktsiyani tasavvur qilsangiz, birinchi navbatda (a; b) oraliqda uning ekstremumini topishingiz kerak. Buning uchun abscissa o'qi to'rtta ekvivalent qismga bo'linadi, keyin 5 nuqtada ko'rib chiqilayotgan funktsiyaning qiymatini aniqlash kerak. Keyinchalik, ular orasidan minimal tanlanadi. Funksiyaning ekstremumi minimal nuqtaga tutashgan (a"; b") oralig'ida bo'lishi kerak. Qidiruv chegaralari 2 marta toraydi. Va agar minimal a yoki b nuqtada joylashgan bo'lsa, u to'rt marta torayadi. Yangi interval ham to'rtta teng segmentga bo'lingan. Ushbu funktsiyaning uch nuqtadagi qiymatlari oldingi bosqichda aniqlanganligi sababli, keyin ikki nuqtada maqsad funktsiyasini hisoblash kerak bo'ladi.

Oltin nisbat usuli

N ning muhim qiymatlari uchun xn va xn-1 kabi nuqtalarning koordinatalari 1 - r ga yaqin, 0,3820 va r ≈ 0,6180 ga teng. Ushbu qadriyatlardan surish kerakli optimal strategiyaga juda yaqin.

Agar F(0,3820) > F(0,6180) deb faraz qilsak, u holda oraliq chiziladi. Biroq, 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1 bo'lganligi sababli, bu nuqtada F allaqachon ma'lum. Shunday qilib, har bir bosqichda, 2-dan boshlab, faqat bitta maqsad funktsiyasini hisoblash kerak bo'ladi va har bir qadam ko'rib chiqilayotgan intervalning uzunligini 0,6180 marta qisqartiradi.

Fibonachchi qidiruvidan farqli o'laroq, ichida bu usul qidiruvni boshlashdan oldin n raqamini tuzatishga hojat yo'q.

Bo'limning "oltin qismi" (a; b) - bu uning uzunligi r ning katta qismiga (a; c) nisbati katta qismi r ning kichik qismiga nisbati bilan bir xil bo'lgan qismdir, ya'ni. , (a; c) dan (c; b). r yuqoridagi formula bilan aniqlanishini taxmin qilish qiyin emas. Shunday qilib, muhim n uchun, Fibonachchi usuli bunga kiradi.

Bosqichni ikki baravar oshirish usuli

Mohiyat - maqsad funktsiyasining pasayish yo'nalishini izlash, harakat qilish bu yo'nalishda asta-sekin o'sib borayotgan qadam bilan muvaffaqiyatli qidiruv bo'lsa.

Birinchidan, biz F(M) funksiyaning M0 boshlang'ich koordinatasini, minimal qadam qiymati h0 va qidiruv yo'nalishini aniqlaymiz. Keyin funksiyani M0 nuqtada aniqlaymiz. Keyinchalik, biz qadam qo'yamiz va shu nuqtada ushbu funktsiyaning qiymatini topamiz.

Agar funktsiya oldingi bosqichda bo'lgan qiymatdan kichik bo'lsa, keyingi qadam avval uni 2 marta oshirib, xuddi shu yo'nalishda amalga oshirilishi kerak. Agar uning qiymati avvalgisidan kattaroq bo'lsa, qidiruv yo'nalishini o'zgartirishingiz kerak va keyin h0 qadamlari bilan tanlangan yo'nalishda harakat qilishni boshlashingiz kerak. Taqdim etilgan algoritmni o'zgartirish mumkin.

Ko'p o'lchovli optimallashtirish usullari

Yuqorida qayd etilgan nol tartibli usulda minimallashtirilgan funksiyaning hosilalari hisobga olinmaydi, shuning uchun hosilalarni hisoblashda qiyinchiliklar yuzaga kelsa, ulardan foydalanish samarali bo'lishi mumkin.

1-tartibli usullar guruhi gradient usullari deb ham ataladi, chunki qidirish yo'nalishini o'rnatish uchun berilgan funktsiyaning gradienti - vektordan foydalaniladi, uning komponentlari mos optimallashtirilgan parametrlarga nisbatan minimallashtirilgan funktsiyaning qisman hosilalari hisoblanadi. .

2-tartibli usullar guruhida 2 ta hosila qo'llaniladi (ularni hisoblashda qiyinchiliklar tufayli ulardan foydalanish ancha cheklangan).

Cheklanmagan optimallashtirish usullari ro'yxati

Ko'p o'lchovli qidiruvdan lotinlardan foydalanmasdan foydalanganda, cheklanmagan optimallashtirish usullari quyidagilardan iborat:

  • Hook and Jeeves (2 turdagi qidiruvni amalga oshirish - naqshga asoslangan va qidiruv);
  • to'g'ri simpleks orqali minimallashtirish (har bir alohida iteratsiyada simpleksning tepalarida uning qiymatlarini taqqoslash orqali mos keladigan funktsiyaning minimal nuqtasini qidirish);
  • siklik koordinata tushishi (koordinata vektorlaridan mos yozuvlar nuqtasi sifatida foydalanish);
  • Rosenbrock (bir o'lchovli minimallashtirishdan foydalanishga asoslangan);
  • deformatsiyalangan simpleks yordamida minimallashtirish (muntazam simpleks yordamida minimallashtirish usulini o'zgartirish: siqish va cho'zish protsedurasini qo'shish).

Ko'p o'lchovli qidiruv jarayonida hosilalardan foydalanish sharoitida eng keskin tushish usuli ajralib turadi (bir nechta o'zgaruvchilar bilan differentsiallanadigan funktsiyani minimallashtirishning eng asosiy protsedurasi).

Konjugat yo'nalishlarini ishlatadigan boshqa usullar ham mavjud (Davidon-Fletcher-Pauell usuli). Uning mohiyati qidiruv yo'nalishlarini Dj*grad(f(y)) sifatida ko'rsatishdir.

Matematik optimallashtirish usullarining tasnifi

An'anaviy ravishda, funktsiyalar (maqsad) o'lchamiga asoslanib, ular:

  • 1 o'zgaruvchi bilan;
  • ko'p o'lchovli.

Funktsiyaga (chiziqli yoki chiziqli bo'lmagan) qarab, masalani hal qilish uchun ekstremumni topishga qaratilgan ko'plab matematik usullar mavjud.

Hosilalarni qo'llash mezoniga ko'ra, matematik optimallashtirish usullari quyidagilarga bo'linadi:

  • maqsad funksiyaning 1 hosilasini hisoblash usullari;
  • ko'p o'lchovli (1-hosil-vektorli miqdor-gradient).

Hisoblash samaradorligiga qarab, quyidagilar mavjud:

  • ekstremumni tez hisoblash usullari;
  • soddalashtirilgan hisoblash.

Bu ko'rib chiqilayotgan usullarning shartli tasnifi.

Biznes jarayonlarini optimallashtirish

Bu erda hal qilinayotgan muammolarga qarab turli usullardan foydalanish mumkin. Biznes jarayonlarini optimallashtirishning quyidagi usullarini ajratib ko'rsatish odatiy holdir:

  • istisnolar (mavjud jarayon darajasini pasaytirish, shovqin va kiruvchi nazorat sabablarini bartaraf etish, transport yo'nalishlarini qisqartirish);
  • soddalashtirish (buyurtmani qayta ishlashni osonlashtirish, mahsulot strukturasining murakkabligini kamaytirish, ishlarni taqsimlash);
  • standartlashtirish (foydalanish maxsus dasturlar, usullar, texnologiyalar va boshqalar);
  • tezlashtirish (parallel muhandislik, rag'batlantirish, prototiplarni operatsion loyihalash, avtomatlashtirish);
  • o'zgarish (xom ashyo, texnologiya, ish usullari, xodimlar soni, ish tizimlari, buyurtma hajmi, qayta ishlash tartib-qoidalarining o'zgarishi);
  • o'zaro hamkorlikni ta'minlash (tashkiliy bo'linmalar, xodimlar, ish tizimiga nisbatan);
  • tanlash va kiritish (zarur jarayonlar, tarkibiy qismlarga nisbatan).

Soliqlarni optimallashtirish: usullar

Rossiya qonunchiligi soliq to'lovchiga soliqlarni kamaytirish uchun juda boy imkoniyatlarni taqdim etadi, shuning uchun ularni minimallashtirishga qaratilgan bunday usullarni umumiy (klassik) va maxsus deb ajratish odatiy holdir.

Soliqlarni optimallashtirishning umumiy usullari quyidagilardan iborat:

  • kompaniyaning hisob siyosatini maksimal darajada ishlab chiqish mumkin bo'lgan dastur taqdim etilgan Rossiya qonunchiligi imkoniyatlar (IBPni hisobdan chiqarish tartibi, tovarlarni sotishdan tushgan daromadni hisoblash usulini tanlash va boshqalar);
  • shartnoma orqali optimallashtirish (imtiyozli bitimlar tuzish, so'z birikmalaridan aniq va malakali foydalanish va boshqalar);
  • har xil turdagi imtiyozlar va soliq imtiyozlarini qo'llash.

Ikkinchi guruh usullari ham barcha kompaniyalar tomonidan qo'llanilishi mumkin, ammo ular hali ham juda tor dastur doirasiga ega. Soliqlarni optimallashtirishning maxsus usullari quyidagilardan iborat:

  • munosabatlarni almashtirish (og'ir soliqqa tortishni o'z ichiga olgan operatsiya boshqasiga almashtiriladi, bu shunga o'xshash maqsadga erishish imkonini beradi, lekin ayni paytda imtiyozli soliq rejimidan foydalanish).
  • munosabatlarning bo'linishi (biznes bitimining faqat bir qismini almashtirish);
  • soliq to'lashni kechiktirish (soliq solish ob'ekti paydo bo'lish vaqtini boshqa kalendar davriga ko'chirish);
  • soliq solish ob'ektini to'g'ridan-to'g'ri kamaytirish (asosiy soliqqa tortiladigan ko'plab operatsiyalardan yoki mulkka salbiy ta'sir ko'rsatmasdan qutulish iqtisodiy faoliyat kompaniyalar).


mob_info