运筹学第10章-动态规划.

1、PagePagePage:1管理运筹学管理运筹学动态规划动态规划PagePagePage:2 综综 述述 动态规划是解决多阶段决策过程最优化问题的一种方法。动态规划所研究的对象是多阶段决策问题。它把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题。 PagePagePage:3 综综 述述 多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。PagePagePage:4 综

2、综 述述 动态规划可以解决管理中的最短路径、装载问题、库存问题、资源分配、生产过程最优化问题。PagePagePage:51.1.多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 最短路径问题:PagePagePage:6最短路径问题的应用最短路径问题的应用 BACBDBCDEC212312312511214106104131211396581052找出找出A到到E的最短路径的最短路径 PagePagePage:7阶段划分阶段划分BACBDBCDEC212312312511214106104131211396581052IIVIIIIIPagePagePage:8将将A A到到E E的

3、最短路径问题，转化为三个性质的最短路径问题，转化为三个性质完全相同，但规模较小的子问题完全相同，但规模较小的子问题 求解策略求解策略记记S SE E(x(x) )为节点为节点x x到到E E的最短路的最短路)(min)(,iBAiBSdASi)(min)(,jCBjiCSdBSji)(min)(,kDCkjDSdCSkj)(kDSPagePagePage:9求解求解S(DS(D1 1)=5)=5，S(DS(D2 2)=2)=2S CS DS DCD()min()()min,112113935928S CS DS DCD()min()()min,212226565527S CS DS DCD()

4、min()()min,312328108510212S(C1)=8；S(C2)=7； S(C3)=12D1ED2EPagePagePage:10S BS CS CS CBC()min()()()min,112311121410128147101220S BS CS CS CBC()min()()()min,21232161046810741214S BS CS CS CBC()min()()()min,31233213121113812711 1219S(C1)=8；S(C2)=7； S(C3)=12PagePagePage:11S(B1)=20；S(B2)=14；S(B3)=19S AS B

5、S BS BAB( )min()()()min,251220514119191232PagePagePage:12最优解最优解BACBDBCDEC212312312511214106104131211396581052052871220141919PagePagePage:132. 2. 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理一、基本概念一、基本概念1.阶段阶段:用动态规划方法求解问题时用动态规划方法求解问题时,首先将首先将问题的全过程适当地分成若干个互相联系问题的全过程适当地分成若干个互相联系的阶段的阶段,以便能按一定的次序去解以便能按一定的次序去解.划分的标划分的标准

6、是时间或空间准是时间或空间.PagePagePage:142. 2. 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理2. 状态状态. 状态是指每个阶段开始时所处的自然状状态是指每个阶段开始时所处的自然状态或客观条件态或客观条件.在例在例1中某个阶段的状态就是中某个阶段的状态就是某个阶段的始点某个阶段的始点.S2=B1,B2,B3,B4北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)s1s2s3s4x1x2x3PagePagePage:152. 2. 基本概念、基本方程与最优化原理基本

7、概念、基本方程与最优化原理3. 决策决策. 决策是某一阶段内的抉择决策是某一阶段内的抉择,第第N阶段的决策阶段的决策与第与第N个阶段的状态有关个阶段的状态有关,通常用通常用Xn(Sn)表示表示第第n阶段处于阶段处于Sn状态时的决策量状态时的决策量,而这个决策而这个决策量又决定第量又决定第n+1阶段的状态阶段的状态.北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)S1s2s3s4x1x2x3PagePagePage:162. 2. 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理4. 策

8、略策略.由所有各阶段的决策函数序列称为全过程由所有各阶段的决策函数序列称为全过程策略策略,简称策略简称策略,记为记为p1,n(s1),能够达到总体最能够达到总体最优的策略叫做最优策略优的策略叫做最优策略.从第从第K个阶段开始个阶段开始到最后阶段的决策组成的决策函数序列称到最后阶段的决策组成的决策函数序列称为为K子过程策略子过程策略,简称简称K子策略子策略,记为记为Pk,N(Sk)PSSSnn112,()(),(),()SX X , X112nPagePagePage:172. 2. 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理5. 指标函数指标函数:指标函数是衡量全过程策略或指

