線性規(guī)劃線性規(guī)劃問題單純形法

1、第二章線性規(guī)劃及圖解法1第一講第二章 線性規(guī)劃及圖解法2問題的提出解決有限資源在有競爭的使用方向中如何進行最佳分配。線性規(guī)劃是運籌學(xué)的一個重要分支，也是運籌學(xué)中應(yīng)用最廣泛的方法之一。自1947年旦茨基（G. B. Dantzig）提出了一般線性規(guī)劃問題求解的方法單純形法（simplex method）之后，線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟管理和工業(yè)生產(chǎn)中遇到的實際問題。調(diào)查表明，在世界500家最大的企業(yè)中，有85%的企業(yè)都曾使用線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。線性規(guī)劃 Linear Programming（LP）3本講中我們將討論什么是線性規(guī)劃

2、問題，線性規(guī)劃問題的數(shù)學(xué)表示，基本概念和圖解方法。線性規(guī)劃問題是什么樣的一類問題呢？ 請看案例線性規(guī)劃 Linear Programming（LP）4線性規(guī)劃 Linear Programming（LP）曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。案 例 河流污染治理規(guī)劃問題5線性規(guī)劃 Linear Programming（LP）曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案 例 河流污染治理規(guī)劃問題6線性規(guī)劃 Linear Programming（LP）曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜

3、，清清江水黑如泥。今日認識未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案 例 河流污染治理規(guī)劃問題7線性規(guī)劃 Linear Programming（LP）今日認識未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍。曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案 例 河流污染治理規(guī)劃問題8線性規(guī)劃 Linear Programming（LP）案 例 河流污染治理規(guī)劃問題背景資料:長江流域某區(qū)域內(nèi)有9化工廠，各廠每月產(chǎn)生的工業(yè)污水量如表-1，流經(jīng)各化工廠的

4、河流流量如表-2，各化工廠治理工業(yè)污水的成本如表-3。上游廠排放的污水流到相鄰下游廠以前，有20%可自然凈化。 根據(jù)環(huán)保標準河流中此種工業(yè)污水的含量不應(yīng)超過0.2%。從該區(qū)域整體考慮，各化工廠應(yīng)該分別處理多少工業(yè)污水才能既滿足環(huán)保要求，又使9化工廠治理工業(yè)污水的總費用最少。9背景資料:線性規(guī)劃 Linear Programming（LP）化工廠11.2化工廠42化工廠72化工廠21化工廠51化工廠80.8化工廠33化工廠61化工廠91.5表-1 污水產(chǎn)生量 單位：萬m3表-2 流經(jīng)各化工廠的河流流量 單位：萬m3表-3 治理工業(yè)污水的成本 單位：百萬元/萬m3化工廠1500化工廠41200化工

5、廠71200化工廠2300化工廠5600化工廠8200化工廠31800化工廠6400化工廠9700化工廠13化工廠44化工廠71化工廠25化工廠55化工廠82化工廠32化工廠66化工廠9310線性規(guī)劃 Linear Programming（LP）194582637問題分析：區(qū)域污染治理的決策各個化工廠應(yīng)處理的工業(yè)污水量（或應(yīng)排放的工業(yè)污水量）。區(qū)域污染治理的約束即滿足環(huán)保要求排放工業(yè)污水（區(qū)域內(nèi)河流中任何點檢測都應(yīng)符合環(huán)保標準）。區(qū)域污染治理的目標總治理成本最少。11線性規(guī)劃 Linear Programming（LP）194582637模型描述：設(shè)第i個化工廠應(yīng)處理的工業(yè)污水量為Xi萬m3，

6、則根據(jù)問題描述的情況以化工廠1、2、 、9 加以分析則可得如下近似關(guān)系式對化工廠2應(yīng)有 （1-X2）/ 300 0.2%對化工廠8應(yīng)有 （0.8-X8）/200 0.2%對化工廠1應(yīng)有 （1.2-X1）+ 0.8（1-X2）+（0.8-X8） /500 0.2%12線性規(guī)劃 Linear Programming（LP）194582637對化工廠9應(yīng)有 （1.5-X9）/ 700 0.2%對化工廠7應(yīng)有 （2-X7）+ 0.8（1.5-X9） / 1200 0.2% 此外顯然還應(yīng)有 Xi 0 （i=1，2，3 8，9）綜上所述決策者所需考慮的區(qū)域內(nèi)各個化工廠應(yīng)處理的工業(yè)污水量 Xi應(yīng)滿足上述所有

