Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 11
Текст из файла (страница 11)
Тогда алгоритм заканчивает работу после конечного числа замещений. Доказательство' ). Покажем, что предположение о существовании цикла приводит к противоречию. Для того чтобы появился цикл, необходимо, чтобы после конечной последовательности замещений мы вернулись к некоторому бдр. Стоимость г должна оставаться постоянной в течение всего цикла, и значение хи, соответствующее каждому замещению, должно равняться нулю, ибо в противном случае 9,= О, откуда следовало бы, что г убывает. Отсюда в свою очередь вытекает, что нулевой столбец хно 1=1, „,, т, остается постоянным в течение всего цикла. Отбрасывая строки и столбцы, не содержащие ведущих элементов во время цикла, получим новую задачу линейного программирования, которая также зацикливается и в которой все х„=О и г постоянно в течение цикла. Пусть теперь а — наибольший индекс переменной, вводимой в базис во время цикла.
Рассмотрим две таблицы: таблицу Т;, после которой хе вводится в базис, и таблицу Т„после которой х выводится из базиса (рис. 2А). Обозначим элементы таблиц Т, и Т, соответственно через хы и хоч а соответствующие им базисы — через,Тл и Я, и пусть столбец р вводится в Т,, Применим лемму 2.3, построив два решения.
Для Т, мы просто используем бдр х„отождествляя Т, с Хь Для Т, определим решение у следующим образом: 1, если )=р, уг — — — хтр, если Аг б М, О в противном случае. Заметим, что у хотя и не является ни базисным, ни допустимым, но все же является решением системы уравнений Ау=о и, следователь- '1 Доказательство представляет собой упрощенный вариант доказательства Бленда, приведенного в работе (Кп). 2.7. Выбор ведущего ялемента и алгоритм Бленда 59 но, удовлетворяет требованиям леммы 2.3. Кроме того, стоимость РешениЯ У Равна 7+х,р, поэтомУ заключение леммы 2.3 дает с У= =х„р(0. Неравенство вытекает из того, что столбец р вводится в Т, и, следовательно, должен иметь отрицательную относительную стоиместь х,р.
Вводится ч Т~ элементы х„ базис Ьэ Выводится Вводи~аз лср 7'т,элсменты хо базис З Рис. 2.4, Таблицы Т, и Т, из доказательства теоремы 2.9. Переменная ха вводится в базис н Т, и выводится из базиса в Т,. Согласно выбору ведущего столбца в Т„получаем О, ~(д, с ~ 71 (О, р=д, и, согласно выбору ведущей строки в Т„ Д вЂ” х, (О, /=Ч / О,! или — хтр)0, т (о. Следовательно, с' у = ~ с,у, + с уа ' .
.сеуа > О. ~<а .Пришли к противоречию. П 60 рь 3'. Свлилеке-в»горев!л 2.о Начало симплекс-апгоригма Мы не осветили только один момент: как получить исходное бдр, с которого можно нач;ать симплекс-алгоритм? Конечно, иногда можно получить бдр как часть формулировки задачи. Например, если вначале нам даны неравенства вида Ак~й, то в этом случае переменные недостатка образуют бдр. Если же нам пе повезет, можно использовать метод! игнуественнык перел!енных, или двукэтапный метод.
В этом методе просто слева от таблицы следующим образом добавляются новые (!!искусственные») переменные х,'., 1=1,...,т: х' х! к! > О !' = 1...,, П х!' > О ! = 1...,, и! Некоторые исходные уравнения мы умножили на — 1, чтобы было Ь~О. Мы имеем теперь бдр х!=Ь!. т На этапе 1 минимизируется функция стоимости $= ~х,' при !=1 заданных выше ограничениях о использованием симплекс-алгоритма. Возможны три исхода. Случай 1. Стоимость С уменьшилась до нуля, и все к'; выброшены из базиса; в этом случае мы получили бдр для исходной задачи. Случай 2. Мы достигли оптимальности с $)0; в этом случае в исходной задаче нарушается предположение 2.2 о том, что имеется некоторое допустимое решение (если бы существовало допустимое решение в исходной задаче, то из этого вытекало бы, что минимальное значение $ равно нулю), Случай 3.
Стоимость $ уменьшилась до нуля, однако некоторые искусственные переменные остались в базисе на нулевом уровне. В случае 1 можно отбросить столбцы, соответствующие искусственным переменным, и продолжать непосредственно этап 11— обычный симплекс-алгоритм с использованием исходной функции стоимости к е'х. Иногда удобно начать с двух строк стоимости— К8.
Начало оимимхо-аооорамма е! 1 одной для $ и одной для г. При переходе от этапа 1 к этапу П нужно *,. просто от первой строки стоимости перейти ко второй. В случае 2, : естественно, необходимо просто остановиться. В случае 3 предположим, что 1-й столбец базиса в конце этапа 1 . соответствует искусственной переменной и х,,=О. В качестве ве', дущего элемента можно выбрать любой ненулевой (не обязательно , положительный) элемент хн строки 1, соответствующий не искусст- ~ венной переменной. Поскольку О„будет равно О, то не произойдет ,' ии нарушения допустимости, ни изменения стоимости $.
Это не ", есть в точности замещение, поскольку возможно, что х;га.О или О; мы скажем просто, чтомыаыгонлемискуссгпвеннуюпеременную ;: из базиса. Будем повторять это до тех пор, пока не получим допустимый базис с исходными переменными. Единственный случай, когда нам не удастся этого сделать — это когда некоторая строка будет нулевой во всех столбцах, соответствующих не искусственным - переменным.
Но это означает, что мы получили нулевую строку в исходной матрице элементарными операциями над строками, что противоречит предположению 2.! и показывает, что ранг матрицы А отличен от полного ранга и. Такие нулевые строки можно удалить и продолжить этап 1! с базисом меньшей размерности. Обратно, если ранг исходной системы уравнений отличен от полного ранга и, то нельзя прийти к случаю ! .
Следовательно, мы ' придем к случаю 2, если задача не имеет допустимого решения, либо некоторая искусственная переменная останется в базисе на нулевомуровневконцеэтапа 1 и тогда на самом деле и в конце этапа П. Пример 2.8. В примере 2.6 нам априори было известно мно, жество базисйых столбцов. Используя двухэтапный метод, мы на. чали бы с таблицы х! х! хоз х! хх х3 х4 хз Строка О' Строка О Вычтем строки 1, 2 и 3 нз строки О, соответствующей стоимости а, е тем, чтобы вначале относительные стоимости для нашего исходВого базиса хы х', и х' РавнЯлись нУлю.
ПолУчим 62 Гх. 2. Сээмпэмкс-алгориэхк хэ хэ хэ хэ "э хэ хэ Ниже приведены таблицы, получаемые последовательно иа этапе 1, с отмеченными в них ведущими элементами. х', хэ хэ К1 кэ хэ кэ ху х,= хэ = ю к,= л;= хэ х,= хэ1 = ба 2,9, Геометрические аспекта замеи!ения х» х< = «а = И конце этапа! имеем к=О, и полученная таблица оказывается иа самом деле оптимальной и для этапа П. (Заключительная таблица относительно переменных от х, до х, согласуется с заключительной оптимальной таблицей в примере 2.6.) () ргосебиге ЛВУХЭТАПНАЯ Ьей!п недопустима,'=<пег», излкшнят =«иет»; (сотгаепн иа »таис ! им могут быть присаосны значения «да») ааести искусстаспиый базис х1; саи СИМПЛЕКС со стоимостью "; =~х)'; и $еят > 0 иа этапе ! !Ьеп недопрстима: = «Да» е!ае Ьей!п Н искусственная псременяая аходит и базис и ие может быть выведена из него Н»еп иалишнят=«да», и опустить соот.
аетстиуюиьую строку; сан СИМПЛЕКС с исходиой стоимостью; епд Этап 1: Этап П: епб Рис. 2,5. Окоичательиыйдаухзтапиый алгоритм. 2.9 «немет рнческне аспекты замещения Решим задачу ЛП из примера 2.2 с помощью симплекс-алгоритма и проследим за последовательностью получаемых бдр на соответствующем многограннике. Получаемая в результате последова- Окончательный двухэтапный алгоритм приведен на рис.
2.6. . Заметим, что мы освободились от предположений 2.1 — 2,3; (1) если ранг матрицы А в исходной задаче не равен т, мы узнаем об этом в конце этапа 1 и можем продолжать работу; (2) если исходная задача недопустима, мы также узнаем об этом в конце этапа 1; (3) если стоимость в задаче не ограничена, мы узнаем об этом на этапе 11, е.р.
Геометрические асяекаае еамещеняя Рис. 2.6. 'яельность таблиц вместе с последовательностью вершин многой анника, соответствующих порождаемым бдр, показана на рис. 2.. с. 2.6. видим, что симплекс-алгоритм просто проводит некоторый путь ~о ребрам многогранника. Мы докажем сейчас формально, что так будет всегда. Определение 2.6. Лве вершины х и у многогранника называются :Фееежными, если отрезок (х, у) является ребром многогранника. '(ква различных бдр х и у некоторой задачи ЛП Ах=Ь, х)0, назы:ваются смежными, если существуют базисы Я„, З„, такие, что Яе= ' ~(DŽ— (Ат)) О (Ад) и х=В, 'Ь, у=В„1Ь. П Таким образом, в симплекс-алгоритме одно бдр заменяется друИмм, смежным с исходным и имеющим стоимость не больше чем у "исходного бдр, до тех пор, пока не получится оптимальное бдр. Теперь можно доказать следующее обобщение теоремы 2А на еч~РЕбРа.
Ф М зозя Е. Ги г. Симплекс-алгоритм 66 Теорема 2.!О. Пусть Р— некоторый многогранник, = (х: Ак=Ь, х эО) — соответствующее допустимое множество и х=(х„..., х„), у=(у„..., у„„) — различные вершины Р. Tагда следующие утверждения эквивалентны' (а) отрезок (х, у1 является ребром Р; (б) если для произвольного г Е (х, у)справедливо г=) г'+(! — ) ) г", где О < Х < 1 и г', г" Е Р, то г', г"' Е ~х, у|; (в) соответствующие векторы х, у из Р являются смежными бдр. Доказательство. (а) =а (б).
Если (х, у| — ребро Р,тго для него существует опорная гиперплоскость Н, уравнение котюрой пусть имеет вид й'х=у. Таким образом, и'я=у для каждого гЕ[х, у1. Предположим теперь, что г= Его+(1 — к) г", где О < Х < 1, г', г" Е Р, и по крайней мере одна из этих точек не лежит в (х, у1, Тогда й'г' < у, й'г" < а, и одно из нераве нств стра. гое. Следовательно, 11'г=й'().г'+(1 — ).)г") <д; получили про. тиворечие. (б)~(в). Допустим, что бдр х,уЕ г соответствуют гочкам из Р, удовлетворяющим свойству (б), но ие являются смежными, Пусть Ег„и ыг — множества столбцов, соответствующих ненулевым компонен гам, соответственно в х и у. Легко видеть, что най. дется бдр шФх, у, у которого ненулевые компоненты лежат галька в ыь„() ег„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
