版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
(一)、基本思路
考慮純整數(shù)問(wèn)題:整數(shù)問(wèn)題的松弛問(wèn)題:第三節(jié)分枝定界法(一)、基本思路考慮純整數(shù)問(wèn)題:整數(shù)問(wèn)題的松弛問(wèn)考慮純整數(shù)問(wèn)題:整數(shù)問(wèn)題的松弛問(wèn)題:判斷題:整數(shù)問(wèn)題的最優(yōu)函數(shù)值總是小于或等于其松弛問(wèn)題的最優(yōu)函數(shù)值??紤]純整數(shù)問(wèn)題:整數(shù)問(wèn)題的松弛問(wèn)題:判斷題:整數(shù)問(wèn)題的最優(yōu)函例一:用分枝定界法求解整數(shù)規(guī)劃問(wèn)題(用圖解法計(jì)算)記為(IP)(二)、例題
例一:用分枝定界法求解整數(shù)規(guī)劃問(wèn)題(用圖解法計(jì)算)記為(IPLP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.5LP21x1=12/5,x2=3Z(21)
=17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)
=17LP212x1=3,x2=5/2Z(212)
=15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3####LP1LPLP2LP21LP22LP211LP212x1≤1例一:用分枝定界法求解整數(shù)規(guī)劃問(wèn)題(用圖解法計(jì)算)記為(IP)解:首先去掉整數(shù)約束,變成一般線性規(guī)劃問(wèn)題記為(LP)例一:用分枝定界法求解整數(shù)規(guī)劃問(wèn)題(用圖解法計(jì)算)記為(IP用圖解法求(LP)的最優(yōu)解,如圖所示。x1x2⑴⑵33⑶用圖解法求(LP)的最優(yōu)解,如圖所示。x1x2⑴⑵33⑶x1x2⑴⑵33(18/11,40/11)⑶x1=18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是(IP)最大值的上限。x1x2⑴⑵33(18/11,40/11)⑶x1LPx1=18/11,x2=40/11Z(0)
=19.8LPx1x2⑴⑵33(18/11,40/11)⑶對(duì)于x1=18/11≈1.64,取值x1≤1,x1≥2對(duì)于x2=40/11≈3.64,
取值x2
≤3,x2
≥4x1=18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是(IP)最大值的上限。先將(LP)劃分為(LP1)和(LP2),取x1≤1,x1≥2x1x2⑴⑵33(18/11,40/11)⑶對(duì)于x1=18/
現(xiàn)在只要求出(LP1)和(LP2)的最優(yōu)解即可。先將(LP)劃分為(LP1)和(LP2),取x1≤1,x1≥2,有下式:現(xiàn)在只要求出(LP1)和(LP2)的最優(yōu)解即可。先將(LLP1x1=?,x2=?Z(1)
=?LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=?,x2=?Z(2)
=?x1≤1x1≥2LP1LPLP2x1≤1x1≥2x1x2⑴⑵33⑶
先求(LP1),如圖所示。11Ax1x2⑴⑵33⑶先求(LP1),如圖所示。11Ax1x2⑴⑵33⑶
先求(LP1),如圖所示。11BA此時(shí)B
在點(diǎn)取得最優(yōu)解。x1=1,x2=3,Z(1)=16x1x2⑴⑵33⑶先求(LP1),如圖所示。11BA此時(shí)BLP1x1=?,x2=?Z(1)
=?LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=?,x2=?Z(2)
=?x1≤1x1≥2LP1LPLP2x1≤1x1≥2LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=?,x2=?Z(2)
=?x1≤1x1≥2LP1LPLP2x1≤1x1≥2x1x2⑴⑵33⑶11BA求(LP2)
,如圖所示。x1x2⑴⑵33⑶11BA求(LP2),如圖所示。x1x2⑴⑵33⑶11在C
點(diǎn)取得最優(yōu)解。即x1=2,x2=10/3,Z(2)
=56/3≈18.7BAC求(LP2)
,如圖所示。x1x2⑴⑵33⑶11在C點(diǎn)取得最優(yōu)解。BAC求(LP2)LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=?,x2=?Z(2)
=?x1≤1x1≥2LP1LPLP2x1≤1x1≥2LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.7x1≤1x1≥2找到整數(shù)解,
此枝停止計(jì)算LP1LPLP2x1≤1x1≥2找到整數(shù)解,
此枝停止計(jì)算在C
點(diǎn)取得最優(yōu)解。即x1=2,x2=10/3,Z(2)
=56/3≈18.7x1x2⑴⑵33⑶11BAC求(LP2)
,如圖所示。
∵Z2>Z1=16∴原問(wèn)題可能有比(16)更大的最優(yōu)解,
但x2不是整數(shù),故利用x2≤3,x2≥4
加入條件。在C點(diǎn)取得最優(yōu)解。x1x2⑴⑵33⑶11BAC求(LP2)(LP)劃分為(LP1)和(LP2),x1≤1,x1≥2(LP)劃分為(LP1)和(LP2),x1≤1,x1≥對(duì)于LP2,加入條件:x2≤3,x2≥4有下式:只要求出(LP21)和(LP22)的最優(yōu)解即可。對(duì)于LP2,加入條件:x2≤3,x2≥4有下式:x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.7LP21x1=?,x2=?Z(21)
=?LP22x1=?,x2=?Z(22)
=?找到整數(shù)解,
此枝停止計(jì)算x1≤1x1≥2x2≥4x2≤3LP1LPLP2LP21LPx1x2⑴⑵33⑶11BAC先求(LP21),如圖所示。x1x2⑴⑵33⑶11BAC先求(LP21),如圖所示。x1x2⑴⑵33⑶11BAC先求(LP21),如圖所示。D此時(shí)D在點(diǎn)取得最優(yōu)解。即x1=12/5=2.4,x2=3,Z(21)=87/5=17.4x1x2⑴⑵33⑶11BAC先求(LP21),如圖所示。D此x1x2⑴⑵33⑶11BACD求(LP22),如圖所示。無(wú)可行解,不再分枝。x1x2⑴⑵33⑶11BACD求(LP22),如圖所示。x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.7LP21x1=?,x2=?Z(21)
=?LP22x1=?,x2=?Z(22)
=?找到整數(shù)解,
此枝停止計(jì)算x1≤1x1≥2x2≥4x2≤3LP1LPLP2LP21LPx1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.7LP21x1=2.4,x2=3Z(21)
=17.4LP22無(wú)可行解找到整數(shù)解,
此枝停止計(jì)算x1≤1x1≥2x2≥4x2≤3LP1LPLP2LP21LPx1x2⑴⑵33⑶11BAC(LP21),如圖所示,
在D點(diǎn)取得最優(yōu)解。即x1=12/5=2.4,x2=3,Z(3)=87/5=17.4Dx1=2.4不是整數(shù),可繼續(xù)分枝。即x1≤2,
x1≥3x1x2⑴⑵33⑶11BAC(LP21),如圖所示,在D點(diǎn)運(yùn)籌學(xué)-分支定界法ppt課件在(LP21)的基礎(chǔ)上繼續(xù)分枝。加入條件x1≤2,
x1≥3有下式:只要求出(LP211)和(LP212)的最優(yōu)解即可。在(LP21)的基礎(chǔ)上繼續(xù)分枝。加入條件x1≤2,x1≥x1≤2LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.5LP21x1=2.4,x2=3Z(21)
=17.4LP22無(wú)可行解LP211x1=?,x2=?Z(211)
=?LP212x1=?,x2=?Z(212)
=?x1≤1x1≥2x2≤3x2≥4x1≥3#找到整數(shù)解,
此枝停止計(jì)算x1≤2LP1LPLP2LP21LP22LP211LP212先求(LP211)x1⑴⑵33⑶11BACDx2先求(LP211)x1⑴⑵33⑶11BACDx2先求(LP211)x1⑴⑵33⑶11BACDEx2如圖所示,此時(shí)E
在點(diǎn)取得最優(yōu)解即x1=2,x2=3,Z(211)=17先求(LP211)x1⑴⑵33⑶11BACDEx2如圖所示,x1x2⑴⑵33⑶11BACDE求(LP212)x1x2⑴⑵33⑶11BACDE求(LP212)x1x2⑴⑵33⑶11BACDE求(LP212)F如圖所示。此時(shí)F在點(diǎn)取得最優(yōu)解。x1=3,x2=2.5,Z(212)=31/2=15.5x1x2⑴⑵33⑶11BACDE求(LP212)F如圖所示。LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.5LP21x1=2.4,x2=3Z(21)
=17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)
=17LP212x1=3,x2=5/2Z(212)
=15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3##找到整數(shù)解,
此枝停止計(jì)算找到整數(shù)解,
此枝停止計(jì)算LP1LPLP2LP21LP22LP211LP212x1≤1LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.5LP21x1=2.4,x2=3Z(21)
=17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)
=17LP212x1=3,x2=5/2Z(212)
=15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3##找到最優(yōu)解找到整數(shù)解,
此枝停止計(jì)算找到整數(shù)解,
此枝停止計(jì)算LP1LPLP2LP21LP22LP211LP212x1≤1LP1x1=1,x2=3Z(1)
=16LPx1=18/11,x2=40/11Z(0)
=19.8LP2x1=2,x2=10/3Z(2)
=18.5LP21x1=2.4,x2=3Z(21)
=17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)
=17LP212x1=3,x2=5/2Z(212)
=15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3####
至此,原問(wèn)題(IP)的最優(yōu)解為:
x1=2,
x2=3,
Z*=Z(211)
=17以上的求解過(guò)程可以用一個(gè)樹形圖表示如右:LP1LPLP2LP21LP22LP211LP212x1≤1練習(xí):用分枝定界法求解整數(shù)規(guī)劃問(wèn)題
(圖解法)練習(xí):用分枝定界法求解整數(shù)規(guī)劃問(wèn)題
(圖解法)LP1x1=1,x2=7/3Z(1)
=10/3LPx1=3/2,x2=10/3Z(0)
=29/6LP2x1=2,x2=23/9Z(2)
=41/9x1≤1x1≥2LP21x1=33/14,x2=2Z(21)
=61/14LP22無(wú)可行解x2≤2x2≥3#LP211x1=2,x2=2Z(211)
=4LP212x1=3,x2=1Z(212)
=4x1≤2x1≥3##LP1LPLP2x1≤1x1≥2LP21LP22x2≤2x23200CB
XB
b
x1x2x3x40x3921109/20x414230114/2-Z032003200CB
XB
b
x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對(duì)應(yīng)的(LP)問(wèn)題,如表所示,獲得最優(yōu)解。初始表最終表例二、用分枝定界法求解整數(shù)規(guī)劃問(wèn)題(單純形法)
3200CBXBbx1x2x3x40x3921109/x1=13/4
x2=5/2Z(0)=59/4=14.75
選x2進(jìn)行分枝,即增加兩個(gè)約束,x2
2≥,x2≤3有下式:
分別在(LP1)和(LP2)中引入松弛變量x5和x6
,將新加約束條件加入上表計(jì)算。即x2+x5=2,-x2+x6=-3
得下表:x1=13/4x2=5/32000CB
XB
b
x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2
-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2Z(1)=29/2=14.5繼續(xù)分枝,加入約束
x1
≤3,x1≥4LP132000CBXBbx1x2x3x4x53x113/432000CB
XB
b
x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2
1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3
Z(2)=27/2=13.5∵
Z(2)<Z(1)∴先不考慮分枝32000CBXBbx1x2x3x4x63x113/4接(LP1)繼續(xù)分枝,加入約束
x1≤3,≤x1≥4
有下式:分別引入松弛變量x7和x8,然后進(jìn)行計(jì)算。接(LP1)繼續(xù)分枝,加入約束x1≤3,≤x1≥4CB
XB
b
x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度智能化停車場(chǎng)車位租賃管理服務(wù)合同模板4篇
- 2025年度智能家居廚房系統(tǒng)安裝工程合同規(guī)范版4篇
- 2024版牛奶飲料購(gòu)銷合同
- 2025年度專業(yè)代理記賬服務(wù)合作協(xié)議書4篇
- 2025年度文化宣傳活動(dòng)傳單派發(fā)合作協(xié)議范本4篇
- 2024年道路擴(kuò)建工程爆破作業(yè)協(xié)議樣本一
- 2025年度水利樞紐沖孔灌注樁施工勞務(wù)分包合同規(guī)范4篇
- 2025年度新型瓷磚產(chǎn)品研發(fā)運(yùn)輸合作協(xié)議4篇
- 2024石材開采與石材加工廠合作合同3篇
- 2025年度智能果園承包合作協(xié)議范本4篇
- 供應(yīng)鏈管理培訓(xùn)
- 2023小學(xué)道德與法治教師招聘考試試題與答案
- 氣管插管患者的壓力性損傷防治
- 湖南高職單招《綜合素質(zhì)測(cè)試》考試題庫(kù)(含答案)
- 失能老年人康復(fù)指導(dǎo)
- 數(shù)控加工技術(shù)-數(shù)控銑床的編程
- 內(nèi)科疾病的門診管理和科室建設(shè)
- 分子生物學(xué)在感染診斷中的應(yīng)用
- 供應(yīng)商年度評(píng)價(jià)內(nèi)容及評(píng)分表
- 山東省濟(jì)南市市中區(qū)2023-2024學(xué)年二年級(jí)上學(xué)期期中數(shù)學(xué)試卷
- 培訓(xùn)機(jī)構(gòu)入駐合作協(xié)議
評(píng)論
0/150
提交評(píng)論