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

線性規(guī)劃線性規(guī)劃問題單純形法1第1頁，共112頁，2023年，2月20日，星期日第一講第二章線性規(guī)劃及圖解法第2頁，共112頁，2023年，2月20日，星期日問題的提出解決有限資源在有競爭的使用方向中如何進(jìn)行最佳分配。線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，也是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一。自1947年旦茨基（G.B.Dantzig）提出了一般線性規(guī)劃問題求解的方法——單純形法（simplexmethod）之后，線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟(jì)管理和工業(yè)生產(chǎn)中遇到的實(shí)際問題。調(diào)查表明，在世界500家最大的企業(yè)中，有85%的企業(yè)都曾使用線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計(jì)的資金。線性規(guī)劃LinearProgramming（LP）第3頁，共112頁，2023年，2月20日，星期日本講中我們將討論什么是線性規(guī)劃問題，線性規(guī)劃問題的數(shù)學(xué)表示，基本概念和圖解方法。線性規(guī)劃問題是什么樣的一類問題呢？請(qǐng)看案例線性規(guī)劃LinearProgramming（LP）第4頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。案例河流污染治理規(guī)劃問題第5頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第6頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。今日認(rèn)識(shí)未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第7頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）今日認(rèn)識(shí)未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第8頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）案例河流污染治理規(guī)劃問題背景資料:長江流域某區(qū)域內(nèi)有9化工廠，各廠每月產(chǎn)生的工業(yè)污水量如表-1，流經(jīng)各化工廠的河流流量如表-2，各化工廠治理工業(yè)污水的成本如表-3。上游廠排放的污水流到相鄰下游廠以前，有20%可自然凈化。根據(jù)環(huán)保標(biāo)準(zhǔn)河流中此種工業(yè)污水的含量不應(yīng)超過0.2%。從該區(qū)域整體考慮，各化工廠應(yīng)該分別處理多少工業(yè)污水才能既滿足環(huán)保要求，又使9化工廠治理工業(yè)污水的總費(fèi)用最少。第9頁，共112頁，2023年，2月20日，星期日背景資料:線性規(guī)劃LinearProgramming（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化工廠71200化工廠2300化工廠5600化工廠8200化工廠31800化工廠6400化工廠9700化工廠13化工廠44化工廠71化工廠25化工廠55化工廠82化工廠32化工廠66化工廠93第10頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）194582637問題分析：區(qū)域污染治理的決策——各個(gè)化工廠應(yīng)處理的工業(yè)污水量（或應(yīng)排放的工業(yè)污水量）。區(qū)域污染治理的約束——即滿足環(huán)保要求排放工業(yè)污水（區(qū)域內(nèi)河流中任何點(diǎn)檢測(cè)都應(yīng)符合環(huán)保標(biāo)準(zhǔn)）。區(qū)域污染治理的目標(biāo)——總治理成本最少。第11頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）194582637模型描述：設(shè)第i個(gè)化工廠應(yīng)處理的工業(yè)污水量為Xi萬m3，則根據(jù)問題描述的情況以化工廠1、2、…、9加以分析則可得如下近似關(guān)系式對(duì)化工廠2應(yīng)有（1-X2）/300≦0.2%對(duì)化工廠8應(yīng)有（0.8-X8）/200≦0.2%對(duì)化工廠1應(yīng)有｛（1.2-X1）+0.8（1-X2）+（0.8-X8）｝/500≦0.2%第12頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）194582637對(duì)化工廠9應(yīng)有——（1.5-X9）/700≦0.2%對(duì)化工廠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)各個(gè)化工廠應(yīng)處理的工業(yè)污水量Xi應(yīng)滿足上述所有不等式方程。我們將這些不等式方程構(gòu)成的方程組稱為污水治理的約束條件。第13頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）194582637另一方面污水治理的總成本可表示為Z（單位：百萬元）Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9而決策者的目標(biāo)是：確定滿足約束條件的Xi使得Z取得最小值。將上述分析歸納后即可得如下數(shù)學(xué)符合模型：第14頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）河流污染治理規(guī)劃問題數(shù)學(xué)模型（整理之后）194582637MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9X2≧0.4X8≧1.6X1+0.8X2+0.8X8≧4.4X9≧0.1X7+0.8X9≧0.8X4+0.8X7+0.64X9≧2.16X6≧0.2X5+0.8X6≧0.6X3+0.8X4+0.8X5+0.64X6+0.64X7+5.12X9≧9.4Xi≧0（i=1，2，3，4，5，6，7，8，9）s.t.第15頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）線性規(guī)劃模型——