7、不等式方程。我們將這些不等式方程構(gòu)成的方程組稱為污水治理的約束條件。13線性規(guī)劃 Linear Programming（LP）194582637另一方面污水治理的總成本可表示為Z（單位：百萬元） Z = 3X1+ 5X2+ 2X3+ 4X4+ 5X5+ 6X6+ 1X7+ 2X8+ 3X9 而決策者的目標是： 確定滿足約束條件的Xi使得Z取得最小值。將上述分析歸納后即可得如下數(shù)學(xué)符合模型：14線性規(guī)劃 Linear Programming（LP）河流污染治理規(guī)劃問題數(shù)學(xué)模型（整理之后）194582637Min Z= 3X1 +5X2 +2X3 +4X4 +5X5 +6X6 +1X7 +2X8

8、+3X9 X2 0.4 X8 1.6 X1 +0.8X2 +0.8X8 4.4 X9 0.1 X7 +0.8 X9 0.8 X4 +0.8X7 +0.64X9 2.16 X6 0.2 X5 +0.8X6 0.6 X3 +0.8X4 +0.8X5 +0.64X6 +0.64X7 +5.12X9 9.4 Xi 0 （i=1，2，3，4，5，6，7，8，9）s.t.15線性規(guī)劃 Linear Programming（LP）線性規(guī)劃模型 Linear Programming Model 或 Linear Optimization Model 用線性規(guī)劃方法解決實際經(jīng)濟與管理問題的第一步是分析建立能夠完

9、整描述和反映實際問題的線性規(guī)劃模型。16線性規(guī)劃 Linear Programming（LP）通常建立LP模型有以下幾個基本步驟：確定決策變量： 決策變量是模型要確定的未知變量，也是模型最重要的參數(shù)，是決策者解決實際問題的控制變量。確定目標函數(shù)： 目標函數(shù)決定線性規(guī)劃問題的優(yōu)化方向，是模型的重要組成部分。實際問題的目標可表示為決策變量的一個線性函數(shù)，并根據(jù)目標函數(shù)的實質(zhì)確定優(yōu)化方向，一般可為最大化（max）或最小化（min）。17線性規(guī)劃 Linear Programming（LP）通常建立LP模型有以下幾個步驟：確定約束方程：一個正確的線性規(guī)劃模型應(yīng)能通過約束方程來描述和反映一系列客觀條件或

10、環(huán)境的限制，這些限制通過一系列線性等式或不等式方程組來描述。變量取值限制：一般情況下，決策變量取正值（非負值）。因此，模型中應(yīng)有變量的非負約束即Xj0，但要注意也存在例外的情形。18線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的一般形式:max（或min）z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn （ = ）b1 a21x1 + a22x2 + a2nxn （ = ）b2 s.t. am1x1 + am2x2 + amnxn （ = ）bm xj 0 （j=1，2 n）19線性規(guī)劃 Linear Programming（LP）

11、線性規(guī)劃問題的標準形式1、目標函數(shù)極大化 “ max ”2、等式約束條件 “ = ” 且右端常數(shù)bi非負3、變量非負 “ xj 0 ” max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s.t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）20線性規(guī)劃 Linear Programming（LP）化標準形式的一般步驟目標函數(shù)極小化“極大化”約束條件的右端項 bi0 “bi0” 約束條件為不等式 或 “=”取值無約束（自由）變量“非負變量”取值

12、非正變量“非負變量”線性規(guī)劃問題的標準形式的作用為單純形法求解作準備！21線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問題的求解：（圖解） 如何求解一般的線性規(guī)劃呢？ 下面我們分析一下簡單的情況 只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。22線性規(guī)劃 Linear Programming（LP）基本概念例1（page 11）max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 023線性規(guī)劃 Linear Programmin

13、g（LP）基本概念max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0唯一最優(yōu)解 X=（9/2，3/2）24線性規(guī)劃 Linear Programming（LP）基本概念例 max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 025線性規(guī)劃 Linear Programming（LP）基本概念max Z = 2X1 + X2x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8

14、()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此點是唯一最優(yōu)解，且最優(yōu)目標函數(shù)值 max Z=17.2可行域26線性規(guī)劃 Linear Programming（LP）基本概念max Z = 3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，

15、2）DL0： 0=3X1+5.7X2 max Z min Z（3.8，4）34.2 = 3X1+5.7X2 綠色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標函數(shù)值max Z=34.2是唯一的?？尚杏?7線性規(guī)劃 Linear Programming（LP）基本概念min Z = 5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域此點是唯一最優(yōu)

