運(yùn)籌學(xué)單純形法課件

1、1單純形法單純形法n單純形法的引入單純形法的引入n單純形法的基本原理單純形法的基本原理n單純形法的迭代步驟與解的討論單純形法的迭代步驟與解的討論n初始可行基的求法初始可行基的求法2單純形法單純形法n單純形法單純形法(simplex algorithm)(simplex algorithm)是求解線性規(guī)是求解線性規(guī)劃問題的基本方法之一，它是美國學(xué)者劃問題的基本方法之一，它是美國學(xué)者（g.b.dantzigg.b.dantzig) )在年提出來的，在年提出來的，年，他又提出了改進(jìn)單純形法年，他又提出了改進(jìn)單純形法年，（年，（ealeeale) )提出了對偶單純形法，提出了對偶單純形法，隨后又出現(xiàn)了

2、原始對偶單純形法，使單隨后又出現(xiàn)了原始對偶單純形法，使單純形法更為完善純形法更為完善3復(fù)習(xí)概念復(fù)習(xí)概念: :一、線性規(guī)劃問題的解的概念一、線性規(guī)劃問題的解的概念 可行解可行解 最優(yōu)解最優(yōu)解 基基 基解（基本解）基解（基本解） 基可行解基可行解 可行基可行基4單純形法的引入單純形法的引入n下面通過一個計(jì)算實(shí)下面通過一個計(jì)算實(shí)例引入單純形法例引入單純形法n例求解（）問例求解（）問題題n問題的標(biāo)準(zhǔn)形式為問題的標(biāo)準(zhǔn)形式為0,15051003217025. .1810max2121212121xxxxxxxxtsxxz) 5 , 2 , 1( 015051003217025. .1810max52142

3、132121jxxxxxxxxxxt sxxzj(2.2)5單純形法單純形法 此線性規(guī)劃問題此線性規(guī)劃問題轉(zhuǎn)化為了一個含有轉(zhuǎn)化為了一個含有五個變量的五個變量的標(biāo)準(zhǔn)標(biāo)準(zhǔn)形形線性規(guī)劃問題，線性規(guī)劃問題， 為松弛變量。為求解上為松弛變量。為求解上面的面的lp問題，我們要考慮滿足約束條件問題，我們要考慮滿足約束條件s.t.并使并使 z 取取得得max的的x x1 1，x x2 2，x x3 3，x x4 4及及x5x5的值，由此分析如下的值，由此分析如下- -543,xxx6單純形法單純形法確定初始基可行解：確定初始基可行解： 通過觀察可以發(fā)現(xiàn)，松弛變量通過觀察可以發(fā)現(xiàn)，松弛變量 對應(yīng)的等式對應(yīng)的等式

4、約束條件中的約束條件中的系數(shù)矩陣為單位矩陣可以作為初始系數(shù)矩陣為單位矩陣可以作為初始可行基可行基矩陣。因此矩陣。因此?。喝。?為基變量；為基變量；x1，x2為非基變量。則（為非基變量。則（2.22.2）可變?yōu)椋┛勺優(yōu)?543,xxx543,xxx)5 ,2, 1(051503210025170.1810max21521421321jxxxxxxxxxxtsxxzj(2.4)7(2.2(2.2）或）或（2.42.4）稱為關(guān)于基的稱為關(guān)于基的典式典式 1 1、等式、等式約束條件中顯含約束條件中顯含基可行解基可行解 2 2、目標(biāo)函數(shù)中不、目標(biāo)函數(shù)中不含含基變量基變量)5 , 2 , 1(015051

5、003217025. .1810max52142132121jxxxxxxxxxxtsxxzj)5 , 2 , 1(051503210025170. .1810max21521421321jxxxxxxxxxxtsxxzj(2.2)(2.4)8約束方程的系數(shù)矩陣為約束方程的系數(shù)矩陣為因?yàn)榫€性無關(guān)，故可以作為一個初因?yàn)榫€性無關(guān)，故可以作為一個初始基：始基： 令非基變量令非基變量 則得到初始基可行解則得到初始基可行解 對應(yīng)的目標(biāo)函數(shù)值對應(yīng)的目標(biāo)函數(shù)值 ),(100510103200125521pppa543,pppipppb),(5430021xx150,100,170, 0, 0) 0 (x0)

