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

Если переменные

и увязывают все виды занятий с временем их проведения, то произведения и связывают время проведения с именемпреподавателя.

В каждый день t и в каждой паре j преподаватель p может вестине более одного занятия по одной дисциплине на одном потоке или в одной группе:

Каждый преподаватель p в течение недели долженпровести аудиторные занятия:

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

Кроме того, для всех совокупностей пересекающихся множеств{A₁_r} и {A₂_r} должны выполняться условия:

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

2.1.4.Целевая функция

Чтобы полноценно вести научную, учебно-методическую работу,готовиться к занятиям, преподаватель вуза должен иметь свободное время. Этоусловие недостаточное, но необходимое. Очевидно, что свободным временем ондолжен располагать не в “рваном” режиме, каковым, например, являются “окна”между занятиями со студентами, а по возможности в полностью свободные рабочиедни. Этому эквивалентна максимизация аудиторной нагрузки преподавателей в тедни, когда они ее имеют (см. (5)). Однако при этомпретензии на свободное время у преподавателей неравны, так как у них разныйтворческий потенциал. Поэтому необходимо ввести весовые коэффициенты,посредством которых должен учитываться соответствующий статус преподавателя –его ученые степени и звание, занимаемая должность, научно-общественнаяактивность и т.п. В некоторых случаях можно на основании экспертных оценокиспользовать индивидуальные весовые коэффициенты, учитывающие другие факторы.

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

Рассмотрим выражение для величины аудиторной нагрузки вдень t преподавателя p:

Вводятся ограничения вида:

где M – произвольное положительное достаточно большое число;

-искомая булева переменная.

Из (10) вытекает, что если

, то =1, и если , то =0.

С учетом указанного выше содержательного смысла критерияоптимизации в дополнительных ограничениях (10), а также вводя весовыекоэффициенты статуса преподавателя

, получаем искомый критерий оптимальности:

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

2.2. МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

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

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

В связи с этим в качестве методов решения были выбраныописанные в [2] модификации симплекс-метода для случая задачи целочисленноголинейного программирования. В общем случае количество операций симплекс-методане допускает полиномиальной оценки (был даже показан класс задач, для которыхколичество операций составляет O(eⁿ)), но для случая нашей задачи среднеечисло операций допускает полиномиальнуюоценку: O(n³m^1/(^n-1)) (n – количество переменных; m – количество ограничений).

2.2.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

Этот алгоритм назван полностью целочисленным, потому чтоесли исходная таблица состоит из целочисленных элементов, то все таблицы,получающиеся в процессе работы алгоритма, содержат только целочисленныеэлементы. Подобно двойственному симплекс-методу, алгоритм начинает работать сдвойственно допустимой таблицы. Если a_i₀ (i = 1 ,…, n+m; a_i₀ – коэффициенты целевой функции) –неотрицательные целые, то задача решена. Если для какой-нибудь строки a_i₀