版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
背包問(wèn)題例1(背包問(wèn)題)設(shè)有一輛背包可以裝入的物品情況如下表:問(wèn):如何安排裝入方案,使背包一次裝入的貨物總價(jià)值最大?解:設(shè)xi為背包裝入第i種貨物的件數(shù)。貨物(件)12…n
最大裝入量
單位重量w1
w2…wn
a單位價(jià)值c1
c2…cn注:若每種物品的最大件數(shù)為1,則xi取值為0或1,稱(chēng)為0-1背包問(wèn)題階段:按照物品的種類(lèi)將裝入背包的過(guò)程分為n個(gè)階段,每個(gè)階段裝入一種物品;狀態(tài)變量sk:裝前k-1種的物品的可用背包容量;決策變量xk
:裝入第k種物品的數(shù)量;狀態(tài)轉(zhuǎn)移方程:sk=sk+1-wkxk最優(yōu)指標(biāo)函數(shù)fk(sk+1):若只裝入k種物品,背包容量為sk+1時(shí)裝入物品的最大價(jià)值動(dòng)態(tài)規(guī)劃的順序遞推方程(順序解法)顯然,我們要求的是fn(a)例1:有一艘貨船的最大載重量為5噸,用以裝載三種貨物,每種貨物的單位重量及單價(jià)如表所示。應(yīng)如何裝載使總重量最大?貨物(件)123
最大裝入量
單位重量3255單位價(jià)值8512解:按順序裝入三種貨物,裝入過(guò)程分為三個(gè)階段,k=1,2,3。采用動(dòng)態(tài)規(guī)劃的順序解法求解。當(dāng)k=2時(shí)當(dāng)k=1時(shí)當(dāng)k=3時(shí)由所以所裝入的最大物品總價(jià)值為13。
旅行商(TSP)問(wèn)題設(shè)有一個(gè)由n個(gè)城市構(gòu)成的交通網(wǎng)絡(luò),各個(gè)城市之間的路徑長(zhǎng)度已知。一個(gè)推銷(xiāo)員從城市1出發(fā)到其他城市,每個(gè)城市必須經(jīng)過(guò)且只經(jīng)過(guò)一次然后返回城市1。問(wèn):該推銷(xiāo)員該如何選擇行走路線(xiàn)使得總的路程最短。記所有城市的集合為V={v1,v2,…,vn};
城市i到城市j的距離為dij;遞推公式(動(dòng)態(tài)規(guī)劃的基本方程):很顯然,我們最后需要求的是,其中將推銷(xiāo)員的旅行過(guò)程分為n個(gè)階段;第k階段的狀態(tài)為:(所在的城市vi,所經(jīng)過(guò)的城市集合Vk
)最優(yōu)值函數(shù)fk(vi,Vk):從城市1出發(fā),經(jīng)過(guò)k個(gè)城市(經(jīng)過(guò)城市集合為Vk)到達(dá)城市vi
的最短路徑長(zhǎng)度采用順序解法進(jìn)行求解例2:求解4個(gè)城市的旅行商問(wèn)題,其4個(gè)城市之間的距離如矩陣所示。求推銷(xiāo)員從城市1出發(fā)經(jīng)過(guò)所有城市一次并回到城市1的最短路徑及路徑長(zhǎng)度。解:由邊界條件可知k=1:從v1出發(fā),經(jīng)過(guò)一個(gè)城
溫馨提示
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 新能源汽車(chē)電池及管理系統(tǒng)檢修 課件全套 吉文哲 項(xiàng)目1-9 動(dòng)力蓄電池的總體認(rèn)知 -新能源汽車(chē)動(dòng)力蓄電池廢棄處理
- 勐臘縣婦女兒童發(fā)展規(guī)劃綱要統(tǒng)計(jì)監(jiān)測(cè)評(píng)估報(bào)告
- 大學(xué)英語(yǔ)四級(jí)(語(yǔ)法與詞匯)練習(xí)試卷8(共180題)
- 汽車(chē)發(fā)動(dòng)機(jī)構(gòu)造與維修 教案 5.3檢查氣缸蓋及氣缸墊襯墊
- 記賬實(shí)操-手袋箱包加工廠(chǎng)的賬務(wù)處理分錄
- 《竹石》堅(jiān)韌精神教案
- 《四季的歌》自然之美教案
- 《猴王出世》奇幻冒險(xiǎn)教案
- 2024智能通道管理系統(tǒng)
- 企業(yè)文檔管理云開(kāi)放平臺(tái)應(yīng)用解決方案
- 閘門(mén)啟閉機(jī)系統(tǒng)課件
- 《靜夜思》課件版
- 素描人物半身像課件
- 八年級(jí)數(shù)學(xué)學(xué)習(xí)探究診斷上冊(cè)
- 第三屆江西省農(nóng)業(yè)綜合行政執(zhí)法大比武考試參考題庫(kù)(含答案)
- 六年級(jí)家長(zhǎng)會(huì)完整版課件
- 部編人教版二年級(jí)道德與法治上冊(cè)完整全冊(cè)課件
- 高考英語(yǔ)閱讀理解七選五問(wèn)題與對(duì)策
- 《角平分線(xiàn)的性質(zhì)》教案 2022年 (省一等獎(jiǎng))
- 中學(xué)生行為習(xí)慣的養(yǎng)成主題班會(huì)(共26張)課件
- 行為習(xí)慣養(yǎng)成教育個(gè)人評(píng)價(jià)量表
評(píng)論
0/150
提交評(píng)論