Бакалаврська робота на тему "Розробка математичної моделі, ПЗ для завдань складання розкладу"
Шановні члени комісії, вам представляється доповідь бакалаврської роботи на тему "Розробка математичної моделі, ПЗ для завдань складання розкладу".
Технологію розробки розкладу слід сприймати не тільки як трудомісткий технічний процес, об'єкт механізації і автоматизації з використанням ЕОМ, але й як акцію оптимального управління. Таким чином, це - проблема розробки оптимальних розкладів занять у вузах з очевидним економічним ефектом. Оскільки інтереси учасників навчального процесу різноманітні, завдання складання розкладу - багатокритеріальна.
Багатокритеріальної цього завдання і складність об'єкта, для якого сроітся математична модель, обумовлює необхідність серйозного математичного дослідження об'єкта для збільшення функціональних можливостей алгоритмів складання розкладів без значного ускладнення моделі і, як наслідок, збільшення обсягів використовуваної пам'яті і часу виконання завдання.
У ході роботи на початковому етапі були проаналізовані і протестовані існуючі на сьогоднішній момент програмні продукти. Тестування здійснювалося на основі даних про ЧДУ за 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. методів рішення.