Поток минимальной стоимости

Рассмотрим задачу определения потока, заданной величины от s к t в сети , в которой каждая дуга (x_i,x_j) характеризуется пропускной способностью и неотрицательной стоимостью пересылки единичного потока из x_i в x_j вдоль дуги (x_i,x_j).

Если , где - величина максимального потока в сети G от s к t, то решения нет. Если же , то может быть определено несколько различных потоков величины от s к t.

Математическая модель задачи выглядит следующим образом: минимизировать где - поток по дуге (x_i,x_j) при ограничениях:

2. Для начальной вершины : - уравнение истока;

3. Для конечной вершины : - уравнение стока;

4. Для любой другой вершины x_j≠s, t: - условие сохранения потока.

Если µ* - кратчайший путь от s к t в сети G=(V,E,D), c_min(µ*) – минимальная из пропускных способностей дуг, входящих в путь µ*, и если , то задача имеет тривиальное решение – весь поток направляется вдоль пути µ*.

Общее решение задачи о потоке минимальной стоимости строится следующим образом. Сначала находится кратчайший путь µ* от s к t и величина максимально возможного потока вдоль этого пути. Если окажется, что , то задача решена. В противном случае сеть модифицируют специальным образом. Затем опять находят кратчайший путь от s к t и максимально возможный поток вдоль этого пути в модифицированной сети. Процедуры модификации сети и нахождения пути в ней повторяются до тех пор, пока либо нужное количество не будет переправлено, либо возникнет сеть, в которой нет пути от s к t, что означает отсутствие решения у исходной задачи.

Модифицированная относительно данного потока сеть строится следующим образом:

1. , т.е. число и набор вершин в модифицированной сети не изменяется.

2. , где F – некоторое множество фиктивных дуг. Т.о., после модификации число дуг сети увеличивается.

3. Если и , то (x_i,x_j) включается в множество F. При этом полагается , . Этот пункт применяется только к дугам, по которым проходит поток , относительно которого происходит модификация сети.

4. Для всех ненасыщенных дуг, где нет противоположного потока, в том числе и для ненасыщенных дуг с потоком, относительно которого происходит модификация сети, т.е. для , и полагают , .