Задачі дослідження операцій

Задачі дослідження операцій поділяються на дві категорії: прямі і зворотні. Прямі задачівідповідають на питання: що буде, якщо в заданих умовах ми приймемо рішення х є Х? Зокрема, чому буде дорівнювати при даному рішенні х вибраний критерій оптимальності W? Для вирішення такої задачі будується математична модель, яка дозволяє виразити один або декілька критеріїв оптимальності через задані умови та елементи вирішення.

Зворотні задачі відповідають на питання: як вибрати рішення х для того, щоб критерій оптимальності W обернувся у максимум? Для простоти надалі ми говоритимемо про „максимум” критерію, не обумовлюючи кожного разу, що потрібно обернути його в мінімум. Напевно, другий випадок по відношенню до першого – це проста зміна знаку W.

Природно, прямі задачі простіші зворотних. Напевно також, що для вирішення зворотної задачі перш за все потрібно уміти вирішувати прямі. Для деяких типів операцій прямі задачі розв’язується настільки просто, що ним спеціально не займаються. Для інших типів операцій побудова математичних моделей і обчислення критеріїв оптимальності саме по собі далеко не тривіальне.

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

1) задані заздалегідь відомі умови виконання операції, котрі для стислості позначимо однією буквою a;

2) залежні від нас, керовані змінні, які утворюють у своїй сукупності рішення Х.

Помітимо, що перша група чинників містить і обмеження, які накладаються на рішення, тобто визначають сферу можливих рішень Х. Критерій оптимальності W залежить від обох груп чинників. Це ми запишемо таким виразом:

W=f(a,x),

яке називається цільовою функцією.

Вважаємо, що вид цієї залежності нам відомий, тобто пряма задача має рішення. Тоді зворотна задача формується таким чином: при заданому комплексі умов a знайти таке рішення х=х*, яке обертає критерій W у максимум. Цей максимум ми позначимо:

W*=max{f(a,x)},

x є Х.

Формула читається так: W* є максимальне значення цільової функції f(a,x), взяте по всіх рішеннях х, які належать безлічі можливих рішень Х. Ця задача належить до класу так званих „варіаційних задач”, добре розроблених у математиці. Найпростіші з них знайомі всім з курсу математичного аналізу. Щоб знайти максимум або мінімум (екстремум) функції багатьох змінних, треба продиференціювати її за всіма аргументами (у даному випадку – керованими змінними), прирівняти похідні до нуля і вирішити одержану систему рівнянь. Здавалося б, що простіше? А ось цей класичний метод у дослідженні операцій має вельми обмежене застосування. По-перше, коли аргументів багато, рішення системи управлінння часто виявляється не простішим, а складнішим, ніж безпосередній пошук екстремуму. По-друге, коли на елементи рішення накладені обмеження, екстремум часто досягається не в точці, де похідна дорівнює нулю, а десь у межах Х. По-третє, в деяких задачах функція взагалі не має похідних, коли задано лише для цілочисельних значень аргументів. Все це робить завдання пошуку екстремуму не таким простим, як здається з першого погляду.

Якщо число можливих варіантів рішення, які утворюють множину Х, невелике, то можна просто обчислити величину для кожного із них, порівняти між собою набуті і безпосередньо вказати один або декілька варіантів, для яких W досягає максимуму. Такий спосіб знаходження оптимального рішення називається „простим перебором”. Проте коли число можливих варіантів рішень, що утворюють множину Х, велике, пошук серед них оптимального простим перебором складний, а часто й практично неможливий. У цих випадках застосовують методи „направленого перебору”, володіючи тією загальною особливістю, що оптимальне рішення можна знайти рядом послідовних „спроб”, з яких кожна подальша наближає нас до оптимального варіанта. Метод пошуку екстремуму і пов‘язаного з ним оптимального рішення х повинен завжди вибиратися, виходячи з особливостей цільової функції f(a,x) і виду обмежень, які накладаються на рішення. Наприклад, якщо цільова функція лінійно залежить від керованих змінних, а обмеження, що накладаються на керовану змінну, мають вид лінійної рівності або нерівностей, то це класична задача лінійного програмування. Якщо функція f(a,x) опукла, застосовуються методи опуклого програмування з їх різновидом – квадратичним програмуванням. Якщо керовані змінні змінюються дискретно, то застосовують цілочисельне програмування. Нарешті існує цілий набір чисельних методів пошуку екстремумів, спеціально пристосованих для реалізації на ЕОМ. Деякі з них включають елемент „випадкового пошуку”, який для багатовимірних задач нерідко виявляється ефективнішим за впорядкований перебір.

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