Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 8
Текст из файла (страница 8)
(а) Каждый выпуклый многогранник является выпуклой оболочкой его вершин. (б) Обратно, если )г — конечное множество точек, то выпуклая оболочка множества «' представляет собой выпуклый многогранник Р. ггг[ножесгггво вергиин многогранника Р является подмножеством множества Г 2.3.3. Многогранники и ЛВ. Согласно теореме 2,3, многогранник Р можно предсгавлять несколькими различными способами: 1. Выпуклая оболочка конечного множеспгва точек. Такой подход довольно удобен, когда даны лишь вершины многогранника, как, например, в гл. 13 и 19 при обсуждении некоторых комбинаторных задач. 2.
[гересечение нескольких полупросгггранств, при условии что это пересечение ограничено. Это естественный способ предсгавлеипя многогранника в том случае, когда соответствующие неравенства заданы явно. Мы увидим далее, что именно такая ситуация имеет место в задачах ЛП. 3. Третий способ представления многогранника — это алгебраическая версия способа 2.
Пусть Ах=Ь, х)0, (2.8) — уравнения и неравенства, определяющие допустимую область Р некоторой задачи ЛП, удовлетворяющей предположениям 2.1, 2.2 и 2.3. Так как ранг А равен т, где А — матрица размера тхп, то можно считать, что уравнения Ах=Ь имеют вид х;=Ь; — Х аг х, Е=-п — т+1, ..., и, (2 8) г=г поскольку в противном случае можно найти базис В в А (без огра- 42 Гл. 2. Симплекс.алгориви« ничения общности можно считать, что это последние т строк в А) и, домножив (2.8) на В ', получить (2.8'). Таким образом, условия (2.8) эквивалентны системе неравенств Ь; — Х аух,)0, г=и — т+1, ..., и, !=! ху)0, 1=1, ..., и — т.
(2.9) Но неравенства (2.9) описывают пересечение и полупространств, которое, согласно теореме 2.2, ограничено. Следовательно, (2.9) определяет выпуклый многогранник Р«=.К " ', Обратно, пусть Р— многогранник в 1«" . Тогда и полупространств, определяющих Р, могут быть выражены неравенствами Йе«х«+... +й! „х„+д, <О, »=1, ..., п. (2,10) Учитывая принятое соглашение, можно считать, что первые и — т неравенств в (2.10) имеют вид х!)О, »=1, ° ° ., п т.
Пусть Н вЂ” матрица, составленная из коэффициентов остальных неравенств. Введя т переменных недостатка х„+„..., х„, можно получить Ах=Ь, х)0, где (тХп)-матрица А имеет вид А=(Н)1) и хай". Таким образом, любой многогранник (удовлетворяющий нашему соглашению) можно представлять после некоторых преобразований как допустимую область Р некоторой задачи ЛП. Более того, любую точку х=(х„... ..., х„„,) ц Р можно преобразовать в х=(х„..., х„) Е Р, положив х,= — д! — Х й, х, !=и — т+1, ..., п. (2.11) !'= ! Теорема 2.4. Пусть Р— выпуклый многогранник, Р = (х: Ах=Ь, х) О) — соответствующее допустимое множество некоторой задачи ЛП и х= (х„..., х„) ц Р.
Тогда следующие условия эквивалентны. (а) Точка х является вершиной многогранника Р. (б) Если х=Хх'+(1 — Х) х", где х', х«цР, 0 < е. < 1, то И наоборот, любую точку х=(х„..., х„)ср можно легко преобразовать в х=(х„..., х, „)бР простым отбрасыванием последних т координат в х.
Покажем теперь, как эти три точки зрения связаны с нашим по. иятием «угла». е.э. Геометрия оодон линейного проериммироеония 43 х'=х"=х (другими словими, х не может быть строгой выпуклой комбинацией точек из Р). (в) Соответствующий вектор х из Р, определяемый равенствами (2.11), есть бдр в Р. Доказательство, (а) =э (б). Пусть к — вершина и существуют точки х', х" ЕР, отличные от х, такие, что я=ах'+(1 — ).)х", где 0 < Х < 1. Так как х — вершина, то существует полупространство Но=(х~ И": й'х<д), такое, что НКП Р=(х). Тогда х', х" (НИ и, следовательно, й'х' ) у и й'х" ь р.
Отсюда й'х= = й'(),х'+(1 — Х) х") ь д и х(НЯ; получаем противоречие. (б) ~ (в). Предположим, что х обладает свойством (б), и рассмотрим соответствующий элемент х из Р. Определим подмножество Я столбцов матрицы А следующим образом: З= (А,: х~>0, ! к! ~ ~п). Покажем сначала, что зто множество столбцов линейно независимо. Пусть это не так. Тогда найдутся целые числа с!н не все равные О, такие, что ну яЗ Х й,л,=о. ( ) 2.12 Так как хср, то Х хл=ь (2.13) Ало З н, кроме того, хе)0, 1=1,..., и. Умножим (2.12) иа некоторое число О, полученное равенство прибавим к (2,13) и вычтем из (2.13). Получим Х (х,~йй,) Л,=Ь.
лреЗ Т ак как хе)0 для А,бЗ, можно выбрать положительное и достаточно малое О таким образом, что хе~04)0 для всех А~бЗ. Следовательно, мы нашли две точки, определяемые равенствами ху Оде Ау е З~ О, А(З, х +Ойм А ~З, О, А(З, э такие, что х', х" ЕР, т. е, х', хы ~ Р и х=х'12+х"!2; получили противоречие. Мы показали, что множество столбцов З линейно независимо, и, следовательно, Щ<т.
Поскольку мы предположили, что в А имеется т линейно независимых столбцов, то всегда возможно расширить множество Я так, чтобы оио содержало т линейно независимых векторов. В этом случае они будут базисиыми столбцами, от- Гл. л. Симплекс.алаориепм куда следует, что х — бдр. (в) -е (а). Если у=(уь ..., у„) — бдр задачи Ах= — Ь, х)0, то, согласно лемме 2.2, существует вектор стоимости с, такой, что у является единственным вектором х б Р", удовлетворяющим условиям в'х< с'у, Ах= Ь, х) О.
Как легко видеть, этн условия означают, что у= (у;, ..., у„„)— единственная точка в Й", удовлетворяющая неравенствам егх(е)'у, хЕР, где с)е с; ~ й„+мер„~+, 1= 1, ° ° ., п — т. ~'=! Следовательно, у — вершина многогранника Р, для которой соответствующая опорная гиперплоскость определяется равенством д'х = сГу. ( ) В $ 2,9 будет дана очень простая характеризация ребер многогранника Р. Теоремой 2.4 установлено соответствие между вершинами многогранника Р и базисами матрицы А.
Если ланы две различные вершины и и и' многогранника Р, то соответствующие базисы Я и Я' должны быть различны, поскольку базис однозначно определяет бдр и, следовательно, вершину. Однако, два различных базиса Я и Я' могут соответствовать одному и тому же бдр х. Пример 2.4. Вернемся к многограннику, показанному на рис. 2.1, и соответствующей задаче ЛП. Матрица А и вектор Ь в ней имеют вид 1111000 1000 100 0010010 0310001 Рассмотрим базисы Я=(А;, А„А„А,) и Я'=(А„А,, А,, А,). Для обоих базисов В 'Ь=В' "Ь=(2, 2, 0,0, О, 3, 0), Причина такогосовпадения ясна из рис.
2.1. Для вычисления вершины, соответствующей Я, полагаем хл — — х,=х,=О, а это означает, что соответствующие три неравенства должны обратиться в равенства, которые определяют вершину (2, 2, 0) как пересечение трех гиперграней. При рассмотрении Я' мы заменяем ограничение х,+х,+хе(4 на хл' -О. Но оказывается, что гиперплоскость х,=О проходит через ту же вершину (2, 2, 0), и поэтому ничего не изменяется. Таким образом, вершина, подобная данной, должна лежать более чем на а — т=3 ги- 2.8, Геометрия задач линейного программирования пергранях; другими словами, бдр должно иметь более чем и — т=З нулей.
(:) Определение 2.5. Бдр (и соответствующая вершина) называется вырожденным, если оно содержит более чем н — т нулей. Сформулируем теперь существенный результат наших обсуждений. Теорема 2.5. Если два различных базиса соответствуют одному и тому же бдр х, то х вырожденно. Доказательство. Пусть Я и Я' определяют одно и то же бдр х.
Тогда х имеет нули в и — т столбцах, не входящих в Я. Кроме того, оно должно иметь нули в столбцах Я вЂ” Я'~ 8. Следовательно, оно вырожденно. ( ) Следующее утверждение равносильно доказательству того факта, что задачу ЛП можно решить за конечное число шагов. Теорема 2.6. В любой индивидуальной задаче Л)г имеется оптимальное бдр. Более того, если имеется г) оптимальных бдр, то их выпуклые комбинации также оптимальны. Доказательство. Согласно теореме 2А и ее доказательству, сформулированное утверждение эквивалентно тому факту, что в многограннике Р найдется оптимальная вершина и что если д вершин из Р оптимальны, то их выпуклые комбинации также оптимальны относительно линейной функции стоимости д'х, Множество Р замкнуто и ограничено, поэтому линейная функция д достигает своего минимума на Р.
Пусть хг — оптимальное решение, и пусть х„..., хн— вершины многогранника Р. Согласно теореме 2.3, можно записать и И х, = ~я~~ а, х„где ~, 'и, =-1, а,)0. г=1 г Пусть ) — индекс, соответствующий вершине с наименьшей стоимостью. Тогда д'х,= Х агд'х;ьд'хг Х а;=д'х» г=с г=| откуда следует, что хг оптимально.
Для доказательства второй части теоремы предположим, что вершины х,, ..., х„оптимальны и у — выпуклая комбинация этих вершин. Тогда у ойтимально, поскольку г д у =й Х а;х;, = Х а, (д'х~,) = д'хйг () г 1 ' г 46 Гл. л. Сссмалека-алгоСсссасм Таким образом, мы установили, что индивидуальную задачу ЛП можно решить за конечное число шагов: нам достаточно проверить стоимость в каждой вершине многогранника Р. Более того, можно порождать все вершины многогранника Р (на самом деле все бдр) систематически, рассматривая каждое множество, содержащее лс столбцов, инвертирун соответствующую матрицу В и отбрасывая те случаи, в которых в В 'Ь имеется отрицательная компонента. Однако этот алгоритм едва ли можно использовать на практике в задачах среднего размера, поскольку число возможных вершин очень велико.
Используя описанное геометрическое представление многогранника Р и его вершин, мы можем разработать сейчас симплекс-алгоритм, в котором переход от вершины к вершине производится систематическим способом, избегая в результате перечисления всех вершин. 2.4 Переход от одного бдр к другому Пусть к, — бдр в индивидуальной задаче ЛП с матрицей А, соответствующее упорядоченному множеству индексов базисных столбцов З=(А„,с,.' с=1, ..., т).
Если к„, с'=1,..., лс,— базисные компоненты вектора км то Х х„Агап — — Ь, где к„)0 (2.14) с и, как обычно, Ас б сс™ использУетсЯ длн пРедставлениЯ 1-го столбца матрицы А. По определению множество базисных вектор-столбцов З линейно независимо, поэтому можно представить любой внебазисный столбец Ас б ск, Ас ( Я в виде линейной комбинации базисных столбцов ~.", ксСА в ш = '" Р (2.15) сы с Умножая (2,!5) на скаляр О)0 и вычитан полученное равенство из (2.14), получаем очень важное равенство т Х (хсл-Окст) Ав ссс+ ОАт =Ь (2.16) с Будем считать пока, что х, невырожденно; тогда хы)0 для всех к;„, и, увеличивая О, начиная с нуля, будем переходить от данного бдр к некоторым допустимым решениям с я+1 строго положительными компонентами. Как долго мы можем увеличивать О и все еще оставаться в допустимой области? До тех пор, пока одна нз компонент(хс,— Оксс) не обратится в нуль, что произойдет при значении О, = ппп ксл!ксР (2.17) с: *ст > а 2,4, Переход от одного ддр к другому 47 Пример 2.0.
Рассмотрим задачу ЛП с ограничениями из примеа 2.2 (или 2.4) Базису Я=(А„А„А„А,), заданному условями (1)=-1, В(2)=-3, В(3)=б, В(4)=7, соответствует бдр х=(2, О, 2, О, О, 1, 4). Внебазисный столбец А,=со! (О, 1, О, 0) можно представить в виде Т еорема 2.7. Пусть дано бдр х, с базисными компоненгпами хг„(=1, ..., т, и базисом Я= <Азий 1=1, ..., т), и пусть! таково, что Аг(Я. Тогда новое допустимое решение, определяе- мое равенствами О,= ш!и (хг,/х«) =хгг/хгт. (2.10) ;,х«>о х„— Ох«, 1Ф1, является бдр с базисом Я', в котором 1 В(1), В' (1) =~ (2.20) Если минимум в (2.10) достигается при более чем одном 1, то новое бдр вьгрожденно. (2.19) А, =х,гА, +х„Аг+х„А„+х„А, = Тогда равенство (2.!0) принимает вид (2 — О) А, + (2 + О) А, + (1 — О) А „+ (4 — О) А, + 0 А г = д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