6、0(z9這個初始可行解表示：工廠沒有安排生產(chǎn)產(chǎn)品甲、這個初始可行解表示：工廠沒有安排生產(chǎn)產(chǎn)品甲、乙，因此乙，因此 三種資源都沒有利用，工廠三種資源都沒有利用，工廠的利潤指標(biāo)的利潤指標(biāo)最優(yōu)性檢驗(yàn)：最優(yōu)性檢驗(yàn)： 基本可行解基本可行解 是最優(yōu)解嗎？顯然不是。應(yīng)是最優(yōu)解嗎？顯然不是。應(yīng)尋找更好的解。從問題的數(shù)學(xué)角度分析，在尋找更好的解。從問題的數(shù)學(xué)角度分析，在典式（典式（2.22.2）的目標(biāo)函數(shù)中，）的目標(biāo)函數(shù)中，非基變量非基變量x1，x2前的系數(shù)都為正，表明前的系數(shù)都為正，表明目標(biāo)函數(shù)值有增加的目標(biāo)函數(shù)值有增加的可能。只要將目標(biāo)函數(shù)中可能。只要將目標(biāo)函數(shù)中系數(shù)為正的某系數(shù)為正的某非基非基變量變量與某

7、一基變量地位對換。與某一基變量地位對換。321,aaa0)0(z)0(x10單純形法單純形法換基迭代：換基迭代： 進(jìn)行進(jìn)行換基就是要從非基變量中選一個變量換基就是要從非基變量中選一個變量入基入基，再，再從基變量中選一個變量從基變量中選一個變量出基出基。并且換基后仍需滿足：。并且換基后仍需滿足：1 1、新的解仍是基本新的解仍是基本可行解；可行解；2 2、目標(biāo)函數(shù)值將得到改善。目標(biāo)函數(shù)值將得到改善。11單純形法單純形法選擇入基變量：選擇入基變量： 由于在目標(biāo)函數(shù)由于在目標(biāo)函數(shù) 中中x1，x2的系數(shù)都為正，哪一個入基都可使目的系數(shù)都為正，哪一個入基都可使目標(biāo)函數(shù)值得到改善。對于求目標(biāo)函數(shù)極大化標(biāo)函數(shù)

8、值得到改善。對于求目標(biāo)函數(shù)極大化的問題，我們希望目標(biāo)值增加得越快越好，因的問題，我們希望目標(biāo)值增加得越快越好，因此系數(shù)最大的此系數(shù)最大的x2入基。入基。選擇出基變量：選擇出基變量： x2入基后，其值從零增加并由入基后，其值從零增加并由于于約束條件的原因會引起其他變量的變化。由約束條件的原因會引起其他變量的變化。由典式典式（2.42.4）以及變量必須取正值的條件，我們以及變量必須取正值的條件，我們可以得到下列不等式關(guān)系：可以得到下列不等式關(guān)系：211810 xxz12當(dāng)當(dāng) 時，時， 為換入變量為換入變量01x2x0 51500 3 10002170252423xxxxxx確定換出變量確定換出變量

9、30)5150 3100 2170min( 2x5x為換出變量為換出變量接下來有下式：接下來有下式： 3 1505 2 21003 1 5170 2 125124123xxxxxxxxx13 用高斯法，將用高斯法，將 的系數(shù)列向量換為單位列向量，的系數(shù)列向量換為單位列向量，其步驟是：其步驟是：2x)(3(-3)2)()(2,)(3(-2)(1)(1 ,5(3)(3化簡后得新的典式方程化簡后得新的典式方程:51251451351 x5130 53 57 10 52523110 xxxxxxxx 3 150 5 2 2100 3 1 5170 2 125124123xxxxxxxxx14代入目標(biāo)函

10、數(shù)：代入目標(biāo)函數(shù)：51215185325401810 xxxxz此時：令此時：令 得到另一個基本可行解得到另一個基本可行解 =（0，30，110，10，0）此時）此時 , 051 xx540)1(z這樣我們就完成了第一次迭代這樣我們就完成了第一次迭代. .由于目標(biāo)函數(shù)中由于目標(biāo)函數(shù)中非其變量非其變量 的系數(shù)仍是正數(shù)的系數(shù)仍是正數(shù), ,這說明目標(biāo)函數(shù)這說明目標(biāo)函數(shù)值還可以增大值還可以增大, , 不是最優(yōu)解不是最優(yōu)解. .1x)1(x)1(x15)0,0,7540,7200,750(74100maxz 767327410054xxz重復(fù)上述步驟重復(fù)上述步驟, ,確定確定 進(jìn)基進(jìn)基, , 出基出基,

11、 ,繼續(xù)迭代繼續(xù)迭代, ,則新的典式方程變?yōu)閯t新的典式方程變?yōu)? :1x4x5425415437271720073757507117237540 xxxxxxxxxx16此時松弛變量此時松弛變量 都是非基變量都是非基變量（取值為零取值為零），這表明資源已用這表明資源已用盡；并且目標(biāo)函數(shù)值盡；并且目標(biāo)函數(shù)值 中中非基變量非基變量 的系數(shù)全為負(fù)值，說明目的系數(shù)全為負(fù)值，說明目標(biāo)函數(shù)已無法進(jìn)一步改善，因此該解已是最優(yōu)標(biāo)函數(shù)已無法進(jìn)一步改善，因此該解已是最優(yōu)解。解。74100z54,xx17找出一個初始可行解找出一個初始可行解是否最優(yōu)是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更大的基本可行解

12、）（找更大的基本可行解）最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)直到找出為止，核心是：變量迭代直到找出為止，核心是：變量迭代結(jié)束結(jié)束其步驟總結(jié)如下：其步驟總結(jié)如下：18換基迭代：換基迭代： 進(jìn)行進(jìn)行換基就是要從非基變量中選一個變量換基就是要從非基變量中選一個變量入基入基，再從基變量中選一個變量再從基變量中選一個變量出基出基。并且換基后仍需。并且換基后仍需滿足：滿足：1 1、新的解仍是基本新的解仍是基本可行解；可行解；2 2、目標(biāo)函數(shù)值將得到改善。目標(biāo)函數(shù)值將得到改善。單純形法單純形法19單純形法的基本原理單純形法的基本原理線性規(guī)劃的典式線性規(guī)劃的典式: :對于標(biāo)準(zhǔn)形線性規(guī)劃問題對于標(biāo)準(zhǔn)形線性規(guī)劃問題),

