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

![]()

Условия (12) могут быть записаны как
|
![]()
Предположим, что для t=0 (т.е. для исходной
таблицы) все aij – целые и столбцы
(j = 1 ,…, n) – лексикографически положительны. Тогда все столбцы на протяжении
вычислений остаются лексикографически положительными.
Прежде чем изложить способ получения дополнительного
ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает
наибольшее целое число, не превосходящее x. Для любого числа y
(положительного или отрицательного) и положительного
можно записать:
|
где
(ry – неотрицательный остаток от деления нацело y на
). В частности,
. Поэтому если
, то
и r = 1. Если
, то
и r = 0.
Вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (12). Рассмотрим некоторое уравнение в t – таблице (опуская индекс строки) с a0<0:
|
![]()
где x – соответствующая компонента вектора
, а
- текущие небазисные
переменные. Можно выразить x, a0 и aj,
используя введенное выше представление (14):
|
|
Подставив выражения (16) и (17) в (15) и переставив члены, получим:
|
Поскольку
,
и на переменные x и
наложено требование
неотрицательности, левая часть уравнения (18) всегда неотрицательна. Рассмотрим
выражение в правой части, заключенное в фигурные скобки. Коэффициенты в этом
выражении представляют собой целые числа, а переменные подчинены требованию
целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим
его через s, т.е.:
|
.
Целочисленная слабая переменная s является
неотрицательной. Действительно, если бы s было отрицательным, т.е.
принимало бы значения -1, -2, …, то
умножение на
сделало
бы всю правую часть уравнения (18) отрицательной, в то время как левая часть
неотрицательна.
Рассмотрим два случая
и
. Для
и
. Подставляя в уравнение (19) выражение для x из (15),
получим:
|
![]()
Полученное уравнение
есть не что иное как отсечение Гомори. Для
имеем
и уравнение (19)
приобретает вид:
|
Уравнение (21) должно выполняться для любого целочисленного
решения задачи (12). Заметим, что если a0<0, то
в уравнении (21).
Потому уравнение (21) может использоваться в качестве ведущей строки в
симплекс-методе. В частности, всегда можно выбрать
достаточно большим,
так чтобы ведущий элемент
в строке (21) стал
равным –1, что позволит сохранить целочисленность таблицы. Выбор соответствующего
будет влиять на
скорость сходимости алгоритма. Прежде всего опишем сам
алгоритм. В качестве начального необходимо взять двойственно допустимое
решение, которое можно получить добавлением ограничения xn+m+1=M – x1 - - … - xn
0, где M – достаточно
большая константа, и проведением одной итерации с добавленной строкой и с
лексикографически минимальным столбцом, взятыми в
качестве ведущих. Алгоритм состоит из следующих шагов:
Шаг 0. Начать с двойственно допустимой матрицы A0 в уравнении (13), элементы которой – целые числа (матрица A0 может содержать и нецелые элементы, об этом см. [2], стр. 306).
Шаг 1. Среди строк с ai0<0 (i=1, …, n+m) выбрать
строку с наименьшим значением i; эта строка станет производящей. (Если ai0
0 (i=1, …, n+m), то задача
решена.)
Шаг 2. Выбрать