運籌學論文之二維背包問題

1、整數規(guī)劃之二維背包問題運籌學課程2011年12月論文評價指標與鑒定意見整數規(guī)劃之二維背包問題摘 要 隨著經濟的增長，人們的體育生活也越來越豐富多彩，登山，成為人們的一種時尚。本文運用動態(tài)規(guī)劃問題對在有限的載重、體積的背包盡可能的使背包中的物品價值最大。關鍵詞 登山 背包 動態(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研究背景及思路 隨著人們物質生活的日益豐富，人們也越來越注重自己的身體鍛煉。登山運動，也越來越燒到人們的親睞。在其有限的體積、載重的背包中使其載重價值最大。 動態(tài)逆序規(guī)劃（Dynamic reverse planning）是動態(tài)規(guī)則的一種方法，動態(tài)規(guī)則是運籌學的一個分支，他是解決多階段決策過程最優(yōu)化的一種數學方法。大約產生于20世紀50年代。1951年美國數學家貝爾曼（R.Bellman）等人，根據一類多階段決策問題的特點，把多階段決策問題變換為一些列互相聯(lián)系的單階段問題，然后逐個加以解決。與此同時，他提出了解決這類問題的“最優(yōu)性原則”，研究了許多實際問題，從而創(chuàng)建了解決最優(yōu)化問題的

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

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

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

7、程： 設指標函數是取個階段指標的和的形式，即 其中表示第j段的指標。它顯然是滿足指標函數三個性質的，所以上式可寫成 當初是狀態(tài)給定時，過程的策略就被確定，則指標函數也就確定了。因此，指標函數是初始狀態(tài)和策略的函數。可記為。故上面遞推關系又可寫成 其子策略可以看成是由決策和組合而成。即 如果用表示初始狀態(tài)為的后部子過程所有子策略中的最優(yōu)子策略。則最優(yōu)值函數為 而 但 所以 邊界條件為。 式中，其求解過程，根據邊界條件，從k=n開始，有后向前逆推，從而逐步可求得各階段的最優(yōu)策略和相應的最優(yōu)值，最后求出時，就得到整個問題的最優(yōu)解。考查n階段決策過程。 決策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階段，決策使狀態(tài)（輸入）轉移為狀態(tài)（輸出），設狀態(tài)轉移方程為 假定過程的總效益（指標函數）與各階段效益（階段指標函數）的關系為 其中記號“*”可都表示為“+”或者表示為“×”。問題為使達到最優(yōu)化，即求，為簡單起見，不妨此處就求max。4.1逆推解法設已知初始狀態(tài)為是，并假設最優(yōu)值函數表示第k階段的初始狀態(tài)為，從k階段到n階段所得到的最大效益。 從第n階段開始，則有 其中是由狀態(tài)所確定的第n階段的允許決策集合。解此一維極值問題，就得到最優(yōu)解和最優(yōu)值

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

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

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

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

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

14、該有目地的計劃，自己的行程，使背包能夠裝載對旅行最有利的東西，根據具體的地形、地域選著所要攜帶的物品。像冬天在附近的區(qū)域，我們可以攜帶多點的衣服來保溫，夏天可以只攜帶少量的衣物。對于野外登山，我們必須注意自身的安全，通訊設備，防身工具是必不可少的。因此，我們必須攜帶一兩件通訊設備、防身工具。參考文獻1運籌學教材編寫組 運籌學 北京 清華大學出版社 第199201頁，第203204頁附錄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("請輸入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