第1章-線性規(guī)劃及單純形法

「線性規(guī)劃」帶來(lái)巨額財(cái)富

與其他傳統(tǒng)數(shù)學(xué)學(xué)門相比較,線性規(guī)劃算是非?！改贻p」卻非?！笇?shí)用」的一門應(yīng)用數(shù)學(xué)。根據(jù)對(duì)二十世紀(jì)八十年代的一項(xiàng)調(diào)查,在美國(guó)「財(cái)富」雜志(Fortune)名列前五百名的大公司中,百分八十五均曾應(yīng)用線性規(guī)劃的方法來(lái)協(xié)助公司的營(yíng)運(yùn)。由此可見(jiàn)線性規(guī)劃應(yīng)用面的寬廣與普及。第1章線性規(guī)劃及單純形法§1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型§2圖解法§3單純形法原理§4單純形法的計(jì)算步驟§5單純形法的進(jìn)一步討論§6數(shù)據(jù)包絡(luò)分析主要內(nèi)容§1

一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型問(wèn)題的提出線性規(guī)劃問(wèn)題的數(shù)學(xué)模型線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的解常山機(jī)器廠生產(chǎn)I、II兩種產(chǎn)品，這兩種產(chǎn)品都要分別在A、B、C三種不同設(shè)備上加工。生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，問(wèn)該企業(yè)應(yīng)安排生產(chǎn)兩種產(chǎn)品各多少件，使總的利潤(rùn)收入為最大。生產(chǎn)每件產(chǎn)品占用設(shè)備時(shí)間(h)產(chǎn)品I產(chǎn)品II計(jì)劃期內(nèi)用于生產(chǎn)的能力設(shè)備A2212設(shè)備B4016設(shè)備C0515單位產(chǎn)品的利潤(rùn)（元）23例1.1生產(chǎn)計(jì)劃問(wèn)題1-1問(wèn)題的提出問(wèn)題分析占用設(shè)備時(shí)間(h)產(chǎn)品I產(chǎn)品II可用的能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤(rùn)（元）23可控因素(所求變量):設(shè)在計(jì)劃期內(nèi)生產(chǎn)I、II兩種產(chǎn)品的數(shù)量分別為目標(biāo)：達(dá)到最大.使得總利潤(rùn)最大，即利潤(rùn)函數(shù)：受制條件：計(jì)劃期內(nèi)設(shè)備的使用量不超過(guò)可用量：設(shè)備B：設(shè)備C：設(shè)備A：模型s.t.

1-2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型(1)規(guī)劃問(wèn)題的數(shù)學(xué)模型的3個(gè)組成要素：決策變量、目標(biāo)函數(shù)、約束條件(2)線性規(guī)劃問(wèn)題的數(shù)學(xué)模型：決策變量為可控的連續(xù)變量、目標(biāo)函數(shù)和約束條件都是線性目標(biāo)函數(shù)約束條件(3)一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示形式：以上模型的簡(jiǎn)寫形式為待定的決策變量

價(jià)值系數(shù)矩陣

為系數(shù)矩陣(或約束矩陣)。向量表示形式其中矩陣表示形式價(jià)值向量右端向量(2)化為標(biāo)準(zhǔn)形式的方法1-3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式取極大bi≥0,等式約束非負(fù)約束(1)標(biāo)準(zhǔn)形式①②松弛變量③剩余變量說(shuō)明：松弛變量和剩余變量在實(shí)際問(wèn)題中分別表示未被利用的資源和超用的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)，所以引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。

例1.2把問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式1-4線性規(guī)劃問(wèn)題的解線性規(guī)劃問(wèn)題滿足約束條件(2)、(3)的解可行解(或可行點(diǎn))可行域全部可行解的集合最優(yōu)解使目標(biāo)函數(shù)(1)達(dá)到最大值的可行解最優(yōu)解集合最優(yōu)值最優(yōu)解的全體最優(yōu)解的目標(biāo)函數(shù)值基設(shè)Am×n為約束方程組(2)的系數(shù)矩陣(設(shè)n＞m),R(A)=mB是矩陣A的m×m階的滿秩子矩陣，基向量基變量非基變量基解不失一般性，設(shè)基B的每一個(gè)列向量Pj