16、解28線性規(guī)劃 Linear Programming（LP）基本概念min Z = 5X1+4X2x1x2oD可行域29線性規(guī)劃 Linear Programming（LP）基本概念max Z = 5X1+4X2x1x2oD可行域 max Z min Z最優(yōu)解目標值Z趨于無窮30線性規(guī)劃 Linear Programming（LP）基本概念max Z = 5X1+4X2x1x2o可行解域為空31線性規(guī)劃 Linear Programming（LP）基本概念圖解法的啟示線性規(guī)劃問題解的可能情況 a.唯一最優(yōu)解 b.無窮多最優(yōu)解 c.無解（沒有有界最優(yōu)解，無可行解）若線性規(guī)劃問題的可行域非空，則可

17、行域是一個凸集；若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的某個頂點上達到。32線性規(guī)劃 Linear Programming（LP）單純形法 單純形方法是G.B.Danzig于1947年首先發(fā)明的。近50年來，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。本節(jié)討論單純形法的基本概念、原理及算法。33線性規(guī)劃 Linear Programming（LP）單純形法給定線性規(guī)劃問題（標準形式） max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s

18、 .t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）34線性規(guī)劃 Linear Programming（LP）單純形法一、線性規(guī)劃問題的解的概念 可行解 最優(yōu)解 基 基解（基本解） 基可行解 可行基35線性規(guī)劃 Linear Programming（LP）單純形法二、凸集及其頂點 凸集 頂點（極點）凸集凹集36線性規(guī)劃 Linear Programming（LP）12345678基解（可行）基解（不可行）37線性規(guī)劃 Linear Programming（LP）單純形法三、線性規(guī)劃基本定理基本定理 1 線性規(guī)劃所有可行解組成的集合S= X | AX =

19、b，X 0 是凸集。基本定理 2 X是線性規(guī)劃問題的基本可行解的充要條件為是 X 是凸集S= X | AX = b，X 0 的極點?；径ɡ?3 給定線性規(guī)劃問題， A是秩為 m 的 mn 矩陣， （i） 若線性規(guī)劃問題存在可行解，則必存在基本可行解 （ii）若線性規(guī)劃問題存在有界最優(yōu)解，則必存在有界最優(yōu)基本可行解。38線性規(guī)劃 Linear Programming（LP）單純形法單純形法迭代原理及其思路單純形法的初步討論例1.8 求解LP問題 化為標準型Max Z = 50X1+30X2s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0Max Z = 50X1+30X2s

20、.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 X1，X2，X3，X4 0（1.18）39線性規(guī)劃 Linear Programming（LP）單純形法 此線性規(guī)劃問題轉(zhuǎn)化為了一個含有四個變量的標準形線性規(guī)劃問題，X3，X4為松弛變量。為求解上面的LP問題，我們要考慮滿足約束條件s.t.并使 Z 取得Max的X1，X2，X3，X4的值，由此分析如下40線性規(guī)劃 Linear Programming（LP）單純形法確定初始基可行解： 通過觀察可以發(fā)現(xiàn)，松弛變量X3和X4對應(yīng)的等式約束條件中的系數(shù)矩陣為單位矩陣可以作為初始可行基矩陣。因此取 X3，X4為基變量；X1

21、，X2為非基變量。則（1.18）可變?yōu)椋?Max Z = 50X1+30X2 s.t. X3 = 120 - 4X1 - 3X2 X4= 50 - 2X1 - X2 （1.19） X1，X2，X3，X4041線性規(guī)劃 Linear Programming（LP）單純形法典式（1.19）或（1.18）稱為關(guān)于基的典式 1、等式約束條件中顯含基可行解 2、目標函數(shù)中不含基變量Max Z = 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 ( 1.18 ) X1，X2，X3，X4 0Max Z =50X1+30X2s.t. X3 = 120 - 4

22、X1 - 3X2 X4= 50 - 2X1 - X2 （1.19 ） X1，X2，X3，X4042線性規(guī)劃 Linear Programming（LP）單純形法 在典式（1.19）中令： X1=X2 =0，我們得到一個基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ，其對應(yīng)的目標函數(shù)值 Z1 = 50X1 + 30X2 = 043線性規(guī)劃 Linear Programming（LP）單純形法最優(yōu)性檢驗： 基本可行解 X1 是最優(yōu)解嗎？顯然不是。應(yīng)尋找更好的解。從問題的數(shù)學(xué)角度分析，在典式（1.19）的目標函數(shù)中，非基變量X1，X2前的系數(shù)都為正，而此時的X1，

