運(yùn)籌學(xué)數(shù)學(xué)建模7-9(1)

1、運(yùn)籌學(xué)理論與建模運(yùn)籌學(xué)理論與建模河北聯(lián)合大學(xué)理學(xué)院河北聯(lián)合大學(xué)理學(xué)院肖繼先肖繼先主要內(nèi)容主要內(nèi)容第一部分第一部分 線性規(guī)劃建模方法線性規(guī)劃建模方法第二部分第二部分 整數(shù)規(guī)劃建模方法整數(shù)規(guī)劃建模方法第三部分第三部分 指派問題指派問題第四部分第四部分 動(dòng)態(tài)規(guī)劃建模動(dòng)態(tài)規(guī)劃建模第五部分第五部分 圖論與網(wǎng)絡(luò)優(yōu)化圖論與網(wǎng)絡(luò)優(yōu)化第一部分第一部分 線性規(guī)劃建模方法線性規(guī)劃建模方法一、從現(xiàn)實(shí)問題到線性規(guī)劃模型一、從現(xiàn)實(shí)問題到線性規(guī)劃模型二、線性規(guī)劃模型的求解二、線性規(guī)劃模型的求解三、線性規(guī)劃建模實(shí)例三、線性規(guī)劃建模實(shí)例例例1 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃1桶桶牛奶牛奶 3公斤公斤A1 12小時(shí)小時(shí)

2、 8小時(shí)小時(shí) 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天每天:一、從現(xiàn)實(shí)問題到線性規(guī)劃模型一、從現(xiàn)實(shí)問題到線性規(guī)劃模型1桶桶牛奶牛奶 3公斤公斤A1 12

3、小時(shí)小時(shí) 8小時(shí)小時(shí) 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031 x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax 每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21 xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析與假設(shè)模型分析與假設(shè) 比比例例性性 可可

4、加加性性 連續(xù)性連續(xù)性 xi對目標(biāo)函數(shù)的對目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xi取值取值成正比成正比 xi對約束條件的對約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xi取值取值成正比成正比 xi對目標(biāo)函數(shù)的對目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xj取值取值無關(guān)無關(guān) xi對約束條件的對約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xj取值取值無關(guān)無關(guān) xi取值連續(xù)取值連續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和的數(shù)量和時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛

5、奶加工出A1,A2的數(shù)量和的數(shù)量和是與時(shí)間相互產(chǎn)量無關(guān)的常數(shù)是與時(shí)間相互產(chǎn)量無關(guān)的常數(shù)加工加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)的牛奶桶數(shù)是實(shí)數(shù) 線性規(guī)劃模型線性規(guī)劃模型A1A2現(xiàn)有資源現(xiàn)有資源設(shè)備設(shè)備128臺(tái)時(shí)臺(tái)時(shí)甲甲4016公斤公斤乙乙0412 公斤公斤利潤利潤2030（元）（元）制訂生產(chǎn)計(jì)劃制訂生產(chǎn)計(jì)劃,使使每天獲利最大每天獲利最大 例例2 2 工廠生產(chǎn)兩種工廠生產(chǎn)兩種產(chǎn)品產(chǎn)品A1,A2,已知生已知生產(chǎn)單位產(chǎn)品情況如產(chǎn)單位產(chǎn)品情況如表：表：設(shè)設(shè)生產(chǎn)生產(chǎn)A1、A2分別分別x1、x2公斤公斤 max z= 20 x1+30 x2 (1)1212121228,(2)4016,(3). .0412,(4

6、)0,0.(5)xxxxs txxxx目標(biāo)函數(shù)目標(biāo)函數(shù)約約束束條條件件決策變量決策變量一、從現(xiàn)實(shí)問題到線性規(guī)劃模型一、從現(xiàn)實(shí)問題到線性規(guī)劃模型線性規(guī)劃模型標(biāo)準(zhǔn)型線性規(guī)劃模型標(biāo)準(zhǔn)型:maxz= c1 x1 +c2x2 +cnxn11112211211222221122,. .,0,1,.nnnnmmmnnmiaxaxaxbaxaxaxbs taxaxaxbxin (LP)線性規(guī)劃模型標(biāo)準(zhǔn)型矩陣表示：線性規(guī)劃模型標(biāo)準(zhǔn)型矩陣表示：max z= cX. .0s tAXbX 12 , , ,ncc cc12 , ,Tmbb bb12 , ,TnXx xx.ij m nAa0,b max(min) z=

7、c1 x1 +c2x2 +cnxn1111221121122222112211( , ),( , ),. .( , ),0,0,.nnnnmmmnnmijkla xa xa xba xa xaxbs taxaxaxbxxiiijjj 線性規(guī)劃模型一般形式：線性規(guī)劃模型一般形式：1.線性規(guī)劃的一般形化為標(biāo)準(zhǔn)型的一般步驟線性規(guī)劃的一般形化為標(biāo)準(zhǔn)型的一般步驟(1) Min f = cX 轉(zhuǎn)化為轉(zhuǎn)化為max z = cX(2)1122iiinna xa xa x ib 加松弛變量加松弛變量yi 1122iiinniia xa xa xyb 1122iiinna xa xa x (3)ib 加剩余變量加

8、剩余變量yi1122iiinniia xa xa xyb (4) 若存在可正可負(fù)變量若存在可正可負(fù)變量xi 令令12,iiixxx 12,0.iixx 例例 將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型1231231231237,2,.325,0,xxxxxxs txxxx xx min z = x1 +2x2 3x3無約束無約束標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型maxz = x1 2x2 +3(x4 x5 )+0 x6 +0 x7 124561245712451245677,2,.3225,0.xxxxxxxxxxs txxxxxxxxxx (1) x3 = x4 x5 , x4 , x5 0(2)

9、x1 +x2 +x3 +x6 =7(3) x1 x2 +x3 x7 =2合理下料問題合理下料問題 有長度為有長度為8米的某型號圓米的某型號圓鋼，現(xiàn)需要長度為鋼，現(xiàn)需要長度為2.5米的米的毛坯毛坯100根，長度為根，長度為1.3米米的毛坯的毛坯200根，如何選者下根，如何選者下料方式，所需總用料最省料方式，所需總用料最省? 解：可能的下料方式：解：可能的下料方式：2.51.3130222314406設(shè)按第設(shè)按第i種下料方式的種下料方式的圓鋼圓鋼xi根，根，i=1,2,3,4 min z= x1+x2 +x3 +x4 12323432100,. . 246200,0,1,2,3,4.ixxxs t

