Как правильно реализовать целевую функцию минимизации затрат в Gurobi? - PullRequest
Новая
       16

Как правильно реализовать целевую функцию минимизации затрат в Gurobi?

0 голосов
/ 25 марта 2019

С учетом транспортных расходов на одну единицу доставки для супермаркета из трех распределительных центров в десять отдельных магазинов.

Примечание. Пожалуйста, посмотрите в разделе #data моего кода, чтобы увидеть данные, которые мне не разрешено публиковать в виде фотографий. ТАКЖЕ обратите внимание, хотя мои расходы являются вектором с 30 записями. Каждый распределительный центр может получить доступ только к 10 затратам. Таким образом, затраты DC1 = записи 1-10, затраты DC2 = записи 11-20 и т. Д.

Я хочу минимизировать транспортные расходы в зависимости от потребности каждого из десяти магазинов (в единицах доставки).

Это может быть сделано осмотром. Минимальная стоимость составляет $ 150313. Проблема в том, чтобы реализовать решение с помощью Python и Gurobi и получить тот же результат.

То, что я пробовал, - это пока неаккуратная модель проблемы в Гуроби. Я не уверен, как правильно индексировать и перебирать мои наборы, необходимые для получения результата.

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

Хотя код "работает". Если я перейду к максимизации, я получу неограниченную проблему. Поэтому я чувствую, что определенно не вызываю правильные данные / итерации по сетам.

Мое решение пока довольно маленькое, поэтому я чувствую, что могу отформатировать его в вопрос и прокомментировать по пути. 

from gurobipy import *

#Sets
Distro = ["DC0","DC1","DC2"]
Stores = ["S0", "S1", "S2", "S3", "S4", "S5", "S6", "S7", "S8", "S9"]
D = range(len(Distro))
S = range(len(Stores))

Здесь я определяю свои наборы распределительных центров и набор магазинов. Я не уверен, где и как точно определить переменные итерации D и S, чтобы получить правильный ответ. 


#Data
Demand  = [10,16,11,8,8,18,11,20,13,12]
Costs = [1992,2666,977,1761,2933,1387,2307,1814,706,1162,
           2471,2023,3096,2103,712,2304,1440,2180,2925,2432,
           1642,2058,1533,1102,1970,908,1372,1317,1341,776]

Просто блок моих соответствующих данных. Я не уверен, что мои данные о расходах должны быть 3 отдельными наборами, учитывая, что каждый распределительный центр имеет доступ только к 10 затратам, а не к 30. Или если есть способ сохранить мои затраты как один набор, но убедитесь, что каждый центр может иметь доступ только к затратам отношение к себе я бы не знал. 

m = Model("WonderMarket")
#Variables
X = {}
for d in D:
    for s in S:
        X[d,s] = m.addVar()

Объявление моей целевой переменной. Опять же, я слепо повторяю в этой точке, чтобы произвести что-то, что работает. Я никогда не программировал раньше. Но я учусь и вкладываю в этот вопрос как можно больше мыслей. 

#set objective
m.setObjective(quicksum(Costs[s] * X[d, s] * Demand[s] for d in D for s in S), GRB.MINIMIZE)

Моя целевая функция - попытаться умножить стоимость каждой доставки из центра в магазин в зависимости от спроса в магазине, а затем сделать это наименьшее возможное значение. У меня пока нет ненулевого ограничения. Мне понадобится в конце концов ?! Но сейчас у меня есть рыба побольше. 

m.optimize()

Я создаю модель из 0 строк, 30 столбцов с 0 ненулевыми записями, которая дает мне решение 0. Мне нужно настроить программу так, чтобы я мог получить значение, которое можно легко вычислить вручную. Я полагаю, что проблема заключается в моем общем объявлении переменных и низком знании итерации и общих проблем "что происходит, куда". Много размышлений только для учебного упражнения!

Цените любого, кто прочитал все до конца. Спасибо за любые советы или помощь заранее.

1 Ответ

1 голос
/ 26 марта 2019

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

Несколько комментариев:

Если вам не нужны имена для центров распределения имагазины, вы можете определить их следующим образом: 

D = 3
S = 10
Distro = range(D)
Stores = range(S)

Вы можете определить затраты в виде двумерного массива, например: 

Costs = [[1992,2666,977,1761,2933,1387,2307,1814,706,1162],
       [2471,2023,3096,2103,712,2304,1440,2180,2925,2432],
       [1642,2058,1533,1102,1970,908,1372,1317,1341,776]]

Тогда стоимость транспортировки из распределительного центра d для хранения s хранятся в Costs[d][s].

Вы можете добавить все переменные одновременно, и я предполагаю, что вы хотите, чтобы они были двоичными: 

X = m.addVars(D, S, vtype=GRB.BINARY)

(или используйте Distro и Stores вместо D и S, если вам нужно использовать имена).

Тогда ваше определение целевой функции становится следующим: 

m.setObjective(quicksum(Costs[d][s] * X[d, s] * Demand[s] for d in Distro for s in Stores), GRB.MINIMIZE)

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

Вам нужны ограничения, гарантирующие, что магазинытребования фактически удовлетворены.Для этого достаточно убедиться, что каждый магазин доставляется из одного распределительного центра, то есть, что для каждого s один X[d, s] равен 1. 

m.addConstrs(quicksum(X[d, s] for d in Distro) == 1 for s in Stores)

Когда я оптимизирую это, я действительно получаюоптимальное решение со значением 150313.

...