運籌學(xué)（第三版）：第1章 線性規(guī)劃與單純形法

1、清華大學(xué)出版社 1 二、線性規(guī)劃與目標規(guī)劃 n第1章 線性規(guī)劃與單純形法 n第2章 對偶理論與靈敏度分析 n第3章 運輸問題 n第4章 目標規(guī)劃 清華大學(xué)出版社 2 第1章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法 n第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型 n第2節(jié) 線性規(guī)劃問題的幾何意義 n第3節(jié) 單純形法 n第4節(jié) 單純形法的計算步驟 n第5節(jié) 單純形法的進一步討論 n第6節(jié) 應(yīng)用舉例 清華大學(xué)出版社 3 第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型 v1.1 問題的提出 v1.2 圖解法 v1.3 線性規(guī)劃問題的標準形式 v1.4 線性規(guī)劃問題的解的概念 清華大學(xué)出版社 4 第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型

2、線性規(guī)劃是運籌學(xué)的一個重要分支。線性規(guī)劃在理線性規(guī)劃是運籌學(xué)的一個重要分支。線性規(guī)劃在理 論上比較成熟，在實用中的應(yīng)用日益廣泛與深入。特別論上比較成熟，在實用中的應(yīng)用日益廣泛與深入。特別 是在電子計算機能處理成千上萬個約束條件和決策變量是在電子計算機能處理成千上萬個約束條件和決策變量 的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。 從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交 通運輸業(yè)、軍事、經(jīng)濟計劃和管理決策等領(lǐng)域都可以發(fā)通運輸業(yè)、軍事、經(jīng)濟計劃和管理決策等領(lǐng)域都可以發(fā) 揮作用。它已是現(xiàn)

3、代科學(xué)管理的重要手段之一。解線性揮作用。它已是現(xiàn)代科學(xué)管理的重要手段之一。解線性 規(guī)劃問題的方法有多種，以下僅介紹規(guī)劃問題的方法有多種，以下僅介紹單純形法單純形法 。 清華大學(xué)出版社 5 1.1 問題的提出 1.1 1.1 問題的提出問題的提出 例例 1 某工廠在計劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知 生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗， 如表1-1所示。 資源 產(chǎn) 品 擁有量 設(shè) 備1 2 8臺時 原材料 A 40 16 kg 原材料 B04 12 kg 每生產(chǎn)一件產(chǎn)品每生產(chǎn)一件產(chǎn)品可獲利可獲利2 2元，每生產(chǎn)一件產(chǎn)品元，每生產(chǎn)一件產(chǎn)品可獲利可獲利 3 3元，問應(yīng)如何安排計劃使該

4、工廠獲利最多元，問應(yīng)如何安排計劃使該工廠獲利最多? ? 清華大學(xué)出版社 6 1.1 問題的提出 稱它們?yōu)闆Q策變量。 產(chǎn)品的數(shù)量，分別表示計劃生產(chǎn)設(shè)III, 21 xx 12416482 2121 21 x;x;xx ,x ,x 這是約束條件。即 有量的限制的數(shù)量多少，受資源擁生產(chǎn) 0 21 x,x,即生產(chǎn)的產(chǎn)品不能是負值 這是目標。最大如何安排生產(chǎn)，使利潤, 用數(shù)學(xué)關(guān)系式描述這個問題用數(shù)學(xué)關(guān)系式描述這個問題 清華大學(xué)出版社 7 1.1 問題的提出 0 124 164 82 32 21 2 1 21 21 x ,x x x xx : xxzmax 約束條件 目標函數(shù) 得到本問題的數(shù)學(xué)模型為: 這

5、就是一個最簡單的線性規(guī)劃模型。這就是一個最簡單的線性規(guī)劃模型。 清華大學(xué)出版社 8 1.1 問題的提出 例例 2 靠近某河流有兩個化工廠 (見圖1-1)，流經(jīng)第一化工廠的 河流流量為每天500萬立方米， 在兩個工廠之間有一條流量為 每天200萬立方米的支流。 圖1-1 化工廠1每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，化工廠2每天 排放的工業(yè)污水為1.4萬立方米。從化工廠1排出的污水流到化工廠2前， 有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于 0.2%。因此兩個工廠都需處理一部分工業(yè)污水?；S1處理污水的成本 是1000元/萬立方米,化工廠2處理污水的成本是800元/

6、萬立方米。問: 在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水， 使兩個工廠處理工業(yè)污水的總費用最小。使兩個工廠處理工業(yè)污水的總費用最小。 清華大學(xué)出版社 9 1.1 問題的提出 設(shè)設(shè)： 化工廠1每天處理的污水量為x1萬立方米； 化工廠2每天處理的污水量為x2萬立方米 1000 2 700 41280 2 1000 2 500 2 2 21 1 )x.()x(. )x( 工廠后的水質(zhì)要求：經(jīng)第 工廠前的水質(zhì)要求：經(jīng)第 建模型之前的分析和計算 清華大學(xué)出版社 10 1.1 問題的提出 0, 4 . 1 2 6 . 18 . 0 1 800100

7、0min 21 2 1 21 1 21 xx x x xx x xxz 約束條件 目標函數(shù) 得到本問題的數(shù)學(xué)模型為： 清華大學(xué)出版社 11 1.1 問題的提出 l每一個線性規(guī)劃問題都用一組決策變量 表示某一方案，這組決策變量的值代表一個具體方案。 一般這些變量的取值是非負且連續(xù)的； l都有關(guān)于各種資源和資源使用情況的技術(shù)數(shù)據(jù)，創(chuàng)造新 價值的數(shù)據(jù)； l存在可以量化的約束條件，這些約束條件可以用一組線 性等式或線性不等式來表示; l都有一個達到某一目標的要求，可用決策變量的線性函 數(shù)(稱為目標函數(shù))來表示。按問題的要求不同，要求目 標函數(shù)實現(xiàn)最大化或最小化。 n x,x,x 21 )n,j;m,i