9、标函数是衡量全过程策略或K子过程策略优劣的数量指标子过程策略优劣的数量指标,指标函数的指标函数的最优值称之为最优指标函数最优值称之为最优指标函数,记作记作f1(S1)或或fk(Sk)最短距离最短距离f1(s1), 最大收益最大收益fk(sk)PagePagePage:182. 2. 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理6. 状态转移方程状态转移方程:已知第已知第N+1阶段的状态是阶段的状态是由第由第N阶段的状态和第阶段的状态和第N阶段的决策所决定阶段的决策所决定的的,用方程表示为用方程表示为:Sn+1=Tn(Sn,Xn)状态转移方程状态转移方程.PagePagePage

10、:192. 2. 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理二、基本方程：二、基本方程：kkkkkkkkk 1k 1XD (S )n 1n 1f (S )minr (S ,X )f(S) kn,n1,1: f(S)0 初始(终点)条件动态规划递归方程动态规划递归方程 PagePagePage:202. 2. 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理二、基本方程：二、基本方程： 0)(Sf :,11,nn,k )(Sf)X,(Srmax)(Sf1n1n1k1kkkkkk初始条件动态规划递归方程动态规划递归方程 PagePagePage:212. 2. 基本概

11、念、基本方程与最优化原理基本概念、基本方程与最优化原理二、基本方程：二、基本方程：f (S )Optr (S ,X )f(S) kn,n1,1f(S)0 (or) 1 kkXD (S )kkkk 1k 1n 1n 1kkk动态规划递归方程动态规划递归方程 PagePagePage:22三、最优化原理与动态规划的基本方法 Bellman原理 动态规划的基本方法 逆向顺序法 前向顺序法PagePagePage:23Bellman原理示意图PagePagePage:24BellmanBellman最优性原理最优性原理 “作为整个过程的最优策略具有这样的性作为整个过程的最优策略具有这样的性质：无论过去

12、的状态和决策如何，相对于质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策必然前面决策所形成的状态，余下的决策必然形成最优子策略形成最优子策略” .最优策略的子策略也是最优的最优策略的子策略也是最优的.PagePagePage:25BellmanBellman最优性原理最优性原理 最短路径的最短路径的子路径子路径仍然是最短路径。仍然是最短路径。全长最优，那么部分仍然是最优。全长最优，那么部分仍然是最优。PagePagePage:26BACBDBCDEC212312312511214106104131211396581052052871220141919AB2C1D1EAB2C

13、1D1A到到E的最的最优是：优是：是是A到到D1的最优的最优PagePagePage:27四、 动态规划建模与求解步骤 建立动态规划模型的基本要求 动态规划的求解步骤PagePagePage:28一、建立动态规划模型的基本要求 将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假设。 确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。 状态变量应当满足无后效性要求。 明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。PagePagePage:29二、动态规划的求解步骤 正确划分阶段。 确定状态变量和决策变量，并给出状态变

14、量和决策变量的可行集合。 确定求解的递推顺序，给出状态转移方程。 确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。 递推求解。 与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。PagePagePage:30建立动态规划模型及求解步骤建立动态规划模型及求解步骤 划分阶段划分阶段确定状态变量及允许状态集合确定状态变量及允许状态集合确定决策变量及决策空间确定决策变量及决策空间确定状态转移方程确定状态转移方程确定转移指标函数并建立递归方程确定转移指标函数并建立递归方程 PagePagePage:313 3 动态规划应用动态规划应用 一、资源分配问题一、资源

15、分配问题二、背包问题二、背包问题三、生产与存贮问题三、生产与存贮问题PagePagePage:32资源分配问题资源分配问题 例例2 2：某公司有：某公司有4 4个推销员在北京、上海和广州三个市场推销个推销员在北京、上海和广州三个市场推销货物，这三个市场里推销人员数与收益的关系如表所示：试货物，这三个市场里推销人员数与收益的关系如表所示：试做出使决收益最大的分配方案。做出使决收益最大的分配方案。PagePagePage:33北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)s1s2s3s4x1x2x3

16、解：解：1。阶段划分。分成三个阶段，。阶段划分。分成三个阶段，K=3；并按逆向；并按逆向编号。广州编号。广州 K=1，上海，上海K=2 北京北京K=3，分配推销员，分配推销员的优先顺序为北京的优先顺序为北京上海上海广州广州.或或按顺向编号。广州按顺向编号。广州 K=3，上海，上海K=2 北京北京K=1，分，分配推销员的优先顺序为北京配推销员的优先顺序为北京上海上海广州广州.PagePagePage:34北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)s1s2s3s4x1x2x3解：解：2.确定状态

