第5章 單純形法

1、123單純形法的基本思路和原理單純形法的表格形式求目標(biāo)函數(shù)值最小的線性規(guī)劃的問(wèn)題的單純形表解法幾種特殊情況41管理運(yùn)籌學(xué)第五章 單 純 形 法圖解法的局限性？1947年G.B.Dantzig提出的單純形法提供了方便、有效的通用算法求解線性規(guī)劃。管理運(yùn)籌學(xué)即從可行域的一個(gè)頂點(diǎn)（基本可行解）開(kāi)始，轉(zhuǎn)移到另一個(gè)頂點(diǎn)（另一個(gè)基本可行解）的迭代過(guò)程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)，問(wèn)題也就得到了最優(yōu)解。管理運(yùn)籌學(xué)一、單純形法的基本思想1、頂點(diǎn)的逐步轉(zhuǎn)移頂點(diǎn)轉(zhuǎn)移的依據(jù)？根據(jù)線性規(guī)劃問(wèn)題的可行域是凸多邊形或凸多面體，一個(gè)線性規(guī)劃問(wèn)題有最優(yōu)解， 就一定可以在可行域的頂點(diǎn)上

2、找到。于是，若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解，這個(gè)最優(yōu)解所對(duì)應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn)；若該線性規(guī)劃有多個(gè)最優(yōu)解， 那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解。管理運(yùn)籌學(xué)轉(zhuǎn)移條件？轉(zhuǎn)移結(jié)果？使目標(biāo)函數(shù)值得到改善得到LP最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值2需要解決的問(wèn)題：(1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎麼轉(zhuǎn)移？ (2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)判斷標(biāo)準(zhǔn)是什麼？管理運(yùn)籌學(xué)單純形法的基本思路：從可行域中某一個(gè)頂點(diǎn)開(kāi)始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是,則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問(wèn)題無(wú)

3、最優(yōu)解為止。通過(guò)第二章例1的求解來(lái)介紹單純形法:在加上松弛變量之后我們可得到標(biāo)準(zhǔn)型如下：目標(biāo)函數(shù)： max 50x1+100x2約束條件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj0 （j=1，2）,sj0（j=1，2,3）6管理運(yùn)籌學(xué)1單純形法的基本思路和原理它的系數(shù)矩陣, 101111000100A = ( p1 , p2 , p3 , p4 , p5 ) = 2 01其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個(gè)數(shù)n，為了找到一個(gè)初始基本可行解，先介紹以下幾個(gè)線性規(guī)劃的基本概念?；?已知A是約束條件的mn系數(shù)矩陣，其秩為

4、m。若B是A中mm階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問(wèn)題中的一個(gè)基?；蛄浚夯鵅中的一列即稱為一個(gè)基向量?；鵅有m個(gè)基向量。非基向量：在A中除了基B之外的一列則稱之為基B的非基向量?；兞浚号c基向量pi相應(yīng)的變量xi叫基變量，基變量有m個(gè)。7管理運(yùn)籌學(xué)1單純形法的基本思路和原理非基變量：與非基向量pj相應(yīng)的變量xj叫非基變量，非基變量有nm個(gè)。由線性代數(shù)的知識(shí)知道，如果我們?cè)诩s束方程組系數(shù)矩陣中找到一個(gè)基，令這個(gè)基的非基變量為零，再求解這個(gè)m元線性方程組就可得到唯一的解了，這個(gè)解我們稱之為線性規(guī)劃的基本解。在此例中我們不妨找到了0為A的一個(gè)基，令這個(gè)基的11000B3 = 111

5、非基變量x，s2為零。這時(shí)約束方程就變?yōu)榛兞康募s束方程：8管理運(yùn)籌學(xué)1單純形法的基本思路和原理x2+s1=300，x2=400， x2+s3=250.求解得到此線性規(guī)劃的一個(gè)基本解：x1=0，x2=400，s1=100，s2=0，s3=150由于在這個(gè)基本解中s1=100，s3=150，不滿足該線性規(guī)劃s10，s30的約束條件，顯然不是此線性規(guī)劃的可行解，一個(gè)基本解可以是可行解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解 是否滿足非負(fù)的條件。我們把滿足非負(fù)條件的一個(gè)基本解叫做基本可行解，并把這樣的基叫做可行基。9管理運(yùn)籌學(xué)1單純形法的基本思路和原理一般來(lái)說(shuō)判斷一個(gè)基是否是可行基，

