教案四--線性規(guī)劃的單純形法

1、教案四線性規(guī)劃的單純形法教學(xué)內(nèi)容第三節(jié)單純形法1 .單純形法2 .單純形法的基本原理3 .單純形解法4 .大M法教學(xué)學(xué)時9學(xué)時教學(xué)目標(biāo)1.理解單純形法的解題思想2,掌握單純形法的基本原理5 .掌握單純形解法和大M法重點難點重點單純形法的基本原理、單純形解法和大M法，難點單純形法的基本原理教學(xué)方法及手段教師講解使用多媒體課件教學(xué)過程一、復(fù)習(xí)鞏固1.線性規(guī)劃圖解法的步驟（見課件）2,線性規(guī)劃數(shù)學(xué)模型解的幾種情況（見課件）二、講授新課1.單純形法基本概念（見課件）典型方程組一般線性規(guī)劃問題標(biāo)準(zhǔn)形式的約束條件如下式（2-1）,是一個有n個未知數(shù)、m個方程的線性方程組.如果這m個方程是獨立的（即其中任一

2、方程均不能由其它方程代替），則通過初等變換，必能使式（2-1）化成式（2-2）形式的同解方程組：nXajXj=0i=1,2,，m（2-1）j1x1+aim1xm1aim2xm2'''''alnxn=biX2+a2mixm1'a2m2xm2',”a2nxn=b2xm+amm1Xm1'amm2Xm2'''''amnxn=bm式中Xl；x2；Xn'是重新排序后的變量.式（2-2）被稱為典型方程組.即如果在一個線性方程組中的每一個方程中都有系數(shù)為1,并且不再出現(xiàn)在其它方程的一個未知量，則此方