(j=1,…,m)與基向量Pj

對(duì)應(yīng)的變量xj

線性規(guī)劃中除基變量以外的其他變量

在約束方程組(2)中,令非基變量xm+1=…=xn=0,可解出m個(gè)基變量的惟一解XB=(x1,…,xm),X=(x1,…,xm,0,…0)T,基解總數(shù)基可行解滿足變量非負(fù)約束條件(3)的基解可行基對(duì)應(yīng)于基可行解的基

例1.3

列出下述線性規(guī)劃問(wèn)題的全部基、基解、基可行解、最優(yōu)解解：系數(shù)矩陣R(A)=2基基解是基可行解？目標(biāo)函數(shù)值x1x2x3x4-45.500×√√√×√×√2/5011/50-1/30011/601/2200-1/2020011P1P2P1P3P1P4P2P3P2P4P3P443/555§2

圖解法優(yōu)點(diǎn)：直觀性強(qiáng)、計(jì)算方便缺點(diǎn)：只適用問(wèn)題中有兩個(gè)變量的情況步驟：建立坐標(biāo)系，將約束條件在圖上表示；確立滿足約束條件的范圍；繪制出目標(biāo)函數(shù)的圖形；確定最優(yōu)解s.t.

例2.1

用圖解法解線性規(guī)劃x1x2oB(0,6)A(6,0)2x1+2x2=125x2=154x1=16z=9z

=15z

=12Q1Q2Q3Q4唯一最優(yōu)解線性規(guī)劃問(wèn)題解的情況：無(wú)可行解(可行域是空集)無(wú)界解或無(wú)最優(yōu)解(可行域無(wú)界)最優(yōu)解存在且唯一，則一定在頂點(diǎn)上達(dá)到最優(yōu)解存在且不唯一(無(wú)窮多最優(yōu)解)，一定存在頂點(diǎn)是最優(yōu)解(1)無(wú)可行解s.t.

x1x2o2x1+2x2=12x1+2x2=14(2)無(wú)界解s.t.

(3)無(wú)窮多最優(yōu)解x1x2o4x1=16s.t.

x2oQ1Q2Q3Q4x1圖解法的啟示(1)求解線性規(guī)劃問(wèn)題時(shí)，解的情況有：惟一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解、無(wú)可行解；(2)若線性規(guī)劃問(wèn)題的可行域存在，則可行域是一個(gè)凸集；(3)若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一(如果有無(wú)窮多的話)一定能夠在可行域的某個(gè)頂點(diǎn)找到；(4)解題思路：先找出凸集的任一頂點(diǎn)，計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值，比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值更優(yōu)，若為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更優(yōu)的另一頂點(diǎn)重復(fù)上述過(guò)程，一直到找出使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點(diǎn)為止。內(nèi)容小結(jié)基本概念線性規(guī)劃、可行解、可行域、最優(yōu)解、最優(yōu)值、基基向量、(非)基變量、基解、可行基基本計(jì)算把問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式用圖解法解線性規(guī)劃§3單純形法原理預(yù)備知識(shí)：凸集和頂點(diǎn)幾個(gè)基本定理的證明確定初始基可行解從初始基可行解轉(zhuǎn)化為另一基可行解最優(yōu)性檢驗(yàn)和判別3-1預(yù)備知識(shí)：凸集和頂點(diǎn)凸集如果集合C中任意兩個(gè)點(diǎn)X1、X2，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)，即對(duì)任何有頂點(diǎn)如果集合C中不存在任何兩個(gè)不同的點(diǎn)X1、X2，使X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn)，或?qū)θ魏尾淮嬖?-2幾個(gè)基本定理的證明定理1

若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。證明：設(shè)C表示線性規(guī)劃問(wèn)題的可行域則有令即則有顯然證畢引理