13、2 , 1(0. .max221122222121112121112211njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn20), 2 , 1(0. .max22112222221211112121112211mnjxbxxaxaxabxxaxaxabxxaxaxatsxcxcxczjmmnnmnmmnnnnnnnn對此問題添加對此問題添加m個松弛變量后，可得下面線性規(guī)劃個松弛變量后，可得下面線性規(guī)劃問題并且是典式的形式。問題并且是典式的形式。21將上面將上面典式中各變量及系數(shù)填寫在一張表格中典式中各變量及系數(shù)填寫在一張表格中就形成下面的就形成下面的

14、單純形表單純形表: :c c1 c2 cn cn+1 cn+2 cn+mcbb x1 x2 xn xn+1 xn+2 xn+10000 xn+1xn+1xn+1 b1 b2 bm a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 112mj = cj zj c1 c2 cn 0 0 0j = cj zj 1 2 n n+1 n+2 n+m bx22上面的單純形表還可以表示成矩陣的形式上面的單純形表還可以表示成矩陣的形式基基解解 x xs xsb a i j c 0n基基解解 xb xn xs xsb b n i j cb cn 023由單純形表進(jìn)行迭代步驟：由單純

15、形表進(jìn)行迭代步驟：選擇選擇 xj 入基：當(dāng)入基：當(dāng) j 行中行中 cj= max cicj= max cici ci 0 0 選擇選擇 xi 出基：當(dāng)出基：當(dāng)i = min bi/aij= min bi/aijaijaij 0 0換基換基迭代：當(dāng)確定了迭代：當(dāng)確定了入基變量入基變量 xj 、出基變量、出基變量 xi 后，以后，以 aij 作為主元對作為主元對單純形表進(jìn)行初等單純形表進(jìn)行初等行變換（取主運(yùn)算），即將行變換（取主運(yùn)算），即將 aij 所在列除采所在列除采用初等行變換用初等行變換將將 aii 變換為變換為1外的其余元素都外的其余元素都變換為變換為 0 0。注意這種變換只能采用。注意這

16、種變換只能采用初等行變初等行變換換! !24單純形方法的矩陣描述：單純形方法的矩陣描述：設(shè)線性規(guī)劃問題設(shè)線性規(guī)劃問題 max z = cx max z = cx + 0xs s.t. ax b s.t. ax + i xns= b （i 式式） x 0 x ，xs 0其中其中 b 0 ，i 是是 mm 單位單位矩陣。矩陣。對上面（對上面（i 式式）經(jīng)過迭代，）經(jīng)過迭代，并設(shè)最終的最優(yōu)基矩陣為并設(shè)最終的最優(yōu)基矩陣為b（不妨設(shè)（不妨設(shè)b 為為a 的的首首m 列，則將（列，則將（i 式式）改寫后有）改寫后有25線性規(guī)劃線性規(guī)劃 linear programming（lp）單純形法單純形法max z

17、= cbxb + cnxn + 0xs s.t. bxb + nxn + i xs = 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)最優(yōu)目標(biāo)函數(shù)值目標(biāo)函數(shù)值z*= cb b -1 ，檢驗(yàn)數(shù)，檢驗(yàn)數(shù) cn - cb b -1 0 ， - cb b -1 0單純形方法單純形方法迭代迭代（i 式）式）（b 式式）26線性規(guī)劃線性規(guī)劃 linear programming（lp）單純形法單純形法單純形方法的矩陣描述：單純形

18、方法的矩陣描述：基基解解 xb xn xs xsb b n i j cb cn 0基基解解 xb xn xs xbb -1b i b -1n b -1 j 0 cn - cb b 1n - cb b -1對應(yīng)對應(yīng)i 式式的的單純形表單純形表 i 表表對應(yīng)對應(yīng)b 式式的的單純形表單純形表 b 表表迭代27例例1將線性規(guī)劃問題化為典式將線性規(guī)劃問題化為典式,并列初始單純形表并列初始單純形表0,15051003217025. .1810max2121212121xxxxxxxxtsxxz543,xxx解：先引入松馳變量解：先引入松馳變量 將問題化為典式將問題化為典式)5 , 2 , 1(015051

19、003217025. .1810max52142132121jxxxxxxxxxxtsxxzj28取初始可行基取初始可行基 此時問題已是關(guān)于基此時問題已是關(guān)于基 的典式，故可直接作初始單純形表的典式，故可直接作初始單純形表ipppb),(54300b10 18 0 0 0 000 170100150 5 2 1 0 0 2 3 0 1 0 1 5 0 0 1z 010 18 0 0 0cbcbxb3x4x5x1x2x3x4x5x由表可知，初始基可行解（0，0，170，100，150），初始目標(biāo)函數(shù)值0)0(z29最優(yōu)性判別與基可行解的改進(jìn)最優(yōu)性判別與基可行解的改進(jìn)定理定理1(最優(yōu)性判別定理最優(yōu)

20、性判別定理)在在(lp)的典式中的典式中,設(shè)設(shè) 是對應(yīng)于基是對應(yīng)于基b的一的一個基可行解個基可行解.若有若有 則則 是是(lp)的最優(yōu)的最優(yōu)解解,并記為了并記為了 相應(yīng)的目標(biāo)函數(shù)最優(yōu)值相應(yīng)的目標(biāo)函數(shù)最優(yōu)值 這時的基這時的基b稱為最優(yōu)基稱為最優(yōu)基.tmbbbx)0 , 0 ,(21)0()., 2, 1(0nmmjjtmbbbx)0 , 0 ,(21tmbbbx)0 , 0 ,(21)0()0(zz30定理定理2(無界性判別定理無界性判別定理)在在(lp)的典式中，的典式中， 是對應(yīng)于基是對應(yīng)于基b的一個的一個基可行解。若有某個非基變量的檢驗(yàn)數(shù)基可行解。若有某個非基變量的檢驗(yàn)數(shù) 且有且有 即即

21、則原問題無界（或無有界最優(yōu)解）。則原問題無界（或無有界最優(yōu)解）。 tmbbbx)0 , 0 ,(21)0()1(0nkmk), 2 , 1(0miaik0kp31單純形法的迭代步驟：單純形法的迭代步驟：1、找出初始可行基，寫出對應(yīng)的典式，確定、找出初始可行基，寫出對應(yīng)的典式，確定初始基可行解，列初始單純形表。初始基可行解，列初始單純形表。2、檢驗(yàn)各非基變量、檢驗(yàn)各非基變量 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) ，若所有，若所有的的 ，則已求得最優(yōu)解。，則已求得最優(yōu)解。3、若在所有的、若在所有的 中，若有某個中，若有某個 對應(yīng)的對應(yīng)的 的系數(shù)列向量的系數(shù)列向量 ，則此問題，則此問題無界。無界。4、根據(jù)、根據(jù) 確定確