3、程組稱為典型方程組.基本變量如果變量Xj在某一方程中系數(shù)為1,而在其它一切方程中的系數(shù)為零，則稱Xj為該方程中的基本變量.否則為非基本變量.如式（2-2）中的x；,x2；xm為基本變量，*1；書？1；也,'''？；為非基本變量.基本變量的個數(shù)為線性無關(guān)的方程的個數(shù).事實上，n個變量中任意m個都可能作為基本變量，因此由排列組合知識可知，基本變量的組數(shù)為個，n為未知變量的個數(shù)，m為線性無關(guān)的方程的個數(shù).基本解在典型方程中，設(shè)非基本變量為零，求解基本變量得到的解，稱為基本解.基本解的個數(shù)為cm個.基本可行解基本變量為非負(fù)的一組基本解稱為基本可行解，基本可行解的個數(shù)最多不超過邸

4、個.例如，對方程組x1+x2x3+2x4=32x1+x2-3x4=1施行初等變換X（-2）+，可以得到：卜1+X2-X3+2x4=3、-X2+2x3-7x4=-5x1):x1+x2-x3+2x4=3x2-2x3+7x4=5X(-1)+:'+x35x4=2、x2-2x3+7x4=5式和為典型方程組，基本變量是xi和x2,非基本變量為x3和x4.設(shè)非基本變量x3和x4為零，則xi和x2分別等于-2和5,即對應(yīng)于典型方程組和，基本解為：X=(-2500.因基本變量中xi為負(fù)值，所以此解不是基本可行解.根據(jù)方程組和有4個未知變量，因此通過初等變換可得到cj組(即6組)典型方程組和基本解.若令x

5、2和x4為基本變量，通過初等變換，方程組和可變換為：X(一1)+:xi+x2x3+2x4=3x1十x3-5x4=-2X(1/5):rx+x2-x3+2x4=310.2%一0.2x3+x4=0.4X(2)+:，.4x1+x20.6x3=2.2L-0.2x1-0.2x3+x4=0.4此時，典型方程組的基本變量為x2和x4,非基本變量為x1和x3.基本解為：X=(02.200.4)、因為基本變量為非負(fù)值，所以此基本解也為基本可行解.2.單純形法的基本原理(見課件)理論上已經(jīng)證明，線性規(guī)劃的基本可行解與可行域的頂點是一對一的.這就決定了線性規(guī)劃可行域的頂點個數(shù)最多也不超過端個.上面討論線性規(guī)劃問題解的

6、特點時已指出，如果線性規(guī)劃有最優(yōu)解，一定可以在可行域的某個頂點處達(dá)到.因此，單純形法的基本思路是：根據(jù)問題的標(biāo)準(zhǔn)形式，從可行域中的一個基本可行解(一個頂點)開始，轉(zhuǎn)換到另一個基本可行解(頂點)，并且使目標(biāo)函數(shù)的值逐步增大；當(dāng)目標(biāo)函數(shù)達(dá)到最大值時，問題就得到了最優(yōu)解.在用單純形法求解線性規(guī)劃問題時，應(yīng)考慮的問題：建立初始基本可行解在用單純形法求解時，首先應(yīng)將線性規(guī)劃問題以標(biāo)準(zhǔn)形式表達(dá)、約束條件以右端常數(shù)非負(fù)的典型方程組表示，確定初始基本可行解.在前面的闡述中，已討論了如何將般線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式的線性規(guī)劃問題，如何將約束條件通過初等變換以典型方程組形式表示，以及如何得出基本可行解（最初得到

7、的基本可行解也稱初始基本可行解），此處不再贅述.經(jīng)Xi過變換，典型方程組和初始基本可行解可用式（2-3）表示:+a1m1Xm1,a1m2Xm.2'a1nXn=b1X2+a2m1Xm1'a2m2Xm2'2nXn=b2(2-3)Xm+amm1Xm1amm2Xm2,'amnXn=bm初始基本可行解：x0=肛bmoo）T.最優(yōu)性檢驗得到一個基本可行解后,我們要判斷它是不是最優(yōu)解.一般情況下，經(jīng)過迭代后式（2-3）變?yōu)閚-bi-xaijXjjm1(i=1,2,，m)(2-4)將式（2-4）代入目標(biāo)函數(shù)式，整理后得-Cibi-二(Cji1j=m1mGa/Xji1(2-5)m

8、令ZoCib;，i1mZj=、ciaiji1j=m1,m2,n于是nZ=Zo(Cj-Zj)Xjjm1(2-6)由于當(dāng)j=1,2，m時,mZj=二Ciaij-Cji1,即Cj-Zj=0（j=1,2，m）,所以式（2-6）也可寫作再令Cj=Cj-Zjj=1,2,nCj為變量Xj的檢驗數(shù).nZ=Zo八CjXjj1(2-7)11）最優(yōu)解判別若X（o）=（b1b；-bmoo）T為基本可行解，且對一切j=1,2，n，有Cj<0,則X（0）為最優(yōu)解.（2）無有限最優(yōu)解判別若X（0）=（bM，工00）T為一基本可行解，有一個Ck>0,且對一切i=1,2,，m有母<0（乳為約束條件方程中的系數(shù)

9、，k=1,2,，n）,那么該線性規(guī)劃問題無有限最優(yōu)解（或稱有無界解或無最優(yōu)解）.事實上，應(yīng)用向量的乘法，可以將檢驗數(shù)的求法表示得簡明一些.令Cj表示目標(biāo)函數(shù)中變量Xj的系數(shù)，Cb表示基本變量在目標(biāo)函數(shù)中的系數(shù)行向量，Pj表示變量Xj在典型方程中的系數(shù)列向量，則%ij”-Z-a2j_、Cj=Cj-Zj=Cj-CB,Pj=Cj-CB,j=1,2，n（2-8）<9mj/基本變量的檢驗數(shù)總等于0.目標(biāo)函數(shù)值Z=Cbb.基本可行解的改進(jìn)若初始基本可行解X（0）不是最優(yōu)解及不能判別無最優(yōu)解時，需找一個新的基本可行解.具體方法是：首先確定進(jìn)基變量，再確定出基變量.進(jìn)基變量的確定：由式（2-7）可知，檢

10、驗數(shù)Cj對線性規(guī)劃問題的實際意義是：Cj表示當(dāng)變量Xj增加1個單位時，目標(biāo)函數(shù)的增加量；其經(jīng)濟(jì)意義表示相對利潤.當(dāng)Cj>0時，說明非基本變量Xj增加1個單位，目標(biāo)函數(shù)可以增加，即現(xiàn)在的函數(shù)值不是最優(yōu)，還能增加.這時要將某個非基本變量換到基本變量中去（稱為進(jìn)基變量）.為了使目標(biāo)函數(shù)值增長最快，所以應(yīng)選擇Cj值最大的一項所對應(yīng)的非基本變量進(jìn)基，max（CjA0）=Ck.則對應(yīng)的xk為進(jìn)基變量.進(jìn)基變量所在的列（k）稱為樞列.出基變量的確定：當(dāng)進(jìn)基變量確定后（假設(shè)Xi是進(jìn)基變量），出基變量的選定是應(yīng)用“最小比值規(guī)則”.即用此時的各約束方程右端的常數(shù)項bi（非負(fù)數(shù)）與相應(yīng)方程中Xk的正系數(shù)4k相

11、比，并選取最小商值的基本變量為為出基變量（將由基本變量變?yōu)榉腔咀兞浚?出基變量所在的行（l）稱為樞行.樞行與樞列交點處的元素（外）稱為樞元.然后通過初等變換，將約束條件轉(zhuǎn)為關(guān)于新的基本變量的典型方程組，并求得新的基本可行解.對于新的基本可行解可再進(jìn)行上述的最優(yōu)性檢驗.3.單純形解法（見課件）上面介紹的單純形法原理看似復(fù)雜，但如用表格形式計算，則比較容易操作.單純形法的計算步驟：第1步：找出初始基本可行解，建立初始單純形表.第2步：檢驗對應(yīng)于非基本變量的檢驗數(shù)C",若對所有的Cj<0,則已得到最優(yōu)解，計算最m優(yōu)值Z=£Cibi,即可結(jié)束.否則，轉(zhuǎn)入下一步.i1第3步：

12、在所有CjA0中，若有一個Ck對應(yīng)Xk的系數(shù)列向量，即對i=1,2,，m均有PikW0,則此問題無有限最優(yōu)解（或稱有無界解或無最優(yōu)解），停止計算.否則轉(zhuǎn)入下一步.第4步：根據(jù)max（C7>0）=Ck,確定Xk為進(jìn)基變量，再依據(jù)最小比值規(guī)則產(chǎn).I（min©=min，印內(nèi)>0"含）確定Xi為出基變量.工Pik/Plk第5步：實施以樞元素為中心的初等變換，使約束方程組變?yōu)殛P(guān)于新的基本變量的典型方程組，得到新的單純形表，重復(fù)第二步，一直到?jīng)]有新的非基本變量可以改善目標(biāo)函數(shù)為止.若線性規(guī)劃模型為：上述計算步驟仍有效，只是其中的第二步改為：若對所有的Cj>0（j=1,

13、2,，n）,則已得到最優(yōu)解；第三步改為在所有Cj<0中，若有一個C7對應(yīng)Xk的系數(shù)列向量，即對i=1,2,，m均有熊<0,則此問題無有限最優(yōu)解（或稱有無界解或無最優(yōu)解）；第四步改為min（Cj<0）=C；,確定Xk為進(jìn)基變量.例2-8現(xiàn)以例2-1來說明單純形法的表上解法.解首先將線性規(guī)劃問題標(biāo)準(zhǔn)化，引入松弛變量X3、X4、X5、X6,則：此時約束方程組已為典型方程組，根據(jù)上述線性規(guī)劃模型可以列出初始單純形表（表2-4）:表2-4單純形法求解例2-1（1）2003000000、022100012601201008404000101600400011232003000000Z=0

14、表2-4中:221012014000J40000001001為典型方程組中變量的系數(shù)，Xj為規(guī)劃中出現(xiàn)的變量,Cj為變量Xj在目標(biāo)函數(shù)中的系數(shù),Xb為基本變量，Cb為基本變量在目標(biāo)函數(shù)中的系數(shù)，b為典bi-.型方程組右端常數(shù)項（非負(fù)值）,日為確定出基變量的商值，a=?（乳>0）,Cj為變量Xj的'ik檢驗數(shù)，Cj=Cj-CbPj,Z為此時目標(biāo)函數(shù)值，Z=Cbb.根據(jù)初始單純形表可以看出：初始基本可行解是x1=0,X2=0,X3=12,X4=8,X5=16,X6=12,12,此時目標(biāo)函數(shù)值Z=（0000）'8=016J2>2、_.1檢驗數(shù)C1=c1-CbR=200（0

15、0001=2004-2、2222222C2=c2CbP2=300（0000）,=3000<4JC3=C4=C5=C6=0（基本變量的檢驗數(shù)總等于零）由于C1>0,C2>0,所以初始基本可行解非最優(yōu)解.又由于C2>C1,所以確定X2為進(jìn)基變進(jìn)一步求最小8值:即從第4個方程中算出的商值最小，而第4個方程中的基本變量是于是X6為出基變量.表中給第4個約束方程中X2的系數(shù)4加上方括號以突出其為樞元.接下去是將X2取代X6,表2-4中的約束方程化為以X3、X4、X5和X2為基本變量，Xi和X6為非基本變量的典型方程.從表2-4中可以看到，只需對方程組實行初等變換，使樞元位置變成1

16、,而樞列中的其它元素變?yōu)榱憔涂梢粤?此處可先將第4個方程除以4,使樞元位置變成1;然后用新得到的第4個方程乘以（-2）后分別加到第1個和第2個方程上，使樞列中的第1個和第二個方程所在位變?yōu)榱?這樣我們可以得到新的單純形表（表2-5）.表2-5給出的新的基本可行解是X1=0,x2=3,x3=6,4=2,x5=16,x6=0此時目標(biāo)函數(shù)值Z=000300，6216<3二900檢驗數(shù)Ci=ci-CbR=200-(0003002、14<0j二200C6=c6-CBF6=0-(000300)1、2120114二一75C2=C3=C4=C5=0（基本變量的檢驗數(shù)總等于零）02010063010

17、0102204000101643000100032000000-75Z=900由于Ci>0,所以此時基本可行解非最優(yōu)解，確定X1為進(jìn)基變量.進(jìn)一步計算最小日值：即從第2個方程中算出的商值最小，而第2個方程中的基本變量是X4,于是X4為出基變量.接著進(jìn)行第二次迭代，將Xi取代X4,表2-5中的約束方程化為以X3、Xi、X5和X2為基本變量,X4和X6為非基本變量的典型方程，以便求出新的單純形表.重復(fù)單純形法計算第2步第5步,一直到?jīng)]有新的非基本變量可以改善目標(biāo)函數(shù)為止(見表2-6和表2-7).表2-6單純形法求解例2-1(3)20030000000001-20242001001020000

18、-4128430001000312000-200025Z=1300表2-7單純形法求解例2-1(4)2003000000X0001-1002001000040000-21430001002000-1500Z=1400向、一，4表2-7中：目標(biāo)函數(shù)值Z=(02000300=1400a檢驗數(shù)C4=04-CbP4=0-020000300)，o=-15021工C5=c5-CbB=0-0200410300)425C1=C2=C3=C6=0（基本變量的檢驗數(shù)總等于零）由于Cj<0,j=1,2,，6，所以此基本可行解X=4,X2=2,X3=0,X4=0,X5=0,X6=4,即為最優(yōu)解，最優(yōu)值為Z*=1

19、400.與前面圖解法求解結(jié)果一致.為了加深對單純形法基本思想的理解，不妨將表2-4、表2-5、表2-6、表2-7和圖2-1進(jìn)行對照，可以發(fā)現(xiàn)表2-4給出的基本可行解對應(yīng)于圖中可行域頂點0,表2-5給出的基本可行解對應(yīng)于頂點A,表2-6給出的基本可行解對應(yīng)于頂點B,表2-7給出的最優(yōu)解對應(yīng)于頂點C.線性規(guī)劃問題有無窮多個可行解，應(yīng)用單純形法可以高效率地求解此類問題.例2-9用單純形法求解下列規(guī)劃問題（解略,見課件）4.大M法（1）人工變量（見課件）單純形法求解的一個重要前提是：線性規(guī)劃問題必須是標(biāo)準(zhǔn)形式，并且約束條件必須化為典型方程組.這樣才能得到初始基本可行解，并制作出初始的單純形表.但許多線

20、性規(guī)劃問題不是以標(biāo)準(zhǔn)形式出現(xiàn)，約束條件也未以典型方程組形式表示，因此我們往往先要把線性規(guī)劃問題化為標(biāo)準(zhǔn)形式，然后再使約束方程變?yōu)榈湫头匠探M.n如果給定的線性規(guī)劃問題中，約束條件都是“£ajXjWbJ'型的，那么將每一個約束條件的左jj邊添加一個松弛變量后，不僅約束條件化為了標(biāo)準(zhǔn)形式，而且也得到了典型方程組，如下列所示.n但是，大多數(shù)的線性規(guī)劃中的約束條件為ZajXj至（或=）b的形式，化為典型方程組就不j那么容易.在這種情況下，比較簡單的方法是先將約束不等式化為等式，然后對每一個約束方程再添加一個非負(fù)變量（如果約束方程沒有明顯的基本變量），使方程組成為典型方程組形式.這種外加

21、的變量不同于松弛變量（或剩余變量），沒有實際意義，只是一種形式的存在，本質(zhì)上應(yīng)當(dāng)?shù)扔诹?，所以被稱為人工變量.（2）大M法求解（見課件）在一個線性規(guī)劃問題的約束條件中加入人工變量，成為典型方程組后，即可用單純形表求解.由于一開始人工變量是作為基本變量的，而它們本質(zhì)上應(yīng)當(dāng)為零，所以必須設(shè)法盡快將它們從基本變量中剔除，成為非基本變量（基本可行解中，非基本變量的值為零）.為此，將人工變量記入目標(biāo)函數(shù)中，并賦予一個極大的負(fù)系數(shù).習(xí)慣上，這種系數(shù)記作-M,其中M是極大的正數(shù).由于標(biāo)準(zhǔn)形式的線性規(guī)劃是極大化問題，目標(biāo)函數(shù)中添加1個或1個以上以-M為系數(shù)的人工變量后，人工變量取任何非負(fù)值均不可能為最優(yōu)解.從而

22、，在應(yīng)用單純形法過程中，人工變量一定會盡快地變成非基本變量，而對原問題的最優(yōu)解不產(chǎn)生絲毫影響.對于目標(biāo)函數(shù)為極小化時，規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為極大的正系數(shù)（+M）.這種方法稱為大M法.例2-10用大M法求解下列問題.解先通過加入松弛變量X3和X4使此線性規(guī)劃問題化為標(biāo)準(zhǔn)形式然后通過加入人工變量X5使約束方程組變?yōu)榈湫头匠探MMaxZ=3x15x2-Mx5用單純形法解之，結(jié)果如下表2-11:表2-11大M法求解例2-103500-MX0101004400201012-M320011863+3M5+2M000Z=-18M3101004002010126-M02-3016305+2M-3-3M