LinearProgrammingModel或LinearOptimizationModel用線性規(guī)劃方法解決實(shí)際經(jīng)濟(jì)與管理問題的第一步是分析建立能夠完整描述和反映實(shí)際問題的線性規(guī)劃模型。第16頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）通常建立LP模型有以下幾個(gè)基本步驟：確定決策變量：決策變量是模型要確定的未知變量，也是模型最重要的參數(shù)，是決策者解決實(shí)際問題的控制變量。確定目標(biāo)函數(shù)：目標(biāo)函數(shù)決定線性規(guī)劃問題的優(yōu)化方向，是模型的重要組成部分。實(shí)際問題的目標(biāo)可表示為決策變量的一個(gè)線性函數(shù)，并根據(jù)目標(biāo)函數(shù)的實(shí)質(zhì)確定優(yōu)化方向，一般可為最大化（max）或最小化（min）。第17頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）通常建立LP模型有以下幾個(gè)步驟：確定約束方程：一個(gè)正確的線性規(guī)劃模型應(yīng)能通過約束方程來描述和反映一系列客觀條件或環(huán)境的限制，這些限制通過一系列線性等式或不等式方程組來描述。變量取值限制：一般情況下，決策變量取正值（非負(fù)值）。因此，模型中應(yīng)有變量的非負(fù)約束即Xj≥0，但要注意也存在例外的情形。第18頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）線性規(guī)劃的一般形式:max（或min）z=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn（≤=≥）b1a21x1+a22x2+…+a2nxn

（≤=≥）b2s.t.………………am1x1+am2x2+…+amnxn（≤=≥）bm

xj≥0（j=1，2…n）第19頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）線性規(guī)劃問題的標(biāo)準(zhǔn)形式1、目標(biāo)函數(shù)極大化——“max”2、等式約束條件——“=”且右端常數(shù)bi非負(fù)3、變量非負(fù)——“xj≥0”maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）第20頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）化標(biāo)準(zhǔn)形式的一般步驟目標(biāo)函數(shù)極小化“極大化”約束條件的右端項(xiàng)bi≤0“bi≥0”約束條件為不等式≤或≥“=”取值無約束（自由）變量“非負(fù)變量”取值非正變量“非負(fù)變量”線性規(guī)劃問題的標(biāo)準(zhǔn)形式的作用——為單純形法求解作準(zhǔn)備！第21頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）線性規(guī)劃問題的求解：（圖解）如何求解一般的線性規(guī)劃呢？下面我們分析一下簡單的情況——只有兩個(gè)決策變量的線性規(guī)劃問題，這時(shí)可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。第22頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念例1（page11）maxz=2x1+x25x2

≤15s.t.6x1+2x2

≤24x1+x2

≤5x1，x2

≥0第23頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1，x2≥0唯一最優(yōu)解X=（9/2，3/2）第24頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念例maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0第25頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=2X1+X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)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）DmaxZminZ此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值maxZ=17.2可行域第26頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZminZ（3.8，4）34.2=3X1+5.7X2

綠色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏虻?7頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念minZ=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

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點(diǎn)是唯一最優(yōu)解第28頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念minZ=5X1+4X2x1x2oD可行域第29頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2oD可行域maxZminZ最優(yōu)解目標(biāo)值Z趨于無窮第30頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2o可行解域?yàn)榭盏?1頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）基本概念圖解法的啟示線性規(guī)劃問題解的可能情況a.唯一最優(yōu)解b.無窮多最優(yōu)解c.無解（沒有有界最優(yōu)解，無可行解）若線性規(guī)劃問題的可行域非空，則可行域是一個(gè)凸集；若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的某個(gè)頂點(diǎn)上達(dá)到。第32頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法