6、只有在求出其基本解以后，當(dāng)其基本解所有變量的解都是大于等于零，才能斷定這個(gè)解是基本可行解，這個(gè)基是可行基。那么我們能否在求解之前，就找到一個(gè)可行基呢？也就是說(shuō)我們找到的一個(gè)基能保證在求解之后得到的解一定是基本可行解呢？由于在線性規(guī)劃的標(biāo)準(zhǔn)型中要求bj都大于等于零，如果我們能找到一個(gè)基是單位矩陣，或者說(shuō)一個(gè)基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無(wú)關(guān)緊要的事）例如， 01001 10 00那么顯然所求得的基本解一定是基本可行解，這個(gè)單位矩陣或由單位矩陣各列向量組成的基一定是可行基。實(shí)際上這個(gè)基本可行解中的各個(gè)變量或等于某個(gè)bj或等于零。10管理運(yùn)籌學(xué)1單純形法的基本思路和原理在本

7、例題中我們就找到了一個(gè)基是單位矩陣。100100B2= 0 01在第一次找可行基時(shí)，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。11管理運(yùn)籌學(xué)1單純形法的基本思路和原理二、 最優(yōu)性檢驗(yàn)所謂最優(yōu)性檢驗(yàn)就是判斷已求得的基本可行解是否是最優(yōu)解。1. 最優(yōu)性檢驗(yàn)的依據(jù)檢驗(yàn)數(shù)j一般來(lái)說(shuō)目標(biāo)函數(shù)中既包括基變量，又包括非基變量?，F(xiàn)在我們要求只用非基變量來(lái)表示目標(biāo)函數(shù)，這只要在約束等式中通過(guò)移項(xiàng)等處理就可以用非基變量來(lái)表示基變量，然后用非

8、基變量的表示式代替目標(biāo)函數(shù)中基變量，這樣目標(biāo)函數(shù)中只含有非基變量了，或者說(shuō)目標(biāo)函數(shù)中基變量的系數(shù)都為零了。此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)，把變量xi的檢驗(yàn)數(shù)記為i。顯然所有基變量的檢驗(yàn)數(shù)必為零。在本例題中目標(biāo)函數(shù)為50x1+100x2。由于初始可行解中x1，x2為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知1=50，2=100，3=0，4=0，5=0。12管理運(yùn)籌學(xué)1單純形法的基本思路和原理2.最優(yōu)解判別定理對(duì)于求最大目標(biāo)函數(shù)的問(wèn)題中，對(duì)于某個(gè)基本可行解， 如果所有檢驗(yàn)數(shù)s j 0，則這個(gè)基本可行解是最優(yōu)解。下面我們用通俗的說(shuō)法來(lái)解釋最優(yōu)解

9、判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如下形式z = z0 + s j xjjJ由于所有的xj的取值范圍為大于等于零，當(dāng)所有的s j都小于等于零時(shí)，可知 s j xj 是一個(gè)小于等于零的數(shù)，要使z的值最大，顯然s j xj 只有為零。我們把這些xj取為非基jJ變量(即令這些xj的值為零)，所求得的基本可行解就使目標(biāo)jJ函數(shù)值最大為z0。*對(duì)于求目標(biāo)函數(shù)最小值的情況，只需把s j 0改為s j 013管理運(yùn)籌學(xué)1單純形法的基本思路和原理三、 基變換通過(guò)檢驗(yàn)，我們知道這個(gè)初始基本可行解不是最優(yōu)解。下面介紹如何進(jìn)行基變換找到一個(gè)新的可行基，具體的做法是從可行基中換一個(gè)列向量，得到一個(gè)新的可行基，使得

10、求解得到的新的基本可行解，其目標(biāo)函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。1. 入基變量的確定從最優(yōu)解判別定理知道，當(dāng)某個(gè)j0時(shí)，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個(gè)以上的j0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的j最大者的非基變量為入基變量，在本例題中2=100是檢驗(yàn)數(shù)中最大的正數(shù)，故選x2為入基變量。14管理運(yùn)籌學(xué)1單純形法的基本思路和原理2. 出基變量的確定在確定了x2為入基變量之后，我們要在原來(lái)的3個(gè)基變量s1，s2，s3中確定一個(gè)出基變量，也就是確定哪一個(gè)基變量變成非基變量呢？如果

