什么是线性规划

在数学中,线性规划(Linear Programming,简称LP)特指目标函数和约束条件皆为线性的最优化问题。线性规划是最优化问题中的一个重要领域。在作业研究中所面临的许多实际问题都可以用线性规划来处理,特别是某些特殊情况。最简单情况就,解线性方程组。

例如:工厂生产A,B两种产品,生产每个A产品需要1斤铜和3斤铁;生产每个B产品需要2斤铜和一斤铁。现有500斤铜和400斤铁,请问如何分配原材料生产的产品数量最多?

线性规划问题的建模和求解,通常按照以下步骤进行:

(1)问题定义,确定决策变量、目标函数和约束条件;
(2)模型构建,由问题描述建立数学方程,并转化为标准形式的数学模型;
(3)模型求解,用标准模型的优化算法对模型求解,得到优化结果;

pulp库

PuLP是一个用Python编写的LP建模器。PuLP可以生成MPS或LP文件,并调用求解器来解决线性问题。

使用 LpVariable 逐一定义变量

import pulp  # 导入 pulp库

# 1.建立优化问题 model: 求最大值(LpMinimize)
model = pulp.LpProblem("工厂生产产品优化", sense=pulp.LpMaximize)  # 定义问题,求最大值
# 2.定义决策变量
A = pulp.LpVariable('产品A', lowBound=0, cat='Integer')  # 定义 A
B = pulp.LpVariable('产品B', lowBound=0, cat='Integer')  # 定义 B

# 3.定义目标函数 cost
model += (A + B)  # 总生产产品数
# 4.设置约束条件
model += (1 * A + 2 * B <= 500)
model += (3 * A + 1 * B <= 400)
# 5.求解线性规划问题
model.solve()
# 6.输出优化结果
print(model)  # 输出问题设定参数和条件
print("求解状态:", pulp.LpStatus[model.status])  # 输出求解状态
for v in model.variables():
    print(v.name, " = ", v.varValue)  # 输出每个变量的最优值
print("最大产品数 = ", pulp.value(model.objective))  # 输出最优解的目标函数值

使用 dict 定义决策变量和约束条件

当变量较多的时候,不方便使用LpVariable逐一定义变量可以使用dict定义变量和约束。

import pulp  # 导入 pulp库

# 1.建立优化问题 model: 求最大值(LpMinimize)
model = pulp.LpProblem("工厂生产产品优化", sense=pulp.LpMaximize)  # 定义问题,求最大值
# 2.定义决策变量
product = {'A': {'cu': 1, 'fe': 3}, 'B': {'cu': 2, 'fe': 1}}
product_vars = pulp.LpVariable.dicts("原料", product, lowBound=0, cat='Integer')

# 3.定义目标函数 cost
model += (pulp.lpSum(product_vars[a_product] for a_product in product))  # 总生产产品数
# 4.设置约束条件
model += (pulp.lpSum(product_vars[a_product] * product[a_product]['cu'] for a_product in product) <= 500)
model += (pulp.lpSum(product_vars[a_product] * product[a_product]['fe'] for a_product in product) <= 400)
# 5.求解线性规划问题
model.solve()
# 6.输出优化结果
print(model)  # 输出问题设定参数和条件
print("求解状态:", pulp.LpStatus[model.status])  # 输出求解状态
for v in model.variables():
    print(v.name, " = ", v.varValue)  # 输出每个变量的最优值
print("最大产品数 = ", pulp.value(model.objective))  # 输出最优解的目标函数值

(完)

文章内容参考:youcans,线性规划-pulp-复杂矩阵