單純形方法是G.B.Danzig于1947年首先發(fā)明的。近50年來，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。本節(jié)討論單純形法的基本概念、原理及算法。第33頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法給定線性規(guī)劃問題（標(biāo)準(zhǔn)形式）maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn

=b1a21x1+a22x2+…+a2nxn

=b2s.t.……………am1x1+am2x2+…+amnxn

=bmxj≥0（j=1，2…n）第34頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法一、線性規(guī)劃問題的解的概念

可行解最優(yōu)解基基解（基本解）基可行解可行基第35頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法二、凸集及其頂點(diǎn)凸集頂點(diǎn)（極點(diǎn)）凸集凹集第36頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）12345678基解（可行）基解（不可行）第37頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法三、線性規(guī)劃基本定理基本定理1

線性規(guī)劃所有可行解組成的集合S={X|AX=b，X≥0}是凸集?；径ɡ?

X是線性規(guī)劃問題的基本可行解的充要條件為是X是凸集S={X|AX=b，X≥0}的極點(diǎn)?；径ɡ?

給定線性規(guī)劃問題，A是秩為m的mn矩陣，

（i）若線性規(guī)劃問題存在可行解，則必存在基本可行解（ii）若線性規(guī)劃問題存在有界最優(yōu)解，則必存在有界最優(yōu)基本可行解。第38頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法單純形法迭代原理及其思路單純形法的初步討論例1.8求解LP問題

化為標(biāo)準(zhǔn)型MaxZ=50X1+30X2s.t.4X1+3X2≤

1202X1+X2≤50X1，X2≥0MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2+X4

=50X1，X2，X3，X4

≥0（1.18）第39頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法此線性規(guī)劃問題轉(zhuǎn)化為了一個(gè)含有四個(gè)變量的標(biāo)準(zhǔn)形線性規(guī)劃問題，X3，X4為松弛變量。為求解上面的LP問題，我們要考慮滿足約束條件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下第40頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法確定初始基可行解：通過觀察可以發(fā)現(xiàn)，松弛變量X3和X4對(duì)應(yīng)的等式約束條件中的系數(shù)矩陣為單位矩陣可以作為初始可行基矩陣。因此取X3，X4為基變量；X1，X2為非基變量。則（1.18）可變?yōu)椋?/p>

Max

Z

=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2（1.19）X1，X2，X3，X4≥0第41頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法典式（1.19）或（1.18）稱為關(guān)于基的典式——1、等式約束條件中顯含基可行解2、目標(biāo)函數(shù)中不含基變量MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2+X4

=50(1.18)X1，X2，X3，X4≥0MaxZ

=50X1+30X2s.t.X3

=120-4X1-3X2

X4=50-2X1-X2（1.19）X1，X2，X3，X4≥0第42頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法在典式（1.19）中令：X1=X2

=0，我們得到一個(gè)基本可行解

X1=（X1，X2，X3，X4）T=（0，0，120，50）T

，其對(duì)應(yīng)的目標(biāo)函數(shù)值Z1=50X1+30X2=0第43頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法最優(yōu)性檢驗(yàn)：基本可行解X1是最優(yōu)解嗎？顯然不是。應(yīng)尋找更好的解。從問題的數(shù)學(xué)角度分析，在典式（1.19）的目標(biāo)函數(shù)中，非基變量X1，X2前的系數(shù)都為正，而此時(shí)的X1，X2均取零值，表明只要增加其值，則目標(biāo)函數(shù)值有增加的可能。因此，將目標(biāo)函數(shù)中系數(shù)為正的某一非基變量與某一基變量地位對(duì)換。第44頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法換基迭代：進(jìn)行換基就是要從非基變量中選一個(gè)變量入基，再從基變量中選一個(gè)變量出基。并且換基后仍需滿足：新的解仍是基本可行解；目標(biāo)函數(shù)值將得到改善。第45頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法選擇入基變量：

