在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。
定义:线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。
$$ \min \boldsymbol{c}^{\boldsymbol{T}}\boldsymbol{x} \ \boldsymbol{s}.\boldsymbol{t}.\begin{cases} \boldsymbol{Ax}\leqslant \boldsymbol{b}\ \boldsymbol{Aeq}\cdot \boldsymbol{x}=\boldsymbol{beq}\ \boldsymbol{lb}\leqslant \boldsymbol{x}\leqslant \boldsymbol{ub}\ \end{cases} $$ 实际问题:
from scipy.optimize import linprog
c=[4,3]
A=[[2,1],[1,1]]
B=[10,8]
x1=[0,None]
x2=[0,7]
res=linprog(c,A,B,bounds=(x1,x2))- c:线性目标函数系数
- A_ub(可选参数): 不等式约束矩阵, 𝐴𝑢𝑏的每一行指定x上的线性不等式约束的系数
- b_ub(可选参数): 不等式约束向量，每个元素代表Aub𝐴𝑢𝑏x的上限
- A_eq(可选参数): 等式约束矩阵，Aeq𝐴𝑒𝑞的每一行指定x xx上的线性等式约束的系数
- b_eq(可选参数): 等式约束向量，Aeq𝐴𝑒𝑞的每个元素必须等于beq𝑏𝑒𝑞的对应元素
- bounds(可选参数): 定义决策变量x的最小值和最大值
- 数据类型： (min, max)序列对
- None：使用None表示没有界限，默认情况下，界限为（0，None）（所有决策变量均为非负数
- 如果提供一个元组(min, max)，则最小值和最大值将用作所有决策变量的界限。
-
x: 在满足限制下使得目标函数最小化的值
-
fun: 目标函数的最优值
-
slack: 不等式约束的松弛值
-
con: 等式约束的残差
-
success: 当算法成功找到最佳方案的时候返回 True
-
status: 表示算法推出状态的整数
- 0: 算法成功
- 1: 达到了迭代限制
- 2: 算法不可行
- 3: 算法不收敛
- 4: 遇到数值问题
-
nit: 遇到阶段中的迭代总数
-
message: 算法退出状态的字符串描述
一般线性规划问题的（数学）标准型为: $$ \max \boldsymbol{z}=\sum_{\boldsymbol{j}=1}^{\boldsymbol{n}}{\boldsymbol{c}{\boldsymbol{j}}\boldsymbol{x}{\boldsymbol{j}}} \ \boldsymbol{s}.\boldsymbol{t}.\begin{cases} \sum_{\boldsymbol{j}=1}^{\boldsymbol{n}}{\boldsymbol{a}{\boldsymbol{ij}}\boldsymbol{x}{\boldsymbol{j}}=\boldsymbol{b}{\boldsymbol{i}}},,\boldsymbol{i}=1,2,\cdots ,\boldsymbol{m}\ \boldsymbol{x}{\boldsymbol{j}}\geqslant 0 \boldsymbol{j}=1,2,\cdots ,\boldsymbol{n}\ \end{cases} $$
- 可行解: 满足约束条件的解,当目标函数达到最大值时候可行解就是最优解
- 可行域: 所有解的集合就看作问题的可行域
step: 画出每个约束条件在x1,x2坐标轴内的图像,然后找出在不同约束下可行域的交集
python绘制:
import numpy as np
import matplotlib.pyplot as plt
x=np.linspace(0,8,100) #这里把x的0到8分成100个
y1=np.zeros(100) #用np生成100元素都为0的空向量
y1[:]=6 #让y1中的所有元素都变成6
y2=9-2.5*x #设置y2与x的关系
upper=np.minimum(y1, y2) #确定上边界需要的线段
x1=np.zeros(100) #让x1中的所有元素都变成6
x1[:]=4 #让y1中的所有元素都变成4
y3=np.linspace(0,10,100)
nx=np.minimum(4, x) #确定了边界，即最大以x=4为上界
fig, ax = plt.subplots()
ax.plot(x, y1, label='y1=6')
ax.plot(x, y2, label='y2=9-1.5*x')
ax.plot(x1, y3, label='x=4')
ax.fill_between(nx,upper,color='gray', alpha=.5)
ax.spines['right'].set_visible(False) #去掉右边界
ax.spines['top'].set_visible(False)
ax.set_xlim((0.0, 10.000)) #设置x的画图显示范围
ax.set_ylim((0.0, 10.000))
ax.legend(loc=1)#标签必须加这个才能进行显示
plt.show()问题概述：一般的运输问题就是要解决把某种产品从若干个产电调运到若干个销地，在每个产地的供应量和每个销地的运输量已知，并知道各地之间的运输单价的前提下，如何确定一个方案使得运输费用最小。
例题：某部门有3个生产同类型产品的加工厂(产地), 生产的产品由4个销售点(销地)出售, 各个工厂的生产量,销售量,以及各个产地与各个销地所需要的运费如下表
| 产地\销地 | B1 | B2 | B3 | B4 | 产量 |
|---|---|---|---|---|---|
| A1 | 4 | 12 | 4 | 11 | 16 |
| A2 | 2 | 10 | 3 | 9 | 10 |
| A3 | 8 | 5 | 11 | 6 | 22 |
| 销量 | 8 | 14 | 12 | 14 | 48 |
基本模型： $$ \mathbf{minz}=\sum_{\mathbf{i}=\mathbf{1}}^{\mathbf{m}}{\sum_{\mathbf{j}=\mathbf{1}}^{\mathbf{n}}{\mathbf{c}{\mathbf{ij}}\mathbf{x}{\mathbf{ij}}}} \ \mathbf{s}.\mathbf{t}.\begin{cases} \sum_{\mathbf{j}=\mathbf{1}}^{\mathbf{n}}{\mathbf{x}{\mathbf{ij}}=\mathbf{a}{\mathbf{i}}\left( \mathbf{i}=\mathbf{1},\mathbf{2},\cdots ,\mathbf{m} \right)}\ \sum_{\mathbf{i}=\mathbf{1}}^{\mathbf{m}}{\mathbf{x}{\mathbf{ij}}=\mathbf{b}{\mathbf{j}}\left( \mathbf{j}=\mathbf{1},\mathbf{2},\cdots ,\mathbf{n} \right)}\ \mathbf{x}_{\mathbf{ij}}\geqslant \mathbf{0}\left( \mathbf{i}=\mathbf{1},\mathbf{2},\cdots ,\mathbf{m};\mathbf{j}=\mathbf{1},\mathbf{2},\cdots ,\mathbf{n} \right)\ \end{cases} $$ 在这里c是指各个产地与各个销地所需要的运费，x是只各个产地与各个销地所需要的运输数量