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

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

3、最優(yōu)解為止。通過第二章例1的求解來介紹單純形法:在加上松弛變量之后我們可得到標準型如下：目標函數(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管理運籌學1單純形法的基本思路和原理它的系數(shù)矩陣, 101111000100A = ( p1 , p2 , p3 , p4 , p5 ) = 2 01其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個數(shù)n，為了找到一個初始基本可行解，先介紹以下幾個線性規(guī)劃的基本概念?；?已知A是約束條件的mn系數(shù)矩陣，其秩為

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

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

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

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

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

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

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

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

12、，把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。在本例題中約束方程為x1 + x2 + s1 = 300, 2x1 + x2 + s2 = 400,x2 + s3 = 250.在第二步中已經(jīng)知道x2為入基變量，我們把各約束方程中x2的為正的系數(shù)除對應的常量，得b1= 300 = 300,b2= 400 = 400,b3= 250 = 250.a121a221a32116管理運籌學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ù)值為50x1+100x2=500+100250=25000。顯然比初始基本可行解x1=0,x2=0,s1=300,s3=250時的目標函數(shù)值為0要好得多。下面我們再進行檢驗其最優(yōu)性，如果不是最優(yōu)解還要繼續(xù)進行基變換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無最優(yōu)解為止。17管理運籌學1單純形法的基本思路和原理單純形法原理（用代數(shù)方法求解LP）例1-6max Z = 2x1 + 3x2+ 3x3

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

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

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

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

