Н.М. Новикова - Дискретные и непрерывные задачи оптимизации, страница 5

Для г-приближенных алгоритмов приведем следующий результат [2, с. 439], доказательство которого основано ыа методе динамического программирования и в данном курсе опускается. Творима 5. Пусть для задачи П оптимизации 1) существует псевдополиномиальный алгоритм ее решения; 2) ч1 б П !Ор1п(1)! < р~(!1!,пщп(1)) и пшп(1) < рз(!1!,Ор1п(1)) для некоторых полиномов р~(, ), рз(ч ); 3) го = е(1), 1 б П: параметры ог, задающие ограничения, и о,„, задающие целевую функцию, не пересекаются, и Ых б Яп(о) функция цели /п(о, х) линейно зависит от параметров о„,; тогда Нр(,.) — полипом: Ыс > 0 3 с-приближенный алгоритм А, решения П с временнбй сложностью Тл,(]1]) < р(]1], 1/с).

Теорема 5 справедлива, например, для ЗР (сравните результат с утверждением 11). Набор алгоритмов (А,), определенный в теореме 5, называется но*веселью аолнномнальной вриблахсснной схемой (ПППС) решения задачи П оптимизации. Наличие ПППС вЂ” лучшее, чего можно ожидать при решении ХР-трудных задач. К сожалению, в целом ряде случаев на зто нельзя рассчитывать, так как имеется ТеОРемА 6. Если для П оптимизации соответствующая ей П распознавания свойств является сильно г1Р-полной и Зр'( ) — полипом: ]Ор1п(1)] < р'(пшп(1)) Ы1 б П, то при условии, что Р ф Р1Р, для П не существует ПППС. Показательство проведем от протквного. Пусть ПППС сушествует.

