Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

знакомо: это ограничение, выражающее границу суммы небазис­ ных (исходных) переменных. Обозначим индекс этой строки, через L. Ограничение имеет вид

Целочисленная константа ai0 выбирается достаточно большой, для того чтобы любое допустимое целочисленное решение удовле­ творяло уравнению (3) при неотрицательном целочисленном зна­ чении слабой переменной Хорошо известно, что добавление1 строки (3) позволяет получить допустимое решение двойственнойзадачи. М ы не будем подчеркивать здесь это свойство L -строки, однако оно играет важную роль в прямом алгоритме х).

столбце и в L -й строке. Дл я каждого столбца а;-определим новый вектор-столбец 2) г;- следующим образом:

( 4 )

Правило выбора ведущего столбца состоит в следующем: столбец. а8 выбирается в качестве ведущего, если rs является лексикогра­ фически минимальным среди столбцов rj, у которых a Lj > 0.

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

Потребуем, чтобы правило выбора производящей строки обла­ дало следующей особенностью:

Такое требование не означает, что условие ais ^ ai0 должно выполняться для всех i в некоторой таблице (что является необ­

ходимым и достаточным условием переходного цикла). Н а ш е требование допускает возможность того, что ais > ai0 для всех i

в некоторой таблице.

содержит т + 1 компонент. Вектор Tj будет использоваться для таблиц, которые расширены введением в систему (1) L-строки и тождественных соотношений для небазисных переменных. Предполагается, что tj содержит компоненты, соответствующие всем строкам расширенной таблицы. Един­ ственным ограничением на такое расширение является то, что нулевая строка таблицы всегда соответствует целевой функции.

Любое правило выбора производящей строки, обладающее свойством (5), будем называть допустимым правилом. Выполнения

свойства (5) достаточно х) для доказательства конечности. Однако само по себе свойство (5) еще не обеспечивает конструктивного способа получения допустимых правил выбора производящей строки. С помощью теоремы 17.1, изложенной ниже, и некоторых дополнительных рассуждений будет получен такой способ, позво­ ляющий: сформулировать допустимые правила.

Поскольку выбор производящей строки является задачей нетривиальной, по-видимому, должно существовать несколько строк, которые могут служить в качестве производящих. В предва­ рительных рассуждениях и в примере начала этой главы в качестве производящей использовалась ведущая строка симплекс-алго­ ритма. Эта строка всегда дает отсечение, которое является веду­ щей строкой с ведущим элементом, равным единице. По-видимому, в таблице существуют и другие строки, из которых могут быть получены отсечения с такими же свойствами. Допустим, что отсечение получается по формуле *2)

Строка и может стать производящей тогда и только тогда, когда

где 0S определяется из условия

= 1Н1П ai0

Определим множество V (s) как совокупность строк3), удовлетво­

ря ющ их условию (7).

х) Свойство (5) не самое слабое ограничение, которое можно исполь­ зовать для получения допустимых правил выбора производящей строки. Однако более слабые ограничения, по-видимому, потребуют более сложных построений, и поэтому мы используем свойство (5), которое просто форму­ лируется и является достаточным условием конечности. Другие формулировки можно найти у Гловера [76] и Юнга [225].

2) Полагая X = avs, как это делается в (6), мы получаем в качестве ведущего элемента 1. В отдельных случаях можно взять X <. avs и при этом

■строки v £ V (s), обладающей свойством (5). Заметим, что в пере­ ходном цикле 0S ^ 1. Поэтому ai0 ^ ais для всех i и, следова­

тельно, свойство (5) имеет место независимо от того, какую строку выбрать в качестве производящей. Таким образом можно сосредо­ точить внимание на выборе производящей строки в стационарных

Заметим, что из условий (8) и (5) можно вывести следующее заклю­ чение: если свойство (5) не выполняется, то существует бесконеч­ ная последовательность таблиц, в которых строка выбирается в качестве производящей. Поэтому необходимо доказать, что можно выбирать производящую строку среди строк с ais > ai0

a vj — j-й элемент строки,v, a avj — соответствующий коэффи­ циент строки v в следующей таблице. Если отсечение

& v j <C d v s •

Дл я того чтобы связать теорему 17.1 с нашими рассуждениями относительно правил выбора производящей строки, вначале

г) f — множество индексов небазисных переменных после преобразо­ вания.— Прим, перев.