РОЗДІЛ 2
ДОСЛІДЖЕННЯ ЗАДАЧІ РЕБЕРНОГО ПОКРИТТЯ ЗВИЧАЙНИХ ГРАФІВ З ВАГОВИМИ КРИТЕРІЯМИ
2.1. Змістовна постановка та математична модель задач про лізинг сільськогосподарської техніки та землекористування
Згідно із п.1.4 змістовна постановка задачі про лізинг сільськогосподарської техніки полягає у наступному. Деяка агрофірма, що формує портфель замовлень на техніку сільськогосподарського призначення, має інформацію про зацікавленість аграрних господарств у різних видах техніки. Кожному замовленню споживача ставиться у відповідність значення очікуваного прибутку від операції та значення коефіцієнта зношуваності техніки, який він може забезпечити. Необхідно скласти такий портфель замовлень, при якому сумарний очікуваний прибуток та сумарний показник збереження вартості техніки були б якомога більші. Математичну модель цієї задачі можна представити як задачу про реберне покриття зірками на зваженому двочастковому графі. При цьому вершини першої частки будуть відповідати замовленням господарств-орендарів, а вершини другої - одиницям техніки. Наявність ребра між парою вершин відповідає зацікавленості господарства у даній одиниці техніки, а вага ребра змістовно є економічним ефектом угоди. Критерієм якості покриття буде слугувати сумарна вага ребер, що входять до нього, тобто критерій виду MAXSUM.
Важливою для сільськогосподарського виробництва є також задача землекористування: деяке господарство володіє орними угіддями, розбитими на окремі дільниці. Напрямком діяльності господарства є вирощування рослинницької продукції. Для цього виникає задача розподілу культур по ділянках господарства (вважається що всі ділянки одного розміру). Математична модель даної задачі також може бути представлена на двочастковому графі, де вершини першої частки відповідають культурам, а вершини другої - ділянкам господарства. Можливість вирощування даної культури на даній ділянці відображається наявністю ребра між відповідними вершинами в графі. Кожному ребру графа приписана вага, що відображає економічний ефект вирощування культури на полі (це може бути, наприклад, врожайність в натуральному або грошовому представленні). На даний час є також важливим еколого-економічні показники. Наприклад, таким показником може бути зміна вмісту гумусу в орному шарі. Отже, для сформульованої вище задачі необхідно побудувати математичну модель в багатокритеріальній постановці.
Таким чином, математичні моделі розглянутих змістовних постановок задач можна представити у вигляді задачі про реберне покриття, де носієм є двочастковий (а в загальному випадку l- частковий, звичайний) граф, типовими підграфами виступають зірки (або, іноді, ланцюги), цільова функція в загальному вигляді має вид (1.1)-(1.3). Тому, подальші дослідження будуть присвячені вивченню властивостей саме таких задач та розробці для них ефективних алгоритмів.
Введемо необхідні означення та сформулюємо оптимізаційну, тобто 1-критеріальну постановку цих задач.
Задано носій - n-вершинний граф , у якому кожному ребру приписана цілочисельна вага .
Означення 2.1. Будемо називати t-вершинну зірку (ланцюг) [50] t-зіркою (t-ланцюгом), . Терміном "множина типів зірок (ланцюгів)" будемо називати упорядковану за зростанням підмножину натуральних чисел , . Для заданої пари G, Т (згідно п.1.1) множину всіх припустимих рішень (МПР) позначимо .
Цільова функція, яка визначена на МПР X, має вигляд MINSUM:
. (2.1)
Оптимізаційна задача реберного покриття графа зірками (ланцюгами) полягає в знаходженні оптимального розв'язку , тобто такого припустимого рішення, на якому значення ЦФ (2.1) досягає мінімуму: .
Як було зазначено, математичне моделювання реальних задач приводить, найчастіше, до багатокритеріальних математичних постановок. Ці задачі вимагають вибору і прийняття рішення з урахуванням багатьох критеріїв якості [18, 29, 32, 102, 124]. Останні, як правило, суперечливі і різнорідні в тому сенсі, що якість порівнюваних альтернатив неможливо адекватно висловити одним комплексним або інтегральним критерієм. Для таких задач поняття "оптимальне рішення" не є дієвим. В умовах багатокритеріальності виникає необхідність замість одного оптимуму шукати деяку множину альтернатив (МА).
Для векторної, тобто багатокритеріальної задачі якість припустимих рішень оцінюється векторною цільовою функцією
, (2.2)
де
, (2.3)
. (2.4)
Якщо кількість вагових критеріїв (2.3) задовольняє нерівності
, (2.5)
то, згідно [33], існують індивідуальні задачі, для яких максимальна потужність шуканого розв'язку, тобто потужність ПМА зростає з експоненційною швидкістю з ростом розмірності (n) задачі. Тобто задача покриття графа ланцюгами або зірками є важкорозв'язуваною.
У силу сказаного вище, є актуальною проблема знаходження й обґрунтування поліноміально розв'язуваних підкласів як 1-критериальних задач покриття графа зірками і ланцюгами, так і відповідних багатокритеріальних задач.
Позначимо задачі, що досліджуються в розділі 2, наступним чином:
- задача () - оптимізаційна (однокритеріальна) задача про реберне покриття звичайного графа з ЦФ (2.2) (ЦФ (2.4)), в якій множина типових підграфів складається із зірок заданого типу, а припустимим розв'язком є суграф , , у якого кожна компонента зв'язності є деякою t-зіркою, ізоморфною деякому типовому підграфу ;
- задача - двокритеріальна задача про реберне покриття звичайного графа з ВЦФ (2.2)-(2.4), в якій множина типових підграфів складається із зірок заданого типу, а припустимим розв'язком є суграф , , у якого кожна компонента зв'язності є деякою t-зіркою, ізоморфною деякому типовому підграфу ;
- задача () - оптимізаційна (однокритеріальна) задача про реберне покриття двочасткового графа , в якій множина типових підграфів складається із зірок заданого типу, а припустимим розв'язком є суграф , , у якого к