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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 230

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

13.4. СВОЙСТВА ДОПОЛНИТЕЛЬНЫХ НЕРАВЕНСТВ

299

На основании приведенных рассуждений можно сделать сле­ дующий вывод: если все коэффициенты в исходной таблице неотри­ цательные целые, то коэффициенты отсечений Гомори, выражен­ ных через исходные небазисные переменные, есть также неотри­ цательные целые числа.

Пусть получено оптимальное решение линейной программы и tj — небазисные переменные для текущего базиса. Из условия двойственной допустимости следует, что в уравнении

х 0 = «00 “Г 2 « о j ( t j )

коэффициенты a0j ^ 0. Кроме того, tj ^ 0. Если рассмотреть -пространство, как показано на рис. 13.3, то целевая функция является опорной гиперплоскостью положительного ортанта, достигающей максимума в начале координат (tj = 0). Любая точка внутри положительного ортанта соответствует положи­

тельным значениям tj, а значит, уменьшает значение х0. Гиперплоскость

« = — /о + 2 М - = ° .

при tj ^ 0 является гиперплоскостью, рассекающей положи­

тельный ортант на две части, одной из которых принадлежит начало координат. Эта гиперплоскость параллельна гиперплоско­

сти s' = 2 f}tu которая является опорной к положительному

ортанту в начале координат. Было показано, что s представляет

собой целочисленную

комбинацию исходных переменных:

 

 

 

s — п' + 2

nixi — —/о+ 2

/А'-

 

 

(^а)

Текущее

решение

tj =

0 дает целочисленной форме п +

2 nixi

нецелое

значение

—/„. Поэтому опорная

гиперплоскость

s' =

= 2 fflj

= 0 может

быть

перемещена внутрь положительного

ортанта.

 

 

 

 

 

 

 

 

Можно взглянуть на отсекающую гиперплоскость и по-друго­

му,

рассмотрев пространство tj (/ = 1 , .

. ., га)

и s в качестве

(п +

1)-й координаты,

как показано на рис. 13.4.

Тогда уравне­

ние (6 а) описывает гиперплоскость Hi в

пространстве

tj

ф s.

Уравнение

 

 

 

 

 

 

 

 

 

 

 

о = - / о + 2 / л

 

 

 

(6б)

задает пересечение гиперплоскости Hi с s == 0. Гиперплоскость Н г, являющаяся этим пересечением, отсекает начало координат в ^-пространстве.

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

ГЛАВА 14

ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

14.1.Полностью целочисленный алгоритм (Гомори [80])

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

Если ai0 (i

= 1, . . ., п + т) — неотрицательные целые, то зада­

ча решена.

Если для какой-нибудь строки ai0 <; 0, то составляется

новое уравнение и записывается внизу таблицы. Эта строка затем служит ведущей. После этого используется двойственный сим­ плекс-метод. Все элементы дополнительной строки должны быть целыми числами, а ведущий элемент равен —1. Введенная таким образом ведущая строка сохранит таблицу целочисленной. Заме­ тим, что в предыдущем алгоритме в качестве производящей строки выбиралась строка с нецелым ai0. В данном случае производящей строкой становится строка с отрицательным ai0.

Пусть дана задача целочисленного линейного программи­ рования:

максимизировать

 

 

 

71

 

 

Xq— а0о +

2 аоз ( —xj)

при условиях

 

3 = 1

 

 

 

 

 

Bi = — 1 ( —я * )> 0 ,

 

Хп —

1 (

Я-п)

0*

 

 

 

п

 

( 1 )

 

#71+1, о +

2

 

% T l+ i =

а П + 1 , } ( ---^ ) > 0 ,

 

 

3= 1

 

 

.

 

п

 

Я-п+т ~

О'п+т, 0 4 ~ 2

® n+m , j ( —

3Cj)^-0.

 

 

5 = 1

 

Условия (1) могут быть записаны как

 

 

х' =

А‘ ( —х^).

(2)

14.1. ПОЛНОСТЬЮ

ЦЕЛОЧИСЛЕННЫЙ

АЛГОРИТМ

301

Предположим, что для

t =

0

