Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 9
Текст из файла (страница 9)
Из рис. 2.1 видно, что при возрастании 0 от 0 до 1 это семейство допустимых точек (2 — О, О, 2+0, О, О, 1 — О, 4 — О) движется от вершины (2, О, 2) (и бдр (2, О, 2, О, О, 1, 4)) к вершине (1, О, 3) (и бдр (1, О, 3, О, 1, О, 3)). Равенство (2.17) дает Ог=!, и новым базисом становится Я' с В'(1)=1, В'(2)=3, В'(3)=5 и В'(4)=7. ( г Отметим два частных условия, которые могут иметь место для бдр х,. Частный случай 1. Если х, вырожденно в силу того, что некоторое х„=О, а соответствующее х«положительно, то 0,=0, согласно (2.17), и мы не движемся в й". Мы остаемся в той же вершине, однако можем считать, что переходим к новому базису, заменяя столбец В(1) столбцом /.
Мы иногда будем говорить в таком случае, что переменная хг входит в базис на нулевом уровне. Частный случай 2, Если все х«, г=1,..., т, неположительны, мы можем двигаться сколь угодно далеко, оставаясь в допустимом множестве. В таком случае Г не ограничено, что противоречит нашему соглашению об ограниченности г', принятому на основании теоремы 2.2.
Остается показать, что новая точка, полученная в результате описанного выше процесса, на самом деле является бдр. Гл. л, Симплекс.олгорио!м Долажипельсп!во. Из рассуждений, относящихся к (2.!б) и (2.17), следует, что х,' с компонентами, определяемыми из (2.!9), является допустимым решением. Поэтому остается показать, что это решение— базисное.
То есть мы должны показать, что множество базисных столбцов Я' линейно независимо. Предположим, что для некоторых констант !1! Го л Х !(!Ав ш = о(!Ау+ 2. "а!Аз н! — О. (2.2!) с=! ~= ! !~! Подставляя Ах= Х х!хАвы! !=! (2,22) получаем Х (о(!х!~+о(!) Авп, +д!хцАв!и — — О. != ! (2.23) 2.$ Организация табпицы В предыдущем параграфе мы считали, что з любой момент можно легко получить представление (2.22) любого внебазисного столбца Аз через базисные столбцы. И если мы хотим построить алгоритм, который в большой степени использует переход от вершины к вершине, то очень важно, чтобы в нашем распоряжении всегда были коэффициенты хы. Это можно обеспечить, если хранить заданную систему уравнений приведенной к диагональному виду относительно базисных переменных.
Предположим, что на каждом шаге мы храним массив чисел размера и! х (и+!), который представляет собой информацию об исходных ограничениях в виде равенств Ах=Ь. Так, например, систему Это линейная комбинация исходных базисных векторов, поэтому все коэффициенты в ней должны равняться нулю. В частности, о(!хм!=0 и, следовательно, !(!=О. Тогда из (2.2!) вытекает, что остальные о(! также равны нулю и, следовательно, новый базис действительно линейно независим.
Для завершения доказательства заметим, что если минимум в (2.!8) достигается при более чем одном !, то соответствующие компоненты в х,' обращаются в 0 согласно (2.!9). Это означает, что х,' вырожденно. (! Описанный метод перехода от одного бдр к другому называется зал!ещением. Мы будем говорить, что столбец В(1) выводится из базиса, а столбец 1 вводится в базис.
49 х.б, Органиэация таблицы уравнений Зх,+2х,+х, =1, бхг+ ха+«в+«4 =Зг 2х,+бх,+х, +х,=4 будем представлять таблицей «г хэ «в «э Г отделяя правые части уравнений вертикальной чертой и рассматривая их как нулевой столбец, Можно умножить любую строку в таблице на ненулевую консганту или прибавить любую строку, умноженную на произвольное число, к любой другой строке, при этом информация, представляемая соответствующей системой уравнений, не изменится.
Эти операции называются обычно элементарными операциями над строками. Если известен базис эд, можно произвести элементарные операции над строками так, чтобы базисные столбцы образовали единичную подматрицу: Ая,г,— — еи 1=1,, т, где е, обозначает вектор-столбец с т элементами, в котором в 1-й строке стоит 1 и в остальных строках стоит О. Таким образом, если в нашем примере%=(Ав, А„А„), то можно умножить строку ! на — 1 и прибавить ее к строкам 2 и 3, при этом получим х! «2 «э «г хэ В нулевом столбце стоят сейчас значения базисных переменных хаи,— — хиь 1=1, ..., т, которые получаются, если внебазисные переменные положить равными нулю. Заметим, что внебазисные столбцы содержат в точности числа хы, например, Аг = ЗА„+ 2А, — А, = Х хн'4 в пи г=г Следовательно, можно непосредственно произвести вычисления, необходимые для изменения базиса.
Пусть, например, мы хотим ввести в базис столбец 1= 1; тогда (2.18) дает О = пц'и ( — ) =- при 1=1=1. /хм! ! в с.„, (г) 1« ) 3 Таким образом, нам необходимо получить в столбце 1=1 единичный вектор с 1 в строке 1=1. Для этого мы разделим строку 1 на 3 и при- 1' Гл. л. Симплекс-алгариспм бавим ее к строке 3, затем умножим строку 1 на — 2 и прибавим к строке 2.
Обычно для представления этой операции мы будем в таблице обводить кружком «ведущий» элемент хиь так, как это сделано в (2.24). Новая таблица имеет вид х~ «е хе хл ь1' Новым базисом будет множество столбцов УЗ'=(Ап А„Ал), соответствующее бдр: х,'= — 113, х,'=4)З и х;„'==-1О/3. В общем случае если х;; и х';, — соответственно старая и новая таблицы, З и Я' — соответственно старое и новое базисные множества и х,л — ведущий элемент, то х„= хсл/хс, д = О, / В(е'), ей(, В' (1) = ~ Теперь, когда мы знаем, как переходить от одного бдр к другому, необходимо исследовать влияние таких переходов на стоимость.
2.6 Выбор выгодного столбца Стоимость бдр х„соответствующего базису З, равна ге=~',",х;сепии Рассмотрим теперь процесс введения в базис столбца Ан Выразим Ае через базисные столбцы Ау= Х хе~Авил (2.2б) с ! Это равенство можно понимать в том смысле, что для каждой единицы переменной х, вводимой в базис, количество хы каждой персменной хвео должно покинуть базис, Таким образом, возрастание переменной х, па единицу приводит в результате к изменению стоимости на величину с; — Ъ",",хысв,о. Величина, задаваемая здесь суммой, достаточно важйа, чтобы иметь собственное обозначение.
Мы обозначим ее г; и назовем разность с;=с,— г; оепиосшпельной селоилеоселью столбца 1. Тогда столбец 1 выгодно ввести в базис в том и только в том случае, если с;<О. Более того, если с;>О для всех 1, то мы имеем локальный оптимум, который является также глобальным оптимумом. Ниже мы дадим более подробное доказательство. 2.б.
Выбор выгодного ововбцо Введем сначала некоторые векторные и матричные обозначения. Для любой таблицы Х через В обозначим (!пхт).матрицу, состоящую из столбцов матрицы А, с!ютветствующих базису в Х, и пусть са есть пь-вектор стоимостей, соответствующих этим базисным переменным.
Поскольку таблица Х получена диагонализацией базисных столбцов матрицы А, можно предсгавигь Х в виде Х =В 'А и вектор г=со1 (г„..., г„), согласно его определению, в виде г'= =свХ=св В 'А Мы будем неоднократно использовать эту матричную терминологию в дальнейшем. Теорема 2.8 (критерий оптимальности). Для бдр х„операция за. меи(ения, при которой х, вводится в базис, изл!еняет стоимость на величину (2.27) О,с,=О,(сх — г ).
Если с=с — г~ )О, (2.28) то х, оптимально. Доказательство. Согласно равенству (2,19) из теоремы 2.7, новое решение имеет вид хм — О,х!, х)о ОО ь=1, поэтому новая стоимость равна г,'= ~чз (х,„— О,х, ) сап,+О с =г,+11„(с1 — г1), Е=! сэ! откуда следует (2.27). Покажем, что из условия с)0 следует оптимальность х,. Г1усть у — любой допусгимый вектор, не обязательно базисный. То есть Ау=Ь и у)0. Так как с=с — г)0, то для стоимости у имеем с'у .-г'у=сьВ 'Ау=с!!В !0=с'х„ откуда следует, что стоимость вектора у не может быть меньше стоимости хо. () Поскольку значения с, дают информацию о том, выгодно ли вводить столбец в базис, хотелось бы хранить их как часть таблицы.
Обычно они хранягся в строке 0 следующим образом Запишем уравнение стоимости в виде 0= — г+с,х, +...+с„х„. (2.29) Тогда относительная стоимость сь соответствующая базисному Гл. 2. Симплекс-алгоритм столбцу 1, равна сд = сд г = с ~л~~ хг са г — — О, г=! поскольку хг †единичн вектор с 1 там, где В (!) = 1.
Если рассматривать равенство (2.29) как нулевую строку нашей таб- лицы, то ее компоненты, соответствующие базисным столбцам, можно сделать равными нулю, умножая г-ю строку на — са и, и прибавляя полученное к нулевой строке. При этом во вне- базисиом столбце получается величина с, = сг —,л~гг, х;, с „, т и в левой части нулевого уравнения получается — г,= — Х хмсаго. г=! Таким образом, нулевая строка принимает вид л — г, = — г+ ~~Р~ сгхр (2.30) 1=! у Если считать теперь, что таблица задана в диагональном виде отно- сительно гп+1 йеременных ха„„ха„п ..., хною и — г, то легко видеть, что для нулевой строки примейяются те же самые правила замещения, что и для строк от 1 до т.
Следовательно, можно хра. нить относительные стоимости с1, используя одну дополнительную строку в таблице. При этом, естественно, нет необходимости хра- нить столбец для переменной — г. ргосебиге СИМПЛЕКС Ьеа1п опт: =«нет», неограниченна: =«нет»; (сопппепт: если любая нз этих переменных принимает значение «да», то алгоритм останавливается) пЬ11е опт=«нет» апб неограниченна=«нет» бо И с!сап для всех ! !Ьеп опт:=«да» е1зе Ьед!п выбрать любое 1, такое, что с! < О; и хи м,о для всех ! !Ьеп неограниченна:=«да» е! зе найти Ое= гп!и 1хгз) к!«а ':л >в хп хы и произвести замещение относительно хн! епб епб Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