由于在目標(biāo)函數(shù)Z1

=50X1+30X2中X1，X2的系數(shù)都為正，哪一個(gè)入基都可使目標(biāo)函數(shù)值得到改善。對(duì)于求目標(biāo)函數(shù)極大化的問題，我們希望目標(biāo)值增加得越快越好，因此系數(shù)最大的X1入基。選擇出基變量：

X1入基后，其值從零增加并由于約束條件的原因會(huì)引起其他變量的變化。由典式（1.19）以及變量必須取正值（可行）的條件，我們可以得到下列不等式關(guān)系：X3=120-4X1-3X2≥0X4=50-2X1-X2≥0第46頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法

因?yàn)榈骕2仍為非基變量（仍會(huì)令其取值為零），則上式可簡化為：120-4X1≥0，且50-2X1≥0，由此可以看出，雖然我們希望X1入基后取正值，取值越大目標(biāo)值增加越大，但是X1又得受到以上約束（保證其可行）。顯然，當(dāng)取X1=min（120/4，50/2）=25時(shí)，才能使上述不等式成立，且此時(shí)恰使基變量X4變?yōu)榱?，這正好滿足非基變量必須取值零的條件，所以可令X4出基，這樣，新的基變量變?yōu)閄3，X1，而X2，X4成了非基變量，則第47頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法約束方程變?yōu)椋?X1+X3=120-3X22X1=50-X2-X4化簡后得：新的典式方程X3=20-X2+2X4X1=25-0.5X2-0.5X4第48頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法代入目標(biāo)函數(shù)可得：Z2

=1250+5X2-25X4

令非基變量X2=X4=0，即可得一個(gè)新的基本可行解X2=（25，0，20，0）T，其對(duì)應(yīng)的目標(biāo)函數(shù)值Z2

=1250，并完成了第一次迭代。由于目標(biāo)函數(shù)Z2=1250+5X2-25X4中X2的系數(shù)仍為正，該解X2仍不是最優(yōu)解。重復(fù)上述迭代過程得到：X2入基，X3出基，則新的典式方程變?yōu)椋篨1=15+0.5X3

-1.5X4X2=20-X3+2X4

Z3

=1350-5X3-15X4第49頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法第三個(gè)基本可行解X3

=（15，20，0，0）T，其對(duì)應(yīng)的目標(biāo)函數(shù)值Z3

=1350。此時(shí)松弛變量都是非基變量（取值為零），這表明資源已用盡；并且目標(biāo)函數(shù)值Z3

=1350-5X3-15X4中非基變量X3，X4的系數(shù)全為負(fù)值，說明目標(biāo)函數(shù)已無法進(jìn)一步改善，因此該解已是最優(yōu)解。第50頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法小結(jié)：

單純形法是這樣一種迭代算法——如下圖…當(dāng)Zk

中非基變量的系數(shù)的系數(shù)全為負(fù)值時(shí)，這時(shí)的基本可行解Xk

即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。X1Z1保持單調(diào)增保持可行性保持可行性保持可行性保持可行性保持單調(diào)增保持單調(diào)增保持單調(diào)增X2X3...XkZ2Z3...Zk當(dāng)Zk

中非基變量的系數(shù)的系數(shù)全為負(fù)值時(shí)，這時(shí)的基本可行解Xk

即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。第51頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形表對(duì)于給定的線性規(guī)劃問題：maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2s.t.………am1x1+am2x2+…+amnxn≤bmxj≥0（j=1，2…n）對(duì)此問題添加m個(gè)松弛變量后，可得下面線性規(guī)劃問題并且是典式的形式。第52頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形表線性規(guī)劃的典式maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+

xn+2=b2s.t.…am1x1+am2x2+…+amnxn+

xn+m=bmxj≥0（j=1，2…n，n+1，n+2，…n+m）第53頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形表：將上面典式中各變量及系數(shù)填寫在一張表格中就形成下面的單純形表cj

c1c2…cncn+1cn+2…cn+mCB基解

