скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

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

Аудиторный фонд определяется до начала составления расписания, поэтому множества можно считать заданными.

2.1.2. Переменные

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

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

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

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

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

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

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

при условиях

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

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

(12)

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

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

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

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

Условия (12) могут быть записаны как

(13)


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

Предположим, что для t=0 (т.е. для исходной таблицы) все aij – целые и столбцы Разработка математической модели и ПО для задач составления расписания(j = 1 ,…, n) – лексикографически положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.

Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосходящее x. Для любого числа y (положительного или отрицательного) и положительного Разработка математической модели и ПО для задач составления расписанияможно записать:

(14)

Страницы: 1, 2, 3, 4, 5, 6


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

© 2010.