22、定 為進(jìn)基變量，又根據(jù)最小比值法則計(jì)算為進(jìn)基變量，又根據(jù)最小比值法則計(jì)算jxj), 2 , 1(0njj0j0kkx0kpnjjjk1 , 0maxkx32rkrikikiabmiaab1 ,0min確定確定 為出基變量，轉(zhuǎn)為出基變量，轉(zhuǎn)5。5、以、以 為主元進(jìn)行旋轉(zhuǎn)變換（即進(jìn)行矩陣的為主元進(jìn)行旋轉(zhuǎn)變換（即進(jìn)行矩陣的初等變換）將初等變換）將 所對應(yīng)的列向量變換為單位向量，所對應(yīng)的列向量變換為單位向量，同時應(yīng)將檢驗(yàn)數(shù)行中的同時應(yīng)將檢驗(yàn)數(shù)行中的 變?yōu)榱?，將變?yōu)榱?，?列中的列中的 換為換為 ，得新的單純形表。返回，得新的單純形表。返回2。從步驟從步驟2-5的每一個循環(huán)稱為的每一個循環(huán)稱為一次單純形

23、迭代一次單純形迭代，一，一個線性規(guī)劃問題往往要經(jīng)過多次迭代才能求得最個線性規(guī)劃問題往往要經(jīng)過多次迭代才能求得最優(yōu)解或者判定它無解。優(yōu)解或者判定它無解。kxikakxkbxrxkx33序號 10 18 0 0 0 1000170100150 5 2 1 0 0 2 3 0 1 0 1 5 0 0 10 10 18 0 0 0200181101030 0 1 0 0 0 1 1 0 0 -540 0 0 0 cbcbxb3x4x5xz1x2x3x4x5x3x4x2x5235257535151z53251834200181101030 0 1 0 0 0 1 1 0 0 -540 0 0 0 301

