運籌學(xué)講義單純形方法課件

運籌學(xué)耿修林12/25/20221運籌學(xué)耿修林12/20/20221五、單純形方法（一）單純形方法的初步討論1、單純形方法的基本思想從可行域中的一個基本可行解出發(fā)，判斷它是否已是最優(yōu)解，若不是，尋找下一個基本可行解，并使目標函數(shù)得到改進，如此迭代下去，直到找出最優(yōu)解或判定問題無界為止。從另一個角度說，就是從可行域的某一個極點出發(fā)，迭代到另一個極點，并使目標函數(shù)的值有所改善，直到找出有無最優(yōu)解時為止。12/25/20222五、單純形方法（一）單純形方法的初五、單純形方法（一）單純形方法的初步討論2、單純形方法：消去法[例]求解線性規(guī)劃模型解：第一步，將線性規(guī)劃模型標準化：MaxZ=50x1+30x2+0x3+0x4s·t·4x1+3x2+x3=1202x1+x2++x4=50x1,x2,x3,,x4≥012/25/20223五、單純形方法（一）單純形方法的初步討論1

2、單純形方法：消去法第二步，尋找初始可行解。變量x3、,x4對應(yīng)的列向量A3、A4可作為初始可行基，那么X3、X4為基變量，X1、X2為非基變量，用非基量表示基變量，則有：MaxZ=50x1+30x2+0x3+0x4s·t·x3=120-4x1-3x2x4=50-2x1-x2x1,x2,x3,,x4≥0令x1、x2=0，得到基本可行解X=（0，0，120，50）。文本文本文本文本文本文本文本文本12/25/202242、單純形方法：消去法文本文本文本文本文本文本文五、單純形方法2、單純形方法：消去法第三步，判斷目標函數(shù)是否達到了最優(yōu)。第四步，選取入基變量。確定x1為基變量，x2仍為非基變量。第五步，選取出基變量。x3=120-4x1-3x2≥0x4=50-2x1-x2≥0解不等式得：x1≤25，只有當x1=25時，x4恰好等于0，所以x4確定為出基變量。于是新的典則方程為：x1

=25-

0.5x2-

0.5x4x3=20-x2+2

x412/25/20225五、單純形方法2、單純形方法：消去法12（一）單純形方法的初步討論第六步，產(chǎn)生新的基本可行解及目標函數(shù)值。令x2、x4等于0，得到x1=25，x3=20，于是新的基本可行解為X=（25，0，20，0），目標函數(shù)值為Z=1250。第七步，判定目標函數(shù)值是否得到了最優(yōu)。根據(jù)分析目前的方案還不是最優(yōu)的。重復(fù)第四、五、六步，x2入基，x3出基，建立新的典則方程：x1=15+0.5x3-1.5x4x2=20-2x3+2x4令非基變量x3、x4等于0，得到新的基本可行解X=（15，20，0，0），目標函數(shù)值為1350。問題求解完成。12/25/20226（一）單純形方法的初步討論第六步，產(chǎn)生新的基本可行解及目標函五、單純形方法（二）單純形方法的矩陣描述1、線性規(guī)劃的典則形式：MaxZ=CBB-1b+(CN-CBB-1N)XNS·t·XB=B-1b-B-1NXN

XB,XN≥02、判別向量與判別數(shù)：（a）λ=CN-

CBB-1A為對應(yīng)基B的所有X的判別向量，其中任一分量λj=cj-CBB-1Aj為變量xj關(guān)于基B的判別數(shù)，j=1,2,-------,n。12/25/20227五、單純形方法（二）單純形方法的矩陣五、單純形方法2、判別向量與判別數(shù)：（b）λN=CN-CBB-1N為對應(yīng)基B的所有非基變量XN的判別向量，其中任一分量λj=cj-CBB-1Aj為非基變量xj關(guān)于基B的判別數(shù)，j=m+1,m+2,----------,n。（c）所有基變量的判別向量是零向量，所有基變量的判別數(shù)是0（為什么？）。3、最優(yōu)解的判定：（a）如果所有的檢驗數(shù)都小于0，則當前解為最優(yōu)解。12/25/20228五、單純形方法2、判別向量與判別數(shù)：12/2五、單純形方法3、最優(yōu)解的判定：（b）如果至少存在一個檢驗數(shù)大于0，且該檢驗數(shù)對應(yīng)的列向量中至少有一個正分量，則需要繼續(xù)進行迭代尋找最優(yōu)解。（c）如果至少存在一個檢驗數(shù)大于0，且該檢驗數(shù)對應(yīng)的列向量的所有分量都小于0，則線性規(guī)劃問題不存在有界最優(yōu)解。12/25/20229五、單純形方法3、最優(yōu)解的判定：12/20/五、單純形方法（三）單純形方法：表上作業(yè)法1、單純形表的構(gòu)造方法1：C-CBB-1A=(CB,CN)-CBB-1(B,N)=(0,CN-CBB-1N)兩邊同乘上X得：（C-CBB-1A）X=(0,CN-CBB-1N)X，化簡得：Z=CBB-1b+(CN-CBB-1N)XN

構(gòu)造聯(lián)立方程：Z+(CBB-1A-C)X

=CBB-1bB-1AX=B-1b12/25/202210五、單純形方法（三）單純形方法：表上作業(yè)法12/20/2五、單純形方法1、單純形表的構(gòu)造這樣得到單純形表：

12/25/202211五、單純形方法1、單純形表的構(gòu)造12/20/2022五、單純形方法1、單純形表的構(gòu)造方法2：XB=B-1b-B-1NXN，則有：XB+B-1NXN=B-1b又Z=CBB-1b+(CN-CBB-1N)XN，于是：Z+（CBB-1N-CN）XN=CBB-1b，這樣得：

Z+（CBB-1N-CN）XN=CBB-1bXB+B-1NXN=B-1b構(gòu)造單純形表：12/25/202212五、單純形方法1、單純形表的構(gòu)造12/20/20221五、單純形方法（三）單純形方法：表上作業(yè)法1、表上作業(yè)的步驟：第一步，將線性規(guī)劃問題進行標準化處理。第二步，確定初始基本可行解與初始可行基。第三步，編制單純形計算表。第四步，計算檢驗數(shù)，判斷線性規(guī)劃問題是否有最優(yōu)解。第五步，確定入基變量。一是最大檢驗數(shù)準則，二是最小下標準則。第六步，確定出基變量。最小檢驗數(shù)對應(yīng)的基變量出基。第七步，編制新的單純形表。重復(fù)以上的第四—七步，

