Задача о максимальном потоке

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

Исходные данные задачи:

G = (V, Е, h) — ориентированный сетевой граф;

V = {i>i, v₂, v_n} — конечное множество вершин (звеньев (посредников) в сети распределения);

Е = {в, в₂,…, е_т) — конечное множество дуг (прямых связей между звеньями в сети распределения);

h — весовая функция дуг;

Cjj = h (v_it Vj) — пропускная способность дуги (v_t, vj), сд. товара / сд. времени.

Вводим целочисленные неотрицательные переменные Xjj, которые интерпретируются как величина потока товаров, проходящего по дугам сети от ?-го до у-го звена, сд. товара / ед. времени.

Требуется определить максимальную величину потока товаров, проходящих по каждому участку сети от начального до конечного пункта, т. е. пропускную способность сети распределения.

Тогда в общем случае математическая постановка данной задачи может быть сформулирована следующим образом:

при ограничениях.

При этом первое ограничение в системе ограничений (9.4) требует выполнения следующего условия: величина потока, выходящего из вершины v_s (истока), должна быть равна величине потока, входящего в вершину v_t (сток). Вторая группа ограничений в системе (9.4) гарантирует выполнение следующего условия: любой частичный поток, входящий в каждую промежуточную вершину графа, должен быть равен потоку, выходящему из этой вершины. Общее количество ограничений первого и второго видов должно быть равно п — 1. Третья группа ограничений в системе (9.4) требует выполнения следующего условия: величина потока, протекающего по дуге (v_jt v.), должна быть неотрицательной и не должна превышать пропускной способности этой дуги Сц. Последнее ограничение в системе (9.4) требует, чтобы все переменные принимали только целочисленные значения.

В специальной литературе рассматривается методика решения задачи о максимальном потоке в сети в различной постановке, а именно задача нахождения максимального потока с несколькими источниками и стоками, задача нахождения потока минимальной стоимости и др.^[1] Для их решения разработаны специальные методы, которые зачастую оказываются более эффективными, чем поиск решения программой MS Excel.

• [1] См., напр.: Греши. юв А. А. Математические методы принятия решений; Леоненков А. В. Решение задач оптимизации в среде MS Excel.