23、X2均取零值，表明只要增加其值，則目標函數(shù)值有增加的可能。因此，將目標函數(shù)中系數(shù)為正的某一非基變量與某一基變量地位對換。44線性規(guī)劃 Linear Programming（LP）單純形法換基迭代： 進行換基就是要從非基變量中選一個變量入基，再從基變量中選一個變量出基。并且換基后仍需滿足： 新的解仍是基本可行解； 目標函數(shù)值將得到改善。45線性規(guī)劃 Linear Programming（LP）單純形法選擇入基變量： 由于在目標函數(shù) Z1 =50X1+30X2 中X1，X2的系數(shù)都為正，哪一個入基都可使目標函數(shù)值得到改善。對于求目標函數(shù)極大化的問題，我們希望目標值增加得越快越好，因此系數(shù)最大的X1

24、入基。選擇出基變量： X1入基后，其值從零增加并由于約束條件的原因會引起其他變量的變化。由典式（1.19）以及變量必須取正值（可行）的條件，我們可以得到下列不等式關(guān)系： X3 = 120 - 4X1- 3X2 0 X4= 50 - 2X1- X2 046線性規(guī)劃 Linear Programming（LP）單純形法 因為迭代后X2仍為非基變量（仍會令其取值為零），則上式可簡化為： 120 - 4X1 0 ，且 50 - 2X1 0 ， 由此可以看出，雖然我們希望X1入基后取正值，取值越大目標值增加越大，但是 X1又得受到以上約束（保證其可行）。 顯然，當取 X1 =min（120/4，50/2

25、）=25時，才能使上述不等式成立，且此時恰使基變量X4變?yōu)榱悖@正好滿足非基變量必須取值零的條件，所以可令X4 出基，這樣，新的基變量變?yōu)閄3 ，X1 ，而 X2 ，X4 成了非基變量，則47線性規(guī)劃 Linear Programming（LP）單純形法約束方程變?yōu)椋?4X1+ X3 =120 - 3X2 2X1 = 50 - X2 - X4化簡后得：新的典式方程 X3 = 20 - X2 + 2X4 X1 = 25 -0.5X2 -0.5X448線性規(guī)劃 Linear Programming（LP）單純形法代入目標函數(shù)可得： Z2 =1250+5X2-25X4 令非基變量X2 =X4 = 0

26、，即可得一個新的基本可行解 X2 =（ 25，0，20，0）T ，其對應(yīng)的目標函數(shù)值Z2 =1250，并完成了第一次迭代。由于目標函數(shù) Z2 =1250+5X2-25X4中X2的系數(shù)仍為正，該解X2仍不是最優(yōu)解。重復(fù)上述迭代過程得到：X2入基，X3出基，則新的典式方程變?yōu)椋?X1 = 15 +0.5X3 - 1.5X4 X2 =20 - X3 + 2X4 Z3 =1350 -5X3 - 15X449線性規(guī)劃 Linear Programming（LP）單純形法第三個基本可行解 X3 =（ 15，20，0，0）T，其對應(yīng)的目標函數(shù)值 Z3 = 1350 。此時松弛變量 都是非基變量（取值為零），

27、這表明資源已用盡；并且目標函數(shù)值 Z3 =1350 -5X3 - 15X4中非基變量X3，X4的系數(shù)全為負值，說明目標函數(shù)已無法進一步改善，因此該解已是最優(yōu)解。50線性規(guī)劃 Linear Programming（LP）單純形法小結(jié)： 單純形法是這樣一種迭代算法如下圖當 Zk 中非基變量的系數(shù)的系數(shù)全為負值時，這時的基本可行解 Xk 即是 線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。X1Z1保持單調(diào)增保持可行性保持可行性保持可行性保持可行性保持單調(diào)增保持單調(diào)增保持單調(diào)增X2X3.XkZ2Z3.Zk 當 Zk 中非基變量的系數(shù)的系數(shù)全為負值時，這時的基本可行解 Xk 即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。51線

28、性規(guī)劃 Linear Programming（LP）單純形表對于給定的線性規(guī)劃問題：max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2s.t. am1x1 + am2x2 + + amnxn bm xj 0 （j=1，2 n） 對此問題添加m個松弛變量后，可得下面線性規(guī)劃問題并且是典式的形式。52線性規(guī)劃 Linear Programming（LP）單純形表線性規(guī)劃的典式max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn + xn+

29、1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2s.t. am1x1 + am2x2 + amnxn + xn+m = bm xj 0 （j=1，2 n，n+1，n+2，n+m）53線性規(guī)劃 Linear Programming（LP）單純形表： 將上面典式中各變量及系數(shù)填寫在一張表格中就形成下面的單純形表cj c1 c2 cn cn+1 cn+2 cn+mCB基解 x1 x2 xn xn+1 xn+2 xn+m0000 xn+1xn+2xn+m b1 b2 bm a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 112mj = c

