Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 19
Текст из файла (страница 19)
Необходимо сделать ряд замечаний. 1. Если рассматривать кая;дую вз подтаблвц как прямо или двойственно допустимую симплексную таблицу, то, согласно предписаниям прямого или двойственного симплекс-метода, в каждой из них можно указать единственный ведущий элемент. Отсюда следует, что для любой последовательности таблиц существует последовательность ведущих элементов.
«Л. ВЗАИМНЫЙ МЕТОД РЕШЕНИЯ 2. Поскольку в качестве характеристической строки прямо допустимой подтаблицы можно выбрать любую строку с положительным левым элементом, последовательность таблиц определяется для данной исходной таблицы отпгодь не однозначно. 3. Так как каждая Т» зодер>кит либо мопьше столбцов, либо меньше строк, чем Та ю то последовательность подтаблнц всегда конечна. 4. На рнс. 6. ( и в табл. 6.
»О строка и столбцы были переставлены только для наглядности. Для того чтобы последовательность таблиц определилась однозначно, необходимо лишь указать характеристический элемент каждой из таблиц. 5. Для каждой прямо допустимой таблицы ТА с положительным характеристическим элементом используется прямой симплекс-метод. Правило выбора ведущего элемента сохранит С' (Та) неположительным. (Здесь знак * используется для обозначепия таблицы после итерации.) С другой стороны, с) (ТА) - с) (Та).
(Если С' (Т») не содорнгит пулей, то с) (Т») ) Н (Та).) Если г) (Тй) - О, то характеристический столбец таблицы Т„' г содержит на один неположительный элемент больше, чем характеристический столбец Т»,. В розультате итерации таблица Та, «приближается» к виду прямо допустимой таблицы.
6. Подобным же образом дчя двойственно допустимой таблицы Та с отрицательным характеристическим элементом мы используем двойственный симплекс-метод. Правило выбора ведущего элемента сохранит Л (ТА) неотрицательной. С другой стороны, д (ТА) < Ы (Т»). (Если В' (Т») » )0 не содержит нулей, то г((Т») < Н(Т»).) Если с((Т«) ~ О, то характеристическая строка таблицы Та «содержит на один неотрицательный элемент больше, чем характеристическая строка таблицы ТА о В результате итерации таблица Т» ««приблигкается» к виду двойственно допустимой таблицы.
Таким образом, вместе с любой таблицей и последовательностью ее подтаблиц возникает как бы иерархия «задач», где !с-я «задача» служит для «улучшония» й-й подтаблицы. «Улучшение» подтаблицы ТА по изменит «задач», связапных с предыдущими подтаблицами ввиду предложенного способа построения последовательности Т«, Т„..., Тд, „Та т). Далее через а (Т») будем обозначать число строк в таблице Тю если )с нечетно, и число столбцов в Т», если я четко. т] Преобразование подтабзнц (рассмотрение соответствующих задач иерархии) совер|нается не автономно, а одновременно. Процесс решения задачи таков: а) по исходной таблице Т, строится (как укааано в тексте) конечная цепочка прямо (двойственно) донустнммх подтаблиц Т,, ..., Т„ и нх водуптих элементов и;; б) вся таблица Т, подвергается снмплексному преобразованию с ведущим элементом а„(из последней подтаблицы); в) если полученная после преобразования таблйца Т~е не оптимальна, то, беря ее аа исходную, повторяем процесс с и, а)).— Прим.
ред. 8« Тд, (ю" 91 Т Таблица 6.16 (Тд)) (Т„) Таблица 6.11 а (Тд,) ) а (Тд с) ини сс (Т„',) = .= (Т,,); )(Т„,)) (Тд,) Тд (й нечетное) О,...,О +...+ Таблица 6,16 а(тб)<6(тд) сс а(тдл)> (Т„) Таблица 6.12 а(Тф)) а(Тд) Таблица 6.14 а(Т,*, с))сс(7'д д) ини а(Тд д)= — — (Тд- ): 6 (Т ' ) < 6 (7'и- ) Тд (и четное) Табло ца 6.
16 6(Тд)) 6(Тд) и сс(Т„') >а(Тд) 6.2. ПРЯМО-ДВОЙСТВЕННЫЙ МЕТОД Таблицы 6.11 — 6.16 иллюстрируют гпесть возможных случаев выбора ведущего элемента и иаменення в результате итерации. Воаможпые исходы итераций могут быть использованы для доказательства конечности алгоритма. 6.2. Прямо-двойственный метод') (Данциг, Форд и Фалкерсон (40)) Поскольку существуют прямой и двойственный сипплексметоды, не удивительно, что существуют методы, использующие идеи как прямого, так и двойственного алгоритмов.
Метод, излагаемый в настоящем параграфе, формально является двойственным, поскольку он сохраняет двойственную допустимость решений. Прямой симплекс-алгоритм испольауется как подалгоритм для уменьшония невнэок 2). Когда решение становится одновременно примо и двойственно допустимым, оно оптимально. Пусть прямая задача имеет вид: минимизировать х= сх при условиях Ах=Ь)0, х)0. Тогда двойственная к задаче (1) формулируется так: максимизировать тт= пЬ при условиях яА<с, я~~О. (2) Допустимое решение задачи (2) получается посредством весьма несложного се анализа.
Если с )~ О, то и = 0 — допустимое решение аадачи (2). Если условие с) ) О выполняется но для всех у и допустимое решенно задачи (2) не очевидно, то задачи (1) и (2) можно слегка измонить следующим образом. Введем новую неотрицательную переменную хи+2 и добавим к ограничениям задачи (1) уравнение х2+хз+ха+ ° ° ° +х +хи+2 =Ь +2 (х+2~~0) гДе Ьтп ° 2 — Достаточно большое положительное число, ОчевиДно, такое ограничение пе изменит оптимального решения прямой задачи.
Двойственная задача при этом будет иметь следующий вид: найти максимум ш' = Я2Ь6 +... + ЯтЬш + Яш+,Ь т1 2) й вашей литературе зтот метод носит название метода последовательного сокращеявя вевязок.— Прим. перев. ') невязяой называется величина )~ а;~л — ь; (2 =- 1,..., т) првфвк- свроеаявых хп — Прим. перла. 118 Гл. 6. Метод Одновве«менного Решения при условиях ла,«+...+л а,+л ь,<с„ л«ам ' ~ ° ° ° + лтатя+ лт+1~(са Лт+1(О. Теперь легко выписать допустимое решение двойственной задачи лть« = ш1п с« н л« = О (1 = 1~ .
ш) Для дальнейшего обсуждения предположим, что нам известно решение л двойственной задачи (2). По следствию из теоремы о дополняющей не«лестности оба решения х и л являются оптимальными решениями соответственно задач (1) и (2) тогда и только тогда, когда опи удовлетворяют условиям (с« — ~„л«а«1) х«=О (для всех у), (За) л;(~а;;х; — Ь;)= — О (для всех 1). (Зб) Если х — допустимое решение задачи (1), то условие (Зб) автоматически выполняется, поскольку ограничении задачи (1) представляют собой уравнения.
Пусть л — текущее допустимое решение задачи (2). Тогда часть ограничений этой задачи выполняется как равенства, а остальные — как неравенства. (Заметим, что л — допустимое решение, по не обязательно базисное, т. е. м может обращать в неравенства все ограничения задачи(2).) Для тех ограничений, которые удовлетворяются как равенства, условие (с« — ла«) х; = О выполняется при любых положительных значениях соответствующих переменных ххь Если «ке ограничение выполняется как неравенство, т. е. с; — ла«) О, то для выполнения условия (с« — ла;) х« = — О необходимо приравнять соответствующу«о переиенну«о х« нулю. Как найти х, удовлетворя«ощее условию (За) и ограничениям задачи (1)? Исходя из допустимого решения л задачи (2), определим мнонгество индексов Х =(у ) с; — лаэ = О). Для у с Х любое х« удовлетворяет условию (За). Для «' е 1«« ' Х выполняется с« — ла« О, поэтому условие (За) выполнитсн только при х« = О.
Таким образом, если выразить вектор Ь через неотрицательную линейную комбинацию столбцов а, («Е У), то коэффициенты х« ~ )О (г Е У) вместе с х; (у Е 11' ', У) составят оптимальное решение задачи (1), поскольку онн удовлетворя«от условиям дополняющей нежесткости (3).
Для нахождения неотрицательной линейной комбинации столбцов а« («е У) поставим следующую задачу, называемую вспомогательной задачей: злх прямо-двоиствкнныи мктод минимизировать ;) 1=с при условиях ~„амх~-хх; =-Ь| () ~Х; (=1, ..., т), х;>О, х';)О, (4) где х,' — искусственные переменные.
Если в оптимальном решении задачи (4) 5=0, то х,'=Он х,()ОХ), удовлетворяющие условиям задачи (4), являтотся искомой линейной комбинацией. Эти х~ (у к Х) вместе с х; = 0 (т' с Л" ', Х) представляют собой допустимое и оптимальное ') решение вадачи (1). Это решение допустимо, потому что ограничения задачи (4) при х, = 0 совпадают с ограничениями задачи (1), из которых вычеркнуты столбцы а; (1 с Л', Х). (Вычеркивание столбца ае эквивалентно условию хт = 0.) Если в оптимальном решении (4) $ ) О, то рассмотрим два случая. Обозначим оптимальное решение задачи, двойственной к (4), через я, Случай 1.
лат<0 для всех )~Л'',Х. Как будет показано, в этом случае задача (1) ке имеет допустимого решения. Чтобы показать зто, рассмотрим ограничения задачи, двойственной к (4): () 6Х) ((=1, ..., т). пад<0 я1<1 и'аз =-(и+Оп) а,=па)+Ока~ <с; , 'Опау(с,. (поскольку яа) <0). а т) Очевидно, з~ есть козявка, характеризующая стевояь невыполнения условия (1), а $ — сумма вевязок. При $ = О вектор х есть решение задачи (1).— Прим, ред.
') Овтимальвое, так как ври этом решении выволвяются условия (За).— Прим. ред. Если ж — оптимальное решение двойствоппой задачи, то гса; < 0 (1ЕХ). Из этого условия и предположения о том, что пах<0 для )ЕУ", Х, следует, что тса,<0 для всех у ЕУ. Пусть и — допустимое решение задачи (2). Тогда покажем, что ж' = я -х Ож (при любом О 0) будет допустимым решением задачи (2). Действительно, 120 ГЛ. 6. МЕТОД ОДНОВРЕМЕННОГО РЕШЕННЯ Далее, значение целевой функции может быть сделано как угодно большим, поскольку НЬ=э»О и и'Ь=(я+Оп)Ь=НЬ+ОлЬ, а 0»«он«но придать любое положитсльпое значопис.
Отсюда в силу теорсмы двойственности задача (1) не имеет допустимых решений. Случай 2. мат>0 по крайной мере для одного 1~Я',У. В этом случае мы увидим, что я'=я+Оп является допустимым решением задачи (2) для значений О, удовлотворяюпдих условию О<0<Оп Заметим, что по определению «множества индексов Х ма;<с, (для всех )ЕУ',Х). Пусть О,=ш«в'( '«:" 11 ) (у ЕЖ",э', яа«>0). (5) яа, Тогда»т'=я+Оп является допустимым решением при 0<0 <Оп поскольку я'а)=-яаэ — ', Ояат<яат+0«паз<науч-с) — яа;<с«(дчя яау>0), я'а) = ла, — ,'— Онат < яа1 < ст (для яа; < 0), Кроме того, я' «лучшс» исходного решения ан л'Ь = яЬ + ОНЬ > лЬ (так как яЬ = $ > О, О > О).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