24、018 0 0 1 1 0 0 0 1 0 0 0 0 z3x4x2x5235257535151532518z3x1x2x7540750720074100723711757371727327635例例2用單純形法求解用單純形法求解0,3142342. .23max2121212121xxxxxxxxtsxxz解解:引入松馳變量引入松馳變量 , , 將問題化為標(biāo)將問題化為標(biāo)準(zhǔn)形式準(zhǔn)形式 3x4x5x)5 , 2 , 1(03142342. .23max52142132121jxxxxxxxxxxtsxxzj361c 3 2 0 0 0 0004143 -1 2 1 0 0 3 2 0 1 0 1

25、 -1 0 0 1z0 3 2 0 0 02003753 0 1 1 0 1 0 5 0 1 -3 1 -1 0 0 1z-9 0 5 0 0 -3bcbxb3x4x5x1x2x3x4x5x3x4x1x373023614 0 0 1 0 1 0 1 0 0z-14 0 0 0 -1 04023 0 0 1 0 1 0 1 0 0z-14 0 0 0 -1 03x2x1x5158515351525x2x1x4154132585818381414138例例3用單純形法求解用單純形法求解) 5 , 2 , 1(021322. .2max53243232122jxxxxxxxxxxtsxxzj解：因解

26、：因 是一個單位矩陣，故可是一個單位矩陣，故可取初始可行基取初始可行基),(541pppipppb),(541039c 0 1 2 0 0 1000212 1 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 12z0 0 1 2 0 0200274 1 -2 1 0 0 3 -5 0 1 0 1 -1 0 0 1z-4 -2 5 0 0 0bcbxb1x4x5x1x2x3x4x5x3x4x5x由定理由定理2知此（知此（lp）問題無解。）問題無解。40結(jié)論結(jié)論:1 :1、一般地說、一般地說, ,一個非退化的基可行解為線性一個非退化的基可行解為線性規(guī)劃問題的唯一最優(yōu)解的充分必要條件是它所

27、對規(guī)劃問題的唯一最優(yōu)解的充分必要條件是它所對應(yīng)的非基變量的檢驗(yàn)數(shù)全小于零應(yīng)的非基變量的檢驗(yàn)數(shù)全小于零, ,即即 . .如例題如例題1 1。2 2、一般來說，在一個線性規(guī)劃問題的最優(yōu)基對應(yīng)、一般來說，在一個線性規(guī)劃問題的最優(yōu)基對應(yīng)的單純形表中，如果非基變量的檢驗(yàn)數(shù)中有零，的單純形表中，如果非基變量的檢驗(yàn)數(shù)中有零，則該問題就有無窮多個最優(yōu)解。則該問題就有無窮多個最優(yōu)解。0n41 0,24261553221212121xxxxxxxxmaxz 0,24 2615 532432142132121 xxxxxxxxxxxxmaxz 0 0 -1/12 -7/24-33/4-z x2x112 x1 x2

28、x3 x4bxbcb 2 1 0 0cji15/43/4011/4-1/810 -1/125/24練習(xí)題練習(xí)題42初始可行基的求法初始可行基的求法人工變量法：人工變量法： 當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們或可得到當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們或可得到一個顯然的基本可行解（如一個顯然的基本可行解（如松弛變量作為基變量的松弛變量作為基變量的一個初始一個初始基本可行解），這樣我們就可以馬上進(jìn)入基本可行解），這樣我們就可以馬上進(jìn)入單純形表的運(yùn)算步驟。然而，并非所有單純形表的運(yùn)算步驟。然而，并非所有問題標(biāo)準(zhǔn)化問題標(biāo)準(zhǔn)化之后我們都可得到一個顯然的之后我們都可得到一個顯然的初始初始基本可行解，這基本可

29、行解，這時就需要我們首先確定出一個基本可行解作為時就需要我們首先確定出一個基本可行解作為初始初始基本可行解。通常采用的是人工變量法來確定這樣基本可行解。通常采用的是人工變量法來確定這樣的的初始初始基本可行解。這種情況下一般有兩種方法：基本可行解。這種情況下一般有兩種方法： 43 為了要在約束方程組的系數(shù)矩陣中湊成一個為了要在約束方程組的系數(shù)矩陣中湊成一個m mm m階的單位矩陣，以便形成一個初始可行基，可以在階的單位矩陣，以便形成一個初始可行基，可以在每個約束方程中人為地加上一個變量每個約束方程中人為地加上一個變量 ，稱為人工變，稱為人工變量。但是量。但是, ,由于引入了人工變量由于引入了人工

30、變量, ,得到的線性規(guī)劃問得到的線性規(guī)劃問題就不可能與原問題等價題就不可能與原問題等價( (因?yàn)槿斯ぷ兞康囊胍呀?jīng)因?yàn)槿斯ぷ兞康囊胍呀?jīng)改變了原問題的約束條件改變了原問題的約束條件). ).為了求解原問題為了求解原問題, ,要設(shè)法要設(shè)法排除人工變量排除人工變量. .下面介紹兩種排除人工變量的方法下面介紹兩種排除人工變量的方法, ,它也是求初始可行基和初始基可行解的方法它也是求初始可行基和初始基可行解的方法. .一般有一般有兩種方法兩種方法: :1 1、大、大mm法（罰因子法）法（罰因子法） 2 2、兩階段法、兩階段法441 1、大、大mm法：即假定人工變量在目標(biāo)函數(shù)中的系數(shù)法：即假定人工變量在

31、目標(biāo)函數(shù)中的系數(shù)為為mm（充分大的正數(shù)），對于求極大值而言，需加（充分大的正數(shù)），對于求極大值而言，需加-m-m。這樣，只要在基本可行解中還有人工變量是。這樣，只要在基本可行解中還有人工變量是基變量，且取值不為零，則目標(biāo)函數(shù)就不可能最大基變量，且取值不為零，則目標(biāo)函數(shù)就不可能最大值（對于極小值問題而言，人工變量在目標(biāo)函數(shù)中值（對于極小值問題而言，人工變量在目標(biāo)函數(shù)中的系數(shù)取的系數(shù)取+m).+m).45單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論1、大、大 m 法（罰因子法）法（罰因子法）max z = - 3x1 + x3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 +

32、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 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0461、大、大 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 ，

33、x4 ， x5 ， x6 ， x7 0基基xb解解b-1bx1x2x3x4x5x6x7 x441111000x61-21-10-110x790310001檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-30100-m-m471、大、大 m 法法基基xb解解b-1bx1x2x3x4x5x6x7 x441111000x61-21-10-110x790310001檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-3-2mm1-m0-m0-m基基xb解解b-1bx1x2x3x4x5x6x7 x441111000x61-21-10-110x790310001檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-3-2m4m10-m00481、大、大 m 法法基基xb解解b-1bx1x2x3x4x5x

34、6x7 x4411110004x61-21-10-1101x7903100013檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-3-2m4m10-m00基基xb解解b-1bx1x2x3x4x5x6x7 x4330211-10x21-21-10-110x7660403-31檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-3+6m01+4m03m-4m0491、大、大 m 法法基基xb解解b-1bx1x2x3x4x5x6x7 x4411110004x61-21-10-1101x7903100013檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-3-2m4m10-m00基基xb解解b-1bx1x2x3x4x5x6x7 x4330211-10x21-21-10-110x7660403-31

35、檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-3+6m01+4m03m-4m0501、大、大 m 法法基基xb解解b-1bx1x2x3x4x5x6x7 x400001-1/21/2-1/2-x23011/30001/39x11102/301/2-1/21/63/2檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00301.5-1.5-m0.5-m基基xb解解b-1bx1x2x3x4x5x6x7 x400001-1/21/2-1/2x25/2-1/2100-1/41/41/4x33/23/20103/4-3/41/4檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-9/2000-3/43/4-m-1/4-m51單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論采用大采用大 m m 法求解線性規(guī)劃