30、j zj c1 c2 cn 0 0 0j = cj zj 1 2 n n+1 n+2 n+m 54線性規(guī)劃 Linear Programming（LP）單純形表： 上面的單純形表還可以表示成矩陣的形式基解 X XSXSb A Ij C 0基解 XB XN XSXSb B N Ij CB CN 0或55線性規(guī)劃 Linear Programming（LP）單純形法由單純形表進行迭代步驟：選擇 Xj 入基：當 j 行中 j= max i i 0 選擇 Xi 出基：當 i = min bi/aijaij 0 換基迭代：當確定了入基變量 Xj 、出基變量 Xi 后，以 aij 作為主元對單純形表進行取

31、主運算，取主運算即采用初等行變換將主元 aij 所在列，除將 aii 變換為1而外，該列中的其余元素都變換為 0。注意這種變換只能采用初等行變換!56線性規(guī)劃 Linear Programming（LP）單純形法最優(yōu)解檢驗：當?shù)M行至某一步時，j 行中所有檢驗數(shù)均小于等于零，則迭代結(jié)束。表中當前所指基本可行解即為最優(yōu)解。當?shù)M行至某一步時，j 行中所有檢驗數(shù)均小于等于零，且此時至少有一個非基變量所對應(yīng)的檢驗數(shù)k 等于零，則原線性規(guī)劃問題有無窮多個最優(yōu)解。當?shù)M行至某一步時，j 行中至少有一個檢驗數(shù) k 大于零，且該檢驗數(shù)對應(yīng)的列中a1k ，a2k ， amk ，均小于等于零，則原線性規(guī)劃

32、問題最優(yōu)解無界（ max Z +）。57線性規(guī)劃 Linear Programming（LP）單純形方法的矩陣描述：設(shè)線性規(guī)劃問題 max Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I 式） X 0 X ，XS 0其中 b 0 ，I 是 mm 單位矩陣。對上面（I 式）經(jīng)過迭代，并設(shè)最終的最優(yōu)基矩陣為B（不妨設(shè)B 為A 的首m 列，則將（I 式）改寫后有58線性規(guī)劃 Linear Programming（LP）單純形方法的矩陣描述：max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS =

33、 b XB ，XN，XS 0 max Z = CB B -1+（CN- CB B -1）XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS 0 B 式中最優(yōu)目標函數(shù)值Z*= CB B -1 ，檢驗數(shù) CN - CB B -1 0 ， - CB B -1 0單純形方法迭代（I 式）（B 式）59線性規(guī)劃 Linear Programming（LP）單純形方法的矩陣描述：基解 XB XN XSXSb B N Ij CB CN 0基解 XB XN XSXBB -1b I B -1N B -1j 0 CN - CB B 1N - CB

34、 B -1對應(yīng)I 式的單純形表 I 表對應(yīng)B 式的單純形表 B 表迭代60線性規(guī)劃 Linear Programming（LP）單純形表計算步驟舉例給定線性規(guī)劃問題max z = 50X1 + 30X2s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 061線性規(guī)劃 Linear Programming（LP）單純形表計算步驟舉例max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1

35、+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0基XB解B-1bX1X2X3X4X31204310X4502101檢驗數(shù) j 5030002120/450/2X111/201/2250201- 2050- 2520/125211X2150- 1/23/210- 5- 1562線性規(guī)劃 Linear Programming（LP）單純形法的進一步討論人工變量法： 當一般線性規(guī)劃問題標準化之后，我們或可得到一個顯然的基本可行解（如松弛變量作為基變量的一個初始基本可行解），這樣我們就可以馬上進入單純形表的運算步驟。然而，并非所有問題標準化之后我們都可得到一個顯然的初始基本可行解，這時就

36、需要我們首先確定出一個基本可行解作為初始基本可行解。通常采用的是人工變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法： 大M法（罰因子法） 兩階段法63線性規(guī)劃 Linear Programming（LP）單純形法的進一步討論1、大 M 法（罰因子法）max z = - 3X1 + X3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0LPM max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1

37、 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 064線性規(guī)劃 Linear Programming（LP）1、大 M 法LPM max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù) j-30100-M-M

38、65線性規(guī)劃 Linear Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù) j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù) j-3-2M4M10-M0066線性規(guī)劃 Linear Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗數(shù) j-3-2M4M10-M00基XB解