11、把s3作為出基變量，則新的基變量為x2，s1，s2，因?yàn)榉腔兞縳1=s3=0， 我們也可以從下式：x2 +s1=300， x2+s2=400， x2=250，求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因?yàn)榇私鉂M足非負(fù)條件，是基本可行解，故s3可以確定為出基變量。能否在求出基本解以前來(lái)確定出基變量呢？以下就來(lái)看在找出了初始基本可行解和確定了入基變量之后，怎么樣的基變量可以確定為出基變量呢？或者說(shuō)出基變量要具有什么條件呢？15管理運(yùn)籌學(xué)1單純形法的基本思路和原理我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的正的系數(shù)除其所在約束方程中的常數(shù)項(xiàng)的值

12、，把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。在本例題中約束方程為x1 + x2 + s1 = 300, 2x1 + x2 + s2 = 400,x2 + s3 = 250.在第二步中已經(jīng)知道x2為入基變量，我們把各約束方程中x2的為正的系數(shù)除對(duì)應(yīng)的常量，得b1= 300 = 300,b2= 400 = 400,b3= 250 = 250.a121a221a32116管理運(yùn)籌學(xué)1單純形法的基本思路和原理b3的值最小，所以可以知道在原基變量中系數(shù)向量為e= (0, 0,1)T其中3a32的基變量s3為出基變量，這樣可知x

13、2，s1，s2為基變量，x1，s3為非基變量。令非基變量為零，得x2+s1=300, x2+s2=400, x2=250.求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.這時(shí)目標(biāo)函數(shù)值為50x1+100x2=500+100250=25000。顯然比初始基本可行解x1=0,x2=0,s1=300,s3=250時(shí)的目標(biāo)函數(shù)值為0要好得多。下面我們?cè)龠M(jìn)行檢驗(yàn)其最優(yōu)性，如果不是最優(yōu)解還要繼續(xù)進(jìn)行基變換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無(wú)最優(yōu)解為止。17管理運(yùn)籌學(xué)1單純形法的基本思路和原理單純形法原理（用代數(shù)方法求解LP）例1-6max Z = 2x1 + 3x2+ 3x3

14、x1+ x2+ x3 3(勞動(dòng)力約束)（原材料約束）s.t.x1 + 4x2+ 7x3 9x , x, x 0123管理運(yùn)籌學(xué)第一步：引入非負(fù)的松弛變量x4,x5,LP化為標(biāo)準(zhǔn)型將該max Z = 2x1 + 3x2+ 3x3+ 0x4+ 0x5(勞動(dòng)力約束)（原材料約束）x1+ x2+ x3+ x4= 3s.t x+ 4x+ 7x+ x= 9.1235x , x, x, x, x 012345管理運(yùn)籌學(xué)第二步：尋求初始可行基，確定基變量1010141710B = (P4 ,P ) = 1A = 1501x4，x5；對(duì)應(yīng)的基變量是第三步：寫出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值管理運(yùn)籌學(xué)兩個(gè)關(guān)鍵的

15、基本表達(dá)式： 用非基變量表示基變量的表達(dá)式管理運(yùn)籌學(xué)x4= 3 - x1 - x2- x3x= 9 - x- 4x- 7x5123初始基本可行解X (0)= (0,0,0,3,9)T用非基變量表示目標(biāo)函數(shù)的11111表達(dá)式請(qǐng)解釋結(jié)果的經(jīng)濟(jì)含義 不生產(chǎn)任何產(chǎn)品，資源全部節(jié)余（x4=3，x5=9），三種產(chǎn)品的總利潤(rùn)為0！管理運(yùn)籌學(xué)Z = 2x1+ 3x2+ 3x3當(dāng)前的目標(biāo)函數(shù)值Z (0)= 0第四步：分析兩個(gè)基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？ 分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式非基變量前面的系數(shù)均為正數(shù)，所以任何一個(gè)非基變量進(jìn)基都能使Z值增加通常把非基變量前面的系數(shù)叫“檢驗(yàn)數(shù)”；管理運(yùn)籌學(xué)Z

