應(yīng)用運(yùn)籌學(xué)-6

1、動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的數(shù)學(xué)方法是解決多階段決策過程最優(yōu)化的數(shù)學(xué)方法動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃概述產(chǎn)生于上世紀(jì)產(chǎn)生于上世紀(jì)50年代，由年代，由R. Bellman 等人提出等人提出基本思想基本思想： 把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個(gè)加以解決；后逐個(gè)加以解決；“最優(yōu)性原理最優(yōu)性原理”動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的方法，在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生的方法，在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門有著廣泛的應(yīng)用，并獲得了顯著的效產(chǎn)及軍事等部門有著廣泛的應(yīng)用，并獲得了顯著的效果。在企業(yè)管理方面：果。在

2、企業(yè)管理方面：最優(yōu)路徑問題最優(yōu)路徑問題資源分配問題資源分配問題生產(chǎn)調(diào)度問題生產(chǎn)調(diào)度問題庫(kù)存問題庫(kù)存問題裝載問題裝載問題排序問題排序問題設(shè)備更新和生產(chǎn)過程最優(yōu)控制等設(shè)備更新和生產(chǎn)過程最優(yōu)控制等動(dòng)態(tài)規(guī)劃的基本方法動(dòng)態(tài)規(guī)劃的基本方法多階段決策過程及實(shí)例多階段決策過程及實(shí)例動(dòng)態(tài)規(guī)劃的基本概念和基本方程動(dòng)態(tài)規(guī)劃的基本概念和基本方程動(dòng)態(tài)規(guī)劃的最優(yōu)性原理動(dòng)態(tài)規(guī)劃的最優(yōu)性原理動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系多階段決策過程：多階段決策過程：在生產(chǎn)和科學(xué)實(shí)驗(yàn)中，有一類活動(dòng)過程，可將其分為若干個(gè)在生產(chǎn)和科學(xué)實(shí)驗(yàn)中，有一類活動(dòng)過程，可將其分為若干個(gè)互相聯(lián)系的階段，在其每一個(gè)階段都需要作出決策，從而使互

3、相聯(lián)系的階段，在其每一個(gè)階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果；整個(gè)過程達(dá)到最好的活動(dòng)效果；各階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀各階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展；態(tài)，又影響以后的發(fā)展；當(dāng)各階段決策確定后，就組成了一個(gè)決策序列，因而也就決當(dāng)各階段決策確定后，就組成了一個(gè)決策序列，因而也就決定了整個(gè)過程的一條活動(dòng)線路；定了整個(gè)過程的一條活動(dòng)線路；這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程，稱為多階段決策過程。過程，稱為多階段決策過程。一、多階段決策過程及實(shí)例一、多

4、階段決策過程及實(shí)例1狀態(tài)狀態(tài)決策決策2狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)最短路線問題最短路線問題多階段決策問題的實(shí)例多階段決策問題的實(shí)例2511214106104131112396581052C1C3D1AB1B3B2D2EC2求從求從A到到E的最短路徑的最短路徑機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題某種機(jī)器可以在高低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。某種機(jī)器可以在高低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器和投入生產(chǎn)的機(jī)器數(shù)量數(shù)量u1的關(guān)系為的關(guān)系為g=g(u1)這時(shí)，機(jī)器的年完好率為這時(shí)，機(jī)器的年完好率為a(0a1)在低

5、負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為的關(guān)系為h=h(u2)相應(yīng)的機(jī)器完好率為相應(yīng)的機(jī)器完好率為b(0ab1)假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1，要求制定一個(gè)，要求制定一個(gè)五年計(jì)劃，在每年開始時(shí)，決定如何重新分配完好的五年計(jì)劃，在每年開始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。品的總產(chǎn)量達(dá)到最高。多階段決策問題的實(shí)例多階段決策問題的實(shí)例( (續(xù)續(xù)) )階段階段把所給問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互

