Xreferat.com » Рефераты по информатике и программированию » Разработка математической модели и ПО для задач составления расписания

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

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

Введем следующие искомые булевы переменные:

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

1, если на потоке r в день t на паре j читается лекция sr;

0 – в противном случае;

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

1, если на потоке r в день t на паре j у группы kr проводится практическое занятие qkr;

0 – в противном случае;

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

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

В случае составления расписания для групп вечерней формы обучения J=2. Обобщение модели на все формы обучения см. [1], стр. 669.

2.1.3. Ограничения

Для каждой группы kr должны выполняться все виды аудиторной работы в течение недели:

(1)

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

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

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

(2)

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

Каждые лекция sr и практическое занятие qkr соответственно для всех потоков r и всех групп kr могут проводиться не более одного раза в любой день t:

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

(3)

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

Если переменные Разработка математической модели и ПО для задач составления расписанияи Разработка математической модели и ПО для задач составления расписанияувязывают все виды занятий с временем их проведения, то произведения Разработка математической модели и ПО для задач составления расписанияи Разработка математической модели и ПО для задач составления расписаниясвязывают время проведения с именем преподавателя.

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

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

(4)

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

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

(5)

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

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

(6)

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

(7)

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

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

(8)

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

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

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

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

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

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

(9)

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

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

(10)


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

где M – произвольное положительное достаточно большое число; Разработка математической модели и ПО для задач составления расписания - искомая булева переменная.

Из (10) вытекает, что если Разработка математической модели и ПО для задач составления расписания, то Разработка математической модели и ПО для задач составления расписания = 1, и если Разработка математической модели и ПО для задач составления расписания, то Разработка математической модели и ПО для задач составления расписания = 0.

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

(11)


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

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

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

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

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

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

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

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

Пусть задана задача целочисленного линейного программирования:

максимизировать

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

при условиях

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: