Математичне моделювання та оптимізація системи дистанційного навчання освітнього закладу

Для досягнення поставленої мети необхідно було вирішити такі задачі:

· аналіз сучасного стану в галузі моделювання навчальних процесів;

· створення математичних моделей складання індивідуальних навчальних планів;

· формування математичних моделей стаціонарних консультацій для окремого студента чи для груп студентів;

· розробка математичних моделей стаціонарних іспитів для окремого студента чи для груп студентів;

· розробка математичних моделей індивідуальних захистів дипломних робіт;

· проектування, програмна реалізація та впровадження Інтегрованої системи управління навчальним закладом.

Об'єктом дослідження є система дистанційного навчання освітнього закладу.

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

Методи досліджень. В ході виконання дисертаційних досліджень запропоновано та обґрунтовано оптимізаційні математичні моделі у вигляді цільових функцій та обмежень з дискретними змінними. Для знаходження задовільних розв'язків використано бібліотеку Java Constraint Programming, яка містить багато вбудованих обмежень та алгоритмів побудови дерева результатів. Моделі задаються таким чином, щоб можна було використати можливості Constraint Logic Programming. Інтегровану систему управління навчальним закладом створено на основі технологій програмування Інтернет-систем та об'єктних можливостей мови Java.

Наукова новизна одержаних результатів полягає в наступному:

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

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

Кількість типів обмежень, які виникають на практиці, є настільки великою, що розв'язування задач є надто складним. В працях авторів Burke E., Elliman D., Ford P., Eare R. можна знайти підходи до вирішення аналізованих задач в багатьох університетах з врахуванням обмежень, що в них виникають. Декілька авторів пробують за допомогою спеціальних універсальних алгоритмів знайти способи ефективного знаходження розв'язків, що дозволяють отримати добрі результати для різних типів обмежень. Це, наприклад, алгоритми на основі гіпер-евристик в публікаціях Burke E.K., Dror M., Petrovic S., Qu R., Ross P., Marin-Blazquez J.G. та Hart E. Задачі складання розкладів іспитів чи консультацій - це типові NP-складні задачі.

При дистанційному навчанні (англ. Distance Education) виникають три завдання (див. рис. 1). Управління матеріалами полягає в створенні дидактичних матеріалів, які можна розповсюджувати через Інтернет та з допомогою яких студент може самостійно вчитись. Системи розповсюдження матеріалів - це великі системи, які окрім доставки матеріалів дозволяють самостійно перевіряти результати навчання. Цю дисертацію присвячено проблемам математичного моделювання процесів дистанційного навчання з індивідуальним підходом до формування навчального плану, складання розкладів консультацій та іспитів.

В літературі розглянуто багато способів розв'язування задач такого типу. Одним з них є програмування в логіці обмежень (англ. Constraint Logic Programming). Цей підхід полягає в програмному описі математичних моделей з використанням апарату дискретної математики. За допомогою дискретних змінних описують кінцевий результат. Кожна змінна володіє доменом можливих значень. За допомогою спеціальних функцій визначають різноманітні обмеження та зв'язки між змінними. Завдяки механізму "поширення" обмежень домени можливих значень звужуються. Серед значень, що залишились, потрібно знайти розв'язок. Крім алгоритмів повного пошуку (англ. Branch and Bound), практичні бібліотеки CLP використовують також алгоритми гіпер-евристичного пошуку.

З кількох бібліотек представлено детальніше бібліотеку Java Constraint Programming. Використання цієї бібліотеки як елементу мови Java дозволяє використовувати її на різних апаратних платформах та при різних способах застосування, таких як Інтернет-системи. Принципи застосування бібліотеки JaCoP зображено на рис. 2.

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

В розділі розглянуто два типи моделей складання навчальних планів: для груп та для окремих студентів. Модель для груп враховує побажання цілої групи студентів та дає можливість складати план тільки на найближчий семестр з урахуванням пройдених предметів. Модель для окремих студентів дозволяє складати навчальний план на всі семестри на основі предметів, які обирає студент. Кінцевим результатом є інформація, поставлена у відповідність кожному предмету, про те, чи даний предмет є вибраний і на який семестр. Ця інформація задається як вектор , де , причому присвоюють значення 0, якщо предмет не обраний, і n, якщо предмет обраний на n-й семестр. Кількість всіх можливих комбінацій матриці X становить , де N - кількість семестрів, а P - кількість всіх предметів. Задача полягає в заповненні матриці X таким чином, щоб її елементи задовольняли всі обмеження та щоб значення цільової функції було максимальним.

