資源描述：
《運籌與決策之4整數(shù)規(guī)劃（46).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、11緒論—Introduction2線性規(guī)劃—LinearProgramming3運輸與指派問題—TransportationModels4整數(shù)規(guī)劃—IntegerProgramming5網(wǎng)絡(luò)模型—NetworkModels6項目計劃—PERT&CPM7排隊論—QueueingModels8模擬—Simulation9決策分析—DecisionTheory10多目標決策—Multi-objectiveDecision《管理數(shù)量方法》目錄2授課內(nèi)容Case:分銷系統(tǒng)設(shè)計（P192）整數(shù)規(guī)劃圖解法及分枝定界法MS6.0軟件求解整數(shù)規(guī)劃應(yīng)用舉例銀行選址P209（
2、講義：消防站選址）案例討論：課本出版P2223Questions整數(shù)規(guī)劃IP與線性規(guī)劃LP有何不同？整數(shù)規(guī)劃的分類？整數(shù)規(guī)劃的求解方法？分枝定界法的基本思路？分枝問題解可能出現(xiàn)的情況？4Q1：整數(shù)規(guī)劃與線性規(guī)劃LP區(qū)別： （要求所有xj的解為整數(shù)，或者要求部分xj的解為整數(shù)）1）一般整數(shù)規(guī)劃。要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃；或者要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃。2）0-1整數(shù)規(guī)劃。它規(guī)定整數(shù)變量只能有兩個值，0或1。5Q2：整數(shù)規(guī)劃的解法圖解法窮舉法分枝定界法(BranchandMethod)割平面法6Q3：分枝定界法的基本思路maxZ=C
3、XAX=bX?0(A)maxZ=CXAX=bX?0X為整數(shù)(B)(B)為(A)的線性規(guī)劃松弛問題。7(C)(D)(B)Xj?i+1(B)Xj?iX*最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，則對(B)每次分兩枝,每枝多一個約束條件8Q4：分枝問題解可能出現(xiàn)的情況如何回答？9表分枝問題解可能出現(xiàn)的情況情況2,4,5找到最優(yōu)解情況3在縮減的域上繼續(xù)分枝定界法情況6問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝的整數(shù)解進行比較，結(jié)論如情況4。結(jié)果101緒論—Introduction2線性規(guī)劃—LinearProgramming3運輸問題—Tr
4、ansportationModels4整數(shù)規(guī)劃—IntegerProgramming5網(wǎng)絡(luò)模型—NetworkModels6項目計劃—PERT&CPM7排隊論—QueueingModels8模擬—Simulation9決策分析—DecisionTheory10多目標決策—Multi-objectiveDecision《管理數(shù)量方法》目錄11授課內(nèi)容整數(shù)規(guī)劃圖解法及分枝定界法MS6.0軟件求解整數(shù)規(guī)劃應(yīng)用舉例銀行選址P230（講義：消防站選址）案例討論：課本出版P24212整數(shù)規(guī)劃舉例產(chǎn)品桌椅備用資源木工1230油漆工3260搬運工0224利潤4050例1、
5、家具廠生產(chǎn)計劃問題桌，椅各生產(chǎn)多少,可獲最大利潤?13圖解法求最優(yōu)解解：X*=(15,7.5)Zmax=975該解是否符合實際要求？0203010102030X1X2DABCDABCC點：X1+2X2=303X1+2X2=60如何求解整數(shù)解？144整數(shù)規(guī)劃整數(shù)規(guī)劃的難度遠大于一般線性規(guī)劃15整數(shù)規(guī)劃簡介要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個的，最優(yōu)解不一定發(fā)生在極點整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解16整數(shù)規(guī)劃的解法圖解法窮舉法分枝定界法割平面法1
6、7§4.1整數(shù)規(guī)劃的窮舉法窮舉法：可以通過計算和比較所有整數(shù)格點的值來求解。18例：maxZ=40x1+60x2+70x3+160x416x1+35x2+45x3+85x4?100x1,x2,x3,x4為0,1X1=1X1=0111010101X2=0X3=00解法1：枚舉法：x1=1,x2=1,x3=1,x4=0。枚舉法？192100個整數(shù)解，用最現(xiàn)代化的計算機也要算上幾億億年。窮舉法是無法用來求解實際問題。最優(yōu)解經(jīng)過四舍五入的方法是否可以？若該整數(shù)規(guī)劃問題有100個0－1整數(shù)變量，那么整數(shù)解有多少個？如何回答？20§4.2分枝定界法的基本思路maxZ=
7、CXAX=bX?0(A)maxZ=CXAX=bX?0X為整數(shù)(B)(B)為(A)的線性規(guī)劃松弛問題。21(C)(D)(B)Xj?i+1(B)Xj?iX*最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，則對(B)每次分兩枝,每枝多一個約束條件22分枝定界法的步驟思路:暫不考慮整數(shù)條件,用單純形法求解,得整數(shù)解,停;不是整數(shù)解,分枝。分枝:每次分兩枝,每枝多一個約束條件，（每個節(jié)點代表一個子問題）。停止分枝條件:1）子問題無可行解.2）子問題得整數(shù)解.3）子問題的目標值比下界差。maxZ定界:1）初始整數(shù)規(guī)劃的松弛問題的最優(yōu)值是上界.2）子問題得整數(shù)解的
8、最優(yōu)值是一個下界。23分枝問題解可能出現(xiàn)的情況如何回答？24表分枝
