Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 33
Текст из файла (страница 33)
Тогда, по лемме 8,5, с'х, и с'х, — различные рациональные числа со знаменателями, не превосходящими 2'-, откуда 1с'х,— с'х»1)2»с — прогиворечие, () Теперь мы можем доказать следующую теорему. Теорема 8.2. Полиномиальный алгоритм для задачи ЛП сусцествует в том и только в том случае, если суьцествует полиномиольный алгоритм для задачи ЛН. Доказательство. Для доказательства части только в том случае заметим, что для решения любой индивидуальной задачи ЛН достаточно определить, допустима ли соответствующая задача ЛП (с добавленными переменными недостатка и удаленными неограниченными переменными; см. з 2.1), Следовательно, полнномиальный алгоритм для задачи ЛП будет порождать полпномиальный алгоритм для задачи ЛН. Обратно, предположим, что алгоритм 4 решает задачу ЛН за полиномиальное время.
Опишем полиномиальный 178 г». з. Алгоритмы и с»южна«ть алгоритм для задачи ЛП, использующий А. Пусть входом служит задача ЛП (8.3), 1. Вначале наш алгоритм определяет, допустима ли задача ЛП, вызывая один раз алгоритм А и подавая на его вход неравенства Ах>Ь, Ах(Ь и х>0. Если А дает ответ «иет», мы делаем вывод о недопустимости нашей задачи и останавливаемся.
2. Далее, мы проверяем на допустимость систему неравенств Ах>Ь, Ах(Ь, х>0, с'х( — 2'~ — 1. Поскольку произведение с'х ограничено снизу величиной — 2«», если оно вообще ограничено, то в случае, когда А определяет, что указанные неравенства выполнимы, мы делаем вывод о неограниченности нашей задачи и останавливаемся. 3, В противном случае мы знаем, что задача имеет оптимальное бдр х. Определим вначале целое число — 2'~(К = 2«с, такое, что К2»с(с'х (К+!)2»с. Это можно сделать с помощью бинарного поиска (см.
лемму 8.4), вызывая 4Е+1 раз алгоритм А для неравенств Ах>Ь, Ах(Ь, х>0, 2".сх(а ври различных значениях а. Так как алгоритм А полиномиален, то К можно определить за полиномиальное время. 4. Окончательно, найдем базис, соответствующий х. Для каждого й=1, ..., п проверим, выполнимы ли одновременно все неравенства Ах(Ь, Ах>Ь, К(2"с х(К+1; х>0, х (О и х (О для ! Е 5(й). Здесь 5(й) — множество индексов, меньших Ь, для которых получен ответ «да». Должно быть очевидным, что любые т столбцов, не входящих в 5 (и+!), можно выбрать в качестве базиса, соответствующего х, и что существует по меньшей мере т столбцов, не входящих в 5(п+!).
Определив таким образом базис (возможно, неоднозначно), можно эффективно найти х простым обращением базиса — обращение целочисленной пмп-матрицы М можно выполнить за полиномиальное время (относительно размера М) с помощью метода исключения Гаусса (Га1. ГЗ Согласно теореме 8.2, сложность ограниченной на вид задачи ЛН остается такой же, как сложность задачи ЛП. Другими словами, этап 1 обычного симплекс-метода (цель которого — всего лишь найти допустимую точку; см. з 2.8) имеет такую же сложность, как и вся задача! Рассмотрим еще одну близкую задачу, зада«у о строгих линейных нераеенспмах (СЛН): для данных целочисленных тхп-матрицы А и т-вектора Ь выяснить, существует ли п-вектор х, такой, что Ах(Ь.
Не удивительно, что задача СЛН не легче, чем ЛН. 179 8.7. Алгорао1м лллоаооивоо Лемма 8.7. Система линейных неравенств а;х < Ь,, 1 = 1. ..,, т, (8.5) имеет решение тогда и только тогда, когда имеет решение система строгих линейных неравенств а1х<Ь1+е, /=1, ..., т, где а=2 '.1. Доказательство. Если система неравенств (8.5) имеет решение, то это решение удовлетворяет также и (8.6).
Для доказательства. обратного утверждения предположим, что (8.6) имеет решение. Исходя из этого решения, построим решение х для (8.5). Это по- строение можно рассматривать как хитрый вариант построения из теоремы' 2.1, где было показано, как построить бдр начиная с про- извольного допустимого решения. Пусть х,— решение системы (8.6). Рассмотрим множество век- тор-строк / = (а,; Ь, < а;х, < Ь, +з). Можно считать, что а/ —— 671а1 для всех / н подходящих чисел 13,. Действительно, если бы некоторый вектор а/ был независим от векторов а, из /, то система аз=О, а1Е/, а'г= 1 1 имела бы некоторое решение г,, Взяв х,=х„+Хг, для достаточно малого Х, можно получить другое решение х, системы неравенств (8.6), для которого множество / содержит на один вектор больше; после не более т шагов этот процесс должен остановиться.
Таким образом, а1 — — ~.. 1, 81,а1 для всех 1 и некоторого линейно независимого подмножества /' множества /. По правилу Крамера каждое 6/1 является отношением двух определителей; (3м — — 011/)О(, абсолютная величина которых меньше чем 2с, Рас- смотрим решение х уравнений а',х = Ьо аг Е /'.
Для каждого / имеем: 0 ~ (а'1х — Ь1) = ~1 0,а,'х — ~ 0 ! Ьг = (по определению х) а1а1 —;~ 0,Ь; — ~0~ Ь = а1а 1' (прнбавили и вычли 10~а';х,) 0; (а,:х, — Ь1) + ) 0 ( (а';х,— Ь ) < а1а 1' (поскольку ~а,'ха — Ь1) < е для 1Е/' и а';х,— Ь <з для всех /') <з/ ~ ~Од~+~0~) <2-'с(т+1)2с <1. ~, а1О1 Гл. 8. А егориями и сложноспь 180 Таким образом, 1О1(а,'х — Ь|) < 1 для всех 1. Кроме того, из определения О следует, что зйаменатели всех компонент вектора х делят ~ О ! и, следовательно, ( О ! (а',х — Ь,) — целое число. Отсюда а',х — Ьгв.0 длЯ всех 1, т е. х — тРебУемое Решение неравенств (8.5).
Г) Следствие. Если существует полинвмиальный алгоритм для СЛН, то существует полиномиальный алгоритм для ЛН. Доказательство. Для проверки выполнимости множества линейных неравенств (8.5) достаточно проверить, выполнима ли система 2'~а,'х(2'Ь,+1, 1=1, ..., т. (8.7) Размер задачи ЛП (8,7) не превосходит удвоенного квадрата размера задачи (8.5) В равд. 8.7.3 будет приведен полиномиальный алгоритм для задачи СЛН.
8.7.2. Аффиниые преобразования и эллипсоиды. В этом разделе будут приведены некоторые стандартные понятия линейной алгебры и некоторые касающиеся их факты (леммы 8.8, 8.9 и 8.10) без доказательств. Пусть Я вЂ” невырожденная а~~ и-матрица и т — вектор длины п. Преобразование Т: й" — )7", определяемое формулой Т(х)= =-1+9 х для каждого к Е )7", называется афуэинным преобразованием. Поскольку матрица 1З невырожденца, то преобразование Т однозначно обратимо. Преобразование, обратное к Т, также яв.
ляется аффинным преобразованием. Множество В„= (х Е)7": х'х(1) называется единичным шаром. Если Т вЂ” аффинное преобразование, го Т(Б„) называется эллипсоидом. Другими словами, Т(Б„)=(уЕй'": (у — 1)'В '(у — 1)(1), где В=ф~ . Матрицы, такие, как  — произведение невырожденной матрицы на транспонированную к ней,— являются положительно определенными; т. е. х'Вх)0 для всех ненулевых хЕ7ть. Аффинные преобразования сохраняют отноц:ение включения между множествами. Лемма 8.8. Если Я с=. В' с= Ь", то Т (В) = Т (5') Пример 8,9. Пусть в 2-мерном пространстве 1= (2, 3)' Г2 01 Гцм О3 и Я=(,,1.
Тогда В '= ( ь,1, и соответствующий эллипсоид Т(В,) имеет вид, показанный на рис. 8.4 В общем случае оси эллипсоида могут быть не параллельны координатным осям, но они всегда ортогональны друг другу. Центр эллипсоида всегда совпадает с С 181 8.7. Лэгоропм ээлиосоодоо Лемма 8.9. Пусть подмноаеество 5 из Ро имеет объььи 1'. Тогда Т Я имеет объем э" Ые1(Я) ~. Например, объем зллипсоида на рис. 8А равен 2п, Рассмотрим аффинное преобразование Р, в котором 1 — -О и матрица (также обозначаемая через И) обладает следующим специальэ 2 3 4 х Рис.
8.4. ным свойством: Ийт=1. Такие преобразования называются вращениями — легко видеть, по они отображают единичный шар на себя. Лемма 8.10. Пусть а б Р" — вектор длины 1а~'. Тогда существует такое вращение й, что йа=(1а~!, О, ..., О). В заключение нам нужен один факт из теории выпуклых многогранников, Рассмотрим выпуклый многогранник Р в Яо. Мы знаем, что Р можно записать в виде Р= (х Е Ро: Ах(Ь) для некопэрых т)п, тхп-матрицы А и т-вектора Ь. Пусть внутренность Р определяется условием 1п1(Р)= (х Е Ро: Ах~б).
Лемма 8.11. Если 1п1(Р)~ьйз, то в Р существуют и+1 линейно независимых вершин. Доказательство. Если все множества из и+1 вершин многогранника Р линейно зависимы, то Р лежит на некоторой гиперплоскости Н. Возьмем, однако, точку хЕ1п1(Р), и пусть а — наи- Гл. 8. Алгоритма и сложность 182 меньшее расстояние от х до граней Р, Так как х Е 1п1(Р) н е)0, то шар с центром в х и радиусом е лежит целиком внутри Р и, следовательно, на Н. Но это абсурдно: никакая (п — 1)-мерная гиперплоскость не может содержать и-мерного шара. () 8.7.3.
Алгоритм. Основная идея алгоритма эллипсоидов очень проста. Алгоритм состоит из итераций. У нас постоянно имеется эллипсоид, содержащий некоторое решение данной системы СЛН, АЛГОРИТМ ЭЛЛИПСОИДОВ ДЛЯ ЗАДАЧИ СЛН Вход. Система строгих линейных неравенств Ах < Ь порядка щ)гп и размера Ь. Выход. п-вектор х, для которого Ах < Ь, если такой вектор существует; «нет> в противном случае. 1: (Задание начальных значений) Положить 1:= О, 1«;= О, Вр,= п~«ь.1 (Сощщеп1: 1 далее считает число итераций; текущий зллнпсоид имеет вид Е) =(х: (х — 11)' В) (х — 11) «1)). 2: (Проверка) И 11 — решение системы Ах < Ь гьеп ге1пгп 1; 0 1 > К=1бп(п+1)Ь Шеп гегигп «нет»; 3: (Итерация) Выбрать любое неравенство в Ах < Ь, которое нарушается при х=(1, скажем а'11гм Ь.
Положить В)а п«Г 2 (В)а) (В)а)'1 В)ег.= —, В) —— п« вЂ” 1 ~ п-1-1 а'В)а 1:=!+1; йо 1о 2. Рис. 8.8. если такое решение вообще существует. Итерация состоит в замене текущего эллипсоида меньшим, который также с гарантией содержит некоторое решение (если оно вообще существует). После достаточного числа итераций мы либо должны обнаружить решение, либо приходим к выводу, что после ряда сжатий эллипсоид стал слишком мал, чтобы содержать решение, и заключаем, что решения не существует. Полностью этот алгоритм приведен на рис. 8.5.
Пример 8.10. Предположим, что для некоторого / мы получили гз оч (у —— (О, О)', Вг — — ( о «1 и одно из неравенств имеет вид х+у< — 1. Эта ситуация изображена на рис. 8.6(а). Напомним, что откуда-то нам известно, что решение данной индивидуальной задачи СЛН, если оно существует, лежит внутри эллипсоида ЕР Так как любое решение должно удовлетворять неравенству х+у( — 1, то с уверенностью можно сказать, что все решения лежат в нижней левой половине этого эллипсоида.
Если бы мы могли каким-нибудь обра- 8.7. Алгоритм оккилсоидоо (б) Рис. 8.6. а) Эллипсоид иа Рй итерации. б) Эллипсоид иа следующей итерации. зом построить эллипсоид Е~+о включающий в себя эту левую нижнюю половину, то зто было бы подходящим шагом. Именно это и де. лает итерация в алгоритме (рис. 8.6(б)). Получаем (уе,=( — 3!)' (3, Гл. 8, Алгорнньны и олозонооть — 4/(3$' ГЗ))' и Корректность алгоритма зллипсоидов вытекает нз следующей теоремы со скучным, но прямым доказательством.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
