Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 44
Текст из файла (страница 44)
Случай 2. Величины гр«(з) зависят от времени, но весь период времени Т может быть разбит на отрезки, в течение каждого из которых в сети пропускается поток только одного продукта между некоторой парой полк>сов. Анализ сети заключается в нахождении максимального (одно- продуктового) потока между всеми парами полюсов. Для иеориентировапйых сетей решение имеет простую и наглядную форму (см. гл. 9 или [89]). Синтез сети, если сеть пеорнептированпая и все еы одинаковые, был рассмотрен в гл.
9. Кслн сы различны, используется аппарат линейного программирования (см. [90]). Решается задача линейного программирования с болыпим числом ограничений. Для уменьшения размера снмплексной таблицы запоминаются только строки, используемые прн вычислениях. Для получения строк, вводимых в таблицу, решается вспомогательная задача о максимальном потоке. Случай 3. Величины гр«(з) произвольным образом зависят от времени. Зтот случай является более общим, чем случаи 1 и 2.
Анализ сети. Голи разбить весь период времени па Т различных отрезков, то получится Т систем неравенств типа (3), соответствующих каждому из отрезков. На каждом яз пих получается задача, рассмотренная в случае 1 '). >) Есзп период Т разбит па такие мол кис отрезка, что г 0) можно счптзть на пих пезаввспмыпп от времена.— Пров. перев.
ГЛ. 11. МНОГОПРОДУКТОВЫЕ ПОТОКИ ~'=Х)[й[[ (1~1)[) (4) гДе Х1 > О. Для того чтобы сеть у удовлетворяла требованиям к потоку в каждый момент времепи, необходимо и достаточно, чтобы она содержалавсебесети1[1, т =- 1, 2,..., Т. Пусть с = [с1, с„... ..., см) — вектор дуговых стоимостей. Тогда задача синтеза заключается в минимизации су при условиях у~~).)Р[,, с — 1, ..., У, 1 <~Х,'., ).,'.- О.
(б) Здесь у и 21 являются неизвестными. Векторы Гт1 предполагаются 1 1 известными, а вектор с — заданным. В такой формулировке имеется (т+1)Т строк и огромное число столбцов. Перепишем (5) в следующем виде: ~Х! [Х11, — 1)([у, — 1), ~ =1, 2, ..., У, (б) где )1)О. Из теоремы 1.3 (леммы Минковского — 1Раркаша) следует, что либо неравенство Ах(Ь имеет неотрицательное решение, либо неравенства уА)0, уЬ<О Синтез сети для этого случая будет здесь рассмотрен подробно.
Обозначим через у = [у„ую..., уэ,) и;мерный вектор, 1-я компонента которого равна пропускнои способности дуги 1 в некоторой сети, содержащей т дуг. Вектор у полностью описыврет сеть, которую нужно синтезировать. Обозначим через 1[1 л1-мерный вектор, описывающий некотору1о сеть, удовлетворяющую всем требованиям к потоку в момент времени 1, 1-я компонента вектора 1[1 равна пропускной способности дуги 1 в этой сети. Ясно, что векторы 1[' обраауют выпуклое неограниченное многогранное множество в т-мерном пространстве.
Обозначим через Х'; крайние точим этого выпуклого мнол1ества. Тогда существует по крайней мере один оптимальный вектор О[1, который может быть представлен в виде 1!.3. СИНТЕЗ КОММУНИКАПИОННЫХ СЕТЕЙ 251 имеют неотрицательное решение. Другими словами, неравенство Ах( Ь имеет неотрицательрое решение тогда и только тогда, когда прн любых л 1О из лА.=зО следует, что лЬ)01).
Применим зту лемму к группе из т-~-1 неравенств в (6), соответствующих некоторому конкретному 1 —.- й. Получим, что зти неравенства~ХА![Ха, — Ц([у, — Ц имеют неотрицательное решение тогда и только тогда, когда существует неотрицательный вектор (л,", ла), такой, что (ла, л,)[Хп — Ц)0 при л!обых К, (л,", л",) [у, — Ц)0. (7) 11оло!Енм па = — и"„и"=-(л,, л,). 7'ог!!а (7) зквивалентно л'[[чь, ЦЪО, л" [у, Ц>0.
(8) (8') Повторяя эти рассуждения для всех моментов времени 1 = =- 1, 2,..., Т, получим, что задача (5) может быть переформулировапа следутощим образом: минимизировать су прп условиях л [У Ц)0, У=-1, 2, ..., !7(1), 1=1, 2,, У', (О) ') Этот результат люжет быть также получен из теоремы двойстнепнОсти. Условна, что неравенство Ах ( Ь имеет неотрицательное решение, зквнвааентпо тому, что равно путю оптимальное ров!ение следующей задачи линейного программирования: минимизировать с =- ч~~ ~л; при условиях 1хо ЕЬ Ах+ — 1е = Ь, х ) О. Двойственная ей задача имеет вид: мавсимизировать л'Ь прн условиях 1л' (1, л'А (О, л' (О.
Полагая л' = — л, получим: минимизировать лЬ прн условиях лА ) О, л ) О. Здесь л =-(л,", л,"), л," — неотрицательный т-згерный вектор, л,"— пеполопгительный скаляр. Векторы л" =. (л",', л,"), удовлетворяющие условиям (8), образуют выпуклое неограниченное многогранное множество,'имеющее конечное число крайних точек ла, л", ..., ла, так что любой 1' 3' '''' Ч' вектор л", удовлетворяющий (8), может быть выражен как положительная комбинация векторов л,".. Следовательно, ограничения (8') можно рассматривать не для всех векторов л, а лишь для крайних точек: 252 ГЛ. 11, МНОГОПРОДУНТОВЫК ПОТОКИ В этой формулировке имеется ж переменных и очень большое число строк, каждая иа которых соответствует своему п;.
Если 1 можно было бы записать все и;, то задача (9) решалась бы как 1 обычная задача линейного программирования. Следовательно, вся трудность заключается в получении векторов и;, явля1ощихся 1 векторами коэффициентов тех неравенств, которые используются в вычислениях. Задачу (9) можно решать двумя методами — двойственным и прямым. Сначала рассмотрим двойственный метод. Оп состоит из двух частей — основной и вспомогательной. В основной части используется таблица двойственного симплекс-метода; вычисления начинаются с получения двойственно допустимого базиса и соответствующего двойственно допустимого у. С помощью вспомогательной части формируются неравенства, испольауемые э оспозпой части.
Двойственный метод состоит из следующих шагов: 1) Выбор строки: среди неравенств (9) выбирается то, которое не удовлетворяет текущему значению у. 2) Выбор столбца, осуществляемый по обычным правилам двойственного симплекс-метода, 3) Выполнение преобрааовапий Гаусса применительно только к обратпой матрице, где ведущий элемент получается в результате выбора строки и столбца па шагах 1 и 2.
Шаги 2 и 3 представляют собой обычные шаги модифицированного симплекс-метода, а п1аг 1 обладает специфическими особенностями. Вычисления в основной части могут быть начаты с любого двойственно допустимого вектора у (например у = [О, О, ., 0), который является двойственно допустимым, так как по условию задачи с 0). Поскольку в самом начале еще пе получены неравенства, формируемые во вспомогательной части, то в основной части пока нельзя осуществить итерацию двойственного симплекс- метода. Тогда переходим к вспомогательной части, где решается следующая задача: максимизировать при условиях «~)„. Хь1 (10) Здесь вектор у — фиксированный двойственно допустимый вектор, получеппый в основной части; 1 =- й фиксировано; вели- 11.3.
СИНТЕЗ КОММУНИКАЦИОННЫХ СЕТЕЙ чины А1' являются неизвестными. Вычисления можно начинать с любой допустимой сети 1(~. При решении задачи (10) возможны 2 исхода: 1. Величина 0 ) 1 при фиксированном Ь. Это означает, что текущее значение у представляет собой сеть, допустимую для периода времени ~ =- 1с. Если 0 ~ )1 при всех г, то, значит, у содержит в себе сеть, допустиму1о для всех Г. Следовательно, у является и двойственно допустимым, и прямо допустимым, т. е. является оптимальным решением, 2. Найден т-мерный вектор относительных оценок я1, который является решением задачи, двойственной к (10): я1у=-0 1, Н, 1(1.- 1 (для всех 1, так как все коэффициенты при )ь1 равны 1).
Обозначим ма==(я,", — 1). Легко видеть, что я~ (у, 1] (0 и яь(1(ь1, 1))0. (11) Следовательно, найден вектор нь, для которого пе выполняется неравенство (9) при текущем значении у, и его можно использовать в основной части. Заметим, что задача (10) представляет собой задачу линейного программирования очень большой размерности, так как каждой сети Х,' соответствует свой столбец, Зти столбцы мо1кно получать следующим образом.
Выберем слабые переменные и .несколько произвольных Х1 в качестве базиса. Найдем нз (10) оценки дуг 1 кй относительно этого базиса. Вектор 1(~, не входящий в базис, следует ввести в базис, если м1г(," ( 1. Следовательно, нам нув1но найти столбец, для которого величина я1Х~ минимальна. Но эта задача есть задача синтеза сети, рассмотренная выше в случае 1. Оценки я~ можно рассматривать как длины дуг, и для получения столбца Х1 можно воспользоваться методом нахождения кратчайших путей между всеми парами узлов (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
