關(guān)于動(dòng)態(tài)規(guī)劃的基本原理和基本應(yīng)用第1頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月2

動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法。由美國(guó)數(shù)學(xué)家貝爾曼（Bellman）等人在20世紀(jì)50年代提出。他們針對(duì)多階段決策問(wèn)題的特點(diǎn)，提出了解決這類問(wèn)題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多實(shí)際問(wèn)題。第2頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月3

動(dòng)態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃和庫(kù)存問(wèn)題、投資問(wèn)題、裝載問(wèn)題、排序問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。第3頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月49.1多階段決策過(guò)程最優(yōu)化問(wèn)題舉例多階段決策過(guò)程最優(yōu)化多階段決策過(guò)程是指這樣一類特殊的活動(dòng)過(guò)程，他們可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策問(wèn)題也稱為序貫決策問(wèn)題。第4頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月5例1多階段資源分配問(wèn)題

設(shè)有數(shù)量為x的某種資源，將它投入兩種生產(chǎn)方式A和B中：以數(shù)量y投入生產(chǎn)方式A，剩下的量投入生產(chǎn)方式B，則可得到收入g(y)+h(x-y)，其中g(shù)(y)和h(y)是已知函數(shù)，并且g(0)=h(0)=0；同時(shí)假設(shè)以y與x-y分別投入兩種生產(chǎn)方式A，B后可以回收再生產(chǎn)，回收率分別為a與b。試求進(jìn)行n個(gè)階段后的最大總收入。

第5頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月6

若以y與x-y分別投入生產(chǎn)方式A與B，在第一階段生產(chǎn)后回收的總資源為x1=ay+b(x-y)，再將x1投入生產(chǎn)方式A和B，則可得到收入g(y1)+h(x1-y1)，繼續(xù)回收資源x2=ay1+b(x1-y1)，……

若上面的過(guò)程進(jìn)行n個(gè)階段，我們希望選擇n個(gè)變量y,y1,y2,…,yn-1，使這n個(gè)階段的總收入最大。

例1第6頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月7

因此，我們的問(wèn)題就變成：求y,y1,y2,…,yn-1，以使g(y)+h(x-y)+g(y1)+h(x1-y1)+…+g(yn-1)+h(xn-1-yn-1)

達(dá)到最大，且滿足條件

x1=ay+b(x-y)

x2=ay1+b(x1-y1)………

xn-1=ayn-2+b(xn-2-yn-2)

yi與xi均非負(fù),i=1,2,…,n-1

例1第7頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月8例2生產(chǎn)和存儲(chǔ)控制問(wèn)題

某工廠生產(chǎn)某種季節(jié)性商品，需要作下一年度的生產(chǎn)計(jì)劃，假定這種商品的生產(chǎn)周期需要兩個(gè)月，全年共有6個(gè)生產(chǎn)周期，需要作出各個(gè)周期中的生產(chǎn)計(jì)劃。設(shè)已知各周期對(duì)該商品的需要量如下表所示：周期123456需求量551030508第8頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月9例2

假設(shè)這個(gè)工廠根據(jù)需要可以日夜兩班生產(chǎn)或只是日班生產(chǎn)，當(dāng)開(kāi)足日班時(shí)，每一個(gè)生產(chǎn)周期能生產(chǎn)商品15個(gè)單位，每生產(chǎn)一個(gè)單位商品的成本為100元。當(dāng)開(kāi)足夜班時(shí)，每一生產(chǎn)周期能生產(chǎn)的商品也是15個(gè)，但是由于增加了輔助性生產(chǎn)設(shè)備和生產(chǎn)輔助費(fèi)用，每生產(chǎn)一單位商品的成本為120元。由于生產(chǎn)能力的限制，可以在需求淡季多生產(chǎn)一些商品儲(chǔ)存起來(lái)以備需求旺季使用，但存儲(chǔ)商品是需要存儲(chǔ)費(fèi)用的，假設(shè)每單位商品存儲(chǔ)一周期需要16元，已知開(kāi)始時(shí)存儲(chǔ)為零，年終也不存儲(chǔ)商品備下年使用，問(wèn)應(yīng)該如何作生產(chǎn)和存儲(chǔ)計(jì)劃，才能使總的生產(chǎn)和存儲(chǔ)費(fèi)用最??？第9頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月10例2

設(shè)第i個(gè)周期的生產(chǎn)量為xi，周期末的存儲(chǔ)量為ui，那么這個(gè)問(wèn)題用式子寫出來(lái)就是：求x1,x2,…,x6，滿足條件：

x1=5+u1

x2+u1=5+u2

x3+u2=10+u3

x4+u3=30+u4

x5+u4=50+u5

