Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 61

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 61)

На рис. 17 1 ато отсечение обозначено через с,. 17.1. введение и ллгогитм 347 Выберем столбец под г1 в качестве ведущегж Производящей строкой является строка хм Получим отсечение и проведем преобразование. Результат записан в табл. 17.4. Как обычно, после того как преобразование таблицы произведено, ведущая строка Р в с. 17.1. вычеркивается из таблицы. На рис. 17.1 соответствующее отсечение о~означено через с,. После преобразования с ведущим элементом, указанным в табл.

17.4, получим оптимальну1о табл. 17.5. Соответствующее отсечение обозначено на рис. 17.1 через см Оптимальным решением является х, = 1, хз = 1, хе = 4. К сожалению, описанная процедура не обеспечивает конечности алгоритма. Для доказательства конечности мы должны ввести в алгоритм дополнительные условия. Основная трудность при доказательстве конечности связана с тем, что отсечение (2) может иметь нулевое значение в столбце констант, т. е. Так случилось на второй и третьей итерации в описанном выше примере. Коли в отсечении в столбце констант появляется нуль, то преобразование таблицы, в котором отсечение служит ведущей строкой, не приводит к изменению столбца констант ае.

Поэтому гл. 17, пРямон алгогитм хо Х1 Х2 Хз Производящая хз строка — Производящая строка .+- Отсечение Гомори л- Отсечение !'онори ' 51 Х1 Х2 .+- Проиаводнщая хз строка Хз л- Производящая строка л- Отсечение Гомори л- Отсечение Гоморн зз Таблица 17.б 1 — 52 — 51 аначения всех базисных переменных не изменяются и, в частности, не изменяется значение целевой функции. Это явление напоминает вырожденность в задачах 'линейного программирования.

Как и в случае симплекс-метода, доказательство конечности должно установить, что вырожденность можно Х1 Х2 хз Хз х1 Х2 хз хз Таблица 17.1 1 — х1 — 52 Таблица 17лт — 51 — 52 Х1 Хз хз Хз Таб ца 1 — 51 — хз Таблица 17.4 1 52 52 17.1. ВВЕДЕНИЕ И АЛГОРИТМ 349 преодолеть не более чем за конечное число преобразований.

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

Проблема конечности в прямых алгоритмах станет понятней, если ввести различие между с7пационарными циклами (выроягденпыми преобразованиями, о которых говорилось выше, т. е. при аор/аез = — 0) и переходными циклами (преобразованиями, которые приводят к новому решению с положительным приращением целевой функции, т. е. при а„/а„в1). Поскольку в прямом алгоритме рассматриваются полностью целочисленные таблицы, в переходном цикле ао, < — 1 и а„о/а„е ' . 1. Поэтому переходный цикл приведет к увеличению значения целевой функции по крайней мере па единицу. Очевидно тогда, что достаточно конечного числа переходнь)х циклов для получения оптимального решения совместной задачи с ограниченной целевой функцией.

Основная проблема конечности сводится к доказательству того факта, что любая последовательность стационарных циклов конечна '). Достаточно внести три изменения в описанпуго выше процедуру, чтобы получить конечный алгоритм. Во-первых, в начальную таблицу нужно добавить новую строку. Во-вторых, ведущий, столбец а, должен выбираться не только исходя из требования а„, с О, но и в соответствии с некоторыми новыми правилами.

)1 в-третьих, строка, используемая в качестве производящей для получения отсечения Гомори не всегда является ведущей строкой симплекс-алгоритма; вместо того чтобы определять производящую строку по правилу проверки отношения, она будет выбираться из множества подходящих строк согласно другому правилу, которое входит в класс правил, гарантирующих конечность.

Новое уравнение, добавляемое к исходной таблице, нам уяге з) Чтобы получить короткое и ве слишком громоздкое яредставаеяяе о прямом алгоритме в доказательстве его конечности, мы обычно во будем делать различия между стационарными И переходными циклами. (Впервые Гловер продвожвл алгоритм, в котором в явяом виде во было этого различая, см. [76).) Однако можво привести изложение алгоритма и доказательство его конечности с учетом этого различая. (См. Бзя-Изрзоз и Чарное [17) я Юяг [224), [225)) Прв вычислениях, возможно, стоит учвтывать указаиыоо разлвчяе. Глг !7.

