线性规划

此总结参考 清华 王焕刚老师的课，本人只是渣渣辉。

min ⁡ ∑ j = 1 n c j x j  s.t.  ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ p ∑ j = 1 n a i j x j ≥ b i , ∀ p + 1 ≤ i ≤ m x j ≥ 0 , ∀ 1 ≤ j ≤ q ∞ > x j > − ∞ , ∀ q + 1 ≤ j ≤ n \begin{array}{l} \min \sum_{j=1}^{n} c_{j} x_{j} \\ \text { s.t. } \quad \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq p \\ \quad \sum_{j=1}^{n} a_{i j} x_{j} \geq b_{i}, \quad \forall p+1 \leq i \leq m \\ \quad x_{j} \geq 0, \forall 1 \leq j \leq q \\ \quad \infty>x_{j}>-\infty, \forall q+1 \leq j \leq n \end{array} min∑j=1n​cj​xj​ s.t. ∑j=1n​aij​xj​=bi​,∀1≤i≤p∑j=1n​aij​xj​≥bi​,∀p+1≤i≤mxj​≥0,∀1≤j≤q∞>xj​>−∞,∀q+1≤j≤n​

max ⁡ c 1 x 1 + c 2 x 2 + ⋯ + c n x n  目标函数   s.t.  a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m }  等式约束  \left.\begin{array}{ll} \max \quad c_{1} x_{1}+c_{2} x_{2}+\cdots+c_{n} x_{n} & \text { 目标函数 } \\ \text { s.t. } \quad a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1 n} x_{n}=b_{1} \\ \quad \quad \quad a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 n} x_{n}=b_{2} \\ \quad \quad \quad \quad \quad \quad \quad \vdots \\ \quad \quad \quad a_{m 1} x_{1}+a_{m 2} x_{2}+\cdots+a_{m n} x_{n}=b_{m} \end{array}\right\} \text { 等式约束 } maxc1​x1​+c2​x2​+⋯+cn​xn​ s.t. a11​x1​+a12​x2​+⋯+a1n​xn​=b1​a21​x1​+a22​x2​+⋯+a2n​xn​=b2​⋮am1​x1​+am2​x2​+⋯+amn​xn​=bm​​ 目标函数 ⎭⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎫​ 等式约束 

x 1 ≥ 0 x 2 ≥ 0 ⋮ x n ≥ 0 } 决策变量具有非负约束 \left.\begin{array}{c} x_{1} \geq 0 \\ x_{2} \geq 0 \\ \vdots \\ x_{n} \geq 0 \end{array}\right\} \text {决策变量具有非负约束} x1​≥0x2​≥0⋮xn​≥0​⎭⎪⎪⎪⎬⎪⎪⎪⎫​决策变量具有非负约束

min ⁡ (  or  max ⁡ ) ∑ j = 1 n c j x j min ⁡ (  or  max ⁡ ) C T X  s.t.  ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m ⇒  s.t.  A X = b ⃗ x j ≥ 0 , ∀ 1 ≤ j ≤ n X ≥ 0 C = ( c 1 ⋮ c n ) X = ( x 1 ⋮ x n ) A = ( a 11 ⋯ a 1 n ⋮ ⋱ ⋮ a m 1 ⋯ a m n ) b ⃗ = ( b 1 ⋮ b m ) \begin{array}{l} \min (\text { or } \max ) \sum_{j=1}^{n} c_{j} x_{j} \quad\quad\quad\quad\quad\quad\quad\quad \min (\text { or } \max ) C^{T} X \\ \text { s.t. } \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq m \quad \Rightarrow \quad \text { s.t. } \quad A X=\vec{b} \\ x_{j} \geq 0, \forall 1 \leq j \leq n \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad X\geq0\\ C=\left(\begin{array}{c} c_{1} \\ \vdots \\ c_{n} \end{array}\right) \quad X=\left(\begin{array}{c} x_{1} \\ \vdots \\ x_{n} \end{array}\right) \quad A=\left(\begin{array}{ccc} a_{11} & \cdots & a_{1 n} \\ \vdots & \ddots & \vdots \\ a_{m 1} & \cdots & a_{m n} \end{array}\right) \quad \vec{b}=\left(\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right) \end{array} min( or max)∑j=1n​cj​xj​min( or max)CTX s.t. ∑j=1n​aij​xj​=bi​,∀1≤i≤m⇒ s.t. AX=b xj​≥0,∀1≤j≤nX≥0C=⎝⎜⎛​c1​⋮cn​​⎠⎟⎞​X=⎝⎜⎛​x1​⋮xn​​⎠⎟⎞​A=⎝⎜⎛​a11​⋮am1​​⋯⋱⋯​a1n​⋮amn​​⎠⎟⎞​b =⎝⎜⎛​b1​⋮bm​​⎠⎟⎞​​

