Розділи і класи задач дослідження операцій

Розділи і класи задач дослідження операцій можна класифікувати, виходячи з елементів загальної структури (1.1), підходячи до їх характеристик з різних точок зору. Тому одне тільки перерахування назв зайняло б кілька сторінок. Ми визначимо тут тільки найбільші класи задач. Почнемо з характеристики середовища (∑) прийняття рішення.

Якщо елементи математичної моделі (1.1) не залежать від часу, тобто процес прийняття рішення зводиться до миттєвого акту вибору точки із заданої множини, то задача ДО називається статичною. Інакше, коли прий-няття рішення є багатоетапним (дискретним) або неперервним (у часі) процесом, то задача ДО називається динамічною. Приклади 1.1-1.4, 1.7 і 1.8 відносяться до статичних, а приклади 1.5-1.6 і 1.9 – до динамічних задач. Задачі ДО, що не містять випадкових величин і ймовірносних явищ називаються детермінованими (приклади 1.1, 1.2, 1.4, 1.5, 1.9), задачі, що характеризуються випадковими величинами з імовірнісними оцінками –стохастичними (приклади 1.3, 1.4, 1.6), а задачі прийняття рішення в умовах невизначеності – конфліктними (приклади 1.7, 1.8).

Залежно від кількості ОПР в (1.1) розрізняють задачі оптимізації (1.2) і ігрові задачі (n ≥ 2, де n – число елементів на множині N).

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

Якщо в задачі оптимізації всі елементи лінійні (цільова функція та обмеження), то отримуємо задачі лінійного програмування (приклади 1.1, 1.2), інакше – задачі нелінійного програмування (приклад 1.З і 1.4, якщо функції R_j, і K_j нелінійні). Якщо в задачі оптимізації присутній фактор часу, то вона називається задачею оптимального керування (приклад 1.5). Іноді такі задачі називають задачами динамічного програмування. Однак ця неточна назва, оскільки динамічне програмування – це назва методу розв’язання задач оптимального керування.

Часто в ОПР є не одна, а кілька цілей. Математична модель

< X; f ₁,…, f_n; Σ > (1.5)

такої задачі називається задачею багатокритеріальної (векторної) оптимізації. У моделі (1.5) ОПР вибирає розв’язок х Î Х таким чином, щоб отримати якомога більші значення f₁ (x),..., f_n (x) критеріїв.

Є такі класи задач ДО, що отримали свою назву, виходячи з їх призначення: системи масового обслуговування (приклад 1.6), задачі керування запасами (приклад 1.3), задачі сіткового і календарного планування (приклад 1.9).

Для повноти сприйняття нижче наведемо ті «класичні» задачі ДО, що, завдяки їх типовості, зустрічаються в багатьох підручниках з математичного програмування. Деякі з них відносяться до початку виникнення теорії оптимізації. Приклади служать для ілюстрації деяких видів задач прийняття рішень і не претендують на реальність в останній інстанції, це навчальні задачі. Задачі і моделі, що становлять безпосеред­ній практичний інтерес, будуть докладнішими, глибокими і складними. Навчальні задачі – це перше наближення до реальних (практичних) задач, їх спрощений аналог. Керуючись матеріалами попередніх двох параграфів, читач може самостійно отримати їх математичні моделі.

Задача оптимального розкрою матеріалу. Фірма виготовляє виріб, що складається з р деталей (наприклад, комплект постільної білизни). Причому в один виріб ці деталі входять у кількостях k₁,…, k_r...З цією метою визначається розкрій m партій матеріалу. У i -ій партії є b_i одиниць матеріалу. Кожну одиницю матеріалу можна розкроїти на деталі n способами. Під час розкрою одиниці i -ої партії j -им способом виходить а_ijr деталей r -го виду. Потрібно скласти такий план розкрою матеріалів, щоб з них отримати максимальне число виробів.

Транспортна задача. Є n постачальників і m споживачів деякого однорідного продукту. Відомі випуск продукції кожного постачальника і потреби в ній кожного споживача, а також витрати на перевезення продукції від постачальників до споживачів.

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

Задача про призначення на роботу. Є n робіт і n виконавців. Вартість виконання роботи i виконавцем j дорівнює c_ij. Потрібно розподілити виконавців на роботи так, щоб мінімізувати витрати.

Задача про суміші (про раціон). З m видів вихідних матеріалів, кожний з яких складається з n компонентів, скласти суміш, у якій вміст компонентів повинен бути не менше b₁,..., b_n. Відомі ціни одиниці матеріалів: c₁... c_m і питома вага j -гo компонента в одиниці i -гo матеріалу. Треба скласти суміш, у якій витрати були б мінімальними.

Задача про рюкзак. Є n предметів у рюкзаку. Вага предмета i дорівнює p₁, а його цінність – c_і (i = l,…, n). Потрібно для заданої цінності вантажу вибрати сукупність предметів мінімальної ваги.

Задача про комівояжера. Є n міст і задана відстань c_ij між ними (i, j = = l...., n). Виїжджаючи з одного (вихідного) міста, комівояжер повинен побувати в усіх інших містах один раз і повернутися у вихідне місто. Треба визначити, у якому порядку слід об’їжджати міста, щоб сумарна пройдена відстань була найменшою.

Задача про верстати. На універсальному верстаті обробляються однакові партії з n деталей. Перехід від оброблення деталі i до оброблення деталі j вимагає переналагодження верстата, що займає c_ij часу. Потрібно визначити послідовність оброблення деталей, за якою загальний час переналагоджень верстата при обробленні партії деталей був би мінімальним.

Задача про розподіл капіталовкладень. Є n проектів, причому для кожного проекту i відомий очікуваний ефект γ_j від його реалізації і необхідна величина капіталовкладень g_j. Загальний обсяг капіталовкладень не може перевищувати заданої величини b. Потрібно визначити, які проекти необхідно реалізувати, щоб сумарний ефект був найбільшим.

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