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

37. Теория двойственности ЛП. Идея метода Кармаркара Следствия систем ЛН. Ай»иииая лемма Фаркаша /без доказательства/. Лемма Фарквша о неразрешимости. Теорема даойсп»вгииости ЛН. Сведение озЛН к однородной системс урагнсиий с ограиичгиигм полохситсльиости. Идея метода Кармаркара и его отличие о»п сими»екс-метода.

1. Система ЛН (1) называется разрешимой, если Эх: Ах < о, и неразрешимой — в противном случае. ОэЛП (2) разрешима, когда разрешима система (1) и максимум в (2) достигается. Опгидилинии 3. Линейное неравенство (4) (с,х) < д является следствием разрешимой системы линейных неравенств (1), если для любого х, удовлетворяющего (1), выполнено (4). Способ получения неравенств-следствий ловольно прост: выберем произвольные Л; > 0 'б Е М, домножим на Л; каждое 1-е неравенство системы (1) и сложим; получим для вектора с= ~~» Л;а; и любого числа д> ~» Л;6»ч »ьэ м »вя м что (4) будет следствием (1). Оказывается, других следствий у ЛН не бывает.

А именно справедлива 33 Лиммл Феркаша (афвякая). Линейное неравенство (4) является следствием разрешимой в вещественных переменных системы ЛН (1) тогда и только тогда, когда существует вектор Л Е Кш: с=~~~ Л;еб Н>~~ Л;Ь;, Л;>О %ЕМ. (6) атем нем (Схему доказательства см. в (3, с. 1В].) Лля неразрешимой системы ЛН (1) можно формально считать следствием (1) заведомо неверное неравенство (О, х) < — 1 и далее пользоваться афинной леммой Фаркаша, как показывает Лнммл Фаркаша о неразрсшилоствв.