以后我们所考虑的线性规划标准型为: max ⁡ C T X  s.t.  A X = b ⃗ X ≥ 0 \begin{array}{c} \max C^{T} X \\ \text { s.t. } A X=\vec{b} \\ X \geq 0 \end{array} maxCTX s.t. AX=b X≥0​ 其中 C ∈ R n , X ∈ R n , A ∈ R m × n , b ⃗ ∈ R m , C \in R^{n}, X \in R^{n}, A \in R^{m \times n}, \vec{b} \in R^{m}, C∈Rn,X∈Rn,A∈Rm×n,b ∈Rm, 并假定

对于模型间的转换，其实就是一些变量的添加和符号的改变

一维、二维、三维规划中：

线性规划的可行集是凸集，标准线性规划问题也是凸集。

所以高纬要解决的问题是：1 可行集是否是凸集，2 顶点集为有限集 3 在顶点集中找到最优解

如果这些问题确定了后，关键就是找到顶点了

规范形式可行集 Ω : ∑ j = 1 n a i j x j ≥ b i , ∀ 1 ≤ i ≤ m \Omega: \sum_{j=1}^{n} a_{i j} x_{j} \geq b_{i}, \quad \forall 1 \leq i \leq m Ω:∑j=1n​aij​xj​≥bi​,∀1≤i≤m x j ≥ 0 , ∀ 1 ≤ j ≤ n x_{j} \geq 0, \forall 1 \leq j \leq n xj​≥0,∀1≤j≤n 对任意的 X ∈ Ω , X \in \Omega, X∈Ω, 将所有的线性不等式进行如下划分 ∑ j = 1 n a i j x j = b i , i = k ( 1 ) , ⋯   , k ( m ^ ) , x j = 0 , j = k ( m ^ + 1 ) , ⋯   , k ( n ^ ) ∑ j = 1 n a i j x j > b i , ∀ i ∉ { k ( 1 ) , ⋯   , k ( m ^ ) } , x j > 0 , ∀ j ∉ { k ( m ^ + 1 ) , ⋯   , k ( n ^ ) } \begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, i=k(1), \cdots, k(\hat{m}), x_{j}=0, j=k(\hat{m}+1), \cdots, k(\hat{n}) \\ \sum_{j=1}^{n} a_{i j} x_{j}>b_{i}, \forall i \notin\{k(1), \cdots, k(\hat{m})\}, x_{j}>0, \forall j \notin\{k(\hat{m}+1), \cdots, k(\hat{n})\} \end{array} ∑j=1n​aij​xj​=bi​,i=k(1),⋯,k(m^),xj​=0,j=k(m^+1),⋯,k(n^)∑j=1n​aij​xj​>bi​,∀i∈/​{k(1),⋯,k(m^)},xj​>0,∀j∈/​{k(m^+1),⋯,k(n^)}​ 那么当且仅当等式方程组的解唯一时 X X X 是 Ω \Omega Ω 的顶点

Ω : ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m x j ≥ 0 , ∀ 1 ≤ j ≤ n \begin{aligned} \Omega: & \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq m \\ & x_{j} \geq 0, \forall 1 \leq j \leq n \end{aligned} Ω:​j=1∑n​aij​xj​=bi​,∀1≤i≤mxj​≥0,∀1≤j≤n​

