線性規劃——規範型，标準型，基陣、基本解、基本可行解、基變量、非基變量.... 概念梳理

文章目錄

• 前言
• 最優化—線性規劃
• • 模型問題
  • • 線性規劃模型的一般形式（min）
    • 線性規劃規範形式
    • 線性規劃标準型
    • 模型的轉換
    • 線性規劃中的規律
    • • 規範形式頂點的數學描述
      • 标準形式頂點的數學描述
      • 标準形式頂點的等價描述之一
      • 标準形式頂點的等價描述之二
    • 線性規劃标準形式的一些基本概念
    • 線性規劃标準形式的基本定理

前言

此總結參考 清華 王煥剛老師的課，本人隻是渣渣輝。

最優化—線性規劃

模型問題

線性規劃模型的一般形式（min）

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. n > m n>m n>m
2. A A A 的行向量線性無關

模型的轉換

對于模型間的轉換，其實就是一些變量的添加和符号的改變

線性規劃中的規律

一維、二維、三維規劃中：

1. 可行集中任意兩點的連線都在可行集内：凸集
2. 最優解都不在兩個不同點的連線上：頂點
3. 所有頂點的個數有限：有限集

線性規劃的可行集是凸集，标準線性規劃問題也是凸集。

是以高緯要解決的問題是：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】 如果标準線性規劃問題的某個基可行解的相鄰的基可行解都不比它好，那麼這個基可行解就是最優解

綜上所述：對于線性規劃，隻用求得它的基本可行解，就能在有限的基本可行解中找到最優解。