10、xxxxi 有一組決策變量有一組決策變量,約束條件是決約束條件是決策變量的線性等式或不等式策變量的線性等式或不等式,目目標(biāo)函數(shù)是決策變量的線性函數(shù)標(biāo)函數(shù)是決策變量的線性函數(shù),這樣的規(guī)劃問題稱為線性規(guī)劃這樣的規(guī)劃問題稱為線性規(guī)劃.記為（記為（LP）例例.某小區(qū)一個(gè)某小區(qū)一個(gè)24小時(shí)營業(yè)便利店小時(shí)營業(yè)便利店,一一天各時(shí)段所需服務(wù)員最少人數(shù)如下天各時(shí)段所需服務(wù)員最少人數(shù)如下表表.根據(jù)實(shí)際情況根據(jù)實(shí)際情況,要求每個(gè)服務(wù)員必要求每個(gè)服務(wù)員必須連續(xù)工作八小時(shí)須連續(xù)工作八小時(shí),試建立需服務(wù)員試建立需服務(wù)員總?cè)藬?shù)最少的排班方案數(shù)學(xué)模型總?cè)藬?shù)最少的排班方案數(shù)學(xué)模型.班次班次123456時(shí)間時(shí)間2-6 6-10

11、10-1414-1818-2222-2人人48107124解：解：設(shè)各班次設(shè)各班次新增服務(wù)員數(shù)分別為新增服務(wù)員數(shù)分別為 x1,x2, x3, x4, x5, x6,則則 min z= x1+x2+ x3+x4+x5+x66112233445564,8,10,7,. .12,4,0,1 ,6.ixxxxxxxxs txxxxxi 且且xi為整數(shù)為整數(shù)連續(xù)投資問題連續(xù)投資問題某部門計(jì)劃某部門計(jì)劃5年內(nèi)用一百萬年內(nèi)用一百萬投資下列項(xiàng)目：投資下列項(xiàng)目：A：從第一年到第四年初可：從第一年到第四年初可投資，次年末回收本利投資，次年末回收本利115%B: 第三年初可投資，第五年第三年初可投資，第五年末回收本

12、利末回收本利125%，投資，投資額額40萬萬C:第二年初可投資，第五年第二年初可投資，第五年末回收本利末回收本利140%，投資，投資額額30萬萬D：每年初可購買公債，當(dāng)：每年初可購買公債，當(dāng)年末歸還，利息年末歸還，利息6%如何投資，五年后獲利最大？如何投資，五年后獲利最大？ 解：設(shè)第解：設(shè)第i年初投資項(xiàng)目年初投資項(xiàng)目A,B,C,D分別為分別為xiA , xiB , xiC , xiD 萬元萬元, i=1,2,3,4,5x1A+x1D=100,x2A+x2C+x2D=1.06 x1D ,x3A+x3B+x3D=1.06 x2D+1.15 x1A,x4A+x4D=1.06 x3D+1.15 x2A

13、,x5D=1.06 x4D+1.15 x3A,x2C 30, x3B 40,xiA , xiB , xiC , xiD0 ，i=1,2,3,4,5.Max Z= 1.15x4A +1.40 x2C +1.25x3B +1.06 x5Ds.t.二、線性規(guī)劃模型的求解二、線性規(guī)劃模型的求解（一）圖解法（一）圖解法（n 3時(shí)）時(shí)）（二）單純形法（二）單純形法max z= c x. .,0s tAXbX(LP) :,0DX AX b X可行解：滿足約束條件可行解：滿足約束條件AX=b ,X最優(yōu)解最優(yōu)解:可行解中使目標(biāo)最優(yōu)的可行解中使目標(biāo)最優(yōu)的. 即即X*D,且任意且任意XD, CX* CX可行集：所有

14、可行解的集合可行集：所有可行解的集合0的的X的值的值12 , ,Tnx xx制訂生產(chǎn)計(jì)劃制訂生產(chǎn)計(jì)劃, ,使每天獲利使每天獲利最大最大. . 工廠生產(chǎn)兩種產(chǎn)品工廠生產(chǎn)兩種產(chǎn)品A1,A2,已已知生產(chǎn)單位產(chǎn)品情況如下：知生產(chǎn)單位產(chǎn)品情況如下：設(shè)設(shè)生產(chǎn)生產(chǎn)A1、A2分別分別x1、x2公斤公斤 max z= 20 x1+30 x2 (1)1212121228,(2)4016,(3). .0412,(4)0,0.(5)xxxxs txxxx A1A2現(xiàn)有資源現(xiàn)有資源設(shè)備設(shè)備128臺(tái)時(shí)臺(tái)時(shí)甲甲4016公斤公斤乙乙0412 公斤公斤利潤利潤2030（元）（元）（一）圖解法（一）圖解法（n 3時(shí)）時(shí)）(1)在

15、平面上作出可行集在平面上作出可行集ABCD34z=140z=0由圖解法直觀得由圖解法直觀得:n=2時(shí)時(shí),(LP)的可行集是凸多邊形的可行集是凸多邊形,最優(yōu)解最優(yōu)解可以在其某個(gè)頂點(diǎn)處達(dá)到可以在其某個(gè)頂點(diǎn)處達(dá)到.線性規(guī)劃基本性質(zhì)線性規(guī)劃基本性質(zhì):(LP)的可行集是的可行集是凸多面體凸多面體,最優(yōu)解可以在凸多面體的最優(yōu)解可以在凸多面體的某個(gè)頂點(diǎn)處達(dá)到某個(gè)頂點(diǎn)處達(dá)到.線性規(guī)劃求解思路線性規(guī)劃求解思路:通過通過代數(shù)的方法描述代數(shù)的方法描述高維空間凸多高維空間凸多面體的面體的頂點(diǎn)頂點(diǎn),再使用再使用經(jīng)濟(jì)經(jīng)濟(jì)的方法來的方法來求出達(dá)到極值的頂點(diǎn)求出達(dá)到極值的頂點(diǎn).x1x20(2)在可行集中找最優(yōu)解在可行集中找最