16、 = 2x1+ 3x2+ 3x3 選哪一個(gè)非基變量進(jìn)基？選x1為進(jìn)基變量（換入變量）問(wèn)題：能否選其他的非基變量進(jìn)基？a 任意一個(gè)a 任意一個(gè)正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量a 最大正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量a 排在最前面的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量管理運(yùn)籌學(xué)由用非基變量表示基變量的表達(dá)式當(dāng)x1增加時(shí)，x4，x5會(huì)減小，但有限度必須大于等于0，以保持解的可行性！于是x 31x= 3 - x 0 39D1= 3=q41x min,11 911x= 9 - x 0x511管理運(yùn)籌學(xué)x4= 3 - x1x= 9 - x51- x2- x3- 4x2- 7x3當(dāng)x1的值從0增加到3時(shí)，x4首先變?yōu)?，此時(shí)x5=60因此選

17、x4為出基變量（換出變量）。這種用來(lái)確定出基變量的規(guī)則稱為“最小比值原則”（或原則）。管理運(yùn)籌學(xué)如果P10，會(huì)出現(xiàn)什麼問(wèn)題？最小比值原則會(huì)失效！m 基變換新的基變量x1,x5；新的非基變量x2,x3,x4；寫出用非基變量表示基變量的表達(dá)式：由可得新的基本可行解X（1）=（3，0，0，0，6）T管理運(yùn)籌學(xué)x1 = 3 - x2 - x3 - x4x= 6 - 3x- 6x+ x5234x4 = 3 - x1 - x2 - x3x= 9 - x- 4x- 7x 5123 寫出用非基變量表示目標(biāo)函數(shù)的表達(dá)式:檢驗(yàn)數(shù)仍有正的返回進(jìn)行討論。管理運(yùn)籌學(xué)可得相應(yīng)的目標(biāo)函數(shù)值為Z（1）=6Z = 2x1 +

18、3x2 + 3x3= 2(3 - x2 - x3 - x4 ) + 3x2 + 3x3= 6 + x2 + x3 - x4第五步：上述過(guò)程何時(shí)停止？當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中，非基變量的系數(shù)（檢驗(yàn)數(shù)）全部非正時(shí)，當(dāng)前的基本可行解就是最優(yōu)解!為什麼？分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式， 如果讓負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的變量進(jìn)基，目標(biāo)函數(shù)值將下降！管理運(yùn)籌學(xué)在講解單純形法的表格形式之前，先從一般數(shù)學(xué)模型里推導(dǎo)出檢驗(yàn)數(shù) s的表達(dá)式。j可行基為m階單位矩陣的線性規(guī)劃模型如下（假設(shè)其系數(shù)矩陣的前m列是單位矩陣）：max z = c1x1 + c2 x2 + cn xn .+ a1,n xn+ a2,n x

