【正文】 (6)基本方程： 解：建立動態(tài)規(guī)劃模型 K=4 u4=4s4 s4 0 1 2 3 f4(s4) 7 6 u4(s4) 4 3 2 1 })()({m in)( 4444 sEucsf ??K=3 s3={0,1,2,3} })()()({m i n)( 33343333 gusfsEucsf ?????且為整數(shù))6,5,6m i n (}2,0m a x { 3333 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 s3 u3(s3) C+E+f4 f3(s3) u3 *(s3) 0)(1 , 2 , 3 , 4k })()()({m i n)(551??????? ?sfgusfsEucsf kkkkkkkks3 0 1 2 3 u3(s3) 2 3 4 5 1 2 3 4 0 1 2 3 0 1 2 C+E+f4 12 13 12 13 8 12 8 12 f3(s3) 12 8 8 u3 *(s3) 2 1 0 0 K=3 s3={0,1,2,3} })()()({m i n)( 33343333 gusfsEucsf ?????且為整數(shù))6,5,6m i n (}2,0m a x { 3333 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 K=2 s2={0,1,2,3} })()()({m i n)( 22232222 gusfsEucsf ?????且為整數(shù))9,6,6m i n (}3,0m a x { 2233 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 s2 u2(s2) C+E+f3 f2(s2) u2 *(s2) 0)(1 , 2 , 3 , 4k })()()({m i n)(551??????? ?sfgusfsEucsf kkkkkkkks2 0 1 2 3 u2(s2) 3 4 5 6 2 3 4 5 1 2 3 4 0 1 2 3 C+E+f3 18 16 17 18 17 15 16 17 f2(s2) 16 15 u2 *(s2) 5 4 3 0 K=2 s2={0,1,2,3} })()()({m i n)( 22232222 gusfsEucsf ?????且為整數(shù))9,6,6m i n (}3,0m a x { 2233 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 s1 0 u1(s1) 2 3 4 5 C+f2 21 22 f1(s1) 21 u1 *(s1) 2 K=1 s1={0} })()()({m i n)( 11121111 gusfsEucsf ?????且為整數(shù)52 1 ?? ui（月） 1 2 3 4 gi（需求） 2 3 2 4 可得最佳生產(chǎn)計劃為：第一個月生產(chǎn) 2單位，第二個月生產(chǎn) 5單位，第三個月不生產(chǎn)，第四個月生產(chǎn) 4單位。 (3)決策變量 :uk為第 k個月的生產(chǎn)量。 i（月） 1 2 3 4 gi（需求） 2 3 2 4 0)(1 , 2 , 3 , 4k })()()({m i n)(551??????? ?sfgusfsEucsf kkkkkkkk(1)階段：每個月為一個階段， k＝ 1， 2， 3， 4。試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下總費用最小。 動態(tài)規(guī)劃在經(jīng)濟管理中應(yīng)用 二、生產(chǎn)經(jīng)營問題 —生產(chǎn)與存貯問題 在生產(chǎn)和經(jīng)營管理中．經(jīng)常遇到如何合理地安排生產(chǎn)計劃、采購計劃以及倉庫的存貨計劃和銷售計劃，使總效益最高的問題。 4狀態(tài)轉(zhuǎn)移方程 ： sk=sk+1xk 5允許決策集合 為： Dk(sk+1)＝ {xk|o≤xk ≤sk+1]， xk為整數(shù) } 6最優(yōu)指標函數(shù) fk(sk+1)表示在前 k段時銷售點的總收效益。 2狀態(tài)變量 sk+1：在第 k段開始時，允許設(shè)點個數(shù)。 0)(n1 , 2 , . . . ,k })()({m a x)(1011]/[,...,1,01????? ????sfxasfxcsf kkkkkkasrkk kkk練 習(xí) 題 某公司打算在三個不同的地區(qū)設(shè)置 4個銷售點，根據(jù)市場預(yù)測部門估計，在不同的地區(qū)設(shè)置不同數(shù)星的銷售店，每月可得到的利潤如表所示。 例 : 有一輛最大貨運量為 10噸的卡車，用以裝載 3種貨物．每種貨物的單位重量及相應(yīng)單位價值如表所示。 6最優(yōu)指標函數(shù) fk(sk+1)表示在背包中允許裝入物品的總重量不超過 sk+1千克，采用最優(yōu)策略只裝前 k種物品時的最大使用價值。 3決策變量 xk：裝入第 k種物品的件數(shù)。 背包問題的整數(shù)規(guī)劃模型 背包問題的動態(tài)規(guī)劃模型 1階段 k： 將可裝入物品按 1， 2， ...， n排序，每段裝 一種物品、共劃分為 n個階段，即 k＝ 1， 2， ...， n。 基本方程為： ????????? ???? ?0)(3,2,1)}()({m a x)(101011sfksfxgsf kkkksxkk kk動態(tài)規(guī)劃在經(jīng)濟管理中應(yīng)用 一、背包問題 背包問題的一般提法是：一位旅行者攜帶背包去登山、已知他所能承受的背包重量限度為 a千克，現(xiàn)有 n種物品可供他選擇裝入背包。 端點取得極大值只可能在10010*112 ????? xss0*1 ?x所以2/92 ?s滿足條件1010010,0 3*3*223*2 ???????? s；xxssx所以最優(yōu)投資方案為全部資金投于第 3個項目，可得最大收益 200萬元。s??端點取得極大值只可能在2/9)()0( 2222 ?? ssff 得當(dāng)2*22222*22222),()0(2/90),()0(2/9sxsf，fsxsf，fs??????時當(dāng)時當(dāng)狀態(tài)轉(zhuǎn)移方程： sk+1＝ skxk ????????? ????0)(1,2,3)}()({m a x)(44110sfksfxgsf kkkksxkk kk＝ 1時 })(4{m a x)(221011 11 sfxsf sx ?? ??2222*2 9)( ss，fsx ?? 時當(dāng)11110011110019}59{m a x}994{m a x)10(11sxsxsxfxx????????2*22222*22222),()0(2/90),()0(2/9sxsf，fsxsf，fs??????時當(dāng)時當(dāng)10010112 ????? xss。 狀態(tài)轉(zhuǎn)移方程： sk+1＝ skxk 最優(yōu)指標函數(shù) fk(sk)：當(dāng)可投資金數(shù)為 sk時，投資第 k3項所得的最大收益數(shù)。下面分別用逆序解法求解。 例 5： 某公司有資金 10萬元．若投資于項目 i(i＝ 1， 2， 3）的投資額為 xi時，其收益分別為 g1(x1)＝ 4x1,g2(x2)＝ 9x2,g3(x3)＝2x32，問應(yīng)如何分配投資數(shù)額才能使總收益最大 ? 2．連續(xù)變量的解法 當(dāng)動態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據(jù)方程的具體情況靈活選取求解方法，如經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數(shù)值計算方法等。如例 4的求解方法就是分段窮舉算法，由于每段的狀態(tài)變量和決策變量離散取值個數(shù)較少，所以動態(tài)規(guī)劃的窮舉法要比一般的窮舉法有效。 圖中兩點之間連線上的數(shù)字表示兩地間的距離，現(xiàn)在要選擇一條鋪設(shè)管道的路線使總長度最短。 fn(sn+1)是整體最優(yōu)函數(shù)值。 最優(yōu)路線為： A－ B1－ C2－ D2－ E2－ F 順序解法的 基本方程： ),(0)(5,4,3,2,1)}(),({m i n)(110111kkkkkkkkkukkusTssfksfusvsfk??????????????逆序解法與順序解法建模的不同點 1．狀態(tài)轉(zhuǎn)移方式不同 sk+1=Tk(sk,uk) sk=Tk(sk+1,uk) 2．指標函數(shù)的定義不同 逆序解法中，我們定義最優(yōu)指標函數(shù) fk(sk)表示第 k段從狀態(tài) sk出發(fā)，到終點后部子過程最優(yōu)效益值， f1(s1)是整體最優(yōu)函數(shù)值。 順序解法的尋優(yōu)方向同于過程的行進方向，計算時從第一段開始逐段向后遞推，計算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計算的結(jié)果就是全過程的最優(yōu)結(jié)果。 根據(jù)題意明確指標函數(shù) vk,n最優(yōu)指標函數(shù) fk(sk)以及 k階段指標 vk(sk,uk)的含義，并正確列出最優(yōu)指標函數(shù)的遞推關(guān)系及邊界條件 (即基本方程 )。即由第 k階段的狀態(tài) sk出發(fā)的后部子過程，可以看作是一個以 sk為初始狀態(tài)的獨立過程。 基本方程為： 模型 ?????111 10xus?????? ?kkkkkxuuss 1??? 33, )( 函數(shù) 指 標kiiik xgV????????? ????0)(1,2,3)}()({m a x)(44110sfksfxgsf kkkksxkk k 建立動態(tài)規(guī)劃模型的要點 分析題意，識別問題的多