17、量确定状态量Sk。状态量。状态量Sk表示第表示第K阶段初未阶段初未分配的推销员数分配的推销员数.显然显然S1=4；S2,S3的取值为的取值为0-4 3.确定决策变量确定决策变量Xk. 决策变量决策变量Xk表示分配给第表示分配给第K阶段市场的推销数阶段市场的推销数.显然显然Xk=Sk.PagePagePage:35北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)s1s2s3s4x1x2x3解：解：4.确定状态转移方程确定状态转移方程Sk。根据前面的定义。根据前面的定义: Sk+1=Sk-Xk 期末期

18、末=期初期初-本期发生额本期发生额 5.确定直接效果函数确定直接效果函数dk(Sk,Xk). 它表示第它表示第K阶段阶段初有推销员数初有推销员数SK,分配给第分配给第K市场市场XK个推销员时所产个推销员时所产生的直接效益生的直接效益,这些效益指标由于表这些效益指标由于表1给出给出. PagePagePage:36北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)s1s2s3s4x1x2x3解：解：6.确定最优指标函数。由于三个市场的总收益确定最优指标函数。由于三个市场的总收益等于三个市场的收益之和等

19、于三个市场的收益之和.所以最优指标函数为所以最优指标函数为:3 , 2 , 1)(),()(11maxkxfxsdsfkkkkkxkkkPagePagePage:37北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)s1s2s3s4x1x2x3解：解：7.确定边界确定边界:fn+1(xn+1)=0 f4(x4)=f4(s4)=0PagePagePage:38北京北京上海广州广州指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3

20、)s1s2s3s4x1x2x3各阶段计算过程如下各阶段计算过程如下: 第第3阶段阶段:S3=0,1,2,3,4 f3(s3)=maxd3(s3,x3)+f4(s4)=maxd3(s3,x3) f3(0)=50, f3(1)=61,f3(2)=72,f3(3)=84,f3(4)=84PagePagePage:39各阶段计算过程如下各阶段计算过程如下: 第第2阶段阶段:S2=0,1,2,3,4 f2(s2)=maxd2(s2,x2)+f3(s3) f2(0)=maxd2(0,x2)+f3(0)=40+50=90 f2(1)=maxd2(1,x2)+f3(s3) d2(1,0)+f3(1)d2(1,

21、1)+f3(0)=max40+6150+50=max=101PagePagePage:40各阶段计算过程如下各阶段计算过程如下: 第第2阶段阶段:S2=0,1,2,3,4 f2(s2)=maxd2(s2,x2)+f3(s3) f2(2)=maxd2(2,x2)+f3(s3) d2(2,0)+f3(2)d2(2,1)+f3(1)=max40+7250+61=max=112d2(2,2)+f3(0)60+50PagePagePage:41各阶段计算过程如下各阶段计算过程如下: 第第2阶段阶段:S2=0,1,2,3,4 f2(s2)=maxd2(s2,x2)+f3(s3) f2(3)=maxd2(3

22、,x2)+f3(s3) d2(3,0)+f3(3)d2(3,1)+f3(1)=max40+8450+72=max=124d2(3,2)+f3(0)60+61d2(3,1)+f3(2)71+50PagePagePage:42各阶段计算过程如下各阶段计算过程如下: 第第2阶段阶段:S2=0,1,2,3,4 f2(s2)=maxd2(s2,x2)+f3(s3) f2(4)=maxd2(4,x2)+f3(s3) d2(4,1)+f3(3)d2(4,3)+f3(1)=max40+8450+84=max=134d2(4,4)+f3(0)60+72d2(4,2)+f3(2)71+61d2(4,0)+f3(4

23、)82+50PagePagePage:43各阶段计算过程如下各阶段计算过程如下: 第第1阶段阶段:S3=4 f1(s1)=maxd1(s1,x1)+f2(s2) f1(4)=maxd1(4,x1)+f2(s2) d1(4,1)+f2(3)d1(4,3)+f2(1)=max20+13432+124=max=159d1(4,4)+f2(0)47+112d1(4,2)+f2(2)57+101d1(4,0)+f2(4)66+90PagePagePage:44分配方案分配方案:北京市场北京市场2个推销员个推销员,上海上海0个个,广州市场广州市场2个推销员个推销员,总收益为总收益为159单位元单位元.Pa