6、把所給問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序求解。聯(lián)系的階段，以便能按一定的次序求解。階段變量階段變量k狀態(tài)狀態(tài)每個(gè)階段開始所處的自然狀況或客觀條件，每個(gè)階段開始所處的自然狀況或客觀條件，它描述了研究問題的狀況，又稱不可控因素。一般指它描述了研究問題的狀況，又稱不可控因素。一般指某階段的出發(fā)位置；事實(shí)上，它既是該階段某支路的某階段的出發(fā)位置；事實(shí)上，它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。起點(diǎn)，又是前一階段某支路的終點(diǎn)。Sk 第第k階段的狀態(tài)變量，階段的狀態(tài)變量，可達(dá)狀態(tài)集合可達(dá)狀態(tài)集合無(wú)后效性無(wú)后效性(馬爾科夫性馬爾科夫性)如果某階段狀態(tài)給定后，則在這個(gè)階

7、如果某階段狀態(tài)給定后，則在這個(gè)階段以后過程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響。段以后過程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響。決策決策當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)，可作出當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)，可作出不同的決定，從而確定下一階段的狀態(tài)?；蚍Q為控制。不同的決定，從而確定下一階段的狀態(tài)?；蚍Q為控制。決策變量決策變量uk(sk) 第第k階段當(dāng)狀態(tài)處于階段當(dāng)狀態(tài)處于sk時(shí)的決策變量時(shí)的決策變量允許決策集合允許決策集合Dk(sk) 第第k階段從狀態(tài)階段從狀態(tài)sk出發(fā)的允許決策集合出發(fā)的允許決策集合uk(sk) Dk(sk) ， 或或uk(sk)是一多值函數(shù)是一多值函數(shù) 2.1動(dòng)態(tài)規(guī)劃的基本概

8、念動(dòng)態(tài)規(guī)劃的基本概念策略策略一個(gè)按順序排列的決策組成的一個(gè)按順序排列的決策組成的集合。集合。k子過程子過程由過程的第由過程的第k階段開始到終止?fàn)顟B(tài)階段開始到終止?fàn)顟B(tài)為止的過程。為止的過程。k子過程策略子過程策略pk,n(sk)由由k子過程每段的決策子過程每段的決策按順序排列組成的決策函數(shù)序列按順序排列組成的決策函數(shù)序列uk(sk), un(sn)，即，即pk,n(sk)= uk(sk), un(sn)允許策略集合允許策略集合P最優(yōu)策略最優(yōu)策略策略策略狀態(tài)移動(dòng)方程狀態(tài)移動(dòng)方程確定過程由一個(gè)狀態(tài)確定過程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程。到另一個(gè)狀態(tài)的演變過程。若給定若給定第第k階段狀態(tài)變量階段狀態(tài)

