Математическая модель задачи имеет вид

(9) H = ∑ f(i,j)*h(i,j) à min

| ∑ f(s,j) - ∑ f(l,s) = 1, s - источник,

|

(10) | ∑ f(i,j) - ∑ f(k,i) = 0,, ∀ i∈X, i≠s, i≠t,

|

| ∑ f(t,j) - ∑ f(k,t) =-1, t - сток,

(11) f(i,j) >= 0 ∀ (i, j) ∈ U.

Здесь условия (10) - условия сохранения 1ед. потока пропущенного через

сеть,а, значит,выделение ориентированных цепей из s в t с дугами веса 1.

Согласно (9) из всех таких цепей выбирается цепь наименьшего веса.

Во втором случае строится дерево кратчайших путей.

(12) H = ∑ f(i,j)*h(i,j) à min

| ∑ f(s,j) = st(s), s - источник,

(13)

| ∑ f(l,i) = 1,, ∀ i∈X, i≠s,

(14) f(i,j) - двоичные ∀ (i, j) ∈ U.

(15) ∑ f(i,j) = n -1, n-число вершин графа.

Здесь n – число вершин графа, l – номер вершины, предшествующей вер-

шине i, h(i, j) – стоимость передачи потока по дуге (i, j), f(l,i) – поток, входя-

щий в вершину i по дуге (l, i).

В двойственной задаче о кратчайшем пути определяются потенциалы

вершин p_i, представляющие собой расстояния от вершины источника до вер-

шины i. Необходимо найти минимальные значения p_i. При этом не имеет смысла разделять задачи нахождения кратчайщего пути и построения дерева кратчайших путей, так как длина кратчайшего пути из источника в сток совпа-

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

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

(16) P = ∑ p_i à max

(17) p_j - p_{i <=} h_k, k = 1,..m;

(18) p_{j –} не ограничены, ps = 0.

Здесь n - число вершин, m - число дуг.

ПОСТАНОВКА ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ

Мы уже дали ранее определение потока на ориентированном графе со

взвешенными дугами (то есть в сети). Поток наибольшей величины называет ся максимальным потоком.Определение потока и дает ограничения задачи ли-

нейного программирования, которая соответствует задаче отыскания макси-

мального потока в сети. С учетом целевой функции математическая модель

выглядит так:

P = ∑ f(s, k) à max (s –источник)

(s,k) ∈ U

∑ f(k, i) = ∑f(i,l), I ∈ X,

(k,i) ∈U (I,l) ∈U

f(i, j) >= 0 ∀ (i, j) ∈ U.