0x1.概述

线性规划研究的是一类在==线性约束==条件下求解==线性目标函数==极值的问题。

单纯形法被誉为20世纪对科学发展和工程实践影响最大的十种算法之一。

0x2.标准模型

线性规划的标准模型为： 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝒄^⊺^ 𝒙 subject to 𝐴𝒙=𝒃 𝒙≥𝟎 其中，𝑐∈ℝ^𝑛^， 𝑏∈ℝ^𝑚^， 𝐴∈ℝ^𝑚×𝑛^。

0x3.二维线性规划

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒄^⊺^ 𝒙 subject to 𝐴𝒙≤𝒃 𝒙≥𝟎

其中，$x=[x_1,x_2]^T,c^T=[1,5]\,A=\begin{bmatrix} 5&6\3&2\end{bmatrix},b=\begin{bmatrix}30\12\end{bmatrix}$

于是，可以在二维坐标轴中画出可行域，从可行域中选择最佳的点来取得结果。

0x3.超几何线性规划

约束集𝐴𝒙≤𝒃, 𝒙≥𝟎是凸多面体。

目标函数的等值面是超平面簇。

凸多面体和超平面的交是什么？临界的超平面是什么？ 凸多面体的支撑超平面。

1.线性规划的标准型

其中，𝒚称为==剩余变量==。剩余变量对目标函数没有任何贡献。

其中，𝒚称为==松弛变量==。松弛变量对目标函数没有任何贡献。

0x4.基本解

线性规划的标准模型为： 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝒄^⊺^ 𝒙 subject to 𝐴𝒙=𝒃 𝒙≥𝟎 其中，𝑐∈ℝ^𝑛^， 𝑏∈ℝ^𝑚^， 𝐴∈ℝ^𝑚×𝑛^。𝑟𝑎𝑛𝑘(𝐴)=𝑚， 𝑚<𝑛。

分块矩阵求解

考虑方程组𝐴𝒙=𝒃，将𝐴写为分块儿矩阵𝐴=[𝐵,𝐷]， 𝐵是一个𝑚×𝑚的非奇异矩阵。 𝐷是一个𝑚×(𝑛−𝑚)的矩阵。

求解方程𝐵𝒙~𝐵~ =𝒃得，𝒙~𝐵~=𝐵^−1^𝑏。

令x为n维向量，它的前m个元素等于x~B~，其余元素为零，即x=[x~B~^T^,0^T^]^T^，那么x是方程Ax=b的一个解。

定义15.1 基本解 基变量 基本列向量

[x~B~^T^,0^T^]^T^是𝐴𝒙=𝒃在基𝐵下的==基本解==，向量𝒙~𝐵~中的元素称为==基变量==，𝐵中的列向量称为==基本列向量==。

• ==退化的基本解==，如果基本解中的某些基变量为零，那么这个基本解称为退化的基本解。
• ==可行解==，满足Ax=b，x≥0的向量x称为可行解。
• ==基本可行解==，既是可行解，也是基本解。
• ==退化的基本可行解==，是基本可行解并且是退化的基本解。

基本解的个数为: $$ C_n^m= \begin{pmatrix} n\m \end{pmatrix} =\frac{n!}{m!(n-m)!} $$ 例子：

定义15.2 最优可行解

对于任何满足约束条件𝐴𝒙=𝒃, 𝒙≥𝟎的向量𝒙，如果它能够使目标函数𝒄^⊺^𝒙取得极小值，那么就将其称为==最优可行解==。

有最优可行解一定有最优基本可行解

定理15.1 线性规划基本定理

线性规划基本定理。对于线性规划的标准型，有如下两个命题：

• 如果存在==可行解==，那么一定存在==基本可行解==。
• 如果存在==最优可行解==，那么一定存在==最优基本可行解==。

定理15.2 几何视角下的线性规划

回顾概念：

凸集：对于任何x，y∈θ，和任意实数α，0<α<1，如果由αx+(1-α)y∈θ，则称集合θ⊂ℝ^𝑛^为凸集。换言之，如果集合中任意两点的连线上的点在该集合内，则称该集合为凸集。

极点：几点并不在集合中其他两点的连线上。

Ω表示由所有可行解组成的凸集，即集合中的所有n维向量x满足： $$ Ax=b,x\ge0 $$ 其中，A∈ℝ^𝑚×𝑛^，𝑚<𝑛。那么，x是Ω的极点当且仅当x是Ax=b，x≥0的基本可行解。