9、變量sk值，如果該階段值，如果該階段的決策變量的決策變量uk一經(jīng)確定，第一經(jīng)確定，第k+1階段狀態(tài)變階段狀態(tài)變量量sk+1的值也完全確定的值也完全確定sk+1 = Tk(sk , uk)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程指標(biāo)函數(shù)指標(biāo)函數(shù)用來(lái)衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)值指用來(lái)衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)值指標(biāo)。它是定義在全過程和所有后部子過程上確定的數(shù)標(biāo)。它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。用量函數(shù)。用Vk,n表示表示Vk,n= Vk,n(sk , uk , sk+1, sn+1)k=1,2,n.Vk,n應(yīng)具有可分離性，并滿足遞推關(guān)系，即應(yīng)具有可分離性，并滿足遞推關(guān)系，即 Vk,n(sk ,

10、uk , sk+1, sn+1)= k (sk , uk , Vk+1,n (sk+1, sn+1)常見的指標(biāo)形式常見的指標(biāo)形式最優(yōu)值函數(shù)，最優(yōu)值函數(shù)，fk(sk)指標(biāo)函數(shù)與最優(yōu)值函數(shù)指標(biāo)函數(shù)與最優(yōu)值函數(shù) nkjjjjnkkkknkusvsususV,111, nkkkknkVusvV,1, nkjjjjnkkkknkusvsususV,111, nkkkknkVusvV,1, 111,1 nkkkknkuuukksususVoptsfnkk最短路線的一個(gè)特征最短路線的一個(gè)特征如果由起點(diǎn)如果由起點(diǎn)A經(jīng)過經(jīng)過P點(diǎn)和點(diǎn)和H點(diǎn)而到達(dá)終點(diǎn)點(diǎn)而到達(dá)終點(diǎn)G是一條最短路線，則是一條最短路線，則由點(diǎn)由點(diǎn)P出發(fā)

11、經(jīng)過出發(fā)經(jīng)過H點(diǎn)到達(dá)終點(diǎn)點(diǎn)到達(dá)終點(diǎn)G的這條子路線，對(duì)于從點(diǎn)的這條子路線，對(duì)于從點(diǎn)P出發(fā)出發(fā)到達(dá)終點(diǎn)到達(dá)終點(diǎn)G的所有可能選擇的不同路線來(lái)說(shuō)，必定也是最短路的所有可能選擇的不同路線來(lái)說(shuō)，必定也是最短路線。線。2.2動(dòng)態(tài)規(guī)劃的基本思想和基本方程動(dòng)態(tài)規(guī)劃的基本思想和基本方程2511214106104131112396581052C1C3D1AB1B3B2D2EC2AB2 C1 D1 E尋找最短路線的方法尋找最短路線的方法從最后一段開始，由后向前逐步遞推，求出各點(diǎn)到終點(diǎn)的最短從最后一段開始，由后向前逐步遞推，求出各點(diǎn)到終點(diǎn)的最短路線，最后求得由起點(diǎn)到終點(diǎn)的最短路線。路線，最后求得由起點(diǎn)到終點(diǎn)的最短路線。

12、上例的求解上例的求解尋找最短路線尋找最短路線最短路線：最短路線：AB2 C1 D1 E 2,542414 DfDfk時(shí)，當(dāng) 12,782953min22,111,1min33323434313 CfCfDfDCdDfDCdCfk時(shí)，當(dāng) 19,14201210714812min33,122,111,1min2322232323212 BfBfCfCBdCfCBdCfCBdBfk時(shí)，當(dāng) 19191145202min33,22,11,min12121211 BfBAdBfBAdBfBAdAfk時(shí)，當(dāng)將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及

13、定義最優(yōu)指標(biāo)函數(shù)，從而把問題化成一族決策變量及定義最優(yōu)指標(biāo)函數(shù)，從而把問題化成一族同類問題的子問題，然后逐個(gè)求解；同類問題的子問題，然后逐個(gè)求解；求解時(shí)從邊界條件開始，逆求解時(shí)從邊界條件開始，逆(或順或順)過程行進(jìn)方向，逐過程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個(gè)子問題求解時(shí)，都要使用它前段遞推尋優(yōu)。在每一個(gè)子問題求解時(shí)，都要使用它前面已得出的最優(yōu)結(jié)果，最后一個(gè)子問題的最優(yōu)解，就面已得出的最優(yōu)結(jié)果，最后一個(gè)子問題的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。是整個(gè)問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來(lái)各段分開，又把動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來(lái)各段分開，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法

14、，當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。最優(yōu)選擇一般是不同的。動(dòng)態(tài)規(guī)劃方法的基本思想動(dòng)態(tài)規(guī)劃方法的基本思想動(dòng)態(tài)規(guī)劃的基本方程是遞推逐段求解的根據(jù)，其一般動(dòng)態(tài)規(guī)劃的基本方程是遞推逐段求解的根據(jù)，其一般形式為形式為指標(biāo)函數(shù)為階段指標(biāo)和形式，即指標(biāo)函數(shù)為階段指標(biāo)和形式，即動(dòng)態(tài)規(guī)劃的基本方程動(dòng)態(tài)規(guī)劃的基本方程 01 ,1,1111nnkkkkksDukksfnnksfusvoptsfkkk則基本方程為則基本方程為 nkjjjjnkusvV,指標(biāo)函數(shù)為階段指標(biāo)積形式，即指標(biāo)函數(shù)為階

15、段指標(biāo)積形式，即 nkjjjjnkusvV, 11 ,1,1111nnkkkkksDukksfnnksfusvoptsfkkk則基本方程為則基本方程為逆序解法逆序解法(后向動(dòng)態(tài)規(guī)劃方法后向動(dòng)態(tài)規(guī)劃方法)尋優(yōu)的方向與多階段決策過程的實(shí)際行進(jìn)方向相反，從最尋優(yōu)的方向與多階段決策過程的實(shí)際行進(jìn)方向相反，從最后一段開始計(jì)算逐段前推，求得全過程的最優(yōu)策略。后一段開始計(jì)算逐段前推，求得全過程的最優(yōu)策略。順序解法順序解法(前向動(dòng)態(tài)規(guī)劃方法前向動(dòng)態(tài)規(guī)劃方法)尋優(yōu)的方向與多階段決策過程的實(shí)際行進(jìn)方向相同，計(jì)算尋優(yōu)的方向與多階段決策過程的實(shí)際行進(jìn)方向相同，計(jì)算時(shí)從第一段開始逐段向后遞推，計(jì)算后一段要用到前一段時(shí)從

16、第一段開始逐段向后遞推，計(jì)算后一段要用到前一段的求優(yōu)結(jié)果，最后一段的計(jì)算結(jié)果就是全過程的最優(yōu)結(jié)果。的求優(yōu)結(jié)果，最后一段的計(jì)算結(jié)果就是全過程的最優(yōu)結(jié)果。逆序解法和順序解法逆序解法和順序解法q動(dòng)態(tài)規(guī)劃的最優(yōu)性原理動(dòng)態(tài)規(guī)劃的最優(yōu)性原理q作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過去的狀態(tài)和決策如何，對(duì)前面的無(wú)論過去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。須構(gòu)成最優(yōu)策略。q一個(gè)最優(yōu)策略的子策略總是最優(yōu)的。一個(gè)最優(yōu)策略的子策略總是最優(yōu)的。q一點(diǎn)說(shuō)明一點(diǎn)說(shuō)明q最優(yōu)性原理不是對(duì)任何決策過程都普遍成

17、最優(yōu)性原理不是對(duì)任何決策過程都普遍成立的。立的。3.1最優(yōu)性原理最優(yōu)性原理動(dòng)態(tài)規(guī)劃應(yīng)用舉例動(dòng)態(tài)規(guī)劃應(yīng)用舉例資源分配問題資源分配問題背包問題背包問題排序問題排序問題貨郎擔(dān)問題貨郎擔(dān)問題一、一、資源分配問題資源分配問題所謂分配問題，就是將數(shù)量一定的一種或若干種資源，所謂分配問題，就是將數(shù)量一定的一種或若干種資源，恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，而使目標(biāo)函數(shù)為最優(yōu)。恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，而使目標(biāo)函數(shù)為最優(yōu)。問題：設(shè)有某種原料，總數(shù)量為問題：設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)，用于生產(chǎn)n種產(chǎn)品。若分種產(chǎn)品。若分配數(shù)量配數(shù)量 xi 用于生產(chǎn)第用于生產(chǎn)第i種產(chǎn)品，其收益為種產(chǎn)品，其收益為 gi(xi) 。問

