Допустимий регіон

Проблема з п'ятьма лінійними обмеженнями (синього кольору, включаючи обмеження негативу). За відсутності цілих обмежень можливою множиною є вся область, обмежена синім кольором, але при цілих обмеженнях це набір червоних крапок.

Закрита можлива область задачі лінійного програмування з трьома змінними - це опуклий багатогранник .

У математичній оптимізації допустима область, допустима множина, простір пошуку чи простір розв'язків - це сукупність усіх можливих точок (наборів значень змінних вибору) проблеми оптимізації, які задовольняють обмеження проблеми, потенційно включаючи нерівності, рівності та цілі обмеження. Це початковий набір кандидатських рішень проблеми до того, як сукупність кандидатів була звужена.

Наприклад, розглянемо проблему

Мінімізуйте $x^{2}+y^{4}$

відносно змінних $x$ і $y,$

за умови

$1\leq x\leq 10$

і

$5\leq y\leq 12.\,$

Тут допустимою множиною є сукупність пар ( x, y ), у яких значення x становить щонайменше 1 і щонайбільше 10, а значення y - принаймні 5 і не більше 12. Зауважимо, що допустима множина задачі є окремою від цільової функції, яка визначає критерій, який слід оптимізувати, і який у наведеному вище прикладі є $x^{2}+y^{4}.$

У багатьох проблемах допустима множина відображає обмеження, що одна чи кілька змінних повинні бути негативними. У чистих цілих задачах програмування можливою множиною є набір цілих чисел (або їх деякий підмножина). У задачах лінійного програмування можливою множиною є опуклий багатогранник : область у багатовимірному просторі, межі якої утворені гіперпланами та кути яких є вершинами .

Задоволення обмеженням - це процес пошуку точки у допустимому регіоні.

Випуклий здійсненний набір

У задачі лінійного програмування ряд лінійних обмежень створює опуклу можливу область можливих значень для цих змінних. У дво-змінному випадку ця область має форму опуклого простого багатокутника .

Опукла допустима множина - це та, у якій відрізок лінії, що з'єднує будь-які дві допустимі точки, проходить лише через інші допустимі точки, а не через будь-які точки поза можливою множиною. Випуклі допустимі множини виникають у багатьох видах задач, включаючи проблеми лінійного програмування, і вони представляють особливий інтерес, оскільки, якщо проблема має опуклу цільову функцію, яку потрібно максимізувати, її взагалі буде легше вирішити за наявності опуклої допустимої множини і будь-який локальний оптимум також будуть глобальним оптимумом.

Відсутність допустимої множини

Якщо обмеження проблеми оптимізації взаємно суперечать один одному, немає точок, які б задовольняли всі обмеження, то, таким чином, допустимою множиною є нульова множина. У цьому випадку проблема не має вирішення і, як кажуть, є нерозв'язною.

Обмежені та необмежені можливі набори

Обмежена допустима множина (вгорі) та необмежена допустима множина (знизу). Множина внизу продовжується безкінечно вправо.

Можливі набори можуть бути обмеженими або необмеженими . Наприклад, здійсненний набір, визначений набором обмежень { 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)).

Розв'язок кандидата

В оптимізації та інших галузях математики та в алгоритмах пошуку (тема з інформатики ) кандидатське рішення є членом набору можливих рішень у реальній області даної проблеми.   Кандидатське рішення не повинно бути ймовірним або розумним рішенням проблеми — воно просто в наборі, що задовольняє всім обмеженням ; тобто це в наборі здійсненних рішень . Алгоритми для вирішення різних типів завдань оптимізації часто звужують набір кандидатських рішень аж до підмножини можливих рішень, точки яких залишаються як кандидатські рішення, тоді як інші можливі рішення відтепер виключаються як кандидати.

Простір усіх кандидатських рішень, перш ніж будь-які можливі точки виключені, називається можливою областю, можливим набором, простором пошуку або простором рішення.   Це сукупність усіх можливих рішень, які задовольняють обмеження проблеми. Задоволення обмеженням - це процес пошуку точки в здійсненому наборі.

Генетичний алгоритм

Що стосується генетичного алгоритму, то кандидатурними рішеннями є люди в популяції, котра розвивається за алгоритмом.

Обчислення

У підрахунку оптимального рішення шукають за допомогою першого тесту на похідну : перша похідна функції, що оптимізується, прирівнюється до нуля, а будь-які значення змінної (-ів) вибору, що задовольняють цьому рівнянню, розглядаються як кандидатські рішення (тоді як ті, що не виключаються як кандидати). Існує кілька способів, за якими рішення кандидата не може бути фактичним рішенням. По-перше, він може дати мінімум, коли домагається максимуму (або навпаки), по-друге, він може дати ні мінімум, ні максимум, а скоріше сідлову точку або перегин, при якій тимчасова пауза в місцевому підйомі або відбувається падіння функції. Такі рішення кандидата можуть бути виключені за допомогою другого тесту на похідні, задоволення якого достатньо, щоб рішення кандидата було принаймні локально оптимальним. По-третє, кандидатом рішення може бути локальний оптимум, але не глобальний оптимум .

При прийомі антидеривативів одночленів форми $x^{n},$ можливим рішенням, що використовує квадратурну формулу Кавальєра, було б ${\tfrac {1}{n+1}}x^{n+1}+C.$ Це рішення кандидата насправді правильне, за винятком випадків, коли $n=-1.$

Лінійне програмування

Серія обмежень лінійного програмування на дві змінні створює область можливих значень для цих змінних. Розв’язувані двозначні задачі матимуть допистиму множину у формі опуклого простого многокутника, якщо він обмежений. В алгоритмі, який тестує можливі точки послідовно, кожна тестована точка в свою чергу є рішенням кандидата.

У симплексному способі вирішення задач лінійного програмування, вершина можливого політопу вибирається в якості вихідного рішення кандидата і перевіряється на оптимальність; якщо вона відхилена як оптимальна, сусідня вершина розглядається як наступне рішення кандидата. Цей процес продовжується до тих пір, поки не знайдеться оптимальне рішення кандидата.