x1x2…xnxn+1xn+2…xn+m0000xn+1xn+2…xn+m

b1

b2…

bma11a12…a1n1a21a22…a2n1……………am1am2…amn112…mj=cj–zj

c1c2…cn00…0j=cj–zj

1

2…

nn+1

n+2…n+m第54頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形表：

上面的單純形表還可以表示成矩陣的形式基解X

XSXSbAIj

C

0基解XB

XN

XSXSbBNIj

CB

CN

0或第55頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法由單純形表進(jìn)行迭代步驟：選擇Xj入基：當(dāng)j行中

j=max{

i∣

i0}選擇Xi出基：當(dāng)i

=min{bi/aij∣aij0}換基迭代：當(dāng)確定了入基變量Xj、出基變量Xi后，以aij作為主元對(duì)單純形表進(jìn)行取主運(yùn)算，取主運(yùn)算——即采用初等行變換將主元aij所在列，除將aii變換為1而外，該列中的其余元素都變換為0。注意這種變換只能采用初等行變換!第56頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法最優(yōu)解檢驗(yàn)：當(dāng)?shù)M(jìn)行至某一步時(shí)，j行中所有檢驗(yàn)數(shù)均小于等于零，則迭代結(jié)束。表中當(dāng)前所指基本可行解即為最優(yōu)解。當(dāng)?shù)M(jìn)行至某一步時(shí)，j行中所有檢驗(yàn)數(shù)均小于等于零，且此時(shí)至少有一個(gè)非基變量所對(duì)應(yīng)的檢驗(yàn)數(shù)k等于零，則原線性規(guī)劃問題有無窮多個(gè)最優(yōu)解。當(dāng)?shù)M(jìn)行至某一步時(shí)，j行中至少有一個(gè)檢驗(yàn)數(shù)k大于零，且該檢驗(yàn)數(shù)對(duì)應(yīng)的列中a1k，a2k，…amk，均小于等于零，則原線性規(guī)劃問題最優(yōu)解無界（maxZ→+∞）。第57頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形方法的矩陣描述：設(shè)線性規(guī)劃問題maxZ=CXmaxZ=CX+0XS

s.t.AX≤bs.t.AX+IXS=b（I式）

X≥0X，XS≥0其中b≥0，I是mm單位矩陣。對(duì)上面（I式）經(jīng)過迭代，并設(shè)最終的最優(yōu)基矩陣為B（不妨設(shè)B

為A的首m列，則將（I式）改寫后有第58頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形方法的矩陣描述：maxZ=CBXB+CNXN+0XS

s.t.BXB+NXN+IXS=bXB，XN，XS≥0

maxZ=CBB-1+（CN-CBB-1）XN-

CBB-1XS

s.t.XB+B-1NXN+B-1XS=B-1bXB，XN，XS≥0

B式中最優(yōu)目標(biāo)函數(shù)值Z*=CBB

-1，檢驗(yàn)數(shù)CN-CBB

-1≤0

，-

CBB

-1≤0單純形方法迭代（I式）（B式）第59頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形方法的矩陣描述：基解XB

XN

XSXSb

BNIj

CB

CN

0基解XB

XN

XSXBB-1b

IB-1NB-1j

0

CN-CBB

–1N-

CBB

-1對(duì)應(yīng)I式的單純形表——

I

表對(duì)應(yīng)B

式的單純形表——B

表迭代第60頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形表計(jì)算步驟舉例給定線性規(guī)劃問題maxz=50X1+30X2s.t.4X1+3X2≤

1202X1+X2

≤50X1，X2

≥0maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4

≥0第61頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形表計(jì)算步驟舉例maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4≥0基XB解B-1bX1X2X3X4X31204310X4502101檢驗(yàn)數(shù)j

5030002120/450/2X111/201/2250201-2050-2520/125×211X2150-1/23/210-5-15第62頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法的進(jìn)一步討論人工變量法：當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們或可得到一個(gè)顯然的基本可行解（如松弛變量作為基變量的一個(gè)初始基本可行解），這樣我們就可以馬上進(jìn)入單純形表的運(yùn)算步驟。然而，并非所有問題標(biāo)準(zhǔn)化之后我們都可得到一個(gè)顯然的初始基本可行解，這時(shí)就需要我們首先確定出一個(gè)基本可行解作為初始基本可行解。通常采用的是人工變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法：

