商品交易中纸浆的误判问题（混合整数规划）

Question

我很难理解在玩具优化问题（混合整数规划）中我做错了什么。你知道吗

假设我们有三个人有不同数量的好人。它们目前分别有10个、0个和50个单位。他们分别需要15个，0个和46个单位，我正试图用纸浆来找出最佳的人员之间的转移，以尽量减少未满足的需求（需要-重新分配后的供应）为所有三个人。你知道吗

这里一个简单的解决方案是，第3个人可以给第1个人总共4个单位，这样重新分配后的供给就变成了14、0、46，而现在第1个人只有一个单位的未满足需求（他们想要15个单位）。你知道吗

当我运行下面的代码时，我得到的结果是，person1应该给person2 10个单位，person3应该给person1 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()})

Answer 1

问题在于目标函数，在这种情况下，目标函数的值总是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 )

考虑到多希望交易的kabdulla's评论，并添加决策变量来跟踪积压和总计（严格地说是为了方便和可读性），可以建立一个正确的模型。你知道吗

检查一下，如果你需要任何澄清，请告诉我

 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])