Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

ПРИЛОЖЕНИЕ В

АЛЬТЕРНАТИВНОЕ ДОКАЗАТЕЛЬСТВО ДВОЙСТВЕННОСТИ

Доказательство теоремы двойственности в гл. 3 основано на теореме 1.2. или на ее эквивалентной форме — теореме об отде­ ляющей гиперплоскости. Доказательство теоремы 1.2. чисто алгебраическое и весьма длинное. Если нас интересует только теорема двойственности сама по себе, мы можем воспользоваться следующим доказательством, которое не связано с теоремой 1.2. (Это доказательство изложено в работе Дрейфуса [50].)

Рассмотрим прямую и двойственную задачи линейного про­

Рассмотрим целевую функцию z задачи (1), как функцию правой части Ь ограничений (1), а для обозначения оптимального значения целевой функции, когда правая часть равна Ь, исполь­ зуем z* (Ь). Тогда по определению

Если увеличить любую компоненту bt вектора Ь задачи (1), то оптимальное значение z* (b) заведомо не уменьшится. Отсюда

Можно получить допустимое решение задачи (8), незначи­ тельно изменив оптимальное решение задачи (1), т. е. можно использовать х* + еа; как допустимое решение задачи (8). Этот факт легко проверяется:

А (х* + ее;-) = Ах* + еа,- ^ Ь + еа;.

Поскольку, х* + ее; — допустимое решение задачи (8),.

т

(Ю>

г=1

Из соотношений (14) и (16) следует соотношение (4) и теорема двойственности доказана.

ПРИЛОЖЕНИЕ С

АЛГОРИТМЫ ТИПА ДЕРЕВА ПОИСКА

Целочисленные алгоритмы, описанные в гл. 13—17, относятся к методу отсечений, поскольку они порождают дополнительные ограничения или отсекающие плоскости. В этом приложении мы обсудим другой подход, который может быть назван методом дерева поиска. Сюда относятся алгоритм ветвей и границ (Лэнд и Дойг [139], Литтл и др. [144]), аддитивный алгоритм (Балаш [4], Бил и Смол [14]), алгоритм прямого поиска (Лемке и Шпильберг [143]) и многие другие. Обзор этих методов и дополнительные ссылки можно найти в работе Балинского [6] и Лемке и Шпильберга [143]. Алгоритмы типа дерева поиска обладают следующими общими свойствами:

(а) они просты для понимания, (б) они легко могут быть запрограммированы на вычислитель­

ной машине, (в) верхняя граница числа шагов, необходимых в алгоритме,

ства алгоритмов этого типа. Свойство (в) является недостатком, поскольку влечет за собой экспоненциальный рост количества вычислений при увеличении размерности задачи. (Здесь необхо­ димо подчеркнуть, что верхней границы числа шагов в алгорит­ мах метода отсечения не установлено.) Мы останавливались по­ дробно на алгоритмах метода отсечений, поскольку они дают луч­ шее понимание задачи (см. гл. 18, 19, 20). Зная структуру задачи, можно надеяться построить более эффективные алгоритмы. Из опыта известно, что для небольших задач алгоритмы типа дере­ ва поиска требуют меньше вычислительного времени, чем алго­ ритмы метода отсечений, но время вычислений растет быстрее в алгоритмах типа дерева поиска. Здесь мы дадим краткое описа­ ние алгоритмов типа дерева поиска.

Если каждая компонента вектора у ограничена сверху целым числом М, то существует (М + 1)” таких неотрицательных цело­ численных векторов у. Мы должны проверить каждый из них на допустимость и выбрать допустимое решение с минимальным значением целевой функции в качестве оптимального решения. Поскольку число (М + 1)" обычно очень велико, в алгоритмах типа дерева поиска делается попытка исключить проверку вариантов, которые доминируются проверенными ранее реше­ ниями.

Опишем сначала метод ветвей и границ. Решим задачу (1) как задачу линейного программирования, отбросив требование цело­ численное™. Если в оптимальном решении все переменные уj ^ О и целочисленны, то очевидно, что у — оптимальное решение задачи целочисленного программирования. Если некоторая ком­ понента y h = lyk] -f- fh, где 0 < / ft < 1, то решаем две задачи линейного программирования, одну с дополнительным ограниче­

ленного решения (например, у г = [/г] -f- / г), то необходимо решить еще две задачи линейного программирования, одну — с дополни­ тельными ограничениями yh = [у*], у г = [г/г], другую с допол­ нительными ограничениями ук = [уд], у* = [уг] + 1.

Все полученные таким образом решения могут быть частично упорядочены в виде дерева, корень которого соответствует реше­ нию задачи линейного программирования, полученному без цело­ численных ограничений. Если решение у0 не удовлетворяет тре­ бованиям целочисленное™, оно разветвляется на два других решения у1 и у2. Решение у0 называется предшествующим реше­ ниям у1 и у2, а у1 и у2 называются следующими за у°.

Если все решения, следующие за у1 и у2, недопустимы, то мы

Вершина называется висячей, если не имеет следующих за ней вершин; из этого определения следует, что висячая вершина представляет собой допустимое целочисленное решение или недо­ пустимое целочисленное решение. Идея метода ветвей и границ заключена в следующих двух фактах.

1. Поскольку предшествующее решение удовлетворяет мень­ шему числу ограничений, чем последующие, а дополнительные ограничения не могут улучшить значения целевой функции, оптимальное значение целевой функции для последующих реше­ ний всегда больше либо равно оптимальному значению для пред­ шествующего решения.