直到能夠確定線性規(guī)劃問題是否有最優(yōu)解為止。

12/25/202213五、單純形方法（三）單純形方法：表上作業(yè)法12/20五、單純形方法2、單純形方法：表上作業(yè)法應(yīng)用舉例求解下列線性規(guī)劃問題：MinZ=X1-3X2S.t.2X1+4X2≤6-X1+3X2≤5X1,X2≥0解：第一步，將上述問題進行標準化處理：12/25/202214五、單純形方法2、單純形方法：表上作業(yè)法12/20/2五、單純形方法應(yīng)用舉例MaxZ=-X1+3X2S.t.2X1+4X2+X3=6-X1+3X2+X4=5X1,X2,X3,X4≥0第二步，確定初始基本可行解與初始基本可行基。初始可行基：B=（A3,A4）初始可行解：X=（0，0，6，5）12/25/202215五、單純形方法應(yīng)用舉例12/20/202215五、單純形方法應(yīng)用舉例第三步，構(gòu)造單純形表：-1300CBXBB-1bX1X2X3X4檢驗數(shù)0X3624103/20X45-13015/3檢驗數(shù)0-130012/25/202216五、單純形方法應(yīng)用舉例-1300CBXBB-1bX1五、單純形方法應(yīng)用舉例第四步，計算檢驗數(shù)并判斷是否是最優(yōu)解。檢驗數(shù)列在初始單純形表中的最后一行。第五步，確定入基變量。對應(yīng)的檢驗數(shù)最大，所以確定X2為入基變量。第六步，確定出基變量。計算的檢驗數(shù)列在初始單純形表中的最后一列。根據(jù)出基變量的判別準則，應(yīng)確定X3出基。12/25/202217五、單純形方法應(yīng)用舉例12/20/202217五、單純形方法-1300CBXBB-1bX1X2X3X4檢驗數(shù)3X21.50.510.2500X40.5-2.50-0.751檢驗數(shù)4.5-2.5-0.750第七步，構(gòu)造新的單純形表：12/25/202218五、單純形方法-1300CBXBB-1bX1X2X五、單純形方法應(yīng)用舉例第八步，判定迭代到這一步是否應(yīng)該停止。因為所有的非基變量的檢驗數(shù)都為負數(shù)，因此可以判斷迭代到此步的基是最優(yōu)基，目標函數(shù)值為Z=4.5，最優(yōu)解為X=（0，1.5，0，0）。原問題的最優(yōu)解為X=（0，1.5，0，0），目標函數(shù)值為Z=-4.5。12/25/202219五、單純形方法應(yīng)用舉例12/20/202219五、單純形方法（四）確定初始基本可行解的方法1、對于約束方程中都是小于等于0，并且約束方程右邊項皆大于0的情況，只要引進松弛變量即可得到單位陣的初始可行基。2、如果約束方程都是等于某些值的情況，此時需要引進人工變量才能構(gòu)造出單位陣的初始可行基和初始可行解。3、如果約束方程中有大于某些值的情況，則需要引進剩余變量并同時引進人工變量，才能構(gòu)造出單位陣的初始可行基和初始可行解。12/25/202220五、單純形方法（四）確定初始基本可行解的方法12/20/六、線性規(guī)劃的其他解法（一）人工變量消除法——M法1、M法的含義：通過引進人工變量，構(gòu)造一個輔助的線性規(guī)劃問題，然后由輔助的線性規(guī)劃問題找出原問題的第一個初始可行基，在此基礎(chǔ)上，利用單純形方法求出原問題的最優(yōu)解。12/25/202221六、線性規(guī)劃的其他解法（一）人工變量消除法——M法12/2六、線性規(guī)劃的其他解法（一）人工變量消除法——M法2、M法的輔助線性規(guī)劃問題：原問題：Maxz=c1x1+c2x2+……+cnxn

s.t.a11x1+a12x2+……+a1nxn=b1a21x1+a22x2+……+a2nxn=b2

……am1x1+am2x2+……+amnxn=bm

x1,x2,……,xn≥

012/25/202222六、線性規(guī)劃的其他解法（一）人工變量消除法——M法12/六、線性規(guī)劃的其他解法（一）人工變量消除法——M法2、M法的輔助線性規(guī)劃問題：Maxz=c1x1+c2x2+…+cnxn-MXn+1-MXn+2-……-MXn+ms.t.a11x1+a12x2+……+a1nxn+Xn+1=b1

a21x1+a22x2+……+a2nxn+

Xn+2=b2

……am1x1+am2x2+……+amnxn+Xn+m=bm

x1,x2,……,xn≥

012/25/202223六、線性規(guī)劃的其他解法（一）人工變量消除法——M法12/20六、線性規(guī)劃的其他解法3、M法的解題步驟（1）把原線性規(guī)劃問題進行標準化處理。（2）引進人工變量，構(gòu)造輔助線性規(guī)劃問題。（3）運用單純形方法，把人工變量全部剔除出基變量。（4）在得到的原問題的初始可行基的基礎(chǔ)上，運用單純形方法進行迭代。（5）直到能夠判斷原問題有無最優(yōu)解時為止。12/25/202224六、線性規(guī)劃的其他解法3、M法的解題步驟12/20/2022六、線性規(guī)劃的其他解法4、M法解的判定（1）經(jīng)過若干次迭代后，基變量中無人工變量，則說明原問題有基本可行解。（2）經(jīng)過若干次迭代后，基變量中仍有人工變量，并且全部檢驗數(shù)皆小于0，則表明原問題無可行解。12/25/202225六、線性規(guī)劃的其他解法4、M法解的判定12/20/20222六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法1、含義：在原來問題引入人工變量后分兩個階段求解線性規(guī)劃問題的方法。其中，第一階段在原來問題中引入人工變量，設(shè)法構(gòu)造一個單位陣的初始可行基，另外在目標函數(shù)中令非人工變量的系數(shù)全部為0，人工變量的系數(shù)為1，構(gòu)造一個新的輔助目標函數(shù)。在此基礎(chǔ)上，建立輔助線性規(guī)劃問題。然后運用單純形方法求解，直到輔助目標函數(shù)為0時為止。第二階段重新回到原來的問題，以第一階段得到的可行基為初始可行基，運用單純形方法以求出原來問題的解。12/25/202226六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法12/六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法2、兩階段法的輔助問題：原問題：Maxz=c1x1+c2x2+……+cnxn

s.t.a11x1+a12x2+……+a1nxn=b1

a21x1+a22x2+……+a2nxn=b2

……am1x1+am2x2+……+amnxn=bmx1,x2,……,xn≥