8、 (c;a jij 11 上述兩個問題具有的共同特征：上述兩個問題具有的共同特征： 清華大學(xué)出版社 12 1.1 問題的提出 n mmnmm n n n cc b b b aaa aaa aaa m xxx 21 2 1 21 22221 11211 21 c 2 1 價值系數(shù) 動 活 資源 決策變量 決策變量及各類系數(shù)之間的對應(yīng)關(guān)系 清華大學(xué)出版社 13 1.1 問題的提出 ).(x,x ,x b),(xaxaxa ).( b),(xaxaxa b),(xaxaxa ).(xcxcxczmax(min) n mnmmm nn nn nn 310 21 11 21 2211 22222121

9、11212111 2211 約束條件 目標函數(shù) 線性規(guī)劃模型的一般形式 清華大學(xué)出版社 14 1.2 圖解法 1.2 1.2 圖解法圖解法 例1是一個二維線性規(guī)劃問題，因而可用作圖法直觀地進行求 解。 0, 124 164 82 32max 21 2 1 21 21 xx x x xx xxz 清華大學(xué)出版社 15 1.2 圖解法 表示一簇平行線 33 2 12 z xx 21 32xxzmax 目標值在（4，2）點，達到最大值14 清華大學(xué)出版社 16 1.2 圖解法 （1）無窮多最優(yōu)解(多重最優(yōu)解)，見圖1-4。 （2）無界解，見圖1-5-1。 （3）無可行解，見圖1-5-2。 通過圖解法

10、，可觀察到線性規(guī)劃的解可能出現(xiàn) 的幾種情況： 清華大學(xué)出版社 17 1.2 圖解法 目標函數(shù) max z=2x1+4x2 圖1-4 無窮多最優(yōu)解（多重最優(yōu)解） 清華大學(xué)出版社 18 1.2 圖解法 ox ,x xx xx xxzmax 21 21 1 21 2 42 圖1-5-1 無界解 清華大學(xué)出版社 19 當(dāng)存在相互矛盾的約束條件時，線性規(guī)劃問題的可 行域為空集。例如，如果在例1的數(shù)學(xué)模型中增加一 個約束條件: 則該問題的可行域即為空集空集，即無可行解， 85 . 1 21 xx 無可行解的情形 1.2 圖解法 清華大學(xué)出版社 20 85 . 1 21 xx 增加的約束條件 圖1-5-2

11、不存在可行域 1.2 圖解法 清華大學(xué)出版社 21 1.3 線性規(guī)劃問題的標準型式 0 a czmax 21 2211 22222121 11212111 2211 1 n nnmnmm nn nn nn x ,x ,x bxaxaxa bxaxaxa bxaxax xcxcx :M 約束條件： 目標函數(shù)： 1.3 線性規(guī)劃問題的標準型式線性規(guī)劃問題的標準型式 清華大學(xué)出版社 22 1.3 線性規(guī)劃問題的標準型式 n,j; b b b b; a a a P; x x x X ;c,c,cC n,j,x bxP CXzmax:M m mj j j j n n j n j jj 21 210 2

12、1 2 1 2 1 21 1 1 約束條件： 目標函數(shù)： 用向量形式表示的標準形式線性規(guī)劃 線性規(guī)劃問題的幾種表示形式 清華大學(xué)出版社 23 1.3 線性規(guī)劃問題的標準型式 用矩陣形式表示的標準形式線性規(guī)劃用矩陣形式表示的標準形式線性規(guī)劃 T n n mnm n x,x,xX ;P,P,P aa aa A X bAX CXzmax:M 21 m 1 21 1 111 1 b b b 0 0 0 0 決策變量向量： ；資源向量：零向量： 系數(shù)矩陣： 約束條件： 目標函數(shù)： 清華大學(xué)出版社 24 1.3 線性規(guī)劃問題的標準型式 kkk xxx (1) 若要求目標函數(shù)實現(xiàn)最小化，即min z =CX

13、，則只需將目標函數(shù)最小 化變換求目標函數(shù)最大化，即令z= z，于是得到max z= CX。 (2) 約束條件為不等式。分兩種情況討論： l若約束條件為“”型不等式，則可在不等式左端加入非負松弛變 量，把原“”型不等式變?yōu)榈仁郊s束； l若約束條件為“”型不等式，則可在不等式左端減去一個非負剩 余變量(也稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束。 (3) 若存在取值無約束的變量xk,可令 0, kk xx 如何將一般線性規(guī)劃轉(zhuǎn)化為標準形式的線性規(guī)劃如何將一般線性規(guī)劃轉(zhuǎn)化為標準形式的線性規(guī)劃 清華大學(xué)出版社 25 1.3 線性規(guī)劃問題的標準型式 例例3 將例1的數(shù)學(xué)模型化為標準形式的線性規(guī)劃。 例

14、1的數(shù)學(xué)模型在加入了松馳變量后變?yōu)?1212345 12312 141 252 121234 max23max23000 2828 416416 412412 ,0,0 zxxzxxxxx xxxxx xxx xxx x xx x x x x 清華大學(xué)出版社 26 1.3 線性規(guī)劃問題的標準型式 例例4 將下述線性規(guī)劃問題化為標準形式線性規(guī)劃 為無約束 321 321 321 321 321 0 53 3 7 32 x;x ,x xxx xxx xxx xxxzmin (1) 用x4x5替換x3，其中x4，x50； (2) 在第一個約束不等式左端加入松弛變量x6； (3) 在第二個約束不等式左

