Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 67
Текст из файла (страница 67)
Однако нулевая строка полностью определяется базисом, поэтому из того, что а, ! 7., следует, что никакой базис не может повториться. Отсюда в свою очередь вытекает, что снмплекс-алгоритм останавливается после конечного числа замещений. Д Конечно, можно ожидать, что аналогичный результат справедлив и для двойственного симплекс-алгоритма, поскольку иа самом деле это замаскированный прямой симплекс-алгоритм (см, ~ 3.7). Теорема 14. ! 1лексикографические правила устранения зацикли- вания для прямого симплекс-метода).
Пусть в начале прямого симплекс-алгоритма все строки, следующие за строкой стоимости, лексикогрофически положигпельныс а,>0, г=!, ..., т, Тогда эти строки остаются лексикографически положительными, нулевая строка строго лексикогрофически возрастает (записывается как ао1Ц и пРЯмой симплекс-алгоРитм останавливаетсЯ после конечного числа замещений, если используются следуюи!ие правила выбора ведущих элементовс а) выбрать любой столбец з, токой, что а„О; б) выбрать строку с=«, для которой достигается 14.З.
Конечность дробного двосоо>ленного алгоритма З47 Теорема 14.2 (лексикографические правила устранения зацикли- вания для двойственного симплекс-метода), (?усть в начале двой- ственного симплекс-алгоритма все столбцы, следуюи(ие за нулевым столбцом, лексикографически положительны: А >О, 1=-1,..., и. Тоеда эти столбцы остаются лексикографически положительными, нулевой столбец строго лексикографически убывает (А, 1 Б) и двой- ственный симплекс-алгоритм останавливается после конечного числа замещений, если используются следующие правила выбора ведущих злементов: а) выбрать любую строку г, такую, что а„,(0, б) выбрать столбец !'=з, для которого достигается !ех->пах ~ — 1. г/ (14,34) Доказал>ельство.
Доказательство втой теоремы оставляем читателю в качестве упражнения; оно использует ту же технику, что и доказательство теоремы 14.! (сч. задачу 8). () Мы просим также читателя объяснить, как сделать все строки в начале прямого алгоритма лексикографически поло>кительнымн, объяснить, как сделать все столбцы в начале двойственного алгоритма лексикографически положительными, и показать, что правило (14.34) приводит к однозначному результату (см. задачи 9 и! 0). 4 4.3 Конечность дробного двойственного алгоритма Лексикографический метод гарантирует конечность как обычного симплекс-алгоритма, так и дробного двойственного алгоритма.
Сформулируем зто в виде теоремы. Теорема 14.3. Будем следующим образом осуществлять выбор в дробном двойственном алгоритме для задачи ЦЛП (см. рис, 14,3): а) в качестве производящей строки выбираем первую строку с неотрицательным значением а;„; б) используем лексикогрофический вариант двойственного силы алекс-алгоритма. Тогда если для исходной задачи имеется верхняя граница стоимости г допустимого реи>ения, пто алгоритм останавливается после конечного числа шагов, выдава целочисленное решение или определяя, ипо в исходной задаче нет допустимых целочисленных решений.
Ги 14. Алгрршпм рросекающев клрскосрои Доказаспельсспво (Соо!, Оо2!. Назовем основной цикл в алгоритме на рис. 14.3 реоппгилсизацией, и пусть после 1-й реоптимизации получается таблица А' со столбцами А1. Тогда алгоритм порождает последовательность нулевых столбцов, монотонно лексикографически убывающих, поскольку строки к таблице всегда добавляются снизу: Ао> Ао> Ао> °" (14.35) По условию первая компонента а„= — г ограничена снизу, поэтому последовательность а„сходится к некоторому числу, скажем свор, которое можно записать в виде Нооо = ( свор ! + 'оо.
(14.38) После некоторого конечного числа реоптимизаций а,', становится меньше, чем ( нооо ) +1, и для некоторого (=Й можно записать 4.= ! Ш.о )+Йо. (14. 37) По правилу (а) следующей порождающей строкой будет строка О, и к таблице добавляется отсечение (!.4. 38) сов Затем производится замещение с использованием двойственного симплекс-алгоритма, при котором некоторый столбец, скажем р, вводится в базис. После этого замещения получаем (14.39) ор В оптимальной таблине двойственного симплекс-алгоритма а,' >О, (14.40) поэтому это число не меньше, чем его дробная часть пор Ро !Ор (14 41) Тогда из (!4.39) вьпекает ао ( аоо — )о, = ( аоо ) = ~ св„) . (14. 42) Так как последовательность а(о сходится к поем это означает, что, начиная с этого момента, а' = ! ш„) — целое, Векторы А,' лексикографически убывают, и мы показали, что с некоторого момента первая компонента остается фиксированной (целочисленной), поэтому далее вторая компонента монотонно не возрастает.
Она ограничена снизу нулем, ибо в противном случае двойственный симплекс-алгоритм работал бы неправильно. Поэтому к а'„можно применить приведенные выше рассуждения. Однако, для того чтобы проходили шаги, следующие за неравенством 349 И.4. Други аагораямм ояеекаяа4ев аооекоеяа (14.40), нужно показать, что (14 АЗ) Но аоео должно оставаться фиксированным, откуда следует, что а," =О, откуда в свою очередь следует неравенство (14.43), поскольку А~)0. Поэтому и,'. становится целым после конечного числа шагов. Можно продолжать эти рассуждения, спускаясь вниз по столбцу О. В результате получим, что все компоненты в конце концов принимают целочисленные значения, после чего алгоритм останавливается.
Единственно, когда еще возможна остановка алгоритма, — это когда двойственный симплекс-алгоритм находит, что двойственная задача пе ограниченна и, следовательно, что исходная задача ЦЛП недопустима. () Во избежание накопления неопределенного числа строк и с1олбцов в дробном двойственном методе обычно выбрасывают переменную недостатка ь соответствующую отсечению Гомори, если такая переменная в неко~орый момент выполнения алгоритма должна войти в базис.
Это означает, что число строк никогда не превосходит п— числа исходных переменных, — поэтому число используемых отсе. чепий в любой момене времени ие превосходит и — пь Это усовершенствование пе влияет на доказательство коиечносги алгоритма (см. задачу 4). На самом деле при такой модификации нетрудно получить экспоненциальную оценку числа итераций, выполняемых алгоритмом (см. задачу !!).
4 4.4 Другие алгоритмы отсекающей плоскости С дробным двойственным алгоритмом связаны две основные проблемы: одна ~з них возникает из-за того, что он дробный, дру~ая— из-за того, что он двойственный. Попытки обойти эти проблемы привели к новым классам алгоритмов, которые мы сейчас кратко обсудим. (См. разд. «Комментарии и ссылки».) Тот факт, что в дробном двойственном алгоритме необходимо делить одно целое число иа другое, означает, что при реализации этого алгоритма в цифровой вычислительной машине элементы таблицы будут храниться лишь с конечной точностью (вспомините обсуждение, сопровождавшее алгоритм эллипсоидов; разд. 8 7.4). Если 1 дели~ся на 3, результат хранится в виде двоичного числа с некоторым конечным числом разрядов; если затем это число умножается на 3, мы не вернемся к значению 1. (Читатель может проверить это на карманном калькуляторе; получается 0.9999999 ) Этот эффект накапливается от этапа к этапу, и в результате может оказаться затруднительным решить, являешься ли данный элеменг целым или нет — различие, которое необходимо для порождения Гл.
14. Алгоритм отсгкиющгд плоскости отсечений. В связи с этим построены полностью целочисленные алгоритмы, в которых ведущие элементы всегда имеют значение !. Кроме всего прочего, дробный двойственный алгоритм является двойственным алтари~мам и не порождает прямого допустимого ре. шения, пока не достигнет оптимальности.
Сбычно в этом нет проблемы, но, к сожалению, алгоритмы для задач ЦЛГ! часто останавливаются, не достигнув оптимальности, поскольку трудно предсказать время их работы, а это время может очень сильно меняться в зависимости от входных данных задачи. Если это происходит в двойственном алгоригме, мы оказываемся в неприятной ситуации, затратив определенное количество машинного времени и не получив никакого полезного результата; мы не получаем ни целочисленного, ни допустимого решения нашей исходной задачи. С другой стороны, алгоритм отсекающей плоскости, работающий с подоптимальными решениями, которые одновременно целочисленны и допустимы относительно исходных ограничений, позволяет использовать результат преждевременной остановки.
Такие алгоритмы действительно построены и обычно называются прямыми целочисленными алгоритмами отсекающей плоскости. Задачи и Покажите, что в решении, использующем отсенающие плоскости, опи. санном в примере (4.2, нарушаются правила для лексикографическаго двоИс~вен. ного алгоритма, приведенные позднее в теореме )4.3. Решите задачу заново, придерживаясь лексикографнческих правил.
Выразите новые отсечения через исходные переменные х, и хз. 2. Предположим, что некоторая задача целочисленного линейного программирования получается добавлением переменных цедостатиа к задаче пип с'х, Ахчцз, х тк О целочисленна, где А, Ь и с — целочисленны. Назовем переменные х исходными переменными. Пусть з — переменная недостатка, соответствующая отсечению Гамори в любом месте алгоритма отсекающей плосностн. докажите, что з можно выразить в виде линейной иомбинапии исходных переменных с целыми коэффициентами плюс целочисленная константа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
