運(yùn)籌學(xué)論文之二維背包問(wèn)題

1、整數(shù)規(guī)劃之二維背包問(wèn)題運(yùn)籌學(xué)課程2011年12月論文評(píng)價(jià)指標(biāo)與鑒定意見(jiàn)整數(shù)規(guī)劃之二維背包問(wèn)題摘 要 隨著經(jīng)濟(jì)的增長(zhǎng)，人們的體育生活也越來(lái)越豐富多彩，登山，成為人們的一種時(shí)尚。本文運(yùn)用動(dòng)態(tài)規(guī)劃問(wèn)題對(duì)在有限的載重、體積的背包盡可能的使背包中的物品價(jià)值最大。關(guān)鍵詞 登山 背包 動(dòng)態(tài)線性規(guī)劃Integer linear programming of the 2 d knapsack problem09Computer science and technology（1）classJIANG-Jiasheng HU-Zilan LI Ning LIU-Yonghu HE shi CHEN LeiAbstr

2、actWith economic growth, people's sports life also more and more rich and colorful, Mountain climbing, become a kind of fashion of people. In this paper, the dynamic planning in limited to weight, volume bag as possible the items value backpack.Key Words：Climbing ;Backpack; Dynamic linear progra

3、mming研究背景及思路 隨著人們物質(zhì)生活的日益豐富，人們也越來(lái)越注重自己的身體鍛煉。登山運(yùn)動(dòng)，也越來(lái)越燒到人們的親睞。在其有限的體積、載重的背包中使其載重價(jià)值最大。 動(dòng)態(tài)逆序規(guī)劃（Dynamic reverse planning）是動(dòng)態(tài)規(guī)則的一種方法，動(dòng)態(tài)規(guī)則是運(yùn)籌學(xué)的一個(gè)分支，他是解決多階段決策過(guò)程最優(yōu)化的一種數(shù)學(xué)方法。大約產(chǎn)生于20世紀(jì)50年代。1951年美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）等人，根據(jù)一類多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一些列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。與此同時(shí)，他提出了解決這類問(wèn)題的“最優(yōu)性原則”，研究了許多實(shí)際問(wèn)題，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的

4、一種新的方法動(dòng)態(tài)規(guī)劃。他的名著“動(dòng)態(tài)規(guī)劃”于1957年出版，該書是動(dòng)態(tài)規(guī)劃的一本著作。 動(dòng)態(tài)規(guī)劃的方法，在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門中都廣泛的應(yīng)用，并且獲得了顯著的效果。在企業(yè)管理方面，動(dòng)態(tài)規(guī)劃可以用來(lái)解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、庫(kù)存問(wèn)題、裝載問(wèn)題、排序問(wèn)題、設(shè)備更新問(wèn)題、生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等等，所以它是現(xiàn)在企業(yè)管理中的一種重要的決策方法。許多問(wèn)題用動(dòng)態(tài)規(guī)劃的方法去處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別對(duì)于離散性的問(wèn)題，由于解析數(shù)學(xué)無(wú)法施展其術(shù)，而動(dòng)態(tài)規(guī)劃的方法就成為非常有用的工具。應(yīng)指出，動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法，是考查問(wèn)題的一種途徑，而不是一

5、種特殊算法（如線性規(guī)劃是一種算法）。因此，它不像線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。思路： 通過(guò)在網(wǎng)上查詢數(shù)據(jù)，了解登上過(guò)程中需要哪些物品，查詢它們的質(zhì)量、體積，運(yùn)用動(dòng)態(tài)逆序規(guī)則解出在背包中需要加入的物品使得物品的總價(jià)值最大，再運(yùn)用java程序編程進(jìn)行校驗(yàn)，將動(dòng)態(tài)逆序規(guī)劃運(yùn)算的結(jié)果與java計(jì)算的結(jié)果進(jìn)行比較。并給出一定的建議使登山中更實(shí)用?；驹韯?dòng)態(tài)逆序規(guī)劃最基本模型：1設(shè)階段數(shù)為n的多階段決策過(guò)程，其階段編號(hào)為 允許策略為最優(yōu)策略的充要條件是對(duì)任意一個(gè)K 和有 (8-2)式中,它是由給定的初始狀態(tài)和子策略所確定的K段狀態(tài)。當(dāng)V是效益函

6、數(shù)2時(shí)，opt取max；當(dāng)V是損失函數(shù)時(shí)，opt取min。推論 若允許策略是最優(yōu)策略，則對(duì)任意的K，它的子策略對(duì)于以為起點(diǎn)的k到n-1子過(guò)程來(lái)說(shuō)，必須是最優(yōu)策略。（注意：k階段狀態(tài)是由和所確定的）建立動(dòng)態(tài)規(guī)劃模型時(shí)，必須做到下面五點(diǎn)：（1） 將問(wèn)題的過(guò)程劃分成恰當(dāng)?shù)碾A段；（2） 正確選擇狀態(tài)變量，使它既能描述過(guò)程的演變，又要滿足無(wú)后效性；（3） 確定決策變量及每階段的允許決策集合；（4） 正確寫出狀態(tài)轉(zhuǎn)移方程；（5） 正確寫出指示函數(shù)的關(guān)系，它應(yīng)滿足下面三個(gè)性質(zhì)： 是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)； 要具體可分離性，并滿足遞推關(guān)系。即 函數(shù)對(duì)于變量要嚴(yán)格單調(diào)。動(dòng)態(tài)規(guī)劃逆序解法的基本方