線性規(guī)劃問(wèn)題的可行解X=(x1,…,xn)T為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。證明：必要性，由基可行解的定義顯然成立。充分性。不失一般性不妨,線性獨(dú)立的，若當(dāng)時(shí)，恰好構(gòu)成一個(gè)基，從而為相應(yīng)的基可行解。當(dāng)時(shí),而R(A)=m,則必有則一定可以從其余列向量中找出m-k個(gè)與構(gòu)成一個(gè)基，其對(duì)應(yīng)的解恰好為X.若X為基解，如何判定是基可行解？若X為可行解，如何判定是基可行解？定理2線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域的頂點(diǎn)。分析：X是可行域的頂點(diǎn)X是基可行解X不是可行域的頂點(diǎn)X不是基可行解定理2線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域的頂點(diǎn)。X不是可行域的頂點(diǎn)(1)X不是基可行解證明：不失一般性,不妨設(shè)X的前m個(gè)分量為正，由X是可行解，得使得即存在一組不全為零的數(shù)線性相關(guān)，由引理知得得得令選取適當(dāng)?shù)闹?，使則又即X不是可行域的頂點(diǎn)。從而不是可行域的頂點(diǎn)有即因固有當(dāng)xi=0時(shí)，必有yi=zi=0得(2)X不是可行域的頂點(diǎn)X不是基可行解不失一般性,不妨設(shè)因有因線性相關(guān)故不全為零證畢若線性規(guī)劃問(wèn)題有最優(yōu)解,一定存在一個(gè)基可行解是最優(yōu)解。定理3證明：設(shè)是最優(yōu)解是目標(biāo)函數(shù)的最大值。若X0不是基可行解，則X0不是可行域的頂點(diǎn)，一定能在可行域內(nèi)找到通過(guò)的X0的直線上的另外兩個(gè)點(diǎn)而有則由此從而若仍不是基可行解，按上面的方法繼續(xù)做下去,最后一定可以找到一個(gè)基可行解,其目標(biāo)函數(shù)值等于CX0.3-3確定初始基可行解由前面的定理可知：如果一個(gè)LP問(wèn)題有最優(yōu)解，則一定在某個(gè)基可行解處達(dá)到。單純形法的基本思想就是先找到一個(gè)初始基可行解，判斷它是否最優(yōu)，如若不是，就找一個(gè)更好的基本可行解，再進(jìn)行判斷。如此迭代下去，直至找到最優(yōu)基本可行解，或者判定該問(wèn)題無(wú)界?。?！一種易求初始基可行解的情形系數(shù)矩陣化為標(biāo)準(zhǔn)形式取單位矩陣作為基，則就是一個(gè)基可行解3-4從初始基可行解轉(zhuǎn)化為另一基可行解設(shè)初始基可行解為,其中非零坐標(biāo)有m個(gè).不失一般性,假定前m個(gè)坐標(biāo)為非零，因固有方程組(*)的增廣矩陣可寫為得由上式知，因是一個(gè)基，則滿足或要使X1是一個(gè)基可行解，而θ>0,故應(yīng)對(duì)同時(shí)成立且至少有一個(gè)等號(hào)成立。當(dāng)aij≤0時(shí)，上式顯然成立。故可令則由上式，知?jiǎng)tX1中的正分量個(gè)數(shù)最多有m個(gè)，易證，故只需按來(lái)確定的θ值，X1就是一個(gè)新的基可行解。線性無(wú)關(guān)，3-5最優(yōu)性檢驗(yàn)和解的判別將基可行解X0和X1分別代入目標(biāo)函數(shù)得通常簡(jiǎn)寫為

檢驗(yàn)數(shù)說(shuō)明：1)當(dāng)所有的

j≤0時(shí),現(xiàn)有基可行解即為最優(yōu)解。

2)當(dāng)所有的

j≤0,又對(duì)某個(gè)非基變量xj有cj－zj=0，且按可以找到θ>0，這表明可以找到另一個(gè)基可行解使目標(biāo)函數(shù)也達(dá)到最大，此時(shí)該規(guī)劃有無(wú)窮多最優(yōu)解。3)如果某個(gè)

