СИСТЕМНИЙ АНАЛІЗ

2.4  Класифікація математичних моделей системного аналізу

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

Якщо елементи математичної моделі (2.1) не залежать від часу, тобто процес прийняття рішення зводиться до миттєвого акту вибору точки із заданої множини, то математична модель системного аналізу називається статичною. Інакше, коли прийняття рішення є багатоетапним (дискретним) або неперервним у часі процесом, то така модель називається динамічною. Приклади 2.1–2.4, 2.7 і 2.8 попереднього розділу відносяться до статичних, а приклади 2.5, 2.6 і 2.9 – до динамічних моделей. Моделі, що не містять випадкових величин і ймовірносних явищ називаються детермінованими (приклади 2.1, 2.2, 2.4, 2.5, 2.9), а якщо моделі характеризуються випадковими вели­чинами з ймовірносними оцінками, то вони називаються стохастичними (при­клади 2.3, 2.4, 2.6).

Залежно від кількості ОПР розрізняють моделі прийняття оптимальних рішень і математичні моделі в умовах протидії (ігрові моделі (n ≥ 2, де n – число елементів на множині N)). Ігрова модель (або гра) – це математична модель задачі прийняття рішення в умовах конфлікту, тобто в тих ситуаціях, коли має місце протистояння інтересів двох або більше сторін. У загальному випадку, залежно від характеру конфлікту розрізняють, антагоністичні (приклади 2.7, 1.8), неантагоністичні (безкоаліційні) і кооперативні ігри.

Якщо в моделях всі елементи лінійні (цільова функція та обмеження), то отримуємо моделі лінійного програмування (приклади 2.1 і 2.2), інакше отримуємо моделі нелінійного програмування (приклади 2.З і 2.4, якщо функції R_j і K_j – нелінійні). Якщо ж у моделях присутній фактор часу, то такі моделі називається моделями оптимального керування (приклад 2.5). Іноді такі моделі називають моделями динамічного програмування. Однак це не точна назва, оскільки динамічне програмування – це назва методу розв’язання задач оптимального керування.

У реальних випадках часто ОПР переслідує не одну, а декілька цілей. Математичні моделі <X; f₁, …, f_n; Σ>, що відповідають цьому, називаються моделями багатокритеріальної (векторної) оптимізації. Так, наприклад, у моделі (2.5) ОПР вибирає рішення х ∈ Х таким чином, щоб отримати як можна більші значення f₁(x), ..., f_n(x) критеріїв.

Є, також, і такі класи математичних моделей, що отримали свою назву, виходячи з їх призначення. Це системи масового обслуговування (приклад 2.6), задачі керування запасами (приклад 2.3), задачі мережного і календарного планування (приклад 2.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_i, а його цінність – 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 підприємств, кожне з яких буде виробляти один вид продукції.