18、應(yīng)如何分。問應(yīng)如何分配，才能使生產(chǎn)配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？種產(chǎn)品的總收入最大？ nixaaxxgziniiniii, , ,2 2, ,1 10 00 0m ma ax x1 11 1非線性規(guī)劃模型非線性規(guī)劃模型動(dòng)態(tài)規(guī)劃模型：動(dòng)態(tài)規(guī)劃模型：設(shè)狀態(tài)變量設(shè)狀態(tài)變量sk用于生產(chǎn)第用于生產(chǎn)第k種產(chǎn)品至第種產(chǎn)品至第n種產(chǎn)品的原材料數(shù)量種產(chǎn)品的原材料數(shù)量決策變量決策變量uk用于生產(chǎn)第用于生產(chǎn)第k種產(chǎn)品的原材料數(shù)量，種產(chǎn)品的原材料數(shù)量， uk = xk nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkkmax)(1,.,1,)(max10資源分配問題資源分配問題舉例舉例某種機(jī)器可以

19、在高低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下生產(chǎn)某種機(jī)器可以在高低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為的產(chǎn)量函數(shù)為g=8u1，其中，其中u1為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為為a=0.7。在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)。在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)h =5u2 ，其中，其中u2為投入生為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1 =1000臺(tái)，試問每年如何安臺(tái)，試問每年如何安排機(jī)器在高低負(fù)荷下的生產(chǎn)，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。排機(jī)器在高低負(fù)荷下的生產(chǎn)，使在五年內(nèi)產(chǎn)品的總產(chǎn)量

