使用Python和Pulp最大化每日利润问题

Question

我正在尝试最大化一家巧克力工厂的日利润时遇到了问题。

问题：一家工厂生产单个巧克力（每种巧克力都有各自的利润和每日最大产量限制）以及特色礼盒（每个礼盒包含3颗巧克力及其对应的利润）。例如：

# 限制变量
# n - 巧克力种类数量
# p - 特色礼盒种类数量
# max_chocolates - 每日巧克力总的最大生产能力
n = 5
p = 2
max_chocolates = 150

# 单个巧克力的数据：每种巧克力（1,2,3,4,5）有各自的利润和每日最大产量
profit_chocolates = [50, 30, 45, 40, 35]
capacity_chocolates = [27, 33, 30, 37, 35]

# 特色礼盒的数据：每个礼盒由3颗巧克力组成及相应礼盒的利润
pack_components = [(1, 3, 5), (2, 3, 4)]
profit_packs = [130, 130]

接下来是用于获取最大日利润的代码：

# 初始化问题
prob = LpProblem("最大化巧克力与礼盒利润", LpMaximize)

# 决策变量：
chocolate_vars = [LpVariable(f"x{i}", lowBound=0, cat="Integer") for i in range(n)]
packs_vars = [LpVariable(f"p{i}", lowBound=0, cat="Integer") for i in range(p)]

# 目标函数
prob += lpSum(profit_chocolates[i] * chocolate_vars[i] for i in range(n)) + \
        lpSum(profit_packs[i] * packs_vars[i] for i in range(p))

# 约束条件：
# 对于每日允许生产的巧克力总量上限
prob += lpSum(chocolate_vars[i] for i in range(n)) <= max_chocolates

# 对于每种巧克力的每日最大产量
for i in range(n):
    prob += chocolate_vars[i] <= capacity_chocolates[i]

# 对于特色礼盒：
# 利润约束：每个礼盒的利润不应低于其包含的巧克力利润之和
for i in range(p):
    prob += lpSum(profit_chocolates[j - 1] for j in pack_components[i]) >= profit_packs[i]

# 礼盒产能约束：每个礼盒需要考虑其所含巧克力的产能——如果礼盒中的任意一颗巧克力的日产量超过了该巧克力的每日生产限额，则无法生产该礼盒
for i in range(p):
    for j in pack_components[i]:
        prob += (chocolate_vars[j - 1]) <= capacity_chocolates[j - 1]

# 每个决策变量必须大于等于0
for i in range(n):
    prob += chocolate_vars[i] >= 0

for i in range(p):
    prob += packs_vars[i] >= 0

prob.solve()

for i in range(len(chocolate_vars)):
    print(chocolate_vars[i].varValue)

for i in range(len(packs_vars)):
    print(packs_vars[i].varValue)

print(f"最大日利润: {int(prob.objective.value())}")

对于上述输入数据，期望得到的最大利润应该是6440，但是我得到的结果是6035。

我认为结果差异与特色礼盒有关，因为它们依赖于各自包含的巧克力。

能否请您帮我找出我在何处遗漏或做错了？

谢谢！

Sam · Answer

您已经接近正确的解决方案了。您所缺少的关键部分是如何计算每种巧克力因生产特色礼盒所需的准确数量。

您真正需要的是某种机制来查询礼盒以获得生产该礼盒所需的单个巧克力数量，这样您就能实现这样的表达式：

production[choc] = individual_pieces[choc] + quantity_in_packs[choc]

这样一来，在对每种巧克力添加约束时，您就能够得到正确的总数。下面的解决方案使用字典实现了这一点，实际上是一个嵌套字典，这样您就可以询问：

quantity_in_pack[pack][choc]

从而得到那个数字，然后在处理每种巧克力时，您需要对所有礼盒进行求和以得到总数（如示例所示）。除了这种方法之外，可能还有其他几种方式来实现。也许可以反转字典的索引顺序，首先按照巧克力索引，然后再按照礼盒索引，但这里采用的方法看起来较为直观。