19、n+ a1,m+1xm+1+ a2,m+1 xm+1+= b1,= b2 ,x1x2+ am,m+1xm+1+ am,n xn= bm ,xmxj 0.( j = 1, 2, m) 表示基變量，用 xj, n)( j = m +1, m + 2,xi (i = 1, 2, n)以下用表示非基變量。30管理運(yùn)籌學(xué)2單純形法的表格形式把第i個(gè)約束方程移項(xiàng)，就可以用非基變量來(lái)表示基變量xi，xi = bi- ai,m+1xm+1 - ai,m+2 xm+2- ai,n xn, m)n(i = 1, 2,= bi -aij xj .j =m+1把以上的表達(dá)式帶入目標(biāo)函數(shù)，就有mn+ cn xn = c

20、i xij =m+1z = c1 x1 + c2 x2+c j x ji=1nn(- z j )x j = z0 + sj =m+1= z0 +cj x jjj =m+1mz0 = cibi ,i=1s j= cj- z j ; a1 j其中：) a2 jm= i=1= (c , c ,= c a+ c a+ cazc a, cjiij1 1 j22 jmmj12m amj= (c1, c2 , cm ) p j31管理運(yùn)籌學(xué)2單純形法的表格形式上面假設(shè)x1,x2,xm是基變量，即第i行約束方程的基變量正好是xi，而經(jīng)過(guò)迭代后，基將發(fā)生變化，計(jì)算zj的式子也會(huì)發(fā)生變化。如果迭代后的第i行約束方

21、程中的基變量為xBi，與xBi相應(yīng)的目標(biāo)函數(shù)系數(shù)為cBi，系數(shù)列( j = 1, 2, n) 則z j = (cB1,pj向量為, cBm ) pj = (cB ) pj ,其中，(cB)是由第1列第m行各約束方程中的基變量相應(yīng)的目標(biāo)函數(shù)依次組成的有序行向量。單純形法的表格形式是把用單純形法求出基本可行解、檢驗(yàn)其最優(yōu)性、迭代某步驟都用表格的方式來(lái)計(jì)算求出，其表格的形式有些像增廣矩陣， 而其計(jì)算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來(lái)求解第二章的例1。max 50x1+100x2+0s 1+0s 2+0s 3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3

22、=250，x1, x2, s1, s2, s30. 把上面的數(shù)據(jù)填入如下的單純形表格32管理運(yùn)籌學(xué)2單純形法的表格形式按照線性規(guī)劃模型在表中填入相對(duì)應(yīng)的值，如上表所示；在上表中有一個(gè)m*m的單位矩陣，對(duì)應(yīng)的基變量為s1,s2,s3； 在zj行中填入第j列與cB列中對(duì)應(yīng)的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位數(shù)填入0；在 s j = cj- z j 行中填入cj-zj所得的值，如s1 = 50 - 0 = 50；z表示把初始基本可行解代入目標(biāo)函數(shù)求得的目標(biāo)函數(shù)值，即b列*cB列； 初始基本可行解為s1=300,s2=400,s3=250,x1=0,x2=0

23、;由于250/1最小，因此確定s3為出基變量；由于s2 s1 0，因此確定x2為入基變量。出基變量所在行，入基變量所在列的交匯處為主元，這里是a32=1，在表中畫圈以示區(qū)別。33管理運(yùn)籌學(xué)迭代次數(shù)基變量cBx1x2s1s2s3b比值Bi/ai2501000000s1 s2 s3000111002101001001300400250300/1400/1250/1zjs j = cj - z j0000050100000z=02單純形法的表格形式以下進(jìn)行第一次迭代，其變量為x2,s1,s2,通過(guò)矩陣行的初等變換，求出一個(gè)新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向量，

24、由于主元在p2的第3 分量上，所以這個(gè)單位向量是e= (0, 0,1)T 也就是主元素變成1。這樣我們又得到的第1次迭代的單純表3如下所示。在上表中第3個(gè)基變量s1已被x2代替，故基變量列中的第3個(gè)基變量應(yīng)變 為x2。由于第0次迭代表中的主元a32已經(jīng)為1，因此第3行不變。為了使 第1行的a12為0，只需把第3行*(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.34管理運(yùn)籌學(xué)迭代次數(shù)基變量cBx1x2s1s2s3b比值bi/aij501000001s1 s2 x2001001010-12001-

25、1010015015025050/1150/2zjs j = cj - z j01000010050000-100250002單純形法的表格形式從上表可以看出，第一次迭代的 s1= 50 0，因此不是最優(yōu)解。設(shè)x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。從上表中可知第二次迭代得到的基本可行解為x1=50,x2=250,s1=0,s2=50, s3=0,這時(shí)z=27500。由于檢驗(yàn)數(shù)都觀察法觀察系數(shù)矩陣中是否含有現(xiàn)成的單位陣？ LP限制條件中全部是“”類型的約束將新增的松弛變量作為初始基變量，對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣；管理運(yùn)籌

26、學(xué)線性規(guī)劃限制條件都是“”或“=”類型的約束先將約束條件標(biāo)準(zhǔn)化，再引入非負(fù)的人工變量， 以人工變量作為初始基變量，其對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣， 稱為“人造基”；然后用大M法或兩階段法求解；管理運(yùn)籌學(xué)使約束方程的系數(shù)矩陣中出現(xiàn)一個(gè)單位陣，用單位陣的每一個(gè)列向量對(duì)應(yīng)的決策變量作為“基變量”，這樣， 出現(xiàn)在單純形表格中的B(i)列（即約 束方程的右邊常數(shù)）值正好就是基變量的取值。（注意：用非基變量表示基變量的表達(dá)式）管理運(yùn)籌學(xué)等式約束左端引入人工變量的目的討論如果限制條件中既有“”類型的約束，又有“”或“=”類型的約束，怎麼辦？為什麼初始可行基一定要選單位陣？b列正好就是基變量的取值，因此稱b列為

27、解答列管理運(yùn)籌學(xué)構(gòu)造“不完全的人造基”?。?）寫出初始基本可行解根據(jù)“用非基變量表示基變量的表達(dá)式”， 非基變量取0，算出基變量，搭配在一起構(gòu)成初始基本可行解。2、建立判別準(zhǔn)則：（1）兩個(gè)基本表達(dá)式的一般形式就LP限制條件中全部是“”類型約束，新增的松弛變量作為初始基變量的情況來(lái)描述：管理運(yùn)籌學(xué)此時(shí)LP的標(biāo)準(zhǔn)型為管理運(yùn)籌學(xué)nn+mMaxZ= c j x j+0x jj =1j =n+1a11 x1 + a12 x2+L + a1n xn+ xn+1= b1ax+ ax+ L + ax+ x= b2112222nnn+22s.t.MMMax+ ax+L + ax+ x= bm11m 22mnnn

28、+mmx1 , x2 ,L, xn+m 0初始可行基 ：初始基本可行解：管理運(yùn)籌學(xué)X (0)= (0,0,L,0,b ,b ,L,b)T12m 10L0B (0)= (P, P,L, P) = 01L0n+1n+2n+m MMMM 00L1一般（經(jīng)過(guò)若干次迭代），對(duì)于基B，用非基變量表出基變量的表達(dá)式 為：用非基變量表示目標(biāo)函數(shù)的表達(dá)式：管理運(yùn)籌學(xué)nx= b- ax,i = 1,2L, mn+iiijjj =1n+mnmnc j x jn+in+ijjjjj=1j=1i=1j=1imn- ci=1 j=1+a xn+iijjnmc + b ,jj0n iijj=1i=1ii=管理運(yùn)籌學(xué)mn+i

29、=1nZ0 + s j x j j=1令s j =c j - z jnZ0 + (c j - z j )x j j=1mn+iij=1mn+iij=1mn+iii=1m= cbn+iii=1nc j x j j=1niijjj=1是（2）最優(yōu)性判別定理對(duì)應(yīng)于基B的基本可若行解，是非基變量s的檢驗(yàn)數(shù)，若對(duì)于(0)jxj一切非基變量的角指標(biāo)j，均有為最優(yōu)解。0，則X(0)（3）無(wú)“有限最優(yōu)解”的判別定理= (0,0,L,0,b ,b ,L,b )為一基本可行解，有若 X (0)12ms k 0一非基變量xk,其檢驗(yàn)數(shù),而對(duì)于i=1,2,，m，均有 0 ，則該線性規(guī)劃問(wèn)題aik沒(méi)有“有限最優(yōu)解”。管

30、理運(yùn)籌學(xué)s jX (0) = (0,0,L,0,b ,b ,L,b )12m證明思路構(gòu)造性證明：依據(jù)用非基變量表示基變量的表達(dá)式構(gòu)造一族可行解，其對(duì)應(yīng)的目標(biāo)函數(shù)值趨于無(wú)窮大。幾何意義：沿著邊界前進(jìn)的一族可行解管理運(yùn)籌學(xué)舉例：用非基變量表示基變量的表達(dá)式代表兩個(gè)約束條件：x2對(duì)應(yīng)的系數(shù)列向量P2=（1，3）T，當(dāng)前的換入變量是 X2，按最小比值原則確定換出變量：管理運(yùn)籌學(xué)x1 + x2 + x3 + x4= 33x2 + 6x3 - x4 + x5= 6x1= 3 - x2- x3- x4x= 6 - 3x- 6x+ x5234= 3= 6- x3 - x4 0x1要求：x- 6x+ x 052

31、34于是：如果x2的系數(shù)列變成P2=（-1，0）T,則用非基變量表示基變量的表達(dá)式就變成；x1= 3 + x2 - x3 - x4 0x= 6 + 0x- 6x+ x 05234可行性自然滿足,最小比值原則失效,意即x2的值可以任意增大原線性規(guī)劃無(wú)“有限最優(yōu)解”。管理運(yùn)籌學(xué)x2 3 /1 x min3 /1,6 / 2= qx 6 / 322- x2- 3x3、進(jìn)行基變換（1） 選擇進(jìn)基變量原則：正檢驗(yàn)數(shù)（或最大正檢驗(yàn)數(shù)）所對(duì)應(yīng)的變量進(jìn)基，目的是使目標(biāo)函數(shù)得到改善（較快增大）； 進(jìn)基變量對(duì)應(yīng)的系數(shù)列稱為主元列。 （2） 出基變量的確定按最小比值原則確定出基變量，為的是保持解的可行性； 出基變量

32、所在的行稱為主元行。 主元行和主元列的交叉元素稱為主元素。管理運(yùn)籌學(xué)4、主元變換（旋轉(zhuǎn)運(yùn)算或樞運(yùn)算）按照主元素進(jìn)行矩陣的初等行變換把主元素變成1，主元列的其他元素變成0（即主元列變?yōu)閱挝幌蛄浚懗鲂碌幕究尚薪?，返回最?yōu)性檢驗(yàn)。管理運(yùn)籌學(xué)求解思想頂點(diǎn)的逐步轉(zhuǎn)移， 條件是使目標(biāo)函數(shù)值不斷得到改善。管理運(yùn)籌學(xué)單純形法小結(jié)第一步：將LP化為標(biāo)準(zhǔn)型，并加以整理。引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數(shù) 陣中有一個(gè)單位陣。確定初始可行基，寫出初始基本可行解管理運(yùn)籌學(xué)表格單純形法求解步驟第二步：最優(yōu)性檢驗(yàn)計(jì)算檢驗(yàn)數(shù)，檢查：j所有檢驗(yàn)數(shù)是否 0？是結(jié)束，寫出最優(yōu)解和目