Система ЛН (1) неразрешима тогда и только тогда, когда разрешима система ~ь Л|а;=О, ~~ь Л;Ь|< — 1 Лс>О %ЕМ. (6) гем нем Локлзлтнльстио. Пусть (1) неразрешима, тогда из разрешимости системы (а;,х) + х„+1 < Ь; е1 Е М должно следовать, что х„+1 < -с < О, т.е. следствием этой системы является неравенство ((0,...,0,1/с),(х,х„+~)) < -1 и из афинной леммы Фаркаша получаем (6) (а также в'дополнение 2 Л; = 1/с). Если же (6) разрешима, то указанное выше неравенство (О, х) < — 1 оказывается следствием (1) и должно выполняться для всех х, удовлетворяющих (1), значит, таких не существует.

пйп (~~ Л;Ь;~ ~ Л;а; = с, Л; > 0 Ув Е М), илв в краткой записи |ем ~ем 34 Теперь мы можем доказать основной теоретический результат ЛП вЂ” теорему двойственности, на которой базируются как методы решения задач ЛП, так и способы анализа решения, и которая фактически дает необходимые и достаточные условия оптимальности в ЛП. Наличие двойственности, обусловив хорошую характеризацию задачи ЛН, предопределило полиномиальность ЛП. Опгеделение 4. Двойсшеенней к задаче ЛП на максимум с ограничениями неравенствами в форме озЛП (2) называется следующая задача ЛП на минимум с ограничениями в канонической форме: (7) ппп (Л, Ь). ллиус лйс Лля того, чтобы построить двойственную к произвольной задаче ЛП, надо представить ее в форме озЛП, применить формулу (7), а затем вернуться к обозначениям исходной задачи.

'УПРАЖНЕНИЕ 7. Показать, что двойственная задача к двойственной задаче ЛП совпадает с прямой задачей ЛП: представить (7) в форме озЛ П (анвлогично упражнению 5), выписать двойственную к полученной задаче я свести ее к (2). Тнегкма 4 (деоястпаенноспьи ЛЛ). Задача ЛП разрешима тогда и только тогда, когда разрешима двойственная к ней. В случае разрешимости оптимальные значения целевых функций в обеих задачах совпадают, т.е. я" = я", где и" — значение (2), и"* — значение (7). Покязлтнльстно проведем для случая озЛП, поскольку любая задача ЛП адекватно представляется в такой форме.

Пусть задача (2) разрешима, тогда (4) является следствием (1) 'эе > а' и не является Ы < я', что по афинной лемме Фаркаша эквивалентно разрешимости (5) при а > и' и неразрешимости (5) при Ы < и", т.е. е' = ш1в(Н~ (5)), а это и есть значение (7). И наоборот, из разрешимости (7) следует неразрешимость (6), ибо в противном случае шш в (7) обращался бы в -оо (так как прибавление решения (6) к решению (7) дает допустимую точку и уменьшает значение целевой функции (7)).

Отсюда получаем разрешимость (1) по лемме Фаркаша о неразрешимости. Кроме того, разрешимость (7) означает разрешимость (5) для любого и' > а", так что (4) оказывается следствием (1) для И > Н'", и поэтому д" ограничивает сверху значение (2), т.е. максимум в (2) достигается. Таким образом получили разрешимость задачи (2) и можем вернуться к началу доказательства для установления равенства И' = и". Из теоремы 4 непосредственно получаем Утвпгжднник 3.

Задача ЛП оптимизации эквивалентна решению системы линейных неравенств. Лействительно, озЛП (2) эквивалентна задаче ЛП (7) и обе они эквивалентны системе ЛН относительно неизвестных (х, Л): Ах<Ь, (с,в)=(Ь,Л), ЛА=с, Л>о. (8) 35 Утввгждвнив 4. Задача ЛП оптимизации эквивалентна решению системы линейных уравнений в неотрицательных переменных. Локлзлткпьство.

От системы ЛН (8) переходим к ограничениям в канонической форме аналогично упражнениям 5,7. Утввгждение 5. Задача Л П эквивалентна поиску неотрицательного ненулевого решения однородной системы линейных уравнений. Локлзлтнльство. На основании утвержления 4 озЛП сводится к некоторой системе ЛН (с целыми коэффициентами) относительно вектора вещественных неизвестных уд (9) пусть Р— матрица (К х (К вЂ” 1)). Введем параметр Н, мажорирующий координаты какого-то решения (9) (по теореме о границах решений), если система (9) разрешима. Лобавим к (9) неравенство (у, е) = у1 + + ук-1 < ФН, которое превратим в равенство с помощью дополнительной переменной ук: (9, е) = 91 +" + Пк 1+ Пк = ФЯ, а (9) перепишется как [Р]О]у = д, у > О.

Теперь сделаем замену переменных х:= у/Рс и обозначим Р =' МН[Р[О] — [у[4]... [д]. Придем к однородной системе Рх = О с дополнительными ограничениями х = (хы...,хк) > О, (х,е) = М, что соответствует системе Рх = О, х > О, (х,е) > О с решениями-лучами гхэ 1Й > О, любое из которых пересчитывается в решение исходной системы. 2. Мешод Кармаркара (Х. Кагшагкаг, 1984 г.).

Воспользуемся утверждением 5 и обозначениями, введенными при его доказательстве. Пусть р(х) =' ((ры х))з + ... + ((рл,х))з, где р; — строки Р. Тогда р(х) = О эквивалентно Рх = О. Введем фумквию Кармаркара й(х) = [„( )]лЧг Применяя теорему 2 и алгоритм округления к задаче решения (9), можно показать, что для точного ее' решения достаточно найти такой х > О, для которого й(й) < 1/[3(Ь(Р))к] [3, с. 25-26]. Полиномиальный алгоритм поиска нужного приближенного й приводится в [3, с. 26-28], и мы не будем его описывать. Отметим 36 только, что аналогичный алгоритм может быть построен на основании применения метода Ньютона (см. в разд.З) к задаче минимизации функпии Кармаркара или ей подобных. В результате получаем пелый класс полиномиальных алгоритмов ЛП, которые на практике оказываются сравнимыми с симплекс-методом, не имея теоретических недостатков последнего.

Предложенные алгоритмы строятся на принпипиально новой идее: не дискретной, а непрерывной трактовки задачи ЛП, когда вместо перебора конечного числа угловых точек осуществляют поиск решения в исходном пространстве вещественных переменных, и траектории алгоритмов не проходят через угловыцточки. Напомним, что метод эллипсоидов также не ориентируется на угловые точки многогранника ограничений.

Характерно, что именно такой уход от дискретного программирования позволил построить полиномиальные алгоритмы ЛП. Поэтому далее будет дан некоторый, обзор основных подходов к решению непрерывных задач оптимизапии. ЗАМЕЧАНИЕ. Если бы речь шла о непосредственном поиске точного решения задачи ЛП указанными методами, то нельзя было бы гарантировать конечношаговость (не то, что полиномиальность) соответствующих алгоритмов.

Лля их применения существенной является возможность остановки в приближенном решении благодаря наличию полиномиального алгоритма округления. Но поскольку для его работы требуется начальное приближение из определенной окрестности решения, зависящей от длины 1 или высоты Ь, или длины входа Ь конкретной задачи Л П, то и число итераций алгоритмов, базирующихся на рассматриваемом принципе, зависит от числа цифр в записи элементов матрицы ограничений. Так что не удается использовать данную идею для построения сильнополиномиальных алгоритмов ЛП, кроме как в частных случаях ограниченности элементов матрицы (например, в задачах на графах и сетяк, где аб = О, ~1). 3.

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ (МП) Литературат 4. Карманов В. Г. Математяческое программирование. М.: Наука, 1986. ' 5. Сухарев А. Г., Тнмохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1985. 6. Мину М. Математическое программирование. М.: Наука, 1990. 18. Обзор адей МП Классификация задач вбП. Преимушества выпукаово случал. Поиятпие о градиспотиых и Пьютпоиовских метподах минимизации. Усаовиая опптимизацив, способы освобождепио от оераиичсииб (мстоды барьеров и штпрафов). 1.

Задача ЛН, как и задача минкмизации функции Кармаркара, является частным случаем задачи МР: .(( ) вЕХ Здесь требуется нанти агб ппп у(х) б Агй пнп Дх), т.е. вЕХ вЕХ х* б Х' = (х' б Х~ ~(х") <,т(х) ттх б Х), и ) = Дх'). (2) Любой такой х* называется решеиием (1); у" — зиачеиие (1), или оптимааьпое зпачеиие целевой функции у в задаче (1), Х вЂ” мпожесптво ограиичепиб или допусптимое миожесптво. В зависимости от природы множества Х задачи оптимизации классифицируются как: дискретные (комбинаторные) — Х конечно или счетно, целочисленные — хт б Е, булевы — хд б В, вещественные (непрерывные) — Х С Ии, бесконечномерные или в функциональном пространстве, например, когда Х вЂ” подмножество гильбертова пространства Ьз, и т.п. В данном рззделе будем по преимуществу рассматривать задачи с вещественными переменными, которые собственно и называются (традиционно) задачами математпическоео проераммироваиия (ЗМП).

Если Х С Ии, то говорам о задаче усаовпой оптимизации (при условии х б Х), иначе (Х = Ип) получаем задачу безусловной оптимизации. 38 Лля ЗМП минимум в (1) достигаегся в условиюс теоремы Вейерштрасса (у непрерывна, Х компактно или для некоторого х б Х ограничено ммохсгсшоо Лгбегг функции ~ — (х к Хы (х) < г (х))). Кроме разделения на условные и безусловные, ЗМП классифицируются по свойствам целевой функции и множества ограничений соответственно на задачи ЛП, выпуклого программирования, гладкие или негладкие и др. Лля каждого из классов ЗМП разрабатываются свои численные методы их решения.