Задачи о потоках в сетях

Это руководство было изначально предоставлено Арпитом Бхатией (Arpit Bhatia).

В теории графов сеть потоков (также известная как транспортная сеть) представляет собой ориентированный граф, в котором каждое ребро имеет пропускную способность и принимает поток. Величина потока через ребро не может превышать его пропускную способность.

Часто в исследовании операций ориентированный граф называют сетью, вершины — узлами, а ребра — дугами.

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

С помощью сети можно моделировать трафик в компьютерной сети, циркуляцию со спросом, движение жидкости в трубах, движение токов в электрической цепи или иную подобную систему, в которой что-либо перемещается по сети узлов.

Для этого руководства требуются следующие пакеты.

using JuMP
import HiGHS

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

Предположим, что каждой дуге графа назначена скалярная стоимость и что стоимость прямого пути определяется как сумма стоимостей его дуг.

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

где равно , если — это начальный узел, , если — это конечный узел, и в остальных случаях.

G = [
    0 100 30 0 0
    0 0 20 0 0
    0 0 0 10 60
    0 15 0 0 50
    0 0 0 0 0
]
n = size(G)[1]
b = [1, -1, 0, 0, 0]
shortest_path = Model(HiGHS.Optimizer)
set_silent(shortest_path)
@variable(shortest_path, x[1:n, 1:n], Bin)
# Дуги с нулевой стоимостью не являются частью пути, так как они не существуют.
@constraint(shortest_path, [i = 1:n, j = 1:n; G[i, j] == 0], x[i, j] == 0)
# Ограничение сохранения потока
@constraint(shortest_path, [i = 1:n], sum(x[i, :]) - sum(x[:, i]) == b[i],)
@objective(shortest_path, Min, sum(G .* x))
optimize!(shortest_path)
@assert is_solved_and_feasible(shortest_path)
objective_value(shortest_path)

55.0

value.(x)

5×5 Matrix{Float64}:
 0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0
 0.0  1.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0

Задача о присваивании

Предположим, что есть человек и предметов и их нужно сопоставить по принципу «один к одному». Для человека предмет имеет ценность , и нужно присвоить предметы людям так, чтобы общая ценность была максимальной.

Также установлено ограничение, согласно которому человеку предмет может быть присвоен только в том случае, если принадлежит заданному множеству пар .

С математической точки зрения нужно найти множество пар «человек — предмет» из такое, чтобы предметы не повторялись, а общая ценность была максимальной.

G = [
    6 4 5 0
    0 3 6 0
    5 0 4 3
    7 5 5 5
]
n = size(G)[1]
assignment = Model(HiGHS.Optimizer)
set_silent(assignment)
@variable(assignment, y[1:n, 1:n], Bin)
# Одному человеку можно присвоить только один предмет.
@constraint(assignment, [i = 1:n], sum(y[:, i]) == 1)
# Один предмет может быть присвоен только одному человеку.
@constraint(assignment, [j = 1:n], sum(y[j, :]) == 1)
@objective(assignment, Max, sum(G .* y))
optimize!(assignment)
@assert is_solved_and_feasible(assignment)
objective_value(assignment)

20.0

value.(y)

4×4 Matrix{Float64}:
 -0.0  1.0  -0.0   0.0
  0.0  0.0   1.0   0.0
  1.0  0.0   0.0  -0.0
 -0.0  0.0   0.0   1.0

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

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

Цель состоит в том, чтобы обеспечить как можно больший поток из в с соблюдением ограничений пропускной способности.

G = [
    0 3 2 2 0 0 0 0
    0 0 0 0 5 1 0 0
    0 0 0 0 1 3 1 0
    0 0 0 0 0 1 0 0
    0 0 0 0 0 0 0 4
    0 0 0 0 0 0 0 2
    0 0 0 0 0 0 0 4
    0 0 0 0 0 0 0 0
]
n = size(G)[1]
max_flow = Model(HiGHS.Optimizer)
@variable(max_flow, f[1:n, 1:n] >= 0)
# Ограничения пропускной способности
@constraint(max_flow, [i = 1:n, j = 1:n], f[i, j] <= G[i, j])
# Ограничения сохранения потока
@constraint(max_flow, [i = 1:n; i != 1 && i != 8], sum(f[i, :]) == sum(f[:, i]))
@objective(max_flow, Max, sum(f[1, :]))
optimize!(max_flow)
@assert is_solved_and_feasible(max_flow)
objective_value(max_flow)

6.0

value.(f)

8×8 Matrix{Float64}:
 -0.0   3.0   2.0  1.0  -0.0  -0.0  -0.0  -0.0
  0.0   0.0   0.0  0.0   2.0   1.0   0.0   0.0
  0.0   0.0   0.0  0.0   1.0  -0.0   1.0   0.0
 -0.0  -0.0  -0.0  0.0  -0.0   1.0  -0.0  -0.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   3.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   2.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   1.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   0.0