012/25/202227六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法12六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法2、兩階段法的輔助問題：輔助問題：MinZ/=Xn+1+Xn+2+…+Xn+ms.t.a11x1+a12x2+……+a1nxn+Xn+1=b1

a21x1+a22x2+……+a2nxn+Xn+2=b2

……am1x1+am2x2+……+amnxn+Xn+m=bmx1,x2,，…,xn≥

0

Xn+1，Xn+2，

…，Xn+m≥

012/25/202228六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法12/六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法3、解的判斷：（1）輔助問題的目標函數(shù)值Z/≥

0。（2）假定B為輔助問題最優(yōu)基，此時若輔助問題的目標函數(shù)值Z/>0，則原問題無解。[證明]（請同學(xué)們自己做一做）。（3）輔助問題在最優(yōu)基B下目標函數(shù)的值Z/=0，此時有兩種情況：第一種情況，若輔助問題的最優(yōu)基B對應(yīng)的基變量中無人工變量，則該最優(yōu)基也是原問題的可行基，這時候只要在單純形表中去掉人工變量所在的列和最后一行，即可得到原問題的初始可行單純形表。12/25/202229六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法12/六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法3、解的判斷：（3）第二種情況，若輔助問題最優(yōu)基B對應(yīng)的基變量中還有人工變量，即存在：yr+Σa/rkyk+Σa/rjxj=0這時需要進行討論：第一，若a/rj=0，即有：yr+Σa/rkyk=0則表明原問題中的第r個約束是多余的，可以從輔助問題單純形表中，直接劃掉這一行。第二，若a/rj中至少有一個不等于0，則需要以之為轉(zhuǎn)軸元素再進行迭代，直到化為第一種情況為止。12/25/202230六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法12（三）退化、循環(huán)及其處理方法1、退化問題在約束系數(shù)矩陣A=(aij)mn,（

m<n）中，若R（A）<m，則稱該線性規(guī)劃問題是退化的。2、退化迭代的特點（1）退化解的基變量中至少有一個取值為0。（2）退化迭代中基在不斷變化但解始終不變。（3）退化迭代不會引起目標函數(shù)值的改進。3、防止循環(huán)迭代的方法（1）攝動法（2）字典順序法（3）最小下標法12/25/202231（三）退化、循環(huán)及其處理方法1、退化問題12/20/202（三）退化、循環(huán)及其處理方法4、退化問題的單純形攝動方法（1）原理對退化的線性規(guī)劃問題的右邊項作微小的擾動，以避免因退化而引起的循環(huán)。（2）應(yīng)用舉例12/25/202232（三）退化、循環(huán)及其處理方法4、退化問題的單純形攝動方法七、電子表格建模及其求解見Excel中的演示12/25/202233七、電子表格建模及其求解見Excel中的演示12/20案例討論12/25/202234案例討論12/20/202234第四講線性規(guī)劃建模第一節(jié)線性規(guī)劃建模的幾個問題第二節(jié)常見的線性規(guī)劃模型第三節(jié)案例討論12/25/202235第四講線性規(guī)劃建模12/20/202235第一節(jié)線性規(guī)劃建模的有關(guān)問題一、線性規(guī)劃建模的要求與思路1、要求：繁簡適當，要能夠反映實際問題的主要因素，得出結(jié)論和產(chǎn)生效益。2、思路：首先將實際問題簡化得能比較容易地建立一個粗略的、可以使用的模型；在這個基礎(chǔ)上考慮加進先前被省略掉的一些因素，改進已建立的模型；重復(fù)這個過程直到能建立符合要求的模型為止。

12/25/202236第一節(jié)線性規(guī)劃建模的有關(guān)問題12/20/202236第一節(jié)線性規(guī)劃建模的有關(guān)問題二、線性規(guī)劃建模的一般過程1、明確決策變量2、確定目標函數(shù)3、確立約束方程4、給出變量取值的限制12/25/202237第一節(jié)線性規(guī)劃建模的有關(guān)問題二、線性規(guī)劃建模的一般過程1第一節(jié)線性規(guī)劃建模的有關(guān)問題三、參數(shù)資料的來源1、統(tǒng)計資料2、會計核算資料3、工程分析4、實驗研究5、合理規(guī)定等12/25/202238第一節(jié)線性規(guī)劃建模的有關(guān)問題三、參數(shù)資料的來源12/2第二節(jié)常見的線性規(guī)劃模型一、配料問題假設(shè)有n種原料，已知每種原料都含有m種成分，又已知每種原料的單位成分含量為aij（i=1,2,…,m,j=1,2,…,n）?，F(xiàn)欲用這n種原料配制成一種產(chǎn)品，要求單位產(chǎn)品的各種成分的含量為bi，如果每種原料的單價為cj。問如何配料才能使產(chǎn)品的生產(chǎn)成本最低。12/25/202239第二節(jié)常見的線性規(guī)劃模型一、配料問題12/20/2022第二節(jié)常見的線性規(guī)劃模型二、資源利用問題生產(chǎn)n種產(chǎn)品，每種產(chǎn)品都要經(jīng)過m道工序，其中，第j種產(chǎn)品在第i道工序上加工所需要的工時為aij（i=1,2,…,m,j=1,2,…,n）,第i道工序可提供的工時最多為bi，第j種產(chǎn)品的單位利潤為cj。問如何規(guī)劃各種產(chǎn)品的數(shù)量，使獲得的利潤最大。12/25/202240第二節(jié)常見的線性規(guī)劃模型二、資源利用問題12/20/202第二節(jié)常見的線性規(guī)劃模型三、運輸問題:某種物資有m個產(chǎn)地、n個需地，產(chǎn)地產(chǎn)量、需地的需求量及由產(chǎn)地到需地的單位運價如下：

