Python PuLP 简单求解线性规划问题

一般步骤

  1. 导入 PuLP
  2. 使用 LpProblem 定义问题(名称、类型)
  3. 使用 LpVariable 定义变量(名称、下限、上限、类型)
  4. 添加目标表达式
  5. 添加约束条件
  6. 求解
  7. 输出结果

简单实例

问题

要用最低成本生产一种猫粮,同时使这种猫粮的营养成分满足一定的要求。生产者希望通过改变每种原料的添加量来实现这一目标。

每份猫粮为100克,其营养成分要求为:蛋白质不少于8克,脂肪不少于6克,纤维不多于2克,盐不多于0.4克。

猫粮的主要原料和其每克成本为:鸡肉($0.013)、牛肉($0.008)、羊肉($0.010)、大米($0.002)、小麦($0.005)、凝胶($0.001)。

每克原料对最终猫粮的营养贡献如下表所示:

原料蛋白质脂肪纤维
鸡肉0.1000.0800.0010.002
牛肉0.2000.1000.0050.005
羊肉0.1500.1100.0030.007
大米0.0000.0100.1000.002
小麦0.0400.0100.1500.008
凝胶0.0000.0000.0000.000
每克原料对最终猫粮的营养贡献,以克为单位。

求成本最低的原料添加量方案。

简化版问题

先考虑简化后的问题,假设只有鸡肉和牛肉两种原料。原料的添加量不能为负值。

简化版问题求解

导入 PuLP

from pulp import *

使用 LpProblem 定义问题

prob = LpProblem("The Cat Food Problem", LpMinimize)

LpProblem 第一个参数为问题的名称,可自定义。第二个参数为问题类型,可在 LpMinimizeLpMaximize 中选择。本题求成本最小值。

使用 LpVariable 定义变量

x1 = LpVariable("ChickenPercent", 0, None, LpContinuous)
x2 = LpVariable("BeefPercent", 0)

LpVariable 第一个参数为变量的名称,可自定义。第二个参数为变量的下限,本题为 0。第三个参数为变量的上限,None 在上下限处表示正无穷或负无穷。第四个参数为变量的类型,可选的值有 LpContinuous, LpIntegerLpBinary,意思即为字面意思,默认为 LpContinuous

添加目标表达式

prob += 0.013 * x1 + 0.008 * x2, "Cost per can"

"Cost per can" 为标识符,可自定义也可省略。注意使用 += 而不是 =

添加约束条件

prob += x1 + x2 == 100, "PercentSum"
prob += 0.100 * x1 + 0.200 * x2 >= 8.0, "Protein"
prob += 0.080 * x1 + 0.100 * x2 >= 6.0, "Fat"
prob += 0.001 * x1 + 0.005 * x2 <= 2.0, "Fibre"
prob += 0.002 * x1 + 0.005 * x2 <= 0.4, "Salt"

同样,引号中的内容为标识符,可自定义也可直接省略整个引号。注意使用 += 而不是 =

求解

prob.solve()

使用默认求解器进行求解。

输出结果

print("Status:", LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)
print("Cost per can = ", value(prob.objective))

prob.status 是求解的状态,为整数型,有 LpStatusOptimal LpStatusNotSolved, LpStatusInfeasible, LpStatusUnboundedLpStatusUndefined 这四种返回,意思即为字面意思。该值是整数型,可以通过 LpStatus[prob.status] 来获取字符串类型的状态。

prob.objective 是求解后目标表达式的值,在本题中即为所求的最低成本。

完整问题求解

求解的基本步骤是一样的,不过在使用 LpVariable 定义变量、添加目标表达式和添加约束条件时可以使用一些方法来减少需要编写的代码。

导入 PuLP

from pulp import *

定义问题中的数据

Ingredients = ["CHICKEN", "BEEF", "MUTTON", "RICE", "WHEAT", "GEL"]

costs = {
    "CHICKEN": 0.013,
    "BEEF": 0.008,
    "MUTTON": 0.010,
    "RICE": 0.002,
    "WHEAT": 0.005,
    "GEL": 0.001,
}

proteinPercent = {
    "CHICKEN": 0.100,
    "BEEF": 0.200,
    "MUTTON": 0.150,
    "RICE": 0.000,
    "WHEAT": 0.040,
    "GEL": 0.000,
}

fatPercent = {
    "CHICKEN": 0.080,
    "BEEF": 0.100,
    "MUTTON": 0.110,
    "RICE": 0.010,
    "WHEAT": 0.010,
    "GEL": 0.000,
}

fibrePercent = {
    "CHICKEN": 0.001,
    "BEEF": 0.005,
    "MUTTON": 0.003,
    "RICE": 0.100,
    "WHEAT": 0.150,
    "GEL": 0.000,
}

saltPercent = {
    "CHICKEN": 0.002,
    "BEEF": 0.005,
    "MUTTON": 0.007,
    "RICE": 0.002,
    "WHEAT": 0.008,
    "GEL": 0.000,
}

为了简化后续所需编写的代码,在此把问题中需要使用的数据先进行定义。

使用 LpProblem 定义问题

prob = LpProblem("The Cat Food Problem", LpMinimize)

使用 LpVariable 定义变量

ingredient_vars = LpVariable.dicts("Ingredients", Ingredients, 0)

在这里我们直接使用先前定义的 Ingredients 列表来定义变量。

添加目标表达式

prob += (
    lpSum([costs[i] * ingredient_vars[i] for i in Ingredients]),
    "Cost per can",
)

同样,在这里我们直接使用先前定义的 costs, ingredient_vars, Ingredients 来定义变量。

其中,lpSum 会把其参数列表的各项相加。

添加约束条件

prob += lpSum([ingredient_vars[i] for i in Ingredients]) == 100, "PercentSum"
prob += (
    lpSum([proteinPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 8.0,
    "Protein",
)
prob += (
    lpSum([fatPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 6.0,
    "Fat",
)
prob += (
    lpSum([fibrePercent[i] * ingredient_vars[i] for i in Ingredients]) <= 2.0,
    "Fibre",
)
prob += (
    lpSum([saltPercent[i] * ingredient_vars[i] for i in Ingredients]) <= 0.4,
    "Salt",
)

同上,使用预先定义的数据来简化代码。

求解

prob.solve()

输出结果

print("Status:", LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)
print("Cost per can = ", value(prob.objective))

参考资料

Optimization with PuLP(外部链接)