15、端減去剩余變量x7； (4) 令z= z，將求min z 改為求max z 即可得到該問題的標準型。 清華大學(xué)出版社 27 1.3 線性規(guī)劃問題的標準型式 例例4 例4的標準型 0, 5)(23 2)( 7)( 00)(32max 765421 421 75421 65421 765421 xxxxxx xxxx xxxxx xxxxx xxxxxxz 清華大學(xué)出版社 28 1.4 線性規(guī)劃問題的解概念 v1.可行解(Feasible Solution) v2.基(Basic) v3.基可行解(Basic Feasible Solution, BF) v4.可行基(Feasible Basis

16、) 清華大學(xué)出版社 29 1.4 線性規(guī)劃問題的解的概念 v定義 滿足約束條件(1-5)、(1-6)式的解X=(x1,x2，xn)T， 稱為線性規(guī)劃問題的可行解，其中使目標函數(shù)達到最 大值的可行解可行解稱為最優(yōu)解最優(yōu)解。 )(n ,j,x )(m,i ,bxa )(xczmax j n j ijij n j jj 61210 5121 41 1 1 1. 可行解可行解 清華大學(xué)出版社 30 1.4 線性規(guī)劃問題的解的概念 為基變量。 為基向量， 為線性規(guī)劃問題的基。稱 階非奇異子矩陣中的是系數(shù)矩陣 ), 2 , 1(x ), 2 , 1(P , B 0BA j j 21 21 22221 11

17、211 mj mj PPP aaa aaa aaa B mmB m mmmm m m 2. 基，基向量，基變量基，基向量，基變量 清華大學(xué)出版社 31 1.4 線性規(guī)劃問題的解的概念 是基可行解 4321 0Q,Q,Q,Q, 滿足非負條件（1-6）的基解，稱為基可行解. 基可行解的非 零分量的數(shù)目不大于m，并且都是非負的。 3 基可行解基可行解 清華大學(xué)出版社 32 1.4 線性規(guī)劃問題的解的概念 l 對應(yīng)于基可行解的基，稱為可行基。 l 約束方程組(1-5)具有的基解的數(shù)目最多是 個，一般 基可行解的數(shù)目要小于基解的數(shù)目。 l 以上提到了幾種解的概念，它們之間的關(guān)系可用圖1-6 表明。 l

18、說明：當(dāng)基解中的非零分量的個數(shù)小于m時，該基解是退化解。 在以下討論時，假設(shè)不出現(xiàn)退化的情況。 m n C 4 可行基可行基 清華大學(xué)出版社 33 1.4 線性規(guī)劃問題的解的概念 m n C 不同解之間的關(guān)系不同解之間的關(guān)系 清華大學(xué)出版社 34 第2節(jié) 線性規(guī)劃問題的幾何意義 v2.1 基本概念 v2.2 幾個定理 清華大學(xué)出版社 35 2.1 基本概念 1. 凸集 2. 凸組合 3. 頂點 清華大學(xué)出版社 36 2.1 基本概念 v定義 設(shè)K是n維歐氏空間的一點集，若任意兩點X(1)K， X(2)K的連線上的所有點X(1)+(1)X(2)K，(01)， 則稱K為凸集。 圖1-7 1.凸集凸

19、集 清華大學(xué)出版社 37 2.1 基本概念 v實心圓，實心球體，實心立方體等都是凸集，圓環(huán)不是凸集。 從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖1-7 中的(a)(b)是凸集，(c)不是凸集。 v圖1-2中的陰影部分是凸集。 v任何兩個凸集的交集是凸集，見圖1-7(d) 清華大學(xué)出版社 38 2.1 基本概念 v設(shè)X(1)，X(2)，X(k)是n維歐氏空間En中的k個點。若存 在1，2，k，且0i1, i=1,2,，k 使 X=1X(1)+2X(2)+kX(k) 則稱X為X(1)，X(2)，X(k)的一個凸組合（當(dāng)0i1時， 稱為嚴格凸組合）。 k i i 1 1 2. 凸組合凸組合 清

20、華大學(xué)出版社 39 2.1 基本概念 v設(shè)K是凸集，XK；若X不能用不同的兩點X(1)K和 X(2)K的線性組合表示為 X=X(1)+(1)X(2)，(01) 則稱X為K的一個頂點(或極點)。 圖中的0，Q1,2,3,4都是頂點。 3. 頂點頂點 清華大學(xué)出版社 40 2.2 幾個定理 v定理定理1 : 若線性規(guī)劃問題存在可行域，則其可行域 是凸集。 n j jjj xbxPXD 1 0, 清華大學(xué)出版社 41 2.2 幾個定理 v定理1的證明：只需證明D中任意兩點連線上的點必然在D內(nèi)即可。設(shè) 是D內(nèi)的任意兩點；且X(1)X(2)。 T n T n xxxX xxxX 22 2 2 1 2 1

21、1 2 1 1 1 , , 則有 n j jjj n j jjj njxbxP njxbxP 1 22 1 11 , 2 , 1, 0, , 2 , 1, 0, 令 X=(x1，x2，xn) T 為 x (1),x(2)連線上的任意一點，即 X=X (1)+(1-)X(2) (01) X 的每一個分量是 21 )1 ( jjj xxx，將它代入約束條件， 得到 清華大學(xué)出版社 42 2.2 幾個定理 bbbb xPxPxP xxPxP n j n j jjjj n j jj n j n j jjjjj 11 22 1 1 11 21 1 又因 01 , 0, 0, 21 jj xx ，所以 x

22、j0，j=1,2,n。 由此可見 XD，D 是凸集。 證畢。 清華大學(xué)出版社 43 2.2 幾個定理 v引理引理 1 線性規(guī)劃問題的可行解X=(x1,x2,，xn)T為基可行 解的充要條件是：X的正分量所對應(yīng)的系數(shù)列向量是線 性獨立的。 證證: : (1) 必要性由基可行解的定義可知。 (2) 充分性若向量P1，P2，Pk線性獨立， 則必有 km；當(dāng) k=m 時，它們恰構(gòu)成一個基，從而 X=(x1,x2,xk,00)為相應(yīng)的基可行解。當(dāng) km 時， 則一定可以從其余的列向量中取出 m-k 個與 P1，P2，Pk 構(gòu)成最大的線性獨立向量組，其對應(yīng)的解恰為 X， 所以根據(jù)定義它是基可行解。 清華大

23、學(xué)出版社 44 2.2 幾個定理 定理定理2 線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點。 證：證：不失一般性，假設(shè)基可行解X的前m個分量為正。 故 現(xiàn)分兩步來討論，分別用反證法。 m j jj bxP 1 清華大學(xué)出版社 45 2.2 幾個定理 (1) 若X不是基可行解，則它一定不是可行域D的頂點。 根據(jù)引理1，若X不是基可行解，則其正分量所對應(yīng)的系數(shù) 列向量P1，P2，Pm線性相關(guān)，即存在一組不全為零的 數(shù)i,i=1,2,m，使得 1P1+2P2+mPm=0 (1-9) 用一個數(shù)0乘(1-9)式再分別與(1-8)式相加和相減，得 (x11)P1+(x22)P2+(xm m)Pm=b (x

24、1+1)P1+(x2+2)P2+(xm+m)Pm=b 清華大學(xué)出版社 46 2.2 幾個定理 因X 不是可行域D的頂點，故在可行域D中可找到不同的兩點 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使得 X=X(1)+(1) X(2) ， 01 設(shè)X是基可行解，對應(yīng)的向量組P1Pm線性獨立，故當(dāng)jm時，有 xj=xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的兩點，因而滿足 m j m j jjjj bxPbxP 11 21 與 （2）若X不是可行域D的頂點，則它一定不是基可行解。 m j jjj xxP 1 21 0 將兩式相

25、減，得 因X(1)X(2)，所以上式中的系數(shù)不全為零，故向量組P1,P2,，Pm線 性相關(guān)，與假設(shè)矛盾，即X不是基可行解。 清華大學(xué)出版社 47 2.2 幾個定理 v引理引理2 若K是有界凸集，則 任何一點XK可表示為K的 頂點的凸組合。 本引理的證明從略，用以下例 子說明本引理的結(jié)論。 v例例5 設(shè)X是三角形中任意一 點，X(1)，X(2)和X(3)是三角形 的三個頂點，試用三個頂點 的坐標表示X(見圖1-8) 圖1-8 清華大學(xué)出版社 48 2.2 幾個定理 解：解：任選一頂點X(2)，做一條連線XX(2)，并延長交于X(1)、X(3)連接線上 一點X。因為X是X(1)、X(3)連線上一點

26、，故可用X(1)、X(3)線性組合表示 為 X=X(1)+(1)X(3) 01 又因X是X與X(2)連線上的一個點，故 X=X+(1 )X(2) 01 將X的表達式代入上式得到 X=X(1)+(1)X(3)+(1)X(2) =X(1)+(1 )X(3)+(1)X(2) 令 1=,2=(1 ),3=(1 )，得到 X=1X(1)+2X(2)+3X(3) ii=1, 0i1 清華大學(xué)出版社 49 2.2 幾個定理 v定理定理 3 若可行域有界，則線性規(guī)劃問題的目標函數(shù) 一定可以在其可行域的頂點上達到最優(yōu)。 證：證： 設(shè)X(1),X(2)，X(k)是可行域的頂點，若X(0)不是 頂點，且目標函數(shù)在X

27、(0)處達到最優(yōu)z*=CX(0)(標準型是 z=max z)。 因X(0)不是頂點，所以它可以用D的頂點線性表示為 代入目標函數(shù)得 k i k i ii i iix X 11 0 1, 0, k i k i i i i i CXXCCX 11 0 清華大學(xué)出版社 50 2.2 幾個定理 在所有的頂點中必然能找到某一個頂點X(m)，使CX(m)是所有 CX(i)中最大者。并且將X(m)代替(1-10)式中的所有X(i)，得到 m k i m i k i i i CXCXCX 11 由此得到 X(0)CX(m) 根據(jù)假設(shè)CX(0)是最大值，所以只能有 CX(0)=CX(m) 即目標函數(shù)在頂點X(m

28、)處也達到最大值。 清華大學(xué)出版社 51 2.2 幾個定理 1 X， 2 X， k X k i k i ii i i XX 11 1, 0, 有時，目標函數(shù)可能在多個頂點處達到最大，這時在這些頂點 的凸組合上也達到最大值，這時線性規(guī)劃問題有無限多個最優(yōu) 解。 假設(shè) 是目標函數(shù)達到最大值的頂點，則對這些頂點的凸組合，有 k i i i k i i i XCXCXC 11 清華大學(xué)出版社 52 2.2 幾個定理 kimXC i , 2 , 1, 設(shè)： 于是： 另外，若可行域為無界，則可能無最優(yōu)解，也可能有最優(yōu)解， 若有最優(yōu)解，也必定在某頂點上得到。 mmXC k i i 1 清華大學(xué)出版社 53

29、基本結(jié)論 l線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無 界域，它們有有限個頂點，線性規(guī)劃問題的每個基可行解對應(yīng) 可行域的一個頂點。 l若線性規(guī)劃問題有最優(yōu)解，必在某頂點上得到。雖然頂點數(shù) 目是有限的，若采用“枚舉法”找所有基可行解，然后一一比 較，最終必然能找到最優(yōu)解。但當(dāng)n,m較大時，這種辦法是行 不通的，所以要繼續(xù)討論如何有效尋找最優(yōu)解的方法。本課程 將主要介紹單純形法單純形法(simplex method)。 l備注：單純形備注：單純形(單純形是指單純形是指0維中的點，一維中的線段，二維中的三角形，三維中的點，一維中的線段，二維中的三角形，三 維中的四面體，維中的四面體，n維空

30、間中的有維空間中的有n+1個頂點的多面體。例如在三維空間中的四面體，個頂點的多面體。例如在三維空間中的四面體， 其頂點分別為其頂點分別為(0,0,0)，(1,0,0)，(0,1,0)，(0,0,1)。 清華大學(xué)出版社 54 第第3節(jié)節(jié) 單純形法單純形法 v3.1 舉例 v3.2 初始基可行解的確定 v3.3 最優(yōu)性檢驗與解的判斷 v3.4 基變換 v3.5 迭代（旋轉(zhuǎn)運算） 清華大學(xué)出版社 55 單純形法求解線性規(guī)劃的思路： 一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于 方程個數(shù)，這時有不定的解。但可以從線性方程組中方程個數(shù)，這時有不定的解。但可以從線性

31、方程組中 找出一個個的單純形，找出一個個的單純形，每一個單純形可以求得一組解每一個單純形可以求得一組解， 然后再判斷該解使目標函數(shù)值是增大還是變小，決定然后再判斷該解使目標函數(shù)值是增大還是變小，決定 下一步選擇的單純形。下一步選擇的單純形。這就是這就是迭代迭代，直到目標函數(shù)實，直到目標函數(shù)實 現(xiàn)最大值或最小值為止。這樣，問題就得到了最優(yōu)解，現(xiàn)最大值或最小值為止。這樣，問題就得到了最優(yōu)解， 先舉一例來說明。先舉一例來說明。 清華大學(xué)出版社 56 3.1 舉例 例例6 試以例1來討論如何用單純形法求解。 解：已知本例的標準型為： )111 (00032max 54321 xxxxxz 5 , 2

32、, 10 124 )121 (164 82 52 41 321 jx xx xx xxx j 清華大學(xué)出版社 57 3.1 舉例 約束條件(1-12)式的系數(shù)矩陣為 從(1-12)式可看到x3,x4,x5的系數(shù)構(gòu)成的列向量 1 0 0 0 1 0 040 004 121 , 54321 PPPPPA 1 0 0 , 0 1 0 , 0 0 1 543 PPP 清華大學(xué)出版社 58 3.1 舉例 P3 ,P4,P5是線性獨立的，這些向量構(gòu)成一個基B 。 對應(yīng)于B的變量x3,x4,x5為基變量. 124 )121 (164 82 52 41 321 xx xx xxx 從(1-12)式中可以得到（

33、1-13） )131 ( 412 416 28 25 14 213 xx xx xxx 清華大學(xué)出版社 59 3.1 舉例 將(1-13)式代入目標函數(shù)(1-11)： 得到 當(dāng)令非基變量x1=x2=0，便得到z=0。這時得到一個基可 行解X(0) X(0)=(0,0,8,16,12)T 本基可行解的經(jīng)濟含義是：工廠沒有安排生產(chǎn)產(chǎn)品、 ，資源都沒有被利用，所以工廠的利潤為z=0。 )111 (00032max 54321 xxxxxz )141 (320 21 xxz 清華大學(xué)出版社 60 3.1 舉例 從分析目標函數(shù)的表達式從分析目標函數(shù)的表達式(1-14)可以看到：可以看到： 非基變量非基變

34、量x1,x2(即沒有安排生產(chǎn)產(chǎn)品即沒有安排生產(chǎn)產(chǎn)品，)的系的系 數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標 函數(shù)的值就可能增大。從經(jīng)濟意義上講，安排生產(chǎn)函數(shù)的值就可能增大。從經(jīng)濟意義上講，安排生產(chǎn) 產(chǎn)品產(chǎn)品或或，就可以使工廠的利潤指標增加。所以，就可以使工廠的利潤指標增加。所以 只要在目標函數(shù)只要在目標函數(shù)(1-14)的表達式中還存在有正系數(shù)的的表達式中還存在有正系數(shù)的 非基變量，這表示目標函數(shù)值還有增加的可能，就非基變量，這表示目標函數(shù)值還有增加的可能，就 需要將非基變量與基變量進行對換。需要將非基變量與基變量進行對換。 清華大學(xué)出版社 61 3

35、.1 舉例 v如何確定換入、換出變量 一般選擇正系數(shù)最大的那個非基變量x2為換入變 量，將它換到基變量中，同時還要確定基變量中 哪一個換出來成為非基變量。 可按以下方法來確定換出變量： o分析(1-13)式，當(dāng)將x2定為換入變量后，必須從x3,x4,x5 中確定一個換出變量，并保證其余的變量仍然非負，即 x3,x4,x50。 清華大學(xué)出版社 62 3.1 舉例 v如何確定換入、換出變量 當(dāng)x1=0時，由(1-13)式得到 )151 ( 0412 016 028 25 4 23 xx x xx )131 ( 412 416 28 25 14 213 xx xx xxx 清華大學(xué)出版社 63 3.

36、1 舉例 v如何確定換入、換出變量 當(dāng)x2取何值時，才能滿足非負要求呢？ 從(1-15)式可看出，只有選擇 x2=min(8/2,-,12/4)=3時，才能使(1-15)式成立。 因當(dāng)x2=3時，基變量x5=0，這就決定用x2去替換x5。 以上數(shù)學(xué)描述說明，每生產(chǎn)一件產(chǎn)品，需要用 掉的各種資源數(shù)為(2，0，4)。由這些資源中的薄 弱環(huán)節(jié)，就確定了產(chǎn)品的產(chǎn)量。 這里就是由原材料B的數(shù)量確定了產(chǎn)品的產(chǎn)量 x2=12/4=3件。 清華大學(xué)出版社 64 3.1 舉例 v如何確定換入、換出變量 為了求得以x3,x4,x2為基變量的一個基可行解和進一步分析 問題，需將(1-13)中x2的位置與x5的位置對

37、換，得到 )131 ( 412 416 28 25 14 213 xx xx xxx )161 ( 3124 2416 182 52 14 123 xx xx xxx 清華大學(xué)出版社 65 3.1 舉例 v將(1-16)式中x2的系數(shù)列向量變換為單位列向量。 其運算步驟是： v=/4；=-2;=, v并將結(jié)果仍按原順序排列有： 171 3 4 1 3 2416 1 2 1 2 52 14 513 xx xx xxx 高斯消去法高斯消去法 清華大學(xué)出版社 66 3.1 舉例 v再將(1-17)式代入目標函數(shù)(1-11)式得到 清華大學(xué)出版社 67 3.1 舉例 從目標函數(shù)的表達式(1-18)可看

38、到，非基變量x1的系數(shù)是正的，說明 目標函數(shù)值還可以增大，即X(1)還不是最優(yōu)解。 于是，再用上述方法確定換入、換出變量，繼續(xù)迭代，得到另一個 基可行解X(2) X(2)=(2,3,0,8,0)T 再經(jīng)過一次迭代，又得到一個基可行解X(3) X(3)=(4,2,0,0,4)T 而這時得到目標函數(shù)的表達式是： z=141.5x3 0.125x4 (1-19) 再檢查(1-19)式，可見所有非基變量x3,x4的系數(shù)都是負數(shù)，這說明若 要用剩余資源x3,x4，就必須支付附加費用。 所以當(dāng)x3=x4=0時，即不再利用這些資源時，目標函數(shù)達到最大值。 所以X(3)是最優(yōu)解。即當(dāng)產(chǎn)品生產(chǎn)4件，產(chǎn)品生產(chǎn)2件

39、時，工廠可 以得到最大利潤。 清華大學(xué)出版社 68 小結(jié) v通過上例，可將每步迭代得到的結(jié)果與圖解法做一對比。 v例1的線性規(guī)劃問題是二維的，即有兩個變量x1,x2。當(dāng)加入松弛變量 x3,x4,x5后，變換為高維的。這時可以想象，滿足所有約束條件的可行域 是高維空間中的凸多面體(凸集)。該凸多面體上的頂點，就是基可行解。 初始基可行解為 X(0)=(0,0,8,16,12)T，對應(yīng)于圖1-2中的原點(0，0)； X(1)=(0,3,2,16,0)T對應(yīng)于圖中的Q4點(0，3)； X(2)=(2，3，0，8，0)T對應(yīng) 于Q3點(2，3)；最優(yōu)解X(3)=(4，2，0，0，4)T相當(dāng)于圖中的 Q

40、2點(4，2)。 從初始基可行解X(0)開始迭代， 依次得到X(1)，X(2)，X(3)，相當(dāng) 于圖中的目標函數(shù)平移時，從0 點開始，首先碰到Q4，然后碰到 Q3，最后達到Q2。 清華大學(xué)出版社 69 3.2 初始基可行解的確定 v為了確定初始基可行解，要首先找出初始可行基， 其方法如下。 (1)直接觀察 (2)加松弛變量 (3)加非負的人工變量 清華大學(xué)出版社 70 3.2 初始基可行解的確定 從線性規(guī)劃問題 的系數(shù)構(gòu)成的列向量Pj(j=1,2,n)中，通過直接觀察，找 出一個初始可行基 njx bxP xcz j n j jj n ij jj , 2 , 10 211 201max 1 1

41、 1 1 , 21 m PPPB (1)直接觀察直接觀察 清華大學(xué)出版社 71 3.2 初始基可行解的確定 對所有約束條件為“”形式的不等式，利用化標準型的方 法，在每個約束條件的左端加上一個松弛變量。經(jīng)過整理， 重新對xj及aij (i=1,2,m; j=1,2,n)進行編號，則可得下列 方程組（x1,x2,xm 為松弛變量）： njx bxaxax bxaxax bxaxax j mnmmmmm nnmm nnmm , 2 , 1, 0 221 11, 2211,22 1111, 11 (2)加松弛變量加松弛變量 清華大學(xué)出版社 72 3.2 初始基可行解的確定 于是，(1-22)中含有一

42、個mm階單位矩陣，初始可行基 B即可取該單位矩陣。 將(1-22)式每個等式移項得 1 1 1 , 21 m PPPB nmmmmmm nnmm nnmm xaxabx xaxabx xaxabx 11, 211, 222 111, 111 231 清華大學(xué)出版社 73 3.2 初始基可行解的確定 令xm+1=xm+2=xn=0，由(1-23)式可得 xi=bi (i=1,2,m) 得到一個初始基可行解。 又因bi0(在1-3節(jié)中已做過規(guī)定)，所以得到一個初始基 可行解 X=(x1,x2,xm,0，0)T nm個 =(b1,b2,bm,0，0)T nm個 清華大學(xué)出版社 74 3.2 初始基可

43、行解的確定 v對所有約束條件為“”形式的不等式及等式約束情況， 若不存在單位矩陣時，可采用人造基方法。 即對不等式約束，減去一個非負的剩余變量，再加上一個非負 的人工變量； 對于等式約束，再加上一個非負的人工變量 v這樣，總能在新的約束條件系數(shù)構(gòu)成的矩陣中得到一個 單位矩陣。 (3)加非負的人工變量加非負的人工變量 清華大學(xué)出版社 75 3.3 最優(yōu)性檢驗與解的判別 v由于線性規(guī)劃問題的求解可能出現(xiàn)唯一最優(yōu)解、無 窮多最優(yōu)解、無界解和無可行解等四種情況，因此， 需要建立解的判別準則。一般情況下，經(jīng)過迭代后 (1-23)式變成 241, 2 , 1, 1 n mj jijii mixabx 清華

44、大學(xué)出版社 76 3.3 最優(yōu)性檢驗與解的判別 將 代入目標函數(shù)(1-20)式， 整理后得 251 )( 111 11 11 11 11 111 111 m i n mj j m i ijijii n mj jj n mj jij m i i m i ii n mj jj n mj jij m i i m i ii n mj jj m i n mj jijii m i n mj jjii n j jj xaccbc xcxacbc xcxacbc xcxabcxcxcxcz n mj mi j x ij a i b i x 1 ), 2 , 1, ( 清華大學(xué)出版社 77 3.3 最優(yōu)性檢驗與

45、解的判別 m i m i ijijii nmjaczbcz 11 0 , 1, n mj jjj xzczz 1 0 )261 (于是 nmjzc jjj , 1設(shè) 271 1 0 n mj jj xzz 令 清華大學(xué)出版社 78 3.3 最優(yōu)性檢驗與解的判別 若 為對應(yīng)于基B的一個基可行 解，且對于一切j=m+1,n，有j0，則X(0)為最優(yōu)解。 稱j為檢驗數(shù)。 T m bbbX0 , 0 , 2 1 0 1.最優(yōu)解的判別定理最優(yōu)解的判別定理 清華大學(xué)出版社 79 3.3 最優(yōu)性檢驗與解的判別 若 為一個基可行解，對于一切 j=m+1，,n，有j0，又存在某個非基變量的檢驗數(shù) m+k=0，則

46、線性規(guī)劃問題有無窮多最優(yōu)解。 證證: 只需將非基變量xm+k換入基變量中，找到一個新基 可行解X(1)。因m+k=0，由(1-27)知z=z0，故X(1)也是最 優(yōu)解。由2.2節(jié)的定理3可知，X(0)和X(1)連線上所有點 都是最優(yōu)解。 T m bbbX0 , 0 , 2 1 0 2.無窮多最優(yōu)解判別定理無窮多最優(yōu)解判別定理 清華大學(xué)出版社 80 3.3 最優(yōu)性檢驗與解的判別 若 為一基可行解， 有一個m+k0，并且對i=1,2,，m，有ai,m+k0，那么 該線性規(guī)劃問題具有無界解(或稱無最優(yōu)解)。 證證: 構(gòu)造一個新的解 X(1)，它的分量為 T m bbbX0 , 0 , 2 1 0 k

47、mjnmjx x abx j km kmiii 并且, 1; 0 0 1 1 , 1 3無界解判別定理無界解判別定理 清華大學(xué)出版社 81 3.3 最優(yōu)性檢驗與解的判別 因 ，所以對任意的0都是可行解， 把x(1)代入目標函數(shù)內(nèi)，得到 z=z0+m+k 因m+k0，故當(dāng)+，則z+，故該問題 目標函數(shù)無界。 0 , kmi a 清華大學(xué)出版社 82 3.3 最優(yōu)性檢驗與解的判別 v其它情形 以上討論都是針對標準型的，即求目標函數(shù)極大 化時的情況。當(dāng)要求目標函數(shù)極小化時，一種情 況是將其化為標準型。 如果不化為標準型，只需在上述1，2點中把j0改 為j0，第3點中將m+k0改寫為m+k0即可。 清

48、華大學(xué)出版社 83 3.4 基變換 v若初始基可行解X(0)不是最優(yōu)解及不能判別無 界時，需要找一個新的基可行解。 v具體做法是 從原可行解基中換一個列向量(當(dāng)然要保證線性獨 立)，得到一個新的可行基，稱為基變換。為了換 基，先要確定換入變量，再確定換出變量，讓它 們相應(yīng)的系數(shù)列向量進行對換，就得到一個新的 基可行解。 清華大學(xué)出版社 84 1.換入變量的確定 v由(1-27)式可知，當(dāng)某些j0時，若xj增大，則目 標函數(shù)值還可以增大。這時需要將某個非基變量 xj換到基變量中去(稱為換入變量)。 v若有兩個以上的j0，那么選哪個非基變量作為 換入變量呢?為了使目標函數(shù)值增加得快，從直觀 上看應(yīng)

49、選j0中的較大者，即由 應(yīng)選擇xk為換入變量。 kj j 0max 清華大學(xué)出版社 85 2.換出變量的確定 v設(shè)P1，P2，Pm是一組線性獨立的向量組，它們對 應(yīng)的基可行解是X(0)，將它代入約束方程組(1-21)得到 m i ii bPx 1 0 281 其他的向量Pm+1,Pm+2,Pm+t,Pn都可以用P1，P2，Pm線性 表示。 若確定非基變量Pm+t為換入變量，必然可以找到一組不全為0的 數(shù)(i=1,2,m)使得 2910 1 , 1 , m i itmitm m i itmitm PPPP或 清華大學(xué)出版社 86 2.換出變量的確定 在(1-29)式兩邊同乘一個正數(shù)，然后將它加到

50、(1-28)式上， 得到 301 m 1i , 0 11 , 0 bPPx bPPPx tmitmii m i m i itmitmii 或 清華大學(xué)出版社 87 2.換出變量的確定 清華大學(xué)出版社 88 2.換出變量的確定 tmi l tmi tmi i i xx , 0 , , 0 0min 這時 xi為換出變量。按最小比值確定值， 稱為最小比值規(guī)則。將 tmi l x , 0 代入 X 中， 便得到新的基可行解。 清華大學(xué)出版社 89 2.換出變量的確定 v新的基可行解為 個分量第 個分量第 tm xx x x xX l tml l tmm tml l m tmm tml l , 0 ,

51、 0 , , 0 , , 0 , , 0 0 1 , , 0 0 1 1 清華大學(xué)出版社 90 2.換出變量的確定 v由此得到由X(0)轉(zhuǎn)換到X(1)的各分量的轉(zhuǎn)換公式 li x li x x x tml l tmi tml l i i , 0 , , 0 0 1 清華大學(xué)出版社 91 2.換出變量的確定 這里 是原基可行解X(0)的分量； 是新基可行解X(1)的各 分量； vi,m+t是換入向量Pm+t對應(yīng)原來一組基向量的坐標。 v現(xiàn)在的問題是，這個新解X(1)的m個非零分量對應(yīng)的列向量 是否獨立?事實上，因為X(0)的第一個分量對應(yīng)于X(1)的相應(yīng) 分量是零，即 0 , 0 tmll x

52、0 i x 1 i x 清華大學(xué)出版社 92 2.換出變量的確定 其中 , 0 1 x均不為零，根據(jù)規(guī)則(最小比值)， l,m+t0。X(1)中的 m 個非零分量對應(yīng)的 m 個列向量是 Pj(j=1,2,m,jl)和Pm+t。若這組向量不是線性獨立， 則一定可以找到不全為零的數(shù)j，使 m j jjtm ljPaP 1 )311 (, m j jtmjtm PP 1 , )321 (, 成立。又因 將(1-32)式減(1-31)式得到 m j ltmljjtmj PPa 1 , 0)( 清華大學(xué)出版社 93 2.換出變量的確定 由于上式中至少有l(wèi),m+t0，所以上式表明P1，P2，Pm是線性相關(guān)

53、，這與 假設(shè)相矛盾。 由此可見，X(1)的m個非零分量對應(yīng)的列向量Pj(j=1,2,m,jl)與Pm+t是線性 獨立的，即經(jīng)過基變換得到的解是基可行解。 實際上，從一個基可行解到另一個基可行解的變換，就是進行一次基變換。 從幾何意義上講，就是從可行域的一個頂點轉(zhuǎn)向另一個頂點。 清華大學(xué)出版社 94 3.5 迭代(旋轉(zhuǎn)運算) 上述討論的基可行解的轉(zhuǎn)換方法是用向量方程描述的，在實際 計算時不太方便，因此下面介紹系數(shù)矩陣法系數(shù)矩陣法。 考慮以下形式的約束方程組 mnmkmkmmmm lnklkmmll nnkkmm nnkkmm bxaxaxax bxaxaxax bxaxaxax bxaxaxax

54、 11, ln11, 22211, 22 11111, 11 331 一般線性規(guī)劃問題的約束方程組中加入松弛變量或人工變量后， 很容易得到上述形式 清華大學(xué)出版社 95 3.5 迭代(旋轉(zhuǎn)運算) lk l ik ik i ia b a a b 0min 設(shè)x1,x2,xm為基變量，對應(yīng)的系數(shù)矩陣是mm單位陣I，它 是可行基。令非基變量xm+1,xm+2,xn為零，即可得到一個基 可行解。 若它不是最優(yōu)解，則要另找一個使目標函數(shù)值增大的基可行 解。這時從非基變量中確定xk為換入變量。顯然這時為 在迭代過程中可表示為 0min lk l ik ik i i a b a a b , iki ab 其

55、中 是經(jīng)過迭代后對應(yīng)于 的元素值。iki ab , 清華大學(xué)出版社 96 3.5 迭代(旋轉(zhuǎn)運算) 按規(guī)則確定xl為換出變量，xk, xl的系數(shù)列向量分別為 個分量第 l P a a a a P l mk lk k k k 0 0 1 0 ; 2 1 清華大學(xué)出版社 97 3.5 迭代(旋轉(zhuǎn)運算) 為了使xk與xl進行對換，須把Pk變?yōu)閱挝幌蛄浚@可以通過 (1-33)式系數(shù)矩陣的增廣矩陣進行初等變換來實現(xiàn)。 )341 ( 1 1 1 1 ln 1 1, 1, 11, 1 11 m l mn n mkmm lkml km nkmml b b b a a a aa aa aa bxxxxxx 清

56、華大學(xué)出版社 98 3.5 迭代(旋轉(zhuǎn)運算) )351 (, 1 , 0 , 0 , 1 , 0 ln 1, lk l lklk ml lk a b a a a a a 變換的步驟是： (1) 將增廣矩陣(1-34)式中的第l行除以al k，得到 (2) 將(1-34)式中xk列的各元素，除al k變換為1以外，其他都 應(yīng)變換為零。其他行的變換是將(1-35)式乘以aik(il)后，從 (1-34)式的第i行減去，得到新的第i行。 ik lk l iik lk ik lk ml mi lk ik a a b ba a a aa a a a a a ln ln 1, 1, , 0 , 0 , 0

57、 , 0 清華大學(xué)出版社 99 3.5 迭代(旋轉(zhuǎn)運算) 由此可得到變換后系數(shù)矩陣各元素的變換關(guān)系式 li a b lib a a b b li a a lia a a a a lk l i lk ik i i lk lj ik lk lj ij ij ; 是變換后的新元素。 , iij ba 清華大學(xué)出版社 100 3.5 迭代(旋轉(zhuǎn)運算) (3) 經(jīng)過初等變換后的新增廣矩陣是 )361 ( 010 10 1 0 001 1, ln 1, 1 1 1, 1 1 11 mmnmm lk mk lml lk nm lk k nkmml baa a a baa a baa a a bxxxxxx

58、清華大學(xué)出版社 101 3.5 迭代(旋轉(zhuǎn)運算) (4) 由(1-36)式中可以看到x1,x2,xk,，xm的系數(shù)列向量構(gòu) 成mm單位矩陣;它是可行基。當(dāng)非基變量xm+1,，xl,xn 為零時，就得到一個基可行解X(1) T mll bbbbX0 , 0 , 0 , 1 1 1 1 在上述系數(shù)矩陣的變換中，元素al k稱為主元素主元素，它所在列稱 為主元列，它所在行稱為主元行，元素al k位置變換后為1。 清華大學(xué)出版社 102 3.5 迭代(旋轉(zhuǎn)運算) 例例7 7 試用上述方法計算例6的兩個基變換。 解：例6的約束方程組的系數(shù)矩陣寫成增廣矩陣 12 16 8 10040 01004 0012

59、1 54321 bxxxxx 當(dāng)以x3,x4,x5為基變量，x1,x2為非基變量，令x1,x2=0，可得到一 個基可行解 X(0)=(0,0,8,16,12)T 清華大學(xué)出版社 103 3.5 迭代(旋轉(zhuǎn)運算) 現(xiàn)用x2去替換x5，于是將x3,x4, x2的系數(shù)矩陣變換為單 位矩陣，經(jīng)變換后為 3 16 2 4/10010 01004 2/10101 54321 bxxxxx 令非基變量x1,x5=0，得到新的基可行解 X(1)=(0,3,2,16,0)T 清華大學(xué)出版社 104 第4節(jié) 單純型法的計算步驟 v4.1 單純型表 v4.2 計算步驟 清華大學(xué)出版社 105 4.1 單純型表 v為

60、了便于理解計算關(guān)系，現(xiàn)設(shè)計一種計算表，稱為單純形表， 其功能與增廣矩陣相似。 v將(1-22)式與目標函數(shù)組成n+1個變量，m+1個方程的方程組。 清華大學(xué)出版社 106 線性規(guī)劃的方程組 0 1111 11 221122 111111 nnmmmm mnmnmmmm nnmm n n mm xcxcxcxcz bxaxax bxaxax bxaxax 清華大學(xué)出版社 107 線性規(guī)劃的方程組 v為了便于迭代運算，可將上述方程組寫成增廣矩陣形式 121 1,111 2,122 ,1 121 0100 0010 0001 10 mmn mn mn m mmnm mmn zxxxxxb aab a