運價（C）需求地（B）產(chǎn)量（a）12…n產(chǎn)地11112…1n122122…2n2………………mm1m2…mnM需求量（b）12…n12/25/202241第二節(jié)常見的線性規(guī)劃模型三、運輸問題:運價第二節(jié)常見的線性規(guī)劃模型三、運輸問題：問如何設(shè)計運輸方案，才能使運輸成本達到最小。（1）產(chǎn)銷平衡（2）產(chǎn)大于銷（3）產(chǎn)小于銷（4）運力限制等12/25/202242第二節(jié)常見的線性規(guī)劃模型三、運輸問題：12/20/202第二節(jié)常見的線性規(guī)劃模型四、投資問題：設(shè)有n個投資項目可供選擇，Cj表示第j個投資項目的收益率，a表示第i種資源用于第j個項目的投資數(shù)量，b表示第i種資源的數(shù)量，問如何進行投資才能使投資總收益率最大。12/25/202243第二節(jié)常見的線性規(guī)劃模型四、投資問題：12/20/202第二節(jié)常見的線性規(guī)劃模型五、混合問題：某石油公司用A、B、C三種原料混合成普通汽油（R）、高級汽油（P）和低鉛汽油（L）3種成品出售。3種原料的單位成本及每月最大購入量：原料單位成本最大購入量Aa100Bb150Cc5012/25/202244第二節(jié)常見的線性規(guī)劃模型五、混合問題：12/20/202第二節(jié)常見的線性規(guī)劃模型五、混合問題：每千克成品油的售價為：普通汽油為d元，高級汽油為e元，低鉛汽油為f元。低鉛汽油每月最多銷售50噸。各種汽油的規(guī)格如下：普通汽油R：A少于20%、C不多于30%；高級汽油P：A不少于40%、B不少于己于10%且不多于20%、C不多于10%；低鉛汽油：B不少于30%。試建立線性規(guī)劃模型。

12/25/202245第二節(jié)常見的線性規(guī)劃模型五、混合問題：12/20/202第二節(jié)常見的線性規(guī)劃模型六、下料問題：用某種材料切割m種毛坯，根據(jù)經(jīng)驗，單位材料上有n種不同的下料方案，每種下料方案可得各種毛坯數(shù)量及每種毛坯的需求量為：C下料方案需求量B1B2……..Bn毛坯名稱A1A2…Am1112……..1nb12122……..2nb2………….…….……..…….m1m2……..mnbm12/25/202246第二節(jié)常見的線性規(guī)劃模型六、下料問題：下料方案需求第二節(jié)常見的線性規(guī)劃問題六、下料問題：問應(yīng)該怎樣安排下料方案，才能是材料的消耗最省。12/25/202247第二節(jié)常見的線性規(guī)劃問題六、下料問題：12/20/202第二節(jié)常見的線性規(guī)劃問題七、分派問題：設(shè)有n件工作B1，B2，…..，Bn，分派給n個人A1，A2，……，An去做，每人只做一件工作且每件工作只安排一人做，Ai完成Bj的工時為Cij。問應(yīng)如何分派才能使總工時最省。12/25/202248第二節(jié)常見的線性規(guī)劃問題七、分派問題：12/20/202第二節(jié)常見的線性規(guī)劃模型八、生產(chǎn)進度問題：某企業(yè)生產(chǎn)一種季節(jié)性很強的產(chǎn)品，產(chǎn)品只能在k個月內(nèi)銷售，同時生產(chǎn)也要在這些月內(nèi)進行。除正常生產(chǎn)時間生產(chǎn)外，也可以加班生產(chǎn)，產(chǎn)品在正常生產(chǎn)時間每月最多能生產(chǎn)A個單位，單位成本為a元，加班生產(chǎn)每月最多能生產(chǎn)B個單位，單位成本為b元。當月生產(chǎn)未及時銷售出去的需貯存，庫存容量為C，貯存費為單位產(chǎn)品c元，k個月的需求量分別為O1、O2,…..,Ok。試建立線性規(guī)劃模型，使得總的生產(chǎn)費用最低。12/25/202249第二節(jié)常見的線性規(guī)劃模型八、生產(chǎn)進度問題：12/20/2第四講線性規(guī)劃對偶理論及其應(yīng)用第一節(jié)線性規(guī)劃的對偶問題一、問題的提出二、原問題與對偶問題的關(guān)系：（1）原問題求極大（?。ε紗栴}求極?。ù螅?）原問題目標函數(shù)的系數(shù)變成對偶問題的約束方程的右邊項，同樣，對偶問題目標函數(shù)的系數(shù)是原問題的約束方程的右邊項（3）原問題的變量的個數(shù)、主約束的個數(shù)分別等于對偶問題的主約束個數(shù)和變量的個數(shù)（4）原問題的約束系數(shù)矩陣與對偶問題的約束系數(shù)矩陣存在轉(zhuǎn)置關(guān)系12/25/202250第四講線性規(guī)劃對偶理論及其應(yīng)用第一節(jié)線性規(guī)劃的對偶問第一節(jié)線性規(guī)劃的對偶問題二、原問題與對偶問題的關(guān)系（5）在原極小問題中的“大于等于”、“小于等于”、“等于”約束，分別與對偶問題中變量的“大于等于0”、“小于等于0”、“無約束”相對應(yīng)。反之，在原極小問題中的變量“大于等于0”、“小于等于0”、“無約束”分別對應(yīng)著對偶問題約束中的“小于等于”、“大于等于”、“等于”。12/25/202251第一節(jié)線性規(guī)劃的對偶問題二、原問題與對偶問題的關(guān)系12/第一節(jié)線性規(guī)劃的對偶問題三、原問題與對偶問題的轉(zhuǎn)換舉例說明。12/25/202252第一節(jié)線性規(guī)劃的對偶問題三、原問題與對偶問題的轉(zhuǎn)換12/2第二節(jié)線性規(guī)劃的對偶理論一、原問題與對偶問題是相互對稱的。二、弱對偶定理：原問題的目標函數(shù)值以對偶問題的目標函數(shù)值為上界，對偶問題的目標函數(shù)值以原問題的目標函數(shù)值為下界。三、無界性定理：若原問題（對偶問題）為無界解，則對偶問題（原問題）無可行解。12/25/202253第二節(jié)線性規(guī)劃的對偶理論一、原問題與對偶問題是相互對稱的。第二節(jié)線性規(guī)劃的對偶理論四、最優(yōu)解性質(zhì)定理：X*、Y*分別是原問題與對偶問題的可行解，若有CX*=Y*b存在，則X*、Y*分別是原問題與對偶問題的最優(yōu)解。五、對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標函數(shù)的值相等。六、互補松弛性定理：X*、Y*分別是原問題和對偶問題的可行解，若Y*Xs=YsX*，當且僅當X*、Y*為最優(yōu)解。12/25/202254第二節(jié)線性規(guī)劃的對偶理論四、最優(yōu)解性質(zhì)定理：12/20/2第三節(jié)互補松弛性定理的應(yīng)用一、關(guān)于互補松弛性定理的幾個重要的推論二、互補松弛定理的應(yīng)用[應(yīng)用舉例]Max2X1+4X2+X3+X4S·t·X1+3X2+X4≤82X1+X2≤6X2+X3+X4≤6X1+X2+X3≤9

