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

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

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

(9)

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

	(10)

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

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

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

	(11)

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

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

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

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

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

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

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

при условиях

(12)

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

	(13)

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

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

(14)

где (ry – неотрицательный остаток от деления нацело y на ). В частности, . Поэтому если , то и r = 1. Если , то и r = 0.

Вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (12). Рассмотрим некоторое уравнение в t – таблице (опуская индекс строки) с a0

	(15)

где x – соответствующая компонента вектора , а - текущие небазисные переменные. Можно выразить x, a0 и aj, используя введенное выше представление (14):

(16)

(17)

Подставив выражения (16) и (17) в (15) и переставив члены, получим:

(18)

Поскольку , и на переменные x и наложено требование неотрицательности, левая часть уравнения (18) всегда неотрицательна. Рассмотрим выражение в правой части, заключенное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требованию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т.е.:

(19)

.

Целочисленная слабая переменная s является неотрицательной. Действительно, если бы s было отрицательным, т.е. принимало бы значения -1, -2, …, то умножение на сделало бы всю правую часть уравнения (18) отрицательной, в то время как левая часть неотрицательна.

Рассмотрим два случая и . Для и . Подставляя в уравнение (19) выражение для x из (15), получим:

	(20)

Полученное уравнение есть не что иное как отсечение Гомори. Для имеем и уравнение (19) приобретает вид:

(21)

Уравнение (21) должно выполняться для любого целочисленного решения задачи (12). Заметим, что если a0 в уравнении (21). Потому уравнение (21) может использоваться в качестве ведущей строки в симплекс-методе. В частности, всегда можно выбрать достаточно большим, так чтобы ведущий элемент в строке (21) стал равным –1, что позволит сохранить целочисленность таблицы. Выбор соответствующего будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве начального необходимо взять двойственно допустимое решение, которое можно получить добавлением ограничения xn+m+1=M – x1 - - … - xn 0, где M – достаточно большая константа, и проведением одной итерации с добавленной строкой и с лексикографически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов:

Шаг 0. Начать с двойственно допустимой матрицы A0 в уравнении (13), элементы которой – целые числа (матрица A0 может содержать и нецелые элементы, об этом см. [2], стр. 306).

Шаг 1. Среди строк с ai0i00 (i=1, …, n+m), то задача решена.)

Шаг 2. Выбрать (правило выбора будет описано дальше) и написать внизу таблицы дополнительную строку

Эта строка выбирается в качестве ведущей.

Шаг 3. Провести шаг двойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться к шагу 1.

Доказательство конечности алгоритма см. [2], стр. 303-304.

Правило выбора формулируется следующим образом.

Шаг 0. Пусть строка с номером v является производящей.

Шаг 1. Пусть - лексикографически минимальный столбец среди столбцов с avj

Шаг 2. Для каждого avj - наибольшее целое, такое, что (лексикографически меньше).

Шаг 3. Пусть , а (строка v - производящая). Тогда

.

Шаг 4. Положить для avj

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

Подробнее об алгоритме можно прочитать в [2], стр. 300.

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

Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых целочисленных решений. Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Основное отличие этого алгоритма состоит в том, что в качестве ведущей строки используется отсечение Гомори с ведущим элементом, равным –1. Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. Использование такого отсечения в качестве ведущей строки сохранит после итерации двойственную допустимость и целочисленность таблицы.

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

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

(22)

при условиях

,

(целые) (k=1,…,n),

где a0j, aij и ai0 – целые числа и ai00.

(23)

Предположим, что столбец выбран в качестве ведущего и строка v – ведущая строка в итерации симплекс-метода, т.е. для всех строк I, в которых ais>0. Прежде чем провести процедуру исключения Гаусса в симплекс-методе, добавим к таблице отсечение Гомори, полученное из строки v:

где J – множество индексов небазисных переменных в (22), sk – новая (базисная) слабая переменная и - неопределенная (временно) положительная константа.

Заметим, что если положить = avs, отсечение (23) будет обладать двумя важными свойствами. Во-первых,

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