Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 64
Текст из файла (страница 64)
е. некоторая линейная комбинация строк равна нулю и, следовательно, бе! (С) =- О. Теперь получаем требуемый результат. Следствие. Любая зидачи ЛП в стиндиртной или канонической форме, митрици ограничений А которой есть либо 1) матргщи инциденций вершин и дуг ориентированного графа, либо 2) митрици пнциденций вершин и ребер неориентированного двудольного грифа, имеет только целочисленные оптимальные вершины. Сюда включаются формулировки в виде зидач ЛП для зади ги о крапгчайшем пути, задачи о максимальном потоке, задпчи Х>гчкокгг и зидачи о взвешенном пиросочетинии в двудольном грифе. Докизательство. В случае 1 матрицы удовлетворяют условию теоремы !3.3 при 1,=8; в случае 2 — при 1,=(1 и 1,=-)г, где 8- =-(у', (1, Е) — данный двудольный граф.
Справедлива также теорема, обратная к теореме 13.2 (но не!3.1): если все вершины многогранника Р,(А) целочисленны для любого целочисленного вектора б, то матрица А должна Г>ыть вполне унимодулярной (задачи 1 и 2). Следовательно, в некотором смысле мы обнаружили, почему определенные задачи ЛП приводят к оптималь- 323 Гл. 13. Целониоленное линейное нрограммирооание ным базисным решениям, которые автоматически целочислеины, в то время как для других задач это не так. В последнем случае мы вынуждены выходить за пределы симплекс-алгоритма для решения соответствующих задач ЦЛП.
1З.З Верхние оценки решений задач ЦЛП В лемме 2.1 было показано, что абсолютная величина любого бдр задачи ЛП ограничена сверху величиной, зависящей от размерности этой задачи ЛП и размера встречающихся в ней целых чисел. х, (б) (е) Рас. 13лн Этот результат отражает здравую геометрическую интуицию. По существу утверждается, что грани многогранника не могут простираться «слишком далеко» так, чтобы получались <большие» бдр, если только не используются огромные целые числа для образования очень маленьких углов (рис. 13 4(а)). Подобное рассуждение кажется справедаивым и для задачи ЦЛП.
Допустимой области очень трудно избежать всех целых точек, за исключением некоторой очень большой точки, если только опять ие используются крайне малые углы и огромные коэффициенты (рис. 13.4(б)). В этом параграфе мы дадим формальное обоснование этого эффекта. Рассмотрим задачу ЦЛП с ограничениями $и Ах=Ь, х)0 целочисленно, где А — целочисленная (епхп)-матрица и Ь вЂ” целочисленный вектор размерности т. Пусть а,=шахц(1йц1), по=шах~(~Ь,Ц. Следующее утверждение представляет собой интуитивно оче- видный геометрический факт.
Рассмотрим три направления на пло- И,8. Верхние оценки реимнаа эадач цдГу 329 скости !рис. 13.5). Тогда справедливо ровно одно из следующих утверждений. 1. Эти направления лежат в одной полуплоскости (рис. !3.51а)). 2. Эти направления могут быть направлениями трех уравновеьиивающих друг друга сил 1т. е. существуют такие три неотрицатель- а! о (б) 1а) Ряа. 13.3 иых коэффициента, не все равные нулю, что соответствующая линейная комбинация векторов обращается в нуль). Докажем теперь обобщение этого факта на многомерный случай для вычислений с конечной точностью, которое можно рассматривать как вариант леммы Фаркаша для вычислений с конечной точностью 1см. 5 .3) Лемма 13.1, 11 усть о„о„..., о — это й ) 0 векторов из 10, -Ь1, ~2, ..., ~а,)"', и пусть М, = !та,)"'+'.
Тогда следующие утверждения эквивалентны. а) Существуют й действительных чисел Ры, . „Рн)0, не все равные нуво, такие, что Х ~рэ — — О. 7 1 б) Существуют такие й целых чисел 0(рэ,..., 1!ь(Мы не все равные нулю, что ~ !)1оо=О. /:-! в) 11е существует такого вектора й ЕРа, что ро=й'оэ)0 для 1=1,..., й. г) Не существует такого вектора Й б 10, ~1, а.2,..., ~М1)'", что 6'о>)1 для 1=1,..., я. Доказательство.
1а)=ь(б). Это следует непосредственно из леммы 2.1 и теоремы 2.1. Гв. 18. цевоноовенное линейное нрогромморовоное (б)~(в). Предположим, что п.(б) выполняется, однако существует вектор д, удовлетворяющий условиям из п.(в). Тогда 0=6 Х(),и = Х Одну)О, г=~ /=! что абсурдно, (в)~(г). Тривиально. (г)=>(а). Предположим, что п.(г) выполняется, и рассмотрим за- дачу линейного программирования пп'п Ь'О, й'ие ) 1, ! = 1, ..., и. (13.8) Теорема !3.4.
Если задача ЦЛП (13.7) имеет доиуслшмое решение, то пна и.иеет допустимое решение .к Е (О, 1,..., М,)", где М и(та)ввнв(1 ! а ) Доказательство. Рассмотрим наименьшее (в смысле суммы компонент) допустимое решение к задачи (13.7). Если все компоненты решения х меныпе илп равны М,=(та,)м", то все в порядке, так как М,(Мв В противном случае допустим, не ограничивая общности, что первые !г компонент, и только они, больше, чем М,.
Пусть и„и„..., ид — соответствующие столбцы матрицы А. Рассмотрим отдельно два случая. Случай !. Существуют такие целые числа !)„, ()„, заклю!енные междУ нУлем и М, и не все Равные нУлю, что ~в!,!)все=О. Если эта задача ЛП имеет допустимое решение, то по правилу Крамера она имеет рациональное допустимое решение, в котором абсолютные величины числителей ограничены числом М, и общий знаменатель 0 удовлетворяет неравенствам ! и:0.=М,. Если д — вектор, составленный из числителей, то для у выполняются услония; дЕ(0, ~1,..., -+-М,)'", й'и!'- 0 в! для !'=-1, ..., й, и условие г) нарушается.
Предположим поэтому, что задача ЛП (!3.8) недопустима. Тогда двойственная ей задача ЛП шах Х ()ез !=! Х !),о!=О, /=! (),>О неограниченна (поскольку она имеет допустимое решение, в котором все )1, пулевые). Следовательно, она имеет строго положительное реш ние — в котором не все ()~ равны нулю — и поэтому п (а) выполняется. П Теперь мы можем получить основной результат этого параграфа.
13.3. Верхние оценки реи!енид задач цдП 33! Отсюда » » н ~~Р х, ( Х й'о хг = й'Ь вЂ” ~~ й'о х . 1=! >=! !=»!-! Выражение в правой части ограничено сверху величиной та,М!+ +(и — й)та,М; -М„, и, следовательно, никакая компонента решения х не может быть больше, чем М,. П Следствие. Если задача ЦЛП Ах<Ь, х) 0 целочисленно имеет допустимое решение, то для нее существует допустимое решение с компонентамп, не превосходящими (и+т) (та,)'"'+»(!+а,), Доказательство.
Можно свести эту задачу ЦЛП к виду (!3.7), используя переменные недостатка, и затем применить теорему 13А. ь) До сих пор мы игнорировали компоненты функции стоимости в задаче ЦЛП. Рассмотрим теперь задачу ЦЛП ш(п с'х, Ах=Ь, х ) 0 целочисленно и ее «ослабление» до задачи линейного программирования ш(п с'х, Ах=й, х) О. (!ЗЛО) Лемма 13.2. Если задача (!3.!0) неограниченна и задача (13.9) имеет допустимое решение, то задичо (13.9) также неограниченна.
Доказагпельстзо. Пусть х — допустимое решение задачи (13.9). Очевидно, х — допустимое решение задачи (13.10). Так как задача В этом случае сразу же получаем, что вектор х'=(х! — (»», х» — р», ". ..., х» — ()д, х»..., х„) также является решением (13.7), причем сумма его компонент меньше, чем сумма компонент решения х; получили противоречие. Случай 2. Таких целых чисел ()„, ()н ие существуез. По лемме !3.1 существует такой вектор й Е (О, д=!,, ~М,)'", что й'и,)! для 1=-1,..., й.
Умножим обе части уравнения Ах=-Ь на й'. Получим » и Х й о1х =й Ь вЂ” ~~Р~ й о1х1. 1=! /=»+! йзв Гл. /3. целочисленное линейное программирование (13.10) неограниченна, то (см. задачу 17 из гл. 2) существует такой рациональный вектор а, что а) с'а(0; б) х+йа допустимо в задаче (13.10) для всех /г)0. Пусть Р— произведение знаменателей компонент вектора а. Тогда точки (х+/Реи !=1, 2,...) целочисленны, допустимы, н соответствующие им стоимости не ограничены снизу. () Теорема 13.5.
Пусть задача ЦЛП (!3.9) имеет конечное оптимальное допустимое решение х. Тогда )с'х((М,~/,!с,!. Доказательство. Величина с'х ограничена сверху значением целевой функции для допустимого решения х ограниченного размера, существование которого гарантируется теоремой 13.4. и Отсюда с'х(с'х и, следовательно, с'х.
«М, ~ !с/!. /=/ Теперь нужно ограничить с'х снизу. Такой нижней границей может служить оптимум в задаче ЛП (13.10). Л мы знаем, что задача (13.!О) имеет ограниченный минимум, поскольку в противном случае, согласно лемме 13.2, задача ЦЛП (!3.9) была бы неограниченной. Пусть минимум в (13.10) достигается для бдр х. Компоненты х по абсолютной величине не превосходят т/а'," (лемма 2.1); поэтому л и с'х)с'х) — т(а',"Х (с () — М, ~ (с/(. /=1 / 1 Так как — М,~2'„",)с ((с'х~Ме~~/„,(с (, то )сх)( «аМ.Х/=" !;!. () Пусть ае=гпах((а„а,)() (!с/(: !=1,..., и)).
Следствие. Если задача ЦЛП (13.9) имеет конечный оптимум, то для нее существует такое оптимальное решение х, что !х/(~ ~пв((т+2)аь)'"+и=Мы 1=1,..., и. Доказательство. Пусть д — величина оптимума в задаче (13.9). Тогда любое оптимальное допустимое решение х удовлетворяет условиям с'х~д, — с'х ) — д, Ах>Ь, х ) 0 целочисленно. Поэтому можно применить следствие из теоремы (13.4), заменив т на т-';2, а, на а, и а, на шах (а„д).
При этом для любого) получаем !х, 1:=М,. 333 Задами Важным свойством доказанных выше оценок является то, что пх логарифмы полиномиальны относительно размера входа, Напомним, что в качестве размера задачи ЛП вЂ” или в данном случае задачи ЦЛП вЂ” можно взять (-=та+!ой 1Р(, где Р— произведение ненулевых элементов матрицы А и векторов Ь и с. Отсюда а, (Р( и !ой ае та~у.. Следовательно, !оа Ма = 3!ой и + (4т + 12) 1!ой (т + 2) + !ой а,| = 0 (7.').
Мы воспользуемся этим фактом для доказательства того, что задачи ЦЛП и НОЛП полиномиально эквивалентны; т. е. полиномиальный алгоритм для одной нз них существует в том и только в том случае, если существует полиномиальный алгоритм для другой. Теорема 13.6. Полиномиальный алгоригпм для задачи ЦЛП существует в том и только в том случае, если существует полиномиальный алгоритм для задачи НОЛП. Доказательство. Если у нас имеется полиномиальный алгоритм для задачи ЦЛП, то, очевидно, частный случай этой задачи, задачу НОЛП, можно решить за полиномиальное время. Для доказательства обратного утверждения предположим, что у пас имеется полиномиальный алгоритм для задачи НОЛП. Покажем, как свести произвольную задачу ЦЛП к эквивалентной задаче НОЛП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