X1、X2、X3、X4≥012/25/202255第三節(jié)互補松弛性定理的應(yīng)用一、關(guān)于互補松弛性定理的幾個重第三節(jié)互補松弛性定理的應(yīng)用二、互補松弛定理的應(yīng)用其最優(yōu)解為X=（2，2，4，0），目標函數(shù)值為16。試運用互補松弛定理求對偶問題的最優(yōu)解。12/25/202256第三節(jié)互補松弛性定理的應(yīng)用二、互補松弛定理的應(yīng)用12/2第三節(jié)互補松弛定理的應(yīng)用三、對偶解的解釋1、對偶解與影子價格2、檢驗數(shù)與邊際貢獻12/25/202257第三節(jié)互補松弛定理的應(yīng)用三、對偶解的解釋12/20/202第四節(jié)對偶單純形方法一、對偶單純形方法的基本思想從對偶問題的可行解和原問題的不可行解出發(fā)，進行換基迭代，一旦當原問題的解也變成可行解時，這時的解就是原問題的最優(yōu)解。二、對偶單純形方法與原單純形方法的區(qū)別1、原單純形方法從可行解和對偶問題不可行解出發(fā)，直到所有的檢驗數(shù)皆小于等于0，而對偶單純形方法則從對偶可行解和原問題不可行解出發(fā)，直到原問題的解也變成可行。12/25/202258第四節(jié)對偶單純形方法一、對偶單純形方法的基本思想12第四節(jié)對偶單純形方法二、對偶單純形方法與原單純形方法的區(qū)別2、最優(yōu)解的判定標準不一樣。3、確定出入基變量的順序不同。原單純形方法，先確定入基變量后再確定出基變量，而對偶單純形方法先確定出基變量后確定入基變量。4、確定出入基變量的方法不同。12/25/202259第四節(jié)對偶單純形方法二、對偶單純形方法與原單純形方法的區(qū)第四節(jié)對偶單純形方法三、對偶單純形方法的解的判定1、B-1b≥0，表明已求出了原問題的最優(yōu)解。2、B-1b中至少有一個負分量，且該負分量所在行的各元素都是非負數(shù)，則問題無最優(yōu)解。3、B-1b中至少有一個負分量，且該負分量所在行的元素中存在負數(shù)，則需要繼續(xù)迭代。12/25/202260第四節(jié)對偶單純形方法三、對偶單純形方法的解的判定12/2第四節(jié)對偶單純形方法四、對偶單純形算法的過程1、對問題進行標準化處理2、確定一個初始的對偶可行解3、編制對偶單純形表4、判定目標函數(shù)是否達到最優(yōu)5、換基迭代，直到能判定問題有無最優(yōu)解時為止。五、應(yīng)用舉例12/25/202261第四節(jié)對偶單純形方法四、對偶單純形算法的過程12/20/第五節(jié)敏感性分析一、敏感性分析的含義由于受到政策、價格、工藝水平、資源貯備、設(shè)備更新等若干因素的影響，線性規(guī)劃模型中的參數(shù)C、A、b經(jīng)常會發(fā)生變化，那么C、A、b在什么樣的范圍內(nèi)變化，才不會導(dǎo)致已求出的最優(yōu)基的改變，這就是敏感性分析所要解決的問題。12/25/202262第五節(jié)敏感性分析一、敏感性分析的含義12/20/20226第五節(jié)敏感性分析二、目標函數(shù)系數(shù)C變化的敏感性分析1、單個目標函數(shù)系數(shù)Cj變化的情況（1）Cj為非基變量的目標函數(shù)系數(shù)（2）Cj為基變量的目標函數(shù)系數(shù)2、多個目標函數(shù)系數(shù)變化的情況（1）變化的目標函數(shù)系數(shù)都是非基變量（2）變化的目標函數(shù)系數(shù)中有一個是基變量，其他的是非基變量（3）變化的目標函數(shù)系數(shù)中有多于一個基變量12/25/202263第五節(jié)敏感性分析二、目標函數(shù)系數(shù)C變化的敏感性分析12/2第五節(jié)敏感性分析三、右邊項發(fā)生變化的敏感性分析1、單個右邊項發(fā)生變化2、多個右邊項發(fā)生變化四、增加新變量的敏感性分析在原問題中增加新變量，會導(dǎo)致約束系數(shù)矩陣的列向量增加，同時也會增加檢驗數(shù)的個數(shù)。如果增加新變量后，新變量的檢驗數(shù)仍小于0，則最優(yōu)解保持不變，否則最優(yōu)解會發(fā)生變化。五、增加新約束的敏感性分析1、如果原問題的最優(yōu)解滿足新約束條件，則最優(yōu)解保持不變。2、如果原問題的最優(yōu)解不滿足新約束條件，則需要尋找新的最優(yōu)解。12/25/202264第五節(jié)敏感性分析三、右邊項發(fā)生變化的敏感性分析12/20/第六講整數(shù)規(guī)劃第一節(jié)概述一、概念對決策變量的取值有整數(shù)限制的規(guī)劃問題，稱為整數(shù)規(guī)劃。二、整數(shù)規(guī)劃的分類1、線性整數(shù)規(guī)劃與非線性整數(shù)規(guī)劃2、純整數(shù)規(guī)劃與混合整數(shù)規(guī)劃12/25/202265第六講整數(shù)規(guī)劃第一節(jié)概述12/20/202265第一節(jié)概述三、線性整數(shù)規(guī)劃的模型MaxZ=CXS·t·AX≤(=、≥)bX≥0,且取整數(shù)12/25/202266第一節(jié)概述三、線性整數(shù)規(guī)劃的模型12/20/202266第一節(jié)概述四、整數(shù)線性規(guī)劃與一般線性規(guī)劃的關(guān)系1、對整數(shù)線性規(guī)劃的整數(shù)約束的放松，便得到一般的線性規(guī)劃，反之，對一般線性規(guī)劃增加變量取整的要求，則便變成整數(shù)線性規(guī)劃。因此，整數(shù)線性規(guī)劃的約束比一般線性規(guī)劃的約束更緊。2、整數(shù)線性規(guī)劃的可行域是一般線性規(guī)劃問題可行域的子集。3、整數(shù)線性規(guī)劃問題的目標函數(shù)值以一般線性規(guī)劃問題目標函數(shù)值為界，即整數(shù)線性規(guī)劃問題的最優(yōu)值，不可能優(yōu)于一般線性規(guī)劃問題的最優(yōu)值。12/25/202267第一節(jié)概述四、整數(shù)線性規(guī)劃與一般線性規(guī)劃的關(guān)系12/20第二節(jié)整數(shù)線性規(guī)劃的幾個典型模型一、背包問題一個背包的容積為V，現(xiàn)有n種物品待裝，物品的重量為wj，體積為vj,j=1,2,…,n，問如何配裝才能使得既不超過背包的容量，又能裝入的物品重量最大。二、工廠的選址問題有n城市｛1,2,…,n｝，需要某種物資的數(shù)量分別為d1,d2,…,dn，現(xiàn)欲打算建造m座工廠，假設(shè)在城市j建廠，規(guī)模為sj，需要投資為fj，從城市i到城市j的單位運輸費用為cij，問m座工廠應(yīng)分設(shè)在何處比較合適。12/25/202268第二節(jié)整數(shù)線性規(guī)劃的幾個典型模型一、背包問題12/20/20第二節(jié)整數(shù)線性規(guī)劃的幾個典型模型三、加工問題有m臺同類型的機床，有n種零件要在這些機床上進行加工，設(shè)加工的時間分別是a1,a2,…,an，問如何分配才能使各機床的總加工任務(wù)相等，或盡可能均衡。四、旅游推銷問題一個旅游推銷商從家門口A0出發(fā)，經(jīng)過預(yù)先確定的村子A1，A2，…An，然后回到家，假定村子Ai到村子Aj的距離為dij,問如何確定一條行走路線，經(jīng)過所有要去的村莊，且使總的行走路程最短。12/25/202269第二節(jié)整數(shù)線性規(guī)劃的幾個典型模型三、加工問題12/20/20第三節(jié)分枝定界法一、“公理”1、對一個整數(shù)線性規(guī)劃問題，如果不考慮變量取整的要求，由此求得的整數(shù)最優(yōu)解X，也一定是整數(shù)線性規(guī)劃問題的最優(yōu)解。2、對于一個整數(shù)非線性規(guī)劃問題，如果不考慮變量取整的要求，由此求得的非整數(shù)最優(yōu)解，則一定可以斷定整數(shù)線性規(guī)劃問題的最優(yōu)解不會好于非整數(shù)最優(yōu)解。3、在求解的過程中最先出現(xiàn)的整數(shù)解，不會好于最優(yōu)整數(shù)解。12/25/202270第三節(jié)分枝定界法一、“公理”12/20/202270第三節(jié)分枝定界法二、分枝定界的含義1、分枝的含義。按“公理”的要求，對一般線性規(guī)劃的可行域進行分解。2、定界的含義通過分枝不斷調(diào)整整數(shù)最優(yōu)解的上下界。12/25/202271第三節(jié)分枝定界法二、分枝定界的含義12/20/202271第三節(jié)分枝定界法三、分枝定界法的解題思路 1、對于給定的整數(shù)線性規(guī)劃問題，先不考慮變量取整的要求，把它當作一般的線性規(guī)劃問題來處理，并求其最優(yōu)解，如果該最優(yōu)解都是整數(shù)，則同時也就得到了整數(shù)線性規(guī)劃問題的最優(yōu)解，問題求解到此為止。2、若由一般線性規(guī)劃求出的最優(yōu)解不是整數(shù)解，假定基變量Xk=b/k不是整數(shù)，那么作如下處理:[b/k]<b/k<[b/k]+1。3、構(gòu)造兩個新的約束方程，并把它們分別加到問題中去，形成兩個整數(shù)規(guī)劃問題。12/25/202272第三節(jié)分枝定界法三、分枝定界法的解題思路12/20/20第三節(jié)分枝定界法兩個新的約束方程為：Xk≤[b/k]Xk≥[b/k]+1兩個新的整數(shù)規(guī)劃問題為：（I）MaxZ=CX（II）MaxZ=CXS·t·AX≤(=、≥)bS·t·AX≤(=、≥)b

