1、運籌學理論與建模運籌學理論與建模河北聯合大學理學院河北聯合大學理學院肖繼先肖繼先主要內容主要內容第一部分第一部分 線性規劃建模方法線性規劃建模方法第二部分第二部分 整數規劃建模方法整數規劃建模方法第三部分第三部分 指派問題指派問題第四部分第四部分 動態規劃建模動態規劃建模第五部分第五部分 圖論與網絡優化圖論與網絡優化第一部分第一部分 線性規劃建模方法線性規劃建模方法一、從現實問題到線性規劃模型一、從現實問題到線性規劃模型二、線性規劃模型的求解二、線性規劃模型的求解三、線性規劃建模實例三、線性規劃建模實例例例1 加工奶制品的生產計劃加工奶制品的生產計劃1桶桶牛奶牛奶 3公斤公斤A1 12小時小時

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

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

4、加加性性 連續性連續性 xi對目標函數的對目標函數的“貢獻貢獻”與與xi取值取值成正比成正比 xi對約束條件的對約束條件的“貢獻貢獻”與與xi取值取值成正比成正比 xi對目標函數的對目標函數的“貢獻貢獻”與與xj取值取值無關無關 xi對約束條件的對約束條件的“貢獻貢獻”與與xj取值取值無關無關 xi取值連續取值連續 A1,A2每公斤的獲利是與各每公斤的獲利是與各自產量無關的常數自產量無關的常數每桶牛奶加工出每桶牛奶加工出A1,A2的數量和的數量和時間是與各自產量無關的常數時間是與各自產量無關的常數A1,A2每公斤的獲利是與相每公斤的獲利是與相互產量無關的常數互產量無關的常數每桶牛奶加工出每桶牛

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

6、)0,0.(5)xxxxs txxxx目標函數目標函數約約束束條條件件決策變量決策變量一、從現實問題到線性規劃模型一、從現實問題到線性規劃模型線性規劃模型標準型線性規劃模型標準型:maxz= c1 x1 +c2x2 +cnxn11112211211222221122,. .,0,1,.nnnnmmmnnmiaxaxaxbaxaxaxbs taxaxaxbxin (LP)線性規劃模型標準型矩陣表示：線性規劃模型標準型矩陣表示：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 線性規劃模型一般形式：線性規劃模型一般形式：1.線性規劃的一般形化為標準型的一般步驟線性規劃的一般形化為標準型的一般步驟(1) Min f = cX 轉化為轉化為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) 若存在可正可負變量若存在可正可負變量xi 令令12,iiixxx 12,0.iixx 例例 將下述線性規劃問題化為標準型將下述線性規劃問題化為標準型1231231231237,2,.325,0,xxxxxxs txxxx xx min z = x1 +2x2 3x3無約束無約束標準型標準型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米的某型號圓米的某型號圓鋼，現需要長度為鋼，現需要長度為2.5米的米的毛坯毛坯100根，長度為根，長度為1.3米米的毛坯的毛坯200根，如何選者下根，如何選者下料方式，所需總用料最省料方式，所需總用料最省? 解：可能的下料方式：解：可能的下料方式：2.51.3130222314406設按第設按第i種下料方式的種下料方式的圓鋼圓鋼xi根，根，i=1,2,3,4 min z= x1+x2 +x3 +x4 12323432100,. . 246200,0,1,2,3,4.ixxxs t

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

11、10-1414-1818-2222-2人人48107124解：解：設各班次設各班次新增服務員數分別為新增服務員數分別為 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為整數為整數連續投資問題連續投資問題某部門計劃某部門計劃5年內用一百萬年內用一百萬投資下列項目：投資下列項目：A：從第一年到第四年初可：從第一年到第四年初可投資，次年末回收本利投資，次年末回收本利115%B: 第三年初可投資，第五年第三年初可投資，第五年末回收本

12、利末回收本利125%，投資，投資額額40萬萬C:第二年初可投資，第五年第二年初可投資，第五年末回收本利末回收本利140%，投資，投資額額30萬萬D：每年初可購買公債，當：每年初可購買公債，當年末歸還，利息年末歸還，利息6%如何投資，五年后獲利最大？如何投資，五年后獲利最大？ 解：設第解：設第i年初投資項目年初投資項目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.二、線性規劃模型的求解二、線性規劃模型的求解（一）圖解法（一）圖解法（n 3時）時）（二）單純形法（二）單純形法max z= c x. .,0s tAXbX(LP) :,0DX AX b X可行解：滿足約束條件可行解：滿足約束條件AX=b ,X最優解最優解:可行解中使目標最優的可行解中使目標最優的. 即即X*D,且任意且任意XD, CX* CX可行集：所有

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

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

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

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