7、程： 設(shè)指標(biāo)函數(shù)是取個(gè)階段指標(biāo)的和的形式，即 其中表示第j段的指標(biāo)。它顯然是滿足指標(biāo)函數(shù)三個(gè)性質(zhì)的，所以上式可寫成 當(dāng)初是狀態(tài)給定時(shí)，過(guò)程的策略就被確定，則指標(biāo)函數(shù)也就確定了。因此，指標(biāo)函數(shù)是初始狀態(tài)和策略的函數(shù)。可記為。故上面遞推關(guān)系又可寫成 其子策略可以看成是由決策和組合而成。即 如果用表示初始狀態(tài)為的后部子過(guò)程所有子策略中的最優(yōu)子策略。則最優(yōu)值函數(shù)為 而 但 所以 邊界條件為。 式中，其求解過(guò)程，根據(jù)邊界條件，從k=n開(kāi)始，有后向前逆推，從而逐步可求得各階段的最優(yōu)策略和相應(yīng)的最優(yōu)值，最后求出時(shí)，就得到整個(gè)問(wèn)題的最優(yōu)解。考查n階段決策過(guò)程。 決策s1 xk xnn1 K 狀態(tài)s1 s2 。

8、s2 . sk sk+1 sn sn+1 效益v1（s1，x1） vk(sk,xk) vn(sn,xn)其中取狀態(tài)變量為;決策變量為。在第k階段，決策使?fàn)顟B(tài)（輸入）轉(zhuǎn)移為狀態(tài)（輸出），設(shè)狀態(tài)轉(zhuǎn)移方程為 假定過(guò)程的總效益（指標(biāo)函數(shù)）與各階段效益（階段指標(biāo)函數(shù)）的關(guān)系為 其中記號(hào)“*”可都表示為“+”或者表示為“×”。問(wèn)題為使達(dá)到最優(yōu)化，即求，為簡(jiǎn)單起見(jiàn)，不妨此處就求max。4.1逆推解法設(shè)已知初始狀態(tài)為是，并假設(shè)最優(yōu)值函數(shù)表示第k階段的初始狀態(tài)為，從k階段到n階段所得到的最大效益。 從第n階段開(kāi)始，則有 其中是由狀態(tài)所確定的第n階段的允許決策集合。解此一維極值問(wèn)題，就得到最優(yōu)解和最優(yōu)值

9、，要注意的是，若只是一個(gè)決策，則就應(yīng)寫成 在第n-1階段，有 其中；解此一維極值問(wèn)題，得到最優(yōu)解和最優(yōu)值。在第k階段，有 其中。解得最優(yōu)解和最優(yōu)值。如此類推，知道第一階段，有 其中；解得最優(yōu)解和最優(yōu)值。由于初始狀態(tài)已知，故和是確定的，從而也就可確定，于是和也就可以確定。這樣，按照上述遞推過(guò)程相反的順序推算下去，就可逐步確定出每階段的決策和效益。數(shù)學(xué)模型一般模式：登山者所能承受的背包的重量（亦即重量不能超過(guò)wkg）.但是實(shí)際上背包除受重量的限制外，還有體積的限制，這就是不但要求旅行者的背包的重量M不能超過(guò)w（kg），還要求旅行者背包的體積V不能超過(guò)v（m3）二維背包的一般條件：物品編號(hào)12kn-

10、1n物品質(zhì)量W1W2WkWn-1Wn物品體積V1V2VkVn-1Vn物品價(jià)值C1C2CkCn-1Cn則可列出整數(shù)線性規(guī)劃的方程組為： 數(shù)據(jù)來(lái)源： 通過(guò)在網(wǎng)上搜尋以及對(duì)一些登山運(yùn)動(dòng)員的調(diào)查可得到以下數(shù)據(jù)： 登山包的載重一般為：30kg、體積一般為35L；衣服：內(nèi)衣，保暖層，防風(fēng)防雨外套等；食物：面包、壓縮餅干及一些熟食等； 通訊工具：對(duì)講機(jī)，手機(jī)，哨子等； 日常用品：相機(jī)，洗簌用品，太陽(yáng)鏡等； 日用藥品：感冒藥，創(chuàng)口貼等。 由于帳篷可以掛著背包外面，因此，它只消耗背包的質(zhì)量，不消耗其體積各物品的數(shù)據(jù)為：物品衣服食物帳篷繩索照明器材通訊設(shè)備日常用品日用藥品物品編號(hào)12345678質(zhì)量（kg）551

