Розробка математичної моделі та ВО для завдань складання розкладу

Доклад.

Бакалаврская робота на задану тему «Розробка математичну модель та ВО для завдань складання расписания».

Шановні члени комісії, ви уявляєте доповідь бакалаврської роботи з тему «Розробка математичної моделі та ВО для завдань складання расписания».

Технологию розробки розкладу слід сприймати як як трудомісткий технічний процес, об'єкт механізації і автоматизації з використанням ЕОМ, а й як акцію оптимального управління. Отже, це — проблема розробки оптимальних розкладів занять до вузів з очевидним економічним ефектом. Оскільки інтереси учасників процесу різноманітні, завдання складання розкладу — багатокритерійну.

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

Працюючи на початковому етапі знають було проаналізовано і протестовані існуючі на момент програмні продукти. Тестування здійснювалося з урахуванням даних про ЧДУ за 1999/2000 навчальний рік. З проаналізованих програм лише 3 спромоглися скласти розклад, задовольняють майже всі вимоги, причому остаточних результатів роботи однієї програми дочекатися не вдалося, а 2 інші працювали близько 3−4 часов.

Поэтому поставили завдання: створення такої математичну модель розкладу у ВНЗ, яка б ефективно (в задані строки й із заданою ступенем оптимальності) вирішувати проблему автоматичного складання розклади і мала б гнучкістю (незначних змін — у разі змін вхідний інформації) на адаптацію системи у межах конкретної практичної завдання. Для деякого спрощення завдання на початковому етапі проектування було зроблено деякі допущения:

— розклад складається з розрахунку трохи більше двох пар щодня (що цілком адресований випадку вечірньої форми обучения);

— все пари проводять у одному корпусе;

— ставиться завдання в термінах лінійного программирования;

— подальша декомпозиція моделі не производится;

— все коефіцієнти моделі і шукані перемінні целочисленны;

Працюючи було побудовано математична модель розкладу у ВНЗ для випадку вечірньої форми навчання без переходів між корпусами, обрані на методи вирішення поставленого завдання і розроблена модель зберігання вихідних даних завдання. Математична формалізація завдання складання розкладу виконувалася виходячи з того (див. плакат 1.):

1. Впроваджувалися целочисленные константи, відповідні групам, проведених занять, викладачам, аудиторного навантаженні викладачів і аудиторному фонду, причому частина їх може приймати тільки булевы значения.

2. Впроваджувалися булевы перемінні, відповідні парі, де проводиться ту чи іншу заняття. Задля збереження лінійної целочисленности отриманої моделі знадобилося вводити по 12 змінних кожне проведене занятие.

3. За підсумками запроваджених констант і апріорній інформації про завданню складалися обмеження на значення булевых переменных.

4. Цільова функція створювалася в такий спосіб, щоб максимізувати зважене число вільних від аудиторного роботи днів всіх викладачів, що фіксованою довжини робочого тижня еквівалентно максимальному сукупного ущільнення аудиторного навантаження. Усі перемінні, що входять до цільову функцію, першого ступеня, і всі коефіцієнти при змінних постоянны.

Поставленная в такий спосіб завдання максимізації лінійної цільової функції при заданої системі обмежень є завданням лінійного целочисленного булева програмування, бо всі коефіцієнти обмежень целочисленны з дискретності вихідних даних завдання; крім цього шукані перемінні математичну модель можуть лише два значення. На цей час часу є кілька можливих методів рішення що така завдань.

В [3] - [8] описані методи упорядкованим індексації і модифікованих позначок, засновані на лагранжевой декомпозиції вихідної моделі на цілий ряд однострочных завдань, розв’язуваних відповідно методами упорядочивающей індексації чи модифікованих позначок. На жаль кількість операцій кожного з методів передбачає полиномиальной оцінки; ще, розмірність таблиці наборів (проміжних значень) методів різко зростає зі збільшенням розмірності розв’язуваної завдання, що неприпустимо у разі. Можливо, зміна алгоритму декомпозиції під конкретну математичну модель дозволить зменшити розмірність таблиць, але ще такого алгоритму не существует.

