七动态规划.pptx

2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1 1本章学习要求n掌握动态规划数学模型的建立n掌握几种典型问题的动态规划求解方法第1页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2 2 动态规划动态规划(Dynamic Programming)是用来解决多阶段决是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一策过程最优化的一种数量方法。其特点在于，它可以把一个个n 维决策问题变换为几个一维最优化问题，从而一个一维决策问题变换为几个一维最优化问题，从而一个一个地去解决。个地去解决。需指出：动态规划是求解某类问题的一种方法，是考需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。型，然后再用动态规划方法去求解。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策第2页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系3 3多阶段决策问题的典型例子：多阶段决策问题的典型例子：1.1.生产决策问题生产决策问题：企业在生产过程中，由于需求是随时间变化的，：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。2.2.机机器器负负荷荷分分配配问问题题：某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产产品品的的年年产产量量g g和和投投入入生生产产的的机机器器数数量量u1u1的关系为的关系为 g=g(u1)g=g(u1)这这时时，机机器器的的年年完完好好率率为为a a，即即如如果果年年初初完完好好机机器器的的数数量量为为u u，到到年年终完好的机器就为终完好的机器就为au,0a1au,0a1在在低低负负荷荷下下生生产产时时，产产品品的的年年产产量量h h和和投投入入生生产产的的机机器器数数量量u2u2的的关关系系为为h=h(u2)h=h(u2)相应的机器年完好率相应的机器年完好率b,0b1b,0b1。假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1s1。要求制定一个五年计划，在。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。数量，使在五年内产品的总产量达到最高。第3页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系4 43.3.航天飞机飞行控制问题：航天飞机飞行控制问题：由于航天飞机的运动的环境是由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。使之能最省燃料和实现目的（如软着落问题）。不包含时间因素的静态决策问题（本质上是一次决策不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。问题用动态规划方法来解决。4.4.线性规划、非线性规划线性规划、非线性规划等静态的规划问题也可以通过适等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。当地引入阶段的概念，应用动态规划方法加以解决。第4页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系5 5 5.最短路问题最短路问题：给定一个交通网络图如下，其中两点之：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从间的数字表示距离（或花费），试求从A点到点到G点的最短距离点的最短距离（总费用最小）。（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643第5页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系6 6 一、引例（例一、引例（例4）7.2 动态规划的基本概念动态规划的基本概念12345AB1B2C1C2C3C4D1D2D3E1E2F452368774585348433526134解决方法解决方法解决方法解决方法1 1：枚举法枚举法每个线路每个线路4次加法次加法24条线路条线路66次加法次加法23次比较次比较解决方法解决方法解决方法解决方法2 2：逆向递推法逆向递推法用用fA表示起点到终点的表示起点到终点的最短路长，最短路长，fF=0用用dky表示某节点表示某节点k到某到某节点节点Y的路段长度的路段长度第6页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系7 7最短路为：最短路为：最短路为：最短路为：A-B1-C2-D2-E2-FA-B1-C2-D2-E2-F共共共共2222次加法，次加法，次加法，次加法，1212次比较次比较次比较次比较第7页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系8 8 二、基本概念二、基本概念1 1、阶段：、阶段：、阶段：、阶段：把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以便于按一定的次序，以便于按一定的次序去求解。去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量,用用k表示表示。阶段的划分，一般是根据时间和空间。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。的自然特征来进行的，但要便于问题转化为多阶段决策。2 2、状态：、状态：、状态：、状态：表示每个阶段开始所处的表示每个阶段开始所处的自然状况或客观条件自然状况或客观条件。既是某阶段过。既是某阶段过程演变的起点，又是前一阶段某种决策的结果。描述过程状态的变量称为程演变的起点，又是前一阶段某种决策的结果。描述过程状态的变量称为状态变量状态变量,用用Sk表示表示。状态变量的取值有一定的允许集合或范围，此集合称为状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合状态允许集合。3 3、决策和策略：、决策和策略：、决策和策略：、决策和策略：表示当过程处于某一阶段的某个状态时，可以作出表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态不同的决定，从而确定下一阶段的状态，这种决定称为这种决定称为决策决策。按一定顺。按一定顺序排列的决策序列称为策略。序排列的决策序列称为策略。第8页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系9 9 描述决策的变量，称为描述决策的变量，称为决策变量决策变量,用用Uk(Sk)。决策变量是状态变量。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。的函数。可用一个数、一组数或一向量（多维情形）来描述。在实际问题中决策变量的取值往往在某一范围之内，此范围称为在实际问题中决策变量的取值往往在某一范围之内，此范围称为允允许决策集合许决策集合,用用Dk(Sk)表示表示。4 4、状态转移方程、状态转移方程、状态转移方程、状态转移方程状态转移方程是状态转移方程是确定过程由确定过程由确定过程由确定过程由一个状态到另一个状态的演一个状态到另一个状态的演一个状态到另一个状态的演一个状态到另一个状态的演变过程。变过程。变过程。变过程。如果第如果第k阶段状态变阶段状态变量量sk的值、该阶段的决策变的值、该阶段的决策变量一经确定，第量一经确定，第k+1阶段状阶段状态变量态变量sk+1的值也就确定。的值也就确定。图示如下：图示如下：12ks1u1s2u2s3skuksk1第9页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1010 能用动态规划方法求解的多阶段决策过程是一类特殊的多能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即阶段决策过程，即具有无后效性具有无后效性的多阶段决策过程。的多阶段决策过程。无后效性无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程的发展不受如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；构造动态规划模型时，要充分注意是否满足无后效性的要求；状态变量要满足无后效性的要求；状态变量要满足无后效性的要求；如果状态变量不能满足无后效性的要求，应适当地改变状态如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。的定义或规定方法。第10页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系11115 5、指标函数：、指标函数：、指标函数：、指标函数：1 1）阶段指标函数：）阶段指标函数：）阶段指标函数：）阶段指标函数：用用d dk k(S(Sk k,U,Uk k)表示表示,指第指第k k阶段，阶段，S Sk k状态下，作出状态下，作出U Uk k决策决策带来的效果。在不同的问题中，指标的含义是不同的，它可能是距离、利润、带来的效果。在不同的问题中，指标的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。成本、产量或资源消耗等。2 2）过程指标函数：）过程指标函数：）过程指标函数：）过程指标函数：用用V Vknkn(S(Sk k,P,Pknkn)表示表示,指指k k阶段，阶段，S Sk k状态下，作出状态下，作出P Pknkn子策子策略带来的效果。用以衡量多阶段决策过程实现效果的一种数量指标，是定义略带来的效果。用以衡量多阶段决策过程实现效果的一种数量指标，是定义在全过程和所有后部子过程的数量函数。在全过程和所有后部子过程的数量函数。3 3）最优（过程）指标函数：）最优（过程）指标函数：）最优（过程）指标函数：）最优（过程）指标函数：用用f fk k(S(Sk k)表示表示,过程指标函数的最优值，称过程指标函数的最优值，称为最优值函数。用为最优值函数。用f fk k(S(Sk k)=optV)=optVknkn(S(Sk k,P,Pknkn)optopt表示最优化，常取表示最优化，常取maxmax或或minmin第11页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系12121、Bellman最优性定理最优性定理一个过程的最优策略具有这样的性质：即无论初始状态及初始一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后所有的决决策如何，对于先前决策所形成的状态而言，其以后所有的决策应构成最优策略。策应构成最优策略。换句话说，最优策略只能由最优子策略构成。换句话说，最优策略只能由最优子策略构成。2、思想方法：、思想方法：在求解过程中，各阶段的状态和决策，对其后在求解过程中，各阶段的状态和决策，对其后面的阶段来说，只影响其初始状态，而不影响后面的最优策略。面的阶段来说，只影响其初始状态，而不影响后面的最优策略。无后效性无后效性方法：方法：“顺序编号，逆序求解顺序编号，逆序求解”三、动态规划的基本思想和基本方程三、动态规划的基本思想和基本方程第12页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系13133、基本方程、基本方程 根据最优性定理，可以写出动态规划递推方程，根据最优性定理，可以写出动态规划递推方程，即基本方程：即基本方程：Vkn(Sk,Pkn）=dj(Sj,Uj),j=k,n时，时，fk(Sk)=opt dk(Sk,Uk）+fk+1(Sk+1)fn+1(Sn+1)=0Vkn(Sk,Pkn）=dj(Sj,Uj),j=k,n时，时，fk(Sk)=opt dk(Sk,Uk）fk+1(Sk+1)fn+1(Sn+1)=1其中的其中的fn+1(Sn+1)为边界条件。为边界条件。第13页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系14147.3 动态规划模型的建立和步骤动态规划模型的建立和步骤 一、动态规划模型的建立一、动态规划模型的建立1 1、划分、划分阶段，阶段，阶段，阶段，正确选择正确选择状态变量状态变量状态变量状态变量N N个阶段个阶段 S Sk k可知性和无后效性可知性和无后效性2 2、确定、确定决策变量决策变量决策变量决策变量u uk k及允许及允许决策集合决策集合决策集合决策集合 3 3、确定、确定状态转移方程状态转移方程状态转移方程状态转移方程S Sk+1k+1=T=Tk k(S(Sk k,u,uk k(S(Sk k)根据根据k k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1k+1阶段状态变量，状态转移方阶段状态变量，状态转移方程应当具有递推关系。程应当具有递推关系。4 4、确定、确定阶段指标函数、过程指标函数阶段指标函数、过程指标函数阶段指标函数、过程指标函数阶段指标函数、过程指标函数和和最优指标函数最优指标函数最优指标函数最优指标函数d(Sd(Sk k,u,uk k)V)Vk,nk,n f fk k(S(Sk k)5 5、建立、建立动态规划基本方程动态规划基本方程动态规划基本方程动态规划基本方程 fk(Sk)=opt dk(Sk,Uk）+fk+1(Sk+1)fN+1(SN+1)=0第14页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1515例例5 5：解法：解法1 1（逆向递推）（逆向递推）1 1、划分阶段：、划分阶段：3 3个阶段个阶段 状态变量状态变量S1,S2,S3S1,S2,S3。Sk:Sk:表示第表示第k k阶段可以投资于第阶段可以投资于第k k个项目到第个项目到第3 3个项个项目的资金。目的资金。S1=10,S4=0S1=10,S4=02 2、确定决策变量：、确定决策变量：x1,x2,x3(uk=xk)x1,x2,x3(uk=xk)3 3、建立状态转移方程：、建立状态转移方程：4 4、确定指标函数：、确定指标函数：5 5、组建函数递推方程（基本方程）、组建函数递推方程（基本方程）第15页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1616所以投资方案为投资于第所以投资方案为投资于第所以投资方案为投资于第所以投资方案为投资于第3 3个项目，可得最大收益个项目，可得最大收益个项目，可得最大收益个项目，可得最大收益200200万元。万元。万元。万元。第16页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1717例例5 5：解法：解法2 2（顺序递推）（顺序递推）Sk+1:Sk+1:表示第表示第k k阶段可以投资于第阶段可以投资于第1 1个项目到第个项目到第k k个项目的资金。个项目的资金。S1=0,S4=10S1=0,S4=10状态转移方程：状态转移方程：组建函数递推方程（基本方程）组建函数递推方程（基本方程）123S1=10S1=10 x1x1S2S2x2x2S3S3S4=0S4=0 x3x3逆序逆序逆序逆序123S1=0S1=0 x1x1S2S2x2x2S3S3S4=10S4=10 x3x3顺序顺序顺序顺序第17页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1818所以投资方案为投资于第所以投资方案为投资于第所以投资方案为投资于第所以投资方案为投资于第3 3个项目，可得最大收益个项目，可得最大收益个项目，可得最大收益个项目，可得最大收益200200万元。万元。万元。万元。第18页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系1919二、顺序解法和逆序解法二、顺序解法和逆序解法1 1、状态转移方式不同、状态转移方式不同逆序：逆序：逆序：逆序：S Sk+1k+1T=Tk k(S(Sk k,u,uk k)顺序：顺序：顺序：顺序：S Sk k=T=Tk k(S(Sk+1k+1,u,uk k)2 2、指标函数的定义不同、指标函数的定义不同逆序：逆序：逆序：逆序：f fk k(S(Sk k)表示第表示第k k阶段从状态阶段从状态S Sk k出发，到终点后部子过程的最优效益出发，到终点后部子过程的最优效益值，值，f f1 1(S(S1 1)是整体最优值。是整体最优值。顺序：顺序：顺序：顺序：f fk k(S(Sk k1 1)表示第表示第k k阶段从起点到状态阶段从起点到状态S Sk k1 1的前部子过程的最优效益的前部子过程的最优效益值，值，f fn n(SSn+1n+1)是整体最优值。是整体最优值。3 3、基本方程的形式不同、基本方程的形式不同(1)(1)当指标函数为阶段指标和形式时当指标函数为阶段指标和形式时(2)(2)当指标函数为阶段指标积形式时当指标函数为阶段指标积形式时第19页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系20207.4 动态规划在经济管理中的应用动态规划在经济管理中的应用一、背包问题一、背包问题一、背包问题一、背包问题二、生产经营问题二、生产经营问题二、生产经营问题二、生产经营问题三、设备更新问题三、设备更新问题三、设备更新问题三、设备更新问题四、复合系统工作可靠性问题四、复合系统工作可靠性问题四、复合系统工作可靠性问题四、复合系统工作可靠性问题第20页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2121 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？作用（使用价值）最大？物品物品1 2 j n重量（公斤重量（公斤/件）件）a1 a2 aj an每件使用价值每件使用价值c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。货物装载问题、人造卫星内的物品装载问题等。一、背包问题一、背包问题第21页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2222设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学种物品的装件数（非负整数）则问题的数学模型如下：模型如下：第22页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2323例例7：解：逆序求解解：逆序求解1.阶段：分阶段：分3个阶段，状态变量个阶段，状态变量Sk:代表分配给第代表分配给第k种至第种至第3种货种货物的重量物的重量2.决策变量决策变量uk=xk k=1,2,3代表装载第代表装载第k种货物的件数；种货物的件数；3.状态转移方程：状态转移方程：Sk+1=Sk-akxk a1=3,a2=4,a3=54.阶段指标：阶段指标：dk(Sk,uk)=ckxk c1=4,c2=5,c3=65.基本方程：基本方程：第23页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2424k=3x3S3f3(S3)x3*0 01 12 20404595910100 0-0 00 00 06 6-6 61 10 06 6121212122 2k=2x2S2f2(S2)x2*0 01 12 21 14 47 70+00+0-0 00 00+00+05+05+0-5 51 10+60+65+05+0-6 60 01010S2=S1-3x10+120+125+65+610+010+012120 0k=1x1S1f1(S1)x1*0 01 12 210100+120+124+64+68+58+512+012+013133 32 2x x1 1*=2 S*=2 S2 2=S=S1 1-3x-3x1 1*=4*=4x x2 2*=1 S*=1 S3 3=S=S2 2-4x-4x2 2*=0*=0 x x3 3*=0*=0第24页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2525 练习：某厂生产三种产品，各种产品重量与利润练习：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过运输能力总重量不超过 6 吨，问如何安排运输，使吨，问如何安排运输，使总利润最大？总利润最大？种类种类 1 2 3重量（吨重量（吨/公斤）公斤）2 3 4 单件利润（元）单件利润（元）80 130 180最优方案：最优方案：X1=（0 0，2 2，0 0）X2=（1 1，0 0，1 1）Z=260=260第25页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2626 1.1.建模：建模：建模：建模：（1）阶段：按时间划分）阶段：按时间划分,k=1,2,3,4（2）状态变量）状态变量Sk:为第为第k个月初的库存量，个月初的库存量，MaxSk=3,E(Sk)为储存费用为储存费用（3）决策变量）决策变量uk：为第为第k个月生产量，个月生产量，Maxuk=6，C(uk）为生产费用）为生产费用（4）状态转移方程：）状态转移方程：Sk+1=Sk+uk-gk 下月初的库存量本月初的库存量每月的生产量需求量下月初的库存量本月初的库存量每月的生产量需求量（5）最优指标函数）最优指标函数fk(Sk)：k阶段状态阶段状态Sk时采用最佳生产时从时采用最佳生产时从k月到第月到第4月的生产、存储最低费用。月的生产、存储最低费用。则基本方程则基本方程 fk(Sk)=MinC(uk)+E(Sk)+fk+1(Sk+uk-gk)f5(S5)=0 k=4,3,2,1二、生产经营问题二、生产经营问题（例（例8:P212）第26页/共34页2008-4-1020084-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系27272.2.逆序求解：逆序求解：逆序求解：逆序求解：当当k=4时时 S5=0 S4+u4-g4=0则则u4=g4-S4=4-S4u4S4f4(S4)u4*1 12 23 30 01 12 2-7 77 7-6.56.5-6.56.5-6 63 3-6 6k=33 35.55.52 24 4-5.55.54 41 1u3S3f3(S3)u3*0 01 12 20 01 12 2-4.5+74.5+76+6.56+6.57+67+6-5.5+6.55.5+6.55.5+65.5+66.5+66.5+6 7.5+5.57.5+5.51+71+75+6.55+6.53 37+5.57+5.5-1.5+6.51.5+6.5-3 35+75+76+66+66.5+5.56.5+5.5-8+5.58+5.5-4 42 21 15 5121211.511.50 08 88 80 0第27页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2828k=2u1S1f1(S1)u1*2 23 34 40 05+165+16 6+15.56+15.58+13.58+13.52121k=15 57+157+152 2u2S2f2(S2)u2*0 01 12 20 01 12 2-6+126+127+11.57+11.5-5.5+125.5+125.5+11.55.5+11.56.5+11.56.5+11.57.5+87.5+8-5+125+123 37+87+88+88+88.5+88.5+81.5+121.5+12-3 3-6+11.56+11.56.5+86.5+8 7.5+87.5+8-8+88+8-4 4161615.515.55 59+89+8-1515-13.513.55 54 43 30 06 6u u1 1*=2 S*=2 S2 2=0=0u u2 2*=5 S*=5 S3 3=2=2u u3 3*=0 S*=0 S4 4=0=0u u4 4*=4*=4第28页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系2929 1.1.建模：建模：建模：建模：（1）阶段：按时间划分）阶段：按时间划分,k=1,2,3,4（2）状态变量）状态变量Sk:为第为第k个月初的库存量，个月初的库存量，MaxSk=1000,S1=500,S5=0（3）决策变量）决策变量:xk为第为第k个月的销售计划，个月的销售计划，yk为第为第k个月的订购计划。个月的订购计划。（4）状态转移方程：）状态转移方程：Sk+1=Sk+yk-xk 下月初的库存量本月初的库存量本月的订购计划量本月销售计划量下月初的库存量本月初的库存量本月的订购计划量本月销售计划量（5）则基本方程）则基本方程 fk(Sk)=Maxpkxk-ckyk+fk+1(Sk+1)f5(S5)=0 k=4,3,2,1例例9:采购与销售问题采购与销售问题与生产和存储问题相似与生产和存储问题相似第29页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系3030 已知：已知：已知：已知：一台设备的效益函数一台设备的效益函数r(t),维修费用函数维修费用函数U(t)及更新费用函数及更新费用函数c(t)，要求，要求在在n年内的每年初作出决策，是继续使用旧设备还是更换新的？使年内的每年初作出决策，是继续使用旧设备还是更换新的？使n年的总效年的总效益最大。益最大。1.1.建模：建模：建模：建模：（1）阶段：按时间划分）阶段：按时间划分,k=1,2,，n（2）状态变量）状态变量Sk:为第为第k年设备已经使用过的年数，即役龄。年设备已经使用过的年数，即役龄。（3）决策变量）决策变量xk：为第：为第k年初更新年初更新R，还是继续使用，还是继续使用K。（4）状态转移方程：）状态转移方程：（5）阶段指标：）阶段指标：则基本方程则基本方程 三、设备更新问题三、设备更新问题（例（例10:P218）第30页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系31312.2.逆序求解：逆序求解：逆序求解：逆序求解：当当k=5时时 x5S5f5(S5)x5*K KR R1 12 23 33.53.53.03.02.32.33.53.52.52.51.51.52.52.51.751.752.02.04 42.02.0k=4K K0.50.5R R1.51.5K KR Rx4S4f4(S4)x4*K KR R1 12 23 33.5+2.53.5+2.53.0+3.53.0+3.52.3+3.52.3+3.56.56.52.5+2.02.5+2.05.85.81.75+1.51.75+1.5 2.0+3.52.0+3.5 5.55.5R RR RR Rk=3x3S3f3(S3)x3*K KR R1 12 23.5+5.83.5+5.8 3.0+6.53.0+6.52.3+6.52.3+6.59.59.52.5+5.52.5+5.58.88.8R RR Rk=2x2S2f2(S2)x2*K KR R1 13.5+8.83.5+8.8 3.0+9.53.0+9.512.512.5R Rk=1x1S1f1(S1)x1*K KR R0 04.5+12.54.5+12.5 4+12.54+12.51717K Kx1=K S2=1 x2=R S3=1x3=R S4=1 x4=R S5=1x5=K第31页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系3232四、复合系统工作可靠性问题四、复合系统工作可靠性问题某种机器的工作系统由某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为了提高系统工作的可靠性，在每个部件上个系统就不能正常工作。为了提高系统工作的可靠性，在每个部件上均装有主要元件的备用件，并设计了备用元件自动投入装备，显然，均装有主要元件的备用件，并设计了备用元件自动投入装备，显然，备用元件越多，整个系统工作的可靠性就越大，但备用元件增多也会备用元件越多，整个系统工作的可靠性就越大，但备用元件增多也会导致系统的成本、重量体积相应增大，工作精度降低，因此，在考虑导致系统的成本、重量体积相应增大，工作精度降低，因此，在考虑上述限制条件下，如何选择各部件的备用元件数，使整个系统的工作上述限制条件下，如何选择各部件的备用元件数，使整个系统的工作可靠性最大？可靠性最大？设部件设部件i装有装有xi个备用元件时，正常工作的概率为个备用元件时，正常工作的概率为Pi(xi),那么整个系统那么整个系统正常工作的概率正常工作的概率Z=Pi(xi)（i=1，,n）,设部件设部件i的单位重量级的单位重量级wi,那么总重量不超过那么总重量不超过w的情况下的情况下,如何配备备用件如何配备备用件,使使Z最大最大?第32页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系33331.建模建模阶段：阶段：k=1，2，n,对应给第对应给第k个部件分配配件的过程个部件分配配件的过程状态状态Sk:表示可供分配第表示可供分配第k个到第个到第n个部件的总重量个部件的总重量决策变量决策变量xk:表示分配给第表示分配给第k个部件配备的备用件数个部件配备的备用件数状态转移方程状态转移方程:Sk+1=Skwkxk阶段指标函数阶段指标函数:d k=Pk(xk)基本方程基本方程:fk(Sk)=maxdk fk+1(Sk+1)(k=n,2,1)fn+1(Sn+1)=1第33页/共34页2008-4-102008-4-10浙江科技学院经济管理学院管工系浙江科技学院经济管理学院管工系3434k=3x3S3f3(S3)x3*1 12 23 30202)2323)3434)-0.10.1-0.10.11 10.10.10.20.2-0.20.22 2k=2x2S2f2(S2)x2*1 12 23 35 56 67 70.5*00.5*0-0.020.021 10.5*00.5*00.9*00.9*00.040.041 10.2*0.70.2*0.7 0.5*0.10.5*0.1 0.9*00.9*00.140.141 18 80.2*0.70.2*0.7 0.5*0.20.5*0.2 0.9*0.10.9*0.1 0.140.141 1k=1x1S1f3(S3)x3*1 12 28 80.3*0.140.3*0.14 0.4*0.040.4*0.04 0.5*0.020.5*0.02 0.0420.0423 31 1x x1 1*=1 S*=1 S2 2=7=7x x2 2*=1 S*=1 S3 3=4=4x x3 3*=3*=3例：习题例：习题例：习题例：习题7.57.54848)0.10.10.20.20.70.70.70.73 3第34页/共34页