33、標(biāo)函數(shù)最優(yōu)值；k還有正檢驗(yàn)數(shù)檢查相應(yīng)系數(shù)列 0？ 是結(jié)束，該LP無(wú)“有限最優(yōu)解”！l不屬于上述兩種情況，轉(zhuǎn)入下一步基變換。 確定是停止迭代還是轉(zhuǎn)入基變換？管理運(yùn)籌學(xué)第三步：基變換選擇（最大）正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列，主元列對(duì)應(yīng)的非基變量為換入變量；最小比值對(duì)應(yīng)的行為主元行，主元行對(duì)應(yīng)的基變量為換出變量。確定進(jìn)基變量和出基變量。管理運(yùn)籌學(xué)第四步 換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算)利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進(jìn)基變量對(duì)應(yīng)的檢驗(yàn)數(shù)變成0，從而得到一張新的單純形表，返回第二步。完成一次迭代，得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值管理運(yùn)籌學(xué)停止迭代的標(biāo)志（停機(jī)準(zhǔn)則）該迭代過(guò)程直至

34、下列情況之一發(fā)生時(shí)停止 檢驗(yàn)數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列 0（最優(yōu)解）依據(jù)：最優(yōu)性檢驗(yàn)的兩個(gè)定理管理運(yùn)籌學(xué)最優(yōu)性判別定理；無(wú)“有限最優(yōu)解”判斷定理五、各種類型線性規(guī)劃的處理 1、分類及處理原則：（1）類型一：目標(biāo)要求是“Max”，約束條件是“”類型左邊加上非負(fù)松弛變量變成等式約束（ 約束條件標(biāo)準(zhǔn)化），將引入的松弛變量作為初始基變量，則初始可行基是一個(gè)單位陣，用原始單純形法求解。管理運(yùn)籌學(xué)（2）類型二：目標(biāo)要求是“Max”，約束條件是“=”類型左邊引入非負(fù)的人工變量，并將引入的人工變量作為初始基變量，則初始可行基是一個(gè)單位陣， 然后用大M法或兩階段法求解。（3）類型三：目標(biāo)要求是“