x6+u5=80xi

30,0uj,i=1,2,…,6;j=1,2,…,5

使S=

=為最小，其中第10頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月11

例3

運(yùn)輸網(wǎng)絡(luò)問(wèn)題：如圖1所示的運(yùn)輸網(wǎng)絡(luò)，點(diǎn)間連線上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時(shí)間等)，要求從v1至v10的最短路線。這種運(yùn)輸網(wǎng)絡(luò)問(wèn)題也是靜態(tài)決策問(wèn)題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為4個(gè)階段，而作為多階段決策問(wèn)題來(lái)研究。第11頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月121234圖1

運(yùn)輸網(wǎng)絡(luò)圖示第12頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月13動(dòng)態(tài)規(guī)劃方法導(dǎo)引為了說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn)，下面以圖1所示為例討論求最短路問(wèn)題的方法。

第一種方法稱做全枚舉法或窮舉法，它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對(duì)它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個(gè)階段。第一二段的走法有三種，第三段的走法有兩種，第四段的走法僅一種，因此共有3×3×2×1＝18條可能的路線，54次加法算出各條路線的距離，最后進(jìn)行17次兩兩比較，可知最優(yōu)路線是v1→v2→

v5→

v8→v10,最短距離是27．第13頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月14

顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算工作量將會(huì)十分龐大，而且其中包含著許多重復(fù)計(jì)算．

第二種方法即所謂“局部最優(yōu)路徑”法，是說(shuō)某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會(huì)致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1→v2→v5→

v9→

v10

，全程長(zhǎng)度是30；顯然，這種方法的結(jié)果常是錯(cuò)誤的．第14頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月15

第三種方法是動(dòng)態(tài)規(guī)劃方法，動(dòng)態(tài)規(guī)劃方法尋求該最短路問(wèn)題的基本思想是，首先將問(wèn)題劃分為4個(gè)階段，每次的選擇總是綜合后繼過(guò)程的一并最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。為了找出所有可能狀態(tài)的最優(yōu)后繼過(guò)程，動(dòng)態(tài)規(guī)劃方法是從過(guò)程的最后階段開(kāi)始考慮，然后逆著實(shí)際過(guò)程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。第15頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月16具體說(shuō)，此問(wèn)題先從v10開(kāi)始，因?yàn)関10是終點(diǎn)。再無(wú)后繼過(guò)程，故可以接著考慮第4階段上所有可能狀態(tài)v8,v9的最優(yōu)后續(xù)過(guò)程．因?yàn)閺膙8,v9

到v10的路線是唯一的，所以v8,v9

的最優(yōu)決策和最優(yōu)后繼過(guò)程就是到v10

，它們的最短距離分別是10和14。接著考慮階段3上可能的狀態(tài)v5,v6,v7到v10的最優(yōu)決策和最優(yōu)后繼過(guò)程．在狀態(tài)V5上，雖然到v8是6，到v9是5，但是1234（10）（14）第16頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月17綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決策是到v8,最優(yōu)后繼過(guò)程是v5→v8→v10，最短距離是16．同理，狀態(tài)v6的最優(yōu)決策是至v8

；v7的最優(yōu)決策是到v9

。同樣，當(dāng)階段3上所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)程，如v2的最優(yōu)決策是到v5,最優(yōu)路線是1234（10）（14）（16）（15）（17）第17頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月18v2→v5→v8→v10，最短距離是22…依此類推，最后可以得到從初始狀態(tài)v1的最優(yōu)決策是到v2最優(yōu)路線是v1→v2→v5→v8→v10，全程的最短距離是27。圖1中紅線表示最優(yōu)路線，每點(diǎn)上圓括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。1234（10）（14）（16）（15）（17）（22）（22）（21）（27）第18頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月19綜上所述可見(jiàn)，全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個(gè)比較復(fù)雜的問(wèn)題分解為一系列同類型的更易求解的子問(wèn)題，便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過(guò)程分為兩個(gè)階段，先按整體最優(yōu)的思想逆序地求出各個(gè)子問(wèn)題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個(gè)問(wèn)題的最優(yōu)策略和最優(yōu)路線。計(jì)算過(guò)程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工作量比窮舉法大為減少。第19頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月20

拾火柴游戲:桌子上放30根火柴,每人一次可拾起1－3根,誰(shuí)拾起最后一根火柴誰(shuí)輸,如果你先選擇,如何保證你能贏得游戲？

