最小资源数量的线性规划解决方案
Linear programming solution for minimum number of resources
我正尝试在 python 中使用 Pulp 使用线性规划来解决这个问题。
我们有芒果包，每个都有不同数量的芒果。
我们应该能够使用最少数量的数据包来满足需求，如果可能的话，可以提供整包。
# Packet Names and the count of mangoes in each packet.
mangoe_packs = {
"pack_1": 2,
"pack_2": 3,
"pack_3": 3,
"pack_4": 2
}
例如，
根据需求我们应该得到正确的数据包。即，如果需求是 2，我们给包 2 个芒果。如果需求量为 5，我们提供 2 和 3 个芒果包。如果您的需求是 2 个，而我们没有 2 个芒果包，我们可以提供 3 个芒果包。在这种情况下，我们将有一个剩余的芒果。我们的目的是在满足需求的同时，让剩余的芒果数量最少。
# Packet Names and the count of mangoes in each packet.
mangoe_packs = {
"pack_1": 2,
"pack_2": 3,
"pack_3": 3,
"pack_4": 2
}
根据以上提供的数据，
If the demand is 2, The solution is pack_2 (can be pack_4 also).
If the demand is 4, The solution is pack_2 + pack_4.
If the demand is 5, The solution is pack_1 + pack_2
我是线性规划的新手，一直卡在这个问题上。尝试了一些解决方案，但它们都不起作用。
我无法想出正确的 objective 函数和约束来解决这个问题。需要帮助。谢谢。
这是我试过的代码。
from pulp import *
prob = LpProblem("MangoPacks", LpMinimize)
# Number of Mangoes in each packet.
mangoe_packs = {
"pack_1": 2,
"pack_2": 3,
"pack_3": 3,
"pack_4": 2
}
# Define demand variable.
demand = LpVariable("Demand", lowBound=2, HighBound=2, cat="Integer")
pack_count = LpVariable.dicts("Packet Count",
((i, j) for i in mangoe_packs.values() for j in ingredients),
lowBound=0,
cat='Integer')
pulp += (
lpSum([
pack_count[(pack)]
for pack, mango_count in mangoe_packs.iteritems()])
)
pulp += lpSum([j], for pack, j in mangoe_packs.iteritems()]) == 350 * 0.05
status = prob.solve()
谢谢。
这是一个最小化剩余芒果总数的简单模型。该模型没有指定可用的确切包装，而是指定了每个尺寸可用的包装数量（这里 5 个尺寸 2 和 15 个尺寸 4）：
from pulp import *
# PROBLEM DATA:
demand = [3, 7, 2, 5, 9, 3, 2, 4, 7, 5] # demand per order
packages = [0, 5, 0, 15] # available packages of different sizes
O = range(len(demand))
P = range(len(packages))
# DECLARE PROBLEM OBJECT:
prob = LpProblem('Mango delivery', LpMinimize)
# VARIABLES
assigned = pulp.LpVariable.dicts('assigned',
((o, p) for o in O for p in P), 0, max(demand), cat='Integer') # number of packages of different sizes per order
supply = LpVariable.dicts('supply', O, 0, max(demand), cat='Integer') # supply per order
remnant = LpVariable.dicts('remnant', O, 0, len(packages)-1, cat='Integer') # extra delivery per order
# OBJECTIVE
prob += lpSum(remnant) # minimize the total extra delivery
# CONSTRAINTS
for o in O:
prob += supply[o] == lpSum([p*assigned[(o, p)] for p in P])
prob += remnant[o] == supply[o] - demand[o]
for p in P:
# don't use more packages than available
prob += packages[p] >= lpSum([assigned[(o, p)] for o in O])
# SOLVE & PRINT RESULTS
prob.solve()
print(LpStatus[prob.status])
print('obj = ' + str(value(prob.objective)))
print('#remnants = ' + str(sum(int(remnant[o].varValue) for o in O)))
print('demand = ' + str(demand))
print('supply = ' + str([int(supply[o].varValue) for o in O]))
print('remnant = ' + str([int(remnant[o].varValue) for o in O]))
如果无法满足需求，则此模型不可行。在这种情况下，另一种选择是最大限度地增加订单数量，并对剩余芒果进行处罚。这是改编后的模型：
from pulp import *
# PROBLEM DATA:
demand = [3, 7, 2, 5, 9, 3, 2, 4, 7, 5] # demand per order
packages = [0, 5, 0, 5] # available packages of different sizes
O = range(len(demand))
P = range(len(packages))
M = max(demand) # a big enough number
# DECLARE PROBLEM OBJECT:
prob = LpProblem('Mango delivery', LpMaximize)
# VARIABLES
assigned = pulp.LpVariable.dicts('assigned',
((o, p) for o in O for p in P), 0, max(demand), cat='Integer') # number of packages of different sizes per order
supply = LpVariable.dicts('supply', O, 0, max(demand), cat='Integer') # supply per order
remnant = LpVariable.dicts('remnant', O, 0, len(packages)-1, cat='Integer') # extra delivery per order
served = LpVariable.dicts('served', O, cat='Binary') # whether an order is served
diff = LpVariable.dicts('diff', O, -M, len(packages)-1, cat='Integer') # difference between demand and supply
# OBJECTIVE
# primary objective is serve orders, secondary to minimize remnants
prob += 100*lpSum(served) - lpSum(remnant) # maximize served orders with a penalty for remnants
# CONSTRAINTS
for o in O:
prob += supply[o] == lpSum([p*assigned[(o, p)] for p in P])
prob += diff[o] == supply[o] - demand[o]
for p in P:
# don't use more packages than available
prob += packages[p] >= lpSum([assigned[(o, p)] for o in O])
for o in O:
# an order is served if supply >= demand
# formulation adapted from https://cs.stackexchange.com/questions/69531/greater-than-condition-in-integer-linear-program-with-a-binary-variable
prob += M*served[o] >= diff[o] + 1
prob += M*(served[o]-1) <= diff[o]
prob += lpSum([assigned[(o, p)] for p in P]) <= M*served[o]
for o in O:
# if order is served then remnant is supply - demand
# otherwise remnant is zero
prob += remnant[o] >= diff[o]
prob += remnant[o] <= diff[o] + M*(1-served[o])
# SOLVE & PRINT RESULTS
prob.solve()
print(LpStatus[prob.status])
print('obj = ' + str(value(prob.objective)))
print('#served = ' + str(sum(int(served[o].varValue) for o in O)))
print('#remnants = ' + str(sum(int(remnant[o].varValue) for o in O)))
print('served = ' + str([int(served[o].varValue) for o in O]))
print('demand = ' + str(demand))
print('supply = ' + str([int(supply[o].varValue) for o in O]))
print('remnant = ' + str([int(remnant[o].varValue) for o in O]))
这里有一些注意事项：
问题的变数是要不要开包。因此，这些变量为 0 或 1（保持关闭或打开）。
问题的主要objective是尽量减少剩余芒果的数量。或者换句话说：尽量减少打开包装中的芒果总数。这是输入字典的值的总和，但只是那些对应的 LP 变量为 1 的条目的总和。当然，这里可以使用乘法（与 0 或 1）。
如果出现平局，应尽量减少打开包的数量。这只是上述变量的总和。为了将其组合成一个，单个 objective，将第一个 objective 的值乘以数据包总数，然后将第二个 objective 的值添加到它。这样您就可以在竞争解决方案中获得正确的顺序。
唯一的限制是打开的包装中的芒果数量总和至少为输入中给出的数量。
所以这是一个实现：
def optimise(mango_packs, mango_count):
pack_names = list(mango_packs.keys())
prob = LpProblem("MangoPacks", LpMinimize)
# variables: names of the mango packs. We can either open them or not (0/1)
lp_vars = LpVariable.dicts("Open", pack_names, 0, 1, "Integer")
# objective: minimise total count of mangoes in the selected packs (so to
# minimise remnants). In case of a tie, minimise the number of opened packs.
prob += (
lpSum([mango_packs[name]*lp_vars[name] for name in pack_names]) * len(mango_packs)
+ lpSum([lp_vars[name] for name in pack_names])
)
# constraint: the opened packs need to amount to a minimum number of mangoes
prob += lpSum([mango_packs[name]*lp_vars[name] for name in pack_names]) >= mango_count
prob.solve()
为了可视化结果，您可以在上面的函数中添加以下内容：
print("Status:", LpStatus[prob.status])
# Each of the variables is printed with it's resolved optimum value
for i, v in enumerate(prob.variables()):
print("{}? {}".format(v.name, ("no","yes")[int(v.varValue)]))
像这样调用函数：
# Packet Names and the count of mangoes in each packet.
mango_packs = {
"pack_1": 10,
"pack_2": 2,
"pack_3": 2,
"pack_4": 2
}
optimise(mango_packs, 5)
输出（当你添加那些 print 语句时）
Status: Optimal
Open_pack_1? no
Open_pack_2? yes
Open_pack_3? yes
Open_pack_4? yes
看看运行 here -- 给它点时间临时安装pulp模块
我正尝试在 python 中使用 Pulp 使用线性规划来解决这个问题。
我们有芒果包，每个都有不同数量的芒果。 我们应该能够使用最少数量的数据包来满足需求，如果可能的话，可以提供整包。
# Packet Names and the count of mangoes in each packet.
mangoe_packs = {
"pack_1": 2,
"pack_2": 3,
"pack_3": 3,
"pack_4": 2
}
例如，
根据需求我们应该得到正确的数据包。即，如果需求是 2，我们给包 2 个芒果。如果需求量为 5，我们提供 2 和 3 个芒果包。如果您的需求是 2 个，而我们没有 2 个芒果包，我们可以提供 3 个芒果包。在这种情况下，我们将有一个剩余的芒果。我们的目的是在满足需求的同时，让剩余的芒果数量最少。
# Packet Names and the count of mangoes in each packet.
mangoe_packs = {
"pack_1": 2,
"pack_2": 3,
"pack_3": 3,
"pack_4": 2
}
根据以上提供的数据，
If the demand is 2, The solution is pack_2 (can be pack_4 also).
If the demand is 4, The solution is pack_2 + pack_4.
If the demand is 5, The solution is pack_1 + pack_2
我是线性规划的新手，一直卡在这个问题上。尝试了一些解决方案，但它们都不起作用。
我无法想出正确的 objective 函数和约束来解决这个问题。需要帮助。谢谢。
这是我试过的代码。
from pulp import *
prob = LpProblem("MangoPacks", LpMinimize)
# Number of Mangoes in each packet.
mangoe_packs = {
"pack_1": 2,
"pack_2": 3,
"pack_3": 3,
"pack_4": 2
}
# Define demand variable.
demand = LpVariable("Demand", lowBound=2, HighBound=2, cat="Integer")
pack_count = LpVariable.dicts("Packet Count",
((i, j) for i in mangoe_packs.values() for j in ingredients),
lowBound=0,
cat='Integer')
pulp += (
lpSum([
pack_count[(pack)]
for pack, mango_count in mangoe_packs.iteritems()])
)
pulp += lpSum([j], for pack, j in mangoe_packs.iteritems()]) == 350 * 0.05
status = prob.solve()
谢谢。
这是一个最小化剩余芒果总数的简单模型。该模型没有指定可用的确切包装，而是指定了每个尺寸可用的包装数量（这里 5 个尺寸 2 和 15 个尺寸 4）：
from pulp import *
# PROBLEM DATA:
demand = [3, 7, 2, 5, 9, 3, 2, 4, 7, 5] # demand per order
packages = [0, 5, 0, 15] # available packages of different sizes
O = range(len(demand))
P = range(len(packages))
# DECLARE PROBLEM OBJECT:
prob = LpProblem('Mango delivery', LpMinimize)
# VARIABLES
assigned = pulp.LpVariable.dicts('assigned',
((o, p) for o in O for p in P), 0, max(demand), cat='Integer') # number of packages of different sizes per order
supply = LpVariable.dicts('supply', O, 0, max(demand), cat='Integer') # supply per order
remnant = LpVariable.dicts('remnant', O, 0, len(packages)-1, cat='Integer') # extra delivery per order
# OBJECTIVE
prob += lpSum(remnant) # minimize the total extra delivery
# CONSTRAINTS
for o in O:
prob += supply[o] == lpSum([p*assigned[(o, p)] for p in P])
prob += remnant[o] == supply[o] - demand[o]
for p in P:
# don't use more packages than available
prob += packages[p] >= lpSum([assigned[(o, p)] for o in O])
# SOLVE & PRINT RESULTS
prob.solve()
print(LpStatus[prob.status])
print('obj = ' + str(value(prob.objective)))
print('#remnants = ' + str(sum(int(remnant[o].varValue) for o in O)))
print('demand = ' + str(demand))
print('supply = ' + str([int(supply[o].varValue) for o in O]))
print('remnant = ' + str([int(remnant[o].varValue) for o in O]))
如果无法满足需求，则此模型不可行。在这种情况下，另一种选择是最大限度地增加订单数量，并对剩余芒果进行处罚。这是改编后的模型：
from pulp import *
# PROBLEM DATA:
demand = [3, 7, 2, 5, 9, 3, 2, 4, 7, 5] # demand per order
packages = [0, 5, 0, 5] # available packages of different sizes
O = range(len(demand))
P = range(len(packages))
M = max(demand) # a big enough number
# DECLARE PROBLEM OBJECT:
prob = LpProblem('Mango delivery', LpMaximize)
# VARIABLES
assigned = pulp.LpVariable.dicts('assigned',
((o, p) for o in O for p in P), 0, max(demand), cat='Integer') # number of packages of different sizes per order
supply = LpVariable.dicts('supply', O, 0, max(demand), cat='Integer') # supply per order
remnant = LpVariable.dicts('remnant', O, 0, len(packages)-1, cat='Integer') # extra delivery per order
served = LpVariable.dicts('served', O, cat='Binary') # whether an order is served
diff = LpVariable.dicts('diff', O, -M, len(packages)-1, cat='Integer') # difference between demand and supply
# OBJECTIVE
# primary objective is serve orders, secondary to minimize remnants
prob += 100*lpSum(served) - lpSum(remnant) # maximize served orders with a penalty for remnants
# CONSTRAINTS
for o in O:
prob += supply[o] == lpSum([p*assigned[(o, p)] for p in P])
prob += diff[o] == supply[o] - demand[o]
for p in P:
# don't use more packages than available
prob += packages[p] >= lpSum([assigned[(o, p)] for o in O])
for o in O:
# an order is served if supply >= demand
# formulation adapted from https://cs.stackexchange.com/questions/69531/greater-than-condition-in-integer-linear-program-with-a-binary-variable
prob += M*served[o] >= diff[o] + 1
prob += M*(served[o]-1) <= diff[o]
prob += lpSum([assigned[(o, p)] for p in P]) <= M*served[o]
for o in O:
# if order is served then remnant is supply - demand
# otherwise remnant is zero
prob += remnant[o] >= diff[o]
prob += remnant[o] <= diff[o] + M*(1-served[o])
# SOLVE & PRINT RESULTS
prob.solve()
print(LpStatus[prob.status])
print('obj = ' + str(value(prob.objective)))
print('#served = ' + str(sum(int(served[o].varValue) for o in O)))
print('#remnants = ' + str(sum(int(remnant[o].varValue) for o in O)))
print('served = ' + str([int(served[o].varValue) for o in O]))
print('demand = ' + str(demand))
print('supply = ' + str([int(supply[o].varValue) for o in O]))
print('remnant = ' + str([int(remnant[o].varValue) for o in O]))
这里有一些注意事项：
问题的变数是要不要开包。因此，这些变量为 0 或 1（保持关闭或打开）。
问题的主要objective是尽量减少剩余芒果的数量。或者换句话说：尽量减少打开包装中的芒果总数。这是输入字典的值的总和，但只是那些对应的 LP 变量为 1 的条目的总和。当然，这里可以使用乘法（与 0 或 1）。
如果出现平局，应尽量减少打开包的数量。这只是上述变量的总和。为了将其组合成一个，单个 objective，将第一个 objective 的值乘以数据包总数，然后将第二个 objective 的值添加到它。这样您就可以在竞争解决方案中获得正确的顺序。
唯一的限制是打开的包装中的芒果数量总和至少为输入中给出的数量。
所以这是一个实现：
def optimise(mango_packs, mango_count):
pack_names = list(mango_packs.keys())
prob = LpProblem("MangoPacks", LpMinimize)
# variables: names of the mango packs. We can either open them or not (0/1)
lp_vars = LpVariable.dicts("Open", pack_names, 0, 1, "Integer")
# objective: minimise total count of mangoes in the selected packs (so to
# minimise remnants). In case of a tie, minimise the number of opened packs.
prob += (
lpSum([mango_packs[name]*lp_vars[name] for name in pack_names]) * len(mango_packs)
+ lpSum([lp_vars[name] for name in pack_names])
)
# constraint: the opened packs need to amount to a minimum number of mangoes
prob += lpSum([mango_packs[name]*lp_vars[name] for name in pack_names]) >= mango_count
prob.solve()
为了可视化结果，您可以在上面的函数中添加以下内容：
print("Status:", LpStatus[prob.status])
# Each of the variables is printed with it's resolved optimum value
for i, v in enumerate(prob.variables()):
print("{}? {}".format(v.name, ("no","yes")[int(v.varValue)]))
像这样调用函数：
# Packet Names and the count of mangoes in each packet.
mango_packs = {
"pack_1": 10,
"pack_2": 2,
"pack_3": 2,
"pack_4": 2
}
optimise(mango_packs, 5)
输出（当你添加那些 print 语句时）
Status: Optimal
Open_pack_1? no
Open_pack_2? yes
Open_pack_3? yes
Open_pack_4? yes
看看运行 here -- 给它点时间临时安装pulp模块