24、gePagePage:45PagePagePage:46资源分配问题资源分配问题 1万元万元15万吨13万吨11万吨2万元万元28万吨29万吨30万吨3万元万元40万吨43万吨45万吨4万元万元51万吨55万吨58万吨ABC 项目项目投入资金投入资金有资金有资金4万元，投资万元，投资A、B、C三个项目，每个项目的投资效益三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目与投入该项目的资金有关。三个项目A、B、C的投资效益的投资效益（万吨）和投入资金（万元）的关系见下表：（万吨）和投入资金（万元）的关系见下表：求对三个项目的最优投资分配，使总投资效益最大。求对三个项目的最优投资分配，使

25、总投资效益最大。 PagePagePage:47项目项目A项目项目B项目项目C指标值指标值(收益收益)V1(s1,x1)指标值指标值(收益收益)V2(s2,x2)指标值指标值(收益收益)V3(s3,x3)s1s2s3s4x1x2x3阶段阶段k：每投资一个项目作为一个阶段；每投资一个项目作为一个阶段；状态变量状态变量sk：投资第投资第k个项目前的资金余额；个项目前的资金余额；决策变量决策变量xk：第第k个项目的投资额；个项目的投资额；决策允许集合：决策允许集合：Dk(sk)=0 xksk状态转移方程：状态转移方程：sk+1=sk-xk阶段指标：阶段指标：vk(sk,xk)见表中所示见表中所示；递

26、推方程：递推方程：fk(sk)=maxvk(sk,xk)+fk+1(sk+1)终端条件：终端条件：f4(s4)=0PagePagePage:48s3D3(s3) s4v3(s3,x3) v3(s3,x3)+f4(s4) f3(s3) x3*00000+0=0000100+0=0101111+0=11*0200+0=0111111+0=11203030+0=30*0300+0=0121111+0=11213030+0=30304545+0=45*0400+0=0131111+0=11223030+0=30314545+0=45405858+0=58*1111230234534584k=4，f4(

27、s4)=0; k=3，0 x3s3，s4=s3-x3 PagePagePage:49k=2，0 x2s2，s3=s2-x2 s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)x2*00000+0=0000100+11=11101313+0=13*0200+30=30*111313+11=24202929+0=290300+45=45*121313+30=43212929+11=40304343+0=430400+58=58131313+45=58222929+30=59*314343+11=54405555+0=551131230034504592PagePag

28、ePage:50k=1，0 x1s1，s2=s1-x1 s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)x1*0400+59=59131515+45=60*222828+30=58314040+13=53405151+0=514601最优解为最优解为:s1=4, x1*=1, s2=s1-x1=3, x2*=0, 最大效益为最大效益为60万吨万吨s3=s2-x2*=3, x3*=3, s4=s3-x3=0PagePagePage:51机器负荷分配问题机器负荷分配问题 某种机器可以在高、低两种负荷下生产。高负荷生某种机器可以在高、低两种负荷下生产。高负荷生产条件

29、下机器完好率为产条件下机器完好率为0.7，即如果年初有，即如果年初有u台完好台完好机器投入生产，则年末完好的机器数量为机器投入生产，则年末完好的机器数量为0.7u台。台。系数系数0.7称为完好率。年初投入高负荷运行的称为完好率。年初投入高负荷运行的u台机台机器的年产量为器的年产量为8u吨。系数吨。系数8称为单台产量。低负荷称为单台产量。低负荷运行时，机器完好率为运行时，机器完好率为0.9，单台产量为，单台产量为5吨。设开吨。设开始时有始时有1000台完好机器，要制订五年计划，每年年台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的初将完好的机器一部分分配到高负荷生产

30、，剩下的机器分配到低负荷生产，使五年的总产量为最高。机器分配到低负荷生产，使五年的总产量为最高。 PagePagePage:52第第1年年s1s2s3x1x2x3第第2年年第第3年年第第4年年第第5年年s4s5s6x4x5指标值指标值(产量产量)V1(s1,x1)指标值指标值(产量产量)V2(s2,x2)指标值指标值(产量产量)V5(s5,x5)指标值指标值(产量产量)V4(s4,x4)指标值指标值(产量产量)V3(s3,x3)PagePagePage:53动态规划模型构造动态规划模型构造阶段阶段k： 运行年份（运行年份（k=1,2,3,4,5,6）；）；状态变量状态变量xk： 第第k年初完好