16、優(yōu)解 max z= 20 x1+30 x2 (1)1212121228,(2)4016,(3). .0412,(4)0,0.(5)xxxxs txxxx z=60引入松弛變量引入松弛變量x3, x4, x5, 化為標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形:（二）單純形法（二）單純形法),(1000101020100015654321PPPPPA 系數(shù)矩陣為系數(shù)矩陣為 815060b顯然顯然A的秩的秩為為3, 任取任取3個(gè)線性無關(guān)的列向量個(gè)線性無關(guān)的列向量,如如P1 , P2 , P3稱為一稱為一組組基基, 記為記為B =(P1 , P2 , P3 ).P1 , P2 , P3 稱為稱為基基向向量量 , 基基向向量量對

17、應(yīng)對應(yīng)的變量的變量 x1 ,x2 ,x3稱為稱為基變量基變量, 其余列向量其余列向量 P4 , P5 稱為稱為非非基基向向量量 ,記為記為N= (P4 , P5 ). 非基對應(yīng)的變量非基對應(yīng)的變量 x4 ,x5 稱為稱為非基變量非基變量. A = (B, N), 相應(yīng)相應(yīng)X = (XB, XN) T, c = (cB, cN)AX= BXB + NXN = b , 則則 XB = B 1b B 1 NXN ,),(1000101020100015654321PPPPPA 系數(shù)矩陣為系數(shù)矩陣為 815060b令非基變量令非基變量XN = 0, 解得基變量解得基變量XB = B-1b, 稱稱(XB

18、, XN)為為基本解基本解.解的所有變量的值都非負(fù)解的所有變量的值都非負(fù), 則稱為則稱為基本可行解基本可行解,此時(shí)的基稱此時(shí)的基稱為為可行基可行基.基本可行解對應(yīng)的目標(biāo)值為基本可行解對應(yīng)的目標(biāo)值為f = cBB-1b . 若可行基進(jìn)一步滿足若可行基進(jìn)一步滿足: cN cBB-1N0, 則對一切可行解則對一切可行解X , 必有必有f(x) cBB-1b , 此時(shí)稱基可行解此時(shí)稱基可行解X = (B-1b, 0) T為為最優(yōu)解最優(yōu)解.另一個(gè)基另一個(gè)基本可行解本可行解定理：定理： (LP)的可行集的的可行集的頂點(diǎn)頂點(diǎn)與與 (LP)的的 基本可行解基本可行解一一對應(yīng)。一一對應(yīng)。單純形法基本思想：單純形

19、法基本思想：目標(biāo)目標(biāo)重復(fù)此重復(fù)此更優(yōu)更優(yōu)過程過程單純形法基本步驟：單純形法基本步驟：不是不是最優(yōu)解最優(yōu)解更優(yōu)更優(yōu)目標(biāo)目標(biāo)重復(fù)此重復(fù)此過程過程(LP)的某個(gè)的某個(gè)基本可行解基本可行解最優(yōu)解最優(yōu)解(LP)的的某個(gè)基某個(gè)基基基本本可可行解行解另一另一個(gè)基個(gè)基基本基本可行解可行解最優(yōu)解最優(yōu)解 即從可行域的即從可行域的(基本可行解基本可行解)開始開始, (另一個(gè)基本可行解另一個(gè)基本可行解)的迭代過程的迭代過程, 轉(zhuǎn)移的條件轉(zhuǎn)移的條件是是使使(逐步變優(yōu)逐步變優(yōu)), 當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí), 問題也就得問題也就得到了最優(yōu)解到了最優(yōu)解.頂點(diǎn)轉(zhuǎn)移的依據(jù)？頂點(diǎn)轉(zhuǎn)移的依據(jù)？ 根據(jù)根據(jù)線性規(guī)劃問

20、題的可行域是凸多邊形或凸多面體線性規(guī)劃問題的可行域是凸多邊形或凸多面體, 一個(gè)一個(gè)線性規(guī)劃問題有最優(yōu)解線性規(guī)劃問題有最優(yōu)解, 就一定可以在可行域的頂點(diǎn)上找到就一定可以在可行域的頂點(diǎn)上找到. 于是于是, 若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解, 這個(gè)最優(yōu)解這個(gè)最優(yōu)解所對應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn)所對應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn); 若該線性規(guī)劃有多個(gè)最若該線性規(guī)劃有多個(gè)最優(yōu)解優(yōu)解, 那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解.(1)頂點(diǎn)的逐步轉(zhuǎn)移頂點(diǎn)的逐步轉(zhuǎn)移 使目標(biāo)函數(shù)值得到改善使目標(biāo)函數(shù)值得到改善 得到得到LP最優(yōu)解