由于由等式方程约束条件产生的只能是等式，所以 对任意的 X ∈ Ω X \in \Omega X∈Ω 可进行如下划分（注意 n > m ） n>m ） n>m） ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m , x j > 0 , j = k ( 1 ) , ⋯   , k ( m ^ ) x j = 0 , j = k ( m ^ + 1 ) , ⋯   , k ( n ) \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m, \begin{array}{c} x_{j}>0, j=k(1), \cdots, k(\hat{m}) \\ x_{j}=0, j=k(\hat{m}+1), \cdots, k(n) \end{array} j=1∑n​aij​xj​=bi​,∀1≤i≤m,xj​>0,j=k(1),⋯,k(m^)xj​=0,j=k(m^+1),⋯,k(n)​ 当且仅当上面的等式方程组解唯一时 X X X 是 Ω \Omega Ω 的顶点

总结：如果一个点 X ∈ Ω X \in \Omega X∈Ω，使得一些约束求作用（使得一些不等式的等号成立），若对于这些成立的约束构成的线性方程组来说，它的解不只是 X X X，那么 X X X不是 Ω \Omega Ω的顶点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yh711aPx-1607047943335)(最优化—线性规划.assets/image-20201204092908344.png)]

∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m ⇒ ∑ j = 1 n ( a 1 j ⋮ a m j ) x j = ( b 1 ⋮ b m ) ⇒ ∑ j = 1 n P j x j = b ⃗ P j = ( a 1 j , ⋯   , a m j ) T , ∀ 1 ≤ j ≤ n x j > 0 , j = k ( 1 ) , ⋯   , k ( m ^ ) ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m , x j = 0 , j = k ( m ^ + 1 ) , ⋯   , k ( n ) ⇒ x k ( j ) > 0 , ∀ 1 ≤ j ≤ m ^ , ∑ j = 1 m P k ( j ) x k ( j ) = b ⃗ \begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m \Rightarrow \sum_{j=1}^{n}\left(\begin{array}{c} a_{1 j} \\ \vdots \\ a_{m j} \end{array}\right) x_{j}=\left(\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right) \\ \Rightarrow \sum_{j=1}^{n} P_{j} x_{j}=\vec{b} \quad P_{j}=\left(a_{1 j}, \cdots, a_{m j}\right)^{T}, \forall 1 \leq j \leq n \\ \qquad \begin{array}{c} x_{j}>0, \quad j=k(1), \cdots, k(\hat{m}) \\ \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m, x_{j}=0, \quad j=k(\hat{m}+1), \cdots, k(n) \\ \Rightarrow x_{k(j)}>0, \forall 1 \leq j \leq \hat{m}, \quad \sum_{j=1}^{m} P_{k(j)} x_{k(j)}=\vec{b} \end{array} \end{array} ∑j=1n​aij​xj​=bi​,∀1≤i≤m⇒∑j=1n​⎝⎜⎛​a1j​⋮amj​​⎠⎟⎞​xj​=⎝⎜⎛​b1​⋮bm​​⎠⎟⎞​⇒∑j=1n​Pj​xj​=b Pj​=(a1j​,⋯,amj​)T,∀1≤j≤nxj​>0,j=k(1),⋯,k(m^)∑j=1n​aij​xj​=bi​,∀1≤i≤m,xj​=0,j=k(m^+1),⋯,k(n)⇒xk(j)​>0,∀1≤j≤m^,∑j=1m​Pk(j)​xk(j)​=b ​​

当且仅当 X ∈ Ω X \in \Omega X∈Ω 的正分量对应的系数向量线性无关

