Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 15
Текст из файла (страница 15)
3.$ 1 Двойственная информация в таблице Нас не должен удивлять тот факт, что заключительная таблица -' в симплекс-алгоритме дает как оптимальное решение прямой задачи, гтак и оптимальное решение двойственной задачи. Удобнее всего 1Г т переменных и одновременно оптимальны тогда и только тогда, ког; да а) для каждой дуги в кратчайшей цепи (которая соответствует ' положительному»» в прямой задаче) соответствующее неравенство 1 в (3.12) обращается в равенство и б) каждое строгое неравенство 1 в (3,!2) соответствует дуге, не входящей в кратчайшую цепь. Пример 3.4 (продолжение).
11а рис. 3.5 показан оптимальный ~ выбор переменных и, соответствующий кратчайшей цепи (з, Ь), з. (Ь, »). Заметим, что на самом деле иет значения и, соответствующего ""„вершине», поскольку уравнение для вершины» было опущено. 'гч Однако по условию дополняющей нежес» кости его можно легко по', лучить, вычитая стоимость последней дуги (Ь, г) в кратчайшем пути ' нз пз (как показано на рисунке) С» Гл. 8. ттвойотввнность считать, что мы начинаем с таблицы, в левой части которой стоит единичная матрица; обычно она соответствует искусственным переменным или переменным недостатка На рис.
3.5 показана исходная таблица при атом предположении, На выходе симплекс-алгоритма после получения оптимального решения мы имеем таблицу, в которой часть, лежащая ниже строки Рис. 3.6. Исходная таблица. Рис. 3.7. Заключительная таблица. стоимости, получается из той же части исходной таблицы умножением на В ', где  — множество столбцов исходной таблицы, соответствующих оптимальному бдр. Кроме того, как мы видели в доказательстве теоремы 3.1, строка стоимости при достижении оптимальности принимает внд с,=с,— л'А >О, (3А3) где л — оптимальное решение двойственной задачи. В столбцах 1, 2,..., и, где по предположению вначале стояла единичная матрица, Ат есть единичный вектор еь поэтому с=с — л, 1=1, ...,т. (3.14) Следовательно, из заключительной таблицы можно получить оптимальное решение двойственной задачи по формулам л = с — с „1' = 1... „т.
(3.15) Отметим также, что в заключительной таблице на месте исходной единичной матрицы стоит матрица В ', как показано на рис. 3.7. Это обстоятельство будет с большой выгодой использовано в следуюшей главе. Пример 3.5. В примере 2.8 в исходной таблице с =О в (наставшей) строке стоимостей г. Поэтому в заключительной таблице л,=- — сп откуда следует, что л,= — 5/2, л,=1, л,=-!, подтверждая пример 3.2. П Пример 3.6. В примере 3.4 (примере задачи о кратчайшем пути) мы не образовали вначале требуемую единичную матрицу. Если же мы хотим получить оптимальное решение двойственной задачи, то удобно начинать с такой матрицы в таблице.
Если бы мы посту- З.б. Двойственный симплекс-алгоритм пили таким образом, мы получили бы на месте этой матрицы в заключительной таблице значения, показанные на рис. 3.5 (см. задачу 4). С) 3.6 Двойственный симплекс-алгоритм Критерий оптимальности с)0 можно рассматривать как выражение допустимости двойственной переменной пг=свВ ', поскольку с' = с' — г' = с' — свВ 'А = с' — и'А. (ЗА 6) Таким образом, можно считать, что в симплекс-алгоритме мы поддерживаем допустимость прямого решения и стремимся к допустимости двойственного.
Такой алгоритм называется прямым алгоритмом. Точно ~ак же можно начать с допустимого двойственного решения и стремиться к допустимости прямого. Такой алгоритм называется двойсгпвенныл сииплекс-алгоритмом. Рассмозрим его более детально. Пусть у нас имеется таблица с базисным (но недопустимым) решением и допустимое двойственное решение (строка стоимости х, )0).
Выберем строку (пусть, например, строку г), соответствующую недопустимой компоненте прямой задачи х,„(0. Тогда в : строке г лежат возможные ведущие элементы. Рассмотрим только те элементы, для которых х„(0, поскольку мы хотим, чтобы при операции замещения г возрастало ( — г убывало). Это следует из того, что двойственное решение остается допустимым и, следова'. тельно, меньшим оптимальной стоимости (на самом деле мы решаем задачу максимизации). После замещения с ведущим элементом х„новые элементы в строке стоимости будут равны Хв~ = Хву — (Хвв/Хгв) Хгр й(ы хотим, чтобы эти элементы остались неотрицательными, с тем ', чтобы сохранилась допустимость двойственного решения.
Следовательно, для х„(0 должно быть х„!х, ~х„!х„Выбор ведущего столбца определяется, таким образом, условием п1ах(хег/х,у). нксг<О Отметим красивую симметрию по отношению к прямому сим,';-' плекс-алгоритму: в двойственном симплекс-алгоритме сначала вы' бирается строка, а затем находится столбец для введения в базис. Проверка отношений состоит в поиске максимума среди неотрицательных отношений элементов строки 0 и строки г вместо поиска минимума среди положительных отношений элементов столбца 0 и столбца э.
При отсутствии вырожденности мы движемся от (недопустимого 1 Г прямого) базисного решения к (иедопустимому прямому) базисному ; решению, увеличивая стоимость. В результате мы должны выйти из множества базисных решений и, следовательно, остановиться. При Га. 3. даоаотаеннооть 86 наличии вырожденности необходимо использовать какое-нибудь правило, такое, например, как правило Блэнда (см. задачу 2).
Пример 3.7. Вернегися к задаче о кратчайшем пути из примера 3,4. и выберем базис в исходной таблице, состоящий из столбцов 2, 3 и 4. Из рис. 3.3. легко видеть, что это недопустимое прямое решение, поскольку множесгво е„ е„ е, не содержит ориентированной цепи. Операция замещения, в результате которой получается этот базис, приводит к таблице Л Л Л Л Л Л= Л = Л= Он и шавляет точку, недопустимую в прямой и допустимую в двоиственной задачах, и можно применить двойгпвенный симплекс- алгоритм, в результате чего получаем ведущий элемент ха .
отмеченный в таблице. Следующая ~аблица имеет вид Л =- Л= Уа и оптимальна; дуга е, заменилась дугой г„что привело к оптимальной цепи (е„иа). (:) 3.7 Интерпретация двойственного симплекс-алгоритма ') Двойственный симплекс-алгоритм настолько симметричен по отношению к прямому симплекс-алгоритму, что читатель, естественно„может подозревать, что первый из них есть просто второй, примененный к двойственной задаче. Мы сейчас подтвердим это подозрение. На любом шаге прямого симплекс-алгоритма можно интерпретировать базисные переменные как переменные недостатка и Е Я" и ") Мы благодарим Ф. Садри аа гомопьь при работе над этим параграфом.
3.7. Интерпретации деойстееннога симплекс-алгоритма 37 (3.18) (3.20) Рнс. 3.3. Таблицы в стандартной форме, соог ветствуюнсне нрвмон задаче (3.17) н двойствен ной задаче 13.21). двойственной задач. В прямой задаче имеются базисные переменные и и внебазисные переменные х; в двойственной задаче — базисные переменные з и внебазисные переменные и. (Эти две задачи можно на самом деле представить в одной и той же таблице, опустив элементы единичных базисов.) Представим обе задачи (3.17) и (3.21) в нашем обычном стандартном виде и запишем их рядом, как показано на рис, 3.8. Можно по- записать прямую задачу в виде ппп с'х, Ах+и=6, (3.17) х, и)0.
Эта задача эквивалентна задаче шах — с'х, Ах<6, х)0, двойственная к которой имеет вид ш)п и'Ь, и'А ) — с', (3.19) и' ) О. Вводя переменные избытка з Е Рн, можно записать эту задачу в стандартной форме следующим образом: пип тс'6, и'А — з' = — с', и', 3') О, или как следующую задачу в стандартной форме ппп Ь'и, ( — А') и+ э=с, (3.21) и, з)0. У нас теперь две задачи в стандартной форме: (3.17) и (3.21), которые можно интерпретировать как пару, состоящую из прямой и Гл.
3. Двойственнвсень 88 :с с с С И О сй н з Е 3 с 8 с с с с с с Задачи казать теперь, что операция замещения из прямого симплекс-алгоритма, примененная к двойстгенной таблице, соответствует операции замещения из двойственного симплекс-алгоритма, примененной к прямой таблице. Рассмотрим операцию замещения прямого симплекс-алгоритма в двойственной таблице.
Вначале мы выбираем Ь„(0. Выбор ведущего элемента определяется условием с с. 1 ппп ~ 1 ~= — п1ах ~ 71, Л(-ау)>о(( — ам)! Пч <Е(а~2 что соответствует выбору ведущего элемента в двойственном симплекс-алгоритме. На рис. 3.9 показана типичная операция замещения в обеих таблицах, для сравнения расположенных рядом таблиц. Читатель может проверить, что операция замещения в двойственной таблице в точности соответствует такой же операции в прямой таблице при условии, что новый внебазисный столбец меняется местами с новым базисным столбцом в каждой таблице (см. задачу ! ).
Задачи 1. (Ф. Садри.) Проверьте, что операция замещения прямого симплекс.алга. ритма, примененная к двойственной таблице на рпс. 3,8, в точности соотвехствует операции замещения двойственного симплекс-алгоритма, примененной к соответствующей прямой таблице, где в каждой таблице новый внебазнсный столбец меняется местами с новым базисным столбцом. 2. (Ф. Садри.) Используя результат предыдущей задачи, разработайте правило устранения зацикливания для двойственного симплекс. алгоритма, аналогичное правилу Блзнда для прямого симплекс-алгоритма Покажите, что ваше правило работает.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