29－25－21－17－13－9－5－1動(dòng)態(tài)規(guī)劃與倒推求解:第20頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月21動(dòng)態(tài)規(guī)劃是解決多階段決策問(wèn)題的一種方法。所謂多階段決策問(wèn)題是指這樣的決策問(wèn)題：其過(guò)程可分為若干個(gè)相互聯(lián)系的階段，每一階段都對(duì)應(yīng)著一組可供選擇的決策，每一決策的選定即依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。ABCDE狀態(tài)A狀態(tài)B狀態(tài)C狀態(tài)D狀態(tài)E狀態(tài)F決策A決策D決策E當(dāng)每一階段的決策選定以后，就構(gòu)成一個(gè)決策序列，稱為一個(gè)決策B決策C策略，它對(duì)應(yīng)著一個(gè)確定的效果。多階段決策問(wèn)題就是尋找使此效果最好的策略。第21頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月22動(dòng)態(tài)規(guī)劃問(wèn)題實(shí)例例給定一個(gè)線路網(wǎng)絡(luò)，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要從A向F鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問(wèn)應(yīng)選擇什么路線，可使總距離最短？第22頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月239.2

動(dòng)態(tài)規(guī)劃的基本概念和基本原理一、基本概念階段：是指問(wèn)題需要做出決策的步數(shù)。階段總數(shù)常記為n，相應(yīng)的是n個(gè)階段的決策問(wèn)題。階段的序號(hào)常記為k，稱為階段變量，k=1,2,…,n.k即可以是順序編號(hào)也可以是逆序編號(hào)，常用順序編號(hào)。全過(guò)程；后部子過(guò)程。狀態(tài)：各階段開(kāi)始時(shí)的客觀條件，第k階段的狀態(tài)常用狀態(tài)變量表示，狀態(tài)變量取值的集合稱為狀態(tài)集合，用表示。例如，例中，第23頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月24AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6第24頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月25決策：是指從某階段的某個(gè)狀態(tài)出發(fā)，在若干個(gè)不同方案中做出的選擇。表示決策的變量，稱為決策變量，用表示例如：表示走到3階段,當(dāng)處于C2路口時(shí)，下一步奔D1.

時(shí)的允許決策集合記為，例如：策略:全過(guò)程策略p1n；子策略pkn；最優(yōu)策略。狀態(tài)轉(zhuǎn)移方程：是從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄乱浑A段某一狀態(tài)值的轉(zhuǎn)移規(guī)律，用表示。決策變量允許的取值范圍稱為允許決策集合，第k階段狀態(tài)為第25頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月26AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6第26頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月27指標(biāo)函數(shù)：分階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是指第k階段從狀態(tài)出發(fā)，采取決策時(shí)的效益，用表示。而過(guò)程指標(biāo)函數(shù)指從第k階段的某狀態(tài)出發(fā)，采取子策略時(shí)所得到的階段效益之和：最優(yōu)指標(biāo)函數(shù)：表示從第k階段狀態(tài)為時(shí)采用最佳策略到過(guò)程終止時(shí)的最佳效益。記為第27頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月28AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6第28頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月29其中opt可根據(jù)具體情況取max或min?；痉匠蹋捍藶橹鸲芜f推求和的依據(jù)，一般為：式中opt可根據(jù)題意取max或min.例如，例的基本方程為：第29頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月30即確定各個(gè)變量及方程函數(shù)1、階段變量2、狀態(tài)變量：選擇時(shí)要滿足兩個(gè)條件：①能正確描述受控過(guò)程的演變特性②要滿足無(wú)后效性無(wú)后效性：給定了某階段狀態(tài)，在這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響。3、決策變量4、列出狀態(tài)轉(zhuǎn)移方程5、指標(biāo)函數(shù)二、模型的構(gòu)成（因素）第30頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月31三、最優(yōu)化原理：最優(yōu)策略的任一后部子策略都是最優(yōu)的。無(wú)論以前狀態(tài)決策如何，從眼下直到最后的諸決策必構(gòu)成最優(yōu)子策略。動(dòng)態(tài)規(guī)劃應(yīng)用舉例例1最短路線問(wèn)題AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第31頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月32逆序遞推方程：（1）k=5時(shí)，狀態(tài)它們到F點(diǎn)的距離即為最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第32頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月33AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4時(shí)，狀態(tài)它們到F點(diǎn)需經(jīng)過(guò)中途點(diǎn)E，需一一分析從E到F的最短路：先說(shuō)從D1到F的最短路有兩種選擇：經(jīng)過(guò)E1,E2,比較最短。第33頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月34AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143這說(shuō)明由D1到F的最短距離為7，其路徑為相應(yīng)的決策為：第34頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月35這說(shuō)明由D2到F的最短距離為5，其路徑為相應(yīng)的決策為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第35頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月36AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距離為5，其路徑為相應(yīng)的決策為：第36頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月37（3）k=3時(shí)，狀態(tài)這說(shuō)明由C1到F的最短距離為12，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第37頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月38AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距離為10，相應(yīng)的決策為第38頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月39即由C3到F的最短距離為8，相應(yīng)的決策為即由C4到F的最短距離為9，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第39頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月40AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2時(shí)，狀態(tài)這說(shuō)明由B1到F的最短距離為13，相應(yīng)的決策為第40頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月41即由B2到F的最短距離為15，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第41頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月42AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（5）k=1時(shí)，只有一個(gè)狀態(tài)點(diǎn)A,則即由A到F的最短距離為17，相應(yīng)的決策為第42頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月43所以最優(yōu)路線為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按計(jì)算順序反推可得最優(yōu)決策序列：第43頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月44順序遞推方程：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1階段2階段3階段4階段5階段行走方向第k階段第44頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1時(shí)注意到：所以第45頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月46K=2時(shí)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第46頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月47K=3時(shí)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第47頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月48AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或類似地，可算出：第48頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月49最優(yōu)策略：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或第49頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月50最短路徑：最短路長(zhǎng)：注：順序解法與逆序解法無(wú)本質(zhì)區(qū)別，一般來(lái)說(shuō)，當(dāng)初始狀態(tài)給定時(shí)用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時(shí)用順序解法。若問(wèn)題給定了一個(gè)初始狀態(tài)與一個(gè)終止?fàn)顟B(tài)，則兩種方法均可使用。第50頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月51AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4，F(xiàn)）（3，F(xiàn)）（5，E1）（5，E2）（7，E1）（12，D1）（10，D2）（8，D2）（9，D3）（13，C2）（15，C3）（17，B1）作業(yè)：P2355.2（雙標(biāo)號(hào)法，順序逆序選一）第51頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月529.3背包問(wèn)題

