Python 求解线性规划

本文记录 Python 实现现行规划的实现方案。

SciPy

提供linprog函数，支持单纯形法和内点法，适合标准线性规划问题。

示例：最小化目标函数 $𝑍=2𝑥_1+3𝑥_2$ 并满足约束 $𝑥_1+𝑥_2≤4$ 和 $2𝑥_1+𝑥_2≤5$：

from scipy.optimize import linprog
c = [-2, -3]  # 目标函数系数（取负转为最小化）
A = [[1, 1], [2, 1]]  # 不等式约束矩阵
b = [4, 5]  # 约束右侧常数
bounds = [(0, None), (0, None)]  # 变量非负
result = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='highs')
print(result.x)  # 输出最优解
print(- result.fun)  # 输出目标函数的最大值

输出：

[0. 4.]
12.0

PuLP

可读性高，适合更加复杂的现行规划。

示例：求解同样的问题。

import pulp
# 创建问题实例，这里我们使用最大化问题
prob = pulp.LpProblem("Minimize_Problem", pulp.LpMaximize)
# 定义决策变量
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
# 定义目标函数
prob += 2*x1 + 3*x2, "Z"
# 添加约束条件
prob += x1 + x2 <= 4, "C1"
prob += 2*x1 + x2 <= 5, "C2"
# 求解问题
prob.solve()
# 输出结果
print("Status:", pulp.LpStatus[prob.status])
print("Optimal value (Z) = ", pulp.value(prob.objective))
print("x1 = ", pulp.value(x1))
print("x2 = ", pulp.value(x2))

输出：

Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - /solverdir/cbc/linux/i64/cbc /tmp/424b9f916f264e4c9f6eb369b6031c8b-pulp.mps -max -timeMode elapsed -branch -printingOptions all -solution /tmp/424b9f916f264e4c9f6eb369b6031c8b-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 7 COLUMNS
At line 14 RHS
At line 17 BOUNDS
At line 18 ENDATA
Problem MODEL has 2 rows, 2 columns and 4 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 2 (0) rows, 2 (0) columns and 4 (0) elements
0  Obj -0 Dual inf 4.9999998 (2)
0  Obj -0 Dual inf 4.9999998 (2)
1  Obj 12
Optimal - objective value 12
Optimal objective 12 - 1 iterations time 0.002
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

Status: Optimal
Optimal value (Z) =  12.0
x1 =  0.0
x2 =  4.0

文章链接：
https://www.zywvvd.com/notes/study/math/python-lp/python-lp/