




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第5章 整數(shù)線(xiàn)性規(guī)劃 第1節(jié) 整數(shù)線(xiàn)性規(guī)劃問(wèn)題的提出 第2節(jié) 分支定界解法 第3節(jié) 割平面解法 第4節(jié) 0-1型整數(shù)線(xiàn)性規(guī)劃 第5節(jié) 指派問(wèn)題第1節(jié) 整數(shù)線(xiàn)性規(guī)劃問(wèn)題的提出 在前面討論的線(xiàn)性規(guī)劃問(wèn)題中,有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù),但對(duì)于某些具體問(wèn)題,常有要求解答必須是整數(shù)的情形(整數(shù)解)。 例如,所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)或裝貨的車(chē)數(shù)等,分?jǐn)?shù)或小數(shù)的解答就不合要求。 為了滿(mǎn)足整數(shù)解的要求,初看起來(lái),似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過(guò)“舍入化整”就可以了。但這常常是不行的,因?yàn)榛蟛灰?jiàn)得是可行解;或雖是可行解,但不一定是最優(yōu)解。 因此,對(duì)求最優(yōu)整數(shù)解的問(wèn)題,有必要另行研究。我們稱(chēng)
2、這樣的問(wèn)題為整數(shù)線(xiàn)性規(guī)劃(integer linear programming),簡(jiǎn)稱(chēng)ILP,整數(shù)線(xiàn)性規(guī)劃是最近幾十年來(lái)發(fā)展起來(lái)的規(guī)劃論中的一個(gè)分支。 整數(shù)線(xiàn)性規(guī)劃中如果所有的變數(shù)都限制為(非負(fù))整數(shù),就稱(chēng)為純整數(shù)線(xiàn)性規(guī)劃(pure integer linear programming)或稱(chēng)為全整數(shù)線(xiàn)性規(guī)劃(all integer linear programming);如果僅一部分變數(shù)限制為整數(shù),則稱(chēng)為混合整數(shù)計(jì)劃(mixed integer linear programming)。 整數(shù)線(xiàn)性規(guī)劃的一種特殊情形是0-1規(guī)劃,它的變數(shù)取值僅限于0或1。本章最后講到的指派問(wèn)題就是一個(gè)0-1規(guī)劃問(wèn)
3、題。 現(xiàn)舉例說(shuō)明用前述單純形法求得的解不能保證是整數(shù)最優(yōu)解。 例1:某廠(chǎng)擬用集裝箱托運(yùn)甲乙兩種貨物,每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表5-1所示。問(wèn)兩種貨物各托運(yùn)多少箱,可使獲得利潤(rùn)為最大? 表5-1 現(xiàn)在我們解這個(gè)問(wèn)題,設(shè)x1,x2分別為甲、乙兩種貨物的托運(yùn)箱數(shù)(當(dāng)然都是非負(fù)整數(shù))。 這是一個(gè)(純)整數(shù)線(xiàn)性規(guī)劃問(wèn)題,用數(shù)學(xué)式可表示為:max z =20 x1+10 x2 5x1+4x224 2x1+5x213 (5.1) x1,x20 x1,x2整數(shù) 它和線(xiàn)性規(guī)劃問(wèn)題的區(qū)別僅在于最后的條件?,F(xiàn)在我們暫不考慮這一條件,即解(以后我們稱(chēng)這樣的問(wèn)題為與原問(wèn)題相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題)很容易求
4、得最優(yōu)解為:x1=4.8 x2=0 max z=96 但x1是托運(yùn)甲種貨物的箱數(shù),現(xiàn)在它不是整數(shù),所以不合條件的要求。 是不是可以把所得的非整數(shù)的最優(yōu)解經(jīng)過(guò)“化整”就可得到合于條件的整數(shù)最優(yōu)解呢? 如將(x1=4.8,x2=0)湊整為(x1=5,x2=0),這樣就破壞了條件(關(guān)于體積的限制),因而它不是可行解; 如將(x1=4.8,x2=0)舍去尾數(shù)0.8,變?yōu)?x1=4,x2=0),這當(dāng)然滿(mǎn)足各約束條件,因而是可行解,但不是最優(yōu)解,因?yàn)楫?dāng)x1=4,x2=0, 時(shí)z=80。但當(dāng)x1=4,x2=1(這也是可行解)時(shí),z=90。 圖中畫(huà)(+)號(hào)的點(diǎn)表示可行的整數(shù)解。湊整的(5,0)點(diǎn)不在可行域內(nèi),
5、而C點(diǎn)又不合于條件。為了滿(mǎn)足題中要求,表示目標(biāo)函數(shù)的z的等值線(xiàn)必須向原點(diǎn)平行移動(dòng),直到第一次遇到帶“+”號(hào)B點(diǎn)(x1=4,x2=1)為止。 這樣,z的等值線(xiàn)就由z=96變到z=90,它們的差值z(mì)=96-90=6 表示利潤(rùn)的降低,這是由于變量的不可分性(裝箱)所引起的。 由上例看出,將其相應(yīng)的線(xiàn)性規(guī)劃的最優(yōu)解“化整”來(lái)解原整數(shù)線(xiàn)性規(guī)劃,雖是最容易想到的,但常常得不到整數(shù)線(xiàn)性規(guī)劃的最優(yōu)解,甚至根本不是可行解。因此有必要對(duì)整數(shù)線(xiàn)性規(guī)劃的解法進(jìn)行專(zhuān)門(mén)研究。第2節(jié) 分支定界解法 在求解整數(shù)線(xiàn)性規(guī)劃時(shí),如果可行域是有界的,首先容易想到的方法就是窮舉變量的所有可行的整數(shù)組合,就像在圖5-1中畫(huà)出所有“+”號(hào)
6、的點(diǎn)那樣,然后比較它們的目標(biāo)函數(shù)值以定出最優(yōu)解。對(duì)于小型的問(wèn)題,變量數(shù)很少,可行的整數(shù)組合數(shù)也是很小時(shí),這個(gè)方法是可行的,也是有效的。 在例1中,變量只有x1和x2 由條件,x1所能取的整數(shù)值為0、1、2、3、4共5個(gè);由條件,x2所能取的整數(shù)值為0、1、2共3個(gè);它的組合(不都是可行的)數(shù)是35=15個(gè),窮舉法還是勉強(qiáng)可用的。 對(duì)于大型問(wèn)題,可行的整數(shù)組合數(shù)是很大的。 例如在本章第5節(jié)的指派問(wèn)題(這也是整數(shù)線(xiàn)性規(guī)劃)中,將n項(xiàng)任務(wù)指派n個(gè)人去完成,不同的指派方案共有n!種,當(dāng)n=10,這個(gè)數(shù)就超過(guò)300萬(wàn);當(dāng)n=20,這個(gè)數(shù)就超過(guò)21018,如果一一計(jì)算,就是用每秒百萬(wàn)次的計(jì)算機(jī),也要幾萬(wàn)年
7、的功夫,很明顯,解這樣的題,窮舉法是不可取的。所以我們的方法一般應(yīng)是僅檢查可行的整數(shù)組合的一部分,就能定出最優(yōu)的整數(shù)解。 分支定界解法(branch and bound method)就是其中的一個(gè)。 分支定界法可用于解純整數(shù)或混合的整數(shù)線(xiàn)性規(guī)劃問(wèn)題。在20世紀(jì)60年代初由Land Doig和Dakin等人提出。由于這方法靈活且便于用計(jì)算機(jī)求解,所以現(xiàn)在它已是解整數(shù)線(xiàn)性規(guī)劃的重要方法。 設(shè)有最大化的整數(shù)線(xiàn)性規(guī)劃問(wèn)題A,與它相應(yīng)的線(xiàn)性規(guī)劃為問(wèn)題B,從解問(wèn)題B開(kāi)始,若其最優(yōu)解不符合A的整數(shù)條件,那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)z*的上界;而A的任意可行解的目標(biāo)函數(shù)值將是z*的一個(gè)下界。分支
8、定界法就是將B的可行域分成子區(qū)域(稱(chēng)為分支)的方法,逐步減小和增大,最終求到z*。例 2 求解A max z=40 x1+90 x2 9x1+ 7x256 7x1+20 x270 (5.2) x1,x20 x1,x2整數(shù) 解解 先不考慮條件,即解相應(yīng)的線(xiàn)性規(guī)劃B,(見(jiàn)圖5-2),得最優(yōu)解x1=4.81,x2=1.82,z0=356 可見(jiàn)它不符合整數(shù)條件。這時(shí)z0是問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界,記作z0= 。而在x1=0,x2=0時(shí),顯然是問(wèn)題A的一個(gè)整數(shù)可行解,這時(shí)z=0,是z*的一個(gè)下界,記作 =0,即0z*356zz分支定界法的解法 首先注意其中一個(gè)非整數(shù)變量的解,如x1,在問(wèn)題B的解
9、中x1=4.81。于是對(duì)原問(wèn)題增加兩個(gè)約束條件x14,x15。 可將原問(wèn)題分解為兩個(gè)子問(wèn)題B1和B2(即兩支),給每支增加一個(gè)約束條件,如圖5-3所示。 這并不影響問(wèn)題A的可行域,不考慮整數(shù)條件解問(wèn)題B1和B2,稱(chēng)此為第一次迭代。圖5-3 x14,x15 得到最優(yōu)解為: 顯然沒(méi)有得到全部變量是整數(shù)的解。 因z1z2,故將 改為349,那么必存在最優(yōu)整數(shù)解,得到z*,并且0z*349z繼續(xù)對(duì)問(wèn)題B1和B2進(jìn)行分解 因z1z2,故先分解B1為兩支。增加條件x22者,稱(chēng)為問(wèn)題B3;增加條件x23者稱(chēng)為問(wèn)題B4。在圖5-3中再舍去x22與x33之間的可行域, 再進(jìn)行第二次迭代。繼續(xù)對(duì)問(wèn)題B2進(jìn)行分解
10、圖5-4 解題的過(guò)程都列在圖5-4中。 從以上解題過(guò)程可得到,用分支定界法求解整數(shù)線(xiàn)性規(guī)劃(最大化)問(wèn)題的步驟為: 將要求解的整數(shù)線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為問(wèn)題A, 將與它相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為問(wèn)題B。 (1)解問(wèn)題B,可能得到以下情況: B沒(méi)有可行解,這時(shí)A沒(méi)有可行解,停止。 B有最優(yōu)解,并符合問(wèn)題A的整數(shù)條件,B的最優(yōu)解即為A的最優(yōu)解,停止。 B有最優(yōu)解,但不符合問(wèn)題A的整數(shù)條件,記它的目標(biāo)函數(shù)值為0z(2) 用觀察法找問(wèn)題A的一個(gè)整數(shù)可行解,一般可取xj=0,j=1,n,試探,求得其目標(biāo)函數(shù)值,并記作 。 以z*表示問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值; 這時(shí)有zzzz*進(jìn)行迭代第一步:分支定界 分支 在B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj,其值為bj,以bj表示小于bj的最大整數(shù)。構(gòu)造兩個(gè)約束條件xjbj和 xjbj+ 1 將這兩個(gè)約束條件,分別加入問(wèn)題B,求兩個(gè)后繼規(guī)劃問(wèn)題B1和B2。 不考慮整數(shù)條件求解這兩個(gè)后繼問(wèn)題。 定界 以每個(gè)后繼問(wèn)題為一分支標(biāo)明求解的結(jié)果,與其他問(wèn)題的解的結(jié)果中,找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。 從已符合整數(shù)條件的各分支中,找出目標(biāo)函數(shù)值為最大者作為新的下界,若無(wú)可行解, 0z第二步:比較與剪支 各分支的最優(yōu)目標(biāo)函數(shù)中若
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東省濟(jì)南市鋼城區(qū)實(shí)驗(yàn)學(xué)校2024年數(shù)學(xué)八年級(jí)第一學(xué)期期末經(jīng)典試題含解析
- 山東省龍口市蘭高鎮(zhèn)蘭高學(xué)校2024年八上數(shù)學(xué)期末調(diào)研模擬試題含解析
- 浙江省杭州市拱墅區(qū)2025屆物理八年級(jí)第一學(xué)期期末統(tǒng)考試題含解析
- 菜鳥(niǎo)驛站加盟店轉(zhuǎn)租合同模板解析
- 中小企業(yè)的創(chuàng)業(yè)環(huán)境與發(fā)展策略研究
- 產(chǎn)品特點(diǎn)與競(jìng)爭(zhēng)優(yōu)勢(shì)剖析
- 2025年《中華人民共和國(guó)藥品管理法》培訓(xùn)試卷含答案
- 2025至2030馬鈴薯全粉市場(chǎng)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢(xún)研究報(bào)告
- 我會(huì)表達(dá)愛(ài)-心理健康教育
- 2025至2030中國(guó)自卸汽車(chē)行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢(xún)研究報(bào)告
- DB11-T 1192-2025 工作場(chǎng)所防暑降溫技術(shù)規(guī)范
- 2025年精益生產(chǎn)管理考試試題及答案
- 歷年造價(jià)員考試試題及答案
- 小學(xué)美術(shù)大單元教學(xué)設(shè)計(jì)與實(shí)施研究
- 山地生態(tài)治理修復(fù)項(xiàng)目可行性研究報(bào)告
- 小兒喘息性肺炎的護(hù)理
- 新能源產(chǎn)業(yè)中液流電池儲(chǔ)能電站項(xiàng)目的成功要素解析
- 2877管理學(xué)基礎(chǔ)1-15套試題答案 國(guó)開(kāi)
- 2025陜西中考語(yǔ)文試題(含答案)
- 物業(yè)培訓(xùn)課件大全
- Unit 1 This is me 語(yǔ)法提升 課件 外研版英語(yǔ)八年級(jí)上冊(cè)
評(píng)論
0/150
提交評(píng)論