Документация Engee

Задача о местоположении предприятия

Это руководство было изначально предоставлено Матье Танно (Mathieu Tanneau) и Алексисом Монтуазоном (Alexis Montoison).

Требуемые пакеты

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

using JuMP
import HiGHS
import LinearAlgebra
import Plots
import Random

Местоположение предприятия с неограниченной производительностью

Описание задачи

Дано следующее:

  • множество клиентов;

  • множество мест, где можно построить предприятие.

Переменные решения. Переменные решения делятся на две категории:

  • Двоичная переменная указывает, построено ли предприятие .

  • Двоичная переменная указывает, привязан ли клиент к предприятию .

Целевая функция. Цель — минимизировать общую стоимость обслуживания всех клиентов. Расходы делятся на две составляющие:

  • Фиксированная стоимость постройки предприятия. В данном примере эта стоимость равна .

  • Стоимость обслуживания клиентов предприятием. В данном примере стоимость обслуживания клиента предприятием представляет собой евклидово расстояние между этими переменными.

Ограничения

  • Каждого клиента может обслуживать одно и только одно предприятие.

  • Чтобы обслуживать клиента, предприятие должно быть открыто.

Формулировка в виде MILP

Задачу можно сформулировать в виде следующей программы MILP:

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

Данные для задачи

Для обеспечения воспроизводимости задается начальное значение для генерирования случайных чисел:

Random.seed!(314)
Random.TaskLocalRNG()

Вот необходимые данные:

# Количество клиентов
m = 12
# Количество местоположений предприятий
n = 5

# Местоположения клиентов
x_c, y_c = rand(m), rand(m)

# Возможные местоположения предприятий
x_f, y_f = rand(n), rand(n)

# Фиксированные затраты
f = ones(n);

# Расстояние
c = zeros(m, n)
for i in 1:m
    for j in 1:n
        c[i, j] = LinearAlgebra.norm([x_c[i] - x_f[j], y_c[i] - y_f[j]], 2)
    end
end

Отобразим данные:

Plots.scatter(
    x_c,
    y_c;
    label = "Clients",
    markershape = :circle,
    markercolor = :blue,
)
Plots.scatter!(
    x_f,
    y_f;
    label = "Facility",
    markershape = :square,
    markercolor = :white,
    markersize = 6,
    markerstrokecolor = :red,
    markerstrokewidth = 2,
)

Реализация в JuMP

Создадим модель JuMP:

model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, y[1:n], Bin);
@variable(model, x[1:m, 1:n], Bin);
# Каждый клиент обслуживается ровно один раз
@constraint(model, client_service[i in 1:m], sum(x[i, j] for j in 1:n) == 1);
# Для обслуживания клиента предприятие должно быть открыто
@constraint(model, open_facility[i in 1:m, j in 1:n], x[i, j] <= y[j]);
@objective(model, Min, f' * y + sum(c .* x));

Решим задачу о местоположении предприятия с неограниченной производительностью с помощью HiGHS:

optimize!(model)
@assert is_solved_and_feasible(model)
println("Optimal value: ", objective_value(model))
Optimal value: 5.7018394545724185

Визуализация решения

Порог 1e-5 гарантирует, что ребра между клиентами и предприятиями проводятся при x[i, j] ≈ 1.

x_is_selected = isapprox.(value.(x), 1; atol = 1e-5);
y_is_selected = isapprox.(value.(y), 1; atol = 1e-5);

p = Plots.scatter(
    x_c,
    y_c;
    markershape = :circle,
    markercolor = :blue,
    label = nothing,
)

Plots.scatter!(
    x_f,
    y_f;
    markershape = :square,
    markercolor = [(y_is_selected[j] ? :red : :white) for j in 1:n],
    markersize = 6,
    markerstrokecolor = :red,
    markerstrokewidth = 2,
    label = nothing,
)

for i in 1:m, j in 1:n
    if x_is_selected[i, j]
        Plots.plot!(
            [x_c[i], x_f[j]],
            [y_c[i], y_f[j]];
            color = :black,
            label = nothing,
        )
    end
end

p

Местоположение предприятия с ограниченной производительностью

Формулировка задачи

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

В частности:

  • Спрос клиента обозначается как .

  • Производительность предприятия обозначается как

В таком случае ограничения производительности записываются так:

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

Следовательно, задачу о местоположении предприятия с ограниченной производительностью можно сформулировать следующим образом:

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

Потребуются новые данные:

# Спрос
a = rand(1:3, m);

# Производительность
q = rand(5:10, n);

Отобразим данные:

Plots.scatter(
    x_c,
    y_c;
    label = nothing,
    markershape = :circle,
    markercolor = :blue,
    markersize = 2 .* (2 .+ a),
)

Plots.scatter!(
    x_f,
    y_f;
    label = nothing,
    markershape = :rect,
    markercolor = :white,
    markersize = q,
    markerstrokecolor = :red,
    markerstrokewidth = 2,
)

Реализация в JuMP

Создадим модель JuMP:

model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, y[1:n], Bin);
@variable(model, x[1:m, 1:n], Bin);
# Каждый клиент обслуживается ровно один раз
@constraint(model, client_service[i in 1:m], sum(x[i, :]) == 1);
# Ограничение производительности
@constraint(model, capacity, x' * a .<= (q .* y));
# Целевая функция
@objective(model, Min, f' * y + sum(c .* x));

Решим задачу:

optimize!(model)
@assert is_solved_and_feasible(model)
println("Optimal value: ", objective_value(model))
Optimal value: 6.1980444155009975

Визуализация решения

Порог 1e-5 гарантирует, что ребра между клиентами и предприятиями проводятся при x[i, j] ≈ 1.

x_is_selected = isapprox.(value.(x), 1; atol = 1e-5);
y_is_selected = isapprox.(value.(y), 1; atol = 1e-5);

Отобразим решение:

p = Plots.scatter(
    x_c,
    y_c;
    label = nothing,
    markershape = :circle,
    markercolor = :blue,
    markersize = 2 .* (2 .+ a),
)

Plots.scatter!(
    x_f,
    y_f;
    label = nothing,
    markershape = :rect,
    markercolor = [(y_is_selected[j] ? :red : :white) for j in 1:n],
    markersize = q,
    markerstrokecolor = :red,
    markerstrokewidth = 2,
)

for i in 1:m, j in 1:n
    if x_is_selected[i, j]
        Plots.plot!(
            [x_c[i], x_f[j]],
            [y_c[i], y_f[j]];
            color = :black,
            label = nothing,
        )
    end
end

p