利用python处理线性规划问题
（例题和部分解答思路来自清风老师）
linprog函数
导入模块
from scipy.optimize import linprog
函数功能
Linear programming: minimize a linear objective function subject to linear equality and inequality constraints.
处理线性规划问题，在等式和不等式约束下最小化目标函数
函数定义
def linprog(c: Any,
A_ub: Any = None,
b_ub: Any = None,
A_eq: Any = None,
b_eq: Any = None,
bounds: Optional[Iterable] = None ）->result
c: 目标函数的系数，表示要最大化或最小化的线性函数的各个变量的系数。
A_ub: 不等式约束的左侧系数矩阵，表示需要满足的上界约束条件的系数。
b_ub: 不等式约束的右侧边界，表示与 A_ub 中相应行相乘后的结果需要小于等于的值。
A_eq: 等式约束的左侧系数矩阵，表示需要满足的等式约束条件的系数。
b_eq: 等式约束的右侧边界，表示与 A_eq 中相应行相乘后的结果需要等于的值。
bounds: 变量的取值范围，定义每个决策变量的最小和最大值，可以是单个值或多个变量的范围
result.x：最优解。
result.fun：最小化后的目标函数值（需要取负以获取最大化值）。
result.status：优化结果状态。
0：成功且找到唯一解。优化过程成功完成，并找到了一个唯一的最优解。
1：达到最大迭代次数。优化过程未能收敛，达到预设的最大迭代次数。
2：多解。存在多个最优解，优化问题的解空间中有多个解都能够达到最优目标。
3：无解。表示没有找到满足约束条件的解。
4：问题无界。优化问题是无界的，即目标函数可以无限增大（或减小）。
5：其他错误。可能是由于输入参数不正确或其他原因导致的错误。
基本例题
例题1
最小化目标函数
z
=
−
5
x
1
−
4
x
2
−
6
x
3
z = -5x_1 -4x_2 - 6x_3
z=−5x1−4x2−6x3
约束条件：
- x 1 − x 2 + x 3 ≤ 20 x_1 - x_2 + x_3 \leq 20 x1−x2+x3≤20
- 3 x 1 + 2 x 2 + 4 x 3 ≤ 42 3x_1 + 2x_2 +4 x_3 \leq 42 3x1+2x2+4x3≤42
- 3 x 1 + 2 x 2 ≤ 30 3x_1 + 2x_2 \leq 30 3x1+2x2≤30
- x 1 , x 2 , x 3 ≥ 0 x_1, x_2, x_3 \geq 0 x1,x2,x3≥0
c=[-5,-4,-6]
A_ub=[[1,-1,1],[3,2,4],[3,2,0]]
b_ub=[20,42,30]
result=linprog(c,A_ub=A_ub,b_ub=b_ub,bounds=[(0,None),(0,None),(0,None)])
# 格式化结果
optimal_value = f"{result.fun:.2f}"
optimal_solution = [f"{x:.2f}" for x in result.x]
print('Optimal value:', optimal_value)
print('Optimal solution:', optimal_solution)
bound中的无穷边界可用None表示，或用float(‘inf’)或np.inf表示
例题2
最大化目标函数
z
=
2
x
1
+
3
x
2
−
5
x
3
z = 2x_1 + 3x_2 - 5x_3
z=2x1+3x2−5x3
约束条件：
- x 1 + x 2 + x 3 = 7 x_1 + x_2 + x_3 = 7 x1+x2+x3=7
- 2 x 1 − 5 x 2 + x 3 ≥ 10 2x_1 - 5x_2 + x_3 \geq 10 2x1−5x2+x3≥10
- x 1 + 3 x 2 + x 3 ≤ 12 x_1 + 3x_2 + x_3 \leq 12 x1+3x2+x3≤12
- x 1 , x 2 , x 3 ≥ 0 x_1, x_2, x_3 \geq 0 x1,x2,x3≥0
c=[-2,-3,5]
A_ub=[[1,3,1],[-2,5,-1]]
b_ub=[12,-10]
A_eq=[[1,1,1]]
b_eq=[7]
result=linprog(c,A_ub=A_ub,b_ub=b_ub,A_eq=A_eq,b_eq=b_eq,bounds=[(0,None),(0,None),(0,None)])
# 格式化结果
optimal_value = f"{-result.fun:.2f}"
optimal_solution = [f"{x:.2f}" for x in result.x]
print('Optimal value:', optimal_value)
print('Optimal solution:', optimal_solution)
典型例题
例一：生产决策问题
建模
代码
c=[0]*9
c[0]=-(1-0.25)
c[1]=-(1-(321*7/10000))
c[2]=250*6/4000
c[3]=783*4/7000
c[4]=200*7/4000
c[5]=300*10/6000
c[6]=321*9/10000
c[7]=-(1.65-250*8/4000)
c[8]=-(2.3-321*12/10000-783*11/7000)
A_ub=[[5,0,0,0,0,10,0,0,0],[0,7,0,0,0,0,9,0,12],[0,0,6,0,0,0,0,8,0],[0,0,0,4,0,0,0,0,11],[0,0,0,0,7,0,0,0,0]]
b_ub=[6000,10000,4000,7000,4000]
A_eq=[[1,1,-1,-1,-1,0,0,0,0],[0,0,0,0,0,1,1,-1,0]]
b_eq=[0,0]
bound=[(0,None)]
result=linprog(c,A_ub=A_ub,b_ub=b_ub,A_eq=A_eq,b_eq=b_eq,bounds=bound*9)
# 格式化结果
optimal_value = f"{-result.fun:.2f}"
optimal_solution = [f"{x:.2f}" for x in result.x]
print('Optimal value:', optimal_value)
print('Optimal solution:', optimal_solution)
结果
Optimal value: 1146.57
Optimal solution: ['1200.00', '230.05', '0.00', '858.62', '571.43', '0.00', '500.00', '500.00', '324.14']
例一：生产决策问题
建模
代码（难点：双下标与单下标转化）
import numpy as np
import math
#料场坐标 (a_i,b_i) i=1,2
loc_sup=[[5,1],[2,7]]
#工地坐标（p_j,q_j） j=1,2,...,6
loc_wok=[[1.25,1.25],[8.75,0.75],[0.5,4.75],[5.75,5],[3,6.5],[7.25,7.25]]
#工地日需求量
need_wok=[3,5,4,7,6,11]
max_sup=20
#决策变量 i->j x_ij x_(6i+j) 表示从料场i送向工地j的水泥吨数
#决策变量系数：表示表示从料场i送向工地j的距离 （a_i-p_j）^2+(b_i-q_j)^2
c=[0]*12
for k in range(12):
i=k//6
j=k%6
c[k]=math.sqrt((loc_sup[i][0]-loc_wok[j][0])**2+(loc_sup[i][1]-loc_wok[j][1])**2)
#约束条件:
#1 x_1j+x_2j=d_j 工地水泥需求
A_eq=np.zeros((6,12))
i=0
for j in range(6):
A_eq[j][i],A_eq[j][i+6]=1,1
i=i+1
b_eq=need_wok
#2 每个料场运输<=20 Σ_j x_ij<=20
A_ub=np.zeros((2,12))
A_ub[0,0:6]=1
A_ub[1,6:]=1
b_ub=[20,20]
bound=[(0,None)]
result=linprog(c,A_ub=A_ub,b_ub=b_ub,A_eq=A_eq,b_eq=b_eq,bounds=bound*12)
# 格式化结果
optimal_value = f"{result.fun:.2f}"
optimal_solution = [f"{x:.2f}" for x in result.x]
print('Optimal value:', optimal_value)
print('Optimal solution:', optimal_solution)
结果
Optimal value: 135.28
Optimal solution: ['3.00', '5.00', '0.00', '7.00', '0.00', '1.00', '0.00', '0.00', '4.00', '0.00', '6.00', '10.00']