python在线性规划中的应用_python线性规划

Python学习

从入门学习到机器学习、从简单绘制折线图到随机绘制各种图，附往期目录：

python入门基础知识
python绘制简单的折线图
python读取excel中数据并绘制多子图多组图在一张画布上
python绘制带误差棒的柱状图
python绘制多子图并单独显示
python读取excel数据并绘制多y轴图像
Python批量调整Word文档中的字体、段落间距及格式
python绘制带误差棒的柱状图

---

从本篇博文开始，开启学习一些优化算法和求解方法

---

线性规划的定义

提示：这里可以添加本文要记录的大概内容：

线性规划（Linear Programming 简记LP）来源于工业生产组织管理的决策问题，数学上它用来确定多变量线性函数在变量满足线性约束条件下的最优值，模型通常由三个要素—决策变量、目标函数和约束条件构成。

---

线性规划的一般模型:
$$max(min)z=\sum _{j=1}^n{c}_i{x}_i;$$

$$s.t.\{\begin{array}{ll}\sum _{j=1}^n{a}_{ij}{x}_j\le (\ge ,=)b_i,& i=1,2,3,4,\cdot \cdot \cdot ,m\\ & \\ x_j>0,& j=1,2,3,4,\cdot \cdot \cdot ,n\end{array}$$
基于模型来看，线性规划的目标函数可以是最大化问题，也可以是最小化问题；约束条件有的是“≥ ”，有的是“≤ ”，也可以是“= ”。

一、线性规划的解

当线性规划问题有最优解时，一定可以在可行域的某个顶点上取到值，当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，其中至少有一个解是可行域的一个顶点。

二、线性规划的python求解

SciPy的scipy.optimize模块提供了一个求解线性规划的函数linprog，函数集中了求解线性规划的常用算法，如单纯形法和内点法，会根据问题的规模或用户的指定选择算法进行求解。

1、引入库

from scipy.optimize import linprog
1

2、SciPy中线性规划的标准型

$$minz=c^{T}x;$$

$$s.t.\{\begin{array}{l}A\cdot x\le b\\ Aeq\cdot x=beq\\ L_b\le U_b\end{array}$$
其中，c对应于上述标准型中的目标向量，
A、b对应于不等号约束，Aeq、beq对应于等号约束，
bounds是决策向量的下界向量和上界向量所组成的 n个元素的元组bounds的默认取值下界都是0，上界都是∞ ；
返回值res.x是求得的最优解，res.fun是目标函数的最优值。
对应函数的调用模式：

#linprog的基本调用格式为：
from scipy.optimize import linprog
res=linprog(c, A, b, Aeq, beq)  #默认每个决策变量下界为0，上界为 
res=linprog(c, A=None, b=None, Aeq=None, beq=None, bounds=None, method='simplex') 
print(res.fun)   #显示目标函数最小值
print(res.x)     #显示最优解
1
2
3
4
5
6

3、训练案例1

$$minz=-x_1+4x_2;$$
$$s.t.\{\begin{array}{l}-3x_1+x_2\le 6\\ x_1+2x_2\le 4\\ x_2\ge -3\end{array}$$

代码如下（示例）：

from scipy.optimize import linprog
c = [-1, 4]; 
A = [[-3, 1], [1, 2]]
b = [6, 4]; 
#bounds是决策向量的下界向量和上界向量所组成的 n个元素的元组bounds的默认取值下界都是0，上界都是∞ 
bound=((None,None),(-3,None))

res=linprog(c,A,b,None,None,bound)
print("目标函数的最小值：",res.fun)
print("最优解为：",res.x)
#运行结果： 目标函数的最小值： -22.0
# 最优解为： [10. -3.]
1
2
3
4
5
6
7
8
9
10
11
12

---

4、训练案例2

$$maxz=x_1-2x_2-3x_3;$$
$$s.t.\{\begin{array}{l}-2x_1+x_2+x_3\le 9\\ -3x_1+x_2+2x_3\ge 4\\ 4x_1-2x_2{x}_3=-6\\ x_1\ge -10,x_2\ge 0\end{array}$$

4.1求解过程

（1）首先化成SciPy中的标准型
$$minz=-x_1+2x_2+3x_3;$$
$$s.t.\{\begin{array}{l}-2x_1+x_2+x_3\le 9\\ 3x_1-x_2-2x_3\le -4\\ 4x_1-2x_2{x}_3=-6\\ x_1\ge -10,x_2\ge 0\end{array}$$

from scipy.optimize import linprog
c=[-1, 2, 3]; 

A = [[-2, 1, 1], [3, -1, -2]]
b=[[9], [-4]]

Aeq=[[4, -2, -1]]
beq=[-6]
LB=[-10, 0, None]

UB=[None]*len(c)  #生成3个None的列表
bound = tuple(zip(LB, UB))   #生成决策向量界限的元组
res=linprog(c,A,b,Aeq,beq,bound)
print("目标函数的最小值：",res.fun)
print("最优解为：",res.x)

# 求解结果：目标函数的最小值： 0.399999999999999
# 最优解为： [-1.6  0.  -0.4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18