Неправильное указание чего-то в puLP в проблеме торговли товарами (смешанное целочисленное программирование)

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

Допустим, у нас есть три человека с разным количеством каких-то товаров. В настоящее время у них есть 10, 0 и 50 единиц соответственно. Им НУЖНЫ 15, 0 и 46 единиц соответственно, и я пытаюсь использовать puLP, чтобы найти оптимальные переводы между людьми, чтобы минимизировать неудовлетворенные потребности (НЕОБХОДИМО - ПОСТАВКА ПОСЛЕ ПЕРЕРАСПРЕДЕЛЕНИЯ) для всех трех человек.

Тривиальным решением здесь может быть то, что человек 3 может дать человеку 1 всего 4 единицы, так что запасы после перераспределения станут 14, 0, 46, и теперь у человека 1 есть только одна единица неудовлетворенной потребности (они хотят 15 единиц).

Когда я запускаю следующий код puLP, я получаю результат: человек 1 должен дать человеку 2 10 единиц, а человек 3 должен дать человеку 1 50 единиц.

Ясно, что я делаю что-то не так, не могли бы вы указать на мою ошибку?

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

Спасибо!

from pulp import *
import pandas as pd


# Creates a list of the unique people
people = ['1','2','3']

# Creates a dictionary for the number of units of units currently in supply
current = {
    '1': 10,
    '2': 0,
    '3': 50
}

# Creates a dictionary for the number of units needed
need = {
    '1': 15,
    '2': 0,
    '3': 46
}


# Creates the prob variable to contain the problem data
prob = LpProblem("Goods redistribution problem", LpMinimize)

# Creates a list of tuples containing all the possible trades
Routes = [(s,t) for s in people for t in people]

# Remove any tuples that are self trades
Routes = [element for element in Routes if (element[0] != element[1])]


# A dictionary called route_vars is created to contain the referenced variables (the routes)
# Make sure there isn't a route to itself
route_vars = {
'1': {'2': LpVariable("1_2",0,None,LpInteger), '3': LpVariable("1_3",0,None,LpInteger)},
'2': {'1': LpVariable("2_1",0,None,LpInteger), '3': LpVariable("2_3",0,None,LpInteger)},
'3': {'1': LpVariable("3_1",0,None,LpInteger), '2': LpVariable("3_2",0,None,LpInteger)}
}


# The objective function is added to prob first
#prob += lpSum([(need[t] - (current[s] + route_vars[t][s])) for (s,t) in Routes]), "Sum of unmet need after trading"
prob += (need['1'] - (current['1'] + route_vars['2']['1'] + route_vars['3']['1'])) \
    + (need['2'] - (current['2'] + route_vars['1']['2'] + route_vars['3']['2'])) \
    + (need['3'] - (current['3'] + route_vars['1']['3'] + route_vars['2']['3'])), "Sum of unmet need after trading"


# The amount each source trades cannot exceed the amount they currently have
prob += (route_vars['1']['2'] + route_vars['1']['3']) <= current['1'], f"Can't trade more than current inventory for person 1"
prob += (route_vars['2']['1'] + route_vars['2']['3']) <= current['2'], f"Can't trade more than current inventory for person 2"
prob += (route_vars['3']['1'] + route_vars['3']['2']) <= current['3'], f"Can't trade more than current inventory for person 3"

prob.solve()

pd.Series({v: int(v.varValue) for v in prob.variables()})

python optimization mixed-integer-programming pulp
person Slyron    schedule 26.08.2019    source источник
comment
Проблема, которую я вижу, - это ваши ограничения. У вас есть отдельные ограничения, в которых говорится, что человек 1 не может дать человеку 2 больше, чем его первоначальное владение, а человек 1 не может дать 3 больше, чем его первоначальное владение, поэтому я думаю, что вы хотите, чтобы сумма всех сделок лица 1 не могла превышать их первоначальное владение. держа. Другими словами, у вас должно быть 3 ограничения, а не 6 отдельных. Вам также необходимо решить, можете ли вы разрешить сделки с множеством надежд - человек 1 дает человеку 2, который дает человеку 3 и т. Д.   -  person kabdulla    schedule 27.08.2019
comment
Спасибо @kabdulla, я только что отредактировал свой вопрос. Не могли бы вы еще раз взглянуть? Новый ответ отличается, но кажется неправильным. Проблема в сделках с множеством надежд?   -  person Slyron    schedule 27.08.2019
comment
Ваш объект obj. Также выглядит не так. Он учитывает только единицы, полученные от других, а не потерю единиц, переданных другим. Я бы рекомендовал избегать этого жесткого стиля кодирования и вместо этого использовать понимание списка для создания ваших списков маршрутов от человека 1 и к человеку 1 для суммирования.   -  person kabdulla    schedule 27.08.2019

Ответы (1)


arrow_upward
0
arrow_downward

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

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

total = {
'1': 50,
'2': 10,
'3': 0 }

Целевая функция по существу дает нам lpSum(need[p] - total[p] for p in people), что означает

15 - 50 = -35
0 - 10 = -10
46 - 0 = 46

Итак, у нас есть

(-35) + (-10) + 46 = 1

Чего не хватает, так это члена, который нивелирует отрицательный вклад затоваривания в целевой функции, например:

lpSum(need[p] - total[p] + overstock[p] for p in people )

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

Проверьте это и дайте мне знать, если вам нужны разъяснения по чему-либо

 from pulp import *
import pandas as pd

# Creates a list of the unique people
people = ['1','2','3']

# Creates a dictionary for the number of units of units currently in supply
current = {
    '1': 10,
    '2': 0,
    '3': 50
}

# Creates a dictionary for the number of units needed
need = {
    '1': 15,
    '2': 0,
    '3': 46
}

# Creates the prob variable to contain the problem data
prob = LpProblem("Goods redistribution problem", LpMinimize)


overstock = LpVariable.dicts("overstock",
                             [p for p in people],
                             lowBound = 0)

route_vars = LpVariable.dicts("Trades",
                     [(i,j) for i in people for j in people if i != j],
                     lowBound = 0, 
                     cat = "Integer")

total = LpVariable.dicts("Total", 
                   [p for p in people],
                   lowBound = 0)

#obj
prob += lpSum(need[p] - total[p] + overstock[p] for p in people )

#s,t
for p in people:
    prob += total[p] - need[p] <= overstock[p] , "overstock definition for person" + str(p)

for p in people:
    prob += lpSum(route_vars[(p,j)] for j in people if p != j) + current[p] - lpSum(route_vars[(i,p)] for i in people if i != p) == total[p], "definition of total stock for person" + str(p)

for i in people:
    prob += lpSum(route_vars[(i,j)] for j in people if i != j) <= current[i] , "trading constraint person" + str(i)

prob.solve()

#Print optimal values in console
for v in prob.variables():
    print(v.name, " = ",  v.varValue)

#Print optimised objective function in console
print("Unmet supply:", prob.objective.value())

#Print solution status in console
print("Status:", LpStatus[prob.status])
person Billal Naseem    schedule 17.10.2019