大M法（罰因子法）兩階段法第63頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法的進(jìn)一步討論1、大M法（罰因子法）maxz=-3X1+X3

x1+x2+x3

≤4-2x1+x2–x3

≥13x2+x3=9x1，x2，x3

≥0LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7

≥0第64頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）1、大M法LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j-30100-M-M第65頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j-3-2M4M10-M00第66頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗(yàn)數(shù)j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗(yàn)數(shù)j-3+6M01+4M03M-4M0第67頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗(yàn)數(shù)j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù)j00301.5-1.5-M0.5-M第68頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2檢驗(yàn)數(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檢驗(yàn)數(shù)j-9/2000-3/43/4-M-1/4-M第69頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）采用大M法求解線性規(guī)劃問題時(shí)可能出現(xiàn)的幾種情況：當(dāng)采用單純形法求解LPM得到最優(yōu)解時(shí)，基變量不含任何人工變量，則所得到的最優(yōu)解就是原問題的最優(yōu)解；當(dāng)采用單純形法求解LPM得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人工變量且非零，則原問題無可行解；當(dāng)采用單純形法求解LPM得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人工變量且人工變量都為零，則通過變換得到原問題最優(yōu)解；第70頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）2、兩階段法maxz=-3X1+X3

x1+x2+x3≤4-2x1+x2–x3≥13x2+x3=9x1，x2，x3≥0I階段問題maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7

≥0第71頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）2、兩階段法I階段問題maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j00000-1-1第72頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）2、兩階段法——第I階段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j00000-1-1基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù)j-2400-100第73頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）2、兩階段法——第I階段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗(yàn)數(shù)j-2400-100基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗(yàn)數(shù)j60403-40第74頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）2、兩階段法——第I階段基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗(yàn)數(shù)j60403-40基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù)j00000-1-1第75頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）2、兩階段法——第II階段基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù)j00000-1-1基XB解B-1bX1X2X3X4X5X400001-1/2X23011/300X11102/301/2檢驗(yàn)數(shù)j00303/2-30100第76頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）2、兩階段法——第II階段基XB解B-1bX1X2X3X4X5X400001-1/2X23011/3009X11102/301/23/2檢驗(yàn)數(shù)j00303/2基XB解B-1bX1X2X3X4X5X400001-1/2X25/2-1/2100-1/4X33/23/20103/4檢驗(yàn)數(shù)j-9/2000-3/4第77頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）單純形法中的幾個(gè)問題目標(biāo)函數(shù)極小化時(shí)，解的最優(yōu)判別：

j≥0退化：一個(gè)或幾個(gè)基變量等于零，一個(gè)簡單易行的避免退化的方法是1974年由勃蘭德（Bland）提出的Bkand法則。無可行解的判別：在采用人工變量求解線性規(guī)劃問題得到最優(yōu)解時(shí)，如果基變量中仍含有非零人工變量，則原問題無可行解。第78頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）數(shù)據(jù)包絡(luò)分析DEA（dateenvelopmentanalysis）引言