(т. е.

для

исходной

таблицы)

все ац — целые и столбцы

а;- (/

=

1 , . .

п)

— лексикографиче­

ски положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.

Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [х] обозначает наибольшее целое число, не превосхо­ дящее х. Для любого числа у (положительного или отрицатель­

ного)

и положительного X можно записать

 

 

 

 

 

 

 

 

+

 

( 3 )

где 0

^

rv <

X (гу — неотрицательный остаток от деления нацело

у на

X).

В

частности, 1 =

[1/А,] X + г.

Поэтому

если А, > 1, то

НА,]

=

0

и г =

1.

Если X =

1, то [ИХ]

= 1 и г

= 0.

Так

же

как

и

ранее, вводимое дополнительное неравенство

должно выполняться при любом целом решении задачи (1). Рас­ смотрим некоторое уравнение в f-таблице (опуская индекс строки)

с а0 <С 0 :

1

 

ж = Я о+ 2

«Н —

(4)

где х — соответствующая компонента вектора х, a Xjt — текущие небазисные переменные. Можно выразить х, а0 и aj, используя введенное выше представление (3):

х = х X 1 = х |

А,+ г } .

(5 )

а' = [ т " ] Я + °

(/ = 0 , 1 , .. ., п).

(6 )

Подставив выражения (5) и (6 ) в (4) и переставив члены, получим

2 г ^ + " = г 0 + ^ { [ х ] +

2 [ - г ] ( - * Р + [ т ] < _ : г ) } •

3= 1

3= 1

Поскольку Г; ^ 0, г ^ 0 и на переменные х и х) наложено требование неотрицательности, левая часть уравнения (7) всегда неотрицательна. Рассмотрим выражение в правой части, заклю­ ченное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требо­ ванию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т. е.

5 = [ х ] + 2 [ х ] ( -

+ [ г ] ( - х ) -

(8)

3—1

302

14. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

Целочисленная слабая переменная s является неотрицатель­ ной. Действительно, если бы s было отрицательным, т. е. прини­ мало значения —1 , —2 , . . ., то умножение на X (X > г0) сделало

бы всю правую часть уравнения (7) отрицательной, в то время как левая часть неотрицательна.

Рассмотрим два случая Х— 1 и

1. Для Х = 1

= [аД

=Подставляя в уравнение (8 ) выражение для х из (4),

получим

s = [ « о ! + 2 [ « Л ( — х\ ) — ( « о + 2 a-i ( — ^ ) } = — / о — 2 —

( 9 )

Полученное уравнение есть не что иное, как отсечение

Гомори,

полученное в § 13.1. Для ?1 > 1

имеем

и УРавнение (8 )

приобретает вид

 

 

 

- [ * ] + 2

[*]<-*}>■

 

( 10)

Уравнение

(10) должно выполняться для любого допустимого

целочисленного

решения задачи

(1). Заметим, что если

а0 < 0Г

то [aJX\ <

0 в

уравнении (10).

Поэтому уравнение (10)

может

использоваться в качестве ведущей строки в двойственном сим­ плекс-методе. В частности, всегда можно выбрать X достаточно большим, так чтобы ведущий элемент [a,jlX\ в строке (10) стал равным —1 , что позволит сохранить целочисленность таблицы.

Выбор соответствующего X будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве началь­ ного необходимо взять двойственно допустимое решение, которое можно получить добавлением ограничения xn+m+i = М — xt — . . .

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

Ш а г 0. Начать с двойственно допустимой матрицы А 0 в урав­ нении (2 ), элементы которой — целые числа (как будет видно'

из дальнейшего, матрица А° может содержать и нецелые элементы).

Ш а г 1. Среди строк с ai0 < 0 (г = 1, . . ., п + т) выбрать строку с наименьшим значением i; эта строка станет производя­ щей. (Если ai0 ^ 0 (i = 1, . . ., п + т), то задача решена.)

г) Если X > 1, то для получения отсечения (10) из (4) требуется только неотрицательность левой части уравнения (4). Следовательно, любая поло­ жительная линейная комбинация строк таблицы может служить произво­ дящей строкой.

Смотрите также файлы