21、，目標(biāo)函數(shù)達(dá)到最優(yōu)值最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值 （單純形法的由來？（單純形法的由來？ ） 2需要解決的問題：需要解決的問題： (1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？ (2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)判斷標(biāo)準(zhǔn)是什么？判斷標(biāo)準(zhǔn)是什么？ 2.單純形法原理（用代數(shù)方法求解單純形法原理（用代數(shù)方法求解LP）123123123123max2333. .479,0zxxxxxxs txxxx xx 勞動(dòng)力勞動(dòng)力原材料原材料利潤利潤A112B143C173現(xiàn)有資源現(xiàn)有資源39勞動(dòng)力約束勞動(dòng)力約束原材料約束原材料約束第一步：引入非負(fù)的松弛變量第一步：引入非負(fù)的松

22、弛變量x4 , x5 , 將該將該LP化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型123451234123512345max233003. .479,0zxxxxxxxxxs txxxxx xxxx 第二步：尋求初始可行基，確定基變量第二步：尋求初始可行基，確定基變量1 1 1 1 01 4 7 0 1A 1001,54PPB對應(yīng)的基變量是對應(yīng)的基變量是 x4，x5； 第三步：寫出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值第三步：寫出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值兩個(gè)關(guān)鍵的基本表達(dá)式：兩個(gè)關(guān)鍵的基本表達(dá)式：用非基變量表示基變量的表達(dá)式用非基變量表示基變量的表達(dá)式41235123(0)3947(0,0,0,3,9)Txxxxx

23、xxxX 初初始始基基本本可可行行解解用非基變量表示目標(biāo)函數(shù)的表達(dá)式用非基變量表示目標(biāo)函數(shù)的表達(dá)式123233zxxx 0)0( Z當(dāng)當(dāng)前前的的目目標(biāo)標(biāo)函函數(shù)數(shù)值值請解釋結(jié)果的經(jīng)濟(jì)含義請解釋結(jié)果的經(jīng)濟(jì)含義 不生產(chǎn)任何產(chǎn)品不生產(chǎn)任何產(chǎn)品, 資源全部節(jié)余資源全部節(jié)余(x4=3，x5=9) , 三種產(chǎn)品的總利潤為三種產(chǎn)品的總利潤為0！第四步：分析兩個(gè)基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？第四步：分析兩個(gè)基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？ 分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式123233zxxx 非基變量前面的系數(shù)均為正數(shù)，所以任何一個(gè)非基變量進(jìn)基都非基變量前面的系

24、數(shù)均為正數(shù)，所以任何一個(gè)非基變量進(jìn)基都能使能使z值增加值增加通常把非基變量前面的系數(shù)叫通常把非基變量前面的系數(shù)叫“”； 選哪一個(gè)非基變量進(jìn)基？選哪一個(gè)非基變量進(jìn)基？ 選選x2為為進(jìn)基變量進(jìn)基變量（換入變量換入變量） 問題：能否選其他的非基變量進(jìn)基？問題：能否選其他的非基變量進(jìn)基？任意一個(gè)任意一個(gè) 任意一個(gè)正檢驗(yàn)數(shù)對應(yīng)的非基變量任意一個(gè)正檢驗(yàn)數(shù)對應(yīng)的非基變量 最大正檢驗(yàn)數(shù)對應(yīng)的非基變量最大正檢驗(yàn)數(shù)對應(yīng)的非基變量 排在排在最前面的正檢驗(yàn)數(shù)對應(yīng)的非基變量最前面的正檢驗(yàn)數(shù)對應(yīng)的非基變量 確定出基變量：確定出基變量：問題討論問題討論 x2進(jìn)基意味著其取值從進(jìn)基意味著其取值從0變成一個(gè)正數(shù)（經(jīng)濟(jì)意義變成一

25、個(gè)正數(shù)（經(jīng)濟(jì)意義生產(chǎn)生產(chǎn)B 產(chǎn)品），能否無限增大？產(chǎn)品），能否無限增大？當(dāng)當(dāng)x2增加時(shí)，增加時(shí)，x4，x5如何變化？如何變化？現(xiàn)在的非基變量是哪些？現(xiàn)在的非基變量是哪些？321532147493xxxxxxxx由由用非基變量表示基變量的表達(dá)式用非基變量表示基變量的表達(dá)式 當(dāng)當(dāng)x2增加時(shí)增加時(shí), x4 , x5會(huì)減小會(huì)減小,但有限度但有限度必須大于等于必須大于等于0, 以保以保持解的可行性！于是持解的可行性！于是24225223303 991min,9 4091 444xxxxxxx 當(dāng)當(dāng)x2的值從的值從0增加到增加到9/4時(shí)時(shí) , x5首先變?yōu)槭紫茸優(yōu)?，此時(shí)，此時(shí)x4=3/40 , 因此因此

26、選選x5為出基變量為出基變量(換出變量換出變量). 這種用來確定出基變量的規(guī)則稱為這種用來確定出基變量的規(guī)則稱為 如果如果P10，會(huì)出現(xiàn)什么問題？，會(huì)出現(xiàn)什么問題？最小比值原則會(huì)失效！最小比值原則會(huì)失效！新的基變量新的基變量x2 , x4；新的非基變量；新的非基變量x1 , x3 , x5 ；寫出寫出412351233947xxxxxxxx 由由213541359171444433314444xxxxxxxx X(1)=(0，9/4，0，3/4，0)T12311353135233917123()344442751234444Zxxxxxxxxxxx 可得相應(yīng)的目標(biāo)函數(shù)值為可得相應(yīng)的目標(biāo)函數(shù)值為

27、 z(1)=27/4檢驗(yàn)數(shù)仍有正的檢驗(yàn)數(shù)仍有正的, 返回返回進(jìn)行討論進(jìn)行討論. 當(dāng)當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式用非基變量表示目標(biāo)函數(shù)的表達(dá)式中中, 時(shí)時(shí), 當(dāng)前的基本可行解當(dāng)前的基本可行解就是就是! 為什么？為什么？分析分析: 用非基變量表示目標(biāo)函數(shù)的表達(dá)式用非基變量表示目標(biāo)函數(shù)的表達(dá)式, 如果如果讓負(fù)檢驗(yàn)數(shù)讓負(fù)檢驗(yàn)數(shù) 所對應(yīng)的變量進(jìn)基所對應(yīng)的變量進(jìn)基，目標(biāo)函數(shù)值將下降！目標(biāo)函數(shù)值將下降！ x1 x2 x3 x4 x52 3 3 0 0b XB1 1 1 1 01 4 7 0 13 x49 x52 3 3 0 0z123451234123512345max233003. .479, ,0z

28、xxxxxxxxxst xxxxx x x x x 把目標(biāo)函數(shù)表達(dá)式改寫成方程的形式，和原有的把目標(biāo)函數(shù)表達(dá)式改寫成方程的形式，和原有的m個(gè)約束個(gè)約束方程組成一個(gè)具有方程組成一個(gè)具有n+m+1個(gè)變量、個(gè)變量、m+1個(gè)方程的方程組：個(gè)方程的方程組：1111221112112222221122112211nnnnnnmmmnnn mmnnnnn mn ma xa xa xxba xa xa xxba xa xa xxbc xc xc xcxcxz 取出系數(shù)寫成增廣矩陣的形式：取出系數(shù)寫成增廣矩陣的形式： xn+1，xn+m所對應(yīng)的系數(shù)列向量構(gòu)成一個(gè)基所對應(yīng)的系數(shù)列向量構(gòu)成一個(gè)基. 11121121