20、達(dá)到最高。構(gòu)建動(dòng)態(tài)規(guī)劃模型：構(gòu)建動(dòng)態(tài)規(guī)劃模型：設(shè)階段序數(shù)設(shè)階段序數(shù)k表示年度表示年度狀態(tài)變量狀態(tài)變量sk第第k年度初擁有的完好機(jī)器數(shù)量年度初擁有的完好機(jī)器數(shù)量決策變量決策變量uk第第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量， sk uk 為為k為該年度中分配低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量；為該年度中分配低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量；狀態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為sk+1 = 0.7uk +0.9(sk-uk ) k=1,2,5指標(biāo)函數(shù)指標(biāo)函數(shù) 515,1,kkkkusvV 5 55 55 55 55 51 10 05 58 8m ma ax x) )( (1 1, ,. . . .

21、, ,4 4, ,9 9. .0 07 7. .0 05 58 8m ma ax x5 55 5ususfkusufususfsukkkkkkksukkkk其中其中vk=8uk+5(sk-uk)二維資源分配問題二維資源分配問題設(shè)有兩種原料，數(shù)量各為設(shè)有兩種原料，數(shù)量各為a和和b，需要分配用于生產(chǎn)，需要分配用于生產(chǎn)n種產(chǎn)品。若種產(chǎn)品。若第一種原材料以數(shù)量第一種原材料以數(shù)量 xi 為單位，第二種原材料以數(shù)量為單位，第二種原材料以數(shù)量 yi 為單位，為單位，用于生產(chǎn)第用于生產(chǎn)第i種產(chǎn)品，其收益為種產(chǎn)品，其收益為 gi(xi ,yi) 。問應(yīng)如何分配這兩種原。問應(yīng)如何分配這兩種原料，才能使生產(chǎn)料，才能

22、使生產(chǎn)n種產(chǎn)品的總收入最大？種產(chǎn)品的總收入最大？ 。 且且為為整整數(shù)數(shù), ,. . . ., ,2 2, ,1 10 0, ,0 0, ,m ma ax x1 11 11 1niyxbyaxyxgziiniiniiniiii非線性規(guī)劃模型非線性規(guī)劃模型二維資源分配問題的動(dòng)態(tài)規(guī)劃模型二維資源分配問題的動(dòng)態(tài)規(guī)劃模型設(shè)狀態(tài)變量設(shè)狀態(tài)變量 : 表示分配用于生產(chǎn)第表示分配用于生產(chǎn)第k種產(chǎn)品至第種產(chǎn)品至第n種產(chǎn)品的第一種原材料的單位種產(chǎn)品的第一種原材料的單位數(shù)量數(shù)量 表示分配用于生產(chǎn)第表示分配用于生產(chǎn)第k種產(chǎn)品至第種產(chǎn)品至第n種產(chǎn)品的第二種原材料的單位種產(chǎn)品的第二種原材料的單位數(shù)量數(shù)量決策變量決策變量(x

23、k,yk):xk 表示分配用于生產(chǎn)第表示分配用于生產(chǎn)第k種產(chǎn)品的第一種原材料的單位數(shù)量種產(chǎn)品的第一種原材料的單位數(shù)量yk 表示分配用于生產(chǎn)第表示分配用于生產(chǎn)第k種產(chǎn)品的第二種原材料的單位數(shù)量種產(chǎn)品的第二種原材料的單位數(shù)量狀態(tài)轉(zhuǎn)換關(guān)系：狀態(tài)轉(zhuǎn)換關(guān)系： kykykkxkxkyssxss 11 1,.,1,max,max,1100nkysxsfyxgssfssgssfkykkxkkkkksysxykxkkynxnnynxnnykkxkk ykxkss, xks yks逆推關(guān)系：逆推關(guān)系：二、背包問題二、背包問題有一個(gè)人帶一個(gè)背包上山，其可攜帶物品重量的限度有一個(gè)人帶一個(gè)背包上山，其可攜帶物品重量的限

24、度為為a公斤。設(shè)有公斤。設(shè)有n種物品可供他選擇裝入背包中，這種物品可供他選擇裝入背包中，這n種物品的編號(hào)為種物品的編號(hào)為1,2,n。已知第。已知第i種物品每件種物品每件 wi 公斤，公斤，在上山過程中的作用在上山過程中的作用(價(jià)值價(jià)值)是攜帶數(shù)量是攜帶數(shù)量 xi 的函數(shù)的函數(shù) ci(xi) 。問此人應(yīng)如何選擇攜帶的物品問此人應(yīng)如何選擇攜帶的物品(各幾件各幾件)，使所起作用，使所起作用(總價(jià)值總價(jià)值)最大？最大？設(shè)設(shè)xi第第i種物品的裝入件數(shù)，則該問題的數(shù)學(xué)模型為種物品的裝入件數(shù)，則該問題的數(shù)學(xué)模型為 nixaxwtsxcfiniiiniii,.,2, 10.max11且為整數(shù)背包問題的動(dòng)態(tài)規(guī)劃

25、求解背包問題的動(dòng)態(tài)規(guī)劃求解設(shè)按可裝入物品的設(shè)按可裝入物品的n種劃分為種劃分為n個(gè)階段；個(gè)階段；狀態(tài)變量狀態(tài)變量 sk 表示所裝的第表示所裝的第1種物品至第種物品至第k種物品的總重種物品的總重量；量；決策變量決策變量 xk 表示裝入第表示裝入第k種物品的件數(shù)，則狀態(tài)轉(zhuǎn)移種物品的件數(shù)，則狀態(tài)轉(zhuǎn)移方程為方程為 sk-1 =sk xkwk動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為 nkxwsfxcsfxcsfkkkkkkwsxkkwsxkkk 2,maxmax1/,.,1,011/,.,1,011111背包問題舉例背包問題舉例有一輛最大貨運(yùn)量為有一輛最大貨運(yùn)量為10t的卡車，用以裝載三種貨物，的

26、卡車，用以裝載三種貨物，每種貨物的單位重量及相應(yīng)單價(jià)如下表。問應(yīng)如何裝每種貨物的單位重量及相應(yīng)單價(jià)如下表。問應(yīng)如何裝載可使總價(jià)值最大？載可使總價(jià)值最大？設(shè)設(shè)xi第第i種物品的裝入件數(shù)，則該問題的數(shù)學(xué)模型為種物品的裝入件數(shù)，則該問題的數(shù)學(xué)模型為 3,2, 1010543.654max321321ixxxxtsxxxzi且為整數(shù)動(dòng)態(tài)規(guī)劃求解動(dòng)態(tài)規(guī)劃求解當(dāng)k=1時(shí)，當(dāng)當(dāng)k=2時(shí)，時(shí)， 3/44max113011111sxsfxsx 為整數(shù) 2212402245max222xsfxsfxsx 為整數(shù)動(dòng)態(tài)規(guī)劃求解動(dòng)態(tài)規(guī)劃求解(續(xù)續(xù))當(dāng)k=3時(shí)， 13012,56,13max012,56,10max510

27、6max102223232,1,033 fffxfxfx0, 1, 2*3*2*1 xxx最優(yōu)策略：三、排序問題三、排序問題設(shè)有設(shè)有n個(gè)工件需要在機(jī)床個(gè)工件需要在機(jī)床A,B上加工，每個(gè)工件都必須上加工，每個(gè)工件都必須經(jīng)過先經(jīng)過先A而后而后B的兩道加工工序。以的兩道加工工序。以ai、bi分別表示工分別表示工件件i(1 i n)在在A,B上的加工時(shí)間。問應(yīng)如何在兩機(jī)床上上的加工時(shí)間。問應(yīng)如何在兩機(jī)床上安排各工件加工的順序，使在機(jī)床安排各工件加工的順序，使在機(jī)床A上加工第一工件上加工第一工件開始到在機(jī)床開始到在機(jī)床B上將最后一個(gè)工件加工完為止，所用上將最后一個(gè)工件加工完為止，所用的加工時(shí)間最少？的加

28、工時(shí)間最少？結(jié)論：結(jié)論：最優(yōu)排序方案只能在機(jī)床最優(yōu)排序方案只能在機(jī)床A,B上加工順序相同上加工順序相同的排序中尋找。的排序中尋找。當(dāng)加工順序確定后，工件在當(dāng)加工順序確定后，工件在A上加工時(shí)沒有等待時(shí)間，而在上加工時(shí)沒有等待時(shí)間，而在B上常常需要等待。上常常需要等待。尋求最優(yōu)排序方案：盡量減少尋求最優(yōu)排序方案：盡量減少B上的等待時(shí)間，這樣才能使總上的等待時(shí)間，這樣才能使總加工時(shí)間最短。加工時(shí)間最短。最優(yōu)排序規(guī)則最優(yōu)排序規(guī)則作工件的加工時(shí)間的工時(shí)矩陣作工件的加工時(shí)間的工時(shí)矩陣 nnbbbaaaM2121在工時(shí)矩陣在工時(shí)矩陣M中找出最小元素中找出最小元素(若最小的不止一個(gè)，可若最小的不止一個(gè)，可任選

29、其一任選其一)；若它在上行，則將相應(yīng)的工件排在最前；若它在上行，則將相應(yīng)的工件排在最前位置；若它在下行，則將相應(yīng)的工件排在最后位置；位置；若它在下行，則將相應(yīng)的工件排在最后位置；將排定位置的工件所對(duì)應(yīng)的列從將排定位置的工件所對(duì)應(yīng)的列從M中劃掉，然后對(duì)余中劃掉，然后對(duì)余下的工件重復(fù)按下的工件重復(fù)按2)進(jìn)行。但此時(shí)的最前位置進(jìn)行。但此時(shí)的最前位置(或最后位或最后位置置)是在已排定的工件之后是在已排定的工件之后(或之前或之前)。如此繼續(xù)，直至。如此繼續(xù)，直至把所有工件都排完為止。把所有工件都排完為止。排序問題舉例排序問題舉例設(shè)有設(shè)有5個(gè)工件需要在機(jī)床個(gè)工件需要在機(jī)床A,B上加工，工件的加工順上加工，

30、工件的加工順序是先序是先A后后B。每個(gè)工件所需加工時(shí)間如下表。問如。每個(gè)工件所需加工時(shí)間如下表。問如何安排加工的順序，使機(jī)床連續(xù)加工完所有工件的何安排加工的順序，使機(jī)床連續(xù)加工完所有工件的加工總時(shí)間最少？并計(jì)算最少加工時(shí)間。加工總時(shí)間最少？并計(jì)算最少加工時(shí)間。475354743272631BA加工時(shí)間加工時(shí)間機(jī)機(jī)床床工件號(hào)碼工件號(hào)碼排序問題求解排序問題求解工件的加工時(shí)間的工時(shí)矩陣工件的加工時(shí)間的工時(shí)矩陣 4372675473M25143工件加工順序：工件加工順序：13 5 4 2總加工時(shí)間：總加工時(shí)間：28小時(shí)小時(shí)四、貨郎擔(dān)問題四、貨郎擔(dān)問題有一個(gè)串村走戶的的賣貨郎，他從某個(gè)村莊出發(fā)，通有一個(gè)

31、串村走戶的的賣貨郎，他從某個(gè)村莊出發(fā)，通過若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村過若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村莊，問應(yīng)如何選擇行走路線，能使總的行程最短。莊，問應(yīng)如何選擇行走路線，能使總的行程最短。設(shè)有設(shè)有n個(gè)城市，以個(gè)城市，以1、2、n表示之。表示之。dij 表示從表示從i城城到到j(luò)城的距離。一個(gè)推銷員從城市城的距離。一個(gè)推銷員從城市1出發(fā)到其他每個(gè)城出發(fā)到其他每個(gè)城市去一次且僅僅一次，然后回到城市市去一次且僅僅一次，然后回到城市1。問他如何選擇。問他如何選擇行走路線，使總的行程最短？行走路線，使總的行程最短？規(guī)定推銷員從城市規(guī)定推銷員從城市1出發(fā)，設(shè)推銷員走到出發(fā)，設(shè)推銷員走到i城，記城，記Ni=2,3,i-1,i+1,n表示由表示由1城到城到i城的中間城市集合。城的中間城市集合。S表示到達(dá)表示到達(dá)i城之前中途所經(jīng)過的城市的集合，則有城之前中途所經(jīng)過的城市的集合，則有S Ni貨郎擔(dān)