Xk≤[b/k]Xk≥[b/k]+1X≥0,且取整數(shù)X≥0,且取整數(shù)

12/25/202273第三節(jié)分枝定界法兩個新的約束方程為：12/20/2022第三節(jié)分枝定界法4、分別按一般線性規(guī)劃求解這兩個整數(shù)規(guī)劃，直到能夠確定整數(shù)規(guī)劃的最優(yōu)解或能夠判定其無最優(yōu)解時為止。12/25/202274第三節(jié)分枝定界法4、分別按一般線性規(guī)劃求解這兩個整數(shù)規(guī)劃，第三節(jié)分枝定界法分枝定界法解的判定標準（I）（II）說明無可行解無可行解整數(shù)規(guī)劃無解無可行解整數(shù)解（II）的解為最優(yōu)解無可行解非整數(shù)最優(yōu)解對（II）繼續(xù)求解整數(shù)解整數(shù)解較優(yōu)解為最優(yōu)整數(shù)解整數(shù)解且目標函數(shù)優(yōu)于（II）非整數(shù)（I）的解為最優(yōu)解整數(shù)解非整數(shù)解且目標函數(shù)優(yōu)于（I）只對（II）繼續(xù)求解（I）的解為最優(yōu)解12/25/202275第三節(jié)分枝定界法分枝定界法解的判定標準12/20/2022第三節(jié)分枝定界法五、分枝定界法的應(yīng)用求解下列規(guī)劃問題：MaxZ=6x1+4x2s·t·2x1+4x2≤132x1+x2≤7x1、

x2≥0且取整數(shù)12/25/202276第三節(jié)分枝定界法五、分枝定界法的應(yīng)用12/20/20227第四節(jié)割平面法一、割平面法的基本思想

解整數(shù)規(guī)劃時，先不考慮變量取整的要求，把它當作一般的線性規(guī)劃問題來處理，假定X為一般規(guī)劃問題的最優(yōu)解，如果X是整數(shù)，則得到整數(shù)規(guī)劃的最優(yōu)解，如果X不是整數(shù)，則構(gòu)造一個約束方程，使X不滿足該方程，但原問題的所有整數(shù)可行解卻滿足該方程，然后再解增加約束后的線性規(guī)劃問題，直到求出最優(yōu)解為止。12/25/202277第四節(jié)割平面法一、割平面法的基本思想12/20/20227第四節(jié)割平面法二、割平面構(gòu)造問題三、應(yīng)用舉例12/25/202278第四節(jié)割平面法二、割平面構(gòu)造問題12/20/202278運籌學(xué)耿修林12/25/202279運籌學(xué)耿修林12/20/20221五、單純形方法（一）單純形方法的初步討論1、單純形方法的基本思想從可行域中的一個基本可行解出發(fā)，判斷它是否已是最優(yōu)解，若不是，尋找下一個基本可行解，并使目標函數(shù)得到改進，如此迭代下去，直到找出最優(yōu)解或判定問題無界為止。從另一個角度說，就是從可行域的某一個極點出發(fā)，迭代到另一個極點，并使目標函數(shù)的值有所改善，直到找出有無最優(yōu)解時為止。12/25/202280五、單純形方法（一）單純形方法的初五、單純形方法（一）單純形方法的初步討論2、單純形方法：消去法[例]求解線性規(guī)劃模型解：第一步，將線性規(guī)劃模型標準化：MaxZ=50x1+30x2+0x3+0x4s·t·4x1+3x2+x3=1202x1+x2++x4=50x1,x2,x3,,x4≥012/25/202281五、單純形方法（一）單純形方法的初步討論1