29、2222121212100010001nnmmmnmnnnn maaabaaabaaabccccccz 1212nnnn mxxxxxxb 用矩陣的初等行變換將目標(biāo)函數(shù)中基變量系數(shù)化為零用矩陣的初等行變換將目標(biāo)函數(shù)中基變量系數(shù)化為零,這時(shí)這時(shí) 變成變成0，相應(yīng)的增廣矩陣變成如下形式：，相應(yīng)的增廣矩陣變成如下形式：12,nnnmccc 1mjjn iijicca 01mn iiizcb 其中，其中， j=1，2，n ； 111211212222120121000 100 010 00nnmmmnmnaaabaaabaaabzz 增廣矩陣的最后一行就是用非基變量表示目標(biāo)函數(shù)的表增廣矩陣的最后一行就

30、是用非基變量表示目標(biāo)函數(shù)的表達(dá)式達(dá)式 , j ( j=1, 2 , , n）就是非基變量的檢驗(yàn)數(shù)）就是非基變量的檢驗(yàn)數(shù).（3）檢驗(yàn)數(shù)的兩種計(jì)算方法：）檢驗(yàn)數(shù)的兩種計(jì)算方法：利用矩陣的行變換，把目標(biāo)函數(shù)表達(dá)式中基變量前面的系利用矩陣的行變換，把目標(biāo)函數(shù)表達(dá)式中基變量前面的系 數(shù)變?yōu)閿?shù)變?yōu)?； 使用計(jì)算公式使用計(jì)算公式 1,1,2, .mjjn iijjBjjjicc acC Pczjn 2. 例例1的表格單純形法計(jì)算過程：的表格單純形法計(jì)算過程： x1 x2 x3 x4 x5 2 3 3 0 0z1 1 1 1 03 x41 4 7 0 1 9 x5 2 3 3 0 0z3/4 0 -3/4 1

31、 -1/43/4 x41/4 1 7/4 0 1/49/4 x25/4 0 9/4 0 -3/4z-27/4 1 0 -1 4/3 -1/3 1 x1 0 1 2 -1/3 1/3 2 x2 0 0 -1 -5/3 -1/3z-8*表格單純形法求解步驟表格單純形法求解步驟第一步：第一步：將將LPLP化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型， 引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變量引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變量, 使約束條件使約束條件化為等式化為等式, 第二步：第二步：最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)是是結(jié)束結(jié)束, 寫出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值寫出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值;檢查相應(yīng)系數(shù)列檢查相應(yīng)系數(shù)列 0？ 是是結(jié)束結(jié)束,

32、該該LP無無“有限最優(yōu)解有限最優(yōu)解”！，轉(zhuǎn)入下一步，轉(zhuǎn)入下一步基變換基變換. 確定是停止迭代還是轉(zhuǎn)入基變換？確定是停止迭代還是轉(zhuǎn)入基變換？ 選擇選擇(最大最大)對應(yīng)的系數(shù)列為對應(yīng)的系數(shù)列為, 主元列對主元列對應(yīng)的非基變量為應(yīng)的非基變量為 最小比值對應(yīng)的行為最小比值對應(yīng)的行為, 主元行主元行對應(yīng)的基變量為對應(yīng)的基變量為.第三步：第三步：基變換基變換確定進(jìn)基變量和出基變量確定進(jìn)基變量和出基變量. .第四步第四步 換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算) )利用矩陣的利用矩陣的把把, , 從而得到一張新的單從而得到一張新的單純形表純形表, 返回第二步返回第二步.完成一次迭代，得到新的基

33、本可行解和相應(yīng)的目標(biāo)函數(shù)值完成一次迭代，得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值.該迭代過程直至下列情況之一發(fā)生時(shí)停止該迭代過程直至下列情況之一發(fā)生時(shí)停止檢驗(yàn)數(shù)行全部變?yōu)榉钦?；檢驗(yàn)數(shù)行全部變?yōu)榉钦担唬ǖ玫阶顑?yōu)解）（得到最優(yōu)解）或或主元列主元列 0 （最優(yōu)解無界）（最優(yōu)解無界） 停止迭代的標(biāo)志（停機(jī)準(zhǔn)則）停止迭代的標(biāo)志（停機(jī)準(zhǔn)則）自來水輸送與貨機(jī)裝運(yùn)自來水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大；怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大；運(yùn)輸問題運(yùn)輸問題各種類型的貨物裝箱，由于受體積、重量等限制，各

34、種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少如何搭配裝載，使獲利最高，或裝箱數(shù)量最少.三、線性規(guī)劃建模實(shí)例三、線性規(guī)劃建模實(shí)例其他費(fèi)用其他費(fèi)用: :450元元/千噸千噸 應(yīng)如何分配水庫供水量，公司才能獲利最多？應(yīng)如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費(fèi)引水管理費(fèi)例例1 自來水輸送自來水輸送收入：收入：900元元/千噸千噸 支出支出A：50B：60C：5

