Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 64
Текст из файла (страница 64)
аьв от.в Следовательно Яо должна быть конечной. Аналогично моя<но показать, что последовательность 8а должна быть конечной. Итак, 8 является конечной последовательностью в противоречие с нашим допущением о том, что первая компонента г, не изменяет своего значения на неограниченной последовательности стацио- нарныХ циклов. ° Доклзлткльство ткогнмы $7.6. Пусть г — значение в в первой аЬ таблице последовательпости стационарных циклов. Если в ней аь, ( 0 для всех 7 ~ У, то таблица оптимальна по теореме $7.2. Пусть пайдется аь,)0. По теореме 17.5 для всех последующих таблиц выполпится условие ~" )г. В силу правила выбора аьв производящей строки через конечное число преобразований будет получена таблица, в которой аь,(аьо.
'Хаким вбразом, через конечное число шагов будет получена таблица, для которой одновРеменно аьв~~аьо, о' )г и аь, > О. ПосколькУ элементы табаьв лиц — целые числа, то существует не более чем конечное число !7.1. ВыВОд соотнОшкпий и полспвпия 305 отрицательных аначекий отношения — '. В силу того, что аг, аса должно строго увеличиваться через конечное число преобразований (теорема 17.5), конечного числа шагов достаточно, чтобы исчерпать все воэмшкные отрицательные значения отношения — *. ат,, Следовательно, через конечное число преобразований ведущий столбец станет лексикографически неотрицательным, что влечет за собой оптимальность таблицы.
° 17.4. Вывод соотношений и пояснения при условиях 1хзд + А"х,„= аа„, хз„, хд,д)0. (27) В (27) ад — вектор-строка относительных оценок целевой фупйция (т. е. значений г! — с!), аа„— вектор констант (не содержащий текущего значения целевой функции) и Ад — матрица, составленная из элементов таблицы, соответствующих небазнсным переменным, за исключением коэффициентов целевой фУнкции ада.
Выпишем задачу. двойственную для (27): максимизировать %'даад при условиях Ад» ~о (28) Последовательность таблиц в прямом алгоритме индуцирует последовательность двойственных задач вида (28). Лексикографпческим обобщением задачи (28) является задача В этом параграфе обсуждаются два вопроса: во-первых, будут даны интерпретации тех идей, которые были использованы и при доказательстве конечности в предыдущем параграфе и; во-вторых, будут выведены соотношения, которыми мы пользовались для доказательства конечности. Существует два основных способа проинтерпретировать рассуждения, которые имели место при доказательстве теорем: в первом случае используются 'идеи двойственпости, во втором— геометрические идеи. Рассмотрим последовательность таблиц, получающу1ося в результате последовательности (стационарных) циклов в прямом алгоритд!е.
Запишем й-ю таблицу в форме задачи линейного программирования: минимизировать 0 адхмд Гл гь пРямОЙ АЯГОРитм максимизировать Раз прн условиях РА< [' (29) где Р— матрица с лексикографнческн неположительными столбцами. Вектор Раз требуется минимизировать в лексикографическом смысле, а неравенство РА<[ ] следует понимать таким образом: каждый столбец матрицы РА лексикографически меньше или равен соответствующему столбцу матрицы ["] Ро Р7 ГА = Покажем, что такое решение является допустимым для (29).
Поскольку г, ( 0 (по теореме А7.2). все столбцы матрицы Р лексикографически неположительны. Столбец с индексом 7 в мат- Допустимое решение задачи (29) содержит в первой строке матрицы Р допустимое рея7енне задачи (28). Подобным же образом оптимальное решение задачи (29) содержит оптимальное решение задачи (28). Индекс й в (29) опущен, вместе с тем очевидяо, что последовательность (стационарных) циклов индуцирует последовательность задач (29).
Использованные в доказательстве конечности параметры г;, ро Ь7 и бы из параграфа 17.3 имеют особое значение в задачах (29). Рассмотрим решение Р задачи (29), построенное следующим обрааом. Все компоненты Р равны нулю, кроме столбца, соответствующего Ь-строке матрицы А; пусть этот единственный ненулевой столбец из Р задается как ыя. вывод соотношкнии и пояснкния 367 рице РА=(0, г,) А') равен атп г, и в силу (22) равен бег бм аы Так как Ат ) 0 (по теореме 17.3), то из (22) следует, что все столбцы ат из А в (29) подчиняются соотношению аь;г, ( и наше решение Р = (О, г,) есть допустимое решение задачи (29). Таким образом видно, что бп из (21) являются слабыми переменными задачи (29), а р; — основные составляющие допустимого решения задачи (29).
В силу нашего определения Р целевая функция Рае принимает вид г,аье. Поскольку аье имеет постоянное значение на последовательности стационарных циклов, в то время как г, лексикографически возрастает, мы получаем последовательность улучшающихся решений для (29). Наконец, когда будет получена таблица, в которой первая компонента г, неотрицательна, то для задачи (28) будет найдено допустимое решение с нулевым значением целевой функции. Это решение устанавливает ниятнтою нулевую границу для оптимального решения задачи (27), которое получается, если положить хм = О. Следовательно, в этой таблице содержится оптимальное решение задач (27) и (28). Связь прямого алгоритма с двойственной задачей можно уста,- новить при помощи следующих замечаний: ведущий столбец всегда соответствует ограничению задачи (29), выполняющемуся как равенство '), т. е. условие А, =. 0 всегда выполняется. В ходе решения возникает последовательность монотонно улучшающихся решений двойственных задач (28) и (29).
Возможно, что эти короткие замечания помогут 'лучше понять значение используемых в $17.3 конструкций. Определеппя (18), (19), (20) и (21) полезны также при построении сравнительно простой геометрической интерпретации т) Столбец гв может стоять иа лтобем л~есте в Р, что яе влияет яа результат.— Прил. иерее. е) Этот факт содержится и в условии задачи (29).— Прил. ред.
а) Те есть в (29) слева в справа иа ~м месте. стеит один и тот вие столбец.— Прил. ред. гл. !ь пРямОЙ ллГОГитм зсв изменения таблиц в последовательности циклов прямого алгоритма. Элементы таблицы мокшо рассматривать, как множество вектор-столбцов (а) ! у с Х), которое соответствует множеству точек в (и + 2)-мерном евклидозом пространстве. Определение (20), из которого следует векторное равенство (22), можно интерпретировать как изменение начала координат, т. с. записав (22) как а,=ах;г,+А;, можно сказать, что вектор а! выражен через отклонение Аг от точки ах)тю раСПОЛОнссписй Па ЛУЧЕ С НанраВЛя7Ощни ВЕКтОрОМ Г,. Такое представление вектора а, в терминах А; и аь,г, подчеркивает определенные геометрические соотношения в структуре таблиц прямого алгоритма. Во-первых, отметим, что лшожество точек (а, ) 7' б У) в любой таблице прямого алгоритма содержится в полупространстве, которое включает начало координат и вектор г„расположенный на границе этого полупространства.
Для доказательства этого утверждения достаточно построить ненулевую вектор-строку и' таким образом, чтобы и'г, = 0 и и'ау~О для всех 7'г Х!). Из равенства а; =- аьгта+ Аг тогда будет следовать г Р и а)=виги г, ';и'А;. Чтобы построить и', полагаем ие =- 1, и, = иэ = ... = и„= 0 и найдем иь, так чтобы и'г,=О. Поскольку А; >р О для всех у' й У, получим бе! 7 0 н по определениго (см.
(18) и (20)) имеем бьг = 0 для всех 1 Г Х. Отсюда н'Аг ) О, что и требовалось '). Во-вторых, заметим, что перемещение любой точки а, в точку ам которое происходит в результате одного преобразования, имеет определегшый геометрический смысл. Равенства (22) н (23) показыва7от, что движение от точки аг к а, осуществляется параллельно вектору г, и, слсдоватольно, параллельно гиперплоскости, !) Тогда и' — ортогоналеп г, к все а (1 б У) составляют с и' нетуиой угол, т, е..а левгат ио одну сторону с г, от гкиер7жоскостк! порождаемой вектором и'.— Прим.
ред. т) Если иоложкть и! =-,е для ! = О, 1,..., а в найти кь, так чтобы выполнялось и'г, = О, то можно до77азать более сильное утверждение о том, что и'а = и'а ) О д:7я всех 1 Ф а для некоторого иоложвтетьвого к достаточного малого е. 17ХО ВЫВОД СООТНОШЕНИЙ И ПОЯСНЕНИЯ 369 определяемой вектором и'. Справедливость утверждения следует из того, что ат имеет то же отклонени9 Л1 от аьтг„что и ат от аьтг,. Этот факт можно доказать и алгебраически, зычтя (22) из (23) и получив а; — а1 = (аьз — аьт) гм ам=аи — арта1, (1С Х), аьз = аьг — ар1аьв, (30) (31).
где р — индекс ведущей строки. Домножив (31) на рь получим Р1ас1 = Р1аы.— ар1Р1аь' Используя (18) и (20), имеем р;а„= ан — Ьн — ар1а1„ после чего подстановка из (30) дает р1И т=а11 — 6». (32) Остается заметить, что (23) является векторной формой соотношения (32). Формулы (24), (25) и (26) получаются следующим образом. В соответствии с (22) аь.;г- = ат — Л1. 7 д (33) 24 т. хт откуда видно, что вектор а1 — а1 отличается от г, скалярным множителем. Доказательство конечности прямого алгоритма показывает, что полупространство, содержащее множество (ат ) 1 Е У1, совпадет с полупространством, определяемым из условия лат ) 0 для ВСЕХ 7'Е Х. Таким образом, можно представить процесс решения с помощью прямого алгоритма как построение последовательности перемещений точек в полупространстве, содержащем все точки (а1 ( у ~ У).
Эта последовательность обрывается тогда, когда в полУпРостРанстве соДеРжатсЯ только такие вектоРы аго У которых аш -. О. Более подробную картину сдвигов в полупространстве, происходящих от таблицы к таблице (которую мы не будем описывать здесь), монгно получить, анализируя (24), (25) и (26). Этот параграф заканчивается выводом соотношений (22)— (26). Формула (22) следует из (19), (20) и (21); (22) фактически является просто векторной формой скалярных уравнений из (20). Для получения (23) воспользуемся формулами симплексного преобразования, используемыми в прямом алгоритме: Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