一般的提法為：一旅行者攜帶背包去登山。已知他所能承受的背包重量的極限為a(千克)，現(xiàn)有n種物品可供他選擇裝入背包。第i種物品的單位重量為(千克)，其價(jià)值（可以是表明本物品對(duì)登山者的重要性指標(biāo)）是攜帶數(shù)量的函數(shù)（i=1，2，…n）.問(wèn)旅行者應(yīng)如何選擇攜帶物品的件數(shù)，以使總價(jià)值最大？此模型解決的是運(yùn)輸工具包括衛(wèi)星的最優(yōu)裝載問(wèn)題。其數(shù)學(xué)模型為：第52頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月53設(shè)為第i

種物品裝入的件數(shù)，則背包問(wèn)題可歸結(jié)為如下

形式的整數(shù)規(guī)劃模型：下面從一個(gè)例子來(lái)分析動(dòng)態(tài)規(guī)劃建模。例有一輛最大貨運(yùn)量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值如表4所示。應(yīng)如何裝載可使總價(jià)值最大？第53頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月54貨物編號(hào)i123單位重量（t）345單位價(jià)值ci456表4設(shè)第種貨物裝載的件數(shù)為則問(wèn)題可表為：階段k:將可裝入物品按1，2，3的順序排序，每段裝入一種物品，共劃分3個(gè)階段，即k=1,2,3.第54頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月55狀態(tài)變量：在第k段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重量。決策變量：裝入第k種物品的件數(shù)。狀態(tài)轉(zhuǎn)移方程：最優(yōu)指標(biāo)函數(shù)：在背包中允許裝入物品的總重量不超過(guò)kg，采取最優(yōu)策略只裝前k種物品時(shí)的最大使用價(jià)值。貨物1貨物2貨物3第55頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月56由此可得動(dòng)態(tài)規(guī)劃的順序遞推方程為：貨物1貨物2貨物3K=1時(shí)第56頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月57貨物1貨物2貨物3K=1時(shí)注意到：例如：時(shí)，其它計(jì)算結(jié)果見(jiàn)表5：第57頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月5801230123456789104×04×0

4×0

……4×0

4×1

4×04×14×24×04×14×24×3000448121200011233表5第58頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月59貨物1貨物2貨物3K=2時(shí)其中例如：時(shí)，第59頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月6001230123456789104×04×0

4×0

……4×0

4×1

4×04×14×24×04×14×24×30004812000123表5第60頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月61其它計(jì)算結(jié)果見(jiàn)表6：0120123456789105×0＋0

…

…

……5×0＋4

5×1＋0

…5×0＋125×1＋85×2＋00513011表6第61頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月62貨物1貨物2貨物3K=3時(shí)第62頁(yè)，課件共82頁(yè)，創(chuàng)作于2023年2月630120123456789105×0＋0

…

…

……5×0＋4

5×1＋0

…5×0＋125×1＋8