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

Классификация задач о потоке приведена на рисунке 18.

Рисунок 18. Классификация задач

Перечислим типы задач:

1.Транспортная задача

Все узлы находятся в двух множествах N₁ и N₂. Дуги соединяют узлы из N₁ с узлами из N₂. Каждая дуга имеет бесконечную пропускную способность, С_ij=oo.

Во всех узлах имеются ненулевые внешние фиксированные потоки b_i<>0.

Сумма внешних потоков b_i равна 0.

2.   Задача о назначениях

Количество складов равно количеству магазинов N₁=N₂.

Все поставки и требования равны 1.

По дуге заданы стоимости, которые связаны с объединением объектов из N₁+N₂.

h{N₁,N₂}

3. Задача о кратчайшем пути

Имеется один исток и 1 сток.

Стоимость дуги равна длине дуги h_k=l_k.

Ищется сумма h_k=min.

Если узел не является  истоком или стоком, то b_i=0.

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

Параметры задачи C_ij,C_k.

Max поток=min разрезу.

5.   Потоки в сетях с выигрышами

Нет условия сохранения потока по дуге

Для каждой дуги задается коэффициент выигрыша. K_ij.

Втекающий поток в узел F_k=fij*Kij

6.Задачи о линейном программировании