j>0,又Pj的所有分量aij≤0,則對(duì)任意θ>0,恒有而θ取值可無(wú)限大，故目標(biāo)函數(shù)也可無(wú)限增大,此時(shí)規(guī)劃問(wèn)題有無(wú)界解。內(nèi)容小結(jié)基本概念凸集、頂點(diǎn)基本結(jié)論1)若線性規(guī)劃問(wèn)題存在可行解，則可行域是凸集。2)

可行解X為基可行解X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。3)

基可行解對(duì)應(yīng)可行域的頂點(diǎn)。4)一定存在一個(gè)基可行解是最優(yōu)解?！?單純形法的計(jì)算步驟單純形法的計(jì)算步驟：step1、求出線性規(guī)劃的初始基可行解，列出初始單純形表。先化成標(biāo)準(zhǔn)形式,設(shè)法使系數(shù)矩陣中包含一個(gè)單位矩陣,不妨設(shè)此單位矩陣是(P1,P2,…,Pm),以此作為基可得一個(gè)初始基可行解X=(b1,b2,…,bm

).構(gòu)造初始單純形表cj

→c1…cm…cj

…cnx1…xm…xj…xnCB基bc1c2cmx1x2xmb1b2bmcj

-zj0…0……1…00…00…1…a1j…a1n…a2j…a2n…amj…amnStep2

進(jìn)行最優(yōu)性檢驗(yàn)

若表中所有的

j≤0,則表中的基可行解就是問(wèn)題的最優(yōu)解，計(jì)算結(jié)束。否則轉(zhuǎn)下一步。

Step3

基可行解轉(zhuǎn)換，得到新單純形表。(1)確定入基變量.對(duì)應(yīng)的變量xk作為換入基的變量.(2)確定出基變量.xl作為換出基的變量.alk稱為主元素(3)生成新的單純形表Step4

重復(fù)第二、三步一直到計(jì)算終止。cj

→c1…cl…cm…cj

…ck…cnCB基bx1…xl…xm…xj…xk…xnc1x11……0……0…ckxk0……0……1…cmxm0……1……0…cj

-zj

0……0……0…s.t.

例1用單純形法求解線性規(guī)劃問(wèn)題解：將上述問(wèn)題化為標(biāo)準(zhǔn)形式組成初始基，得到初始基可行解初始單純形表cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000為入基變量為出基變量[]cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000[]cj

→23000CB基bx1x2x3x4x5cj

-zjx3x4x2003301001/5164001062010-2/52000-3/5為入基變量為出基變量[]cj

→23000CB基bx1x2x3x4x5cj

-zjx1x4x2203301001/5400-214/53101/20-1/500-10-1/5上表中所有的

j≤0,得到最優(yōu)解為

X=(3,3,0,4,0

).最優(yōu)值為

1、當(dāng)取法不唯一時(shí)，可任取一個(gè)對(duì)應(yīng)的xj為入基變量。2、相持，即取法不唯一時(shí)。可任取一個(gè)基變量作為出基變量，則下表中其他基變量的值將等于0，這種現(xiàn)象稱為退化。退化的基可行解關(guān)于單純形方法的幾點(diǎn)說(shuō)明(3)退化問(wèn)題的處理攝動(dòng)方法、字典序方法和Bland反循環(huán)方法問(wèn)題由定理知，一個(gè)非退化的線性規(guī)劃問(wèn)題一定可以在有限步內(nèi)得到最優(yōu)解或判定無(wú)最優(yōu)解。但是對(duì)于一個(gè)退化問(wèn)題，情況又怎樣呢？例1可見(jiàn)，它是一個(gè)退化的可行基。列出它的單純形表，并進(jìn)行迭代取作為初始可行基。cj

→3/4-1501/50-6000CB基bx1x2x3x4x5x6x70x501/4-60-1/2591000x601/2-90-1/5030100x710010001cj

-zj

