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

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

Прежде чем доказывать эти теоремы, полезно ввести простое определение и вывести из него несколько заключений.

Пусть аю —число, стоящее в строке i и нулевом столбце в первой таблице последовательности стационарных циклов. Тогда

вует лишь конечное число возможных значений отношения —— .

х) Такое предположение не нарушает общности рассуждений, поскольку далее будет.показано, что ни одна компонента вектора rs не может бесконеч­ ное число раз увеличиваться, в то время как предыдущие компоненты этого вектора остаются с постоянным значением. Поэтому несущественно, рас­ смотрим ли мы в качестве первой увеличивающейся компоненты 2-ю или г'-ю.

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

при условиях

(29)

где Р — матрица с лексикографически неположительными столб­ цами. Вектор Ра0 требуется минимизировать в лексикографи­

ческом смысле, а неравенство

а0

РА

А

следует понимать таким образом: каждый столбец матрицы РА лексикографически меньше или равен соответствующему столбцу матрицы

”а°“

А‘

Допустимое решение задачи (29) содержит в первой строке матрицы Р допустимое решение задачи (28). Подобным же образом оптимальное решение задачи (29) содержит оптимальное решение задачи (28). Индекс к в (29) опущен, вместе с тем очевидно, что последовательность (стационарных) циклов индуцирует последо­ вательность задач (29).

Использованные в доказательстве конечности параметры rj, рг, А; и бл из параграфа 17.3 имеют особое значение в задачах (29).

Рассмотрим решение Р задачи (29), построенное следующим обра­ зом. Все компоненты Р равны нулю, кроме столбца, соответствую­ щего L-строке матрицы А; пусть этот единственный ненулевой столбец из Р задается как

/Ро N

Pi

Ртг

\Рь/

Покажем, что такое решение является допустимым для (29).

Поскольку rs < О (по теореме 17.2), все столбцы матрицы Р лексикографически неположительны. Столбец с индексом j в мат­

и наше решение Р = [0, rs] есть допустимое решение задачи (29). Таким образом видно, что би из (21) являются слабыми перемен­ ными задачи (29), а р; — основные составляющие допустимого решения задачи (29).

В силу нашего определения Р целевая функция Ра0 принимает вид г8аьоПоскольку ач, 0 имеет постоянное значение на последо­

вательности стационарных циклов, в то время как rs лексикогра­ фически возрастает, мы получаем последовательность улучшаю­ щихся решений для (29). Наконец, когда будет получена таблица, в которой первая компонента rs неотрицательна, то для задачи (28) будет найдено допустимое решение с нулевым значением целевой функции. Это решение устанавливает нижнюю нулевую границу для оптимального решения задачи (27), которое получается, если положить x N = 0. Следовательно, в этой таблице содержится оптимальное решение задач (27) и (28).

Связь прямого алгоритма с двойственной задачей можно уста­ новить при помощи следующих замечаний: ведущий столбец всегда соответствует ограничению задачи (29), выполняющемуся как равенство 3), т. е. условие As = О всегда выполняется. В ходе решения возникает последовательность монотонно улучшающихся решений двойственных задач (28) и (29). Возможно, что эти корот­

бец.— П р и м . р е д .