31、的机器数（年初完好的机器数（k=1,2,3,4,5,6）；）；决策变量决策变量dk： 第第k年投入高负荷运行的机器数；年投入高负荷运行的机器数；状态转移方程：状态转移方程：sk+1=0.7xk+0.9(sk-xk)决策允许集合：决策允许集合：Dk(sk)=xk|0 xk sk阶段指标：阶段指标： vk(sk,xk)=8xk+5(sk-xk)终端条件：终端条件： f6(s6)=0递推方程：递推方程： fk(sk)=maxvk(sk,xk)+fk+1(sk+1) xk Dk(sk) =max8xk+5(sk-xk)+fk+10.7xk+0.9(sk-xk) 0 xk skPagePagePage:

32、54555sx066555sx055853xmax )(sf)x5(s8xmax)(sf5555ss5*5sx 第第5年年s5s6x5指标值指标值(产量产量)V5(s5,x5)+f6(s6)PagePagePage:55444sx0444444sx05444sx055444sx04413.7s12.3s1.4xmax )x0.9(s80.7x)x5(s8xmax 8s)x5(s8xmax )(sf)x5(s8xmax)(sf444444444*4sx 第第4年年s4s5x4指标值指标值(产量产量)V4(s4,x4)+f5(s5)PagePagePage:56f3(s3)=max8x3+5(s3

33、-x3)+f4(s4)0 x3 3 s3 3 =max8x =max8x3 3+5(s+5(s3 3-x-x3 3)+13.7s)+13.7s4 4 0 x3 s3 =max8d =max8d3 3+5(s+5(s3 3-d-d3 3)+13.70.7d)+13.70.7d3 3+0.9(s+0.9(s3 3-d-d3 3) 0 x3 s3 =max0.28x =max0.28x3 3+17.24s+17.24s3 3=17.52s=17.52s3 3 0 x3 s3 x x3 3* *=s=s3 3s3x3第第3年年s4指标值指标值(产量产量)V3(s3,x3)+f4(s4)PagePage

34、Page:57f2(s2)=max8x2+5(s2-x2)+f3(s3) 0 x2 2 s2 2 =max8x =max8x2 2+5(s+5(s2 2-x-x2 2)+17.52s)+17.52s3 3 0 0 x2 2 s2 2 =max8x =max8x2 2+5(s+5(s2 2-x-x2 2)+17.520.7x)+17.520.7x2 2+0.9(s+0.9(s2 2-x-x2 2)0 0 x2 2 s2 2 =max-0.504x =max-0.504x2 2+20.77s+20.77s2 2=20.77s=20.77s2 20 0 x2 2 s2 2x x2 2* *=0=0s

35、2s3x2第第2年年指标值指标值(产量产量)V2(s2,x2)+f3(s3)PagePagePage:58f1(s1)=max8x1+5(s1-x1)+f2(s2)0 x1 1 s1 1 =max8x =max8x1 1+5(s+5(s1 1-x-x1 1)+20.77s)+20.77s2 2 0 0 x1 1 s1 1 =max8x =max8x1 1+5(s+5(s1 1-x-x1 1)+20.770.7x)+20.770.7x1 1+0.9(s+0.9(s1 1-x-x1 1)0 0 x1 1 s1 1 =max-0.05x =max-0.05x1 1+23.69s+23.69s1 1=

36、23.69s=23.69s1 10 0 x1 1 s1 1x x1 1* *=0=0第第1年年s1s2x1指标值指标值(产量产量)V1(s1,x1)+f2(s2)PagePagePage:59由此可以得到：由此可以得到：f1(s1)=23.69s1,x1*=0f2(s2)=20.77s2,x2*=0f3(s3)=17.52s3,x3*=s3f4(s4)=13.60s4,x4*=s4f5(s5)=8s5x5*=s5用用s1=1000代入，得到五年最大产量为代入，得到五年最大产量为f1(s1)=f1(1000)=23690PagePagePage:60每年投入高负荷运行的机器数以及每年初完好的机每

37、年投入高负荷运行的机器数以及每年初完好的机器数为：器数为：s1=1000 x1*=0,s2=0.7x1+0.9(s1-x1)=900 x2*=0,s3=0.7x2+0.9(s2-x2)=810 x3*=s3=810,s4=0.7x3+0.9(s3-x3)=567x4*=s4=567,s5=0.7x4+0.9(s4-x4)=397x5*=s5=397,s6=0.7x5+0.9(s5-x5)=278PagePagePage:61生产库存问题生产库存问题生 产系 统1月 初 库 存 量 :s1=0生 产 量x1决 策 准 则 :生 产 成 本c1x1最 小生 产系 统2月 初 库 存 量 :s2生

38、产 量x23月 初 库 存 量 :s3决 策 准 则 :生 产 成 本c2x2最 小生 产系 统生 产 量x77月 底 库 存 量 :s80决 策 准 则 :生 产 成 本c7x7最 小7月 初 库 存 量 :s7PagePagePage:62一个工厂生产某种产品，一个工厂生产某种产品，17月份生产成本和月份生产成本和产品需求量的变化情况如下表：产品需求量的变化情况如下表：月份月份(k)1234567生产成本生产成本(ck)11181317201015需求量需求量(rk)0853274为了调节生产生产和需求，工厂设有一个产品仓为了调节生产生产和需求，工厂设有一个产品仓库，库容量库，库容量H=9

39、。已知期初库存量为。已知期初库存量为2，要求期末，要求期末（七月低）库存量为（七月低）库存量为0。每个月生产的产品在月末。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低量，能满足各月的需求，并使生产成本最低. .。 PagePagePage:63阶段阶段k：月份，月份，k=1,2,7,8；状态变量状态变量sk：第第k个月初（发货以前）的库存量；个月初（发货以前）的库存量；决策变量决策变量xk：第第k个月的生产量；个月的生产量；状态转移方程：状态转移方程：sk+1=sk-rk+xk；决策允许集合：决

40、策允许集合：Dk(sk)=xk | xk 0, rk+1k+1 sk+1k+1 H =x =xk k | x| xk k 0, rk+1k+1 sk k-r-rk k+x+xk k H；阶段指标：阶段指标：vk k(s(sk k,x,xk k)=c)=ck kx xk k；终端条件：终端条件：f8 8(s(s8 8)=0,)=0,s s8 8=0=0；递推方程：递推方程：fk k(s(sk k)=minv)=minvk k(s(sk k,x,xk k)+f)+fk+1k+1(s(sk+1k+1)x xk k Dk k(s(sk k) ) =minc =minck kx xk k+f+fk+1k

41、+1(s(sk k-r-rk k+x+xk k) x xk k Dk(sk)PagePagePage:64三、生产存储问题 某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。时期（月）需求量（dk）12342324PagePagePage:65已知的其它条件 已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。 设第k月的生产量uk，存储量为Sk,则总成本为kkkkkSuuSC5 . 003),(PagePagePage:66建立数学模型 以

42、月划分阶段，k=1,2,3,4 各阶段决策变量为该阶段生产量uk，状态变量为该阶段存储量Sk。需求dk 采用逆序算法，则状态转移方程为 最低成本递推公式是kkkkduSS10)()(),(min)(551160SfSfuSCSfkkkkkduSukkkkkkPagePagePage:67第四阶段的最优解 当k=4时，d4=4,因第四阶段末无存货，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5) f4(S4)生产存储01234432107654000.511.5276.565.52000000000076.565.52PagePagePage:68第三阶段最优解 当k=3时，

43、由于 ，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6)44SS3u3本期成本C3S4f4(S4) f3(S3)生产存储0234565678900000567890123476.565.521212.51313.511PagePagePage:69第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4) f3(S3)生产存储112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5PagePagePage:70第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4) f3(S3)生

44、产存储2012340456711111156780123476.565.52811.512.012.510.0PagePagePage:71第三阶段最优解:S3=3,4S3u3本期成本C3S4f4(S4) f3(S3)生产存储3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59PagePagePage:72第三阶段最优解:S3=5,6S3u3本期成本C3S4f4(S4) f3(S3)生产存储501042.52.52.56.5345.5288.560033425PagePagePage:73第二阶段最优解 当k=2时