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

Заметим, что если положить

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

Это означает, что прямая допустимость таблицы сохраниться, еслииспользовать отсечение (23) в качестве ведущей строки. Во-вторых,

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

Эти идеи послужили основанием прямого алгоритма вцелочисленном программировании:

Шаг 0. Начать со столбцовой таблицы, в которой a_i₀

0 (i1) и все элементы a₀_j, a_ijи a_i₀ – целые.

Шаг 1. Проверить выполнение условий a₀_j

0 (j1); если они выполнены, то конец,текущее базисное решение оптимально; если нет – перейти к шагу 2.

Шаг 2. Выбрать ведущий столбец s с a₀_si₀/a_is среди строк с a_is> 0. Эта строка служит производящей дляотсечения Гомори.

Шаг 3. Получить отсечение Гомори из производящей строки идописать ее внизу таблицы, т.е. добавить к ограничениям задачи уравнение (23),где

Шаг 4. Произвести преобразование таблицы, используяотсечение (23) как ведущую строку. Слабая переменная s_k в (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). Как только vV(s), вернуться к 2.

Правило 2.

1. Пусть V_t(s) – множество V(s),соответствующее t-й таблице. Если V_t(s) содержит более одного элемента: V_t(s) = {v₁, v₂, …, v_k₊₂}, то в качестве производящей выбрать такую строку

, что в последовательности множеств V₁(s₁), V₂(s₂), …, V_t(s) строка появилась раньше (непозднее) остальных и затем сохраняласьвплоть до V_t(s); перейти к 2.

2. Последовательно выбирать строку v, взятую в 1.,до тех пор, пока

. Как только , вернуться к 1.

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

2.2.3.ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСА

Решение каждым из приведенных выше методов можетпроизводиться только в том случае, если задача линейного программирования является или прямо, или двойственнодопустимой. Такая допустимость означает наличие начального допустимого базиса висходной задаче. Если задача допустима и прямо, и двойственно, то полученноерешение – оптимально. В большинстве случаев после постановки задачиоказывается, что она не допустима ни прямо, ни двойственно. Поэтому приведемалгоритм получения начального допустимого базиса.

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

минимизировать

при условиях

Все b_i можно сделать неотрицательными, умножив, если надо, соответствующееуравнение на –1. Тогда можно добавить в каждое уравнение искусственнуюпеременную

(искусственныепеременные должны быть неотрицательными) таким образом, чтобы из искусственныхпеременных образовать начальный базис: