Транспортные сети и электрические цепи

10

1. Решение должно быть оптимальным
   В населенный пункт В необходимо организовать бесперебойную доставку грузов из пункт А. В пункт А имеется достаочное, практическое неограниченное количество автоматизированного тоннжа, но количество грузов, отправляемых из А в В в единицу времени, ограничено из-за дорогных условий.

Пункты А и В связаны сетью дорог, схема которой приведена на рисунке 1. Номер 1 на этой схеме обозначен пункт отправления А, номер 5 — пункт назначения В, номерами 2, 3, 4 — промежуточные пункты — перекрестки дорог. Направление движения указано стрелками. Каждый участок пути может пройти за единицу времени не более определенного числа тонн грузов (обусловливаемого шириной участка пути в его наиболее узком месте, характером покрытий, состоянием местов и др.). Изовем это число пропускной способностью и будем считать его известным для каждой из участков пути, соединяющих качне-либо два пункта на нашей схеме.

11

Пропускную спссобность участка, ведущего из пункта $i$ в пункта $j$ (участка $i - j$), созначит через $a_{ij}(T/\mu a c)$.

Допустим, что мы стремимся отправлять в каждой единицу времени из $A$ в $B$ грузов как можно больше. Не следует, однako, думать, что для этого нужно отправлять ежедневно $a_{12}$ тонн по участку $1 - 2$ и $a_{13}$ тонн по участку $1 - 3$: ведь может оказаться, что из-за недостаточной пропускной способности других участков пути в каких-то промежуточных пунктах образуется «пробки», в результате чего движение нарушится или прекраится совсем. Например, если $a_{12} > a_{23} + a_{24}$, то «пробка» возникнет на перекрестке 2. Значит, для налучшей организации транспортировки грузов из $A$ в $B^*$) нам нужно решить такую задачу: определить, сколько тонн грузов нужно ежедневно по каждой участку дорогной сети, связывающей пункты $A$ и $B$, чтобы при этом не превысить пропускной способности ни одного из участков сети, не создать ни одной «пробки» в промежуточных пунктах и чтобы количество грузов, ежедневно доставляемых в $B$, было наиболее.

*) Такую организацию снабжения называют оптимальным.

Искомое количество грузов, проводимых по участку $i - j$ ежедневно (объем перевозок), обозначим через $x_{ij}(T/\mu a c)$.

Итак, задача поставлена. Но как ее решить?

2. Листая старые номера «Кванта»

Просматривая комплект журнала «Квант» за 1970 год, в разделе «Сети и потоки» статьи М. И. Башмакова «Паросочетания и транспортные сети» находим нашу задачу, только в несколько более «уценой» одежде.

Оказывается, схемы, составленные из точек и стрелок (как на рисунке 1), называются орентированными графами, причем точки — вершин нами, а стрелки — угами графа. Каждый дуга имеет определенное направление (отсюда и название — орентированный граф), поэтому одна из соединений его вершин — начальная, другая — конечная; говорят также, что дуга выходит из начальной вершины и входит в конечную. Вершина, являющаяся для всех связанных с него дуг начальной (конечной), называется входом (в выходом) графа (на рисунке 1 — вершины 1 и 5 соответственно). Орентированный граф с одним входом и одним выходом — это и есть граница сеть (именено таков граф на рисунке 1). Вершины транспортировки сети, не являющиеся входом или выходом, называются проекторными м尼.

Остановим на минуту этот поток терминов и переведем двух. Конечно, замена слов «сеть дорог» — «транспортная сеть», «пункт» — «вершина», «участок пути» — «дуга» нас к решению не приблизила. Зато выяснились, что мы не perвыше запитересовались подобной пробелой. Провните еще немного терпения — и вы придете к широкому известной в математике формулировке нашей задачи.

Искомую величины объема перевозок $x_{ij}$ называют потоком по

12

дуге $i-j$, а сумму потоков по всем дугам, выходящим из входа сети (в нашем случае $x_{12} + x_{13}$), — потоком по сети. Теперь, наконец, нашей задаче можно придать «парадную форму».

Задача о максимальном потоке. Дана трансортиная сеть, для каждой дуги комори указана пропускная способность. Требуется определить потоки по дугам сети, не превосходящие соответствующих пропускных способностей, так, чтобы для любой промежуточной вершины сумма потоков по входящим дугам была равна сумме потоков по выходящим дугам («условие неперерывности потока») и чтобы поток по сети был наиболее низ возможных.

Итак, наша задача — частный случай задачи о максимальном потоке (условие неперерывности потока — это знакомое нам условие отсутствия транспортиных «пробок»). Пользовясь веденными обозначениями, ее можно сформировать так:

Найти максимальное $x_{ij}$ потоков по дугам, при коморых достизации максимума величины потока по сети
$$X = x_{12} + x_{13}$$

(1)
при следующих условия:
a) определение пропускных способностей дуг
$$x_{12} \leq a_{12}, x_{13} \leq a_{13}, x_{23} \leq a_{23},$$
$$x_{24} \leq a_{24}, x_{34} \leq a_{34}, x_{35} \leq a_{35},$$
(2)
неперерывность потока в пропускных вершинах
$$x_{12} - x_{23} - x_{24} = 0,$$
$$x_{13} + x_{23} - x_{34} - x_{35} = 0,$$
$$x_{24} + x_{34} - x_{45} = 0.$$

(3)
При установившемся потоке количество грузов, вывозимых из входа 1, должно быть равно количество грузов, поступающих за то же время на выход 5 (иначе нарушилось бы условия неперерывности потока):
$$X = x_{12} + x_{13} = x_{35} + x_{45}.$$

(4)
Раз мы нашли в стате М. И. Башмакова формулировку нашей задачи, естественно там же попскать и решение. И действительно — углубившись в чтение, находим изложение алгоритма Форда — Фолкерсона, с помощью которого можно определить все значения $x_{ij}$ (предполагая, правда, что это целые числа). Нало только запасись терпенiem; чтобы разобраться в алгоритме и суметь применить его, придется изрядно потрудиться. Не удивительно, если у читателей, недолюбливающих вычисления, возникнет в этом месте вопрос: а нельзя ли как-нибудь инчае?

3. О полные аналогий

Посмотрите внешательно на уравнение (3). Чем-то они нам очень знакомы… Ба, да ведь если трансортиную сеть считать электрической цепью, а объемы перевозок $x_{ij}$ — величины токов в соответствии их ветвях цепи, то уравнения (3) выражают просто 1-й закон Кирхгофа для промежуточных узлов цепи: аллебрацией сумма токов в узле равна нулю (то есть сумма токов, втекающих в узел, равна сумме токов, втекающих из узла)!

Правда, эта аналогия не полная, поскольку закон Кирхгофа обычно формулируется для за мкнутей цепи и относится к любом безмкнутя, а условия типа (3) неверны для крайних узлов 1 и 5. Однако можно так видно изменить задачу о потоке, что отмеченное расхождение устройства. С этой целью ведем в транспортиную сеть дополнительнуюную дуги ограничивающую не будем, а поток по ней применять равным $X$, то есть поток по сети. По полученной обобщенной сети поток будет совершать уже замкнутый путь от входа к выходу по заданной транспортиной сети, а затем — от выхода на вход по дополнительной дуге.

Тогда нашу задачу можно переформулировать так: определить также обобщенную перевозок $x_{ij}$, при коморых

13

Рис. 2.

доступаем максимум величина $X$ (помок по семи) при ограничениях (2) и условиях (3) и (4) непрерывности потока во всех узлах:

$$X - x_{12} - x_{13} = 0,$$
$$x_{12} - x_{23} - x_{24} = 0,$$
$$x_{13} + x_{23} - x_{34} - x_{35} = 0,$$
$$x_{24} + x_{34} - x_{45} = 0,$$
$$x_{35} + x_{45} - X = 0.$$

Получалась полная аналогия с законом Кирхгофа, и поэтому возникнет вопрос: а нельзя ли построить электрический модель транспортиной сети, в которой искомым потокам по дугам соответствовали бы токи в ветвях, определяемые непосредствием измерением без каких-либо вычислений?

Мы показем, что такую модель построить можно.

Естественно, что дугам сети в этой модели должны соответствовать ветви электрической цепи, а вершина — узлы цепи.

Заметан ие. Мы будем пользоваться следующими обозначениями: $\sigma$ — источник тока указанного направления, $a$ — сила тока в ветви; $\mu$ — источник направления, $u$ — величины направления в ветви; $\beta$ — диод, пропускящий ток в направлении слева направо.

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

14

Рис. 4.

При этом в схеме ветви появились узлы $\alpha$ и $\beta$, которые в транспортировке не были. Направление и величины тока в ветви $\alpha - M - \beta$, содержащей источник тока, выполняются этим источником; направление тока в ветви $\alpha - N - \beta$ определяется диодом; величины тока в ней обозначим $I_{ij}$. Токи в ветвях $i - \alpha$ и $\beta - j$ обозначим через $\tilde{x}_{ij}$ и $\tilde{y}_{ij}$ соответственно, направления этих токов указаны на схеме.

Применение закона Кирхгофа дает:

1. в узле $\alpha$: $\tilde{x}_{ij} + I_{ij} = a_{ij}$ или $I_{ij} = a_{ij} - \tilde{x}_{ij}$ по свойству диода $I_{ij} \geq 0$, следовательно,
   $$\tilde{x}_{ij} \leq a_{ij},$$
   (6)
2. в узле $\beta$: $a_{ij} = \tilde{y}_{ij} + I_{ij}$, то есть
   $$\tilde{y}_{ij} = \tilde{x}_{ij}.$$
   (7)

Значит, по основной ветви $i - j$ цепи идет ток заданного направления (от узла $i$ к узлу $j$), величина которого $\tilde{x}_{ij}$ не превозходит пропускной способности $a_{ij}$ соответственно; по правилам построения модели $U = 1$.

Мы утверждаем, что ток $\tilde{x}_{ij}$, установливающийся в основных ветвях электрической модели транспортировки, численно равны объемам перевозок по соответствующим дугам и дает решение задачи о максималь-

15

ном потоке для этой сети. При этом ток $\tilde{X}$ в дополнительной ветви модели численно равен максимальном потоку по сети.

Если нам удastoreя это доказать, то построенная модель полностью решает нашу задачу: достаточно, приведем модель в действие, изменить амператором токи $x_{ij}$ в ветях!

4. Итак — за работу

Чтобы убедиться, что численные значения токов $\tilde{x}_{ij}$ в ветях модели являются объемами перевозок, дающим решение задачи о максимальном потоке, нужно доказать, что при $\tilde{x}_{ij} = \tilde{x}_{ij}$ выполняются условия (2) и (3) и что величины потока $X$ в сети принята наиболее из возможных значений.

Не первый часть этого утверждения мы уже доказали. В самом деле, написав неравенства (6) для всех ветвей модели $\tilde{x}_{12} \leq a_{12}, \tilde{x}_{13} \leq a_{13}, \tilde{x}_{23} \leq a_{23}, \tilde{x}_{24} \leq a_{24}, \tilde{x}_{34} \leq a_{34}, \tilde{x}_{35} \leq a_{35}, \tilde{x}_{45} \leq a_{45}$, (9) получим, что для токов $\tilde{x}_{ij}$ условия (2) выполнены, а применив 1-й закон Кирхгофа ко всем основным узлам модели, получим для токов $\tilde{x}_{ij}$ пять соответствующих условий (3).

Значит, осталось только доказать, что величина $\tilde{X}$ в электрической цепи есть наиболее из возможных значений потока $X$, совместимых с условиями (2) и (3). Доказательство этого факта состоит из двух частей.

