Махно Михайло Федорович Моделі та методи розв’язання нечітких задач оптимального роз­поділу часового ресурсу : Махно Михаил Федорович Модели и методы решения нечетких задач оптимального распределения временного ресурса

Краткое описание

Махно Михайло Федорович, асистент кафедри сис­темного аналізу та теорії прийняття рішень Київського на­ціонального університету імені Тараса Шевченка: «Моделі та методи розв’язання нечітких задач оптимального роз­поділу часового ресурсу» (01.05.04 - системний аналіз і теорія оптимальних рішень). Спецрада Д 26.001.35 у Київ­ському національному університеті імені Тараса Шевченка

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ТАРАСА ШЕВЧЕНКА
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ТАРАСА ШЕВЧЕНКА
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Рукопис
МAХНО МИХАЙЛО ФЕДОРОВИЧ
УДК 519.874:519.852:519.816
ДИСЕРТАЦІЯ
МОДЕЛІ ТА МЕТОДИ РОЗВ’ЯЗАННЯ НЕЧІТКИХ ЗАДАЧ
ОПТИМАЛЬНОГО РОЗПОДІЛУ ЧАСОВОГО РЕСУРСУ
01.05.04 – системний аналіз і теорія оптимальних рішень
Подається на здобуття наукового ступеню кандидата технічних наук
Дисертація містить результати власних досліджень. Використання ідей,
результатів і текстів інших авторів мають посилання на відповідне джерело
___________________________
(підпис, ініціали та прізвище здобувача)
Науковий керівник Івохін Євген Вікторович, доктор фізико-математических
наук, професор
Київ  2017

