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

Задача о потоке нескольких видов товаров

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

Это руководство представляет собой реализацию на JuMP модели перевозки нескольких видов товаров, описанной в книге AMPL:[ ]https://ampl.com/resources/the-ampl-book/[A Modeling Language for Mathematical Programming], R. Fourer, D.M. Gay and B.W. Kernighan.

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

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

В этом руководстве используются следующие пакеты.

using JuMP
import DataFrames
import HiGHS
import SQLite
import Tables
import Test

const DBInterface = SQLite.DBInterface
julia
DBInterface
output

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

Задача о потоке нескольких видов товаров представляет собой простое расширение задачи The transportation problem на несколько типов товаров. Если коротко, мы начинаем с формулировки транспортной задачи:

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

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

Данные

Для целей данного руководства в репозитории JuMP есть пример базы данных под названием multi.sqlite.

filename = joinpath(@__DIR__, "multi.sqlite");
julia

Для локального выполнения скачайте файл multi.sqlite и соответствующим образом измените значение filename.

Загрузите базу данных с помощью SQLite.DB:

db = SQLite.DB(filename)
julia
SQLite.DB("/home/docs/julia_docs/JuMP.jl-master/docs/build/tutorials/linear/multi.sqlite")
output

Схему базы данных можно быстро просмотреть с помощью SQLite.tables:

SQLite.tables(db)
julia
5-element Vector{SQLite.DBTable}:
 SQLite.DBTable("locations", Tables.Schema:
 :location  Union{Missing, String}
 :type      Union{Missing, String})
 SQLite.DBTable("products", Tables.Schema:
 :product  Union{Missing, String})
 SQLite.DBTable("supply", Tables.Schema:
 :origin   Union{Missing, String}
 :product  Union{Missing, String}
 :supply   Union{Missing, Float64})
 SQLite.DBTable("demand", Tables.Schema:
 :destination  Union{Missing, String}
 :product      Union{Missing, String}
 :demand       Union{Missing, Float64})
 SQLite.DBTable("cost", Tables.Schema:
 :origin       Union{Missing, String}
 :destination  Union{Missing, String}
 :product      Union{Missing, String}
 :cost         Union{Missing, Float64})
output

Взаимодействие с базой данных осуществляется путем выполнения запросов и передачи результатов в соответствующую таблицу. Примером может служить DataFrame:

DBInterface.execute(db, "SELECT * FROM locations") |> DataFrames.DataFrame
julia

10×2 DataFrame

Row location type

String

String

1

GARY

origin

2

CLEV

origin

3

PITT

origin

4

FRA

destination

5

DET

destination

6

LAN

destination

7

WIN

destination

8

STL

destination

9

FRE

destination

10

LAF

destination

Однако поддерживаются таблицы и других типов, например Tables.rowtable:

DBInterface.execute(db, "SELECT * FROM locations") |> Tables.rowtable
julia
10-element Vector{@NamedTuple{location::String, type::String}}:
 (location = "GARY", type = "origin")
 (location = "CLEV", type = "origin")
 (location = "PITT", type = "origin")
 (location = "FRA", type = "destination")
 (location = "DET", type = "destination")
 (location = "LAN", type = "destination")
 (location = "WIN", type = "destination")
 (location = "STL", type = "destination")
 (location = "FRE", type = "destination")
 (location = "LAF", type = "destination")
output

rowtable — это вектор Vector кортежей NamedTuple.

Можно создавать и более сложные запросы SQL:

origins =
    DBInterface.execute(
        db,
        "SELECT location FROM locations WHERE type = \"origin\"",
    ) |> Tables.rowtable
julia
3-element Vector{@NamedTuple{location::String}}:
 (location = "GARY",)
 (location = "CLEV",)
 (location = "PITT",)
output

Но в нашем случае достаточно списка строк:

origins = map(y -> y.location, origins)
julia
3-element Vector{String}:
 "GARY"
 "CLEV"
 "PITT"
output

Эти две операции можно объединить, чтобы получить список пунктов назначения:

destinations =
    DBInterface.execute(
        db,
        "SELECT location FROM locations WHERE type = \"destination\"",
    ) |>
    Tables.rowtable |>
    x -> map(y -> y.location, x)
julia
7-element Vector{String}:
 "FRA"
 "DET"
 "LAN"
 "WIN"
 "STL"
 "FRE"
 "LAF"
output

И список товаров из таблицы products:

products =
    DBInterface.execute(db, "SELECT product FROM products") |>
    Tables.rowtable |>
    x -> map(y -> y.product, x)
julia
3-element Vector{String}:
 "bands"
 "coils"
 "plate"
output

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

Начнем с создания модели и переменных решения:

model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, x[origins, destinations, products] >= 0)
julia
3-dimensional DenseAxisArray{VariableRef,3,...} with index sets:
    Dimension 1, ["GARY", "CLEV", "PITT"]
    Dimension 2, ["FRA", "DET", "LAN", "WIN", "STL", "FRE", "LAF"]
    Dimension 3, ["bands", "coils", "plate"]
