Доповідь.

Бакалаврська робота на тему "Розробка математичної моделі і ПЗ для завдань складання розкладу"

Шановні члени комісії, вам представляється доповідь бакалаврської роботи на тему "Розробка математичної моделі, ПЗ для задач складання розкладу ".

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

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

У ході роботи на початковому етапі були проаналізовані і протестовані існуючі на сьогоднішній момент програмні продукти. Тестування здійснювалося на основі даних про ЧДУ за 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. методів рішення.