 |
 |
 |
 |
|
 |
 |
68
Задачу минимизации функции (3.13) при ограничениях (3.11)-(3.12) обычно называют линейной
сетевой задачей. Очевидно, что она является задачей линейного программирования. Если
дополнительно для каждой дуги сети
d?D определить величины r
d
? 0, называемые пропускными
способностями, то, добавив ограничения
мы получаем задачу о потоке в сети с ограниченными пропускными способностями.
Приведенные формулировки задач специально даны в столь абстрактном виде, что позволяет
подчеркнуть их универсальность. К очевидной сфере их приложения относится организация
грузоперевозок в транспортной сети. В таких моделях вершины i трактуются как пункты, соединенные
сетью дорог, и характеризуются потребностями в некотором продукте (b
i
<0) или его запасами (b
i
>0).
Задачи определения плана, минимизирующего затраты на перевозки, которые с математической точки
зрения полностью идентичны (3.11)-(3.13), (3.14), также называют транспортными задачами в сетевой
постановке.
3.2.2. Метод потенциалов для транспортной задачи в сетевой постановке. Рассмотрим задачу
определения оптимального потока Х в некоторой сети (I, D, G), для которого
при ограничениях
где r
d
? 0.
Предполагается также, что сеть является сбаланси
рованной, т. е.
Для задачи (3.15)-(3.17) справедлив критерий оптимальности:
Для того, чтобы допустимый поток Х={х
d
}
d
?
D
(т. е. удовлетворяющий условиям (3.16)-(3.17)) был
оптимальным, необходимо и достаточно существование для каждой вершины i ? I такого числа v
i
,
называемого потенциалом, что для всех дуг d = (i, j)
Заметим, что логика обоснования данного критерия абсолютно идентична той, которая
использовалась для обоснования критерия оптимальности плана транспортной задачи в матричной
постановке: построение двойственной задачи и применение соответствующей теоремы двойственности.
Для решения транспортной задачи в сетевой постановке (3.15)-(3.17) также может быть применен
метод потенциалов, который является обобщением описанного выше метода потенциалов для
транспортной задачи в матричной постановке.