У математичній оптимізації допустима область, допустима множина, простір пошуку чи простір розв'язків - це сукупність усіх можливих точок (наборів значень змінних вибору) проблеми оптимізації, які задовольняють обмеження проблеми, потенційно включаючи нерівності, рівності та цілі обмеження. Це початковий набір кандидатських рішень проблеми до того, як сукупність кандидатів була звужена.
Наприклад, розглянемо проблему
- Мінімізуйте
відносно змінних і
за умови
і
Тут допустимою множиною є сукупність пар ( x, y ), у яких значення x становить щонайменше 1 і щонайбільше 10, а значення y - принаймні 5 і не більше 12. Зауважимо, що допустима множина задачі є окремою від цільової функції, яка визначає критерій, який слід оптимізувати, і який у наведеному вище прикладі є
У багатьох проблемах допустима множина відображає обмеження, що одна чи кілька змінних повинні бути негативними. У чистих цілих задачах програмування можливою множиною є набір цілих чисел (або їх деякий підмножина). У задачах лінійного програмування можливою множиною є опуклий багатогранник : область у багатовимірному просторі, межі якої утворені гіперпланами та кути яких є вершинами .
Задоволення обмеженням - це процес пошуку точки у допустимому регіоні.
Випуклий здійсненний набір
Опукла допустима множина - це та, у якій відрізок лінії, що з'єднує будь-які дві допустимі точки, проходить лише через інші допустимі точки, а не через будь-які точки поза можливою множиною. Випуклі допустимі множини виникають у багатьох видах задач, включаючи проблеми лінійного програмування, і вони представляють особливий інтерес, оскільки, якщо проблема має опуклу цільову функцію, яку потрібно максимізувати, її взагалі буде легше вирішити за наявності опуклої допустимої множини і будь-який локальний оптимум також будуть глобальним оптимумом.
Відсутність допустимої множини
Якщо обмеження проблеми оптимізації взаємно суперечать один одному, немає точок, які б задовольняли всі обмеження, то, таким чином, допустимою множиною є нульова множина. У цьому випадку проблема не має вирішення і, як кажуть, є нерозв'язною.
Обмежені та необмежені можливі набори
Можливі набори можуть бути обмеженими або необмеженими . Наприклад, здійсненний набір, визначений набором обмежень { x ≥ 0, y ≥ 0}, не є обмеженим, оскільки в деяких напрямках немає меж того, як далеко можна пройти і все-таки опинитися в здійсненій області. Навпаки, здійснене безліч, утворене набором обмежень { x ≥ 0, y ≥ 0, x + 2 y ≤ 4}, обмежене тому, що ступінь руху в будь-якому напрямку обмежена обмеженнями.
У задачах лінійного програмування з n змінними необхідною, але недостатньою умовою обмеження можливого набору є те, щоб число обмежень було принаймні n + 1 (як показано на прикладі вище).
Якщо можливий набір без обмежень, то може бути або не бути оптимальним, залежно від специфіки цільової функції. Наприклад, якщо здійсненна область визначена набором обмежень { x ≥ 0, y ≥ 0}, то проблема максимізації x + y не має оптимуму, оскільки будь-яке кандидатське рішення можна покращити шляхом збільшення x або y ; але якщо проблема полягає в мінімізації x + y, то існує оптимум (конкретно, при ( x, y ) = (0, 0)).
Розв'язок кандидата
В оптимізації та інших галузях математики та в алгоритмах пошуку (тема з інформатики ) кандидатське рішення є членом набору можливих рішень у реальній області даної проблеми. Кандидатське рішення не повинно бути ймовірним або розумним рішенням проблеми — воно просто в наборі, що задовольняє всім обмеженням ; тобто це в наборі здійсненних рішень . Алгоритми для вирішення різних типів завдань оптимізації часто звужують набір кандидатських рішень аж до підмножини можливих рішень, точки яких залишаються як кандидатські рішення, тоді як інші можливі рішення відтепер виключаються як кандидати.
Простір усіх кандидатських рішень, перш ніж будь-які можливі точки виключені, називається можливою областю, можливим набором, простором пошуку або простором рішення. Це сукупність усіх можливих рішень, які задовольняють обмеження проблеми. Задоволення обмеженням - це процес пошуку точки в здійсненому наборі.
Генетичний алгоритм
Що стосується генетичного алгоритму, то кандидатурними рішеннями є люди в популяції, котра розвивається за алгоритмом.
Обчислення
У підрахунку оптимального рішення шукають за допомогою першого тесту на похідну : перша похідна функції, що оптимізується, прирівнюється до нуля, а будь-які значення змінної (-ів) вибору, що задовольняють цьому рівнянню, розглядаються як кандидатські рішення (тоді як ті, що не виключаються як кандидати). Існує кілька способів, за якими рішення кандидата не може бути фактичним рішенням. По-перше, він може дати мінімум, коли домагається максимуму (або навпаки), по-друге, він може дати ні мінімум, ні максимум, а скоріше сідлову точку або перегин, при якій тимчасова пауза в місцевому підйомі або відбувається падіння функції. Такі рішення кандидата можуть бути виключені за допомогою другого тесту на похідні, задоволення якого достатньо, щоб рішення кандидата було принаймні локально оптимальним. По-третє, кандидатом рішення може бути локальний оптимум, але не глобальний оптимум .
При прийомі антидеривативів одночленів форми можливим рішенням, що використовує квадратурну формулу Кавальєра, було б Це рішення кандидата насправді правильне, за винятком випадків, коли
Лінійне програмування
У симплексному способі вирішення задач лінійного програмування, вершина можливого політопу вибирається в якості вихідного рішення кандидата і перевіряється на оптимальність; якщо вона відхилена як оптимальна, сусідня вершина розглядається як наступне рішення кандидата. Цей процес продовжується до тих пір, поки не знайдеться оптимальне рішення кандидата.
Список літератури
- Beavis, Brian; Dobbs, Ian (1990). . New York: Cambridge University Press. с. 32. ISBN . Архів оригіналу за 1 липня 2019. Процитовано 24 грудня 2019.
- Whitley, Darrell (1994). (PDF). Statistics and Computing. 4 (2): 65—85. doi:10.1007/BF00175354. Архів оригіналу (PDF) за 17 квітня 2012. Процитовано 24 грудня 2019.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U matematichnij optimizaciyi dopustima oblast dopustima mnozhina prostir poshuku chi prostir rozv yazkiv ce sukupnist usih mozhlivih tochok naboriv znachen zminnih viboru problemi optimizaciyi yaki zadovolnyayut obmezhennya problemi potencijno vklyuchayuchi nerivnosti rivnosti ta cili obmezhennya Ce pochatkovij nabir kandidatskih rishen problemi do togo yak sukupnist kandidativ bula zvuzhena Problema z p yatma linijnimi obmezhennyami sinogo koloru vklyuchayuchi obmezhennya negativu Za vidsutnosti cilih obmezhen mozhlivoyu mnozhinoyu ye vsya oblast obmezhena sinim kolorom ale pri cilih obmezhennyah ce nabir chervonih krapok Zakrita mozhliva oblast zadachi linijnogo programuvannya z troma zminnimi ce opuklij bagatogrannik Napriklad rozglyanemo problemu Minimizujte x 2 y 4 displaystyle x 2 y 4 vidnosno zminnih x displaystyle x i y displaystyle y za umovi 1 x 10 displaystyle 1 leq x leq 10 i 5 y 12 displaystyle 5 leq y leq 12 Tut dopustimoyu mnozhinoyu ye sukupnist par x y u yakih znachennya x stanovit shonajmenshe 1 i shonajbilshe 10 a znachennya y prinajmni 5 i ne bilshe 12 Zauvazhimo sho dopustima mnozhina zadachi ye okremoyu vid cilovoyi funkciyi yaka viznachaye kriterij yakij slid optimizuvati i yakij u navedenomu vishe prikladi ye x 2 y 4 displaystyle x 2 y 4 U bagatoh problemah dopustima mnozhina vidobrazhaye obmezhennya sho odna chi kilka zminnih povinni buti negativnimi U chistih cilih zadachah programuvannya mozhlivoyu mnozhinoyu ye nabir cilih chisel abo yih deyakij pidmnozhina U zadachah linijnogo programuvannya mozhlivoyu mnozhinoyu ye opuklij bagatogrannik oblast u bagatovimirnomu prostori mezhi yakoyi utvoreni giperplanami ta kuti yakih ye vershinami Zadovolennya obmezhennyam ce proces poshuku tochki u dopustimomu regioni Vipuklij zdijsnennij nabirU zadachi linijnogo programuvannya ryad linijnih obmezhen stvoryuye opuklu mozhlivu oblast mozhlivih znachen dlya cih zminnih U dvo zminnomu vipadku cya oblast maye formu opuklogo prostogo bagatokutnika Opukla dopustima mnozhina ce ta u yakij vidrizok liniyi sho z yednuye bud yaki dvi dopustimi tochki prohodit lishe cherez inshi dopustimi tochki a ne cherez bud yaki tochki poza mozhlivoyu mnozhinoyu Vipukli dopustimi mnozhini vinikayut u bagatoh vidah zadach vklyuchayuchi problemi linijnogo programuvannya i voni predstavlyayut osoblivij interes oskilki yaksho problema maye opuklu cilovu funkciyu yaku potribno maksimizuvati yiyi vzagali bude legshe virishiti za nayavnosti opukloyi dopustimoyi mnozhini i bud yakij lokalnij optimum takozh budut globalnim optimumom Vidsutnist dopustimoyi mnozhiniYaksho obmezhennya problemi optimizaciyi vzayemno superechat odin odnomu nemaye tochok yaki b zadovolnyali vsi obmezhennya to takim chinom dopustimoyu mnozhinoyu ye nulova mnozhina U comu vipadku problema ne maye virishennya i yak kazhut ye nerozv yaznoyu Obmezheni ta neobmezheni mozhlivi naboriObmezhena dopustima mnozhina vgori ta neobmezhena dopustima mnozhina znizu Mnozhina vnizu prodovzhuyetsya bezkinechno vpravo Mozhlivi nabori mozhut buti obmezhenimi abo neobmezhenimi Napriklad zdijsnennij nabir viznachenij naborom obmezhen x 0 y 0 ne ye obmezhenim oskilki v deyakih napryamkah nemaye mezh togo yak daleko mozhna projti i vse taki opinitisya v zdijsnenij oblasti Navpaki zdijsnene bezlich utvorene naborom obmezhen x 0 y 0 x 2 y 4 obmezhene tomu sho stupin ruhu v bud yakomu napryamku obmezhena obmezhennyami U zadachah linijnogo programuvannya z n zminnimi neobhidnoyu ale nedostatnoyu umovoyu obmezhennya mozhlivogo naboru ye te shob chislo obmezhen bulo prinajmni n 1 yak pokazano na prikladi vishe Yaksho mozhlivij nabir bez obmezhen to mozhe buti abo ne buti optimalnim zalezhno vid specifiki cilovoyi funkciyi Napriklad yaksho zdijsnenna oblast viznachena naborom obmezhen x 0 y 0 to problema maksimizaciyi x y ne maye optimumu oskilki bud yake kandidatske rishennya mozhna pokrashiti shlyahom zbilshennya x abo y ale yaksho problema polyagaye v minimizaciyi x y to isnuye optimum konkretno pri x y 0 0 Rozv yazok kandidataV optimizaciyi ta inshih galuzyah matematiki ta v algoritmah poshuku tema z informatiki kandidatske rishennya ye chlenom naboru mozhlivih rishen u realnij oblasti danoyi problemi Kandidatske rishennya ne povinno buti jmovirnim abo rozumnim rishennyam problemi vono prosto v nabori sho zadovolnyaye vsim obmezhennyam tobto ce v nabori zdijsnennih rishen Algoritmi dlya virishennya riznih tipiv zavdan optimizaciyi chasto zvuzhuyut nabir kandidatskih rishen azh do pidmnozhini mozhlivih rishen tochki yakih zalishayutsya yak kandidatski rishennya todi yak inshi mozhlivi rishennya vidteper viklyuchayutsya yak kandidati Prostir usih kandidatskih rishen persh nizh bud yaki mozhlivi tochki viklyucheni nazivayetsya mozhlivoyu oblastyu mozhlivim naborom prostorom poshuku abo prostorom rishennya Ce sukupnist usih mozhlivih rishen yaki zadovolnyayut obmezhennya problemi Zadovolennya obmezhennyam ce proces poshuku tochki v zdijsnenomu nabori Genetichnij algoritm Sho stosuyetsya genetichnogo algoritmu to kandidaturnimi rishennyami ye lyudi v populyaciyi kotra rozvivayetsya za algoritmom Obchislennya U pidrahunku optimalnogo rishennya shukayut za dopomogoyu pershogo testu na pohidnu persha pohidna funkciyi sho optimizuyetsya pririvnyuyetsya do nulya a bud yaki znachennya zminnoyi iv viboru sho zadovolnyayut comu rivnyannyu rozglyadayutsya yak kandidatski rishennya todi yak ti sho ne viklyuchayutsya yak kandidati Isnuye kilka sposobiv za yakimi rishennya kandidata ne mozhe buti faktichnim rishennyam Po pershe vin mozhe dati minimum koli domagayetsya maksimumu abo navpaki po druge vin mozhe dati ni minimum ni maksimum a skorishe sidlovu tochku abo peregin pri yakij timchasova pauza v miscevomu pidjomi abo vidbuvayetsya padinnya funkciyi Taki rishennya kandidata mozhut buti viklyucheni za dopomogoyu drugogo testu na pohidni zadovolennya yakogo dostatno shob rishennya kandidata bulo prinajmni lokalno optimalnim Po tretye kandidatom rishennya mozhe buti lokalnij optimum ale ne globalnij optimum Pri prijomi antiderivativiv odnochleniv formi x n displaystyle x n mozhlivim rishennyam sho vikoristovuye kvadraturnu formulu Kavalyera bulo b 1 n 1 x n 1 C displaystyle tfrac 1 n 1 x n 1 C Ce rishennya kandidata naspravdi pravilne za vinyatkom vipadkiv koli n 1 displaystyle n 1 Linijne programuvannya Seriya obmezhen linijnogo programuvannya na dvi zminni stvoryuye oblast mozhlivih znachen dlya cih zminnih Rozv yazuvani dvoznachni zadachi matimut dopistimu mnozhinu u formi opuklogo prostogo mnogokutnika yaksho vin obmezhenij V algoritmi yakij testuye mozhlivi tochki poslidovno kozhna testovana tochka v svoyu chergu ye rishennyam kandidata U simpleksnomu sposobi virishennya zadach linijnogo programuvannya vershina mozhlivogo politopu vibirayetsya v yakosti vihidnogo rishennya kandidata i pereviryayetsya na optimalnist yaksho vona vidhilena yak optimalna susidnya vershina rozglyadayetsya yak nastupne rishennya kandidata Cej proces prodovzhuyetsya do tih pir poki ne znajdetsya optimalne rishennya kandidata Spisok literaturiBeavis Brian Dobbs Ian 1990 New York Cambridge University Press s 32 ISBN 0 521 33605 8 Arhiv originalu za 1 lipnya 2019 Procitovano 24 grudnya 2019 Whitley Darrell 1994 PDF Statistics and Computing 4 2 65 85 doi 10 1007 BF00175354 Arhiv originalu PDF za 17 kvitnya 2012 Procitovano 24 grudnya 2019