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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

250

ГЛ. 11. МНОГОПРОДУКТОВЫЕ п о т о к и

Синтез сети для этого случая будет здесь рассмотрен подробно. Обозначим через у = [г/i, г/2> • • У'т\ m-мерный вектор, )-я ком­ понента которого равна пропускной способности дуги j в некото­ рой сети, содержащей т дуг. Вектор у полностью описывает сеть, которую нужно синтезировать.

Обозначим через N' нг-мерный вектор, описывающий некоторую сеть, удовлетворяющую всем требованиям к потоку в момент времени t, г-я компонента вектора N* равна пропускной способ­

ности дуги i в этой сети. Ясно, что векторы N* образуют выпуклое неограниченное многогранное множество в m-мерном простран­

стве. Обозначим через N* крайние точки этого выпуклого множе­ ства. Тогда существует по крайней мере один оптимальный вектор

N4, который может быть представлен в виде

Nf = 2^ iN i ( 1 < 2 М ) ,

(4)

гг

где к\ ^ 0 .

Для того чтобы сеть у удовлетворяла требованиям к потоку в каждый момент времени, необходимо и достаточно, чтобы она

содержала в себе сети N(, t — 1,

2, . . ., Т. Пусть с == [clt

с2, . . .

. . ., ст] — вектор дуговых стоимостей.

Тогда задача

синтеза

заключается в минимизации

 

 

 

при условиях

су

 

 

 

 

 

y > 2 M Nn

* = 1’

Г ’

 

г

 

 

(5)

 

 

 

г

Здесь у и к\ являются неизвестными. Векторы N* цредполагаются известными, а вектор с — заданным. В такой формулировке имеется (т-\ i)T строк и огромное число столбцов.

Перепишем (5) в следующем виде:

 

 

2 MIN', - 1 ] < [ у , - 1 ] ,

* = 1, 2, . . . , Т,

(6)

 

 

г

 

 

 

где

 

Из теоремы 1.3

(леммы Минковского —Фаркаша)

сле­

дует,

что

либо неравенство

Ах^ГЬ

имеет неотрицательное реше­

ние,

либо

неравенства

 

 

 

у А > 0 ,

уЬ < 0

11.3.

СИНТЕЗ КОММУНИКАЦИОННЫХ СЕТЕЙ

251

имеют неотрицательное решение. Другими

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

А х ^ Ь имеет неотрицательное решение

тогда

и

только тогда,

когда при любых я ^ О из яА ^ О следует,

что яЬ ^ О 1).

 

Применим эту

лемму к

группе из

т + 1

неравенств в (6 ),

соответствующих

некоторому

конкретному

t =

k.

Получим,

что

эти неравенства 2

Щ[N^, — 1 ]^ [у , — 1 ]

имеют

неотрицательное

решение тогда и только тогда, когда существует неотрицательный

вектор (я£, я*),

такой, что

 

(я£,

я{|) [Nj1,

— 1 ]^ 0 при любых

г,

 

(я£, я|})[у,

— 1 ] > 0 .

(7)

 

 

Положим

=

— я*}, я '1 = (я*, я'г). Тогда (7)

эквивалентно

 

 

 

я к [№, 1 ] > 0 ,

(8)

 

 

 

 

 

 

 

Яь [у, 1 ] > 0 .

( 8' )

Здесь яй = (я^, я£), я * — неотрицательный m-мерный вектор, лк— неположительный скаляр.

Векторы я к = (лк, л к), удовлетворяющие условиям (8 ), обра­

зуют выпуклое неограниченное многогранное множество, имеющее конечное число крайних точек я*, я*, . .., я£, так что любой

вектор я ь, удовлетворяющий (8 ), может быть выражен как поло­

жительная комбинация векторов я£. Следовательно,

ограниче­

ния (8 ')

можно рассматривать не для всех векторов л к,

а лишь для

крайних

точек:

 

 

 

 

 

 

 

л) [у, 1 ] > 0 ,

/ = 1 , . . . ,

q(k).

 

Повторяя

эти

рассуждения

для всех

моментов времени t =

= 1, 2,

. . .,

Т,

получим, что задача (5)

может быть переформу­

лирована следующим образом:

 

 

 

минимизировать су при условиях

]) Этот результат может быть также получен из теоремы двойственности. Условие, что неравенство Ах Ь имеет неотрицательное решение, эквива­ лентно тому, что равно нулю оптимальное решение следующей задачи линей­

