Ограничения записываются следующим образом

Для исходной вершины: ,

где все x_i выходят из исходной вершины, а N - число вершин графа.

Для остальных вершин: сумма дуг (переменных), прилегающих к рассматриваемой вершине, равна единице, причём дуги, входящие в вершину, берутся со знаком “+”, а выходящие - со знаком “-”.

Вид целевой функции будет следующим:

,

где значения коэффициентов целевой функции С_i характеризуют стоимости потоков (рис. 3.7).

На переменные x_i­ необходимо наложить условия неотрицательности и целочисленности.

Cистема ограничений и целевая функция для данной задачи имеют вид:

x₁ + x₂ + x₃ = 4

x₁ + x₅ - x₄ = 1

x₂ - x₅ - x₆ + x₇ = 1

x₃ - x₇ - x₈ = 1

x₄ + x₆ + x₈ = 1

x_i ³ 0

x_i - целые

F = 2x₁ + 2x₂ + 3x₃ + 5x₄ + 4x₅ + 3x₆ + x₇ + 0x₈ ® min

Решение задачи имеет вид:

x1 = 1

x2 = 1

x3 = 2

x4 = 0

x5 = 0

x6 = 0

x7 = 0

x8 = 1

F_min = 10

В этом случае получаем граф оптимального решения, изображённый на рис. 3.8.

Рис. 3.8. Граф оптимального решения

Дуги, не принадлежащие остовному дереву, имеют поток по ним равным нулю (переменные X_i=0).