2、單純形方法：消去法第二步，尋找初始可行解。變量x3、,x4對應(yīng)的列向量A3、A4可作為初始可行基，那么X3、X4為基變量，X1、X2為非基變量，用非基量表示基變量，則有：MaxZ=50x1+30x2+0x3+0x4s·t·x3=120-4x1-3x2x4=50-2x1-x2x1,x2,x3,,x4≥0令x1、x2=0，得到基本可行解X=（0，0，120，50）。文本文本文本文本文本文本文本文本12/25/2022822、單純形方法：消去法文本文本文本文本文本文本文五、單純形方法2、單純形方法：消去法第三步，判斷目標函數(shù)是否達到了最優(yōu)。第四步，選取入基變量。確定x1為基變量，x2仍為非基變量。第五步，選取出基變量。x3=120-4x1-3x2≥0x4=50-2x1-x2≥0解不等式得：x1≤25，只有當x1=25時，x4恰好等于0，所以x4確定為出基變量。于是新的典則方程為：x1

=25-

0.5x2-

0.5x4x3=20-x2+2

x412/25/202283五、單純形方法2、單純形方法：消去法12（一）單純形方法的初步討論第六步，產(chǎn)生新的基本可行解及目標函數(shù)值。令x2、x4等于0，得到x1=25，x3=20，于是新的基本可行解為X=（25，0，20，0），目標函數(shù)值為Z=1250。第七步，判定目標函數(shù)值是否得到了最優(yōu)。根據(jù)分析目前的方案還不是最優(yōu)的。重復(fù)第四、五、六步，x2入基，x3出基，建立新的典則方程：x1=15+0.5x3-1.5x4x2=20-2x3+2x4令非基變量x3、x4等于0，得到新的基本可行解X=（15，20，0，0），目標函數(shù)值為1350。問題求解完成。12/25/202284（一）單純形方法的初步討論第六步，產(chǎn)生新的基本可行解及目標函五、單純形方法（二）單純形方法的矩陣描述1、線性規(guī)劃的典則形式：MaxZ=CBB-1b+(CN-CBB-1N)XNS·t·XB=B-1b-B-1NXN

XB,XN≥02、判別向量與判別數(shù)：（a）λ=CN-

CBB-1A為對應(yīng)基B的所有X的判別向量，其中任一分量λj=cj-CBB-1Aj為變量xj關(guān)于基B的判別數(shù)，j=1,2,-------,n。12/25/202285五、單純形方法（二）單純形方法的矩陣五、單純形方法2、判別向量與判別數(shù)：（b）λN=CN-CBB-1N為對應(yīng)基B的所有非基變量XN的判別向量，其中任一分量λj=cj-CBB-1Aj為非基變量xj關(guān)于基B的判別數(shù)，j=m+1,m+2,----------,n。（c）所有基變量的判別向量是零向量，所有基變量的判別數(shù)是0（為什么？）。3、最優(yōu)解的判定：（a）如果所有的檢驗數(shù)都小于0，則當前解為最優(yōu)解。12/25/202286五、單純形方法2、判別向量與判別數(shù)：12/2五、單純形方法3、最優(yōu)解的判定：（b）如果至少存在一個檢驗數(shù)大于0，且該檢驗數(shù)對應(yīng)的列向量中至少有一個正分量，則需要繼續(xù)進行迭代尋找最優(yōu)解。（c）如果至少存在一個檢驗數(shù)大于0，且該檢驗數(shù)對應(yīng)的列向量的所有分量都小于0，則線性規(guī)劃問題不存在有界最優(yōu)解。12/25/202287五、單純形方法3、最優(yōu)解的判定：12/20/五、單純形方法（三）單純形方法：表上作業(yè)法1、單純形表的構(gòu)造方法1：C-CBB-1A=(CB,CN)-CBB-1(B,N)=(0,CN-CBB-1N)兩邊同乘上X得：（C-CBB-1A）X=(0,CN-CBB-1N)X，化簡得：Z=CBB-1b+(CN-CBB-1N)XN

構(gòu)造聯(lián)立方程：Z+(CBB-1A-C)X

=CBB-1bB-1AX=B-1b12/25/202288五、單純形方法（三）單純形方法：表上作業(yè)法12/20/2五、單純形方法1、單純形表的構(gòu)造這樣得到單純形表：

12/25/202289五、單純形方法1、單純形表的構(gòu)造12/20/2022五、單純形方法1、單純形表的構(gòu)造方法2：XB=B-1b-B-1NXN，則有：XB+B-1NXN=B-1b又Z=CBB-1b+(CN-CBB-1N)XN，于是：Z+（CBB-1N-CN）XN=CBB-1b，這樣得：

Z+（CBB-1N-CN）XN=CBB-1bXB+B-1NXN=B-1b構(gòu)造單純形表：12/25/202290五、單純形方法1、單純形表的構(gòu)造12/20/20221五、單純形方法（三）單純形方法：表上作業(yè)法1、表上作業(yè)的步驟：第一步，將線性規(guī)劃問題進行標準化處理。第二步，確定初始基本可行解與初始可行基。第三步，編制單純形計算表。第四步，計算檢驗數(shù)，判斷線性規(guī)劃問題是否有最優(yōu)解。第五步，確定入基變量。一是最大檢驗數(shù)準則，二是最小下標準則。第六步，確定出基變量。最小檢驗數(shù)對應(yīng)的基變量出基。第七步，編制新的單純形表。重復(fù)以上的第四—七步，

直到能夠確定線性規(guī)劃問題是否有最優(yōu)解為止。