ПРЯМОЙ АЛГОРИТМ знакомо: это ограничение, выражающее границу суммы небазисных (исходных) переменных. Обозначим индекс этой строки, через Ь. Ограничение имеет вид (ъ+ д' к.7=ало. (3) гзт Целочисленная копстанта аьо выбирается достаточно больпюй„ для того чтобы любое допустимое целочисленное решение удовлетворяло уравнению (3) при неотрицательном целочисленном значении слабой переменной уь. Хорошо известно, что добавление строки (3) позволяет получить допустимое решение двойственной задачи. Мы пе будем подчеркивать здесь это свойство Ь-строки, однако оно играет важную роль в прямом алгоритме 7). Цель введения Ь-строки заключается в том, чтобы помочь в выборе ведущего столбца.

Пусть аь) обозначает элемент в )-и столбце и в Л-й строке. Для каждого столбца а. определим новый т 1 вектор-столбец ) г) следующим образом: Правило выбора ведущего столбца состоит в следующем: столбец а, выбирается в качестве ведущего, если г, явчяется лексикографически минимальным среди столбцов гм у которых аь;) О. Сформулировать кратко критерий выбора производящей строки не удается.

Поэтому сначала будет сформулировано основное требование к производящей строке, а затем обсуждено значение такого подхода. Потребуем, чтобы правило выбора производящей .строки обладало следующей особенностью: строка а может быть взята в качестве производящей, если выбрав ее в качестве таковой, мы для каждой строки 1 эа конечное число симплексных итераций получим таблицу, в которой ам ~ ~а~с. (бу Такое требование не означает, что условие ам ( аш должно выполняться для всех 1 в пекоторой таблице (что. является необходимым и достаточным условием переходного цикла). Наше требование допускает возможность того, что аы ) аш для всех й в некоторой таблице. г) См.

Юнг [224) и [22Б) и Гловер [76), а также й 17.4. з) В определении (4) мы предполагаем, что вектор-столбец аг иа (1) содержит о7-)- 1 компонент. Вектор г будет использоваться для таблиц, которые расширены введением в систему (1) Ь-строки и тождественных соотношений для ~ебазисяых переменвых. Предполагается, что г; содержит компоненты, соответствующие всем строкам расширенной таблицы. Единственным ограничением па такое расширение является то, что нулевая строка таблицы всегда соответствует целевой функции. «тл.

Введкиие и лт«гогитм 351 Любое правило выбора производящей строки, обладающее свойством (5), будем называть допустимым правилом. Выполнения свойства (5) достаточно !) для доказательства конечности. Однако само по себе свойство (5) еще не обеспечивает конструктивного способа получения допустимых правил выбора производящей строки. С помощью теоремы 17.1, изложенной ниже, и некоторых дополнительных рассуждений будет получен такой способ, позволяющий сформулировать допустимые правила. Поскольку выбор производящей строки является задачей нетривиальной, по-внднмому, должно существовать несколько строк, которые могут служить в качестве производящих.

В предварительных рассуждениях и в примере начала атой главы в качестве производящей использовалась ведущая строка симплекс-алгоритма. Эта строка всегда дает отсечение, которое является ведущей строкой с ведущим злемептом, равным единице. По-видимому, в таблице существуют и другие строки, из которых могут быть получены отсечения с такимн же свойствами. Допустим„что отсечение получается по форму«(е з) Строка и может стать производящей тогда и только тогда, когда О~~ — "' ~-=Е., (7) где О, определяется из условия О« = пт1п — . а;о а. >о ы Определим множество у (з) как совокупность строке), удовлетво- ряющих условию (7). ') Свойство (5) пе самое слабое ограничение, которое можно использовать для получения допустимых правил выбора производящей строки. Однако более слабые ограничения, по-видимому, потребуют более сложных построений, и позтому мы используем свойство (5), которою просто формулируется и является достаточным условием конечности.

Другие формулировки можно найти у Глезера (76! и Юнга (225!. з) Полагая й = а«ю как зто делается в (6),,мы получаем в качестве ведущего заеме«па 1. В отдельных случаях можно взять Х ( ае«н прн этом ае, — ~ = — 1 (что сохраняет ведущий элемент, равный 1) н получить более силь- Х нос («глубокосз) отсечение. Эта идея была предложена Вильсоном [214!. Мы ве будем елось пользоваться этими соображениями, поскольку ови приводят к более сложным правилам выбора производящей строки и потому усложняют изложение в целом. Однако тем, кто интересуется вычислительными аспектами, следует номннть о такой возможности. з) Иногда автор говорит не о строках из у (е), а о номерах этих строк.— Прим.

ред. ГЛ. Ги ПРЯМОЙ АЛГОРИТМ 352 Теперь рассмотрим, как можно получить правила выбора строки и Е У(з), обладающей свойством (5). Заметим, что в переходном цикле О, )~ 1. Поэтому а,а ) а,е для всех 1 и, следовательно, свойство (5) имеет место независимо от того, какую строну выбрать в качестве производящей.

Характеристики

Список файлов книги