36、問題時可能出現(xiàn)的幾種情況：法求解線性規(guī)劃問題時可能出現(xiàn)的幾種情況：1 1、當(dāng)采用單純形法求解、當(dāng)采用單純形法求解 lplpmm 得到最優(yōu)解時，基變量得到最優(yōu)解時，基變量不含不含任何任何人工變量，則所得到的最優(yōu)解就是原問題的最優(yōu)解；人工變量，則所得到的最優(yōu)解就是原問題的最優(yōu)解；2 2、當(dāng)采用單純形法求解、當(dāng)采用單純形法求解 lplpmm 得到最優(yōu)解時，基變量至少得到最優(yōu)解時，基變量至少含有含有一個人工變量且一個人工變量且非零非零，則原問題無可行解；，則原問題無可行解；3 3、當(dāng)采用單純形法求解、當(dāng)采用單純形法求解 lplpmm 得到最優(yōu)解時，基變量至少得到最優(yōu)解時，基變量至少含有含有一個人工變量

37、且人工變量都一個人工變量且人工變量都為零為零，則通過變換得到原問題最優(yōu)，則通過變換得到原問題最優(yōu)解；解；52 0,1 2324112 3max32131321321321xxxxxxxxxxxxxxz例例1用大用大m法求解法求解解解:引入松馳變量引入松馳變量 , 和人工變量和人工變量 及一及一個充分大的個充分大的m 0,將原問題化為大將原問題化為大m問題問題 4x5x76,xx53 0, 1 2 3 24 11 2 3max32173165 321432176321xxxxxxxxxxxxxxxmxmxxxxz54c3-1-100-m-mcbxbbx1x2x3x4x5x6x70 x4111-2

38、11000-mx63-4120-110-mx71-20100014m3-6m-1+m-1+3m0-m00cbxbbx1x2x3x4x5x6x70 x4103-20100-1-mx610100-11-2-1x31-20100011+m1-1+m00-m01-3mzz55c3-1-100-m-mcbxbbx1x2x3x4x5x6x70 x4123001-22-5-1x210100-11-2-1x31-201000121000-11-m-1-mcbxbbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-20

39、00-1/3-1/31/3-m2/3-m最優(yōu)解為最優(yōu)解為（4 , 1 , 9 , 0 ,0 , 0 , 0）， = 2zzz56單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論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 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0572、兩階段

40、法、兩階段法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-1bx1x2x3x4x5x6x7 x441111000x61-21-10-110x790310001檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00000-1-1582、兩階段法、兩階段法第第i 階段階段基基xb解解b-1bx1x2x3x4x5x6x7 x441111000x61-21-10-110x790310001檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00000-1-

41、1基基xb解解b-1bx1x2x3x4x5x6x7 x441111000x61-21-10-110x790310001檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-2400-100592、兩階段法、兩階段法第第i 階段階段基基xb解解b-1bx1x2x3x4x5x6x7 x4411110004x61-21-10-1101x7903100013檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-2400-100基基xb解解b-1bx1x2x3x4x5x6x7 x4330211-10x21-21-10-110x7660403-31檢驗(yàn)數(shù)檢驗(yàn)數(shù) j60403-40602、兩階段法、兩階段法第第i 階段階段基基xb解解b-1bx1x2x3x4x5x6x7 x44

42、11110004x61-21-10-1101x7903100013檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-2400-100基基xb解解b-1bx1x2x3x4x5x6x7 x4330211-10x21-21-10-110x7660403-31檢驗(yàn)數(shù)檢驗(yàn)數(shù) j60403-40612、兩階段法、兩階段法第第i 階段階段基基xb解解b-1bx1x2x3x4x5x6x7 x4330211-101x21-21-10-110-x7660403-311檢驗(yàn)數(shù)檢驗(yàn)數(shù) j60403-40基基xb解解b-1bx1x2x3x4x5x6x7 x400001-1/21/2-1/2x23011/30001/3x11102/301/2-1/21

43、/6檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00000-1-1622、兩階段法、兩階段法第第ii 階段階段基基xb解解b-1bx1x2x3x4x5x6x7 x400001-1/21/2-1/2x23011/30001/3x11102/301/2-1/21/6檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00000-1-1基基xb解解b-1bx1x2x3x4x5 x400001-1/2x23011/300x11102/301/2檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00303/2-30100632、兩階段法、兩階段法第第ii 階段階段基基xb解解b-1bx1x2x3x4x5 x400001-1/2-x23011/3009x11102/301/23/2檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00

44、303/2基基xb解解b-1bx1x2x3x4x5 x400001-1/2x25/2-1/2100-1/4x33/23/20103/4檢驗(yàn)數(shù)檢驗(yàn)數(shù) j-9/2000-3/464單純形法中的幾個問題單純形法中的幾個問題1. 1.目標(biāo)函數(shù)極小化時，解的最優(yōu)判別：目標(biāo)函數(shù)極小化時，解的最優(yōu)判別： j j 02. 2.退化退化一個或幾個一個或幾個基變量基變量等于零，一個簡單易行的等于零，一個簡單易行的避免退化的方法是避免退化的方法是19741974年由勃蘭德（年由勃蘭德（blandbland）提出）提出的的bkandbkand 法則。法則。3. 3.無可行解的判別：無可行解的判別： 在采用人工變量求解