В цьому сенсі як методів рішення було обрані достойні [2] модифікації симплекс-метода для випадку завдання целочисленного лінійного програмування. У випадку кількість операцій симплекс-метода передбачає полиномиальной оцінки (було навіть показаний клас завдань, котрим кількість операцій становить O (en)), але для випадку нашої завдання середня кількість операцій допускає полиномиальную оцінку: O (n3m1/(n-1)) (n — кількість змінних; m — кількість обмежень). Алгоритм роботи методів представлений плакаті 2.

Алгоритми математичної формалізації моделі і нові методи рішення було реалізовані як програмних модулів. Швидкість роботи алгоритмів була протестирована на різнорідних наборах вихідних даних, у результаті були визначено можливості й області застосування алгоритмів.

Ядро системи та інтерфейсна частина було написано на Delphi 6.0. База даних реалізували на СУБД Oracle 8i, запити до неї здійснюються мовою PL/SQL.

Алгоритми виконання завдання були протестовані в різних вибірках вихідних даних. Тестування вироблялося на ЕОМ з процесором Intel Pentium 350 МГц, СУБД Oracle 8i було встановлено на двухпроцессорном сервері: 2 CPU Intel Pentium II 350 МГц, ОЗУ 384 МБ; як каналу зв’язку використовувалася LAN з пропускною здатністю до 100 Мбіт/с. Як тестових вихідних даних було використано як реальні даних про групах, викладачів і читаються предметах вечірньої форми навчання ЧДУ на 1999/2000 навчальні роки, так і випадково формовані вихідні дані (читаним предметів випадково визначали аудиторії щодо занять). У середньому вироблялося від 5 до 10 тестів кожної тестируемой розмірності вихідних даних. У результаті отримали дані, наведені на плакаті 3.

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

Во-первых, використана математична модель містить у собі «зайві» обмеження, існування яких зумовлено лінійної целочисленной моделлю, крім цього кожному читаемому на потоці (потік може й з однієї групи) предмета ставлять у відповідність 12 (для випадку вечірників) змінних, кожна з яких представляє з себе булеву зміну. По-друге, різко зростає час розв’язування задачі зі збільшенням вхідних даних. Це наслідок різкого збільшення кількості змінних та в моделі, внаслідок чого зростає розмірність масивів і час розв’язування задачі. По-третє, формалізована математично завдання охоплює тільки завдання складання розкладу для студентів вечірньої форми навчання не враховуючи переходів між корпусами. Облік додаткових вимог збільшить кількості обмежень завдання, що може негативно стимулюватиме швидкість роботи алгоритмів решения.

Обратим увагу до зростання різницю між мінімальним та середнім значенням часу виконання завдання зі збільшенням розмірності завдання. Ця різниця відповідає тому, наскільки «вдало» (найближче оптимального) знайшли початкова дозволене базисне вирішення завдання. Тому час розв’язування задачі можна значно зменшити, «вдало» знайшовши початкова базисне дозволене рішення. Для пошуку цього рішення найкраще використати евристичні і декомпозиционные алгоритмы.

Отметим, що евристичні і декомпозиционные алгоритми не можна залучити до «чистому» вигляді, оскільки у разі евристичного рішення її (рішення) оптимальність (чи досягнення глобального максимуму) то, можливо доведено лише повним перебором всіх можливих варіантів (ясно, у цьому разі час алгоритму буде, дуже великим), тому ітерації евристичних алгоритмів припиняються по досягнення якогось максимального (не можна сказати, локального чи глобального) значення. Рішення такого алгоритму то, можливо близькими до оптимальному, але з оптимальним. І тут задля досягнення глобального максимуму можна використовувати розглянутий у роботі спосіб розв’язання, оскільки оптимум може бути досягнуть протягом кількох ітерацій представлених на плакаті 2. методів решения.