在最优化中，目标函数和约束函数皆为线性函数的优化问题称为线性规划（LP），它是相对简单的最优化问题。

  如下形式的线性规划记2-1： min ⁡ ∑ j = 1 n c j x j  s.t.  ∑ j = 1 n a i j x j = b i , i = 1 , 2 , ⋯   , m x j ≥ 0 , j = 1 , 2 , ⋯   , n } \left.\begin{array}{ll}{\min \sum_{j=1}^{n} c_{j} x_{j}} \\ {\text { s.t. } \sum_{j=1}^{n} a_{i j} x_{j}=b_{i},} & {i=1,2, \cdots, m} \\ {x_{j} \geq 0,} & {j=1,2, \cdots, n}\end{array}\right\} min∑j=1n​cj​xj​ s.t. ∑j=1n​aij​xj​=bi​,xj​≥0,​i=1,2,⋯,mj=1,2,⋯,n​⎭ ⎬ ⎫​

  称为线性规划的标准形式。其中 c j c_{j} cj​称为价格系数， b i b_{i} bi​称为右端项。

  采用向量－矩阵表示法，标准形式可以简写为如下形式，记为2-2:

min ⁡ c T x s.t.  A x = b x ≥ 0 } \left.\begin{array}{c}{\min c^{T} x} \\ {\text {s.t. } A x=b} \\ {x \geq 0}\end{array}\right\} mincTxs.t. Ax=bx≥0​⎭ ⎬ ⎫​

  其中 A = ( a i j ) m × n A=(a_{ij})_{m \times n} A=(aij​)m×n​， b = ( b 1 , ⋯   , b m ) T b=(b_{1}, \cdots, b_{m})^{T} b=(b1​,⋯,bm​)T， c = ( c 1 , ⋯   , c n ) T c=(c_{1}, \cdots , c_{n})^{T} c=(c1​,⋯,cn​)T， x = ( x 1 ， ⋯   , x n ) T x=(x_{1}，\cdots , x_{n})^{T} x=(x1​，⋯,xn​)T。

  在下面进行理论分析时，经常把 A A A看作由 n n n个列向量构成的，即：

A = [ a 1 ， a 2 ， ⋯ ， a n ] A=[a_{1}，a_{2}，\cdots ，a_{n}] A=[a1​，a2​，⋯，an​]

  其中第 j j j列向量是 a j = [ a 1 j ， a 2 j ， ⋯ ， a m j ] T a_{j}=[a_{1j}，a_{2j}，\cdots ，a_{mj}]^{T} aj​=[a1j​，a2j​，⋯，amj​]T。于是，2-2中的 A x = b Ax=b Ax=b可写成：

∑ j = 1 n x j a j = b \sum_{j=1}^{n}x_{j}a_{j}=b j=1∑n​xj​aj​=b

  若 A A A中有 m m m个列向量可以合并成单位矩阵，且 b ≥ 0 b \geq 0 b≥0，则此时的2-2称为线性规划的典范形式。

  对于一般形式的线性规划，比如标准形式中是求极小，而有时候给出的是求极大，所以我们需要将其化成标准形，然后对标准形做研究，得到通用的解法。

  那么实际问题中出现的非标准形式如何处理呢？有三个基本原则：

  如求 m a x ∑ j = 1 n c j x j max \sum_{j=1}^{n}c_{j}x_{j} max∑j=1n​cj​xj​，可变为 m i n ∑ j = 1 n ( − c j ) x j min \sum_{j=1}^{n}(-c_{j})x_{j} min∑j=1n​(−cj​)xj​。

注意：新引入变量的价格系数全部设为零，因此目标函数中没有出现新变量。

  第一种方法将增加变量的数目，导致问题的维数增大。第二种方法正好相反。

  在介绍解的性质之前，先需要了解一下各种各样的解的概念。

  满足 A x = b Ax=b Ax=b的 x x x称为方程组 A x = b Ax=b Ax=b的解，而满足 A x = b Ax=b Ax=b， x ≥ 0 x \geq 0 x≥0的 x x x称为线性规划2-2的容许解。现在要定义一种特殊的容许解-基本容许解，而在介绍基本容许解之前需要介绍另一个概念：基。

定义： A A A的 m m m个线性无关列向量称为基。基中的每个列向量称为基向量，而 A A A中的其余列向量称为非基向量。由全体基向量合成的矩阵称为基矩阵，也简称为基。若基是单位矩阵，则称为标准基。

定义： 在约束 ∑ j = 1 n x j a j = b \sum_{j=1}^{n}x_{j}a_{j}=b ∑j=1n​xj​aj​=b中，确定一个基后，与基向量对应的变量称为基变量，与非基向量对应的变量称为非基变量。

定义： 设 x 0 x_{0} x0​是 A x = b Ax=b Ax=b的一个解。若它有 m m m个分量所对应的 A A A的列向量构成基 B B B,而其余 n − m n-m n−m个分量全部为0，则 x 0 x_{0} x0​称为约束 A x = b Ax=b Ax=b关于基 B B B的基本解。若 x 0 x_{0} x0​还满足 x 0 ≥ 0 x_{0} \geq 0 x0​≥0则 x 0 x_{0} x0​称为约束 A x = b Ax=b Ax=b， x ≥ 0 x \geq 0 x≥0关于基 B B B的基本容许解，也称为线性规划2-2关于基 B B B的基本容许解。

  简单地说，在确定基之后，所有非基变量取值都为0的解是基本解，所有非基变量取值都为0的容许解是基本容许解。

定义：设 B B B是2-2的一个基。若2-2存在关于 B B B的基本容许解，则称B是2-2的容许基；否者称为非容许基。若容许基是单位矩阵，则称为标准容许基。

  上述所涉及到的概念，总结如下，方便复习：

定义： 若基本解中基变量的取值都不为0，则该解称为非退化的；否者称为退化的。若2-2的所有基本容许解都是非退化的，则线性规划2-2称为非退化的；否者称为退化的。

  若线性规划是非退化的，则容许基与其基本容许解是一一对应的。相反地，退化地基本容许解可能与多个容许基相对应，也就是说不同的容许基会有相同的容许解。

  约束： A x = b ,    x ≥ 0 Ax=b, \ \ x \geq 0 Ax=b,  x≥0

  的基本容许解与这组约束所确定的容许集的极点在一定条件下是一一对应的。

定理： 设 A A A是秩为 m m m的 m × n m \times n m×n矩阵， D D D是由约束 A x = b ,    x ≥ 0 Ax=b, \ \ x \geq 0 Ax=b,  x≥0所确定的容许集，则 X X X为 A x = b ,    x ≥ 0 Ax=b, \ \ x \geq 0 Ax=b,  x≥0的基本容许解的充要条件是 x x x为 D D D的极点。

推论： 容许集 D = { x ∣ A x = b ， x ≥ 0 } D=\{x|Ax=b，x \geq 0\} D={x∣Ax=b，x≥0}的极点个数有限。其中假定 A A A是秩为 m m m的 m × n m \times n m×n矩阵。

  这里书上都有证明，这里我引用一位老师的话，定理都是证明给怀疑的人看的，如果你不怀疑，就不需要证明。如果你用过图解法。其实上面这个很好理解的。

定理： 线性规划若有容许解，则必有基本容许解。

定理： 线性规划若有最优解，则必有最优基本容许解。

我的微信公众号名称：小小何先生 公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！