18、3x2 + 3x3= 2(3 - x2 - x3 - x4 ) + 3x2 + 3x3= 6 + x2 + x3 - x4第五步：上述過程何時停止？當用非基變量表示目標函數(shù)的表達式中，非基變量的系數(shù)（檢驗數(shù)）全部非正時，當前的基本可行解就是最優(yōu)解!為什麼？分析用非基變量表示目標函數(shù)的表達式， 如果讓負檢驗數(shù)所對應的變量進基，目標函數(shù)值將下降！管理運籌學在講解單純形法的表格形式之前，先從一般數(shù)學模型里推導出檢驗數(shù) s的表達式。j可行基為m階單位矩陣的線性規(guī)劃模型如下（假設其系數(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管理運籌學2單純形法的表格形式把第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把以上的表達式帶入目標函數(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管理運籌學2單純形法的表格形式上面假設x1,x2,xm是基變量，即第i行約束方程的基變量正好是xi，而經(jīng)過迭代后，基將發(fā)生變化，計算zj的式子也會發(fā)生變化。如果迭代后的第i行約束方

21、程中的基變量為xBi，與xBi相應的目標函數(shù)系數(shù)為cBi，系數(shù)列( j = 1, 2, n) 則z j = (cB1,pj向量為, cBm ) pj = (cB ) pj ,其中，(cB)是由第1列第m行各約束方程中的基變量相應的目標函數(shù)依次組成的有序行向量。單純形法的表格形式是把用單純形法求出基本可行解、檢驗其最優(yōu)性、迭代某步驟都用表格的方式來計算求出，其表格的形式有些像增廣矩陣， 而其計算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解第二章的例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管理運籌學2單純形法的表格形式按照線性規(guī)劃模型在表中填入相對應的值，如上表所示；在上表中有一個m*m的單位矩陣，對應的基變量為s1,s2,s3； 在zj行中填入第j列與cB列中對應的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位數(shù)填入0；在 s j = cj- z j 行中填入cj-zj所得的值，如s1 = 50 - 0 = 50；z表示把初始基本可行解代入目標函數(shù)求得的目標函數(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管理運籌學迭代次數(shù)基變量cBx1x2s1s2s3b比值Bi/ai2501000000s1 s2 s3000111002101001001300400250300/1400/1250/1zjs j = cj - z j0000050100000z=02單純形法的表格形式以下進行第一次迭代，其變量為x2,s1,s2,通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向量，

24、由于主元在p2的第3 分量上，所以這個單位向量是e= (0, 0,1)T 也就是主元素變成1。這樣我們又得到的第1次迭代的單純表3如下所示。在上表中第3個基變量s1已被x2代替，故基變量列中的第3個基變量應變 為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管理運籌學迭代次數(shù)基變量cBx1x2s1s2s3b比值bi/aij501000001s1 s2 x2001001010-12001-

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

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

27、解答列管理運籌學構造“不完全的人造基”?。?）寫出初始基本可行解根據(jù)“用非基變量表示基變量的表達式”， 非基變量取0，算出基變量，搭配在一起構成初始基本可行解。2、建立判別準則：（1）兩個基本表達式的一般形式就LP限制條件中全部是“”類型約束，新增的松弛變量作為初始基變量的情況來描述：管理運籌學此時LP的標準型為管理運籌學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初始可行基 ：初始基本可行解：管理運籌學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)過若干次迭代），對于基B，用非基變量表出基變量的表達式 為：用非基變量表示目標函數(shù)的表達式：管理運籌學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=管理運籌學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)性判別定理對應于基B的基本可若行解，是非基變量s的檢驗數(shù)，若對于(0)jxj一切非基變量的角指標j，均有為最優(yōu)解。0，則X(0)（3）無“有限最優(yōu)解”的判別定理= (0,0,L,0,b ,b ,L,b )為一基本可行解，有若 X (0)12ms k 0一非基變量xk,其檢驗數(shù),而對于i=1,2,，m，均有 0 ，則該線性規(guī)劃問題aik沒有“有限最優(yōu)解”。管

30、理運籌學s jX (0) = (0,0,L,0,b ,b ,L,b )12m證明思路構造性證明：依據(jù)用非基變量表示基變量的表達式構造一族可行解，其對應的目標函數(shù)值趨于無窮大。幾何意義：沿著邊界前進的一族可行解管理運籌學舉例：用非基變量表示基變量的表達式代表兩個約束條件：x2對應的系數(shù)列向量P2=（1，3）T，當前的換入變量是 X2，按最小比值原則確定換出變量：管理運籌學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,則用非基變量表示基變量的表達式就變成；x1= 3 + x2 - x3 - x4 0x= 6 + 0x- 6x+ x 05234可行性自然滿足,最小比值原則失效,意即x2的值可以任意增大原線性規(guī)劃無“有限最優(yōu)解”。管理運籌學x2 3 /1 x min3 /1,6 / 2= qx 6 / 322- x2- 3x3、進行基變換（1） 選擇進基變量原則：正檢驗數(shù)（或最大正檢驗數(shù)）所對應的變量進基，目的是使目標函數(shù)得到改善（較快增大）； 進基變量對應的系數(shù)列稱為主元列。 （2） 出基變量的確定按最小比值原則確定出基變量，為的是保持解的可行性； 出基變量

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

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

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

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

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

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

38、籌學（最大正檢驗數(shù)或從左至右第1個出現(xiàn)的正檢驗數(shù)所對應的非基變量進基）課堂練習：直接按極小化問題求解下面的LP：管理運籌學MinZ=x1+ 2x2- x1+ 2x2 2s.t x 3.1x 0, x 012管理運籌學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, 相應的目標函數(shù)最優(yōu)值為Zmin=2管理運籌學一、大M法以第二章的例2來講解如何用單純形表的方法求解目標函數(shù)值最小的線性規(guī)劃問題。min f = 2x1 + 3x2.x1 + x2 350,x1 125,2x1 + x2 600,x1 , x2 0.目標函數(shù)：約束條件：加入松弛變量和剩余變量變?yōu)闃藴市?，得到新的約束條件如下：x1 + x2 - s1 = 350,x1 - s2 = 125,2x1 + x2 + s3 = 600,x1 , x2 , s1 , s2 , s3 0.76管理運籌學3求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法至于目標函數(shù)，在標準型中并不一定要求求最大值或最小值，但是為了使單純形表解法有一個統(tǒng)