3/4-1501/50-6000[]3/4x101-240-4/25364000x600303/50-15-2100x710010001cj

-zj

0307/50-33-3003/4x10108/25-84-1280-150x20011/500-1/2-1/151/3000x710010001cj

-zj

002/25-18-1-10[][]1/50x3025/801-525/2-75/2250-150x20-1/160101/401/120-1/6000x71-25/800525/275/2-251cj

-zj

-1/40032-30[]cj

→3/4-1501/50-6000CB基bx1x2x3x4x5x6x71/50x3025/801-525/2-75/2250-150x20-1/160101/401/120-1/6000x71-25/800525/275/2-251cj

-zj

-1/40032-30[]1/50x30-125/2105001050-1500-6x40-1/440011/3-2/300x71125/2-1050000-501501cj

-zj

1/2-120001-10上述迭代過(guò)程中，初始表與最后表完全相同，即迭代6次后，又回到初始基。出現(xiàn)了“死循環(huán)”，永遠(yuǎn)也得不到最優(yōu)解。[]0x50-5/42101/5001-30-6x401/6-30-1/150101/300x710010001cj

-zj

7/4-330-1/500020[]0x501/4-60-1/2591000x601/2-90-1/5030100x710010001cj

-zj

3/4-1501/50-600注:在實(shí)際計(jì)算中,單純形方法出現(xiàn)死循環(huán)的現(xiàn)象是極其少見(jiàn)的.為了解決這個(gè)問(wèn)題,1952年,A.Charnes

提出攝動(dòng)法;1954年,G.B.Dantzig

提出字典序法.本節(jié)例子是E.Beale于1955年提出的.

勃蘭特法則1974年,R.G.Bland利用組合方法成功地解決了退化的線性規(guī)劃問(wèn)題,并提出了兩條簡(jiǎn)便的規(guī)則,稱為勃蘭特法則：②選取最小比數(shù)中下標(biāo)最小的基變量為換出變量。①選取中下標(biāo)最小的非基變量為換入變量，其中§5單純形法的進(jìn)一步討論人工變量法兩階段法關(guān)于解的判別單純形法計(jì)算的向量矩陣描述單純形法小結(jié)例:用單純形法求解線性規(guī)劃問(wèn)題解：化為標(biāo)準(zhǔn)形式增加列向量,構(gòu)造出單位陣5-1人工變量法系數(shù)矩陣約束條件可相應(yīng)表位：人工變量約束條件中增加人工變量后,目標(biāo)函數(shù)如何處理?對(duì)任何可行解,原問(wèn)題的等式約束必須滿足,故在最優(yōu)解中人工變量取值必須為零.為此,令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個(gè)負(fù)值,用-M表示,只要當(dāng)人工變量的取值不為0,目標(biāo)函數(shù)就不可能極大化.cj

→-30100-

M-M

CB基bx1x2x3x4x5x6x70x441111000-

Mx61-21-10-110-

Mx790310001cj

-zj

-4M-34M10-

M00[]0x4330211-100x21-21-10-110-

Mx7660403-31cj

-zj

6M-304M+103M-4M00x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj

-zj

00303/2-M-3/2-M+1/20x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj

-zj

-9/2000-3/4-M+3/4-M-1/4[][]5-2兩階段法基本思想

第一階段：通過(guò)求解輔助問(wèn)題的最優(yōu)基可行解得到原問(wèn)題的初始基可行解。