ного программирования: минимизировать £ =

2

xi ПРИ условиях 1х“ + Ах +

+ Is

= b, х ^

0. Двойственная ей задача имеет вид: максимизировать я'Ь

при

условиях

1я'

1, я'А < 0, я'

0.

Полагая я' = — я, получим:

минимизировать

яЬ

при условиях яА

0,

я

^ 0.

252ГЛ. 11. МНОГОПРОДУКТОВЫЕ потоки

Вэтой формулировке имеется т переменных и очень большое число строк, каждая из которых соответствует своему я). Если

можно было бы записать все я], то задача (9) решалась бы как обычная задача линейного программирования. Следовательно,

вся трудность заключается в получении векторов я,t-, являющихся векторами коэффициентов тех неравенств, которые используются в вычислениях.

Задачу (9) можно решать двумя методами — двойственным и прямым.

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

Двойственный метод состоит из следующих шагов:

1)Выбор строки: среди неравенств (9) выбирается то, которое не удовлетворяет текущему значению у.

2)Выбор столбца, осуществляемый по обычным правилам двойственного симплекс-метода.

3)Выполнение преобразований Гаусса применительно только

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

Шаги 2 и 3 представляют собой обычные шаги модифицирован­ ного симплекс-метода, а шаг 1 обладает специфическими осо­

бенностями.

Вычисления в основной части могут быть начаты с любого двойственно допустимого вектора у (например у = [0 , 0 , . . ., 0 ],

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

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

i

при условиях

y > 2 ^ i - Ni, i = i, .... g(fc).

(10)

Здесь вектор у — фиксированный двойственно допустимый вектор, полученный в основной части; t = к фиксировано; вели­

11.3. СИНТЕЗ КОМ МУНИКАЦИОННЫХ СЕТЕЙ

253

чины Xi являются

неизвестными. Вычисления можно

начинать

„

 

-vrk

 

с любой допустимой сети

.

 

При решении задачи (10) возможны 2 исхода:

1.Величина 0 ^ 1 при фиксированном к. Это означает, что текущее значение у представляет собой сеть, допустимую для периода времени t = к. Если 0 ^ 1 при всех t, то, значит, у содержит в себе сеть, допустимую для всех t. Следовательно, у является и двойственно допустимым, и прямо допустимым, т. е. является оптимальным решением.

2.Найден т-мерный вектор относительных оценок я15 который

является решением задачи, двойственной к (1 0 ):

л ч у = 0 <

1 ,

rtt. N i > l

(для всех £, так как все коэффициенты при Х\ равны 1 ).

Обозначим яй = (я£, — 1). Легко видеть, что

я й[у, 1 ] < 0 и ttft(№, 1 ) > 0 . (И)

Следовательно, найден вектор яй, для которого не выполняется неравенство (9) при текущем значении у, и его можно использовать в основной части.

Заметим, что задача (10) представляет собой задачу линейного программирования очень большой размерности, так как каждой сети N* соответствует свой столбец. Эти столбцы можно получать

следующим образом. Выберем слабые переменные и несколько произвольных N* в качестве базиса. Найдем из (10) оценки дуг

я j относительно этого

базиса. Вектор

N не входящий в базис,

следует ввести в базис,

если я 4]Ч{ ^ 1.

Следовательно, нам нужно

найти столбец, для которого величина

я ^ ? минимальна. Но эта

задача есть задача синтеза сети, рассмотренная выше в случае 1 .

Оценки Я] можно рассматривать как длины дуг, и для получения столбца Nf можно воспользоваться методом нахождения крат­ чайших путей между всеми парами узлов (см. [1 1 1 ]).

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

минимизировать z — су при условиях

я ‘у > 1 , £ = 1 , . . . , Т, i = l,

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