45、線性規(guī)劃問題得到最優(yōu)在采用人工變量求解線性規(guī)劃問題得到最優(yōu)解時，如果基變量中仍含有解時，如果基變量中仍含有非零人工變量非零人工變量，則原，則原問題無可行解。問題無可行解。65 對上述模型求解（單純形法），若對上述模型求解（單純形法），若w=0,w=0,說明問題說明問題存在基本可行解，可以進(jìn)行第二個階段；否則，原問存在基本可行解，可以進(jìn)行第二個階段；否則，原問題無可行解，停止運(yùn)算。題無可行解，停止運(yùn)算。 第二階段：在第一階段的最終表中，去掉人工變第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的

46、初始表（用單純形法計(jì)算）。作為第二階段計(jì)算的初始表（用單純形法計(jì)算）。例：例： 0, 1 2 3 24 11 2 3min32173165 3214321321xxxxxxxxxxxxxxxxxxz第一階段第一階段66cj0000011cbxbbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-20100011-z46-1-301000 x4103-20100-11x610100-11-210 x31-2010001-z10-100103i0 x4123001-22-50 x210100-11-20 x31-2010000-z00000011

47、67cj-31100cbxbbx1x2x3x4x50 x4123001-241x210100-11x31-20100-z-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3-z20001/31/3i第二階段第二階段 最優(yōu)解為（最優(yōu)解為（4 1 9 0 04 1 9 0 0），目標(biāo)函數(shù)），目標(biāo)函數(shù) z = -2z = -2683231 323x , 3 :052122 xxxbbii，變變換換有有：兩兩端端乘乘如如、6 6、無、無可行解的判斷：運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，可行解的判斷：運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，仍含有人工變量，無可行解。仍含有人工變量，無可行解。)

48、0 )0( 0 0 min max 7 jjjjjjjjczczzczc（或或或或、檢檢驗(yàn)驗(yàn)數(shù)數(shù)：69 8 8、退化：、退化： 即計(jì)算出的即計(jì)算出的（用于確定換（用于確定換出變量）存在有兩個以上相同的最小比值，出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。等于零，這就是退化（會產(chǎn)生退化解）。 雖任意換出變量，目標(biāo)函數(shù)值不變，但雖任意換出變量，目標(biāo)函數(shù)值不變，但此時不同的基卻表示為同一頂點(diǎn)，其特例此時不同的基卻表示為同一頂點(diǎn)，其特例是永遠(yuǎn)達(dá)不到最優(yōu)解。需作如下處理：是永遠(yuǎn)達(dá)不到最優(yōu)解。需作如下處理

49、： . .當(dāng)當(dāng) 中出現(xiàn)兩個以上最大值中出現(xiàn)兩個以上最大值時，時，選下標(biāo)最小的非基變量為換入變量；選下標(biāo)最小的非基變量為換入變量； . .當(dāng)當(dāng)中出現(xiàn)兩個以上最小值時，選下中出現(xiàn)兩個以上最小值時，選下標(biāo)最小的基變量為換出變量。標(biāo)最小的基變量為換出變量。0 jjzc70二、人工變量法注意事項(xiàng)二、人工變量法注意事項(xiàng)n最終單純形表中人工變量仍為基變量，最終單純形表中人工變量仍為基變量，則此線性規(guī)劃問題無可行解。則此線性規(guī)劃問題無可行解。n約束條件為約束條件為=時時, ,先用剩余變量變?yōu)闃?biāo)準(zhǔn)先用剩余變量變?yōu)闃?biāo)準(zhǔn)形形, ,再加人工變量構(gòu)造單位矩陣。再加人工變量構(gòu)造單位矩陣。n計(jì)算機(jī)采用兩階段法計(jì)算含大于等于

50、和計(jì)算機(jī)采用兩階段法計(jì)算含大于等于和等于條件的線性規(guī)劃模型。等于條件的線性規(guī)劃模型。71建建立立模模型型個個 數(shù)數(shù)取取 值值右右 端端 項(xiàng)項(xiàng)等式或等式或不等式不等式極大或極小極大或極小新加新加變量變量系數(shù)系數(shù)兩兩個個三個三個以上以上xj0 xj無無約束約束xj 0 bi 0bi 0=maxzminzxs xa求求解解圖圖解解法、法、單單純純形形法法單單純純形形法法不不處處理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不處處理理約束約束條件條件兩端兩端同乘同乘以以-1加加松松弛弛變變量量xs加加入入人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=-