39、B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗數(shù) j-3+6M01+4M03M-4M067線性規(guī)劃 Linear Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗數(shù) j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗數(shù) j00301.5-1.5-M0.5-M68線性規(guī)劃 Linea

40、r Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2檢驗數(shù) j00301.5-1.5-M0.5-M基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4檢驗數(shù) j-9/2000-3/43/4-M-1/4-M69線性規(guī)劃 Linear Programming（LP）采用大 M 法求解線性規(guī)劃問題時可能出現(xiàn)的幾種情況：當采用單純形法求解 L

41、PM 得到最優(yōu)解時，基變量不含任何人工變量，則所得到的最優(yōu)解就是原問題的最優(yōu)解；當采用單純形法求解 LPM 得到最優(yōu)解時，基變量至少含有一個人工變量且非零，則原問題無可行解；當采用單純形法求解 LPM 得到最優(yōu)解時，基變量至少含有一個人工變量且人工變量都為零，則通過變換得到原問題最優(yōu)解；70線性規(guī)劃 Linear Programming（LP）2、兩階段法max z = - 3X1 + X3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0I階段問題 max z = x6 x7 x1 + x2 + x3 + x4 = 4 - 2x

42、1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 071線性規(guī)劃 Linear Programming（LP）2、兩階段法I 階段問題 max z = x6 x7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù) j00000-1-172線

43、性規(guī)劃 Linear Programming（LP）2、兩階段法第I 階段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù) j00000-1-1基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù) j-2400-10073線性規(guī)劃 Linear Programming（LP）2、兩階段法第I 階段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗數(shù) j-2400-100基XB解B-1bX1X2X

44、3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗數(shù) j60403-4074線性規(guī)劃 Linear Programming（LP）2、兩階段法第I 階段基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗數(shù) j60403-40基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗數(shù) j00000-1-175線性規(guī)劃 Linear Programming（LP）2、兩階段法第II 階段基XB

45、解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗數(shù) j00000-1-1基XB解B-1bX1X2X3X4X5X400001-1/2X23011/300X11102/301/2檢驗數(shù) j00303/2-3010076線性規(guī)劃 Linear Programming（LP）2、兩階段法第II 階段基XB解B-1bX1X2X3X4X5X400001-1/2X23011/3009X11102/301/23/2檢驗數(shù) j00303/2基XB解B-1bX1X2X3X4X5X400001-1/2X25/2-1/21

46、00-1/4X33/23/20103/4檢驗數(shù) j-9/2000-3/477線性規(guī)劃 Linear Programming（LP）單純形法中的幾個問題目標函數(shù)極小化時，解的最優(yōu)判別： j 0退化： 一個或幾個基變量等于零，一個簡單易行的避免退化的方法是1974年由勃蘭德（Bland）提出的Bkand 法則。無可行解的判別： 在采用人工變量求解線性規(guī)劃問題得到最優(yōu)解時，如果基變量中仍含有非零人工變量，則原問題無可行解。78線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA （date envelopment analysis）引言 一種基于線性規(guī)劃的用于評價同類型組織（或項

47、目）工作績效相對有效性的特殊工具手段。這類組織例如學(xué)校、醫(yī)院、銀行的分支機構(gòu)、超市的各個營業(yè)部等，各自具有相同的投入相同的產(chǎn)出。衡量這類組織之間的績效高低，通常采用投入產(chǎn)出比這個指標，當各自的投入產(chǎn)出均可折算成同一單位計量時，容易計算出各自的投入產(chǎn)出比并按其大小進行績效排序。但當被衡量的同類型組織有多項投入和多項產(chǎn)出，且不能折算成統(tǒng)一單位時，就無法算出投入產(chǎn)出比的數(shù)值，因而，需采用一種全新的方法進行績效比較。這種方法就是二十世紀七十年代末產(chǎn)生的數(shù)據(jù)包絡(luò)分析DEA。79線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA （date envelopment analysis）

48、引言 1978年，著名運籌學(xué)家、美國德克薩斯大學(xué)教授A.Charnes及W.W.Cooperh和E.Rhodes發(fā)表了一篇重要論文：“Measuring the efficiency of decision making units”（決策單元的有效性度量），刊登在權(quán)威的“歐洲運籌學(xué)雜志”上。正式提出了運籌學(xué)的一個新領(lǐng)域：數(shù)據(jù)包絡(luò)分析。其模型簡稱 C2R 模型。80線性規(guī)劃 Linear Programming（LP）相對有效性評價問題例子 例1：碩士點教育質(zhì)量評價 某系統(tǒng)工程研究所對我國金屬熱處理專業(yè)的26個碩士點的教育質(zhì)量，進行了有效性評價。評價采用的指標體系為：輸入：導(dǎo)師人數(shù)；實驗設(shè)備；

