4.7.2. Задача о распределении потоков в сетях

В задачах подобного типа требуется найти оптимальный вариант транспортировки продукта по сети определенной конфигурации. В этом случае элементы сети имеют следующие характеристики: с_ij – стоимость транспортировки единицы продукции для ребра сети между вершинами i и j, D_ij – пропускная способность этого ребра, в общем

случае ограниченная в пределах (если ребро между данными вершинамиi и j графа отсутствует, то пропускная способность равна нулю, если поток ничем не ограничен – то бесконечности). Очевидно, что в этом случае должно выполняться требование сохранения потока: суммарный поток, входящий и выходящий из узла, должны быть равны.

Пусть x_ij – поток в ребре графа, тогда для промежуточной вершины сети

, (4.6)

где k – перечисление всех входящих, j – всех исходящих ребер для вершины i.

Для потока в любом ребре требуется, чтобы

.

Для начальной и конечной вершины, очевидно, необходимо выполнение условия

,

Рис. 4.32. Решение задачи на поиск кратчайшего маршрута

где A₁ – максимальный выходной поток, создаваемый исходной вершиной сети, необходимо, чтобы он был меньше, чем суммарная пропускная способность всех исходящих из вершины ребер,

,

где B_n – максимальный поток, потребляемый конечной вершиной сети, он также не должен превышать пропускной способности входящих ребер.

Возможны различные постановки задачи оптимизации – минимизации стоимости транспортировки и максимизации потока. Получаем соответственно две формулировки математической модели задачи.

1. Минимизация стоимости:

- минимизируемая целевая функция – общая стоимость транспортировки. Ограничения:

- поток не может накапливаться в промежуточных вершинах, т.е.

- по пропускной способности;

- сохранение непрерывности потока.

2. Максимизация потока:

- максимизируемая целевая функция – суммарный поток, входящий в конечный узел.

- суммарные затраты не должны превысить величины имеющихся средств С_s.

Ограничения:

- поток не может накапливаться в промежуточных вершинах, т.е.

- по пропускной способности;

- сохранение непрерывности потока.

Рассмотрим задачу на поиск максимального потока для системы автодорог, представленной на рисунке документа рис. 4.33, где цифрами обозначена максимальная пропускная способность участков транспортной сети (тысяч машин в день).

Заданный граф частично ориентирован. Для того чтобы прийти к математической модели, необходимо преобразовать граф в ориентированную сеть. Это можно сделать, заменив каждое неориентированное ребро – дорогу с двусторонним движением двумя ориентированными – односторонними полосами движения, каждая с исходной пропускной способностью. Дороги x₄ и x₅ стали односторонними, так как возможность противоположного направления движения в данной задаче для них несущественна.

Задача может быть решена геометрически: согласно теореме, максимальная пропускная способность сети равна минимальной пропускной способности сечений сети. Аналитическое решение сводится к методам линейного программирования. Кроме того, тогда возможно определить соответствующие ему потоки в каждом ребре сети.

Рис. 4.33. Решение задачи на поиск максимального потока для

системы автодорог

Сравнение максимально возможного потока, исходящего из начального узла сети, с результатом решения (9>6) показывает, что данная транспортная сеть требует дополнительного расширения для его пропуска.