8.2. Загальний алгоритм складання розкладу занять з використанням методів дослідження операцій

– максимізація засвоєння,

де w – тиждень;

t – пара всередині тижня;

i – заняття (окреме заняття певного виду певної дисципліни без прив’язки до часу та аудиторії), N = 150 тис. для КНУБА;

h – кількість засвоєної інформації кожним студентом;

x_i^wt – брати чи не брати заняття i парою wt, ;

β – коефіцієнт збіжності, відсоток об’єднання двох ЦФ, .

– мінімізація завантажень східців,

де j – аудиторія;

c – час переходу (у хвилинах) від минулої пари до аудиторії j;

y_ij^wt – брати чи не брати заняття i парою wt в аудиторії j, ;

– перший критерій є головнішим, ніж другий

Обмеження:

– не перевищення для дисциплін тижневого обсягу;

– сума всіх занять, яка дорівнює сумі всіх аудиторій,

де – загальні обсяги в тиждень;

a_i – кількість аудиторій, що потрібні для заняття i (як правило, 1).

– аудиторія може бути зайнята (1) або ні (0)

– аналіз перетинання за викладачами та групами (аналіз «накладок»).

Задача розв’язується на основі методу поступок у двох частинах:

Розрахунок розкладу, який гарантує наявність аудиторного фонду, методом ситуативного планування коефіцієнтів ЦФ та адитивним (back-track) алгоритмом.

Мінімізація переходів студентів між аудиторіями на основі задачі про призначення за допомогою алгоритму Vengr_1.

Розглянемо приклад розрахунку для блоку «Адитивний алгоритм».

На дату D є шість занять з визначеними академічними групами та викладачами. Враховуючи обмеження за аудиторіями (дві аудиторії на 30 студентів та одна аудиторія на 60 студентів), треба скласти розклад занять на день.

Заняття	x1	x2	x3	x4	x5	x6
Група	1	1, 2	2	3	3	2, 3
Викладачі	1	1	2	3	3	4

Враховуючи ситуативно розраховані вагомості дисциплін, математична модель матиме такий вигляд:

.

Також є ряд обмежень. Обмеження за групами:

.

Обмеження за викладачами:

.

Обмеження за аудиторіями:

.

Оскільки ЦФ адитивна, то задача розв’язується за допомогою back-track технології для кожної пари t.

Примітка. Якщо провести аналогію із задачею пересилання файлів через e-mail (див. п. 4.4, 8.1), то сеансами передачі даних є пари t, а файлами – заняття i при розв’язанні задачі за допомогою back-track технології.

Відповідь: 1-а пара – заняття 1, 3, 5; 2-а пара – 2, 4; 3-я пара – 6.

8.3. Класифікація методів технічного пошуку рішень

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

До методів МПР відносяться: ряд асоціативних методів (фокальних об’єктів, гірлянд, випадків і синонімів), методи контрольних питань, мозкового штурму, морфологічного аналізу, аналізу взаємозалежних областей, функціонально-вартісного аналізу, розв’язку винахідницьких задач, а також узагальнюючі методи.

Асоціативні методи – методи, основою яких є асоціації (зв’язки між ідеями), метафори (перетинання властивостей предметної області з іншими на основі аналізу їхньої спільності) та випадково обрані поняття (термін, що при виборі методу є опорним, наприклад, ми не знаємо, яким методом можна розв’язати задачу, але припускаємо, що це задача транспортна). Метод фокальних об’єктів дає змогу створити стійку універсальну модель та включає етапи: вибір фокального об’єкта та 3-4 випадкових, генерація ідей для об’єктів та приєднання їх до фокального, розвиток ідей та їхній зв’язок, оцінка та підбір ідей.

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

Метод мозкового штурму (колективного рішення) має на меті активізувати маси (як в Японії) та включає такі етапи:

1. Добір групи осіб (для генерування ідей) та групи експертів.

2. Організація процесу генерування ідей («ставлю вам задачу»).

3. Фіксація та оцінка ідей, заохочення авторів («продаю-купую» ідею).

4. Реалізація цінних ідей та прогресивне заохочення авторів.

Метод морфологічного аналізу полягає в формуванні варіантів розв’язку, що випливають із закономірності та історії розвитку на основі аналізу старої бази моделі.

Метод аналізу взаємозалежних областей має в основі розгляд суміжних предметних областей. Аналізується лише практичний аспект окремої області, а потім застосовується щодо іншої області (наприклад, задачу про розклад у вузі на основі аналогій «аудиторія-технологічне місце», «студент-ресурс» та «викладач-верстат» можна застосувати до промислового підприємства).

Метод функціонально-вартісного аналізу є розвитком мозкового штурму. Між експертами організовується «ділова гра». Критерієм є вартісні показники, тож вибір ідей розбитий на етапи: підготовчий (опис та класифікатори), інформаційний (система класифікацій та кодування), аналітичний (ДО), дослідницький (чутливість) та рекомендований.

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

Узагальнюючі методи полягають в організації системи штучного інтелекту (СШІ). СШІ – це система, яка задовольняє таким вимогам.

1. Використання бази даних (знань).

2. Критичність до нової інформації (усе, що нове надходить до системи, має бути перевірене).

3. Терпимість до неповноти бази знань.

4. Здатність до самонавчання.