这是笔者学习使用PULP库进行线性规划问题求解的学习笔记，水平有限，错误在所难免，请方家不吝指正。
PULP库简介
PULP是用Python写的一个线性规划(Linear Programming, LP)问题求解库。它的主要作用是将优化问题描述为数学模型，生成MPS或者LP文件，然后调用LP求解器，如CBC、GLPK、CPLEX、Gurobi等来进行求解。
PULP库安装
作为python的库，PULP的安装非常简单了，打开command window，输入以下指令，等待安装完成即可：
pip install pulp
优化问题的求解步骤
通常来说，优化问题的求解可以分为以下五个步骤：
- 获取问题描述
- 数学剑魔
- 求解数学模型
- 后续分析
- 根据最优解，提出实施方案
下面逐一进行详述：
获取问题描述
这一步的目的是获得严格无歧义的对问题的描述。在这一步中，需要反复和业务方进行探讨，确保模型和实际业务严密贴合。需要注意模型和数据是紧密联系的，有时哪怕你提出的模型很好，但是业务方无法提供可用的数据，那你也不可能凭空对模型进行求解。因此必须要确认好对方的需求和可用的数据，才能保证模型求解之后作出的决策可以落地。
数学建模
在这一步中，我们需要从问题的描述里抽象出几个关键因素：决策变量、约束和目标函数。这一步又可以分解为四个步骤：
- 找到决策变量，也就是我们需要改变以在满足约束范围内找到最优目标函数的变量，特别需要注意其单位；
- 用决策变量表示目标函数，大多数情况下目标函数是问题在给定决策变量范围内的总成本或者总利润；
- 用决策变量表示约束，这些约束可能是在问题描述中显式提出的，也可能是一些隐式的约束，例如说我们不可能给一项工作分配负数时间，在运输时不能运输0.8台车等；
- 确定求解问题所需的数据。为了在数学上求解模型，我们需要数据的支持，比如经过某条路径所需的时间、某个变量的具体上界数字等。
求解数学模型
在这一步中我们要找到模型的全局最优或者近似全局最优以帮助我们作出决策。在规模合理的线性优化中，我们通常可以借助求解器中已经实施好的改进单纯形法、内点法等来帮助我们得到全局最优。但是如果是非线性问题或者问题规模很大，那么在较短时间内可能无法求出精确解，这时候通常我们会借助启发式算法，在给定时间内收敛到一个质量较高的近似全局最优(注意在通常情况下，启发式算法是不能保证每次都收敛到全局最优附近的)。
后续分析
为了帮助作出最后的决策，通常在跑通求解之后，需要对模型进行进一步的分析：哪些变量的改变对结果影响最大，收紧或者放松约束对结果的影响等等。这些分析可以帮助我们检验模型的鲁棒性，并且为作出决策提供支持。
此外，需要考虑最优解代表的决策是否符合逻辑，或者是否符合业务方的需求。
根据最优解，提出实施方案
在这一步中，我们需要将用数学语言表述的最优解转化为简洁可行的实施方案，进行展示和反馈。这一步中，让业务方理解在优化过程中发现的关键因素，以及让他们明白具体在操作中如何实施是非常重要的，否则可能面临着一个数学上非常优秀的解在业务上无法落地的结局。
也可以考虑一些将来的工作，如监测优化方案实施后业务数据的变化、进一步分析数学模型，为业务方寻找新的价值等。
在PULP中求解简单线性规划问题
下面用官方文档上的一个例子解释以下用PULP求解线性问题的基本步骤：
问题描述
制造商想要用鸡肉和牛肉两种材料来混合出猫粮。在满足猫粮所需要的蛋白质、脂肪、纤维、盐等营养成分的前提下，尽可能降低成本。营养成分约束如下：
每克猫粮中，蛋白质大于8%，脂肪大于6%，纤维小于2%，盐分小于0.4%。
每克鸡肉的成本是0.013元，牛肉的成本是0.008元。而每克的这两种肉含有的营养成分如下表(单位：克)：
| 所用肉类 | 蛋白质 | 脂肪 | 纤维 | 盐分 |
|---|---|---|---|---|
| 鸡肉 | 0.100 | 0.080 | 0.001 | 0.002 |
| 牛肉 | 0.200 | 0.100 | 0.005 | 0.005 |
制造商想要知道最优的混合比例如何。
数学模型
确定决策变量
此问题中，决策变量就是鸡肉和牛肉的比例，可以用两个变量表示：
目标函数
这里的优化目标就是最小化成本，因此目标函数为：
约束
此问题的约束来自两方面：隐式的约束在于两个比例之和必须为1，显式的约束在于各营养成分之和必须要大于要求。
PULP求解
函数介绍
在PULP中可以通过LpProblem建立优化问题，其函数原型如下：
pulp.LpProblem(name='NoName', sense=LpMinimize)
其函数的参数为name：在lp文件中写入的问题名称；sense：最大或者最小，可为LpMinimize\LpMaximize二者之一。
对于优化变量，可以通过LpVariable函数给出，其函数原型如下：
pulp.LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)
其函数参数为name：变量名；lowBound变量下界；upBound变量上界；cat变量类型，可以为LpInteger\LpBinary\LpContinuous三者之一；e指明变量是否在目标函数和约束中存在，主要用来实现列生成算法。
完整代码如下：
from pulp import *
# 1. 建立问题
prob = LpProblem("Bleding Problem", LpMinimize)
# 2. 建立变量
x1 = LpVariable("ChickenPercent", 0, None, LpInteger)
x2 = LpVariable("BeefPercent", 0)
# 3. 设置目标函数
prob += 0.013*x1 + 0.008*x2, "Total Cost of Ingredients per can"
# 4. 施加约束
prob += x1 + x2 == 100, "PercentagesSum"
prob += 0.100*x1 + 0.200*x2 >= 8.0, "ProteinRequirement"
prob += 0.080*x1 + 0.100*x2 >= 6.0, "FatRequirement"
prob += 0.001*x1 + 0.005*x2 <= 2.0, "FibreRequirement"
prob += 0.002*x2 + 0.005*x2 <= 0.4, "SaltRequirement"
# 5. 求解
prob.solve()
# 6. 打印求解状态
print("Status:", LpStatus[prob.status])
# 7. 打印出每个变量的最优值
for v in prob.variables():
print(v.name, "=", v.varValue)
# 8. 打印最优解的目标函数值
print("Total Cost of Ingredients per can = ", value(prob.objective))
求解结果如下：
Status: Optimal
BeefPercent = 57.0
ChickenPercent = 43.0
Total Cost of Ingredients per can = 1.015
网友评论