18、, XN)為為基本解基本解.解的所有變量的值都非負解的所有變量的值都非負, 則稱為則稱為基本可行解基本可行解,此時的基稱此時的基稱為為可行基可行基.基本可行解對應的目標值為基本可行解對應的目標值為f = cBB-1b . 若可行基進一步滿足若可行基進一步滿足: cN cBB-1N0, 則對一切可行解則對一切可行解X , 必有必有f(x) cBB-1b , 此時稱基可行解此時稱基可行解X = (B-1b, 0) T為為最優解最優解.另一個基另一個基本可行解本可行解定理：定理： (LP)的可行集的的可行集的頂點頂點與與 (LP)的的 基本可行解基本可行解一一對應。一一對應。單純形法基本思想：單純形

19、法基本思想：目標目標重復此重復此更優更優過程過程單純形法基本步驟：單純形法基本步驟：不是不是最優解最優解更優更優目標目標重復此重復此過程過程(LP)的某個的某個基本可行解基本可行解最優解最優解(LP)的的某個基某個基基基本本可可行解行解另一另一個基個基基本基本可行解可行解最優解最優解 即從可行域的即從可行域的(基本可行解基本可行解)開始開始, (另一個基本可行解另一個基本可行解)的迭代過程的迭代過程, 轉移的條件轉移的條件是是使使(逐步變優逐步變優), 當目標函數達到最優值時當目標函數達到最優值時, 問題也就得問題也就得到了最優解到了最優解.頂點轉移的依據？頂點轉移的依據？ 根據根據線性規劃問

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

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

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

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

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

25、個正數（經濟意義生產生產B 產品），能否無限增大？產品），能否無限增大？當當x2增加時，增加時，x4，x5如何變化？如何變化？現在的非基變量是哪些？現在的非基變量是哪些？321532147493xxxxxxxx由由用非基變量表示基變量的表達式用非基變量表示基變量的表達式 當當x2增加時增加時, x4 , x5會減小會減小,但有限度但有限度必須大于等于必須大于等于0, 以保以保持解的可行性！于是持解的可行性！于是24225223303 991min,9 4091 444xxxxxxx 當當x2的值從的值從0增加到增加到9/4時時 , x5首先變為首先變為0，此時，此時x4=3/40 , 因此因此

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

27、 z(1)=27/4檢驗數仍有正的檢驗數仍有正的, 返回返回進行討論進行討論. 當當用非基變量表示目標函數的表達式用非基變量表示目標函數的表達式中中, 時時, 當前的基本可行解當前的基本可行解就是就是! 為什么？為什么？分析分析: 用非基變量表示目標函數的表達式用非基變量表示目標函數的表達式, 如果如果讓負檢驗數讓負檢驗數 所對應的變量進基所對應的變量進基，目標函數值將下降！目標函數值將下降！ 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 把目標函數表達式改寫成方程的形式，和原有的把目標函數表達式改寫成方程的形式，和原有的m個約束個約束方程組成一個具有方程組成一個具有n+m+1個變量、個變量、m+1個方程的方程組：個方程的方程組：1111221112112222221122112211nnnnnnmmmnnn mmnnnnn mn ma xa xa xxba xa xa xxba xa xa xxbc xc xc xcxcxz 取出系數寫成增廣矩陣的形式：取出系數寫成增廣矩陣的形式： xn+1，xn+m所對應的系數列向量構成一個基所對應的系數列向量構成一個基. 11121121

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

