Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 80
Текст из файла (страница 80)
(5) Если к этой матрице мы применяем шаги со второго ао четвертый стандартной процедуры, то либо будем иметь диагонализированную матрицу с Ьп, делящим Ьп, либо будем иметь элемент, меньший с и эанимающий положение (1,1). Таким обраэом, не более, чем черев 1одгЭ [тс + 4 (г + р)] операций, мы получим Ьп, которое делит НОРМЛИ1 НЛЯ ФОРМА СМИТА Пример. Пусть ь= 7 Ь= 0 Тогда мы имеем е,=е,+Зег е,'=ег | о — з) е", = е,' = ег ег= е| = ег+ Зег Ь;=Ь,+ЗЬ, (2 1о) е,' = е", + 2е", = 2е, + 7ег е,"' = е,' = е, + Зег (о оо| Ь;=е,'", Ь; = 10е,"'.
ПРИЛОЖЕНИЕ В АЛЬТЕРНАТИВНОЕ ДОКАЗАТЕЛЬСТВО ДВОЙСТВЕННОСТИ Доказательство теоремы двойственности в гл. 3 основано на теореме 1.2. или на ее эквивалентной форме — теореме об отделяющей гкперплоскости. Докааательство теоремы 1.2. чисто алгебраическое и весьма длинное. Если нас интересует только теорема двойственности сама по себе, мы лложем воспользоваться следующим доказательством, которое не связано с теоремой 1.2. (Это доказательство изложено в работе Дрейфуса (50).) Рассмотрим прямую и двойственную задачи линейного программирования: минимизировать г=сх при ограничениях Ах)Ь, х)0 и максимизировать лл= уЬ при ограничениях уА<с, у>0.
(2) Легко видеть, что любая пара допустимых решений х и у задач (1) и (2) будет удовлетворять соотношениям г = сх ) (уА) х = у (Ах) ) уЬ = ш. (3) Покаялем теперь, что для оптимальных решений хе и уе г'" =- ох* = у"Ахе = уеЬ = — ше. (4) Рассмотрим целевую фупкцило г задачи (1), как функцию правой части Ъ ограничений (1), а для обоаначенкя оптимального значения целевой функции, когда правая часть равна Ь, используем г* (Ъ). Тогда по определению г* (Ь) = сх~. Если увеличить любую компоненту Ь, вектора Ь задачи (1), то онтимальиое значение г* (Ь) заведомо не уменьшится.
Отсюда Л:!ЬТКГНАТИВНОЕ ДОКАЗАТЕЛЬСТВО ДВОИСТВКННОСТП 45T следует, что дь )О для всех ! (О) дЬ, Предположим, что !юс ограничение задачи (1) выполняется как строгое неравенство для оптимального решения х*, т. е и а!!!Зх! ) Ьы ' 41 Тогда найдется такое з, что при увеличепии Ь;, на е, Ьсе неравенство будет все еще выполняться, а оптимальное зяачепие га (Ъ) не иаменится. Отсюда следует, что п — =0 для ~~, а!Вх,г) ЬО (7) Ф-а Рассмотрим следующую аадачу линейного программирования„ которая несколько отличается от задачи (1): минимизировать з = сх при ограничениях А(х*+ ее,) = Ахи+ еа1~ )Ъ+ сан Поскольку' х* + зез — допустимое решение задачи (8), с (хи + зез) должно быть нс меньше оптимального аначения целевой функции задачи (8). Другими словами, зи (Ь + за,) ( с (хи — , 'зе;) = охи + есе; = за (Ъ) + зсн Выражая обе части неравенства через з, получаем (предполагая хи =- В 'Ь)0) з" (Ь)-) з ~ дь а!1~~а" (Ъ) — , 'зсы 1=! Коли з ) О, то из соотношения (9) следует (9) дс" — а!1(ся дЬ! (10Ь Ах>Ь+за;, х>0.
(8) Можно получить допустимое решение задачи (8), незначительно изменив оптимальное решение задачи (1), т. е. можно. использовать х* + еа; как допустимое решение задачи (8). Этот факт легко проверяется: пгиложение В Если х,*) О, то можно выбрать з ( 0 таким, чтобы хт+ з' .О, т. е. чтобы х* — ', зе; оставалось допустимым ре1пением задачи (8). ,Для з(0 из соотношения (9) следует дс* — ап>,", (11) .из утверя1дений (10) и (11) вытекает, что — ам=с!, есЛИ Х! ~0. дь! дзч а 1=1 (12) Обозначим дз*!дЬ! через у7 н покажем, что у" — оптимальное решение задачи (2) и что соотношение (4) выполнено. Из соотношений (6) и (10) видно, что у,' пеотрицательно и удовлетворяет ограничениям задачи (2).
Далее заметим, что имеет место следующее соотношение: с!ха=(2 у,*а!1) Х~т, 1=1, . ° ., п. (13) 1=1 Действительпо, если х,'=О, то утвер1кдение (13) очеви;!по. Если же х,") О, то в силу (12) имеем с;=","„у;'ась откуда и следует 1=1 а13). Из (13) получаем сх" = ~~', ( ~~~! у,'а11) хт = ~ (у"а1) хт = у'Ах* (14) ут(~~Р~ а!1Хт) =у,*.Ьо 1 (15) Действительно, в силу (1) всегда Д, аых; ~Ь! при)'=1, ..., и,.
1=1 и Если ~ а!1х!т = Ь;, то равенство (15) очевидно выполняется. Если же ~, аых,") Ь;, то в силу !=1 (7) имеем ут =' — = 0 дг дь! и первая часть равенства (4) доказана. Чтобы доказать вторую часть равенства (4), ааметим, что справедливо следующее соотно- зпение: альтвгн4тивнов докАЗАтнльство двоиствкппости 459 и утверждение (15) справедливо. Из (15) легко получаем П3 а тл у"Ах*= Х уа (~', агах;*) = ~", у,'Ь;=уаЬ. ь:.1 т=1 ~=4 (16) Из соотношений (14) и (16) следует соотношение (4) и теорема двойственности доказана.
Всюду в доказательстве мы предполагали, что функция з* (Ь) дифферепцируема. При доказательстве соотношения (9) предполагалось, что х* = В ~Ь ) 0 и, следовательно, зе (Ъ + за;)— линейная функция от Ь + сап в противном случае она содержала бы члены более высокого порядка относительно е. ПРИЛОЖЕНИЕ С АЛГОРИТМЫ ТИПА ДЕРЕВА ПОИСКА Целочисленные алгоритмы, описанные в гл.
13 — 17, относятся к методу отсечений, поскольку они порождают дополнительные ограничения или отсекающие плоскости. В этом приложении мы обсудим другой подход, который может быть пазвап методом дерева поиска. Сюда относятся алгоритм ветвей и границ (Лэнд и Дойг П39), Литгл и др. [144)), аддитивный алгоритм (Балаш [4), Бил и Смол [14)), алгоритм прямого поиска (Лемке и П[пильберг [143)) и многие другие. Обзор этих методов и дополнительные ссылки можно найти в работе Балинского [6) и Лемке и Шпиль- берга [143).
Алгоритмы типа дерева поиска обладают следующими общими свойствами: (а) оии просты для понимания, (б) они легко могут быть запрограммированы на вычислительной машине, (в) верхняя граница числа шагов, необходимых в алгоритме. имеет порядок 0(й"), где п — число переменных, (г) они обладают простой математической структурой. Свойства (а) и (б) выража1от, несомненно, большие преимущества алгоритмов этого типа. Свойство (в) является недостатком, поскольку влечет за собой зкснонеициальный рост количества вычислений при увеличении размерности задачи.
(Здесь необходимо подчеркнуть, что верхней границы числа шагов в алгоритмах метода отсечения не установлено.) Мы останавливались подробно на алгоритмах метода отсечений, поскольку они дают лучшее попимание аадачи (см. гл. 18, 19, 20). Зная структуру задачи, можно надеяться построить более аффективные алгоритмы. Из опыта известно, что для небольших задач алгоритмы типа дерева поиска требуют меньше вычислительного времени, чем алгоритмы метода отсечений, но время вычислений растет быстрее в алгоритмах типа дерева поиска.
Здесь мы дадим краткое описание алгоритмов типа дерева поиска. Рассмотрим задачу целочисленного программирования минимизировать з = су при ограничениях Ау ) Ь, у ) )О, у — целочисленный вектор. ллгогитмы типА днРЕВА поиска 461 Если каждая компонента вектора у ограничена сверху целым числом М, то существует (М + [)" таких неотрицательных целочисленных векторов у. Мы должны проверить каждый из них на допустимость и выбрать допустимое решоние с минимальным значением целевой функции в качестве оптимального решения.
Поскольку число (М + й)" обычно очень велнно, в алгоритмах типа дерева поиска делается попытка исключить проверку вариантов, которые доминируются проверенными ранее регпепиями. Опишем сначала метод ветвей и границ. Решим задачу (1) кан задачу линейного программирования, отбросив требование целочисленпости, Если в оптимальном решении все перемепные у, ) О и целочислепны, то очевидно, что у — оптимальное решение задачи целочисленного программирования. Если некоторая компонента у„ = [уа1 + 1ю где О ( ~а ( 1, то реп(аем две задачи линейного программирования, одну с дополнительным ограничением уд = [уа1, а другу(о с дополнительным ограничением ув —— = [уз[ + 1.
Если одна из этих двух задач линейного программирования, скажем, с ограничением уа = [уа1, не дает целочисленного решения (например, у( = Д(1 + ~(), то необходимо рен(ить еще дзе задачи линейного программирования, одну — с дополнительными ограничениями уд = [уа), у( =- [у(1, другую с дополнительными ограничениями уь = [уз[, у( =- [у(1 + (. Все полученные таким образом решения могут быть частично упорядочепы в виде дерева, корень которого соответствует решению аадачи линейного программирования, полученному без целочисленных ограничений. Если решение у' не удовлетворяет требованиям целочисленности, оно разветвляется на два других решения у' и уз.
Решение у' называется прада(ествующим решениям у( и у', а у' и уа называются следующими за уа. Если все решения, следующие за у( и уз, недопустимы, то мы должны ветвиться из уа снова с ограничениями у, = [у(1 — 1 н у, = [у(1+ 2. Л(обая вершина с нецелочисленпым у( может иметь много следующих вершин, соответству(ощих у, = [у(1, у(=-[у(1 — 1,..., у(=[у(1+1, у,=[у,[+2... и т. д.
Вершина нааывается висячей, если не имеет следующих за пей вер(пин; нз этого определения следует, что висячая вершина представляет собой допустимое целочисленное решение или недопустимое целочисленное решение. Идея метода ветвей и границ заключена в следующих двух фантах. 1. Поскольку предшеству(ощее реп(епие удовлетворяет меньшему числу ограничений, чем последующие, а дополнвтельпые ограничения не могут улуч(пить значения целевой функции, оптимальное значение целевой функции для последующих решений всегда больше либо равно оптимальному аначепию для предшествующего решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