49、圖書資料；學(xué)生入學(xué)情況。輸出：科研成果；論文篇數(shù)；學(xué)生畢業(yè)時的情況。使用DEA進行評價，結(jié)果基本合理。81線性規(guī)劃 Linear Programming（LP）相對有效性評價問題例子 例2：行風(fēng)（行業(yè)作風(fēng)）建設(shè)有效性評價 本項目研究人員選定江蘇省S市交通客運系統(tǒng)作為對象，包括7家交通客運汽車公司。 評價采用的指標基礎(chǔ)依據(jù)為：1、國際公交組織頒布的“十項基本考核指標”2、國內(nèi)頒布的公交運營服務(wù)的“八項考核指標”。 在此基礎(chǔ)上，根據(jù)該系統(tǒng)實際情況，最終選定了輸入指標4項，輸出指標4項。分別是：82線性規(guī)劃 Linear Programming（LP）相對有效性評價問題例子輸入指標：1、年末職工總熟

50、（單位：人）； 2、單位成本（單位：元/千人公里）； 3、燃料單位消耗（單位：升/千人公里）； 4、行車責(zé)任事故率（單位：次/千人公里）。輸出指標：1、勞動生產(chǎn)率（單位：元/人）； 2、行車準點率（%）； 3、群眾滿意率（按問卷調(diào)查）（%） 4、車輛服務(wù)合格率（包括：服務(wù)態(tài)度、服務(wù)措施、 車輛設(shè)施等）（%）83線性規(guī)劃 Linear Programming（LP）相對有效性評價問題例子 收集到所需數(shù)據(jù)后，使用DEA方法綜合評價，結(jié)果為：3家公司為行風(fēng)建設(shè)有效；4家公司在行風(fēng)建設(shè)上存在不同程度（以量化形式給出）的缺點與不足。84線性規(guī)劃 Linear Programming（LP）相對有效性評價

51、問題舉例 4所小學(xué)S1，S2，S3，S4，在校學(xué)生分別為1200，1000，1600，1400人，按800名標準學(xué)生的規(guī)模折算各個學(xué)校的教職工人數(shù)和建筑面積的投入，如下表： 學(xué) 校投 入S1S2S3S4教職工人數(shù)建筑面積/m2251800401500351700202500請您評價：就培養(yǎng)800名學(xué)生而言，那些學(xué)校的投入產(chǎn)出效率較高，那些較低？85線性規(guī)劃 Linear Programming（LP）相對有效性評價問題舉例 一連鎖餐飲企業(yè)擁有遍布全國的20家連鎖餐廳，每家餐廳的每周運營時間、員工人數(shù)以及每周利潤和所占市場份額如下表：餐廳 周運營時間全職員工每周利潤市場份額增長率%餐廳 周運營時

52、間全職員工每周利潤市場份額增長率%A96.00 16.00 3800.00 25.00 K112.00 23.00 5900.00 22.00 B110.00 22.00 4600.00 32.00 L104.00 19.00 6300.00 20.00 C100.00 18.00 4400.00 35.00 M180.00 30.00 8000.00 18.00 D125.00 25.00 6500.00 30.00 N130.00 25.00 6800.00 16.00 E120.00 24.00 6000.00 28.00 O128.00 23.00 5800.00 21.00 F105

53、.00 19.00 5800.00 33.00 P118.00 19.00 4600.00 30.00 G115.00 20.00 5000.00 27.00 Q107.00 25.00 5300.00 23.00 H109.00 18.00 5200.00 18.00 R116.00 24.00 6100.00 28.00 I98.00 17.00 4500.00 26.00 S127.00 19.00 5730.00 20.00 J130.00 28.00 6800.00 24.00 T108.00 16.00 4000.00 21.00 您對這20家餐廳的運營效率又作何判斷？86線性規(guī)劃

54、 Linear Programming（LP）相對有效性評價問題舉例教職工人數(shù)建筑面積生產(chǎn)前沿線（面）S4S1S3S2M數(shù)據(jù)包絡(luò)線87線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA問題線性規(guī)劃數(shù)學(xué)模型 在DEA中一般稱被衡量績效的組織為決策單元（decision making unitDMU）。設(shè)：n 個決策單元（ j = 1，2，n ） 每個決策單元有相同的 m 項投入（輸入）（i = 1，2，m ） 每個決策單元有相同的 s 項產(chǎn)出（輸出）（r = 1，2，s ） aij 第 j 決策單元的第 i 項投入 brj 第 j 決策單元的第 r 項產(chǎn)出 評價（衡量）第