Построим алгоритм А' следующим образом. Пля любой индивидуальной задачи 1 А' вызывает А, с с = 1/(р' (пшп(1))+1). Тогда по определению с-приближенного алгоритма А, ]Ор$п(1)— -А'(Ц] < ]Ор1п(1)]/(р'(пшп(Ц) + 1) < р'(пшп(1))/(р'(пшп(1)) + 1) по условию теоремы. Но в левой части полученного неравенства было целое число, которое оказывается равным нулю как неотрицательное, меньшее 1. Таким образом, алгоритм А' точен, причем Та'(]11) = Тл.(]1[) < р(]1],р'(пшп(1)) + 1) по определению ПППС. Следовательно, алгоритм А' псевдополиномиален, что противоречит теореме 4. Утвкгжднннк 12. Если Р зб г1Р, то ни для какого с > 0 не существует полиномиального с-приближенного алгоритма решения оптимизапионной постановки задачи коммивояжера.

Локязяткльство см. в [2, с. 440-441]. Зля частного случая КМ, в котором функция и(., ) расстояния между городами удовлетворяет неравенству треугольника, наиболее точным из известных с-приближенных полиномиальных алгоритмов решения КМ оптимизапии является 0.5-приближенный алгоритм Кристофидеса [2, с. 429-432]. 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Липтерашура: 3. Хачиян Л. Г. Сложность задач линейного программирования. Мл Зыание, 1987, 1т1 10.

25. Понитие о сложности задачи линейного программирования (ЛП) Определение основной задачи ЛП (оэЛП). Принцип граничных решений а геометрическое описание симплекс-метподв. Алгебраическая и битовав сложность мептодов ЛП. Рсзульшатпы но сложмостпи задач, близких к ЛП. Теорема о ераницвх решений задач ЛП с целыми коэффицисшпами. Теорема о мере несовместпкоспти сисптсм линейных мсрввенстпв с целыми коэффициснтмвми. 1. Согласно (3] линейное программирование — зто раздел прыкладной математики, изучающий теорию, приложения и методы решения конечных систем линейных неравенств с конечным числом вещественных неизвестных хт,..., х»: а11Х1 + а12Х2 + ° ° ° + а1»Х» < »1 аюхт + аззхз+ ..

+ ая»х„< ез (1) Э ат1Х1 + ат»2Х2 + ° ° ° + а»т»Х» < От или в сокрашенной записи Ах < 6. Считаем, что матрица А не содержит нулевых строк а;. Основная задача ЛП (озЛП) состоит в нахождении такого решения (1), которое максимизирует заданную линейную функцию (с, х) = от хт+ сзхз+...+ с»х„вектора неизвестных х по всем вещественным х, удовлетворяющим системе (1): птах (с, х); (2) вин т лвйь озЛП (2) с и неизвестными и, тп ограничениями называется задачей размерности (и, тп) и задается числовой таблицей Ьт 32 а12 '... от„ аяя аа а11 аю (3) ат1 атз ° ° а»ит От ст сз ... с» 0 24 своих коэффициентов. В частном случае с = 0 задача (2) эквивалентыа (1), так что умение решать озЛП предполагает умение решать системы линейных неравенств (ЛН).

В з7 будет показано обратное сведение. Вообще говора, в форме (2) может быть представлена любак задача ЛП с ограничениями равенствами и неравенствами, в том числе каноаачгскаг задача ЛП шах (с, х). Азжб, з>6 (Здесь р далее черта сверху будет использоваться длк выделения вектора в отличие от похожего числа.) 'УПРАЖНЕНИЕ 5. Предстввнть каноническую задачу ЛП в форме озЛП. Несмотрз на то, что формально задачи ЛП ые квлзютск дыскретными (х б Ка), их решение нетрудно свести к перебору конечного числа угловых точек (вершин полиэдра (1), задающего ограничения) на основании араавааа грааачыых ргшгааа: если задача (2) имеет решение, то найдетса таках подматрица Аг матрыпы А, что любое решение системы уравнений Агх = йг, т.е. (ад х1 + опхз +... + ам хи = 6;! 1 е 1), реализует максимум в (2).

Отметим, что для невырожденных Аг решение соответствующей системы уравнений Агх = бг, удовлетворяющее ограничениям (1), является угловой точкой (1). Из принципа граничных решений следует, что если угловая точка (1) существует, то разрешимая задача (2) имеет решение и в угловой точке (1), т.е. она эквивалентыа максимизации (с, х) на конечном множестве вершин полнэдра (1). Процедура решения системы линейных уравнений методом Гаусса требует не более полинома 3-й степени от пз, п (точнее; шах(1п, и) [ппп(~в, п)] ) арифметических операций с элементами А и о.

Однако число возможных подматриц матрицы А экспоненциально, и метод полного их перебора не эффективен. В 1820-х гг. Ж. Фурье и затем в 1947 г. Пж. Ланциг предложили метод направленного перебора смежных вершин (1) — в направлении возрастания нелевой функции (2) — самалекс-метод. Хоты каждый шаг симплекс-метода (представлающий собой определенную 25 процедуру пересчета элементов симплекс-таблицы (3)) ограничен по порядку числом гвв арифметических операций, в иастояшее время для всех известных вариантов симплекс-метода приведены примеры, экспоаеациальиые по числу итераций, когда перебирается более 2 м1"""уз1 вершин, ао доказательство невозможности построить полииомиальыый симплекс-метод также отсутствует.

Подчеркнем, что аа практике симплекс-метод ые показывает дааыой оценки ("плохие" примеры довольно редки). Можно построить алгоритм решения задачи ЛП с опеакой у(в)вз арифметкческих операций (ыад числами, записанными в (3)), где 1( ) растет быстрее экспоиеыты. Алгоритм с полиаомиальыой опеакой одновременно по в и ш ые известен и вряд ли будет построен. Теперь заметим, что функция, оцеыиваюшая число арифметических операций в зависимости от в и ш, не учитывает длину кода элементов (3), а только ых количество и поэтому ае является времеаабй сложностью алгоритма. Указанная функция носит название алгебраической слоясносша в отличие от бяшоеой слоясносше— функции, оцеииваюшей число арифметических операций с битами (или с коыечаыми порциями — по размеру мапшкиого регистра) цифровой записи параметров индивидуальной задачи ЛП в зависимости от длиыы входного слова, т.е.

от в, 1в и длин 1 кодов чисел в симплекс-таблице. Очевидно, бктовая сложаость алгоритма соответствует его времеыыбй сложности (см. 11). Входные коэффкциеаты задачи ЛП обычно рациональны, поэтому далее условимся считать их целыми, тогда 1 — длина записи максимального коэффициента в (3) — конечна. Набор (в, вз, 1) называется битовой размерностью задачи ЛП.

Вопрос о сушествоваиии алгоритма ЛП с полииомиальыой битовой сложностью был решен Л. Г. Хачияаом в 1978 г., и тем самым была доказана полиаомиальность задач ЛП. Осыоваые моменты этого доказательства излагаются в следуюшем пуикте и 36. Здесь же укажем ыа отличие классов сложности задачи ЛП и других лииейыых задач. Метод Гаусса решения системы линейных алгебраических уравнений имеет полиыомиальаую алгебраическую сложность, т.е. является сальяоволамомяальяым. Лля ЛП вопрос о сушествовааии сильаополикомиальыого алгоритма открыт. Кроме того, задача решения 26 системы линейных уравнений принадлежит классу Р1С, а аналогичный результат для ЛП означал бы равенство ЯСшР, ожидать которое нег оснований.

Из полиномяальности ЛП вытекает полиномиальность задачи ЛН (существуст ли решение системы ЛИ): ЛН б Р. Аналогячные задачи с дополнятельным ограничением целочисленности или булевости решения 1д1Р-полны: ЦЛН,БЛН б г1РС (см. з2), т.е. полиномиальные алгоритмы для них вряд ли будут построены. Существует неполиномиальное обобшение Л П вЂ” задача проверки истинности высказываний вида Ч1Х1 ' ' ' Сэввп Р((а1 ~ Х) < Ь1 ~ ..

~ (Оув~ Х) < Ьуу~)~ где Я~ б (У,3), а д'(,..., ) — предложение, составленное из линейных неравенств с помощью связок Й,Ч, (и, нли, отрицание). Показано, что любой алгоритм, решаюший эту массовую задачу, имеет не менее чем экспоненциальную сложность. Тот же результат будет и при замене равенствами всех неравенств в постановке задачи.

2. Рассмотрим некоторые свойства задач ЛП с целыми коэффициентами. Лля любой пелочисленной матрицы В введем параметр гз(Р) = шах [деФду [. ПШ вЂ” кввдратвад подматркпв Щ Будем обозначать через [АЩ матрацу, составленную из А и вектора- столбца Ь б Е, дописанного справа. Здесь и далее Екв — тв-мерное пространство целочисленных векторов, Е+' — его неотряпательный ортант.

Творима 1 (о граненая решгнай). Если озЛП (2) размерности (в, дв) с целыми коэффициентами разрешима, то у нее существует рациональное решение х* в шаре йЩ < в'~зсв([А[Ь)) и значением озЛП (2) И" =' (с, х") является рациональное число М/г со знаменателем, ограниченным величиной Ь(А). Воказдтппьство. На основании принципа граничных решений и по правилу Крамера ЗА~ С А: х' = бенд~/деВАд < тд([А[Ь)), ибо йе1Аг > 1, а определитель матрицы Ад~, полученной из Аг заменой 2У уьго столбца на Ыг, не превышает по модулю Ь([А]6]). Отсюда для евклидовой нормы х* получаем требуемую оценку. С учетом цело- численности вектора с знаменатель И' может быть выбран равным знаменателю х' Чу, и 2-е утверждение теоремы следует из определения Ь(А) > ]оесАг]. Опгкдклнник 1.

Точка х' называется с-приближенным решением снстемы линейнык первенств (1), еслв (а;,х') < 6;+с 'яз = 1,пз, где а; — сья строка матрицы А, или в матрнчной записи, обозначая е — вектор-столбец из единиц, Ахк < 6+ се. (1,) ТеОРемА 2 (о мере иесовмесщнвста). Если система ЛН (1) имеет с~-приближенное решение для с~ =' 1/((и+2)Ь(А)], то зта система разрешима, т.е.