And data, a 3×7×3 Array{VariableRef, 3}:
[:, :, "bands"] =
 x[GARY,FRA,bands]  x[GARY,DET,bands]  …  x[GARY,LAF,bands]
 x[CLEV,FRA,bands]  x[CLEV,DET,bands]     x[CLEV,LAF,bands]
 x[PITT,FRA,bands]  x[PITT,DET,bands]     x[PITT,LAF,bands]

[:, :, "coils"] =
 x[GARY,FRA,coils]  x[GARY,DET,coils]  …  x[GARY,LAF,coils]
 x[CLEV,FRA,coils]  x[CLEV,DET,coils]     x[CLEV,LAF,coils]
 x[PITT,FRA,coils]  x[PITT,DET,coils]     x[PITT,LAF,coils]

[:, :, "plate"] =
 x[GARY,FRA,plate]  x[GARY,DET,plate]  …  x[GARY,LAF,plate]
 x[CLEV,FRA,plate]  x[CLEV,DET,plate]     x[CLEV,LAF,plate]
 x[PITT,FRA,plate]  x[PITT,DET,plate]     x[PITT,LAF,plate]
output

Одним из подходов при работе с базами данных является извлечение всех данных в структуру данных Julia. Например, давайте перенесем таблицу затрат в DataFrame, а затем построим целевую функцию путем перебора строк в DataFrame:

cost = DBInterface.execute(db, "SELECT * FROM cost") |> DataFrames.DataFrame
@objective(
    model,
    Max,
    sum(r.cost * x[r.origin, r.destination, r.product] for r in eachrow(cost)),
);
julia

Если мы не хотим использовать DataFrame, можно воспользоваться Tables.rowtable:

supply = DBInterface.execute(db, "SELECT * FROM supply") |> Tables.rowtable
for r in supply
    @constraint(model, sum(x[r.origin, :, r.product]) <= r.supply)
end
julia

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

demand = DBInterface.execute(db, "SELECT * FROM demand")
for r in Tables.rows(demand)
    @constraint(model, sum(x[:, r.destination, r.product]) == r.demand)
end
julia

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

Запросы SQLite могут быть сколь угодно сложными. Например, вот запрос для формирования всех возможных пар «пункт отправления — пункт назначения»:

od_pairs = DBInterface.execute(
    db,
    """
    SELECT a.location as 'origin',
           b.location as 'destination'
    FROM locations a
    INNER JOIN locations b
    ON a.type = 'origin' AND b.type = 'destination'
    """,
)
julia
SQLite.Query{false}(SQLite.Stmt(SQLite.DB("/home/docs/julia_docs/JuMP.jl-master/docs/build/tutorials/linear/multi.sqlite"), Base.RefValue{Ptr{SQLite.C.sqlite3_stmt}}(Ptr{SQLite.C.sqlite3_stmt} @0x0000000035d272d8), Dict{Int64, Any}()), Base.RefValue{Int32}(100), [:origin, :destination], Type[Union{Missing, String}, Union{Missing, String}], Dict(:origin => 1, :destination => 2), Base.RefValue{Int64}(0))
output

При этом вводится ограничение на отправку не более чем 625 единиц между каждой парой:

for r in Tables.rows(od_pairs)
    @constraint(model, sum(x[r.origin, r.destination, :]) <= 625)
end
julia

Решение

Наконец, можно оптимизировать модель:

optimize!(model)
Test.@test is_solved_and_feasible(model)
solution_summary(model)
julia
* 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    : 2.25700e+05
  Objective bound    : 2.25700e+05
  Relative gap       : Inf
  Dual objective value : 2.25700e+05

* Work counters
  Solve time (sec)   : 8.43287e-04
  Simplex iterations : 54
  Barrier iterations : 0
  Node count         : -1
output

и вывести решение:

begin
    println("         ", join(products, ' '))
    for o in origins, d in destinations
        v = lpad.([round(Int, value(x[o, d, p])) for p in products], 5)
        println(o, " ", d, " ", join(replace.(v, "   0" => "  . "), " "))
    end
end
julia
         bands coils plate
GARY FRA    25   500   100
GARY DET   125    .     50
GARY LAN    .     .     .
GARY WIN    .     .     50
GARY STL   250   300    .
GARY FRE    .     .     .
GARY LAF    .     .     .
CLEV FRA   275    .     .
CLEV DET   100   200    50
CLEV LAN   100    .     .
CLEV WIN    .     .     .
CLEV STL    .    625    .
CLEV FRE   225   400    .
CLEV LAF    .    375   250
PITT FRA    .     .     .
PITT DET    75   550    .
PITT LAN    .    400    .
PITT WIN    75   250    .
PITT STL   400    25   200
PITT FRE    .    450   100
PITT LAF   250   125    .
output