55、j0 決策單元是否DEA有效88線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA問題線性規(guī)劃數(shù)學(xué)模型決策單元 1 2 n投入項目12m a11 a12 a1n a21 a22 a2n am1 am2 amn 1 2 n決策單元 b11 b12 b1n b21 b22 b2n bs1 bs2 bsn12s產(chǎn)出項目89線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA問題線性規(guī)劃數(shù)學(xué)模型構(gòu)建模型的思路： 衡量某一決策單元 j0 是否DEA有效是否處于由包絡(luò)線組成的生產(chǎn)前沿面上，先構(gòu)造一個由 n 個決策單元組成（線性組合成）的假想決策單元。如果該假想單元

56、的各項產(chǎn)出均不低于 j0 決策單元的各項產(chǎn)出，它的各項投入均低于 j0 決策單元的各項的各項投入。即有：90線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA問題線性規(guī)劃數(shù)學(xué)模型j brj brj0 （r = 1，2，s）j aij E aij0 （i = 1，2，m，E1）j = 1 ，j 0 （j = 1，2，n）j=1j=1j=1nnn這說明 j0 決策單元不處于生產(chǎn)前沿面上。91線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA問題線性規(guī)劃數(shù)學(xué)模型 基于上述事實，可以寫出如下線性規(guī)劃的數(shù)學(xué)模型：min E S.t.j brj brj0 （r

57、= 1，2，s）j aij E aij0 （i = 1，2，m）j = 1 ，j 0 （j = 1，2，n）j=1j=1j=1nnn我們稱模型中的 j 為設(shè)計變量， E 為效率因子92線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA問題線性規(guī)劃數(shù)學(xué)模型模型求解結(jié)果分析：當求解結(jié)果有 E 1 時，則 j0 決策單元非DEA有效；否則，則 j0 決策單元DEA有效。93線性規(guī)劃 Linear Programming（LP）DEA分析應(yīng)用舉例例8（Page 39） 振華銀行的 4 個分理處的投入產(chǎn)出如下表。求各個分理處的運行是否DEA有效。 產(chǎn)出單位：處理筆數(shù)/月分理處投入產(chǎn)

58、出職員數(shù)營業(yè)面積（m2）儲蓄存取貸款中間業(yè)務(wù)分理處1分理處2分理處3分理處41520212014013012013518001000800900200350450420160010001300150094線性規(guī)劃 Linear Programming（LP）DEA分析應(yīng)用舉例解： 若先確定分理處1的運行是否DEA有效。建立線性規(guī)劃模型min E 18001 +10002 + 8003 + 9004 1800 2001 + 3502 + 4503 + 4204 200 16001 +10002 +13003 +15004 1600S.t. 151 + 202 + 213 + 204 15E 14

59、01 + 1302 + 1203 + 1354 140E 1 + 2 + 3 + 4 = 1 j 0 （ j = 1，2，3，4 ）95線性規(guī)劃 Linear Programming（LP）DEA分析應(yīng)用舉例求解結(jié)果分析：對分理處1，E =1，說明分理處1的運行DEA有效。對分理處2，E =0.996，說明分理處2的運行非DEA 有效。對分理處3，E =1，說明分理處3的運行DEA有效。對分理處4，E =1，說明分理處4的運行DEA有效。96線性規(guī)劃 Linear Programming（LP）DEA分析應(yīng)用舉例DEA應(yīng)用中的“窗口”技術(shù)空軍基地的效率評價（美國）美國空軍軍方曾對 7 個空軍基

60、地的效率進行了評價，使用的方法為DEA。輸入指標選定 3 項，輸出指標選定 4 項（內(nèi)容未報道）。評價的時間范圍為 1992 年 10 月 1 日至1993 年12 月 31 日。 盡管具體內(nèi)容及結(jié)果未予公布，但有一項技術(shù)“窗口技術(shù)”卻很有參考價值，介紹如下：97線性規(guī)劃 Linear Programming（LP）DEA分析應(yīng)用舉例DEA應(yīng)用中的“窗口”技術(shù)空軍基地的效率評價（美國）一般來說，在對決策單元集進行DEA 評價時，對單元的個數(shù) n ，輸入指標個數(shù) m ，以及輸出指標個數(shù) s 應(yīng)有一定的要求。經(jīng)驗表明它們大體上應(yīng)滿足或接近 n 2ms 在本例中，空軍基地有 7 個，分別記為 A 、