高中數學第五章線性規劃方法 單純形表法的計算步驟

第五章 線性規劃方法 Linear Programming

(資料圖片)

5.1 線性規劃問題的一般形式5.2 線性規劃問題的解5.2.1 基本解的產生與轉換5.2.2 基本可行解的產生與轉換5.2.3 基本可行解的變換條件1. 最優性條件2. 非負性條件 5.3 單純形算法 The Simplex Method

5.1 線性規劃問題的一般形式

5.2 線性規劃問題的解

基本解：只滿足約束方程的解。 基本可行解：同時滿足約束方程和變量非負約束的解。 最優解：使目標函數取得最小值的基本可行解。

5.2.1 基本解的產生與轉換

線性規劃問題的約束方程實際上是一個包括n個變量和m個方程（n>m）的線性方程組，由于變量個數多于方程數，故有多個滿足方程的解。 若取n-m個變量并令其等于0，解出另外的m個不為0的變量，就可得到一個基本解。 在這樣的基本解中，稱n-m個為0的變量為非基本變量，另外的m個變量為基本變量。

5.2.2 基本可行解的產生與轉換

根據線性規劃問題的不同特征，一個初始基本可行解的獲得可分為以下兩種情況：

如果除變量非負約束之外的約束條件全是“ ≤ \leq ≤”的不等式約束，而且對應的常數向量中的元素均為正數，此時只要引入松弛變量，并以松弛變量為基本變量，得到的解就是一個基本可行解。如果除變量非負約束之外的約束條件中還包含等式約束，此時可以在各個等式約束中分別引進一個與松弛變量類似的變量，稱為人工變量，然后建立一個輔助規劃問題求解此輔助規劃問題，就可以得到一個基本可行解。

5.2.3 基本可行解的變換條件

1. 最優性條件

2. 非負性條件

5.3 單純形算法 The Simplex Method

SIMPLEXTABLEx 1    x 2    ?    x n x_1 \ \ x_2 \ \ \cdots \ \ x_n x1  x2  ?  xnx n + 1    x n + 2    ?    x n + m x_{n+1}\ \ x_{n+2}\ \ \cdots\ \ x_{n+m} xn+1  xn+2  ?  xn+mb i b_i bi

Basic VariableCoefficientsc 1      c 2    ?    c n c_1\ \ \ \ c_2\ \ \cdots\ \ c_n c1    c2  ?  cn0              0      ?      0 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots \ \ \ \ 0 0            0    ?    0c 0 c_0 c0

x n + 1 x_{n+1} xn+10a 11    a 12 ? a 1 n a_{11} \ \ a_{12} \cdots a_{1n} a11  a12?a1n1              0      ?      0 1 \ \ \ \ \ \ \ \ \ \ \ \ 0 \ \ \ \ \cdots \ \ \ \ 0 1            0    ?    0b n + 1 b_{n+1} bn+1

x n + 2 x_{n+2} xn+20a 11    a 12 ? a 1 n a_{11} \ \ a_{12} \cdots a_{1n} a11  a12?a1n0              1      ?      0 0 \ \ \ \ \ \ \ \ \ \ \ \ 1\ \ \ \ \cdots\ \ \ \ 0 0            1    ?    0b n + 1 b_{n+1} bn+1

? \vdots ?? \vdots ??          ?              ? \vdots\ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \vdots ?        ?            ?0              0      ?      0 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots\ \ \ \ 0 0            0    ?    0? \vdots ?

x n + m x_{n+m} xn+m0a 11    a 12 ? a 1 n a_{11}\ \ a_{12} \cdots a_{1n} a11  a12?a1n0              0      ?      1 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots\ \ \ \ 1 0            0    ?    1b n + 1 b_{n+1} bn+1

Judgementnumber σ j \sigma_j σjσ 1     σ 2    ? σ n \sigma_1 \ \ \ \sigma_2 \ \ \cdots \sigma_n σ1   σ2  ?σn0              0      ?      1 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots\ \ \ \ 1 0            0    ?    1f ( X ) f(X) f(X)

單純形表法的計算步驟：

給定一個初始基本可行解 X 0 X^0 X0，并置k=0；計算判別數： σ j = c j ? ∑ i = 1 m c i a i j         ( j = 1 , 2 , ? ? , n ) \sigma_j=c_j-\sum^m_{i=1}c_ia_{ij} \ \ \ \ \ \ \ (j=1,2,\cdots,n) σj=cj?i=1∑mciaij       (j=1,2,?,n) 若 σ j ≥ 0 ( j = 1 , 2 , ? ? , n ) \sigma_j\geq 0(j=1,2,\cdots,n) σj≥0(j=1,2,?,n)，令 X ? = X k ,   f ( X ? ) = f ( X k ) X^*=X^k,\ f(X^*)=f(X^k) X?=Xk, f(X?)=f(Xk)，結束計算；否則轉步驟3;選主元 a l k a_{lk} alk σ k = m i n { σ j ∣ σ j < 0 , j = 1 , 2 , ? ? , n } b l a l k = m i n { b i a i k ∣ a i k > 0   ( i = 1 , 2 , ? ? , m ) } \sigma_k=min \{\sigma_j|\sigma_j<0,j=1,2,\cdots,n\} min="">0 \ (i=1,2,\cdots,m)\} σk=min{σj∣σj<0,j=1,2,?,n}alkbl=min{aikbi∣aik>0 (i=1,2,?,m)}以 a l k a_{lk} alk為主元進行消元變換，得到新的基本可行解 X k + 1 X^{k+1} Xk+1，令k=k+1，轉步驟2。

其中，判別式： σ j = c j ? ∑ i = 1 m c i a i j         ( j = 1 , 2 , ? ? , n ) \sigma_j=c_j-\sum^m_{i=1}c_ia_{ij} \ \ \ \ \ \ \ (j=1,2,\cdots,n) σj=cj?i=1∑mciaij       (j=1,2,?,n) i代表行 j代表列（基本變量對應的各列判別式為0，非基本變量對應的各列判別式等于該列頂端的系數減去各列中各個系數 a i j a_{ij} aij與左側系數 c i c_{i} ci的乘積 ）