无论如何，您真正需要关注的只有两个约束条件：

总共生产的数量
每种巧克力的生产数量

注意事项：

我在代码中留下了一些注释，并注释掉了不必要的部分。
我重新命名了集合变量名，使它们更易读，同时也避免了使用 j-1 这样的索引计算。
使用列表或集合表示索引比使用 range(n) 更易读，所以我倾向于那样做，便于阅读，而且可以很容易地进行类似数学表达式的操作，比如 for car in cars 等。
我在这里大量使用了字典打包功能，这非常方便，或者您也可以从头开始直接创建字典。
希望我没有为您完成了冬季线性规划项目的全部工作。

下面是经过修订后的代码：

from pulp import *

# 限制变量
# n - 巧克力种类数
# p - 特色礼盒种类数
# max_chocolates - 每日巧克力生产总的最大数量
n = 5
chocolates = ['黑巧', '牛奶', '覆盆子', '焦糖', '彩珠']
p = 2
packs = ['超级豪华礼盒', '妈妈精选礼盒']
max_chocolates = 150

# 单个巧克力数据：每种巧克力有各自的利润和每日最大产量
profit_chocolates = [50, 30, 45, 40, 35]
profit_chocolates = dict(zip(chocolates, profit_chocolates))
capacity_chocolates = [27, 33, 30, 37, 35]
capacity_chocolates = dict(zip(chocolates, capacity_chocolates))

# 特色礼盒数据：每个礼盒由3颗巧克力组成及对应礼盒的利润
pack_components = [('黑巧', '覆盆子', '彩珠'), ('牛奶', '覆盆子', '焦糖')]
# 这个会非常有用：分解礼盒内容及其数量
pack_breakdown = {
    '超级豪华礼盒': {chocolates[i-1]: 1 for i in pack_components[0]},
    '妈妈精选礼盒': {chocolates[i-1]: 1 for i in pack_components[1]}
}
profit_packs = [130, 130]
profit_packs = dict(zip(packs, profit_packs))

# 初始化问题
prob = LpProblem("最大化巧克力与礼盒利润", LpMaximize)

# 决策变量：
# make_chocolate 只表示单独销售的数量，而非总量
make_chocolate = LpVariable.dicts("make_chocolate", chocolates, lowBound=0, cat="Integer") 
make_pack = LpVariable.dicts("make_pack", packs, lowBound=0, cat="Integer")

# 目标函数（正确）
prob += lpSum(profit_chocolates[c] * make_chocolate[c] for c in chocolates) + \
        lpSum(profit_packs[p] * make_pack[p] for p in packs)

# 约束条件：
# 捕获单个生产和礼盒中包含的所有巧克力数量
# 每日可生产的巧克力总量上限
prob += lpSum(make_chocolate[c] for c in chocolates) \
        + lpSum(make_pack[p] * sum(pack_breakdown[p].values()) for p in packs) \
        <= max_chocolates

# 每种巧克力的每日最大产量限制
for c in chocolates:
    # 创建一个便捷表达式来求和所有礼盒中特定巧克力 c 的数量
    qty_in_packs = lpSum(pack_breakdown[p].get(c, 0) * make_pack[p] for p in packs)

    prob += make_chocolate[c] + qty_in_packs <= capacity_chocolates[c]

# 特色礼盒的利润约束：（注释掉，原表达式已正确）
# # for i in range(p):
# #     prob += lpSum(profit_chocolates[j - 1] for j in pack_components[i]) >= profit_packs[i]

# 礼盒产能约束：（注释掉，已在总体约束中考虑）
# # for i in range(p):
# #     for j in pack_components[i]:
# #         prob += (make_chocolate[j - 1]) <= capacity_chocolates[j - 1]

# 每个决策变量必须大于等于0（注释掉，已经在变量定义时指定）
# for i in range(n):
#     prob += make_chocolate[i] >= 0
# for i in range(p):
#     prob += make_pack[i] >= 0

