Разработка математической модели и ПО для задач составления расписания

Доклад.Бакалаврская работа на тему Разработка математическоймодели и ПО для задач составления расписания Уважаемые члены комиссии, вам представляется доклад бакалаврской работы на тему Разработка математическоймодели и ПО для задач составления расписания .Технологию разработки расписания следует воспринимать не только кактрудоемкий технический процесс, объект механизации и автоматизации сиспользованием ЭВМ, но и как акцию оптимального управления. Таким образом, это- проблема разработки оптимальных расписаний занятий в вузах с очевиднымэкономическим эффектом.

Поскольку интересы участников учебного процессамногообразны, задача составления расписания - многокритериальная.Многокритериальность этой задачи исложность объекта, для которого сроится математическая модель, обуславливаетнеобходимость серьезного математического исследования объекта для увеличенияфункциональных возможностей алгоритмов составления расписаний без значительногоусложнения модели и, как следствие, увеличения объемов используемой памяти ивремени решения задачи.

Входе работы на начальном этапе были проанализированы и протестированысуществующие на сегодняшний момент программные продукты.Тестированиеосуществлялось на основе данных о ЧГУ за 1999 2000 учебный год. Изпроанализированных программ только 3 оказались в состоянии составитьрасписание, удовлетворяющие почти всем требованиям, причем окончательныхрезультатов работы одной программы дождаться так и не удалось, а 2 остальныеработали около 3-4 часов.Поэтому была поставлена задача созданиетакой математической модели расписания в вузе, которая позволяла бы эффективно в заданные сроки и с заданной степенью оптимальности решать задачуавтоматического составления расписания и обладала бы гибкостью незначительныхизменений в случае изменений входной информации для адаптации системы в рамкахконкретной практической задачи. Для некоторого упрощения задачи на начальномэтапе проектирования были сделаны некоторые допущения - расписаниесоставляется из расчета не более двух пар в день что вполне подходит дляслучая вечерней формы обучения - все парыпроводятся в одном корпусе - задачаставится в терминах линейного программирования - дальнейшаядекомпозиция модели не производится - всекоэффициенты модели и искомые переменные целочисленны В ходе работы была построенаматематическая модель расписания в вузе для случая вечерней формы обучения безпереходов между корпусами, выбраны методы решения поставленной задачи иразработана модель хранения исходных данных задачи.Математическая формализация задачи составления расписания выполняласьисходя из принципов см. плакат 1. Вводились целочисленные константы, соответствующиегруппам, проводимым занятиям, преподавателям, аудиторной нагрузкепреподавателей и аудиторному фонду, причем часть из них может принимать толькобулевы значения.2. Вводились булевы переменные, соответствующие паре, накоторой проводится то или иное занятие.

Для сохранения линейной целочисленностиполученной модели потребовалось вводить по 12 переменных на каждое проводимоезанятие.3. На основе введенных констант и априорной информации озадаче составлялись ограничения на значения булевых переменных.4. Целевая функция составлялась таким образом, чтобымаксимизировать взвешенное число свободных от аудиторной работы дней для всехпреподавателей, что при условии фиксированной длины рабочей недели эквивалентномаксимальному совокупному уплотнению аудиторной нагрузки.

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

В 3 8 описаны методыупорядоченной индексации и модифицированных пометок, основанные на лагранжевойдекомпозиции исходной модели на ряд однострочных задач, решаемых соответственнометодами упорядочивающей индексации или модифицированных пометок.

К сожалениюколичество операций каждого из методов не допускает полиномиальной оценки кроме того, размерность таблицы наборов промежуточных значений методов резковозрастает при увеличении размерности решаемой задачи, что недопустимо в нашемслучае.

Возможно, изменение алгоритма декомпозиции под конкретную математическуюмодель позволит уменьшить размерность таблиц, но пока такого алгоритма несуществует.В связи с этим в качестве методоврешения были выбраны описанные в 2 модификации симплекс-метода для случаязадачи целочисленного линейного программирования.

В общем случае количествоопераций симплекс-метода не допускает полиномиальной оценки был даже показанкласс задач, для которых количество операций составляет O en , но для случая нашей задачи среднее числоопераций допускает полиномиальнуюоценку O n3m1 n-1 n количествопеременных m количествоограничений . Алгоритм работы методов представлен на плакате 2.Алгоритмы математической формализации модели и методы решения былиреализованы в виде программных модулей. Скорость работы алгоритмов былапротестирована на разнородных наборах исходных данных, в результате чего былиопределены возможности и области применения алгоритмов.

Ядросистемы и интерфейсная часть были написаны на Delphi 0. База данных была реализованана СУБД Oracle 8i, запросы к нейосуществляются на языке PL SQL. Алгоритмырешения задачи были протестированы на различных выборках исходных данных.Тестирование производилось на ЭВМ с процессором Intel Pentium 350 Мгц, СУБД Oracle 8i был установлен на двухпроцессорномсервере 2 CPU Intel Pentium II350 Мгц, ОЗУ 384 Мб в качестве канала связи использовалась LAN с пропускной способностью до 100Мбит с. В качестве тестовых исходных данных были использованы как реальныеданные о группах, преподавателях и читаемых предметах вечерней формы обученияЧГУ на 1999 2000 учебные годы, так и случайно формируемые исходные данные читаемым предметам случайным образом определяли аудитории для проведениязанятий . В среднем производилось от 5 до 10 тестов для каждой тестируемойразмерности исходных данных.

В результате получили данные, приведенные наплакате 3.Анализируяполученные данные можно сделать некоторые выводы о функциональных возможностяхалгоритмов решения и математической модели, их недостатках и областяхприменения.Во-первых,использован ная математическая модель содержит в себе лишние ограничения,существование которых обусловлено линейной целочисленной моделью, кроме этогокаждому читаемому на потоке поток может состоять и из одной группы предметуставится в соответствие 12 для случая вечерников переменных, каждая изкоторых представляет из себя булеву переменную.

Во-вторых, резко возрастаетвремя решения задачи при увеличении входных данных.

Это происходит из-зарезкого увеличения количества переменных и ограничений в модели, в результатечего возрастает размерность массивов и соответственно время решения задачи.

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

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

Поэтому время решения задачиможно значительно уменьшить, удачно найдя начальное базисное допустимое решение.Для поиска такого решениялучше всего использовать эвристические и декомпозиционные алгоритмы.Отметим, чтоэвристические и декомпозиционные алгоритмы нельзя использовать в чистом виде,поскольку в случае эвристического решения его решения оптимальность илидостижение глобального максимума может быть доказана только полным переборомвсех возможных вариантов ясно, что в этом случае время работы алгоритма будеточень большим , поэтому итерации эвристических алгоритмов прекращаются подостижении некоего максимального нельзя сказать, локального или глобального значения.

Решение такого алгоритма может быть близким к оптимальному, но неоптимальным.

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