З метою орієнтації на студентів, навчальний заклад надає можливість вибору предметів, які студент хоче здати за весь період навчання. Вибір студента у вигляді побажань записується в матриці , де . Значення 0 означає, що студент s не бажає вивчати предмет p. Значення 1 означає, що студент s бажає вивчати предмет p. Таким чином, студенти мають вибір предметів, які будуть вивчати. Ці побажання розглядають як м'які обмеження в цільовій функції. Цільову функцію задаємо по-різному для двох типів моделей. В моделі для груп студентів:

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

При складанні навчального плану виникає багато обмежень. До найважливіших і найважчих щодо реалізації є обмеження почерговості предметів, яку записують у вигляді матриці , де . Значення 1 елемента цієї матриці означає, що предмет повинен йти в навчальному плані перед предметом , тобто є його попередником. До інших обмежень належать кількості годин і - мінімальна і максимальна для n-го семестру, і - мінімальна та максимальна кількості годин за весь період навчання, а також відповідні кількості годин для окремих предметів, які задаються вектором .

Модель враховує європейські стандарти можливості переходу студентів з навчального закладу в одній країні в навчальний заклад в іншій країні. Вони полягають у присвоєнні предметам так званих трансферних кредитів ECTS (англ. European Credit Transfer System), які студент отримує протягом навчання. Присвоєння предметам трансферних кредитів відбувається за допомогою значень , а обмеження на кількість кредитів визначаються як і - мінімальна та максимальна кількість кредитів для n-го семестру, і - мінімальна та максимальна кількість кредитів за весь період навчання.

Всі предмети поділяються на обов'язкові та факультативні, які студенти можуть обирати. Це задається за допомогою вектора, де. Значення 0 означає, що предмет p є факультативним, а 1 - обов'язковим. В моделі складання плану для груп студентів план обирається лише на поточний семестр, але потрібно враховувати предмети, що вже були за час попередніх семестрів. Обмеження та використані класи бібліотеки JaCoP наведено в табл. 1. Ця таблиця містить список об'єктних класів бібліотеки Java Constraint Programming для окремих обмежень. Механізм розв'язування звужує дерево можливих розв'язків за допомогою механізму "розширення" обмежень до розмірів, які дають можливість отримати розв'язок за допустимий час.

Таблиця 1. Обмеження та класи бібліотеки JaCoP (навчальні плани).

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

В розділі наведено дві моделі - складання розкладів консультацій для груп студентів та для окремих студентів. В обох моделях однаково враховано як в жорстких, так і в м'яких обмеженнях побажання викладачів щодо термінів. Ці обмеження записують за допомогою матриці, де. Значення 0 означає, що викладач w не буде доступний в період t. Додатні значення означають, що викладач буде доступний, причому більше значення відповідає бажанішому терміну. Визначені таким чином побажання дають можливість планувати час викладачів довільним чином, включно з мінімізацією так званих вікон. В обох моделях також враховано побажання студентів щодо термінів. Вони задаються у вигляді матриці , де . Студенти можуть визначати лише, чи бажають даний період, чи ні. В обох моделях побажання студентів не враховують як жорсткі обмеження, оскільки на практиці це би вело до відсутності розв'язку. В обох моделях визначено предмети, з яких можуть відбуватися консультації для студентів або для груп студентів, причому задають їх матрицею, де. Значення означає, що група студентів g не має консультації з предмету p, а додатне значення означає, що група g повинна мати консультацію з предмету p у викладача w.

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

В моделі консультацій для окремого студента потрібно визначити N консультацій для кожного студента з усіх предметів, які має цей студент. Записуємо матрицю, що описує кінцевий розв'язок: , де ; - номер терміну консультації; - n-й термін k-ї консультації для студента з предмету у викладача . Цільова функція, де - побажання викладача щодо терміну ; - побажання студента щодо терміну .

Модель враховує багато обмежень, що виникають при реальному дистанційному навчанні, їх наведено в табл. 2 з відповідними застосованими об'єктними класами бібліотеки Java Constraint Programming.

Таблиця 2. Обмеження та класи бібліотеки JaCoP (консультації).

