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

Эта строка выбирается в качестве ведущей.
Шаг 3. Провести шаг двойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться к шагу 1.
Доказательство конечности алгоритма см. [2], стр. 303-304.
Правило выбора
формулируется
следующим образом.
Шаг 0. Пусть строка с номером v является производящей.
Шаг 1. Пусть
- лексикографически
минимальный столбец среди столбцов с avj<0.
Шаг 2. Для каждого avj<0
пусть
- наибольшее целое,
такое, что
(лексикографически
меньше).
Шаг 3. Пусть
, а
(строка v -
производящая). Тогда
.
Шаг 4. Положить
для avj<0.
Правило выбора
, описанное выше, позволяет сделать ведущий элемент равным
–1, при этом сохраняется двойственная допустимость таблицы и
в то же время нулевой столбец будет максимально лексикографически
уменьшаться.
Подробнее об алгоритме можно прочитать в [2], стр. 300.
2.2.2 Прямой алгоритм целочисленного программированияТермин “прямой”, примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному решению посредством получения последовательно “улучшаемых” решений. Каждой из этих решений допустимо в том смысле, что оно удовлетворяет как линейным ограничениям, так и условию целочисленности. Одним из вероятных достоинств алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения.
Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых целочисленных решений. Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Основное отличие этого алгоритма состоит в том, что в качестве ведущей строки используется отсечение Гомори с ведущим элементом, равным –1. Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. Использование такого отсечения в качестве ведущей строки сохранит после итерации двойственную допустимость и целочисленность таблицы.
Оказывается, можно аналогично модифицировать симплекс-метод таким образом, чтобы получить алгоритм, который сохраняет прямую допустимость и целочисленность таблиц. Для описания вычислительной процедуры рассмотрим следующую задачу целочисленного программирования:
максимизировать
|
при условиях
,
(целые) (k=1,…,n),
где a0j, aij и ai0 – целые числа и ai0
0.
|
для всех строк I, в которых ais>0.
Прежде чем провести процедуру исключения Гаусса в симплекс-методе, добавим к
таблице отсечение Гомори, полученное из строки v:

где J – множество индексов небазисных переменных в (22), sk –
новая (базисная) слабая переменная и
- неопределенная
(временно) положительная константа.
Заметим, что если положить
= avs, отсечение (23) будет обладать двумя важными свойствами. Во-первых,
Это означает, что прямая допустимость таблицы сохраниться, если
использовать отсечение (23) в качестве ведущей строки. Во-вторых,
, т.е. ведущий элемент равен 1 (если отсечение используется
как ведущая строка). Легко удостовериться (путем исследования формул изменения
базисных переменных), что преобразование симплексной таблицы с единичным
ведущим элементом сохраняет целочисленность элементов симплексной таблицы.
Эти идеи послужили основанием прямого алгоритма в целочисленном программировании:
Шаг 0. Начать со столбцовой таблицы, в которой ai0
0 (i
1) и все элементы a0j, aij
и ai0 – целые.
Шаг 1. Проверить выполнение условий a0j
0 (j
1); если они выполнены, то конец,
текущее базисное решение оптимально; если нет – перейти к шагу 2.
Шаг 2. Выбрать ведущий столбец s с a0s< 0. Выбрать строку v по правилу проверки отношения ai0/ais среди строк с ais> 0. Эта строка служит производящей для отсечения Гомори.
Шаг 3. Получить отсечение Гомори из производящей строки и
дописать ее внизу таблицы, т.е. добавить к ограничениям задачи уравнение (23),
где
.
Шаг 4. Произвести преобразование таблицы, используя отсечение (23) как ведущую строку. Слабая переменная sk в (23) станет небазисной. Вернуться к шагу 1.
Доказательство конечности алгоритма см. [2], стр. 346-353.
Поскольку выбор производящей строки является задачей нетривиальной, по-видимому, должно существовать несколько строк, которые могут служить в качестве производящих. В предварительных рассуждениях в качестве производящей строки использовалась ведущая строка симплекс-метода. Эта строка всегда дает отсечение, которое является ведущей строкой с ведущим элементом, равным единице. По-видимому, в таблице существуют и другие строки, из которых могут быть получены отсечения с такими же свойствами. Допустим, что отсечение получается по формуле:
|
Строка v может стать производящей тогда и только тогда, когда
|
где
определяется из условия

Определим множество V(s) как совокупность строк, удовлетворяющих условию (25).
Следующие два правила представляют собой примеры допустимых правил выбора производящей строки:
Правило 1.
1. Составить последовательный конечный список индексов строк таким образом, чтобы индекс каждой строки вошел в него по меньшей мере один раз. Перейти к 2.
2.
Если список пуст или не содержит
ни одного индекса из V(s), вернуться к 1.; в противном случае найти в списке первый индекс v
V(s). Выбрать строку v как
производящую. Вывести из списка индекс v и все предшествующие ему
индексы. Перейти к 3.
3.
Последовательно выбирать строку v, взятую в 2.,
как производящую, до тех пор, пока v
V(s). Как только v
V(s), вернуться к 2.
Правило 2.
1.
Пусть Vt(s) – множество V(s),
соответствующее t-й таблице. Если Vt(s) содержит более одного элемента: Vt(s) = {v1, v2, …, vk+2}, то в качестве производящей выбрать такую строку
, что в последовательности множеств V1(s1), V2(s2), …, Vt(s) строка
появилась раньше (не
позднее) остальных
и затем сохранялась
вплоть до Vt(s); перейти к 2.
2.
Последовательно выбирать строку v, взятую в 1.,
до тех пор, пока
. Как только
, вернуться к 1.
Подробнее об алгоритме можно прочитать в [2], стр. 344.
2.2.3. ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСАРешение каждым из приведенных выше методов