51、zminz=max z0-m根據(jù)上表列出初始單純形表根據(jù)上表列出初始單純形表 a（二）、線性規(guī)劃小結(jié)（二）、線性規(guī)劃小結(jié)72停止停止ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika對對任任一一)0( lklkiiaab 計(jì)計(jì)算算lkxx替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個個ax含有含有量中是否量中是否基變基變 0 j非非基基變變量量的的有有某某個個最最優(yōu)優(yōu)解解一一唯唯 無無可可行行解解最優(yōu)解最優(yōu)解無窮多無窮多是是否否環(huán)環(huán)循循否否否否否否是是是是是是循環(huán)循環(huán)無無界界解解73練習(xí)練習(xí) 0,10527532max32132132

52、1321xxxxxxxxxxxxz 0,105270532max654321653214321654321xxxxxxxxxxxxxxxmxxmxxxxz74-m+1/7-1/7-m-16/7-50/700-102/7-z1/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxbcb-m0-m-532cj0-m0-5+2m3-4m2+3m-z51-101-5210 x6-m70011117x4-mx6x5x4x3x2x1bxbcb-m0-m-532cji75作業(yè)作業(yè) 無無約約束束43214321432143214321 , 0,2232

53、143 22 4 5243xxxxxxxxxxxxxxxxxxxxminz760, 02 )( 23214 )( 3 2 )( 2 400)( 5243max0.,1053110965321865321765321109876532165654xxxxxxxxxxxxxxxxxxxxxmxxxmxxxxxxzxxxxx令：770100 x2-4-2/35/3-10/3x1300-z-1/3-1/300-2/32/3-1/32/3x2-440 10-1/31/3105/3-5/310/340/310/3 x804-1/31/301-1/31/3-5/34/3 x7-mx10 x9x8x7x6x5

54、x3bxbcb-m00-m5-52cji 3101m 352m 37 m37m34 m344m 4m-4311x2-43-6m-21-4x130-m005-3m3m-52-3m-z2/31-100-22-12x10-m14 400101-1314 4 x8020001-11-22 x7-mx10 x9x8x7x6x5x3bxbcb-m00-m5-52cji 780100 x2-4-31/2-3/25/2-15/2x13-m0-1/2-m+9/200-17/22 7-z001/21/2001/28 3x2-4001/2-1/21-15/26 1 x65-111/25/200-5/210 5 x9

55、0 x10 x9x8x7x6x5x3bxbcb-m00-m5-52cji 0100 x2-4-13-45-10 x13-m00-m+41-1-68-z-0001-11-22x2-46001-12-2512 2 x80-1103-11-54 x90 x10 x9x8x7x6x5x3bxbcb-m00-m5-52cji 79 一般而言，一個經(jīng)濟(jì)、管理問題凡一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃是滿足以下條件時，才能建立線性規(guī)劃模型。模型。 . .要求解問題的目標(biāo)函數(shù)能用數(shù)要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；值指標(biāo)來反映，且為線性函數(shù)； . .存在著多種方

56、案；存在著多種方案； . .要求達(dá)到的目標(biāo)是在一定條件要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述。等式描述。六、線性規(guī)劃模型的應(yīng)用六、線性規(guī)劃模型的應(yīng)用80（一）、資源的合理利用（一）、資源的合理利用 一般提法：一般提法： 某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)b b1 1,b,b2 2, , b bn n種產(chǎn)品，種產(chǎn)品，要消耗要消耗a a1 1,a,a2 2, , a am m種資源，已知每件產(chǎn)品所消耗的資源種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤如表數(shù)、每種資源的數(shù)量限制以及

57、每件產(chǎn)品可獲得的利潤如表所示，問如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，所示，問如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤最大？使獲得的總利潤最大？單件 產(chǎn) 消耗 品資源資源限制單件利潤nbb 1maa 1mbb 1ncc 1mnmnaaaa 1111 0maxjijijjjxbxaxcz模型81（二）、生產(chǎn)組織與計(jì)劃問題（二）、生產(chǎn)組織與計(jì)劃問題 一般提法：某工廠用機(jī)床一般提法：某工廠用機(jī)床a a1 1,a,a2 2, , a am m 加工加工b b1 1,b,b2 2, , b bn n 種零件。在一個周期內(nèi)，各機(jī)床可能工作的機(jī)時（臺種零件。在一個周期內(nèi)，各機(jī)床可能工作的

58、機(jī)時（臺時），工廠必須完成各種零件的數(shù)量、各機(jī)床加工每個零時），工廠必須完成各種零件的數(shù)量、各機(jī)床加工每個零件的時間（機(jī)時件的時間（機(jī)時/個）和加工每個零件的成本（元個）和加工每個零件的成本（元/個）如個）如表所示，問如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任表所示，問如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？務(wù)，又使總成本最低？加工 零 時間 件機(jī)床機(jī)時限制必須零件數(shù)nbb 1maa 1maa 1nbb 1mnmnaaaa 1111加工 零 成本 件機(jī)床nbb 1maa 1mnmncccc 111182 0 min ( 11ijjijiijijminjijijijjiijxb

59、xaxaxczxbax一一組組變變量量）。模模型型：的的數(shù)數(shù)量量，求求在在一一生生產(chǎn)產(chǎn)周周期期加加工工零零件件為為機(jī)機(jī)床床設(shè)設(shè)83（三）、合理下料問題（三）、合理下料問題 一般提法一般提法 設(shè)用某種原材料截取零件設(shè)用某種原材料截取零件a a1 1,a,a2 2, , a am m的毛坯。根據(jù)以的毛坯。根據(jù)以往的經(jīng)驗(yàn)，在一種原材料上可以有往的經(jīng)驗(yàn)，在一種原材料上可以有b b1 1,b,b2 2, , b bn n種不同的種不同的下料方式，每種下料方式可截得的各種毛坯個數(shù)以及每種下料方式，每種下料方式可截得的各種毛坯個數(shù)以及每種零件的需要量如表所示，問應(yīng)如下料才能既滿足需要又使零件的需要量如表所示，問應(yīng)如下料才能既滿足需要又使原材料消耗最少？原材料消耗最少？下料 下料毛 件數(shù) 方式坯型號需 要毛坯數(shù)nbb 1maa 1mbb 1mnmnaaaa 111184 )2 , 1( 0 min )2 , 1(x111111121jnjxbxaxabxaxaxxxznjbjmnmnmnnnj數(shù)數(shù)學(xué)學(xué)模模型型為為：下下料料的的原原材材料料件件數(shù)數(shù)，其其種種方方式式表表示示用用設(shè)設(shè)：85 現(xiàn)有一批某種型號的圓鋼長現(xiàn)有一批某種型號的圓鋼長8 8米，需要截取米，需要截取2.52.5米米長的毛坯長的毛坯100100根，長根，長1.31.3米的毛