12/25/202291五、單純形方法（三）單純形方法：表上作業(yè)法12/20五、單純形方法2、單純形方法：表上作業(yè)法應(yīng)用舉例求解下列線性規(guī)劃問題：MinZ=X1-3X2S.t.2X1+4X2≤6-X1+3X2≤5X1,X2≥0解：第一步，將上述問題進行標準化處理：12/25/202292五、單純形方法2、單純形方法：表上作業(yè)法12/20/2五、單純形方法應(yīng)用舉例MaxZ=-X1+3X2S.t.2X1+4X2+X3=6-X1+3X2+X4=5X1,X2,X3,X4≥0第二步，確定初始基本可行解與初始基本可行基。初始可行基：B=（A3,A4）初始可行解：X=（0，0，6，5）12/25/202293五、單純形方法應(yīng)用舉例12/20/202215五、單純形方法應(yīng)用舉例第三步，構(gòu)造單純形表：-1300CBXBB-1bX1X2X3X4檢驗數(shù)0X3624103/20X45-13015/3檢驗數(shù)0-130012/25/202294五、單純形方法應(yīng)用舉例-1300CBXBB-1bX1五、單純形方法應(yīng)用舉例第四步，計算檢驗數(shù)并判斷是否是最優(yōu)解。檢驗數(shù)列在初始單純形表中的最后一行。第五步，確定入基變量。對應(yīng)的檢驗數(shù)最大，所以確定X2為入基變量。第六步，確定出基變量。計算的檢驗數(shù)列在初始單純形表中的最后一列。根據(jù)出基變量的判別準則，應(yīng)確定X3出基。12/25/202295五、單純形方法應(yīng)用舉例12/20/202217五、單純形方法-1300CBXBB-1bX1X2X3X4檢驗數(shù)3X21.50.510.2500X40.5-2.50-0.751檢驗數(shù)4.5-2.5-0.750第七步，構(gòu)造新的單純形表：12/25/202296五、單純形方法-1300CBXBB-1bX1X2X五、單純形方法應(yīng)用舉例第八步，判定迭代到這一步是否應(yīng)該停止。因為所有的非基變量的檢驗數(shù)都為負數(shù)，因此可以判斷迭代到此步的基是最優(yōu)基，目標函數(shù)值為Z=4.5，最優(yōu)解為X=（0，1.5，0，0）。原問題的最優(yōu)解為X=（0，1.5，0，0），目標函數(shù)值為Z=-4.5。12/25/202297五、單純形方法應(yīng)用舉例12/20/202219五、單純形方法（四）確定初始基本可行解的方法1、對于約束方程中都是小于等于0，并且約束方程右邊項皆大于0的情況，只要引進松弛變量即可得到單位陣的初始可行基。2、如果約束方程都是等于某些值的情況，此時需要引進人工變量才能構(gòu)造出單位陣的初始可行基和初始可行解。3、如果約束方程中有大于某些值的情況，則需要引進剩余變量并同時引進人工變量，才能構(gòu)造出單位陣的初始可行基和初始可行解。12/25/202298五、單純形方法（四）確定初始基本可行解的方法12/20/六、線性規(guī)劃的其他解法（一）人工變量消除法——M法1、M法的含義：通過引進人工變量，構(gòu)造一個輔助的線性規(guī)劃問題，然后由輔助的線性規(guī)劃問題找出原問題的第一個初始可行基，在此基礎(chǔ)上，利用單純形方法求出原問題的最優(yōu)解。12/25/202299六、線性規(guī)劃的其他解法（一）人工變量消除法——M法12/2六、線性規(guī)劃的其他解法（一）人工變量消除法——M法2、M法的輔助線性規(guī)劃問題：原問題：Maxz=c1x1+c2x2+……+cnxn

s.t.a11x1+a12x2+……+a1nxn=b1a21x1+a22x2+……+a2nxn=b2

……am1x1+am2x2+……+amnxn=bm

x1,x2,……,xn≥

012/25/2022100六、線性規(guī)劃的其他解法（一）人工變量消除法——M法12/六、線性規(guī)劃的其他解法（一）人工變量消除法——M法2、M法的輔助線性規(guī)劃問題：Maxz=c1x1+c2x2+…+cnxn-MXn+1-MXn+2-……-MXn+ms.t.a11x1+a12x2+……+a1nxn+Xn+1=b1

a21x1+a22x2+……+a2nxn+

Xn+2=b2

……am1x1+am2x2+……+amnxn+Xn+m=bm

x1,x2,……,xn≥

012/25/2022101六、線性規(guī)劃的其他解法（一）人工變量消除法——M法12/20六、線性規(guī)劃的其他解法3、M法的解題步驟（1）把原線性規(guī)劃問題進行標準化處理。（2）引進人工變量，構(gòu)造輔助線性規(guī)劃問題。（3）運用單純形方法，把人工變量全部剔除出基變量。（4）在得到的原問題的初始可行基的基礎(chǔ)上，運用單純形方法進行迭代。（5）直到能夠判斷原問題有無最優(yōu)解時為止。12/25/2022102六、線性規(guī)劃的其他解法3、M法的解題步驟12/20/2022六、線性規(guī)劃的其他解法4、M法解的判定（1）經(jīng)過若干次迭代后，基變量中無人工變量，則說明原問題有基本可行解。（2）經(jīng)過若干次迭代后，基變量中仍有人工變量，并且全部檢驗數(shù)皆小于0，則表明原問題無可行解。12/25/2022103六、線性規(guī)劃的其他解法4、M法解的判定12/20/20222六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法1、含義：在原來問題引入人工變量后分兩個階段求解線性規(guī)劃問題的方法。其中，第一階段在原來問題中引入人工變量，設(shè)法構(gòu)造一個單位陣的初始可行基，另外在目標函數(shù)中令非人工變量的系數(shù)全部為0，人工變量的系數(shù)為1，構(gòu)造一個新的輔助目標函數(shù)。在此基礎(chǔ)上，建立輔助線性規(guī)劃問題。然后運用單純形方法求解，直到輔助目標函數(shù)為0時為止。第二階段重新回到原來的問題，以第一階段得到的可行基為初始可行基，運用單純形方法以求出原來問題的解。12/25/2022104六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法12/六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法2、兩階段法的輔助問題：原問題：Maxz=c1x1+c2x2+……+cnxn

s.t.a11x1+a12x2+……+a1nxn=b1

a21x1+a22x2+……+a2nxn=b2

……am1x1+am2x2+……+amnxn=bmx1,x2,……,xn≥

012/25/2022105六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法12六、線性規(guī)劃的其他解法（二）人工變量消除法——兩階段法2、兩階段法的輔助問題：輔助問題：MinZ/=Xn+1+Xn+2+…+Xn+ms.t.a11x1+a12x2+……+a1nxn+Xn+1