Определение

Поток f в сети G (X, U) величины v от вершины s к вершине t есть функция f: U à R₊, такая, что

а) f(i, j) >=0, f(i, j) <= c(i, j) для всех дуг (i, j)

здесь c(i, j) – пропускная способность дуги.

б) ∑ f(k, i) – ∑ f(i, j) = 0, i ≠ s,t

∑ f(k, t) =∑ f(s, j) = v

СТАНДАРТНАЯ ЗАДАЧА О ПОТОКЕ МИНИМАЛЬНОЙ СТОИМОСТИ

Прямая задача линейного программирования для СЗПМС формулируется следующим образом.

Задан ориентированный граф G(X,U), где X – множество вершин,U – мно жество дуг, по которым могут протекать потоки f(i, j) про-

дукта одного вида.

Требуется найти минимум целевой функции:

H=∑ f(i,j) * h(i,j), ∀ (i,j) ∈ U. (1)

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

∑ f(i,j) - ∑ f(l,i) = b(i), ∀ i∈X, (2)

f(i,j) <= c(i,j), ∀ (i,j) ∈ U (3)

f(i,j) >= 0, (4)

где h(i,j) – стоимость передачи потока по дуге (i,j); f(l,i) - поток входящий в узел i по дуге (l,i); ограничения (2) являются условиями сохранения потока

(УСП) по дугам сети; ограничения (3) учитывает ограниченную пропускную способность дуг, а ограничение (4) – условие неотрицательности дуговых потоков.

В процессе решения прямую задачу линейного программирования (ПрЗЛП) определяются потоки по дугам f(i,j), дающие минимальное значение целевой функции.

Для ПрЗЛП существует двойственная задача линейного программирования (ДвЗЛП), сформулированная ниже.

Найти минимум целевой функции

P = p_ib_i + d_kc_k (5)

p_i - p_j + d_k >= -h_k, k = 1,..m (6)

p_i - не ограничены, i = 1,..n-1, (7)

d_k >= 0, (8)

где n – число вершин; m – число дуг; p_i – потенциал узла i; p_j – потенциал узла j; c_k – пропускная способность дуги k; δ_k – переменная-индикатор, показывающая на принадлежность дуги к минимальному

разрезу при максимальном потоке в сети. При решении ДвЗЛП опре-

деляется потенциалы узлов p_i.

Частными случаями СЗПМС, которые приходится решать в процессе управле- ния потоковыми процессами, являются задача нахождения кратчайших пу -тей и задача нахождения максимального потока в сети.