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

1、耿修林12/15/20211l（一）單純形方法的初步討論1、單純形方法的基本思想 從可行域中的一個基本可行解出發(fā)，判斷它是否已是最優(yōu)解，若不是，尋找下一個基本可行解，并使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找出最優(yōu)解或判定問題無界為止。 從另一個角度說，就是從可行域的某一個極點出發(fā)，迭代到另一個極點，并使目標(biāo)函數(shù)的值有所改善，直到找出有無最優(yōu)解時為止。12/15/20212l（一）單純形方法的初步討論2、單純形方法：消去法例求解線性規(guī)劃模型 解：第一步，將線性規(guī)劃模型標(biāo)準(zhǔn)化： Max Z=50 x1+30 x2+0 x3+0 x4 st 4x1+3x2+x3 =120 2x1+x2+ +x4

2、=50 x1 , x2 , x3 , ,x4012/15/20213 2、單純形方法：消去法 第二步，尋找初始可行解。變量x3 、,x4對應(yīng)的列 向量A3、A4 可作為初始可行基，那么X3、X4為基 變量，X1、X2為非基變量，用非基量表示基變量， 則有： Max Z=50 x1+30 x2+0 x3+0 x4 st x3 =120- 4x1-3x2 x4 =50 -2x1-x2 x1 , x2 , x3 , ,x40 令x1 、 x2 =0，得到基本可行解 X=（0，0，120，50）。12/15/202142、單純形方法：消去法第三步，判斷目標(biāo)函數(shù)是否達(dá)到了最優(yōu)。第四步，選取入基變量。確定

3、x1 為 基變量， x2仍為非基變量。第五步，選取出基變量。 x3 =120- 4x1-3x20 x4 =50 -2x1-x20解不等式得：x125 ，只有當(dāng)x1=25時， x4恰好等于0，所以x4確定為出基變量。于是新的典則方程為： x1 =25 - 0.5x2 - 0.5 x4 x3 =20 - x2 + 2 x412/15/20215第六步，產(chǎn)生新的基本可行解及目標(biāo)函數(shù)值。令x2 、 x4等于0，得到x1 =25， x3 =20，于是新的基本可行解為X=（25，0，20，0），目標(biāo)函數(shù)值為Z=1250。第七步，判定目標(biāo)函數(shù)值是否得到了最優(yōu)。根據(jù)分析目前的方案還不是最優(yōu)的。重復(fù)第四、五、六

4、步， x2入基， x3 出基，建立新的典則方程： x1 =15+ 0.5 x3 -1.5 x4 x2 =20 - 2 x3 + 2 x4令非基變量x3 、 x4等于0，得到新的基本可行解X=（15，20，0，0），目標(biāo)函數(shù)值為1350。問題求解完成。12/15/20216l（二）單純形方法的矩陣描述1、線性規(guī)劃的典則形式： Max Z=CBB-1b+(CN-CBB-1N)XN St 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, -,