1. Покажем сначала, что для любых значений переменных $x_{ij}$, удовлетворяющих условия (2) и (3), выполняется неравенство
   $$\tilde{X} = x_{12} + x_{13} \leq \sum_{i,j} a_{ij}u_{ij},$$ (11)

где $u_{ij}$ — численное значение напряжения в ветви $i - j$, а сумма берется по всем ветям электрической цепи *), то есть показем, что при любых допустимых объемах перевозок по дугам транспортировки сети поток $X$ по сети не превышает числа $\sum_{i,j} a_{ij}u_{ij}$.

В силу неравенств (2) и неотрицательности $u_{ij}$ (см. (8)) имеем $x_{ij}u_{ij} \leq a_{ij}u_{ij}$; следовательно,
$$\sum_{i,j} x_{ij}u_{ij} \leq \sum_{i,j} a_{ij}u_{ij}.$$ (12)

Вспомним теперь, что $u_{ij} = p_i - p_j$, где $p_i, p_j$ — потенциальы соответствуют узлов. Поэтому
$$\sum_{i,j} x_{ij}u_{ij} = \sum_{i,j} x_{ij}(p_i - p_j) = x_{12}(p_1 - p_2) + x_{13}(p_1 - p_3) + x_{23}(p_2 - p_3) + x_{24}(p_2 - p_4) + x_{34}(p_3 - p_4) + x_{35}(p_3 - p_5) + x_{45}(p_4 - p_5) = p_1(x_{12} + x_{13}) + p_2(-x_{12}) + p_2(x_{13} - x_{23}) + p_3(-x_{13} - x_{23}) + p_4(-x_{24} - x_{34}) + p_5(-x_{35} - x_{45}).$$

Выражения в скобках при $p_2, p_3$ и $p_4$ равны нулю (см. (3)); при $p_1$ и $p_5$ равны $X$ и $-X$ (см. (4)), $p_1 - p_5 = U = 1$; поэтому
$$\sum_{i,j} x_{ij}u_{ij} = p_1X - p_5X = (p_1 - p_5)X = X.$$ (13)

Учитывая (12), получаем нужное неравенство
$$\tilde{X} \leq \sum_{i,j} a_{ij}u_{ij}.$$ (14)

*) Символ $\sum_{ij}$ обозначает сумму членов расматриваемого вида, соответствующих всем возможным для данного задачи набора значений индексов $i, j$. В нашем случае
$$\sum_{i,j} a_{ij}u_{ij} = a_{12}u_{12} + a_{13}u_{13} + a_{23}u_{23} + a_{24}u_{24} + a_{34}u_{34} + a_{35}u_{35} + a_{45}u_{45}.$$

16

Рис. 5.

Это и будет означать, что $\tilde{X}$ — наиболее из возможных значений $X$.

Для доказательства равенства (14) воспользуемся соответствием (8), описывающим свойство идеального диода:

$$u_{ij} (a_{ij} - \tilde{x}_{ij}) = 0$$ или $a_{ij} u_{ij} = \tilde{x}_{ij} u_{ij}$.

Отсюда непосредственно следует, что

$$\sum_{i,j} a_{ij} u_{ij} = \sum_{i,j} \tilde{x}_{ij} u_{ij}.$$ (15)

Поскольку для токов $\tilde{x}_{ij}$, $\tilde{X}$ выполняны те же соответствия (1), (4), что и для $x_{ij}$ и $X$, то

$$\sum_{i,j} \tilde{x}_{ij} u_{ij} = \tilde{X}.$$ (16)

5. Попробуйте сами

Из тех же (идеализированных!) элементов — источников тока, источников напряжения и диодов — можно построить электрические модели для решения и других оптимизации задач, связанных с трансportными сетями. Рассмотрим здесь одну такую задачу, имеющую больше значения в экономике.

Задача о минимизации трансportных затрат. Пусть дна трансportная сеть и известно, что стоимость перевозки единицы груза по дуée $i - j$ равна $c_{ij}$ (см. рис. 5). Требуется определить объем перевозок $x_{ij}$ по дуе-

Рис. 6.