第二階段：求原問(wèn)題的最優(yōu)解輔助問(wèn)題設(shè)原問(wèn)題為不妨假設(shè)如果某一個(gè)元素小于0,該方程兩邊乘于-1后則可以使右端數(shù)變成正數(shù)。考慮如下輔助問(wèn)題：其中首先用單純形法解輔助問(wèn)題。原問(wèn)題與輔助問(wèn)題的關(guān)系1.若原問(wèn)題有可行解,則輔助規(guī)劃的最優(yōu)值為0,反之亦然。就可以得到輔助規(guī)劃的初始基可行解3．輔助規(guī)劃有可行解同時(shí),所以即輔助問(wèn)題的目標(biāo)函數(shù)有下界,所以該問(wèn)題一定有最優(yōu)解。4．先求輔助規(guī)劃的最優(yōu)基可行解,如果最優(yōu)值為0，則所以其非零分量對(duì)應(yīng)系數(shù)矩陣的列向量線性無(wú)關(guān)。是原問(wèn)題的基可行解。的基可行解，2.由于,所以以為基變量，,所以是原問(wèn)題的可行解。由于是輔助規(guī)劃的非零分量對(duì)應(yīng)的系數(shù)矩陣的列向量也線性無(wú)關(guān),所以所以求輔助問(wèn)題的三種情況cj

→00000-1-1

CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj

-zj

-2400-100[]0x4330211-100x21-21-10-110-1x7660403-31cj

-zj

60403-400x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj

-zj

00000-1-1[][]0x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj

-zj

00000-1-1cj

→-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj

-zj

00303/20x400001-1/20x25/2-1/2100-1/41x33/23/20103/4cj

-zj

-9/2000-3/45-3關(guān)于解的判別例1用單純形法求解線性規(guī)劃問(wèn)題將上述問(wèn)題化為標(biāo)準(zhǔn)形式cj

→33000CB基bx1x2x3x4x53x13101/20-1/50x4400-214/53x2301001/5cj

-zj

00-3/200[]3x141001/400x5500-5/25/413x22011/2-1/40cj

-zj

00-3/200無(wú)窮多最優(yōu)解例2用單純形法求解線性規(guī)劃問(wèn)題將上述問(wèn)題化為標(biāo)準(zhǔn)形式cj

→230CB基bx1x2x30x116401cj

-zj230無(wú)界解例3用單純形法求解線性規(guī)劃問(wèn)題將上述問(wèn)題化為標(biāo)準(zhǔn)形式cj

→2300-MCB基bx1x2x3x4x50x31222100-Mx514120-11cj

-zj2+M3+2M0-M03x26111/200-Mx52-10-1-11cj

-zj-1-M0-3/2-M-M0無(wú)解5-4單純形法計(jì)算的向量矩陣描述線性規(guī)劃的標(biāo)準(zhǔn)形式初始單純形表為初始解非基變量基變量bBNIcj-zj

N0,…,0基可行解基變量非基變量B-1bIB-1NB-1cj-zj0,…,0-y1,…,-ym關(guān)系：或s.t.

例1用單純形法求解線性規(guī)劃問(wèn)題(計(jì)算用向量矩陣描述)解：將上述問(wèn)題化為標(biāo)準(zhǔn)形式組成初始基，初始單純形表cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj23000組成基若取0x40100cj

→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj

-zj00-10-1/50x40100cj

→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj

-zj230000x40100cj

→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj

-zj00-10-1/50x401006數(shù)據(jù)包絡(luò)分析數(shù)據(jù)包絡(luò)分析(dataenvelopentanalysis,DEA)：一種對(duì)具有相同類型決策單元進(jìn)行績(jī)效評(píng)價(jià)的方法.衡量單位績(jī)效的指標(biāo)：投入產(chǎn)出比(一個(gè)投入一個(gè)產(chǎn)出)6-1

基本概念例11

有4個(gè)銀行儲(chǔ)蓄所,每月均完成10000筆人民幣的存款、取款業(yè)務(wù),但投入情況不同,見(jiàn)下表,試分析這4個(gè)儲(chǔ)蓄所的績(jī)效儲(chǔ)蓄所B1B2B3B4職員數(shù)63107營(yíng)業(yè)面積(m2)1001205070解：o6職員數(shù)營(yíng)業(yè)面積1293120906030B1B2B4B3連接B2B4和B4B3組成一條凸的折線，通過(guò)B3作水平線,通過(guò)B2作一垂線。生產(chǎn)可行集：虛線和折線B2B4B3右上方所有點(diǎn)組成的集合生產(chǎn)前沿面：由虛線和折線B2B4B3形成的數(shù)據(jù)包絡(luò)線DEA有效：處于生產(chǎn)前沿面上的決策單元DD(5.6,93.3)6-2

