线性规划的作用

求一个线性目标函数在线性可行域内的最值问题

线性规划的典型应用

• 配送运输问题：选大车还是小车
• 生产规划问题：每种原料各买多少
• 几何切割问题：切割长宽各多少
• 买卖利润问题：最多能挣多少钱
• …

线性规划的本质

问题是线性的
约束是线性的

线性代数基本概念

线性代数基本概念：向量

向量的基本运算：

向量的集合：矩阵
这里不细讲了，忘了就复习线性代数

运用Python进行矩阵运算

1. 首先导入numpy库

import numpy as np

2. 使用np.array创建矩阵

a = np.array([[1,2,3],[4,5,6]])
b = np.array([[1,2],[3,4],[5,6]])
c = np.array([[1,2,3]])
d = np.array([[9,8,7],[3,2,1]])

3. 矩阵加法和数乘

sum = a + b #加法
e = 3 * a #数乘

4. 使用np.dot进行矩阵相乘

e = np.dot(a, b)

5. 元素乘（要求行列一致）

e = a * d

6. 矩阵转置

e = c.T

7. 使用np.linalg.inv求逆

result = np.linalg.inv(e)

8. 使用np.linalg.det求行列式

reslut = np.linalg.det(e)

9. 使用np.linalg.matrix_rank求矩阵的秩

e = np.linalg.matrix_rank(d)

运用Python求解一次方程组

例如：
$$\left\{\begin{array}{rl}10x-y-2z=& 72\\ -x+10y-2z=& 83\\ -x-y+5z=& 42\end{array}\right)$$

解法：
$$x=A^{-1}b$$

求数值解：使用numpy库

import numpy as np  A = np.array([[10, -1, -2], [-1, 10, -2], [-1, -1, 5]])  # A为系数矩阵  
b = np.array([72, 83, 42])  # b为常数列  
inv_A = np.linalg.inv(A)  # 求A的逆矩阵  
x = inv_A.dot(b)  # A的逆矩阵点乘b  
x = np.linalg.solve(A, b)  # 5,6行可用本行替代  
print(x)

结果：[11. 12. 13.]

我们还可以使用sympy库求符号解或数值解：

from sympy import symbols, Eq, solve  x, y, z = symbols('x y z')  
# 直接写入方程形式
eqs = [Eq(10 * x - y - 2 * z, 72),  Eq(-x + 10 * y - 2 * z, 83),  Eq(-x - y + 5 * z, 42)]  
print(solve(eqs, [x, y, z]))

结果：{x: 11, y: 12, z: 13}

从矩阵角度思考线性规划的标准形式

1. 不等式组条件矩阵化
2. 方程组条件矩阵化
3. 写出变量自身的取值范围
4. 把目标函数向量化
5. 求极值

用程序做线性规划问题时的规范形式：
$$\begin{array}{rl}& \underset{x}{\min }{c}^{T}x\\ & \text{ s.t. }\{\begin{array}{l}Ax\le b\\ Aeq\cdot x=beq\\ lb\le x\le ub\end{array}\end{array}$$

1. 求一个线性函数的极小值
2. 不等式约束一定是小于等于号

线性规划的三要素：决策变量、目标函数、约束条件

线性规划的Python程序求解

例：

$$\max z=2x_1+3x_2-5x_3$$
$$s.t.\{\begin{array}{l}{x}_1+x_2+x_3=7\\ 2x_1-5x_2+x_3>=10\\ x_1+3x_2+x_3<=12\\ x_1,x_2,x_3>=0\end{array}$$

前面提到，规范形式中要求极小值，且不等式约束必须是小于等于号

所以目标函数和第一条不等式需要乘以-1

import numpy as np  
from scipy import optimize  # 向量化  
c = np.array([-2, -3, 5])  # 乘以-1变为求极小值  
Aeq = np.array([[1, 1, 1]])  # 方程  
beq = np.array([7])  
A = np.array([[-2, 5, -1], [1, 3, 1]])  # 不等式  
b = np.array([-10, 12])  
x1, x2, x3 = (0, None), (0, None), (0, None) # 范围 res = optimize.linprog(c, A, b, Aeq, beq, bounds=(x1, x2, x3)) # 计算
print(res)

结果：

message: Optimization terminated successfully. (HiGHS Status 7: Optimal)success: Truestatus: 0fun: -14.571428571428571 # 最优函数值（因为要取最大值所以结果要取fun的相反数）x: [ 6.429e+00  5.714e-01  0.000e+00] # x的结果nit: 3 # 3轮计算得出结果lower:  residual: [ 6.429e+00  5.714e-01  0.000e+00]marginals: [ 0.000e+00  0.000e+00  7.143e+00]upper:  residual: [       inf        inf        inf]marginals: [ 0.000e+00  0.000e+00  0.000e+00]eqlin:  residual: [ 0.000e+00]marginals: [-2.286e+00]ineqlin:  residual: [ 0.000e+00  3.857e+00]marginals: [-1.429e-01 -0.000e+00]mip_node_count: 0mip_dual_bound: 0.0mip_gap: 0.0

算法的特性：输入、输出、有穷性、确定性、可行性