Модификация основной постановки

Во многих практически важных случаях содержательное описание ситуации отличается от рассмотренного ранее. Рассмотрим основные модификации данной модели.

1. Число источников больше единицы. Прежде всего, дадим точные модифицированные формулировки введённых понятий. Предполагается, что у сети имеется несколько источников. Это означает, что есть несколько вершин, в каждой из которых нет входящих дуг (есть только выходящие). Потоком в такой сети по-прежнему является вектор, число компонент которого равно числу дуг; неравенства (1) – ограничения на потоки в дугах – также не меняются. Закон сохранения (2) выполняются во всех вершинах, кроме всех источников и стока. Определение величины потока заменяется на аналогичное: величиной потока является сумма потоков во всех дугах, выходящих из всех источников. Как и в базовом случае, максимальным потоком называ-ется любой поток с максимальной величиной Р (u).

Убедимся, что задача о максимальном потоке в данной модификации сводится к той же задаче в исходной постановке раздела 2. Пусть вершины графа сети x ₁, …, x_k (k > 1) являются источниками. Добавим к графу сети S новую вершину x ₀, и соединим её дугами со всеми «ста-рыми» источниками x ₁, …, x_k, как это показано на рис.4. Пропускные способности в новых ду-гах положим равными ∞, оставив их без изменений во всех дугах старой сети S. Таким образом, определена новая потоковая сеть T.

Рис.4

Пусть u = (u ₁, u ₂,..., u_m) – произвольный поток в исходный сети S с источниками x ₁, …, x_k. Определим поток v = (w ₁, …, w_k. u ₁, u ₂,..., u_m) в сети T, положив поток w_i в новых дуге (x ₀, x_i) равным сумме потоков во всех старых дугах, выходящих из стока x_i (i = 1, …, k). По построе-нию, старые источники стали внутренними вершинами в новой сети; при этом выполнение за-кона сохранения (2) сразу следует из определения потоков w_i. Ясно, что величины потоков u и v совпадают. Поэтому любой максимальный поток в исходной сети S получается из максималь-ного потока в новой сети T просто отбрасыванием первых k компонент. Таким образом, нахож-дение максимального потока в сети с несколькими источниками сводится к нахождению макси-мального потока в сети с одним источником.

2. Число стоков больше единицы. Конструкция практически не отличается от предыду-щей. Отличие только в том, что теперь старые стоки y ₁, …, y_l соединяются с новым cтоком y ₀.

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

Формально в данном случае сетью называется граф с теми же свойствами 1) - 3), что и ра-нее (см. раздел 1), у которого заданы пропускные способности вершин b ₁, b ₂,..., b_n. При этом потоком в такой сети (назовём их сетями 2-го рода в отличие от ранее введённых сетей 1-го рода) называется любой вектор u = (u ₁, u ₂,..., u_m), удовлетворяющий, наряду с условием сохранения потоков (2) и условием неотрицательности

u_j ≥ 0 (j = 1, 2,..., m), (4)

ограничениям в вершинах

≤ b_i (i = 2, 3,..., n), (5)

≤ b ₁ (6)

(условие (6) понадобилось выделить, так как в источник x ₁ не входит ни одна дуга).

Задача о максимальном потоке для сетей 2-го рода содержательно состоит в определении максимально возможной производительности данного участка (моделируемого сетью 2-го рода), если заданы производительности b ₁, b ₂,..., b_n всех отдельных агрегатов этого участка. Формально эта задача записывается следующим образом:

→ max

при условиях (2), (4), (5) и (6).

Заметим, что целевые функции в задаче о максимальном потоке для сетей 1-го и 2-го рода сов-падают.

Поскольку ограничения в задаче для сетей 1-го и 2-го рода различны, на первый взгляд, эта задача отличается от предыдущей задачи о максимальном потоке в сети 1-го рода. Пока-жем, что на самом деле задача для сети 2-го рода сводится к задаче для сети 1-го рода. Пусть задана сеть 2-го рода, x_i - любая вершина в ней, b_i - её пропускная способность. Заменим в гра-фе сети вершину x_i на пару вершин , и соединяющую их дугу _i с той же пропускной спо-собностью b_i. При этом все дуги, входившие в x_i, будут входить в , а все дуги, выходившие из x_i, будут выходить из вершины . Указанный переход от фрагмента старой сети к фрагменту новой сети показан на рис.5.

Аналогичным образом заменим все вершины исходной сети 2-го рода на пары вершин. Пропускные способности оставшихся дуг исходной сети (ранее они не задавались) положим равными достаточно большому положительному числу (достаточно взять число m ´ ). Таким образом, по исходной сети S 2-го рода построена сеть S * 1-го рода.

Рис.5

Утверждение 1. Максимальный поток в исходной сети S 2-го рода равен максимальному потоку в построенной по ней указанным выше способом сети S * 1-го рода ■

В силу утверждения 1 достаточно рассмотреть методы решения задачи о максимальном потоке только в сети 1-го рода. Решение задачи (3) при условиях (1) и (2) рассмотрены в следу-ющем разделе 4.