Задача о перевозках

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

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

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

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

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

using JuMP
import DelimitedFiles
import HiGHS

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

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

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

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

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

Данные

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

open(joinpath(@__DIR__, "transp.txt"), "w") do io
    print(
        io,
        """
             . FRA  DET LAN WIN  STL  FRE  LAF SUPPLY
          GARY  39   14  11  14   16   82    8   1400
          CLEV  27    .  12   .   26   95   17   2600
          PITT  24   14  17  13   28   99   20   2900
        DEMAND 900 1200 600 400 1700 1100 1000      0
        """,
    )
    return
end

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

Мы не стали учитывать ребра, которых нет в формулировке, но можно внести небольшое изменение и зафиксировать значение при .

Сначала необходимо преобразовать этот текстовый формат в подходящую структуру данных Julia, с которой можно будет работать. Так как данные представляют собой таблицу с именованными строками и столбцами, одним из вариантов является объект JuMP Containers.DenseAxisArray:

function read_data(filename::String)
    data = DelimitedFiles.readdlm(filename)
    rows, columns = data[2:end, 1], data[1, 2:end]
    return Containers.DenseAxisArray(data[2:end, 2:end], rows, columns)
end

data = read_data(joinpath(@__DIR__, "transp.txt"))

2-dimensional DenseAxisArray{Any,2,...} with index sets:
    Dimension 1, Any["GARY", "CLEV", "PITT", "DEMAND"]
    Dimension 2, Any["FRA", "DET", "LAN", "WIN", "STL", "FRE", "LAF", "SUPPLY"]
And data, a 4×8 Matrix{Any}:
  39    14      11   14       16    82     8  1400
  27      "."   12     "."    26    95    17  2600
  24    14      17   13       28    99    20  2900
 900  1200     600  400     1700  1100  1000     0

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

Согласно рекомендациям в разделе Design patterns for larger models, мы записываем нашу модель JuMP как функцию, которая принимает входные данные. В этом примере выходные данные выводятся в stdout:

function solve_transportation_problem(data::Containers.DenseAxisArray)
    # Получаем множество значений предложения и спроса
    O, D = axes(data)
    # Удаляем узлы SUPPLY и DEMAND из множеств
    O, D = setdiff(O, ["DEMAND"]), setdiff(D, ["SUPPLY"])
    model = Model(HiGHS.Optimizer)
    set_silent(model)
    @variable(model, x[o in O, d in D] >= 0)
    # Удаляем ребра со стоимостью «.», присваивая им фиксированное значение 0,0.
    for o in O, d in D
        if data[o, d] == "."
            fix(x[o, d], 0.0; force = true)
        end
    end
    @objective(
        model,
        Min,
        sum(data[o, d] * x[o, d] for o in O, d in D if data[o, d] != "."),
    )
    @constraint(model, [o in O], sum(x[o, :]) <= data[o, "SUPPLY"])
    @constraint(model, [d in D], sum(x[:, d]) == data["DEMAND", d])
    optimize!(model)
    @assert is_solved_and_feasible(model)
    # Выводим решение в структурированном формате входных данных
    print("    ", join(lpad.(D, 7, ' ')))
    for o in O
        print("\n", o)
        for d in D
            if isapprox(value(x[o, d]), 0.0; atol = 1e-6)
                print("      .")
            else
                print(" ", lpad(value(x[o, d]), 6, ' '))
            end
        end
    end
    return
end

solve_transportation_problem (generic function with 1 method)

Решение

Давайте получим и проверим решение:

solve_transportation_problem(data)

        FRA    DET    LAN    WIN    STL    FRE    LAF
GARY      .      .      .      .  300.0 1100.0      .
CLEV      .      .  600.0      . 1000.0      . 1000.0
PITT  900.0 1200.0      .  400.0  400.0      .      .