prob.solve()

print('单个巧克力生产计划：')
for c in chocolates:
    print(f'  {c:<10}:  {make_chocolate[c].varValue}')

print('
礼盒生产计划：')
for p in packs:
    print(f'  {p:<15}:  {make_pack[p].varValue}')

print('
生产量限制检查（实际/限制）：')
for c in chocolates:
    amount_produced = make_chocolate[c].varValue
    amount_produced += sum(pack_breakdown[p].get(c, 0) * make_pack[p].varValue for p in packs)
    print(f'  {c:<10}: {amount_produced}/{capacity_chocolates[c]}')

print(f"
最大日利润: {int(prob.objective.value())}")

以下是运行后的输出结果：

结果 - 找到了最优解

目标值：                  6440.00000000
枚举节点数：              0
迭代次数总计：            0
CPU 时间：                0.00 秒
实际时间：                0.00 秒

单个巧克力生产计划：
  黑巧:  27.0
  牛奶:  0.0
 覆盆子:  0.0
  焦糖:  7.0
  彩珠:  26.0

礼盒生产计划：
  超级豪华礼盒:  0.0
 妈妈精选礼盒:  30.0

生产量限制检查（实际/限制）：
  黑巧: 27.0/27
  牛奶: 30.0/33
 覆盆子: 30.0/30
  焦糖: 37.0/37
  彩珠: 26.0/35

最大日利润: 6440

Alexander Mills · Answer

我会稍微改变一下变量的设置：分别为非礼盒内的巧克力数量以及每种特色礼盒的数量。

然后相应地重新构建约束条件：

import pulp

# 限制变量
# n - 巧克力种类数
# p - 特色礼盒种类数
# max_chocolates - 每日巧克力生产总的最大数量
n = 5
p = 2
max_chocolates = 150

# 单个巧克力数据：每种巧克力（1-5）有各自的利润和每日最大产量
profit_chocolates = [50, 30, 45, 40, 35]
capacity_chocolates = [27, 33, 30, 37, 35]

# 特色礼盒数据：每个礼盒由3颗巧克力组成及对应礼盒的利润
pack_components = [(1, 3, 5), (2, 3, 4)]
profit_packs = [130, 130]

# 初始化问题
prob = pulp.LpProblem("最大化巧克力与礼盒利润", pulp.LpMaximize)

# 决策变量：

# 不在礼盒内巧克力1-5的数量
chocolate_alone_vars = [
    pulp.LpVariable(f"单独巧克力{i}", lowBound=0, cat="Integer") for i in range(n)
]

# 特色礼盒1、2的数量
pack_vars = [pulp.LpVariable(f"礼盒{j}", lowBound=0, cat="Integer") for j in range(p)]

# 目标函数
prob += pulp.lpSum(profit_chocolates[i] * chocolate_alone_vars[i] for i in range(n)) + \
        pulp.lpSum(pack_vars[j] * profit_packs[j] for j in range(p))

# 约束条件：
# 每日允许生产的巧克力总量上限
prob += (
    pulp.lpSum(chocolate_alone_vars[i] for i in range(n))
    + pulp.lpSum(pack_vars[j] * len(pack_components[j]) for j in range(p))
) <= max_chocolates

# 每种巧克力的每日最大产量
for i in range(n):
    prob += (
        chocolate_alone_vars[i]
        + pulp.lpSum(pack_vars[j] * (i+1 in pack_components[j]) for j in range(p))
    ) <= capacity_chocolates[i]

prob.solve()

print(f"最大日利润: {int(prob.objective.value())}")

for v in prob.variables():
    print(f"{v.name} = {v.varValue}")

运行这段代码后输出如下：

...

最大日利润: 6440

单独巧克力0 = 27.0
单独巧克力1 = 0.0
单独巧克力2 = 0.0
单独巧克力3 = 7.0
单独巧克力4 = 26.0
礼盒0 = 0.0
礼盒1 = 30.0