高中數(shù)學(xué)第五章線(xiàn)性規(guī)劃方法 單純形表法的計(jì)算步驟

第五章 線(xiàn)性規(guī)劃方法 Linear Programming

(資料圖片)

5.1 線(xiàn)性規(guī)劃問(wèn)題的一般形式5.2 線(xiàn)性規(guī)劃問(wèn)題的解5.2.1 基本解的產(chǎn)生與轉(zhuǎn)換5.2.2 基本可行解的產(chǎn)生與轉(zhuǎn)換5.2.3 基本可行解的變換條件1. 最優(yōu)性條件2. 非負(fù)性條件 5.3 單純形算法 The Simplex Method

5.1 線(xiàn)性規(guī)劃問(wèn)題的一般形式

5.2 線(xiàn)性規(guī)劃問(wèn)題的解

基本解：只滿(mǎn)足約束方程的解。 基本可行解：同時(shí)滿(mǎn)足約束方程和變量非負(fù)約束的解。 最優(yōu)解：使目標(biāo)函數(shù)取得最小值的基本可行解。

5.2.1 基本解的產(chǎn)生與轉(zhuǎn)換

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

5.2.2 基本可行解的產(chǎn)生與轉(zhuǎn)換

根據(jù)線(xiàn)性規(guī)劃問(wèn)題的不同特征，一個(gè)初始基本可行解的獲得可分為以下兩種情況：

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

5.2.3 基本可行解的變換條件

1. 最優(yōu)性條件

2. 非負(fù)性條件

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)

單純形表法的計(jì)算步驟：

給定一個(gè)初始基本可行解 X 0 X^0 X0，并置k=0；計(jì)算判別數(shù)： σ 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)，結(jié)束計(jì)算；否則轉(zhuǎn)步驟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為主元進(jìn)行消元變換，得到新的基本可行解 X k + 1 X^{k+1} Xk+1，令k=k+1，轉(zhuǎn)步驟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代表列（基本變量對(duì)應(yīng)的各列判別式為0，非基本變量對(duì)應(yīng)的各列判別式等于該列頂端的系數(shù)減去各列中各個(gè)系數(shù) a i j a_{ij} aij與左側(cè)系數(shù) c i c_{i} ci的乘積 ）