Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 42
Текст из файла (страница 42)
Так как ~ (2, 2') ограничена сверху величиной ш[п [с (2, 2'), с (1, 2; 1', 2') — / (1, 1')[, то алгоритм конечен. ° Заметим, что случай, когда Ю1 = Л', или Л', = Лло является частным случаем, при котором выполняются условия теоремы 11.1. Действительно, этот частный случай может быть представлен с помощью сети, в которой Ьлл или Ьлл — произвольно большое число.
ых.многопгодтктовык потоки 1, если дуга 1 входит в цепь у, ап= 0 в противном случае. и Обозначим через х; величипу потока, протекающего ло цепи у, Тогда задача максимизации суммы величин всех цешгых потоков примет вид максимизировать ~ х; при условиях 1 апх;+з; =Ь; г (1=.1, 2, ..., вь), х,, з;)О, где з; — слабые переменные. Заметим, что при такой формулировке задачи матрица А мозкет иметь миллионы столбцов, где всевозмоигным цепям каясдого из продуктов соответствуют свои столбцы. К счастью, как будет показапо ниже, для того, чтобы решить задачу (1), иам понадобится запоминать только матрицу размера (пз + 1) х х (т + 1). В ограничениях (1) мпогопродуктовый характер задачи представлен в неявном виде, он учитывается при построении матрицы А г).
В случае когда имеется единственный продукт, задача (1) превращается в обычнуго задачу о максимальном потоке. Предположим, что имеется пг столбцов, образующих начальный базис задачи (1). Тогда можно разрешить (1) относительно этого ') Имеетсн в виду, что в магрнцо А каждая цепь фигурирует столько раз, сколько различных продуктов может по ней перевозиться.— Прил. леры.
11.2. Многопродуктовые потоки (Форд и Фалкерсон [66!, Томлии [186)) Прежде чем приступить к изучению этого параграфа, читателю рекомендуется перечитать первые 5 абзацев $ 11.1. Рассмотрим сначала задачу о максимальном многопродуктовом потоке.
Пусть в сети для каждого продукта задан источник и сток. Сеть содержит т дуг, заданы их пропускные способности Ьп Ьз,..., Ь . Для каждого продукта в сети имеется несколько цепей, ведущих из источника в сток. Требуется пропустить поток каждого продукта по цопям таким образом, чтобы не были превышены пропускные способности дуг и сумма величип потоков по всем цепям была бы максимальна. Произвольная цепь в сети может быть кредставлепа т-мерным вектором, 1-я компонента которого равна 1, если дуга 1 входит в эту цепь, и равна 0 в противном случае. Определим матрицу инциденций дуги-цепи А = (аы) следующим образом: ГЛ.
>!. МНОГОПРОДУКТОВЫК ПОТОКИ 240 базиса и найти вектор цен >т = (я„яа,..., Им), где каждый элемент и! соответствует своей строке. Заметим, что относительная оценка с! каждого небазисного столбца а; определяется выражением с! =- с! — пар Если все с! (О, то текущий базис является оптимальным. Если некоторый с! ) О, то соответствующий этому с! столбец а; должен быть введен в базис. Оказывается, что задача нахождения с! несложна. Будем интерпретировать я! как длину дуги й Тогда величина ма; будет равна длине той цепи, которой соответствует столбец а!. Заметим, что с; = +1 для всех столбцов. При вычислениях с помощью симплекс-метода вектор я появляется в нулевой строке под слабыми переменными ').
Оказывается, что пам не нужно запоминать все столбцы матрицы А, соответствующие всевозможным цепям каждого продукта. На каждой стадии вычислений можно просто использовать модифицированный симплекс-метод и запоминать матрицу размера (т -) 1) х (>и + 1). Если какая-то из цен я! окажется отрицательной, то столбец, стоящий под этой ценой я! в симплексной таблице, выбирается в качестве ведущего. Если все я, окажутся неотрицательными, то будем интерпретировать л; как длины дуг и искать для каждого продукта кратчайшую цепь, ведущую из источника в сток.
Если кратчайшие цепи для всех продуктов окажутся длины 1 или больпге, то это значит, что текущий базис является онтммальным т). Заметим, что перед введением в таблицу каждый столбец должен быть скорректирован, как зто делается в з 7.2. Перейдем теперь к многопродуктовой задаче о допустимости. Для каждого продукта задана величина потока, и требуется определить, могут ли быть эти величины одновременно реализованы в заданной сети. Например, пусть задана сеть с ограничениями на пропускные способности дуг, представленная на рис.
11.8. Требования к четырехпродуктовому потоку представлены на рис. 11.9 (т. е. нужно пропустить 2 единицы 1-го продукта из )>>! в й ю три единицы 2-го продукта — нз )т'т в Л', и т. д.). Требуется определить, моягет ли быть пропущен этот четырехпродуктовый поток в заданной сети так, чтобы пропускные способности дуг не были бы превы>пены. Рассмотрим так называемые допустимые сети, которые удовлетворяют заданным требованиям к потоку. Каждая такая сеть получается следующим образом. Для калдого продукта находят некоторую цепь из его источника в сток, затем каждой дуге этой цепи приписывают пропускную способность, равпуи> заданному !) В нулевой строке под слабыми поременными появляется вектор я, а ио — я из-за того, что мы используем — св и — ск в исходной таблице.
т) Если длина некоторой кратчайшей цепи окажется меньше 1, то столбец, соответствующий атой цепи, дол>кеи быть введем в базис.— При верее. 11ОЬ МНОГОПРОДУКТОВЫК ПОТОКИ требованнто к потоку этого продукта. Сеть, получаемую в результате «наложения» друг на друга цепей, соответствующих всем заданным требованиям к потоку, назовем допустимой. Можно считать, что все допустимые сети имеют те же дути и узлы, что и исходная сеть, по разные дуговые пропускные способности.
[Некоторые из пропускных способностей дуг могут быть равны О, Р к с. 11.8. Дуговые пропускные способности. Р к с. 11.9. Требава- нвя к соти. 16 т. ху но эти дуги не выбрасываются, чтобы все допустимые сети имели одинаковые дуги.) Может существовать несколько миллионов допустимых сетей, каждая из которых удовлетворяет заданным требованиям к многопродуктовому потоку. Произвольную допустимую сеть можно представить т-мерным вектором аз = [аьп а»;,..., а 1], где а„— пропускпая способность 1-й дуги, а»1 — пропускная способность 2-й дуги и т. д.
Тогда все допустимые сети могут быть представлены в виде матрицы [аы], содержащей т строк. [Например, для сети на рис. 11.8 матрица [аы] будет иметь 5 строк.) Будем называть линейной выпуклой комбииауией допустимых сетей лппейку1о выпуклую комбипаци>о векторов а;. Любая линейная выпуклая комбинация допустимых сетей также удовлетворяет заданным требованиям к потоку. Предлагаемый ниже подход позволяет определить, содержится лк в исходной сети такая сеть, которая является линейной выпуклой комбинацией допустимых сетей.
Если исходная сеть, представимая в виде [Ь„Ь, ..., Ь содержит сеть вида [Ь;, Ь,',..., Ь'„], где Ь'; ( Ь1 [1 =.— 1, 2, ..., т), а столбец [Ь;, Ь;,..., Ь' ] является линейной выпуклой комбинацией столбцов матрицы [а11], то эта исходная сеть удовлетворяет заданным требованиям к потоку. Обозначим через х1 коэффициент при столбце а1 в линейной комбинации столбцов матрицы [ап]. Тогда многопродуктовую задачу о допустимости можно сформулировать следующим образом: »1аксимизироватьб=х хз С' Гл. !1.
мнОГОпгодуктовьте потоки 242 при условиях ~ амхт+г;=-Ь! (1=1, 2, ..., т), хп 11) О. Если оптимальное значение 0 ) 1, это значит, что в исходной сети все требования к многопродуктовому потоку выполняются. Если оптимальное значение 0 = 1, то исходная сеть является допустимой. При такой формулировке матрица [а;;[ может содерх1ать миллионы столбцов, но, к счастью, нет необходимости все их выписывать. Если у нас имеется т столбцов, являющихся начальным базисом аадачи (2), то с помощью симплекс-метода можно найти вектор цен и. С помощью этого вектора и можно, как это делалось в модифицированном симплекс-методе, найти столбец, который увеличивает значение целевой функции. Так как относительная оценка с; столбца а! определяется выражением ст — — с; — пагь а су = — 1 для всех столбцов, то нам надо искать минимальную из величин па;.
Если при минимальном значении тта! Получится, что с; = = с, — тта! ( О, то текущее решение будет оптимальным. При вычислениях мы запоминаем матрицу раамера (т + 1) х х (т + 1) и интерпретируем величину я! как стоимость дуги ! единичной пропускной способности. Когда в симплекспой таблице получа!отея все п; ) О, мы пытаемся ввести в базис столбец, который представляет саму!о дешеву1о допустимую сеть '). Если получается 0 ) 1, значит, все требования к многопродуктовому потоку выполняются. Если получается, что 0 ( 1, а наг ) 1 для всех 1, то исходная сеть не содер1кит линейной выпуклой комбинации допустимых сетей ').
Рассмотрим пример, иллюстрирующий решение многопродуктовой задачи о допустимости. Пусть в сети на рис. 11.8 числа около дуг указывают их пропускные способности, а требования к четырехпродуктовому потоку в этой сети представлены на на рис. 11.9. Требуется определить, можно ли этот четырехпродуктовый поток пропустить в заданной сети. В симплексной таблице 11 1 представлены дуговые пропускные способности исходной сети (как аначения слабых неременных); 0 в атой таблице равно О. Здесь вектор Ь =- [Ь1, Ье, Ьэ Ью Ье) = = [е/в, Чт, 3, 4, ь/е[. Заметим, что в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