З М І С Т
ВСТУП………………………………………………………………….……….. 11
РОЗДІЛ 1. ОСНОВНІ МАТЕМАТИЧНІ МОДЕЛІ ЧІТКИХ ТА НЕЧІТКИХ
ЗАДАЧ ОПТИМАЛЬНОГО ПЛАНУВАННЯ І РОЗПОДІЛУ РЕСУРСІВ….. 23
1.1. Чіткі задачі оптимального планування і розподілу ресурсів та їх
властивості…………………………………………………………. 24
1.1.1. Задача про рюкзак…………………………………………… 28
1.1.2. Задача складання розкладу…………………………………. 29
1.1.3. Задача про вибір заявок…………………………………….. 30
1.2. Загальна постановка нечітких задач лінійного програмування…... 31
1.2.1. Нечіткі величини та нечіткі числа.………………………… 31
1.2.2. Принцип формулювання нечітких задач лінійного
програмування………………………………………………… 34
1.2.3. Задачі лінійного програмування з нечіткими ресурсними
обмеженнями у правій частині………………………………. 39
1.2.4. Задачі лінійного програмування з нечіткими технологічними
коефіцієнтами………………………………………………… 42
1.3. Висновки по першому розділу……………………………………… 45
РОЗДІЛ 2. МОДЕЛІ ТА МЕТОДИ РОЗВ’ЯЗАННЯ ЧІТКИХ ЗАДАЧ ОПТИМАЛЬНОГО РОЗПОДІЛУ ЧАСОВОГО РЕСУРСУ ЯК ЗАДАЧ СКЛАДАННЯ
РОЗКЛАДУ………………………………………………………………………… 46
2.1. Задачі оптимального розподілу часового ресурсу як задачі теорії
складання розкладів………………………………………………….. 46
2.1.1. Класифікація задач теорії розкладів залежно від характеристик
машин, робіт, цільової функції……………………………….. 47
2.1.2. Математичні постановки оптимізаційних задач розподілу
часового ресурсу………………………………………………. 52
2.1.3. Формулювання загальної задачі складання розкладу в термінах
лінійного цілочисельного програмування…………………… 55
2.1.4. Задача складання розкладу виконання заданої кількості робіт
для однієї машини……………………………………………… 57
2.1.5. Формулювання задачі оптимальної рекомбінації робіт……… 60
2.2. Методи розв’язання задач оптимального розподілу часового ресурсу 62
2.2.1.Властивості методів розв’язання оптимізаційних задач……… 62
2.2.2. Застосування методу динамічного програмування для
розв’язування задач теорії розкладів…………………………. 65
2.2.3. Метод найменших відхилень розв’язання задачі розподілу
10
ресурсів……………………………………………………….. 69
2.2.4. Реалізація жадібного підходу до розв’язування задач розподілу
ресурсів…………………………………………………….…. 72
2.2.5. Застосування економічних стратегій для розв’язання задач
розподілу ресурсів…………………………………..………… 74
2.3. Висновки по другому розділу……………………………………….. 76
РОЗДІЛ 3. МОДЕЛІ ТА МЕТОДИ РОЗВ’ЯЗАННЯ НЕЧІТКИХ ЗАДАЧ
ОПТИМАЛЬНОГО РОЗПОДІЛУ ЧАСОВОГО РЕСУРСУ………………….… 77
3.1. Нечітка задача про рюкзак як засіб розподілу нечітко
визначеного часового ресурсу.………….………..………………….. 77
3.2. Задача складання розкладу з нечітко заданими інтервалами
налаштувань…………………...…………………………………….… 78
3.3. Задачі теорії розкладів з нечітким вимірюванням часу…………….. 81
3.3.1. Застосування структурованих нечітких чисел для опису
вимірювання відліку часу………………………………………. 83
3.3.2. Нечітка задача про рюкзак як засіб розподілу часового ресурсу
з нечітко заданими термінами виконання..………………….… 88
3.3.3. Гібридна модель динаміки процесу обробки сукупності завдань 90
3.4. Метод перетворення області допустимих розв’язків з урахуванням
близькості обмежень задачі…………………………………………… 99
3.5. Пошук розв’язків за наявності систем альтернативних обмежень… 107
3.6. Висновки по третьому розділу…………………………..……………. 110
РОЗДІЛ 4. ПРИКЛАДИ ПРАКТИЧНОГО РОЗВ’ЯЗУВАННЯ ЗАДАЧ
ОПТИМАЛЬНОГО РОЗПОДІЛУ ЧАСОВОГО РЕСУРСУ……..……………… 111
4.1. Розклад занять академічних груп і викладачів в межах аудиторного
фонду навчального закладу протягом типового тижня……………... 112
4.2. Моделювання динаміки розподілу часового ресурсу при проведенні
процесу тестування…………………….……………………………… 118
4.3. Комп’ютерна система для проведення дистанційного тестування… 122
4.4. Висновки по четвертому розділу……………………………………... 123
ВИСНОВКИ………………………………………………………………………. 124
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ…………………………………………. 126
Додаток А. Результати розрахунків розподілів часового ресурсу у випадку
нечітко заданих термінів виконання……………..……………………………… 133
Додаток Б. Результати моделювання динаміки розподілу часового ресурсу…. 135
Додаток В. Опис системи EdUni для проведення дистанційних тестувань…… 137
Додаток Г. Акти впровадження………………………………………………….. 146
ВСТУП
Актуальність теми. Одним з найважливіших класів систем управління є
клас систем, які складаються з великої кількості підсистем, що взаємодіють між
собою, інтереси яких не завжди узгоджуються або навіть можуть бути
суперечливими, а ефективність функціонування оцінюється за допомогою
сукупності якісних і кількісних показників. Розробка і практичне впровадження
методів найбільш ефективного управління організаційними системами
відносяться до наукових досліджень в області дослідження операцій.
Багато проблем оптимізації можна розглядати у вигляді задач лінійного
програмування (ЗЛП), де всі цільові функції і обмеження, що визначають
множину допустимих рішень, є лінійними. Розв’язок задачі оптимізації на
заданій множині допустимих рішень характеризується однозначною залежністю із значенням лінійної цільової функції і за наявності єдиного критерію
оптимальності легко може бути знайдено за допомогою різних методів [1].
Необхідно відзначити, що величезний внесок у розвиток сучасного математичного апарату і створення багатьох напрямів дослідження операцій внесли як
зарубіжні (Р.Белман, Г.Данциг, Г.Кун, Т.Сааті, А.Кофман, Р.Форд, та ін.), так і
вітчизняні (Л.В.Канторович, Б.В.Гнеденко, В.С.Михалевич, Ю.М.Ермол’єв,
Н.З.Шор та ін.) вчені.
Пошук розв’язків задач оптимізації суттєво залежить від природи
параметрів, присутніх в моделі. У багатьох випадках значення параметрів
можуть бути відомі частково, з деякою мірою точності або не можуть бути
чисельно формалізовані традиційними способами. В цьому випадку в
дослідженні операцій був розроблений підхід, що враховує різні ступені
задоволення отриманим рішенням. У ряді задач даний підхід забезпечує
кращий розв’язок, чим традиційна оптимізація [2].
Окремої уваги серед інших заслуговують оптимізаційні задачі лінійного
програмування, сформульовані з елементами неточності і невизначеності. До
них відносяться задачі нечіткого лінійного програмування (НЛП), параметри в
12
яких можуть бути описані кількісно тільки за допомогою нечітких множин.
Проблеми пошуку розв’язків нечітких задач лінійного програмування з
урахуванням величини функції приналежності нечітких параметрів моделі,
розробка гнучких і достатньо простих обчислювальних методів, що враховують
ступінь точності визначення параметрів, розглядаються, наприклад, у [2-5].
Необхідно звернути увагу на те, що формалізація неточностей в завданні
параметрів може бути проведена на основі підходів, запропонованих у теорії
нечітких числових множин. У цьому випадку модель параметризується таким
чином, щоб розв’язок задачі задовольняв бажаному рівню значень функції
належності. Така модель НЛП, як правило, є більш гнучкого по відношенню до
умов реальної задачі і простою в обчислювальному плані [6].
Першим і найбільш значущим стимулом до математичної формалізації
нечіткості вважається робота Задe [7]. Сучасний рівень розвитку його ідеї
включає численні спроби застосування теорії нечітких множин як інструмент
для адекватного математичного опису проблем формалізації неточності [8-11].
За останній період були подолані деякі проблеми формалізації реальних задач,
створені деякі важливі принципи в теорії нечітких множин та її застосувань.
Окремі результати, присвячені пошуку рішень нечітких задач оптимізації
можна знайти в [12,13]. Величезна увага приділяється розробці методів і
підходів для вирішення деяких спеціальних задач шляхом залучення так званих
«м'яких обчислень» [14].
Нечіткі методи активно застосовуються в задачах формування та підтримки прийняття рішень, зокрема багатоцільового (багатокритеріального) прийняття рішень та пошуку рішень в ієрархічних оптимізаційних задачах [6, 15-22].
Широка дослідницька робота, пов'язана з нечітким прийняттям рішень, включає також розробку додатків теорії нечітких множин в теорії управління і дослідженні операцій [4]. Деякі характерні результати приведені в [5, 8, 9, 10, 23].
Багато прикладних проблем пов'язано з розподілом обмежених ресурсів в
ієрархічних системах [24-30]. Це, наприклад, може бути задача збалансованого
розподілу навантаження в однорідній мережі [25], розподіл робіт для
13
паралельних комп'ютерів [26], розподіл ресурсів в процесі переговорів [27] і
т.д. Основна проблема при цьому полягає у формалізації проблеми у вигляді
багатокритеріальних багатоіндексних задач оптимізації [28-30]. В цьому
випадку вважається, що елементи процесу та їх відносини задовольняють
умовам обмеженості ресурсів, що впливає на об'єми ресурсів, які циркулюють
у системі. Прикладами таких задач розподіл навантаження на канали передачі
даних Internet-провайдерів [28], планування виробництва [30] та ін.
Задачі впорядковування робіт, що виконуються машинами, при
використанні деяких ресурсів є задачами теорії розкладів (ТР). Результати
розв’язання подібних задач мають вартісний характер або визначаються іншою
величиною. Дослідження задач ТР, а також методів і алгоритмів їх вирішення
дозволяє отримати оптимальні або близькі до оптимальних результати.
Теорії розкладів присвячені роботи зарубіжних і вітчизняних учених
Дж.Адамса, Р.Л.Грехема [31], Х.Фишера [32], Е.Г.Коффмана, Б.Гиффлера [33],
Дж. Томпсона, С.В.Севастьянова [34], Я.М.Шафранского та ін.
У ТР історично склалися два напрямки: один називається мережевим або
календарним плануванням (Project Scheduling (PS)) [31-34], другий - власне
теорія розкладів (Machine Scheduling (MS)) (див. pиc.1). На початковому етапі
досліджень вони суттєво розрізнялися у формулюваннях задач: у задачах
мережевого планування, як правило присутні ресурсні обмеження і не йдеться
мова про якісь машини; у теорії розкладів, навпаки, обов'язково є машини (що є
специфічним видом ресурсів), є роботи, що складаються, взагалі кажучи, з
декількох операцій (на відміну від робіт, що розглядаються в мережевому
плануванні), і, як правило, немає інших ресурсних обмежень, хоча можуть бути
присутніми досить складні обмеження специфічного вигляду. Проте, останнім
часом ці напрямки все більше зближуються один з іншим.
В результаті маємо загальний висновок: обидві області ТР вирішують
практично однe і тe ж коло задач, але при цьому користуються різними
моделями і різними методами розв’язання [34].
14
Рис.1. Основні класи задач теорії складання розкладів
Крім мережевого планування (PS) і теорії розкладів (MS), задачі на
складання розкладів розглядаються в таких галузях дослідження операцій як
складання тимчасових таблиць (Time tabling (TT)) і маршрутизація пакетів
(Packet routing (PR)) [31-34]. До задач маршрутизації пакетів (PR) відносяться
задачі складання розкладу занять у навчальному закладі, тижневих (циклічних)
розкладів польотів літаків, тижневих або добових розкладів руху залізничного
транспорту і т.п. Для всіх цих задач характерним є те, що інтервал часу, в
рамках якого слід розподілити заданий набір робіт, відомий наперед. Таким
чином, тут не розглядаються завдання на швидкодію (тобто на мінімум
тривалості реалізації розкладу), а використовуються інші критерії оцінки якості
розкладу, що будується.
Маршрутизація пакетів (PR) виникла у зв'язку з необхідністю в
оптимізації потоків інформації, що курсують в мережах зв'язку (у локальних
мережах або в глобальній мережі Інтернет). Для задач з цієї області також
характерні специфічні критерії оптимальності, що не розглядаються в рамках
класичної теорії розкладів.
Результати дослідження процесів функціонування різних технічних і
соціальних систем приводять до висновку про необхідність і важливість
рішення оптимізаційних задач, в рамках яких виникає питання про ефективний
розподіл і порядок використання часових ресурсів. Такі задачі традиційно
виникають, наприклад, в процесі розв’язування і оцінювання тестових завдань
при проведенні різних заходів навчально-методичного характеру в різних
учбових закладах.
Задачі складання
розкладу
Мережеве або
календарне
програмування
Теорія
розкладів
Складання часових таблиць
Маршрутизація
пакетів
15
В задачах розподілу ресурсів часто спостерігається ситуація, коли є
повний набір робіт (дій), які необхідно виконати, а наявних ресурсів для
виконання кожної роботи найкращим чином не вистачає. Для заданих множини
робіт та обсягів наявних ресурсів потрібно розподілити ресурси поміж
роботами таким чином, щоб максимізувати певний критерій ефективності
(наприклад, максимізувати прибуток виробництва за умов реалізації повного
переліку дій). До таких задач відносяться задача про рюкзак [35], задача
календарного планування [36] та інші. В математичних моделях оптимізаційних
задач серед інших розглядається критерій мінімізації загальної тривалості
робіт, тобто часового інтервалу між моментами початку першого етапу робіт до
завершення останнього етапу робіт.
Необхідно відзначити, що «часовий» характер задач розподілу ресурсів
виділяє їх в особливу категорію, що відноситься до теорії розкладів. При цьому
специфіка обліку часу істотно відрізняє їх від «об'ємних» економічних задач.
Якщо в останніх потрібно відповісти на питання, що та скільки виpобляти, то в
задачах теорії розкладу необхідно визначити, коли і в якій послідовності
виконувати роботи. Ця відмінність у специфіці задач визначає відмінність в
методах і можливостях їх розв’язання.
Пошук оптимального або близького до оптимального розкладу
здійснюється за допомогою методів математичного програмування. При цьому
необхідно звернути увагу на те, що у математичних моделях задач оптимізації
система обмежень визначає область допустимих розв’язків на основі
сукупності умов, які повинні виконуватись одночасно. В задачах теорії
розкладів ряд умов мають виконуватися альтернативно: або одна операція
передує іншій, або навпаки.
Ряд робіт (див., наприклад, [37]) відрізняються тим, що в них
розглядаються не окремі операції, а технології, що представляють собою набір
операцій, в результаті дії яких може бути отриманий той чи інший продукт. Для
виконання технології необхідна наявність деякої сукупності машин, що
працюють одночасно, іншими словами, має місце групування машин за
16
технологіями (в [37, 38] такі технології називаються багатопроцесорними
роботами). На практиці також часто виникають задачі теорії розкладів, де для
виконання операцій потрібно дотримуватися різного роду обмежень на ресурси.
Розв’язання цих задач в рамках декомпозиційного підходу [39], як правило,
здійснюється поетапно. При цьому, на кожному з етапів розв’язується своя
сукупність завдань, а формування остаточного розкладу їх виконання складає
суть задач календарного планування [40].
Серед робіт, присвячених алгоритмам розв’язування задач математичного
програмування та оцінці їх складності, виділимо, наприклад, роботи [41-43].
Ефективні алгоритми розв’язання задач оптимізації розроблені для випадків,
коли параметри моделей відомі апріорі. Проте, на практиці достатньо часто
розглядаються ситуації, в яких ці параметри не можуть бути задані точно або є
невідомими із-за специфіки окремих неконтрольованих чинників [44].
Багато досліджень зв’язано з розв’язуванням транспортної задачі (ТЗ). У
роботі Bellman і Zadeh [23] запропонована концепція прийняття рішення в
нечітких умовах для транспортної задачі з неточними параметрами. Стаття Lai і
Hwang [45] присвячена ситуації, в якій всі параметри моделі ТЗ є нечіткими. У
1979 році Isermann [46] розробив алгоритм рішення ТЗ, який знаходить її
ефективні рішення. Ringuest і Rinks [47] запропонували дві ітераційні схеми
рішення лінійних багатокритеріальних транспортних задач. S.Chanas і D.Kuchta
[48] розробили підхід, заснований на інтервальному визначенні неточно
заданих коефіцієнтів. Тien Fuling [49] застосував метод інтерактивного
нечіткого багатоцільового лінійного програмування для розв’язання задачі
транспортного планування.
Існують дослідження, що розглядають зведення нечітких транспортних
задач до традиційних ТЗ [50-52]. R.N.Gasimov і K.Yenilmez [53] досліджували
транспортні задачі з нечіткими величинами запитів і пропозицій, вирішуючи їх
шляхом зведення до параметричних моделей математичного програмування з
урахуванням критерію Белмана і Заде.
17
Нові арифметичні операції над трапецієвидними (трикутними) нечіткими
числами [52] дали можливість використовувати нечіткі числа для формалізації
нечітких задач лінійного програмування. Цей підхід спростив формалізацію і
рішення оптимізаційних задач, величини ресурсів в яких задаються нечіткими
трикутними числами [54]. Окрім цього, залучення методики порівняння
важливості критеріїв в задачах вибору дозволило узагальнити даний підхід на
випадок різної важливості обмежень ЗЛП.
Серед нечітких задач оптимізації, яким дослідники приділяють достатньо
багато уваги, необхідно відмітити задачі цілочисельного лінійного програмування [55-57]. До таких задач відносяться задачі оптимального розподілу
ресурсів в комп'ютерних і енергетичних мережах [58, 59], задача про
призначення [60, 61]. При цьому, потрібно підкреслити високу обчислювальну
складність таких задач.
У науковій літературі багато публікацій присвячено огляду результатів,
пов’язаних з аналізом складності та побудовою наближених алгоритмів
розв’язання згаданих задач. Більшість задач складання розкладів є NP-повними
задачами [62]. Лише деякі постановки з частинними умовами можуть бути
розв’язані за поліноміальний час. Детальний огляд задач теорії розкладів з
аналізом їх обчислювальної складності наведено у [63].
Наближені алгоритми дозволяють знаходити допустимі розв’язки з
гарантованою оцінкою точності за поліноміальний час [62]. Чисельні
алгоритми, що базуються на реалізації евристичних підходів, також знаходять
допустимі розв’язки за прийнятний час, але, як правило, не мають апріорної
оцінки похибки [63].
Дана дисертаційна робота присвячена розробці та практичному застосуванню методів і алгоритмів розв’язування нечітких задач складання розкладу
виконання сукупності завдань з урахуванням змін у часових ресурсних обмеженнях. У роботі розглянуті класи задач розподілу ресурсів як задач складання
розкладів, наведені основні положення про нечіткі величини і способи їх
формалізації. Використовуючи принцип формування нечіткого розв’язку
18
Белмана-Заде в нечітких задачах лінійного програмування, розглянуті різні
варіанти нечітких моделей ЗЛП (з нечіткими технологічними коефіцієнтами та
ресурсними обмеженнями). Проаналізовані способи та виписані оптимізаційні
задачі для знаходження нечітких рішень.
Наведено огляд результатів досліджень чітких і нечітких задач розподілу
ресурсів при виконанні заданої сукупності робіт, сформульована модель розподілу часового ресурсу, дослідження якої проводиться у дисертаційній роботі.
Розглянуто математичні постановки оптимізаційних задач розподілу часового
ресурсу за умов відсутності та наявності термінів переналагодження робіт.
Проведено детальний аналіз задач нечіткого розподілу часового ресурсу
як задач лінійного програмування з параметричними обмеженнями у вигляді
нечітких трикутних чисел. Використання понять сильної і слабкої зв'язності
обмежень задачі оптимізації дозволило розробити метод перетворення області
допустимих розв’язків, що враховує близькість обмежень. Запропоновано
схему розв’язання нечітких ЗЛП за наявності систем альтернативних обмежень.
Розроблено схеми жадібних алгоритмів для розв’язування задач рекомбінації.
Формалізовано та досліджено нечіткі задачі складання розкладу
виконання робіт з урахуванням впливу динаміки плину часу. Визначено спосіб
побудови нечітких множини, що описують швидкість зміни часу. Запропоновано гібридну модель динаміки часового ресурсу за умов виконання/
невиконання окремих робіт, отримано твердження про загальний розв’язок цієї
моделі, змодельовано динаміку функціонування схеми виконання сукупності
робіт з врахуванням швидкості плину часу.
Розроблену методику використано при складанні та проведенні процесів
навчання та тестування осіб, що проходять освітню перепідготовку за умов
обмеженості часу та аудиторного форду. Запропоновані методи можуть бути
використані при розв’язанні різних нечітких задач складання розкладів
виконання заданої кількості робіт з нечітко заданими часовими ресурсними
обмеженнями.
19
Зв'язок роботи з науковими програмами, планами, темами.
Дисертаційна робота є складовою частиною наукових робіт, які
ведуться на кафедрі системного аналізу і теорії прийняття рішень і в
науково-дослідному секторі "Проблем системного аналізу" Київського
національного університету імені Тараса Шевченка. Дослідження
виконувалися в рамках науково-дослідної теми №16БФ015-02 “Розробка
нових математичних методів системного аналізу і теорії оптимальних
рішень та їх застосування” (державний номер реєстрації 0116U002529,
термін виконання 2016-2018г.г., в рамках програми "Інформатизація
суспільства") і науково-дослідної теми «Розробка і впровадження
інформаційної та організаційної системи заходів по забезпеченню
інноваційної спрямованості науково-дослідних робіт в Київському
національному університеті імені Тараса Шевченка», НДР № 08БП 013-01
(за напрямом Підпрограми "Інформаційні технології в науці та
навчальному процесі").
Мета і задачі дослідження. Метою роботи є розробка методів та
алгоритмів розв’язування задач розподілу часового ресурсу при складанні
розкладів виконання сукупності робіт з нечітко заданими ресурсними
обмеженнями та термінами виконання, формалізації підходів для моделювання
поведінки динамічних процесів з урахуванням зміни темпів плину часу (на
прикладі процесу тестування осіб, що проходять перевірку рівня підготовки на
основі заданої сукупності тестів).
Задачі дослідження полягають в наступному:
 провести системний аналіз сучасного стану досліджень чітких та нечітких
задач складання часового розкладу виконання сукупності робіт;
 розробити методи для чіткої та нечіткій оптимізації задач розподілу
часового ресурсу;
 провести моделювання динаміки процесів і систем, функціонування яких
враховує різні темпи плину часу;
20
 розробити підхід для імітації процесу тестування з урахуванням різної
складності завдань та рівня підготовки, створити комп’ютерну систему
автоматизації процесу тестування.
Об'єктом дослідження є процеси знаходження розв’язків та оцінювання
кількісних характеристик в системах оптимізації розподілу часових ресурсів.
Предмет дослідження – математичні моделі, методи та інструментальні
засоби для врахування характеристик параметрів плину часу в динамічних
процесах, зв’язаних з оптимальним використанням часових ресурсів.
Методи дослідження. При розв’язанні поставлених задач були
використані методи системного аналізу, методи теорії оптимізації та теорії
нечітких множин для побудови математичних моделей задач лінійного
програмування з нечіткими ресурсними обмеженнями; методи дослідження
гібридних систем для розв’язання задачі моделювання динаміки процесів з
урахуванням зміни темпів плину часу.
Для подання нечітких даних при розв’язанні задачі розподілу нечітко
визначених часових ресурсів використано спосіб формалізації нечітких чисел у
вигляді нечітких трикутних чисел.
Наукова новизна отриманих результатів. У процесі розв’язання
поставлених задач отримано нові наукові результати, які полягають в
наступному:
1. на основі системного аналізу досліджень чітких та нечітких задач
математичного програмування обгрунтовано доцільність і необхідність
розвитку методів оптимізації для розв’язання лінійних оптимізаційних
задач з нечіткими ресурсними обмеженнями;
2. вперше сформульовано задачу розподілу часових ресурсів як задачу
складання розкладу виконання сукупності робіт;
3. на основі понять сильної і слабкої зв'язності обмежень задачі оптимізації
вдосконалено метод перетворення області допустимих рішень на основі
оцінки близькості обмежень;
21
4. запропоновано нову схему розв’язання нечітких задач лінійного
програмування за наявності систем альтернативних обмежень;
5. вперше змодельовано динаміку процесів з урахуванням зміни темпів плину
часу;
6. запропоновано нову схему жадібного алгоритму для розв’язання задачі
рекомбінації;
7. розроблено нові математичні моделі процесів тестування та оптимального
розподілу часових ресурсів;
8. розроблено комп’ютерну систему для організації та проведення процесів
тестування осіб, що проходять перевірку рівня підготовки на основі заданої
сукупності тестів.
Обґрунтованість та достовірність отриманих результатів підтверджується
коректністю постановок задач, строгим доведенням теорем, узгодженістю
отриманих аналітичних результатів з даними чисельного експерименту.
Практичне значення отриманих результатів полягає в тому, що в
дисертаційній роботі досліджено та розв’язано ряд практичних задач складання
розкладів виконання сукупності робіт з нечітко заданими часовими параметрами. Запропоновані методи та підходи створено на основі використання
нечітких трикутних чисел. Ці результати можуть бути використані при
створенні ефективних програмних систем для аналізу та моделювання процесів
розподілу часового ресурсу в нечітких умовах, для підтримки прийняття рішень
при дослідженні процесів і систем, динаміка поведінки яких враховує різні
темпи плину часу. Результати дисертаційного дослідження використовувались
у навчальному процесі на факультеті кібернетики Київського національного
університету імені Тараса Шевченка при підготовці лекційних та спеціальних
курсів «Сучасні інформаційні технології», «Методи прийняття рішень в умовах
нечіткості» та «Методи дослідження нечітких динамічних систем».
Особистий внесок здобувача. Дисертація є самостійною науковою
працею, в якій висвітлені власні ідеї та розробки автора, що дозволили досягти
поставленої мети. Наукові положення, пропозиції та рекомендації, що
22
виносяться на захист, отримані здобувачем самостійно. У спільних роботах із
науковим керівником Є.В.Івохіним, вибір методів дослідження та доведення
основних результатів виконано автором, особистий внесок якого полягає у
наступному: у роботі [2] наведено опис математичних і програмних засобів
адаптивного тестування та автоматичного оцінювання знань, у роботі [3]
встановлено умови евристичного алгоритму розв’язання нечіткої задачі
рекомбінації, у роботі [4] отримано умови сильної залежності обмежень в
лінійних задачах оптимізації, наведено результати проведених обчислень, що
підтверджують застосування методики скорочення обмежень, у роботі [5]
запропоновано метод розподілу часового ресурсу із змінними темпами плину
часу.
Апробація результатів дисертації. Матеріали дисертаційної роботи
доповідалися та обговорювалися на наукових конференціях та семінарах:
XVII Міжнародній конференції “Dynamic System Modeling and Stability
Investigation” (Київ, травень, 2015); VIІ міжнародній науково-практичній
конференції «Сучасні проблеми математичного моделювання, прогнозування та
оптимізації» (Кам’янець-Подільський, квітень, 2016); міжнародній школісемінарі «Теорії прийняття рішень» (Ужгород, вересень, 2016); XXVII
Міжнародній науковій конференції “Problems of Decision Making under
Uncertainties” (PDMU-2016), (Tбілісі-Батумі, Грузія, травень, 2016);
Міжнародній науковій конференції ”Интеллектуальний анализ информации”
(ІАІ-2016) (Київ, травень, 2016); Міжнародній науково-практичній конференції
«Обчислювальний інтелект» (Черкаси, травень, 2015; Київ, травень, 2017); на
наукових семінарах факультету кібернетики Київського національного
університету імені Тараса Шевченка.
Публікації. Основні наукові твердження, висновки і результати дисертаційної роботи опубліковані в 10 наукових працях. З них – 6 наукових статей, у
тому числі 5 у фахових виданнях [1-5], 1 стаття у виданні, яке входить до
наукометричної бази даних [5], 4 – праці та тези наукових конференцій [7-10].

Список литературы

ВИСНОВКИ
Дисертаційна робота присвячена розробці методів та алгоритмів
розв’язування задач розподілу часового ресурсу при складанні розкладів
виконання сукупності робіт з нечітко заданими ресурсними обмеженнями та
термінами виконання, формалізації підходів для моделювання поведінки
динамічних процесів з урахуванням зміни темпів плину часу (на прикладі
процесу тестування).
Проведено огляд класів задач лінійного програмування як основних задач
дослідження операцій. Детально викладено зміст задач про рюкзак, про
складання розкладу та про вибір заявок. Наведено основні положення про
нечіткі величини та способи їх формалізації. Викладено принцип формування
нечіткого розв’язку Белмана-Заде нечітких задач лінійного програмування,
розглянуто різні варіанти нечітких моделей ЗЛП (з нечіткими технологіч-ними
коефіцієнтами та ресурсними обмеженнями). Сформульовано нечіткі
оптимізаційні задачі та проаналізовано способи для знаходження нечітких
розв’язків. Розглянуто властивості та проаналізовано методи розв’язування
оптимізаційних задач планування, розміщення та розподілу ресурсів.
В роботі розглянуто та визначено методику розв’язування чітких і
нечітких задач розподілу часового ресурсу як задач складання розкладу:
наведено класифікацію задач теорії розкладів залежно від різних
характеристик, викладено математичні постановки оптимізаційних задач
розподілу часового ресурсу, сформульовано загальної задачі складання
розкладу в термінах лінійного цілочисельного програмування, досліджено
задачу складання розкладу виконання заданої кількості робіт для однієї
машини, наведено постановку і спосіб розв’язання задачі оптимальної
рекомбінації виконання робіт.
Викладено спосіб використання методу динамічного програмування для
розв’язування задач теорії розкладів у випадках з регулярним та нерегулярним
критеріями. Запропоновано метод найменших відхилень розв’язання задачі
розподілу часового ресурсу, схему реалізації жадібного підходу до
125
розв’язування задач розподілу ресурсів, підходи до застосування економічних
стратегій для розв’язання задач розподілу ресурсів.
Наведено детальний розгляд моделей і методів, які застосовуються при
розв’язанні нечітких задач оптимального розподілу часового ресурсу.
Сформульовано нечітку задачу про рюкзак як засіб розподілу нечітко
визначеного часового ресурсу. Описано задачу складання розкладу з нечітко
заданими інтервалами налаштувань.
Особливу увагу приділено задачі теорії розкладів з нечітким
вимірюванням часу. Визначено поняття структурованих нечітких чисел, які
використовуються для опису вимірювання відліку часу. Розглянуто нечітку
задачу про рюкзак з нечітко заданими термінами виконання.
На основі сильної та слабкої зв’язності обмежень лінійних задач
оптимізації розроблено метод перетворення області допустимих розв’язків з
урахуванням близькості обмежень. Проілюстровано вплив запропонованого
методу на результати розв’язання нечітких ЗЛП. Розроблено схему розв’язання
нечітких задач лінійного програмування за наявності систем альтернативних
обмежень.
Побудовано гібридну модель динаміки процесу обробки сукупності
завдань, отримано твердження про фундаментальну матрицю її розв’язків.
Отримані результати можуть бути використані при розв’язанні
актуальних прикладних задач в умовах невизначеності. Розглянуто приклади
практичного розв’язування задач оптимального розподілу часового ресурсу.
Запропоновано програмну реалізацію підходу для складання розкладу занять
академічних груп і викладачів в межах аудиторного фонду навчального закладу
протягом типового тижня. Проведено комп’ютерне моделювання динаміки
розподілу часового ресурсу при проведенні процесу тестування.
Коротко описано систему для проведення дистанційних тестувань, її
можливостей та вимог для використання.