30、是用非基變量表示目標函數的表達式達式 , j ( j=1, 2 , , n）就是非基變量的檢驗數）就是非基變量的檢驗數.（3）檢驗數的兩種計算方法：）檢驗數的兩種計算方法：利用矩陣的行變換，把目標函數表達式中基變量前面的系利用矩陣的行變換，把目標函數表達式中基變量前面的系 數變為數變為0； 使用計算公式使用計算公式 1,1,2, .mjjn iijjBjjjicc acC Pczjn 2. 例例1的表格單純形法計算過程：的表格單純形法計算過程： 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化為標準型化為標準型， 引入適當的松馳變量、剩余變量和人工變量引入適當的松馳變量、剩余變量和人工變量, 使約束條件使約束條件化為等式化為等式, 第二步：第二步：最優性檢驗最優性檢驗是是結束結束, 寫出最優解和目標函數最優值寫出最優解和目標函數最優值;檢查相應系數列檢查相應系數列 0？ 是是結束結束,

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

33、本可行解和相應的目標函數值完成一次迭代，得到新的基本可行解和相應的目標函數值.該迭代過程直至下列情況之一發生時停止該迭代過程直至下列情況之一發生時停止檢驗數行全部變為非正值；檢驗數行全部變為非正值；（得到最優解）（得到最優解）或或主元列主元列 0 （最優解無界）（最優解無界） 停止迭代的標志（停機準則）停止迭代的標志（停機準則）自來水輸送與貨機裝運自來水輸送與貨機裝運生產、生活物資從若干供應點運送到一些需求點，生產、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大；怎樣安排輸送方案使運費最小，或利潤最大；運輸問題運輸問題各種類型的貨物裝箱，由于受體積、重量等限制，各

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

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

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

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

38、到任意小；貨機裝運貨機裝運每種貨物可以在一個或多個貨艙中任意分布；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標目標函數函數( (利潤利潤)約束約束條件條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx貨機裝運貨機裝運模型建立模型建立 貨艙貨艙

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

40、法整數規劃建模方法一、整數規劃簡介一、整數規劃簡介二、二、整數整數規劃的規劃的分分支定界法支定界法三、三、整數整數規劃的建模實例規劃的建模實例2.1 整數規劃簡介整數規劃簡介要求所有要求所有 xj 的解為整數，稱為純整數規劃的解為整數，稱為純整數規劃要求部分要求部分 xj 的解為整數，稱為混合整數規劃的解為整數，稱為混合整數規劃對應沒有整數解要求的線性規劃稱之為松弛問題對應沒有整數解要求的線性規劃稱之為松弛問題整數規劃的解是可數個的，最優解不一定發生在極點整數規劃的解是可數個的，最優解不一定發生在極點整數規劃的最優解不會優于其松弛問題的最優解整數規劃的最優解不會優于其松弛問題的最優解11max

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

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

43、后續分枝所得到的解進行比較，結論如情況續分枝所得到的解進行比較，結論如情況 4 或或 5序號序號問題問題1問題問題2說明說明1無可行解無可行解無可行解無可行解整數規劃無可行解整數規劃無可行解2無可行解無可行解整數解整數解此整數解即為最優解此整數解即為最優解3無可行解無可行解非整數解非整數解對問題對問題2繼續分枝繼續分枝4整數解整數解整數解整數解較優的一個為最優解較優的一個為最優解5整數解整數解,目標函數目標函數值優于值優于2非整數解非整數解問題問題1的解即為最優解（剪枝）的解即為最優解（剪枝）6整數解整數解非整數解非整數解,目標目標函數值優于函數值優于1問題問題1停止分枝，其整數解為界，停止分

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

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

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

47、s txxxx 為整數為整數分枝定界法分枝定界法(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分枝：分枝：應如何安排原油的采購和

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

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

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

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

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

53、和期望收益見下表： 項目項目 投資額投資額(萬元萬元) 投資收益投資收益(萬元萬元)121015023002103100 604130 805260180由于技術原因，投資受到以下約束由于技術原因，投資受到以下約束: 在項目在項目1, 2 和和3中必須且只能有一項被選中中必須且只能有一項被選中; 項目項目3和和4最多只能被選中一項最多只能被選中一項; 項目項目5被選中的前提是項目被選中的前提是項目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) 矛盾約束：矛盾約束：同時出現的矛盾約束同時出現的矛盾約束f (x) 5 0 或或 f (x) 0 引入一個引入一個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 個約束中，只能有一個約束有效個約束中，只能有一個約束有效:fi (x) 0i = 1, 2, , n引入引入 n 個個0 1變量變量 yi , i = 1, 2, ,

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

57、5公斤，求重要性系數最大公斤，求重要性系數最大的攜帶物品方案的攜帶物品方案.令令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對一維背包問題，對一維背包問題，上例使用的啟發式算法是很上例使用的啟發式算

58、法是很有效的：只要比較有效的：只要比較 ci /ai的比值，依次令有最大的的比值，依次令有最大的比值的決策變量為比值的決策變量為1，直到資源，直到資源 b 用盡為止。該算用盡為止。該算法當法當 n 較大，且較大，且 ai b 時更為準確時更為準確.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, 求最小的覆蓋子集。求最小的覆蓋子集。解解 一個可能的覆蓋為一個可能的覆蓋為 1, 2, 3, 另一個另一個 為為 2, 3; 該該問題可以用一個整數規劃來求解：問題可以用一個整數規劃來求解：令令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地地區區12345610101628272021002432171031624012272142832120

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