35、Max”，約束條件是“”類型約束條件標(biāo)準(zhǔn)化，左邊減去非負(fù)的剩余變量，變成等式約束，化為類型二。管理運(yùn)籌學(xué)（4）類型四：目標(biāo)要求是“Min”方法1化為極大化問(wèn)題方法2按照極小化問(wèn)題直接在單純形表格上計(jì)算處理，但管理運(yùn)籌學(xué)相應(yīng)的原則要作改動(dòng)。 2、處理人工變量的方法：（1）大M法在約束條件中人為地加入非負(fù) 的人工變量，以便使它們對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣。問(wèn)題：加入的人工變量是否合理？如何處理？在目標(biāo)函數(shù)中，給人工變量前面添上一個(gè)絕對(duì)值很大的負(fù)系數(shù)-M（M0），迭代過(guò)程中， 只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化懲罰！管理運(yùn)籌學(xué)結(jié)果最優(yōu)表中，基變量不包含人工變量，則最優(yōu)解就是原線性

36、規(guī)劃的最優(yōu)解，不影響目標(biāo)函數(shù)的取值；最優(yōu)表中，基變量中仍含有人工變量，表明原線性規(guī)劃的約束條件被破壞，線性規(guī)劃沒(méi)有可行解，也就沒(méi)有最優(yōu)解！管理運(yùn)籌學(xué)（2） 兩階段法第一階段：建立輔助線性規(guī)劃并求解，以判斷原線性規(guī)劃是否存在基本可行解。輔助線性規(guī)劃的結(jié)構(gòu)：目標(biāo)函數(shù)W為所有人工變量之和，目標(biāo)要求是使目標(biāo)函 數(shù)極小化，約束條件與原線性規(guī)劃相同。管理運(yùn)籌學(xué)3、用表格單純形法直接計(jì)算極小化線性規(guī)劃時(shí)要修改哪些原則？（初始表？最優(yōu)解判別？換入變量？換出變量？旋轉(zhuǎn)運(yùn)算？引入人工變量？） 最優(yōu)性判別：所有檢驗(yàn)數(shù)非負(fù)換入變量的選擇原則：（最小）負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的變量進(jìn)基，以保證目標(biāo)函數(shù)值（較快）減??；用大M法求解