評(píng)價(jià)決策單元DEA有效性的C2R模型DEA有效性的評(píng)價(jià)是對(duì)已有決策單元績(jī)效的比較評(píng)價(jià)，屬相對(duì)評(píng)價(jià)。設(shè)有n個(gè)決策單元(j=1,2,…,n),每個(gè)決策單元有相同的m項(xiàng)投入(i=1,2,…,m),和相同的s項(xiàng)產(chǎn)出(r=1,2,…,s)。xij:

第j單元的第i項(xiàng)投入量；yrj

:

第j單元的第r項(xiàng)產(chǎn)出量；vi：第i項(xiàng)投入的權(quán)值；ur：第r項(xiàng)產(chǎn)出的權(quán)值；決策單元投入產(chǎn)出hj：第j決策單元投入產(chǎn)出比通過(guò)適當(dāng)選取權(quán)值vi和ur，使對(duì)j=1,…,n有則對(duì)第j0個(gè)決策單元的績(jī)效評(píng)價(jià)可歸結(jié)為如下優(yōu)化模型：分式規(guī)劃模型對(duì)偶問(wèn)題對(duì)偶問(wèn)題的經(jīng)濟(jì)意義：為了評(píng)價(jià)j0決策單元的績(jī)效，可用一個(gè)假想的組合決策單元與其比較.決策單元的投入和產(chǎn)出.分別表示這個(gè)組合若非DEA有效若DEA有效課后習(xí)題1.8已知某線性規(guī)劃問(wèn)題的和用單純形法得到的表如下,試求未知數(shù)a~l的值.x1x2x3x4x5x46bcd10x51-13e01cj

-zja-1200初始單純形表x1x2x3x4x5x1fg2-11/20x54hi11/21cj

-zj0-7jkl迭代后x1為入基變量g=1,h=0(1)(1’)(2)(2’)(1)×1/2=(1’)b=2,c=4,d=-2,f=3(1)×1/2+(2)=(2’)i=5(1)×(-3/2)+(3)=(3’)(3)(3’)j=5,k=-3/2,l=01.9試將下述問(wèn)題改寫成線性規(guī)劃問(wèn)題轉(zhuǎn)化

1.10判斷下列說(shuō)法是否正確,并簡(jiǎn)要說(shuō)明理由.a)對(duì)取值無(wú)約束的變量xj

,通常令,其中,在用單純形法求得的最優(yōu)解中,有可能同時(shí)出現(xiàn).b)若X1,X2分別是某一線性規(guī)劃的最優(yōu)解,則X=λX1+(1-λ)X2也是該問(wèn)題的最優(yōu)解,其中0≤λ

≤1。c)單純形法計(jì)算中選取最大正檢驗(yàn)數(shù)對(duì)應(yīng)的變量作為換入基的變量，將使迭代后的目標(biāo)函數(shù)值得到最快增長(zhǎng).╳╳√

1.10判斷下列說(shuō)法是否正確,并簡(jiǎn)要說(shuō)明理由.a)對(duì)取值無(wú)約束的變量xj

,通常令,其中,在用單純形法求得的最優(yōu)解中,有可能同時(shí)出現(xiàn).╳設(shè)xj

對(duì)應(yīng)的列為Pj

，則對(duì)應(yīng)的列為Pj

和-Pj分析：若在最優(yōu)解中,同時(shí)出現(xiàn)則一定為基變量，Pj

和–Pj一定同時(shí)為基向量，這樣與基的定義產(chǎn)生矛盾

1.10判斷下列說(shuō)法是否正確,并簡(jiǎn)要說(shuō)明理由.c)單純形法計(jì)算中選取最大正檢驗(yàn)數(shù)對(duì)應(yīng)的變量作為換入基的變量，將使迭代后的目標(biāo)函數(shù)值得到最快增長(zhǎng).分析：s.t.

cj

→22.1000CB基bx1x2x3x4x50x312221000x