11、231452體積（L）69022486價(jià)值510472524通過(guò)上述可得到以下式子： 用動(dòng)態(tài)逆序規(guī)劃求解如下：當(dāng)k=8時(shí)： 當(dāng)k=7時(shí)： 同理： 當(dāng)k=6時(shí)： 當(dāng)k=5時(shí)： 當(dāng)k=4時(shí)： 當(dāng)k=3時(shí)： 當(dāng)k=2時(shí)： 當(dāng)k=1時(shí):即=1，=1 則當(dāng)其背包載重大于等于10kg并且其體積大于等于15L時(shí)：最大價(jià)值為15。則其余的最大值為5；通過(guò)觀察可知以下的值為5： 當(dāng)k=2時(shí)：即=1 則中滿足背包載重大于等于22kg并且體積大于等于15L的條件時(shí)其價(jià)值最大為：19，其余值分別為：559999999當(dāng)k=3時(shí)：即=1 則中滿足背包載重大于等于25kg并且體積大于等于17L的條件時(shí)其價(jià)值最大為：21，

12、其余值分別為：99111119191919當(dāng)k=4：即=1 則中滿足背包載重大于等于26kg并且體積大于等于19L的條件時(shí)其價(jià)值最大為：23，其余值分別為：1113212121當(dāng)k=5時(shí)：即=1 則中滿足背包載重大于等于30kg并且體積大于等于21L的條件時(shí)其最大值為：28 它們的值分別為：21212628當(dāng)k=6時(shí)：即=1 通過(guò)上述情況可知背包的載重已經(jīng)用完，只有體積余下，則經(jīng)過(guò)計(jì)算可得的值：=28，即=0時(shí)成立；=26 。即=1時(shí)成立。當(dāng)k=7時(shí)：即=1 經(jīng)過(guò)計(jì)算可得到值為：=30，即=1時(shí)。通過(guò)上述的情況可得以下結(jié)論： 即有情況：=1，=0，=1，=1，=0，=1，=1，=1 則將衣服，

13、食物，帳篷，照明器材，通訊設(shè)備，日用藥品放入背包使其所獲取的價(jià)值最大。而繩索，日常用品不需要裝入。其最大價(jià)值為30。結(jié)論及評(píng)價(jià)通過(guò)逆序規(guī)劃的方法我們得到了在一定載重和體積的背包中的最大價(jià)值。通過(guò)計(jì)算我們也看到一些不足之處，可總結(jié)為以下幾點(diǎn)：（1） 對(duì)于逆序規(guī)劃，在數(shù)據(jù)較多時(shí)，算法比較繁瑣，計(jì)算時(shí)很容易出錯(cuò)。龐大數(shù)據(jù)不利于用逆序規(guī)劃。（2） 在數(shù)據(jù)的收集時(shí)可能過(guò)于簡(jiǎn)單，只是在淘寶搜集物品質(zhì)量和對(duì)一些登山運(yùn)動(dòng)愛(ài)好者的詢問(wèn)。（3） 在計(jì)算過(guò)程中，可能由于個(gè)人原因會(huì)出現(xiàn)一些人為的誤差，造成結(jié)果可能數(shù)據(jù)上的一些偏差。（4） 由于知識(shí)面不廣，文中有很多不足之處，需要進(jìn)行改進(jìn)的。建議： 在登山旅行中，我們應(yīng)

14、該有目地的計(jì)劃，自己的行程，使背包能夠裝載對(duì)旅行最有利的東西，根據(jù)具體的地形、地域選著所要攜帶的物品。像冬天在附近的區(qū)域，我們可以攜帶多點(diǎn)的衣服來(lái)保溫，夏天可以只攜帶少量的衣物。對(duì)于野外登山，我們必須注意自身的安全，通訊設(shè)備，防身工具是必不可少的。因此，我們必須攜帶一兩件通訊設(shè)備、防身工具。參考文獻(xiàn)1運(yùn)籌學(xué)教材編寫組 運(yùn)籌學(xué) 北京 清華大學(xué)出版社 第199201頁(yè)，第203204頁(yè)附錄Java程序代碼：public class Erwei static int MaxValue(int n,int j,int w,int k,int b,int v,int m) int t =Math.max

15、(wn,bn); for(int i = 1;i<t;i+) for( int p = 1;p<t;p+ ) mnip = 0; for(int i = t;i<wn;i+) for(int p = t;p<bn;p+) mnip = vn; for(int i = n-1;i>1;i-) t = Math.max(wi,bi); for(int j1 = 1;j1<t;j1+) for(int k1 = 1;k1<t;k1+) mij1k1 = mi+1j1k1; for(int j1 = t;j1<=j;j1+) for(int k1 = t

16、;k1<=k;k1+) mij1k1 = Math.max(mi+1j1k1,mi+1j1-wik1-bi+vi); m1jk = m2jk; if(m2j-w1k-b1+v1>m1jk) m1jk = m2j-w1k-b1+v1; return m1jk; public static void main(String args) int n=7,j=30,k=35,a,l; System.out.print("請(qǐng)輸入a的值:a="); a=Integer.parseInt(args0); int w=5,5,12,3,1,4,5,2; int b=6,9,0,2,2,4,8,6; int v=5,1