如果 ( P 1 , ⋯   , P n ) \left(P_{1}, \cdots, P_{n}\right) (P1​,⋯,Pn​) 是行满秩矩阵，那么 X X X 是可行集 Ω = { X = ( x 1 , ⋯   , x n ) T ∣ ∑ j = 1 n P j x j = b ⃗ , x j ≥ 0 , ∀ 1 ≤ j ≤ n } \Omega=\left\{X=\left(x_{1}, \cdots, x_{n}\right)^{T} \mid \sum_{j=1}^{n} P_{j} x_{j}=\vec{b}, x_{j} \geq 0, \forall 1 \leq j \leq n\right\} Ω={X=(x1​,⋯,xn​)T∣j=1∑n​Pj​xj​=b ,xj​≥0,∀1≤j≤n} 的顶点充要条件是：存在可逆方阵 ( P k ( 1 ) , ⋯   , P k ( m ) ) \left(P_{k(1)}, \cdots, P_{k(m)}\right) (Pk(1)​,⋯,Pk(m)​), 可以把 X X X 的分量划分为 x k ( j ) , j = 1 , ⋯   , n , x_{k(j)}, j=1, \cdots, n, xk(j)​,j=1,⋯,n, 使满足 ( x k ( 1 ) ⋮ x k ( m ) ) = ( P k ( 1 ) , ⋯   , P k ( m ) ) − 1 b ⃗ ≥ 0 , x k ( j ) = 0 , ∀ m + 1 ≤ j ≤ n \left(\begin{array}{c}x_{k(1)} \\ \vdots \\ x_{k(m)}\end{array}\right)=\left(P_{k(1)}, \cdots, P_{k(m)}\right)^{-1} \vec{b} \geq 0, \quad x_{k(j)}=0, \forall m+1 \leq j \leq n ⎝⎜⎛​xk(1)​⋮xk(m)​​⎠⎟⎞​=(Pk(1)​,⋯,Pk(m)​)−1b ≥0,xk(j)​=0,∀m+1≤j≤n 主要理由 : ∑ j = 1 m P k ( j ) x k ( j ) = b ⃗ ⇒  正分量对应的系   数向量线性无关  \large : \sum_{j=1}^{m} P_{k(j)} x_{k(j)}=\vec{b} \Rightarrow \begin{array}{l}\text { 正分量对应的系 } \\ \text { 数向量线性无关 }\end{array} :∑j=1m​Pk(j)​xk(j)​=b ⇒ 正分量对应的系  数向量线性无关 ​

基阵、基本解、基本可行解、基变量、非基变量 称可逆矩阵 ( P k ( 1 ) , ⋯   , P k ( m ) ) \left(P_{k(1)}, \cdots, P_{k(m)}\right) (Pk(1)​,⋯,Pk(m)​) 为基阵 称其分量由下式决定的 X X X 为基本解 ( x k ( 1 ) ⋮ x k ( m ) ) = ( P k ( 1 ) , ⋯   , P k ( m ) ) − 1 b ⃗ , x k ( j ) = 0 , ∀ m + 1 ≤ j ≤ n \left(\begin{array}{c} x_{k(1)} \\ \vdots \\ x_{k(m)} \end{array}\right)=\left(P_{k(1)}, \cdots, P_{k(m)}\right)^{-1} \vec{b}, x_{k(j)}=0, \forall m+1 \leq j \leq n ⎝⎜⎛​xk(1)​⋮xk(m)​​⎠⎟⎞​=(Pk(1)​,⋯,Pk(m)​)−1b ,xk(j)​=0,∀m+1≤j≤n 称可行的基本解为基本可行解 称基阵对应变量为基变量，其余变量为非基变量 标准线性规划的基本可行解就是可行集的顶点 标准线性规划的可行集的顶点个数总是有限的

【定理1】 一个标准形式线性规划问题若有可行解，则至少存在一个基本可行解 【定理2】 一个标准形式线性规划问题若有有限的最优目标值，则一定存在一个基本可行解是最优解 【定理3】 如果标准线性规划问题的某个基可行解的相邻的基可行解都不比它好，那么这个基可行解就是最优解

综上所述：对于线性规划，只用求得它的基本可行解，就能在有限的基本可行解中找到最优解。