35、0甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：?。?0；40水庫供水量水庫供水量(千噸千噸)小區(qū)基本用水量小區(qū)基本用水量(千噸千噸)小區(qū)額外用水量小區(qū)額外用水量(千噸千噸)（以天計(jì)）（以天計(jì)）總供水量：總供水量：160確定送水方案確定送水方案使利潤最大使利潤最大問題問題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：?。?0；40 總需求量總需求量(300)每個(gè)水庫最大供水量都提高一倍每個(gè)水庫最大供水量都提高一倍利潤利潤 = 收入收入(900) 其它費(fèi)用其它費(fèi)用( (450) 引水管理費(fèi)引水管理費(fèi)利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁

36、A290320230280B310320260300C260250220/1112131421222324313233290320230280310320260300260250220Max zxxxxxxxxxxx 供應(yīng)供應(yīng)限制限制B, C 類似處理類似處理11121314:50Axxxx11121314100 xxxx 問題討論問題討論 確定送水方案確定送水方案使利潤最大使利潤最大需求約束可以不變需求約束可以不變?nèi)绾稳绾窝b運(yùn)，裝運(yùn)，使本次飛行使本次飛行獲利最大？獲利最大？ 例例2 貨機(jī)裝運(yùn)貨機(jī)裝運(yùn) 重量（噸）重量（噸）空間空間( 米米3/噸）噸）利潤（元利潤（元/噸）噸）貨物貨物11848

37、03100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大三個(gè)貨艙中實(shí)際載重必須與其最大載載重成比例重成比例 前倉：前倉：10；6800中倉：中倉：16；8700后倉：后倉：8；5300飛機(jī)平衡飛機(jī)平衡三個(gè)貨艙三個(gè)貨艙最大最大載載重重( (噸噸),),最大容積最大容積( (米米3 3) ) 決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量( (噸）噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉分別代表前、中、后倉)模型假設(shè)模型假設(shè) 每種貨物可以分割到任意小；每種貨物可以分割

38、到任意?。回洐C(jī)裝運(yùn)貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標(biāo)目標(biāo)函數(shù)函數(shù)( (利潤利潤)約束約束條件條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 貨艙貨艙

39、重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx貨物貨物供應(yīng)供應(yīng) 18131211xxx15232221xxx23333231xxx12434241xxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量第二部分第二部分 整數(shù)規(guī)劃建模方

40、法整數(shù)規(guī)劃建模方法一、整數(shù)規(guī)劃簡介一、整數(shù)規(guī)劃簡介二、二、整數(shù)整數(shù)規(guī)劃的規(guī)劃的分分支定界法支定界法三、三、整數(shù)整數(shù)規(guī)劃的建模實(shí)例規(guī)劃的建模實(shí)例2.1 整數(shù)規(guī)劃簡介整數(shù)規(guī)劃簡介要求所有要求所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃的解為整數(shù)，稱為純整數(shù)規(guī)劃要求部分要求部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃的解為整數(shù)，稱為混合整數(shù)規(guī)劃對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解11max

41、(min)( )( , ),1,2,. .0,1,2,njjjnijjijjf xc xa xbims txjn 且且 整整且為整數(shù)且為整數(shù)2.2 整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法3.求解分枝的松弛問題求解分枝的松弛問題 定界過程定界過程設(shè)兩個(gè)分枝的松弛問題分別為問題設(shè)兩個(gè)分枝的松弛問題分別為問題 1 和問題和問題 2 , 它們的最它們的最優(yōu)解有如下情況優(yōu)解有如下情況: 2.2.1 思路與解題步驟思路與解題步驟只解松弛問題只解松弛問題1. 在全部可行性域上解松弛問題在全部可行性域上解松弛問題若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最

42、優(yōu)解2. 分枝過程分枝過程若松弛問題最優(yōu)解中某個(gè)若松弛問題最優(yōu)解中某個(gè) xk=bk 不是整數(shù)，令不是整數(shù)，令 bk為為 bk 的整數(shù)的整數(shù)部分部分: 構(gòu)造兩個(gè)新的約束條件構(gòu)造兩個(gè)新的約束條件 xk bk 和和 xk bk +1，分別加，分別加于原松弛問題，形成兩個(gè)新的整數(shù)規(guī)劃于原松弛問題，形成兩個(gè)新的整數(shù)規(guī)劃.表表2.2.1 分枝問題解可能出現(xiàn)的情況分枝問題解可能出現(xiàn)的情況情況情況 2, 4, 5 找到最優(yōu)解找到最優(yōu)解情況情況 3 在縮減的域上繼續(xù)分枝定界法在縮減的域上繼續(xù)分枝定界法情況情況 6 問題問題 1 的整數(shù)解作為的整數(shù)解作為界界被保留，用于以后與問題被保留，用于以后與問題 2 的后的

43、后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況 4 或或 5序號序號問題問題1問題問題2說明說明1無可行解無可行解無可行解無可行解整數(shù)規(guī)劃無可行解整數(shù)規(guī)劃無可行解2無可行解無可行解整數(shù)解整數(shù)解此整數(shù)解即為最優(yōu)解此整數(shù)解即為最優(yōu)解3無可行解無可行解非整數(shù)解非整數(shù)解對問題對問題2繼續(xù)分枝繼續(xù)分枝4整數(shù)解整數(shù)解整數(shù)解整數(shù)解較優(yōu)的一個(gè)為最優(yōu)解較優(yōu)的一個(gè)為最優(yōu)解5整數(shù)解整數(shù)解,目標(biāo)函數(shù)目標(biāo)函數(shù)值優(yōu)于值優(yōu)于2非整數(shù)解非整數(shù)解問題問題1的解即為最優(yōu)解（剪枝）的解即為最優(yōu)解（剪枝）6整數(shù)解整數(shù)解非整數(shù)解非整數(shù)解,目標(biāo)目標(biāo)函數(shù)值優(yōu)于函數(shù)值優(yōu)于1問題問題1停止分枝，其整數(shù)解為界，停止分

44、枝，其整數(shù)解為界，對問題對問題2繼續(xù)分枝繼續(xù)分枝 2.2.2 分枝定界法舉例分枝定界法舉例 例例2.1.1 且為整數(shù)且為整數(shù) 0,7 2134246)(max21212121xxxxxxxxxf解：解：松弛問題的最優(yōu)解為松弛問題的最優(yōu)解為 x1=2.5, x2=2, OBJ=23 由由 x1=2.5 得到兩個(gè)分枝如下：得到兩個(gè)分枝如下：且為整數(shù)且為整數(shù)問題問題 0,2 7 21342I46)(max211212121xxxxxxxxxxf且為整數(shù)且為整數(shù)問題問題 0,3 7 21342II46)(max211212121xxxxxxxxxxf 表表2.2.3 分枝問題的松弛解分枝問題的松弛解問

45、題問題II的解即原整數(shù)問題的最優(yōu)解的解即原整數(shù)問題的最優(yōu)解 可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過程繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過程. 當(dāng)存在很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情當(dāng)存在很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解況下相當(dāng)于組合所有可能的整數(shù)解. 一般整數(shù)規(guī)劃問題屬于一類未解決的難題，一般整數(shù)規(guī)劃問題屬于一類未解決的難題，NP-complete，只有少數(shù)特殊問題有好的算法，如只有少數(shù)特殊問題有好的算法，如任務(wù)分配問題、匹配問

46、題任務(wù)分配問題、匹配問題.例例.某廠擬用集裝箱托運(yùn)某廠擬用集裝箱托運(yùn)甲甲,乙兩種貨物。已知乙兩種貨物。已知貨物貨物體積體積(米米3/箱箱)重量重量(噸噸/箱箱)利潤利潤(百元百元/箱箱)甲甲9740乙乙72090托運(yùn)托運(yùn)限制限制5670問：如何安排利潤最大？問：如何安排利潤最大？設(shè)甲乙分別托運(yùn)設(shè)甲乙分別托運(yùn)x1, x2箱箱模型建立模型建立 12max4090(1)zxx IP(1)-(4)稱為與稱為與(IP)相相對應(yīng)的線性規(guī)劃對應(yīng)的線性規(guī)劃(LP)求解求解(LP)得得 x1=4.81, x2 =1.82, z=356121212129756(2)72070(3). .,0(4),(5)xxxx

47、s txxxx 為整數(shù)為整數(shù)分枝定界法分枝定界法(branch and bound method)(IP) x1*, x2* , z *(LP)x1=4.81,x2=1.82, z0=356(LP1) x1=4,x2=2.1, z0=349X14X15(LP2) x1=5,x2=1.57, z0=341(z * 349定界定界)(LP3) x1=4,x2=2, z0=340X22X23(LP4) x2=3,x1=1.42,z0=327(z *340 定界定界)(LP5) x2=1,x1=5.44,z0=308X21(LP6) 無無可行解可行解X22x14x15分枝：分枝：應(yīng)如何安排原油的采購和

48、加工應(yīng)如何安排原油的采購和加工 ？ 例例2 原油采購與加工原油采購與加工 市場上可買到不超過市場上可買到不超過1500噸的原油噸的原油A： 購買量不超過購買量不超過500噸時(shí)的單價(jià)為噸時(shí)的單價(jià)為10000元元/ /噸；噸； 購買量超過購買量超過500噸但不超過噸但不超過1000噸時(shí)，超過噸時(shí)，超過500噸的噸的 部分部分8000元元/ /噸；噸； 購買量超過購買量超過1000噸時(shí)，超過噸時(shí)，超過1000噸的部分噸的部分6000元元/ /噸噸. .售價(jià)售價(jià)4800元元/噸噸 售價(jià)售價(jià)5600元元/噸噸庫存庫存500噸噸 庫存庫存1000噸噸 汽油甲汽油甲(A 50%) 原油原油A 原油原油B 汽

49、油乙汽油乙 (A 60%) 2.3整數(shù)整數(shù)規(guī)劃的建模實(shí)例規(guī)劃的建模實(shí)例決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù)問題問題分析分析 利潤：銷售汽油的收入利潤：銷售汽油的收入 購買原油購買原油A的支出的支出 難點(diǎn)：原油難點(diǎn)：原油A的購價(jià)與購買量的關(guān)系較復(fù)雜的購價(jià)與購買量的關(guān)系較復(fù)雜)()(6 . 5)( 8 . 422122111xcxxxxzMax甲甲(A 50%) A B 乙乙(A 60%) 購買購買xx11x12x21x224.8千元千元/噸噸 5.6千元千元/噸噸原油原油A的購買量的購買量, ,原油原油A, B生產(chǎn)生產(chǎn)汽油汽油甲甲,乙的數(shù)量乙的數(shù)量c(x) 購買原油購買原油A的支出的支出利潤利潤(

50、千元千元)c(x)如何表述？如何表述？原油供應(yīng)原油供應(yīng) 約束約束條件條件xxx500121110002221 xx1500 x10 (0500)8 1000 (5001000)63000 (10001500)( )xxc xxxxx x 500噸單價(jià)為噸單價(jià)為10千千元元/ /噸；噸； 500噸噸 x 1000噸，超過噸，超過500噸的噸的8千千元元/ /噸；噸；1000噸噸 x 1500噸，超過噸，超過1000噸的噸的6千千元元/ /噸。噸。 目標(biāo)目標(biāo)函數(shù)函數(shù)購買購買x A B x11x12x21x22庫存庫存500噸噸 庫存庫存1000噸噸 目標(biāo)函數(shù)中目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線

51、性規(guī)劃；不是線性函數(shù)，是非線性規(guī)劃； 對于用分段函數(shù)定義的對于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟，一般的非線性規(guī)劃軟件也難以輸入和求解；件也難以輸入和求解； 想辦法將模型化簡，用現(xiàn)成的軟件求解想辦法將模型化簡，用現(xiàn)成的軟件求解. .汽油含原油汽油含原油A的比例限制的比例限制 5 . 0211111 xxx6 . 0221212 xxx2111xx 221232xx 約束約束條件條件甲甲(A 50%) A B 乙乙(A 60%) x11x12x21x221. 整數(shù)變量整數(shù)變量2. 特殊約束處理特殊約束處理3. 背包問題背包問題4. 集合覆蓋問題集合覆蓋問題5. 固定費(fèi)用問題固定費(fèi)用問題

52、1. 整數(shù)變量整數(shù)變量表示不可分割的數(shù)量表示不可分割的數(shù)量表示決策變量表示決策變量 ( 0 1 整數(shù)變量整數(shù)變量) 1表示決策表示決策 j 為為“是是” xj = 0表示決策表示決策 j 為為“否否”表示決策之間的邏輯關(guān)系，如決策表示決策之間的邏輯關(guān)系，如決策 i 必須以決策必須以決策 j 的結(jié)果為前提：的結(jié)果為前提：xi xj 或或 xi = xj 描述互斥的選擇，從多種方案中選一個(gè)方案：描述互斥的選擇，從多種方案中選一個(gè)方案： j xj = 1 某公司有某公司有600萬元資金用于投資，有萬元資金用于投資，有5個(gè)項(xiàng)目列入投個(gè)項(xiàng)目列入投資計(jì)劃，各項(xiàng)目投資額和期望收益見下表：資計(jì)劃，各項(xiàng)目投資額

53、和期望收益見下表： 項(xiàng)目項(xiàng)目 投資額投資額(萬元萬元) 投資收益投資收益(萬元萬元)121015023002103100 604130 805260180由于技術(shù)原因，投資受到以下約束由于技術(shù)原因，投資受到以下約束: 在項(xiàng)目在項(xiàng)目1, 2 和和3中必須且只能有一項(xiàng)被選中中必須且只能有一項(xiàng)被選中; 項(xiàng)目項(xiàng)目3和和4最多只能被選中一項(xiàng)最多只能被選中一項(xiàng); 項(xiàng)目項(xiàng)目5被選中的前提是項(xiàng)目被選中的前提是項(xiàng)目1被選中被選中;問如何選擇最好的投資方案問如何選擇最好的投資方案, 使投資收益最大使投資收益最大.解：解：令令 xi 為為 0-1 決策變量決策變量 , 模型為模型為:max z = 150 x1+2

54、10 x2+60 x3+80 x4+160 x5 s.t. 210 x1+300 x2+100 x3+130 x4+260 x5 600 x1 + x2 + x3 = 1 x3 + x4 1 x5 x1 xi = 1 或或 0 , i =1 , . , 5(1) 矛盾約束：矛盾約束：同時(shí)出現(xiàn)的矛盾約束同時(shí)出現(xiàn)的矛盾約束f (x) 5 0 或或 f (x) 0 引入一個(gè)引入一個(gè)01變量變量 y 來處理：來處理： f (x)+5 M(1 y) 和和 f (x) M y y = 1 f (x) 5 0 和和 f (x) M y = 0 f (x) 5 M 和和 f (x) 0 2. 特殊約束處理特殊

55、約束處理(2) 絕對值約束絕對值約束: f (x) a ( a 0 )約束可寫為：約束可寫為：f (x) a 或或 f (x) a引入引入0 1變量變量y后，約束可改寫為：后，約束可改寫為： f (x) + a M(1 y) 和和 f (x) + a My y = 1 f(x) + a 0 和和 f(x)+a M y = 0 f(x) + a M 和和 f (x)+ a 0 (3) 多中選一的約束多中選一的約束在下列在下列 n 個(gè)約束中，只能有一個(gè)約束有效個(gè)約束中，只能有一個(gè)約束有效:fi (x) 0i = 1, 2, , n引入引入 n 個(gè)個(gè)0 1變量變量 yi , i = 1, 2, ,

56、n , 約束可寫為：約束可寫為：fi (x) M(1 yi) i = 1, 2, , ny1 + y2 + + yn = 1 序序號號1234567物物品品食食品品氧氧氣氣冰冰鎬鎬繩繩索索帳帳篷篷照照相相器器材材通通訊訊設(shè)設(shè)備備重重量量55261224重重要要系系數(shù)數(shù)2015181484103. 背包問題背包問題一登山隊(duì)員做登山準(zhǔn)備，需要攜帶的物品有：食一登山隊(duì)員做登山準(zhǔn)備，需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相機(jī)和通訊設(shè)備。品、氧氣、冰鎬、繩索、帳篷、照相機(jī)和通訊設(shè)備。每種物品的重要性系數(shù)和重量見下表：每種物品的重要性系數(shù)和重量見下表：要求背包重量不能超過要求背包重量不能超過2

57、5公斤，求重要性系數(shù)最大公斤，求重要性系數(shù)最大的攜帶物品方案的攜帶物品方案.令令xi 為是否攜帶物品為是否攜帶物品 i 的決策變量：的決策變量： maxz = 20 x1+15x2+18x3+14x4+8x5+4x6+10 x7 s.t. 5x1+ 5x2+ 2x3+ 6x4+12x5+2x6+ 4x7 25xi = 1或或0， i =1, 2, ., 7 背包問題的一般形式為：背包問題的一般形式為： max z = c1x1+c2 x2+cnxn s.t. a1x1+a2x2+anxn b x1, x2, , xn 0對一維背包問題，對一維背包問題，上例使用的啟發(fā)式算法是很上例使用的啟發(fā)式算

58、法是很有效的：只要比較有效的：只要比較 ci /ai的比值，依次令有最大的的比值，依次令有最大的比值的決策變量為比值的決策變量為1，直到資源，直到資源 b 用盡為止。該算用盡為止。該算法當(dāng)法當(dāng) n 較大，且較大，且 ai b 時(shí)更為準(zhǔn)確時(shí)更為準(zhǔn)確.4. 集合覆蓋問題集合覆蓋問題 有集合有集合 S = 1, 2, . , m 被一系列被一系列 S的子集的子集 i S ，i = 1, 2, . , n 覆蓋，并要求使用的子集最少覆蓋，并要求使用的子集最少.例例: 有集合有集合S=1, 2, 3, 4, 5, 子集子集 1=1, 2, 2=1, 3, 5, 3=2, 4, 5, 4=1, 5 =4,

59、 5, 求最小的覆蓋子集。求最小的覆蓋子集。解解 一個(gè)可能的覆蓋為一個(gè)可能的覆蓋為 1, 2, 3, 另一個(gè)另一個(gè) 為為 2, 3; 該該問題可以用一個(gè)整數(shù)規(guī)劃來求解：問題可以用一個(gè)整數(shù)規(guī)劃來求解：令令xi為是否使用集合為是否使用集合 i 的決策變量的決策變量Min z = x1 + x2 + x3 + x4 + x5s.t. x1 + x2 + x4 1 x1 + x3 1 x2 1 x3 + x5 1 x2 + x3 + x5 1 xi = 0 或或 1 , i =1 , . , 5地地區(qū)區(qū)12345610101628272021002432171031624012272142832120

60、1525527172715014620102125140例例某城市有某城市有6個(gè)區(qū)個(gè)區(qū), 規(guī)劃建消防站規(guī)劃建消防站, 任何區(qū)發(fā)生任何區(qū)發(fā)生火警時(shí)消防車要在火警時(shí)消防車要在15分鐘內(nèi)趕到分鐘內(nèi)趕到, 各區(qū)間消防車行各區(qū)間消防車行駛的時(shí)間見下表駛的時(shí)間見下表, 求設(shè)置消防站最少的方案求設(shè)置消防站最少的方案.設(shè)設(shè) xj 為在為在 j 地區(qū)設(shè)置消防站的決策地區(qū)設(shè)置消防站的決策( j = 1 , 2 , , 6) 整數(shù)規(guī)劃問題為：整數(shù)規(guī)劃問題為：min z = x1 + x2 + x3 + x4 + x5 + x6 s.t. x1 + x2 1 x1 + x2 + x6 1 x3 + x4 1 x3 +