一種基于線性規(guī)劃的用于評(píng)價(jià)同類型組織（或項(xiàng)目）工作績效相對(duì)有效性的特殊工具手段。這類組織例如學(xué)校、醫(yī)院、銀行的分支機(jī)構(gòu)、超市的各個(gè)營業(yè)部等，各自具有相同的投入相同的產(chǎn)出。衡量這類組織之間的績效高低，通常采用投入產(chǎn)出比這個(gè)指標(biāo)，當(dāng)各自的投入產(chǎn)出均可折算成同一單位計(jì)量時(shí)，容易計(jì)算出各自的投入產(chǎn)出比并按其大小進(jìn)行績效排序。但當(dāng)被衡量的同類型組織有多項(xiàng)投入和多項(xiàng)產(chǎn)出，且不能折算成統(tǒng)一單位時(shí)，就無法算出投入產(chǎn)出比的數(shù)值，因而，需采用一種全新的方法進(jìn)行績效比較。這種方法就是二十世紀(jì)七十年代末產(chǎn)生的數(shù)據(jù)包絡(luò)分析DEA。第79頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）數(shù)據(jù)包絡(luò)分析DEA（dateenvelopmentanalysis）引言1978年，著名運(yùn)籌學(xué)家、美國德克薩斯大學(xué)教授A.Charnes及W.W.Cooperh和E.Rhodes發(fā)表了一篇重要論文：“Measuringtheefficiencyofdecisionmakingunits”（決策單元的有效性度量），刊登在權(quán)威的“歐洲運(yùn)籌學(xué)雜志”上。正式提出了運(yùn)籌學(xué)的一個(gè)新領(lǐng)域：數(shù)據(jù)包絡(luò)分析。其模型簡稱C2R模型。第80頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）相對(duì)有效性評(píng)價(jià)問題例子

例1：碩士點(diǎn)教育質(zhì)量評(píng)價(jià)某系統(tǒng)工程研究所對(duì)我國金屬熱處理專業(yè)的26個(gè)碩士點(diǎn)的教育質(zhì)量，進(jìn)行了有效性評(píng)價(jià)。評(píng)價(jià)采用的指標(biāo)體系為：輸入：導(dǎo)師人數(shù)；實(shí)驗(yàn)設(shè)備；圖書資料；學(xué)生入學(xué)情況。輸出：科研成果；論文篇數(shù)；學(xué)生畢業(yè)時(shí)的情況。使用DEA進(jìn)行評(píng)價(jià)，結(jié)果基本合理。第81頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）相對(duì)有效性評(píng)價(jià)問題例子

例2：行風(fēng)（行業(yè)作風(fēng)）建設(shè)有效性評(píng)價(jià)本項(xiàng)目研究人員選定江蘇省S市交通客運(yùn)系統(tǒng)作為對(duì)象，包括7家交通客運(yùn)汽車公司。評(píng)價(jià)采用的指標(biāo)基礎(chǔ)依據(jù)為：1、國際公交組織頒布的“十項(xiàng)基本考核指標(biāo)”2、國內(nèi)頒布的公交運(yùn)營服務(wù)的“八項(xiàng)考核指標(biāo)”。在此基礎(chǔ)上，根據(jù)該系統(tǒng)實(shí)際情況，最終選定了輸入指標(biāo)4項(xiàng)，輸出指標(biāo)4項(xiàng)。分別是：第82頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）相對(duì)有效性評(píng)價(jià)問題例子輸入指標(biāo)：1、年末職工總熟（單位：人）；2、單位成本（單位：元/千人公里）；3、燃料單位消耗（單位：升/千人公里）；4、行車責(zé)任事故率（單位：次/千人公里）。輸出指標(biāo)：1、勞動(dòng)生產(chǎn)率（單位：元/人）；2、行車準(zhǔn)點(diǎn)率（%）；3、群眾滿意率（按問卷調(diào)查）（%）4、車輛服務(wù)合格率（包括：服務(wù)態(tài)度、服務(wù)措施、車輛設(shè)施等）（%）第83頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）相對(duì)有效性評(píng)價(jià)問題例子

收集到所需數(shù)據(jù)后，使用DEA方法綜合評(píng)價(jià)，結(jié)果為：3家公司為行風(fēng)建設(shè)有效；4家公司在行風(fēng)建設(shè)上存在不同程度（以量化形式給出）的缺點(diǎn)與不足。第84頁，共112頁，2023年，2月20日，星期日線性規(guī)劃LinearProgramming（LP）相對(duì)有效性評(píng)價(jià)問題舉例

4所小學(xué)S1，S2，S3，S4，在校學(xué)生分別為1200，1000，1600，1400人，按800名標(biāo)準(zhǔn)學(xué)生的規(guī)模折算各個(gè)學(xué)校的