Реалізація цих обмежень за допомогою бібліотеки Java Constraint Programming дає можливість знайти задовільний розв'язок за допомогою алгоритму Credit. Задовільний розв'язок визначають, за допомогою певного коефіцієнта, який є частиною максимального значення цільової функції. Знаходження задовільного розв'язку є обмеженим в часі. Процедури розв'язування за допомогою технології Constraint Logic Programming полягають у "розширенні" всіх обмежень так, щоб звузити дерево пошуку і застосувати алгоритм побудови дерева. Використаний алгоритм Credit застосовує алгоритм повного пошуку на кілька рівнів в глибину, а далі - алгоритм локального пошуку. Це дає можливість знайти задовільний розв'язок за допустимий час.

В четвертому розділі розроблено математичні моделі для укладення розкладів стаціонарних іспитів для груп студентів та для окремих студентів. При дистанційному навчанні знання студентів потрібно перевіряти все-таки на території навчального закладу в присутності викладачів. В розділі розглянуто дві моделі. Перша модель враховує традиційний поділ на групи і базується на механізмі вибору викладача зі списку доступних. Це дає можливість складати розклад без попереднього призначення конкретних викладачів. Такий розв'язок є універсальним. Змінні задають таким чином, щоб можна було застосовувати доступні обмеження бібліотеки JaCoP.

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

З огляду на інтеграцію, моделі допускають задавання побажань викладачів та студентів щодо термінів аналогічно до моделей складання розкладів консультацій, тобто за допомогою матриць та . Матриця визначає, які предмети повинна здавати група, а які окремі студенти. Також в моделях додатково враховано кілька реальних проблем. Викладач не є визначеним наперед, натомість доступним є список викладачів, які можуть прийняти заданий предмет. Це описують за допомогою матриці , де . Значення 1 означає, що викладач w може екзаменувати студентів з предмету p. Іспити проходять в лабораторіях та аудиторіях, які відповідають предмету. Це описують за допомогою елементів матриці , де одиничні значення означають, що аудиторія l відповідає предмету p. Крім того, приміщення мають певні місткості, які записані у векторі . Кожен викладач має обмеження максимальної кількості студентів, записане у векторі . Додатковою проблемою, взятою до уваги в моделях, є врахування складності іспитів та обмеження суми складності іспитів за один день. Складність предметів відображається вектором , а денна складність - вектором .

Розроблені математичні моделі враховують багато обмежень, що виникають під час реального процесу укладання розкладів іспитів. Ці обмеження та відповідні застосовані класи бібліотеки Java Constraint Programming наведено в табл. 3.

Таблиця 3. Обмеження та класи бібліотеки JaCoP (іспити).

Застосування обмежень, наведених в табл. 3, з використанням бібліотеки Java Constraint Programming та відповідного алгоритму дає можливість знайти розв'язок за задовільний час.

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

Для збереження повної інтегрованості системи, в цій задачі також відображено побажання викладачів, які описують за допомогою матриці . Також наявний параметр, що показує доступність студентів, його записують у вигляді матриці , з тією різницею, що значення 0 означає, що студент в цей час недоступний (на практиці терміни захистів дипломних робіт погоджують із студентом). Комісійний іспит вимагає збору кількох викладачів і обов'язковою є присутність студента. Додатково враховано можливість проведення одночасно кількох захистів. Обмеження кількості захистів для терміну t записують за допомогою вектора . Для студентів відомий вектор їх керівників . Решту викладачів - рецензента і голову комісії потрібно вибрати. Запишемо за допомогою матриць і можливість вибору зі списку доступних викладачів. Елементи цих матриць можуть набувати значень 0 або 1. Значення 1 означає, що викладач w може бути обраним до комісії для студента s.

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

Модель враховує багато обмежень, що виникають при реальному складанні розкладів захистів дипломних робіт. Ці обмеження та відповідні об'єктні класи бібліотеки Java Constraint Programming наведено в табл. 4. Застосування обмежень, наведених в цій таблиці, за допомогою бібліотеки Java Constraint Programming та відповідного алгоритму, дає можливість знайти задовільний розв'язок за прийнятний час.

Таблиця 4. Обмеження та класи бібліотеки JaCoP (дипломні роботи).

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

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

В шостому розділі представлено архітектуру створеної підсистеми дистанційного навчання, яка є елементом Інтегрованої системи управління навчальним закладом. Ця система є одним з основних результатів дисертаційної роботи, її структура зображена на рис. 3. До підсистеми дистанційного навчання входить як внутрішня адміністративна частина, так і зовнішня частина, доступна для викладачів і студентів через Інтернет.

Рис. 3. Структура підсистеми дистанційного навчання.

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

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

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