У математичній оптимізації допустима область, допустима множина, простір пошуку чи простір розв'язків — це сукупність усіх можливих точок (наборів значень змінних вибору) задачі оптимізації, які задовольняють обмеження задачі, потенційно включаючи нерівності, рівності та цілі обмеження. Це початковий набір допустимих розв'язків задачі до того, як їх сукупність було звужено.
Наприклад, розглянемо задачу
Мінімізуйте
відносно змінних і
за умови
і
Тут допустимою множиною є сукупність пар (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)).
Допустимий розв'язок В оптимізації та інших галузях математики та в алгоритмах пошуку (тема з інформатики) допустимий розв'язок є членом набору можливих розв'язків у реальній області даної задачі. Допустимий розв'язок не повинен бути ймовірним або розумним розв'язком задачі — він просто в наборі, що задовольняє всі обмеження; тобто, в наборі здійсненних розв'язків. Алгоритми для розв'язання різних типів задач оптимізації часто звужують набір допустимих розв'язків аж до підмножини можливих розв'язків, точки яких залишаються як допустимі розв'язки, тоді як інші можливі розв'язки відтепер виключаються як допустимі.
Простір усіх допустимих розв'язків, перш ніж будь-які можливі точки виключені, називається можливою областю, можливим набором, простором пошуку або простором розв'язків. Це сукупність усіх можливих розв'язків, які задовольняють обмеження задачі. Задоволення обмежень — це процес пошуку точки в здійсненому наборі.
Генетичний алгоритм Що стосується генетичного алгоритму, то допустимими розв'язками є люди в популяції, котра розвивається за алгоритмом.
Обчислення У підрахунку оптимального розв'язку шукають за допомогою першого тесту на похідну : перша похідна функції, що оптимізується, прирівнюється до нуля, а будь-які значення змінної (-ів) вибору, що задовольняють цьому рівнянню, розглядаються як допустимі розв'язки (тоді як ті, що не виключаються як допустимі). Існує кілька способів, за якими допустимий розв'язок не може бути фактичним розв'язком. По-перше, він може дати мінімум, коли домагається максимуму (або навпаки), по-друге, він може дати ні мінімум, ні максимум, а скоріше сідлову точку або перегин, при якій тимчасова пауза в місцевому підйомі або відбувається падіння функції. Такі допустимі розв'язки можуть бути виключені за допомогою другого тесту на похідні, задоволення якого достатньо, щоб допустимий розв'язок був принаймні локально оптимальним. По-третє, допустимим розв'язком може бути локальний оптимум, але не глобальний оптимум.
При прийомі антидеривативів одночленів форми можливим розв'язком, що використовує квадратурну формулу Кавальєра, було б Цей допустимий розв'язок насправді правильний, за винятком випадків, коли
Лінійне програмування
У симплексному способі розв'язування задач лінійного програмування, вершина можливого політопа вибирається початковим допустимим розв'язком і перевіряється на оптимальність; якщо вона відхилена як оптимальна, сусідня вершина розглядається як наступний допустимий розв'язок. Цей процес продовжується, поки не знайдеться оптимальний допустимий розв'язок.
Примітки