Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 32
Текст из файла (страница 32)
Кроме того, согласно зеореме 2.10, смежные невырожденные бдр задачи ЛП соответствуют вершинам, соединенным ребром (1-мерной гранью) многогранника (например, вершины (О, О, !) и (О, 1, ! ) на рис. 8.2 (а) смежны). Пусть теперь многогранник ориентирован так, что при движении вверх стоимость убывает. Тогда нам нужно найти последовательность, содержащую экспоиенциальное число вершин, в которой каждая вершина смежна со следующей вершиной и каждая вершина выше, чем предыдущая. Но прежде всего мы должны иметь многогранник с экспоненциальным числом вершин. Примером такого многогранника является киб: 0<хе<1, 1=1, 2, 3 (рис. 8,2(а)).
В 3-мерном кубе шесть граней — многие игры основаны на этом фундаментальном факте — и восемь вершин. В общем случае нетрудно видеть, что а'-мерный куб (или с(-гиперкуб), определяемый неравенствами 0<хе<1, 1=1, 2, ..., д, имеет 2д граней, по одной для каждого неравенства, и 2а вершин, соответствующих присвоению единиц любому подмножеству пере- менных из (ям кь ..., ха) и нулей остальным переменным. Гл. 8. Алгориосмы и слосссиоссиь 172 гс1 са) с,с',1 Рис. В.2. В.в.
Сссмнлеке-олеорссым не м«лнеоссн нолнномоольным 17.3 Многогранник, кспорый мы хотим построи~ь, очень похож на куб (рис. 8.2(б)). Он определяется неравенствами 1 э х, и е, 1 †э ; ~ )хс.-э еху , ! = 2, 3, ..., д, (8.1) для некоторого е, такого, что О(з -'/,. Таким образом, в пределе при е -» О этот многогранник стремится к и-мерному кубу; т. е.
многогранник (8 !) является возмущением д-мерного куба. На рис. 8.2 приведен пример для 3-мериого случая вместе с указанием «длинной» последовасельнос» и смежных вершин с убывающей стоимостью. Ниже мы аналитически ус!аноним существование такой последовательности. Для приведения (8 1) к стандартной форме добавим с( переменных недостатка и д переменных избытка.
Тогда т=2д и п=3«(. Будем максимизировать хл. Полностью эта задача ЛП запишется в виде пп'и — х„, х,— г,=а, х,+я,=1, 8.2 х — ех — г =О ( ) / 'У-с х,+ехс,+я =1, (=2, 3, ..., с(, хы г~, яс ~) О, ! = 1, ..., с(. Какие бдр имеюгся в задаче (8.2)? Следующая лемма дает ответ на этот вопрос Лемма 8.1, Множеспсво допустимых базисов задачи (8.2) совпадает с семейством подмножеств множества (х„..., хсь г,, ..., ее, я„.„, ял), содержащих все х и в точности один из ялементов зм г! для каждого !'= — !,, с! Более того, все яти базисы невырожденны. Доказателы тво.
Поскольку х,)з и х,) ех для !'=1,..., д — 1, то в любом допустимом решении х, ) ас ) О Поэтому все допустимые базисы задачи (8.2) должны содержать д столбцов, соответствующих переменным х. Далее, пусть г =я?=О для некоторого !. Если ! = 1, то з= х, = 1, что абсурдно Если !' ) 1, то из третьего ограничения в (8.2) вытекает х = еху „ и из четвертого вытекает х, + вхт, —— ! или 2нхл с = 1. Но х,, ( 1, согласно второму и четвертому ограничениям из (8.2), и, кроме того, е ( 1)2; поэтому последнее равенство невозможно. Мы заключаем, что любой допустимый базис должен содержать для каждого ! один из столбцов, соответствусощих я, и с . Но это дает уже 2д=т базисных столбцов.
Более того, мы доказали, что ни одно такое бдр не может иметь нулевых компонент и, следовательно, все они невырожденны Е) Будем записывать бдр задачи (8.2) в виде х», где 5 — подмножество множества (1, 2, ., с(), соответствующее ненулевым г в хв. Значение переменной х в хз будет обозначаться через х~~. Нам потребуется 174 Гм В, Алгоритмы и сложчссгпь Лемма 8.2. Пусть йЕ5, но й(3'; тогда х, ) хК. Кроме того, если 3'=3 — (а), то хз'=! — хсз.
Доказательство. Так как йЕ5, то з„=О и из четвертого ограничения в (8.2) вытекает хлз=! — ехз,. Но х',<1 и е < 172; поэтому 4) 172. С другой стороны, поскольку й(5', то г =О и из тРетьего огРаничениЯ в (8.2) вытекает хсз' =ахль', < 112. Следовательно, хз' < хю Для доказательства второй части заметим, что если 5 =5' () (с!), то хсз',=хсз,.
Тогда 4'=ех3',=1 — (1 — ехсз с)=! — хз. П Лемма 8.3. Пусть подмножества множества (1, 2, ..., й) занумерованы таким образом, что хоп < хс' <... (хс' . Тогда все неравенства строгие и бдр х 7 и х'7+с смежны при всех ! = = 1, 2, ..., 2" — 1. Доказательство. Воспользуемся индукцией по й.
Утверждение, очевидно, выполняется для й=1. В этом случае мы имеем два бдр, а именно (х„го з,) =(е, О, 1 — е) и (1, 1 — е, О). Эти бдр имеют неравные х, и, очевидно, смежны. Предположим теперь, что лемма установлена для й-мерного куба, и пусть 8„..., 5,л — соответствующая нумерация. Но 5„..„3,с являются также подмножествами множества (1, 2, ..., й+ 1), и, кроме того, х„7, = ех„~, Отсюда, согласно предположению индукции, хс,', < хсс, (...
(хг',. Рассмотрим теперь остальные подмножества множества (1, ..., й+ Ц, а именно 5; = 5 з с =5 0 (й+1), 1= 1, ..., 2", Согласно лемме 8.2, х ~„, )хи~, и хл1, = 1 — хл~~,. Следовательно, По предположению индукции х~/ и хз/с' смежны, значит, смеж- 5 3 ) з.с зс ны х ~ и х н'. Прн этом х '" и х '" также смежны, поскольку второй базис получается из первого добавлением глс, и выбрасыванием з„о Лемма доказана. Теперь можно доказать основное утверждение этого параграфа. Теорема 8.1. Для любого й)! существует задача ЛП с 2й уравнениями, И переменными и целочисленными коэффициентами, абсолютная величина которых не превосходит 4, в которой симплекс- алгоритм может при нахождении оптимума проделать 2" — 1 итераций.
В.7. Аеееритм еееипсоидое 175 Доказагпельетео. Возьмем з=1!4 и умножим все уравнения в (8.2) на 4, при этом все коэффициенты будут целыми. Поскольку в (8.2) требуется максимизировать хю зо в экспоненциальнодлинной цепи смежных бдр, существование которой установлено в лемме 8.3, стоимости будут убывать. Теорема доказана. (1 Результаты, аналогичные теореме 8.1, известны для почти всех вариантов симплекс-алгоритма, включая некоторые эвристические правила замещения, прямо-двойственный симплекс-алгоритм из гл. 5 и др.; см. задачи и ссылки в конце этой главы.
До недавнего времени вопрос о том, может ли существовать какой-нибудь полиномиальный алгоритм для задачи ЛП, был очень запутанным. Относительно ответа на этот вопрос имелись противоречивые соображения. С одной стороны, задача ЛП была, естественно, одной из тех задач (вместе с ЗК и многими другими; см. гл. 15), для которых, казалось, никакие разумные попытки построитьполиномиальный алгоритм пе могут привести к успеху.
С другой стороны, задача ЛП обладает двумя положительными чертами, которые делают ее совершенно отличной от других классических задачэтого семейства. Во-первых, для ЛП имеется сильная гпеория деойсгпеенности, чего нет для других трудных комбинаторных задач (см. й 16.1). И во-вторых, для задачи ЛП есть алгоритм, симплекс-метод, который — хотя и экспоненциален в худшем случае — уверенно работает на практике для задач, по-видимому, неограниченного размера. В следующем параграфе мы рассмотрим недавнее сенсационное открытие, разрешившее эту головоломку. ая Алгоритм эллилсоидов Весной 1979 г, советский математик Л.
Г. Хачиян опубликовал доказательство гого, что некоторый алгоритм для задачи ЛП полиномиален, разрешив таким образом вопрос, долго стоявший открытым. Результат Хачияна основан на работе других советских математиков по нелинейному программированию (см. ссылки) и совершенно отличается от большинства предыдущих подходов к ЛП тем, что в нем почти полностью игнорируется комбинаторная природа задачи. В следующих разделах мы опишем и обсудим этот алгоритм.
Прежде всего нам необходимо установить некоторые вспомогательные результаты, представляющие одновременно и самостоятельный интерес. 8.7.1. ЛН, ЛН и СЛН. Формально задача линейного прогрпхяиирования (ЛП) (в стандартной форме) — это следующая вычислительная задача.
Для данных целочисленной гпхп-матрицы А, и-вектора Ь и л-вектора о либо Гл. Е. Алгоритмы и сложность 176 Нет Да Нет Да Нет х > 16? х> 8? .х > 12? х > 1О? л > 11? 16 Я 16 Я 11 11 12 !1 = х, Рис. 8.3. Последовательность из пяти вопросов вида: <Верно ли, что к > а?» для различных значений а, в результзте которой определяется, что с=11.
Оказывается, что задача ЛН почти так же трудна, как ЛП, по крайней мере в том, что касается существования полиномиальных алгоритмов. Для установления этого нам потребуются некоторые вспомогательные утверждения. Начнем с рассмотрения очень общего метода программирования, называемого бинарным поиском.
Предположим, мы хотим найти (неизвестное) целое число х между 1 и В, задавая вопросы вида: еВерно ли, что х)а?» для некоторого выбранного нами а. Для решения этой задачи можно сначала спросить, находится ли х в верхней половине интервала (1, В), затем спросить, находится ли х в верхней половине нового (вдвое меньшего) интервала, и т, д. до тех пор, пока интервал, в котором заведомо лежит х, не будет содержать ровно одно целое число — х. Это произойдет после Г!од В( таких вопросов — Г !ой В) можно, в частности, определить как число, показывающее, сколько раз нужно поделить В на 2, чтобы получить число, не превосходящее 1.
На рис. 8.3 проиллюстрирован бинарный поиск для В=-32 и х=!1. При этом достаточно 1од 32 ) ? 5 вопросов. а) найти и-вектор х с рациональными координатами, такой, что х)0, Ах=Ь и с'х принимает минимальное значение при этих условиях, либо б) установить, что не существует и-вектора х, такого, что х>0 и Ах=Ь, либо в) установить, что множество (с'х: Ах=-Ь, х)0) не ограничено снизу. Рассмотрим задачу о линейных неравенствах (ЛН), определяемую следующим образом. Для данных тлсп-матрицы А и т-вектора Ь выяснить, существует ли п-вектор х, такой, что Ах«Ь. Для удобства будем считать, что в ЛН и определяемой ниже задаче СЛН т)п, хотя это условие не ограничивает задачу, Вопрос Ответп Интервал яитожных х после вопроса З.7.
А»ворогом»ллиоооидов 177 Сформулируем этот результат в ниде леммы. Лемма 8.4. Целое число х между 1 и В можно узнать за Г 1од В ) вопросов аида: аВерно ли, что х~а?» Рассмотрим задачу ЛП в стандартной форме с т ха-матрицей А: ппп с'х, Ах= Ь, (8.3) х)0, Ее размер— В = тп+ Г 1ой ~ Р ) ~, (8.4) где Р— произведение ненулевых (целочисленных) коэффициентов, входящих в А, Ь и с (вспомните пример 8.5), Сформулируем теперь следующий вариант леммы 2.1.
Лемма 8.5. Все бдр задачи (8.3) являются п-векторами, соспиыленными из рациональных чисел, абсолютные величины и знаменатели которых не превосходят 2». Доказательство аналогично лемме 2.1. Г) Лемма 8.6. Пусть два бдр х„х» задачи (8,3) удовлетворяют нерааенстаам К2»с ( с'х„с'х,((К+ 1) 2 'с для некоторого целого К. Тогда с'х, =с'х., Доказательство. Допустим, что с'х,~с'х».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
