運(yùn)籌與決策之4整數(shù)規(guī)劃

1、11緒論緒論 Introduction2線性規(guī)劃線性規(guī)劃 Linear Programming3運(yùn)輸與指派問題運(yùn)輸與指派問題Transportation Models 4整數(shù)規(guī)劃整數(shù)規(guī)劃 Integer Programming5網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Models6項目計劃項目計劃 PERT & CPM7排隊論排隊論 Queueing Models8 模擬模擬 Simulation 9決策分析決策分析 Decision Theory10多目標(biāo)決策多目標(biāo)決策 Multi-objective Decision2Case:分銷系統(tǒng)設(shè)計分銷系統(tǒng)設(shè)計整數(shù)規(guī)劃整數(shù)規(guī)劃銀行選址銀行選址 P

2、209（講義：消防站選址講義：消防站選址）案例討論：課本出版案例討論：課本出版P22231.整數(shù)規(guī)劃整數(shù)規(guī)劃IP與線性規(guī)劃與線性規(guī)劃LP有何有何不同不同？整數(shù)規(guī)劃的分類？整數(shù)規(guī)劃的分類？2.整數(shù)規(guī)劃的求解方法？整數(shù)規(guī)劃的求解方法？3.分枝定界法的基本思路？分枝定界法的基本思路？4.分枝問題解可能出現(xiàn)的情況？分枝問題解可能出現(xiàn)的情況？41）一般整數(shù)規(guī)劃。要求所有）一般整數(shù)規(guī)劃。要求所有 xj 的解為整數(shù)，的解為整數(shù)，稱為純整數(shù)規(guī)劃；或者要求部分稱為純整數(shù)規(guī)劃；或者要求部分 xj 的解為整的解為整數(shù)，稱為混合整數(shù)規(guī)劃。數(shù)，稱為混合整數(shù)規(guī)劃。2）0-1整數(shù)規(guī)劃。它規(guī)定整數(shù)變量只能有兩個整數(shù)規(guī)劃。它規(guī)