5、n。12/15/202172、判別向量與判別數(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，則當(dāng)前解為最優(yōu)解。12/15/202183、最優(yōu)解的判定：（b）如果至少存在一個檢驗數(shù)大于0，且該檢驗數(shù)對應(yīng)的列向量中至少有一個正分量，則需要繼續(xù)進(jìn)行迭代尋找最優(yōu)解。（c）如果至少存在一個檢驗數(shù)大于0，且該檢驗數(shù)對應(yīng)的列向量的所有分量都小于0，則線性規(guī)劃問題不

6、存在有界最優(yōu)解。12/15/20219l（三）單純形方法：表上作業(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-1b B-1AX =B-1b12/15/2021101、單純形表的構(gòu)造 這樣得到單純形表： 12/15/2021111、單純形表的構(gòu)造方法2： XB=B-1b-B-1NXN，則有： XB+B-1N XN =B-1b 又 Z=CBB

7、-1b+(CN-CBB-1N)XN，于是： Z+（CBB-1N-CN）XN=CBB-1b，這樣得： Z+（CBB-1N-CN）XN=CBB-1b XB +B-1N XN=B-1b 構(gòu)造單純形表：12/15/202112l（三）單純形方法：表上作業(yè)法1、表上作業(yè)的步驟：第一步，將線性規(guī)劃問題進(jìn)行標(biāo)準(zhǔn)化處理。第二步，確定初始基本可行解與初始可行基。第三步，編制單純形計算表。第四步，計算檢驗數(shù)，判斷線性規(guī)劃問題是否有最優(yōu)解。第五步，確定入基變量。一是最大檢驗數(shù)準(zhǔn)則，二是最 小下標(biāo)準(zhǔn)則。第六步，確定出基變量。最小檢驗數(shù)對應(yīng)的基變量出基。第七步，編制新的單純形表。重復(fù)以上的第四七步， 直到能夠確定線性規(guī)

8、劃問題是否有最優(yōu)解為止。 12/15/202113l2、單純形方法：表上作業(yè)法l應(yīng)用舉例 求解下列線性規(guī)劃問題： Min Z=X1-3X2 S.t. 2X1+4X2 6 -X1+3X25 X1 , X20 解： 第一步，將上述問題進(jìn)行標(biāo)準(zhǔn)化處理：12/15/202114l應(yīng)用舉例 Max Z=-X1+3X2 S.t. 2X1+4X2+X3 =6 -X1+3X2 + X4 =5 X1,X2,X3,X4 0第二步，確定初始基本可行解與初始基本可行基。 初始可行基： B=（A3,A4） 初始可行解： X=（0，0，6，5）12/15/202115l應(yīng)用舉例第三步，構(gòu)造單純形表：-1300CBXB B

9、-1bX1 X2 X3X4檢驗數(shù)0X3624103/20X45-13015/3檢驗數(shù)0-130012/15/202116l應(yīng)用舉例第四步，計算檢驗數(shù)并判斷是否是最優(yōu)解。檢驗數(shù)列在初始單純形表中的最后一行。第五步，確定入基變量。 對應(yīng)的檢驗數(shù)最大，所以確定X2為入基變量。第六步，確定出基變量。計算的檢驗數(shù)列在初始單純形表中的最后一列。根據(jù)出基變量的判別準(zhǔn)則，應(yīng)確定X3出基。12/15/202117-1300CBXB B-1bX1 X2 X3X4檢驗數(shù)3X21.50.510.2500X40.5-2.50-0.751檢驗數(shù)4.5-2.5-0.750第七步，構(gòu)造新的單純形表：12/15/202118l

10、應(yīng)用舉例第八步，判定迭代到這一步是否應(yīng)該停止。 因為所有的非基變量的檢驗數(shù)都為負(fù)數(shù)，因此可以判斷迭代到此步的基是最優(yōu)基，目標(biāo)函數(shù)值為Z=4.5，最優(yōu)解為X=（0，1.5，0，0）。原問題的最優(yōu)解為X=（0，1.5，0，0），目標(biāo)函數(shù)值為Z=-4.5。12/15/202119l（四）確定初始基本可行解的方法1、對于約束方程中都是小于等于0，并且約束方程右邊項皆大于0的情況，只要引進(jìn)松弛變量即可得到單位陣的初始可行基。2、如果約束方程都是等于某些值的情況，此時需要引進(jìn)人工變量才能構(gòu)造出單位陣的初始可行基和初始可行解。3、如果約束方程中有大于某些值的情況，則需要引進(jìn)剩余變量并同時引進(jìn)人工變量，才能構(gòu)

11、造出單位陣的初始可行基和初始可行解。12/15/202120l（一）人工變量消除法M法1、M法的含義： 通過引進(jìn)人工變量，構(gòu)造一個輔助的線性規(guī)劃問題，然后由輔助的線性規(guī)劃問題找出原問題的第一個初始可行基，在此基礎(chǔ)上，利用單純形方法求出原問題的最優(yōu)解。12/15/202121l（一）人工變量消除法M法2、M法的輔助線性規(guī)劃問題： 原問題： Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn=b1 a21 x1+ a22x2+ +a2nxn =b2 am1x1+am2x2+amnxn=bm x1,x2, ,xn 012/15/202122l（一）人工變量消除法M

12、法2、M法的輔助線性規(guī)劃問題： Max z=c1x1+c2x2+cnxn-MXn+1-MXn+2-MXn+m s.t. a11x1+a12x2+a1nxn+Xn+1 =b1 a21x1+a22x2+ +a2nxn + Xn+2 =b2 am1x1+am2x2+ +amnxn +Xn+m=bm x1,x2, ,xn 012/15/202123l3、M法的解題步驟（1）把原線性規(guī)劃問題進(jìn)行標(biāo)準(zhǔn)化處理。（2）引進(jìn)人工變量，構(gòu)造輔助線性規(guī)劃問題。（3）運用單純形方法，把人工變量全部剔除出基變量。（4）在得到的原問題的初始可行基的基礎(chǔ)上，運用單純形方法進(jìn)行迭代。（5）直到能夠判斷原問題有無最優(yōu)解時為止。

13、12/15/202124l4、M法解的判定（1）經(jīng)過若干次迭代后，基變量中無人工變量，則說明原問題有基本可行解。（2）經(jīng)過若干次迭代后，基變量中仍有人工變量，并且全部檢驗數(shù)皆小于0，則表明原問題無可行解。12/15/202125l（二）人工變量消除法兩階段法1、含義：在原來問題引入人工變量后分兩個階段求解線性規(guī)劃問題的方法。其中，第一階段在原來問題中引入人工變量，設(shè)法構(gòu)造一個單位陣的初始可行基，另外在目標(biāo)函數(shù)中令非人工變量的系數(shù)全部為0，人工變量的系數(shù)為1，構(gòu)造一個新的輔助目標(biāo)函數(shù)。在此基礎(chǔ)上，建立輔助線性規(guī)劃問題。然后運用單純形方法求解，直到輔助目標(biāo)函數(shù)為0時為止。第二階段重新回到原來的問題

14、，以第一階段得到的可行基為初始可行基，運用單純形方法以求出原來問題的解。12/15/202126l（二）人工變量消除法兩階段法2、兩階段法的輔助問題： 原問題： Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn =b1 a21 x1+ a22x2+ +a2nxn =b2 am1x1+am2x2+amnxn =bm x1,x2, ,xn 012/15/202127l（二）人工變量消除法兩階段法2、兩階段法的輔助問題： 輔助問題： Min Z/=Xn+1+Xn+2+Xn+ms.t. a11x1+a12x2+a1nxn+Xn+1 = b1 a21 x1+ a22

15、x2+ +a2nxn + Xn+2 =b2 am1x1+am2x2+amnxn + Xn+m=bm x1,x2, ，,xn 0 Xn+1，Xn+2 ， ，Xn+m 012/15/202128l（二）人工變量消除法兩階段法3、解的判斷：（1）輔助問題的目標(biāo)函數(shù)值Z/ 0。（2）假定B為輔助問題最優(yōu)基，此時若輔助問題的目標(biāo)函數(shù)值Z/ 0，則原問題無解。 證明（請同學(xué)們自己做一做）。 （3）輔助問題在最優(yōu)基B下目標(biāo)函數(shù)的值Z/=0，此時有兩種情況：第一種情況，若輔助問題的最優(yōu)基B對應(yīng)的基變量中無人工變量，則該最優(yōu)基也是原問題的可行基，這時候只要在單純形表中去掉人工變量所在的列和最后一行，即可得到原問

16、題的初始可行單純形表。12/15/202129l（二）人工變量消除法兩階段法3、解的判斷：（3）第二種情況，若輔助問題最優(yōu)基B對應(yīng)的基變量中還有人工變量，即存在： yr+a/rkyk+a/rjxj=0這時需要進(jìn)行討論：第一，若a/rj=0，即有： yr+a/rkyk=0 則表明原問題中的第r個約束是多余的，可以從輔助問題單純形表中，直接劃掉這一行。第二，若a/rj中至少有一個不等于0，則需要以之為轉(zhuǎn)軸元素再進(jìn)行迭代，直到化為第一種情況為止。12/15/2021301、退化問題 在約束系數(shù)矩陣A=(aij)mn, （ mn）中，若R（A） m，則稱該線性規(guī)劃問題是退化的。2、退化迭代的特點（1）

17、退化解的基變量中至少有一個取值為0。（2）退化迭代中基在不斷變化但解始終不變。（3）退化迭代不會引起目標(biāo)函數(shù)值的改進(jìn)。3、防止循環(huán)迭代的方法（1）攝動法（2）字典順序法（3）最小下標(biāo)法12/15/202131l4、退化問題的單純形攝動方法（1）原理 對退化的線性規(guī)劃問題的右邊項作微小的擾動，以避免因退化而引起的循環(huán)。（2）應(yīng)用舉例12/15/202132見Excel中的演示12/15/20213312/15/202134l第一節(jié) 線性規(guī)劃建模的幾個問題l第二節(jié) 常見的線性規(guī)劃模型l第三節(jié) 案例討論12/15/202135l一、線性規(guī)劃建模的要求與思路1、要求：繁簡適當(dāng)，要能夠反映實際問題的主要

18、因素，得出結(jié)論和產(chǎn)生效益。2、思路：首先將實際問題簡化得能比較容易地建立一個粗略的、可以使用的模型；在這個基礎(chǔ)上考慮加進(jìn)先前被省略掉的一些因素，改進(jìn)已建立的模型；重復(fù)這個過程直到能建立符合要求的模型為止。 12/15/202136l二、線性規(guī)劃建模的一般過程 1、明確決策變量 2、確定目標(biāo)函數(shù) 3、確立約束方程 4、給出變量取值的限制12/15/202137l三、參數(shù)資料的來源 1、統(tǒng)計資料 2、會計核算資料 3、工程分析 4、實驗研究 5、合理規(guī)定等12/15/202138l一、配料問題 假設(shè)有n種原料，已知每種原料都含有m種成分，又已知每種原料的單位成分含量為aij（i=1,2, ,m,j

19、=1,2, ,n）?，F(xiàn)欲用這n種原料配制成一種產(chǎn)品，要求單位產(chǎn)品的各種成分的含量為bi ，如果每種原料的單價為cj。問如何配料才能使產(chǎn)品的生產(chǎn)成本最低。12/15/202139l二、資源利用問題 生產(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/15/202140l三、運輸問題:某種物資有m個產(chǎn)地、n個需地，產(chǎn)地產(chǎn)量、需地的需求量及由產(chǎn)地到需地的單位運價如下： 運價（C） 需求地（B） 產(chǎn)量

20、（a）12n產(chǎn)地111121n1221222n2mm1m2mnM需求量（b）12n12/15/202141l三、運輸問題：問如何設(shè)計運輸方案，才能使運輸成本達(dá)到最小。（1）產(chǎn)銷平衡 （2）產(chǎn)大于銷（3）產(chǎn)小于銷 （4）運力限制等12/15/202142l四、投資問題： 設(shè)有n個投資項目可供選擇，Cj表示第j個投資項目的收益率，a表示第i種資源用于第j個項目的投資數(shù)量，b表示第i種資源的數(shù)量，問如何進(jìn)行投資才能使投資總收益率最大。12/15/202143l五、混合問題：某石油公司用A、B、C三種原料混合成普通汽油（R）、高級汽油（P）和低鉛汽油（L）3種成品出售。3種原料的單位成本及每月最大購入

21、量： 原料 單位成本 最大購入量 A a 100 B b 150 C c 5012/15/202144l五、混合問題： 每千克成品油的售價為：普通汽油為d元，高級汽油為e元，低鉛汽油為f元。 低鉛汽油每月最多銷售50噸。 各種汽油的規(guī)格如下： 普通汽油R：A少于20%、C不多于30%； 高級汽油P：A不少于40%、B不少于己于10%且不多于20%、C不多于10%； 低鉛汽油：B不少于30%。試建立線性規(guī)劃模型。 12/15/202145l六、下料問題： 用某種材料切割m種毛坯，根據(jù)經(jīng)驗，單位材料上有n種不同的下料方案，每種下料方案可得各種毛坯數(shù)量及每種毛坯的需求量為： C 下料方案需求量B1B

22、2.Bn毛坯名稱A1A2Am1112.1nb12122.2nb2.m1m2.mnbm12/15/202146l六、下料問題： 問應(yīng)該怎樣安排下料方案，才能是材料的消耗最省。12/15/202147l七、分派問題： 設(shè)有n件工作B1，B2，.，Bn，分 派給n個人A1，A2，An去做，每 人只做一件工作且每件工作只安排一人 做，Ai完成Bj的工時為Cij。問應(yīng)如何分 派才能使總工時最省。12/15/202148l八、生產(chǎn)進(jìn)度問題： 某企業(yè)生產(chǎn)一種季節(jié)性很強的產(chǎn)品，產(chǎn)品只能在k個月內(nèi)銷售，同時生產(chǎn)也要在這些月內(nèi)進(jìn)行。除正常生產(chǎn)時間生產(chǎn)外，也可以加班生產(chǎn)，產(chǎn)品在正常生產(chǎn)時間每月最多能生產(chǎn)A個單位，單

23、位成本為a元，加班生產(chǎn)每月最多能生產(chǎn)B個單位，單位成本為b元。當(dāng)月生產(chǎn)未及時銷售出去的需貯存，庫存容量為C，貯存費為單位產(chǎn)品c元，k個月的需求量分別為O1、O2,.,Ok。試建立線性規(guī)劃模型，使得總的生產(chǎn)費用最低。12/15/202149l第一節(jié) 線性規(guī)劃的對偶問題l一、問題的提出l二、原問題與對偶問題的關(guān)系：（1）原問題求極大（小）對偶問題求極?。ù螅?）原問題目標(biāo)函數(shù)的系數(shù)變成對偶問題的約束方程的右邊項，同樣，對偶問題目標(biāo)函數(shù)的系數(shù)是原問題的約束方程的右邊項（3）原問題的變量的個數(shù)、主約束的個數(shù)分別等于對偶問題的主約束個數(shù)和變量的個數(shù)（4）原問題的約束系數(shù)矩陣與對偶問題的約束系數(shù)矩陣存在

24、轉(zhuǎn)置關(guān)系12/15/202150l二、原問題與對偶問題的關(guān)系（5）在原極小問題中的“大于等于”、“小于等于”、“等于”約束，分別與對偶問題中變量的“大于等于0”、“小于等于0”、“無約束”相對應(yīng)。反之，在原極小問題中的變量“大于等于0”、“小于等于0”、“無約束”分別對應(yīng)著對偶問題約束中的“小于等于”、“大于等于”、“等于”。12/15/202151l三、原問題與對偶問題的轉(zhuǎn)換 舉例說明。12/15/202152l一、原問題與對偶問題是相互對稱的。l二、弱對偶定理： 原問題的目標(biāo)函數(shù)值以對偶問題的目標(biāo)函數(shù)值為上界，對偶問題的目標(biāo)函數(shù)值以原問題的目標(biāo)函數(shù)值為下界。l三、無界性定理：若原問題（對偶

25、問題）為無界解，則對偶問題（原問題）無可行解。12/15/202153l四、最優(yōu)解性質(zhì)定理： X*、Y*分別是原問題與對偶問題的可行解，若有CX*=Y*b存在，則X*、Y*分別是原問題與對偶問題的最優(yōu)解。l五、對偶定理： 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)的值相等。l六、互補松弛性定理： X*、Y* 分別是原問題和對偶問題的可行解，若Y* Xs=Ys X* ，當(dāng)且僅當(dāng)X*、Y*為最優(yōu)解。12/15/202154l一、關(guān)于互補松弛性定理的幾個重要的推論l二、互補松弛定理的應(yīng)用應(yīng)用舉例 Max 2X1+4X2+X3+X4 St X1+3X2 +X4 8 2X1+X2 6 X2+X

26、3+X46 X1+X2+X3 9 X1、X2、X3、X4012/15/202155l二、互補松弛定理的應(yīng)用 其最優(yōu)解為X=（2，2，4，0），目標(biāo)函數(shù)值為16。試運用互補松弛定理求對偶問題的最優(yōu)解。12/15/202156l三、對偶解的解釋1、對偶解與影子價格2、檢驗數(shù)與邊際貢獻(xiàn)12/15/202157l一、對偶單純形方法的基本思想 從對偶問題的可行解和原問題的不可行解出發(fā)，進(jìn)行換基迭代，一旦當(dāng)原問題的解也變成可行解時，這時的解就是原問題的最優(yōu)解。l二、對偶單純形方法與原單純形方法的區(qū)別1、原單純形方法從可行解和對偶問題不可行解出發(fā)，直到所有的檢驗數(shù)皆小于等于0，而對偶單純形方法則從對偶可行解

27、和原問題不可行解出發(fā)，直到原問題的解也變成可行。12/15/202158l二、對偶單純形方法與原單純形方法的區(qū)別2、最優(yōu)解的判定標(biāo)準(zhǔn)不一樣。3、確定出入基變量的順序不同。原單純形方法，先確定入基變量后再確定出基變量，而對偶單純形方法先確定出基變量后確定入基變量。4、確定出入基變量的方法不同。12/15/202159l三、對偶單純形方法的解的判定1、B-1b0，表明已求出了原問題的最優(yōu)解。2、 B-1b中至少有一個負(fù)分量，且該負(fù)分量所在行的各元素都是非負(fù)數(shù)，則問題無最優(yōu)解。3、 B-1b中至少有一個負(fù)分量，且該負(fù)分量所在行的元素中存在負(fù)數(shù)，則需要繼續(xù)迭代。12/15/202160l四、對偶單純形

28、算法的過程1、對問題進(jìn)行標(biāo)準(zhǔn)化處理2、確定一個初始的對偶可行解3、編制對偶單純形表4、判定目標(biāo)函數(shù)是否達(dá)到最優(yōu)5、換基迭代，直到能判定問題有無最優(yōu)解時為止。l五、應(yīng)用舉例12/15/202161l一、敏感性分析的含義 由于受到政策、價格、工藝水平、資源貯備、設(shè)備更新等若干因素的影響，線性規(guī)劃模型中的參數(shù)C、A、b經(jīng)常會發(fā)生變化，那么C、A、b在什么樣的范圍內(nèi)變化，才不會導(dǎo)致已求出的最優(yōu)基的改變，這就是敏感性分析所要解決的問題。12/15/202162l二、目標(biāo)函數(shù)系數(shù)C變化的敏感性分析1、單個目標(biāo)函數(shù)系數(shù)Cj變化的情況（1）Cj為非基變量的目標(biāo)函數(shù)系數(shù)（2） Cj為基變量的目標(biāo)函數(shù)系數(shù)2、多個

29、目標(biāo)函數(shù)系數(shù)變化的情況（1）變化的目標(biāo)函數(shù)系數(shù)都是非基變量（2）變化的目標(biāo)函數(shù)系數(shù)中有一個是基變量，其他的是非基變量（3）變化的目標(biāo)函數(shù)系數(shù)中有多于一個基變量12/15/202163l三、右邊項發(fā)生變化的敏感性分析1、單個右邊項發(fā)生變化 2、多個右邊項發(fā)生變化l四、增加新變量的敏感性分析 在原問題中增加新變量，會導(dǎo)致約束系數(shù)矩陣的列向量增加，同時也會增加檢驗數(shù)的個數(shù)。如果增加新變量后，新變量的檢驗數(shù)仍小于0，則最優(yōu)解保持不變，否則最優(yōu)解會發(fā)生變化。l五、增加新約束的敏感性分析1、如果原問題的最優(yōu)解滿足新約束條件，則最優(yōu)解保持不變。2、如果原問題的最優(yōu)解不滿足新約束條件，則需要尋找新的最優(yōu)解。1

30、2/15/202164l第一節(jié) 概述l一、概念 對決策變量的取值有整數(shù)限制的規(guī)劃問題，稱為整數(shù)規(guī)劃。l二、整數(shù)規(guī)劃的分類1、線性整數(shù)規(guī)劃與非線性整數(shù)規(guī)劃2、純整數(shù)規(guī)劃與混合整數(shù)規(guī)劃12/15/202165l三、線性整數(shù)規(guī)劃的模型 Max Z=CX St AX(=、)b X0,且取整數(shù)12/15/202166l四、整數(shù)線性規(guī)劃與一般線性規(guī)劃的關(guān)系1、對整數(shù)線性規(guī)劃的整數(shù)約束的放松，便得到一般的線性規(guī)劃，反之，對一般線性規(guī)劃增加變量取整的要求，則便變成整數(shù)線性規(guī)劃。因此，整數(shù)線性規(guī)劃的約束比一般線性規(guī)劃的約束更緊。2、整數(shù)線性規(guī)劃的可行域是一般線性規(guī)劃問題可行域的子集。3、整數(shù)線性規(guī)劃問題的目標(biāo)函

31、數(shù)值以一般線性規(guī)劃問題目標(biāo)函數(shù)值為界，即整數(shù)線性規(guī)劃問題的最優(yōu)值，不可能優(yōu)于一般線性規(guī)劃問題的最優(yōu)值。12/15/202167l一、背包問題 一個背包的容積為V，現(xiàn)有n種物品待裝，物品的重量為wj，體積為vj,j=1,2, ,n，問如何配裝才能使得既不超過背包的容量，又能裝入的物品重量最大。l二、工廠的選址問題 有n城市1,2, ,n，需要某種物資的數(shù)量分別為d1, d2, ,dn，現(xiàn)欲打算建造m座工廠，假設(shè)在城市j建廠，規(guī)模為sj，需要投資為fj，從城市i到城市j的單位運輸費用為cij，問m座工廠應(yīng)分設(shè)在何處比較合適。12/15/202168l三、加工問題 有m臺同類型的機床，有n種零件要在這些機床上進(jìn)行加工，設(shè)加工的時間分別是a1,a2,an，問如何分配才能使各機床的總加工任務(wù)相等，或盡可能均衡。l四、旅游推銷問題 一個旅游推銷商從家門口A0出發(fā)，經(jīng)過預(yù)先確定的村子A1，A2，An，然后回到家，假定村子Ai到村子Aj的距離為dij,問如何確定一條行走路線，經(jīng)過所有要去的村莊，且使總的行走路程最短。12/15/202169l一、“公理”1、對一個整數(shù)線性規(guī)劃問題，如果不考慮變量取整的要求，由此求得的整數(shù)最優(yōu)解X，也一定是整數(shù)線性規(guī)劃問題的