37、時(shí)，在目標(biāo)函數(shù)中人工變量的前面添上一個(gè)很大的正系數(shù)M；管理運(yùn)籌學(xué)六、迭代過(guò)程中可能出現(xiàn)的問(wèn)題及處理方法1、為確定出基變量要計(jì)算比值，該比值= 解答列元素/主元列元素。對(duì)于主元列的0 元素或負(fù)元素是否也要計(jì)算比值？（此時(shí)解的可行性自然滿足，不必計(jì)算；如果主元列元素全部為0元素或負(fù)元素， 則最小比值失效，線性規(guī)劃無(wú)“有限最優(yōu)解”）管理運(yùn)籌學(xué)2、現(xiàn)若干個(gè)相同的最小比值怎麼辦？的基本可行解，即非0分量（說(shuō)明出現(xiàn)了的個(gè)數(shù)小于約束方程的個(gè)數(shù)。按照“攝動(dòng)原理”所得的規(guī)則，從相同比值對(duì)應(yīng)的基變量中選下標(biāo)最小的基變量作為換出變量可以避免出現(xiàn)“死循環(huán)”現(xiàn)象）3、選擇進(jìn)基變量時(shí)，同時(shí)有若干個(gè)正檢驗(yàn)數(shù)，怎麼選？管理運(yùn)

38、籌學(xué)（最大正檢驗(yàn)數(shù)或從左至右第1個(gè)出現(xiàn)的正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量進(jìn)基）課堂練習(xí)：直接按極小化問(wèn)題求解下面的LP：管理運(yùn)籌學(xué)MinZ=x1+ 2x2- x1+ 2x2 2s.t x 3.1x 0, x 012管理運(yùn)籌學(xué)CBXBcj xjb1200MqjX1X2X3X4X5MX52-120-1012/20X431010_-Z-2M1+M2-2MM0020X2X413-1/21-1/201/210010-Z-22010M-1由最優(yōu)表得：最優(yōu)解為X*=（0，1，0，3，0）T, 相應(yīng)的目標(biāo)函數(shù)最優(yōu)值為Zmin=2管理運(yùn)籌學(xué)一、大M法以第二章的例2來(lái)講解如何用單純形表的方法求解目標(biāo)函數(shù)值最小的線性規(guī)劃問(wèn)題。min f = 2x1 + 3x2.x1 + x2 350,x1 125,2x1 + x2 600,x1 , x2 0.目標(biāo)函數(shù)：約束條件：加入松弛變量和剩余變量變?yōu)闃?biāo)準(zhǔn)型，得到新的約束條件如下：x1 + x2 - s1 = 350,x1 - s2 = 125,2x1 + x2 + s3 = 600,x1 , x2 , s1 , s2 , s3 0.76管理運(yùn)籌學(xué)3求目標(biāo)函數(shù)值最小的線性規(guī)劃的問(wèn)題的單純形表解法至于目標(biāo)函數(shù)，在標(biāo)準(zhǔn)型中并不一定要求求最大值或最小值，但是為了使單純形表解法有一個(gè)統(tǒng)