Задача о консервном заводе

Это руководство было изначально предоставлено Луисом Луангкесорном (Louis Luangkesorn).

В этом руководстве решается задача о консервном заводе из книги Данцига (Dantzig) Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963. Этот класс задач известен как задачи о перевозках.

Цель данного руководства — продемонстрировать использование данных JSON при формулировании модели JuMP.

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

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

using JuMP
import HiGHS
import JSON
import Test

Формулировка

Задача о консервном заводе предполагает оптимизацию отгрузки ящиков с консервами с заводов-производителей на рынки .

Каждый завод имеет производительность , а каждый рынок — спрос . Стоимость доставки одного ящика с консервами с завода на рынок составляет .

Нам нужно найти план распределения , то есть количество ящиков с консервами для отправки с завода на рынок при и , с минимальными затратами на доставку. Задачу можно сформулировать в виде следующей линейной программы:

Данные

Главной целью руководства является демонстрация загрузки данных из JSON.

Для простоты данные жестко заданы ниже. Однако, если бы данные были доступны в виде файла .json, для их считывания можно было бы использовать data = JSON.parsefile(filename).

data = JSON.parse("""
{
    "plants": {
        "Seattle": {"capacity": 350},
        "San-Diego": {"capacity": 600}
    },
    "markets": {
        "New-York": {"demand": 300},
        "Chicago": {"demand": 300},
        "Topeka": {"demand": 300}
    },
    "distances": {
        "Seattle => New-York": 2.5,
        "Seattle => Chicago": 1.7,
        "Seattle => Topeka": 1.8,
        "San-Diego => New-York": 2.5,
        "San-Diego => Chicago": 1.8,
        "San-Diego => Topeka": 1.4
    }
}
""")

Dict{String, Any} with 3 entries:
  "plants"    => Dict{String, Any}("Seattle"=>Dict{String, Any}("capacity"=>350…
  "distances" => Dict{String, Any}("San-Diego => New-York"=>2.5, "Seattle => To…
  "markets"   => Dict{String, Any}("Chicago"=>Dict{String, Any}("demand"=>300),…

Создаем множество заводов:

P = keys(data["plants"])

KeySet for a Dict{String, Any} with 2 entries. Keys:
  "Seattle"
  "San-Diego"

Создаем множество рынков:

M = keys(data["markets"])

KeySet for a Dict{String, Any} with 3 entries. Keys:
  "Chicago"
  "Topeka"
  "New-York"

Нам также нужна функция для расчета расстояния от завода до рынка:

distance(p::String, m::String) = data["distances"]["$(p) => $(m)"]

distance (generic function with 1 method)

Формулировка на языке JuMP

Теперь мы готовы преобразовать математическую формулировку в модель JuMP.

Сначала создадим модель JuMP. Так как программа линейная, мы используем оптимизатор HiGHS:

model = Model(HiGHS.Optimizer)

A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Наши переменные решения индексируются по множеству заводов и рынков:

@variable(model, x[P, M] >= 0)

2-dimensional DenseAxisArray{VariableRef,2,...} with index sets:
    Dimension 1, ["Seattle", "San-Diego"]
    Dimension 2, ["Chicago", "Topeka", "New-York"]
And data, a 2×3 Matrix{VariableRef}:
 x[Seattle,Chicago]    x[Seattle,Topeka]    x[Seattle,New-York]
 x[San-Diego,Chicago]  x[San-Diego,Topeka]  x[San-Diego,New-York]

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

@constraint(model, [p in P], sum(x[p, :]) <= data["plants"][p]["capacity"])

1-dimensional DenseAxisArray{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, ScalarShape},1,...} with index sets:
    Dimension 1, ["Seattle", "San-Diego"]
And data, a 2-element Vector{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, ScalarShape}}:
 x[Seattle,Chicago] + x[Seattle,Topeka] + x[Seattle,New-York] ≤ 350
 x[San-Diego,Chicago] + x[San-Diego,Topeka] + x[San-Diego,New-York] ≤ 600

А каждый рынок должен получать не менее своего спроса:

@constraint(model, [m in M], sum(x[:, m]) >= data["markets"][m]["demand"])

1-dimensional DenseAxisArray{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, ScalarShape},1,...} with index sets:
    Dimension 1, ["Chicago", "Topeka", "New-York"]
And data, a 3-element Vector{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, ScalarShape}}:
 x[Seattle,Chicago] + x[San-Diego,Chicago] ≥ 300
 x[Seattle,Topeka] + x[San-Diego,Topeka] ≥ 300
 x[Seattle,New-York] + x[San-Diego,New-York] ≥ 300

Наконец, наша цель — минимизировать расстояние перевозки:

@objective(model, Min, sum(distance(p, m) * x[p, m] for p in P, m in M));

Решение

Давайте выполним оптимизацию и посмотрим на решение:

optimize!(model)
solution_summary(model)

* Solver : HiGHS

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "kHighsModelStatusOptimal"

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : FEASIBLE_POINT
  Objective value    : 1.68000e+03
  Objective bound    : 0.00000e+00
  Relative gap       : Inf
  Dual objective value : 1.68000e+03

* Work counters
  Solve time (sec)   : 2.41995e-04
  Simplex iterations : 3
  Barrier iterations : 0
  Node count         : -1

Каков оптимальный план доставки?

Test.@test is_solved_and_feasible(model)
for p in P, m in M
    println(p, " => ", m, ": ", value(x[p, m]))
end

Seattle => Chicago: 300.0
Seattle => Topeka: 0.0
Seattle => New-York: 0.0
San-Diego => Chicago: 0.0
San-Diego => Topeka: 300.0
San-Diego => New-York: 300.0