3、定整數(shù)變量只能有兩個值，值，0或或1。njxmibxatsxcxfjnjijijnjjj, 2 , 1,0, 2 , 1,),(. .)(max(min)11且為整數(shù)5v圖解法圖解法v窮舉法窮舉法v分枝定界法分枝定界法(Branch and Method) v割平面法割平面法6分枝定界法的基本思路分枝定界法的基本思路max Z=CXAX=bX 0(A)max Z =CXAX=bX 0X為整數(shù)為整數(shù) (B)(B)為為 (A) 的的松弛問題。松弛問題。7(C)(D)(B)Xj i+1(B)Xj iX*最優(yōu)解最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，最優(yōu)解為非整數(shù)解，則對則對(B)每次分

4、兩枝每次分兩枝, 每枝多一個約束條件每枝多一個約束條件8如何回答？如何回答？9序序號號 問問題題 1 1 問問題題 2 2 說說 明明 1 無無可可行行解解 無無可可行行解解 整整數(shù)數(shù)規(guī)規(guī)劃劃無無可可行行解解 2 無無可可行行解解 整整數(shù)數(shù)解解 此此整整數(shù)數(shù)解解即即最最優(yōu)優(yōu)解解 3 無無可可行行解解 非非整整數(shù)數(shù)解解 對對問問題題 2 繼繼續(xù)續(xù)分分枝枝 4 整整數(shù)數(shù)解解 整整數(shù)數(shù)解解 較較優(yōu)優(yōu)的的一一個個為為最最優(yōu)優(yōu)解解 5 整整數(shù)數(shù)解解，目目標(biāo)標(biāo)函函數(shù)數(shù)優(yōu)優(yōu)于于問問題題 2 非非整整數(shù)數(shù)解解 問問題題 1 的的解解即即最最優(yōu)優(yōu)解解 6 整整數(shù)數(shù)解解 非非整整數(shù)數(shù)解解，目目標(biāo)標(biāo)函函數(shù)數(shù)優(yōu)優(yōu)于于

5、問問題題 1 問問題題 1 1 停停止止分分枝枝( (剪剪枝枝) )，其其整整數(shù)數(shù)解解為為界界，對對問問題題 2 繼繼續(xù)續(xù)分分枝枝 情況情況 2, 4, 5 找到最優(yōu)解找到最優(yōu)解情況情況 3 在縮減的域上繼續(xù)分枝定界法在縮減的域上繼續(xù)分枝定界法情況情況 6 問題問題 1 的整數(shù)解作為的整數(shù)解作為界界被保留，用于以后與問被保留，用于以后與問題題 2 的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況 4。結(jié)果結(jié)果101緒論緒論 Introduction2線性規(guī)劃線性規(guī)劃 Linear Programming3運(yùn)輸問題運(yùn)輸問題 Transportation Models

6、4整數(shù)規(guī)劃整數(shù)規(guī)劃 Integer Programming5網(wǎng)絡(luò)模型網(wǎng)絡(luò)模型 Network Models6項目計劃項目計劃 PERT & CPM7排隊論排隊論 Queueing Models8 模擬模擬 Simulation 9決策分析決策分析 Decision Theory10多目標(biāo)決策多目標(biāo)決策 Multi-objective Decision11整數(shù)規(guī)劃整數(shù)規(guī)劃銀行選址銀行選址 P230（講義：消防站選址講義：消防站選址）案例討論：課本出版案例討論：課本出版P24212 產(chǎn)品產(chǎn)品 桌桌 椅椅 備用資源備用資源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬運(yùn)工搬運(yùn)工 0

7、 2 24 利潤利潤 40 50例例1、家具廠生產(chǎn)計劃問題、家具廠生產(chǎn)計劃問題桌桌，椅各生產(chǎn)多少椅各生產(chǎn)多少, 可獲最大利潤可獲最大利潤?13圖解法求最優(yōu)解圖解法求最優(yōu)解解：解：X* = (15,7.5) Zmax =975該解是否符合實際該解是否符合實際要求？要求？0203010102030X1X2DABCDABCC點：點： X1+2X2 =30 3X1+2X2 =60如何求解整數(shù)解？如何求解整數(shù)解？14 整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃15要求所有要求所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃的解為整數(shù)，稱為純整數(shù)規(guī)劃要求部分要求部分 xj 的解為整數(shù)，稱為混合

8、整數(shù)規(guī)劃的解為整數(shù)，稱為混合整數(shù)規(guī)劃對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個的，最優(yōu)解不一定發(fā)生在極點整數(shù)規(guī)劃的解是可數(shù)個的，最優(yōu)解不一定發(fā)生在極點整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解njxmibxatsxcxfjnjijijnjjj, 2 , 1,0, 2 , 1,),(. .)(max(min)11且為整數(shù)16v圖解法圖解法v窮舉法窮舉法v分枝定界法分枝定界法v割平面法割平面法174.1窮舉法窮舉法njxmibxatsxcxfjnjijijnjjj, 2 , 1,0, 2 , 1

9、,),(. .)(max(min)11且為整數(shù)窮舉法：可以通過計算和比較所有整窮舉法：可以通過計算和比較所有整數(shù)格點的值來求解。數(shù)格點的值來求解。18例：例：maxZ = 40 x1+60 x2 +70 x3 + 160 x416x1 + 35x2+45x3+85x4 100 x1 , x2 , x3 , x4為為 0 ,1 X1 =1X1 =0111 01 01 01X2 =0X3 =00解法解法1：枚舉法：枚舉法：x1=1 , x2=1 , x3=1 , x4=0 。枚舉法？枚舉法？19v2100個整數(shù)解，用最現(xiàn)代化的計算機(jī)也要算個整數(shù)解，用最現(xiàn)代化的計算機(jī)也要算上幾億億年。上幾億億年。v

10、窮舉法是無法用來求解實際問題。窮舉法是無法用來求解實際問題。v最優(yōu)解經(jīng)過四舍五入的方法是否可以？最優(yōu)解經(jīng)過四舍五入的方法是否可以？如何回答？如何回答？204.2 分枝定界法的基本思路分枝定界法的基本思路max Z=CXAX=bX 0(A)max Z =CXAX=bX 0X為整數(shù)為整數(shù) (B)(B)為為 (A) 的的松弛問題。松弛問題。21(C)(D)(B)Xj i+1(B)Xj iX*最優(yōu)解最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，最優(yōu)解為非整數(shù)解，則對則對(B)每次分兩枝每次分兩枝, 每枝多一個約束條件每枝多一個約束條件22v思路思路: 暫不考慮整數(shù)條件暫不考慮整數(shù)條件,用單純形

11、法求解用單純形法求解,得整數(shù)得整數(shù)解解,停停;不是整數(shù)解不是整數(shù)解,分枝。分枝。v分枝分枝: 每次分兩枝每次分兩枝, 每枝多一個約束條件，每枝多一個約束條件，（每個（每個節(jié)點代表一個子問題）節(jié)點代表一個子問題）。v停止分枝條件停止分枝條件: 1） 子問題無可行解子問題無可行解. 2 ）子問題）子問題得整數(shù)解得整數(shù)解. 3 ）子問題的目標(biāo)值比下界差。）子問題的目標(biāo)值比下界差。vmax Z定界定界: v1 ）初始整數(shù)規(guī)劃的松弛問題的最優(yōu)值是上界）初始整數(shù)規(guī)劃的松弛問題的最優(yōu)值是上界. v2 ）子問題得整數(shù)解的最優(yōu)值是一個下界。）子問題得整數(shù)解的最優(yōu)值是一個下界。23序號序號 問題問題 1 1 問題

12、問題 2 2 說說 明明 1 無可行解無可行解 無可行解無可行解 整數(shù)規(guī)劃整數(shù)規(guī)劃解解如何如何？ 2 無可行解無可行解 整數(shù)解整數(shù)解 3 無可行解無可行解 非整數(shù)解非整數(shù)解 4 整數(shù)解整數(shù)解 整數(shù)解整數(shù)解 5 整數(shù)解，目標(biāo)函整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題數(shù)優(yōu)于問題 2 非整數(shù)解非整數(shù)解 6 整數(shù)解整數(shù)解 非整數(shù)解，目標(biāo)非整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題函數(shù)優(yōu)于問題 1 如何回答？如何回答？24序序號號 問問題題 1 1 問問題題 2 2 說說 明明 1 無無可可行行解解 無無可可行行解解 整整數(shù)數(shù)規(guī)規(guī)劃劃無無可可行行解解 2 無無可可行行解解 整整數(shù)數(shù)解解 此此整整數(shù)數(shù)解解即即最最優(yōu)優(yōu)解解 3 無無可可行行

13、解解 非非整整數(shù)數(shù)解解 對對問問題題 2 繼繼續(xù)續(xù)分分枝枝 4 整整數(shù)數(shù)解解 整整數(shù)數(shù)解解 較較優(yōu)優(yōu)的的一一個個為為最最優(yōu)優(yōu)解解 5 整整數(shù)數(shù)解解，目目標(biāo)標(biāo)函函數(shù)數(shù)優(yōu)優(yōu)于于問問題題 2 非非整整數(shù)數(shù)解解 問問題題 1 的的解解即即最最優(yōu)優(yōu)解解 6 整整數(shù)數(shù)解解 非非整整數(shù)數(shù)解解，目目標(biāo)標(biāo)函函數(shù)數(shù)優(yōu)優(yōu)于于問問題題 1 問問題題 1 1 停停止止分分枝枝( (剪剪枝枝) )，其其整整數(shù)數(shù)解解為為界界，對對問問題題 2 繼繼續(xù)續(xù)分分枝枝 情況情況 2, 4, 5 找到最優(yōu)解找到最優(yōu)解情況情況 3 在縮減的域上繼續(xù)分枝定界法在縮減的域上繼續(xù)分枝定界法情況情況 6 問題問題 1 的整數(shù)解作為的整數(shù)解作為

14、界界被保留，用于以后與問被保留，用于以后與問題題 2 的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況 4。結(jié)果結(jié)果25舉例舉例例：例：max Z = x1+ x2 6x1 + 2x2 175x1 + 9x2 44x1 , x2 為為 整數(shù)整數(shù) 如何回答？如何回答？26 松弛問題松弛問題Z0=5.545X1=1.477X2=4.068子問題子問題1Z1=5.333X1=1X2=4.333子問題子問題2Z2=4.5X1=2X2=2.5子問題子問題3Z3=5X1=1X2=4子問題子問題4無可行解無可行解x12x11x24x25求解過程求解過程 最優(yōu)整數(shù)解最優(yōu)整數(shù)解X1=

15、 1X2= 4最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值Z = 527v決策變量取值決策變量取值0或或1，稱，稱0-1或二進(jìn)制變量或二進(jìn)制變量 。v0-1變量可數(shù)量化地描述諸如開與關(guān)、取與變量可數(shù)量化地描述諸如開與關(guān)、取與棄、有與無等現(xiàn)象所反映的離散變量間的棄、有與無等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互斥的約束條件邏輯關(guān)系、順序關(guān)系以及互斥的約束條件 v0-1規(guī)劃應(yīng)用：如規(guī)劃應(yīng)用：如工廠選址工廠選址 、生產(chǎn)計劃安排、生產(chǎn)計劃安排、旅行購物、背包問題、人員安排、旅行購物、背包問題、人員安排、代碼、代碼選取、線路設(shè)計選取、線路設(shè)計 、可靠性等、可靠性等281.Xj= 未選中方案選中方案jj.0.1

16、njjx11njjx133.從從N個方案中最多選中個方案中最多選中3個個:2.從從N個方案中必須選中一個個方案中必須選中一個: 291. 只有方案只有方案J選中時，方案選中時，方案I才可能被選才可能被選中中: 如何表示？如何表示？ xixj2. 方案方案I與方案與方案J是否選中是同時的是否選中是同時的: xi=xj3. 矛盾約束矛盾約束: f(x) -50 與與f(x) 0 - f(x) +5 M(1-y)與與 f(x) MyM表示很大的數(shù)表示很大的數(shù)，y為為01變量。變量。 如何回答？如何回答？304.多個選一多個選一:fi(x) 0, I=1,2,n.如何表示？如何表示？ 5.邏輯關(guān)系約束

17、：邏輯關(guān)系約束：若若f(x)無限制無限制, 則則g(x) 0;若若f(x)0不成立不成立, 則則g(x)無限制無限制. 如何表示？如何表示？ fi(x) M (1-yi) I=1,2,n. y1+y2+yn=1f(x) -M(1-y), g(x) My，M表示很大的數(shù)表示很大的數(shù)， y為為01變量。變量。318.3.1 資金預(yù)算（投資決策）問題資金預(yù)算（投資決策）問題8.3. 2 固定成本問題固定成本問題8.3. 3 配送系統(tǒng)設(shè)計配送系統(tǒng)設(shè)計8.3. 4 銀行選址（覆蓋問題）銀行選址（覆蓋問題）8.3. 5 產(chǎn)品設(shè)計與市場份額優(yōu)化產(chǎn)品設(shè)計與市場份額優(yōu)化32例例 華美公司有華美公司有5個項目被列

18、入投資計劃，各項目個項目被列入投資計劃，各項目的投資額和期望的投資收益見下表：該公司的投資額和期望的投資收益見下表：該公司只有只有600萬元資金可用于投資，由于技術(shù)上的萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：原因，投資受到以下約束： 1.在項目在項目1、2和和3中必須（只）有一項被選中；中必須（只）有一項被選中； 2.項目項目3和和4只能選中一項；（必須選一項）只能選中一項；（必須選一項） 3.項目項目5被選中的前提是項目被選中的前提是項目1必須被選中。必須被選中。 如何在上述條件下選擇一個最好的投資方如何在上述條件下選擇一個最好的投資方案，使投資收益最大。案，使投資收益最大。

19、33項目項目 投資額（萬元）投資額（萬元） 投資收益（萬元）投資收益（萬元） 1 210 150 2 300 210 3 100 60 4 130 80 5 260 180Xj = 1表項目表項目j選中選中, Xj=0表項目表項目j未選中未選中. j=1,2,3,4,5. 約束條件如何表示？約束條件如何表示？34解解: Xj=1表項目表項目j選中選中, Xj=0表項目表項目j未選中未選中. j=1,2,3,4,5. Z表示總收益表示總收益. 則模型如下則模型如下: Max Z =150X1+210X2+60X3+80X4+180X5 s.t: 210X1+300X2+100X3+130X4+2

20、60X5 600X1+X2+X3=1 X3+X4=1 X5 X1Xj=0或1; j =1,2,3,4,5.35解決某市解決某市消防站的布點問題消防站的布點問題。該城市共有該城市共有6個區(qū)，個區(qū)，每個都可以建消防站。每個都可以建消防站。市政府希望建設(shè)的消防站最市政府希望建設(shè)的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在車要在15分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛的時間見下表：請幫助該市制定一個最消防車行駛的時間見下表：請幫助該市制定一個最節(jié)省的計劃。節(jié)省的計劃。 消防車在各區(qū)行駛距離表消防車

21、在各區(qū)行駛距離表 地區(qū)地區(qū)1 地區(qū)地區(qū)2 地區(qū)地區(qū)3 地區(qū)地區(qū)4 地區(qū)地區(qū)5 地區(qū)地區(qū)6地區(qū)地區(qū)1地區(qū)地區(qū)2地區(qū)地區(qū)3地區(qū)地區(qū)4地區(qū)地區(qū)5地區(qū)地區(qū)6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0How to solve？36解解: Xj=1表地區(qū)設(shè)消防站表地區(qū)設(shè)消防站, Xj=0表地區(qū)不設(shè)消防站表地區(qū)不設(shè)消防站. Z=消防站總數(shù)消防站總數(shù), 則模型如下則模型如下: Min Z=X1+X2+X3+X4+X5+X6 s.t. X1+X21 X

22、1+X2+X61 X3+X41X3+X4+X5 1X4+X5+X6 1X2+X5+X6 1Xj=0或或1；j =1,2,3,4,5,6.37l俄亥俄信托公司（俄亥俄信托公司（Ohio Trust Company）希望）希望在俄亥俄西北部在俄亥俄西北部20個縣進(jìn)行選址，該地區(qū)還沒個縣進(jìn)行選址，該地區(qū)還沒有首席業(yè)務(wù)處（有首席業(yè)務(wù)處（Principal Place of business PPB）。根據(jù)俄亥俄州的銀行法，如果金融企）。根據(jù)俄亥俄州的銀行法，如果金融企業(yè)在任何一個縣設(shè)立業(yè)在任何一個縣設(shè)立PPB，就可以在該縣及其，就可以在該縣及其比鄰的縣設(shè)立分支機(jī)構(gòu)。比鄰的縣設(shè)立分支機(jī)構(gòu)。俄亥俄信托公司

23、想知俄亥俄信托公司想知道在那些縣設(shè)立道在那些縣設(shè)立PPB會使其數(shù)量最少？會使其數(shù)量最少？38考慮的縣考慮的縣鄰縣的數(shù)字代號鄰縣的數(shù)字代號考慮的縣考慮的縣鄰縣的數(shù)字代號鄰縣的數(shù)字代號12，12，16118，10，13，14，15，18，19，2021，3，12121，2，3，10，13，1632，4，9，10，12，13133，10，11，12，15，1643，5，7，91411，15，2054，6，71511，13，14，1665，7，17161，12，13，1574，5，6，8，9，17，18176，7，1887，9，10，11，18187，8，11，17，1993，4，7，8，101911

24、，18，20103，8，9，11，12，132011，14，193940紅光服裝廠可生產(chǎn)三種服裝：西服、襯衫和紅光服裝廠可生產(chǎn)三種服裝：西服、襯衫和羽絨服。生產(chǎn)不同種類的服裝要使用不同的設(shè)備，羽絨服。生產(chǎn)不同種類的服裝要使用不同的設(shè)備，紅光服裝廠可從專業(yè)租賃公司租用這些設(shè)備。設(shè)紅光服裝廠可從專業(yè)租賃公司租用這些設(shè)備。設(shè)備租金和其他經(jīng)濟(jì)參數(shù)見下表：假定市場需求不備租金和其他經(jīng)濟(jì)參數(shù)見下表：假定市場需求不成問題，服裝廠每月可用工人工時為成問題，服裝廠每月可用工人工時為2000小時，小時，該廠如何安排生產(chǎn)可使每月的利潤最大？該廠如何安排生產(chǎn)可使每月的利潤最大？ 41序序號號服裝服裝種類種類設(shè)備設(shè)備租金租金元元生 產(chǎn)生 產(chǎn)成本成本元元/件件銷