第三章运输问题.ppt

《第三章运输问题.ppt》由会员分享，可在线阅读，更多相关《第三章运输问题.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 动态规划动态规划-DynamicProgramming20052005年年9 9月月 龙子泉龙子泉概概述述一、动态规划的提出一、动态规划的提出动态规划是动态规划是19511951年由美国学者年由美国学者R.BellmanR.Bellman等人等人在解决所谓多阶段决策问题时提出的一种优化在解决所谓多阶段决策问题时提出的一种优化方法，从此，动态规划成为运筹学的一个重要方法，从此，动态规划成为运筹学的一个重要分支。该方法在进行多阶段决策时，先将问题分支。该方法在进行多阶段决策时，先将问题变换成一系列相互联系的单阶段问题，当解决变换成一系列相互联系的单阶段问题，当解决了这一系列单阶段问题

2、之后，在了这一系列单阶段问题之后，在“最优性原理最优性原理”的基础上，就可以解决整个多阶段决策问题。的基础上，就可以解决整个多阶段决策问题。二、动态规划的有效性二、动态规划的有效性DP在工程技术、企业管理和军事等方面多有着广在工程技术、企业管理和军事等方面多有着广泛的应用。泛的应用。企业管理方面的最短路问题、生产与库企业管理方面的最短路问题、生产与库存问题、资源分配问题、排序问题、设存问题、资源分配问题、排序问题、设备更新问题等；备更新问题等；工程技术方面的水库优化调度问题、电工程技术方面的水库优化调度问题、电力系统经济调度问题等。力系统经济调度问题等。许多问题用动态规划方法解决，比其他常用方

3、法许多问题用动态规划方法解决，比其他常用方法如线性规划或非线性规划等方法更为有效。特别如线性规划或非线性规划等方法更为有效。特别是对于离散的问题，由于目标函数或约束条件难是对于离散的问题，由于目标函数或约束条件难以用解析的方式表达时，此时，动态规划方法就以用解析的方式表达时，此时，动态规划方法就成为非常有效的工具。成为非常有效的工具。三、动态规划的分类三、动态规划的分类动态规划模型的分类一般根据其状态的性质或多动态规划模型的分类一般根据其状态的性质或多少来分类。而状态有离散的和连续的、有确定的少来分类。而状态有离散的和连续的、有确定的和随机的、有一维的和多维的。和随机的、有一维的和多维的。离散

4、确定型离散确定型 离散随机型离散随机型 连续确定型连续确定型 连续随机型连续随机型 一维动态规划模型一维动态规划模型 多维动态规划模型多维动态规划模型 20052005年年9 9月月 龙子泉龙子泉 一、多阶段决策过程一、多阶段决策过程在在生生产产决决策策中中，若若某某一一活活动动过过程程可可以以分分为为若若干干相相互互联联系系的的阶阶段段，每每一一阶阶段段又又需需要要作作出出决决策策，从从而而使整个过程达到最好的活动效果。使整个过程达到最好的活动效果。这这种种把把一一个个问问题题看看作作是是一一个个前前后后关关联联具具有有链链状状结结构构的的多多阶阶段段过过程程就就称称为为多多阶阶段段决决策策

5、过过程程，这这种种问问题就称为题就称为多阶段决策问题多阶段决策问题。第一节第一节 多阶段决策过程及其问题举例多阶段决策过程及其问题举例二、多阶段决策问题举例二、多阶段决策问题举例例例5.1 5.1 最短路问题最短路问题如如图图5252，给给定定一一个个线线路路网网络络，两两点点之之间间连连线线上上的的数数字字表表示示两两点点间间的的距距离离（或或费费用用、时时间间等等），试试求求一一条条由由A A到到E E的的线线路，使总距离为最短（或费用最小、时间最少等）。路，使总距离为最短（或费用最小、时间最少等）。B1A C1 B2 C3E D1 C4 C2 D3 D2 3 5 3 1 68 6673

6、5 8 33 8 4232图图52例例5.2 5.2 生产与存储问题生产与存储问题假假设设某某厂厂某某车车间间每每月月底底都都要要供供应应总总装装车车间间一一定定数数量量的的部部件件，但但由由于于生生产产条条件件的的变变化化，该该车车间间每每月月生生产产单单位位部部件件所所耗耗费费的的工工时时不不同同，各各月月份份的的生生产产量量于于当当月月的的月月底底以以前前，全全部部要要存存入入仓仓库库以以备备后后用用。已已知知总总装装车车间间各各个个月月份份的的需需求求量量以以及及在加工车间生产该部件每单位数量所需工时如表在加工车间生产该部件每单位数量所需工时如表51所示所示设设库库存存容容量量H=9，

7、开开始始时时库库存存量量为为2，期期终终库库存存量量为为0，现现要要求求制制定定一一个个半半年年逐逐月月生生产产计计划划，使使得得既既满满足足需需求求和和库库存存容量的限制，又使总耗费的工时最少容量的限制，又使总耗费的工时最少。月月 份份 k0123456月需求量月需求量 dk0853274单位工时单位工时 ak11181317201020052005年年9 9月月 龙子泉龙子泉一、动态规划的基本概念一、动态规划的基本概念（1 1）阶段）阶段对对于于多多阶阶段段决决策策问问题题，按按问问题题的的特特点点可可将将其其划划分分为为若若干干个个相相互互联联系系的的阶阶段段，阶阶段段就就是是问问题题所

8、所处处的的地地段段或或时时段段。描描述述阶阶段段的的变变量量称称为为阶阶段段变变量量，通通常常用用k表表示示。例例5.1中中，阶阶段段为为问问题题所所处处的的地地段段，且且k=1，2，3，4；例例5.2中中，阶阶段段为为问问题题所所处处的的时时段段（月），且（月），且k=0，1，6；第二节第二节 动态规划的基本概念与基本方程动态规划的基本概念与基本方程（2 2）状态）状态状态状态就是在各阶段开始时问题的自然状况就是在各阶段开始时问题的自然状况描述过程状态的变量称为状态变量。通常用描述过程状态的变量称为状态变量。通常用Sk表表示第示第k阶段的状态集合，用阶段的状态集合，用sk表示第表示第k阶段的

9、某一阶段的某一具体的状态。具体的状态。结合例结合例1、例、例2说明说明动态规划状态必须满足两个条件：动态规划状态必须满足两个条件：能描述问题的过程能描述问题的过程 满足满足无后效性无后效性所所谓谓无无后后效效性性是是指指如如果果某某阶阶段段的的状状态态给给定定以以后后，则则在在这这阶阶段段以以后后过过程程的的发发展展不不受受这这阶阶段段以以前前各各状状态态的的影影响响，即即过过程程的的过过去去历历史史只只能能通通过过当当前前的的状状态态去去影影响响它它的的未未来来的的发发展展，当当前前的的状状态态是是以以往往历历史的一个总结。史的一个总结。（3 3）决策）决策决决策策表表示示当当过过程程处处于

10、于某某一一阶阶段段的的某某一一状状态态时时，为为确确定下一阶段的某一状态所作出的决定或者选择定下一阶段的某一状态所作出的决定或者选择描描述述决决策策的的变变量量称称为为决决策策变变量量。通通常常用用uk（sk）表表示示第第k阶阶段段在在状状态态为为sk时时所所作作出出的的决决策策，用用Dk（sk）表表示示第第k阶阶段段在在状状态态为为sk处处所所有有可可行行决决策策构构成成的的决策集合，显然有决策集合，显然有uk（sk）Dk（sk）；）；举例举例（4）状态转移方程）状态转移方程 描描述述相相邻邻两两阶阶段段状状态态与与决决策策相相互互关关系系的的方方程程称称为为状状态态转转移移方方程程。状状态

11、态转转移移方方程程的的一一般般形形式式可可描描述述为为sk+1=Tk（sk，uk），），Tk称为状态转移函数；称为状态转移函数；举例举例（5 5）策略）策略对对于于n阶阶段段决决策策问问题题，从从初初始始状状态态出出发发到到终终段段状状态态的的全全过过程程中中，每每阶阶段段的的决决策策uk（sk）（k=1，2，n）所所构构成成的的决策序列就称为一个决策序列就称为一个整体策略整体策略，简称，简称策略策略。记为：。记为：p1，n（s1）=u1（s1），），u2（s2），），un（sn）另外，称下式所描述的为另外，称下式所描述的为后部后部k段子策略段子策略 pk，n（sk）=uk（sk），），uk+

12、1（sk+1），），un（sn）称下式所描述的为称下式所描述的为前部前部k段子策略段子策略 p1，k（s1）=u1（s1），），u1（s1），），uk（sk）在在实实际际问问题题中中，可可供供选选择择的的策策略略有有一一定定的的范范围围，此此范范围围称称为为允允许许策策略略集集合合，用用P表表示示。允允许许策策略略集集合合中中使使问问题题达达到到最最优优效果的策略称为效果的策略称为最优策略最优策略结合例结合例1、例、例2 说明说明（6 6）指标函数）指标函数把把描描述述问问题题优优劣劣的的数数量量指指标标与与问问题题策策略略或或子子策策略略关关系系的的函函数数称称为为指指标标函函数数。即即，衡

13、衡量量问问题题的的优优劣劣必必须须有有数数量量指指标标，而而该该数数量量指指标标可可以以是是定定义义在在问问题题策策略略或子策略上的函数，通常用或子策略上的函数，通常用Vk，n表示。即表示。即 Vk，n=Vk，n(pk，n(sk)k=1，2，n对对于于动动态态规规划划模模型型来来说说，指指标标函函数数应应满满足足可可分分离离性性，即可以描述成即可以描述成sk、uk、Vk+1，n的函数。记为的函数。记为 Vk，n(pk，n(sk)=ksk，uk，Vk+1，n(pk+1，n(sk+1)（6 6）指标函数）指标函数动态规划的指标函数的形式一般有如下两种动态规划的指标函数的形式一般有如下两种阶阶段段指

14、指标标和和的的形形式式，即即过过程程或或子子过过程程的的指指标标为为各各阶段指标的和，用公式描述如下阶段指标的和，用公式描述如下:阶阶段段指指标标积积的的形形式式，即即过过程程或或子子过过程程的的指指标标为为各各阶段指标的积阶段指标的积 其其中中，vj（sj，uj）表表示示j阶阶段段在在状状态态为为sj作作出出决决策策为为uj时的指标，即所谓的时的指标，即所谓的阶段指标阶段指标 推导两种形式的可分离性推导两种形式的可分离性20052005年年9 9月月 龙子泉龙子泉20世世纪纪50年年代代，R.Bellman 等等人人根根据据研研究究多多阶阶段段决决策策问问题题的的成成果果，提提出出了了最最优

15、优性性原原理理，该该原原理理作作为为动动态态规规划划的的理理论论基基础础，解解决决了了很很多多类类型型决决策策过程最优化问题。过程最优化问题。动动态态规规划划规规划划的的最最优优性性原原理理描描述述如如下下：“作作为为整整个个过过程程的的最最优优策策略略具具有有这这样样的的性性质质：即即无无论论过过去去的的状状态态和和决决策策如如何何，对对前前面面的的决决策策所所形形成成的的状状态态而而言言，余余下下的的诸诸决决策策必必须须构构成成最最优优策策略略。”简简言言之，一个最优策略的子策略总是最优的之，一个最优策略的子策略总是最优的 二、动态规划最优性原理二、动态规划最优性原理20052005年年9

16、 9月月 龙子泉龙子泉根据根据DP原理，有原理，有DP方程形式方程形式三、动态规划基本方程三、动态规划基本方程式式中中，为为乘乘子子，根根据据指指标标函函数数的的形形式式分分别别取取“+”和和“”OPT根据问题的目标取根据问题的目标取“min”或或“max”用例用例1说明说明DP方程的含义方程的含义从从DPDP基本概念和基本方程可归纳出动态规划的基本概念和基本方程可归纳出动态规划的基本思想基本思想：动动态态规规划划方方法法的的关关键键在在于于正正确确地地写写出出基基本本的的递递推推关关系系式式（基基本本方方程程）。要要做做到到这这一一点点，必必须须首首先先将将问问题题的的过过程程划划分分成成若

17、若干干个个相相互互联联系系的的阶阶段段，正正确确地地选选择择问问题题的的状状态态变变量量和和决决策策变变量量以以及及定定义义指指标标函函数数的的具具体体形形式式，从从而而将将一一个个大大问题化成一簇同类型的子问题，然后逐个求解。问题化成一簇同类型的子问题，然后逐个求解。在在多多阶阶段段决决策策过过程程中中，动动态态规规划划方方法法是是既既把把当当前前一一段段和和未未来来各各段段分分开开，又又把把当当前前效效益益和和未未来来效效益益结结合合起起来来考考虑虑的的一一种种最最优优化化方方法法。因因此此，每每段段决决策策的的选选取取是是从从全全局局来来考考虑虑的的，与该段的最优选择答案一般是不同的。与

18、该段的最优选择答案一般是不同的。在求整个问题的最优策略时，由于初始状态是已知的，而在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线段状态便可逐次变换得到，从而确定了最优路线 20052005年年9 9月月 龙子泉龙子泉一、动态规划方法解题步骤一、动态规划方法解题步骤1建立问题的动态规划模型建立问题的动态规划模型 包包括括划划分分阶阶段段、选选择择问问题题的的状状态态变变量量与与决决策策变变量量、写写出出状状态态转转移移方方程程、描描述述问问题题的的指指

19、标标函函数数、列列出出问问题题的的动动态态规划方程。规划方程。2递推计算递推计算 即即按按第第一一步步所所描描述述的的动动态态规规划划方方程程分分阶阶段段逐逐一一计计算算，若若问题是离散的，则，每阶段的每一个状态都要计算。问题是离散的，则，每阶段的每一个状态都要计算。3寻找最优策略寻找最优策略 以以第第二二步步递递推推计计算算的的结结果果为为基基础础，以以状状态态转转移移方方程程为为纽纽带，按与递推计算相反的方向寻找最优策略。带，按与递推计算相反的方向寻找最优策略。第三节第三节 动态规划方法解题动态规划方法解题例例5.3 用动态规划方法求解例用动态规划方法求解例1所描述的最短路问题。所描述的最

20、短路问题。1建立问题的动态规划模型建立问题的动态规划模型阶段：按地段划分阶段，则阶段：按地段划分阶段，则k=1，2，3，4；状态：各阶段初的起始位置，用状态：各阶段初的起始位置，用sk表示；表示；决决策策：各各阶阶段段在在给给定定状状态态sk条条件件下下的的路路径径选选择择，用用uk（sk）表示；）表示；状态转移方程：状态转移方程：sk+1=uk（sk）指指标标函函数数：衡衡量量问问题题优优劣劣的的数数量量指指标标为为距距离离，指指标标函函数数的的形形式式为为各各阶阶段段指指标标的的和和，即即Vk,n(=nj=kv(sj,uj)，其其中中vj（sj，uj）分别标注在图中的相应线段上。）分别标注

21、在图中的相应线段上。动态规划方程：动态规划方程：2.递推计算递推计算 逐步计算（板书）逐步计算（板书）3.寻优寻优 板书板书20052005年年9 9月月 龙子泉龙子泉二、顺序解法与逆序解法二、顺序解法与逆序解法从从问问题题的的最最后后阶阶段段逐逐步步向向前前进进行行的的，因因此此称称为为动动态态规规划划的的逆序解法。逆序解法。某某些些问问题题的的递递推推计计算算可可以以从从前前向向后后进进行行，即即所所谓谓的的动动态态规规划顺序解法。划顺序解法。假假定定阶阶段段序序数数k和和状状态态变变量量sk的的定定义义不不变变，而而uk表表示示第第k阶阶段段在在状状态态为为sk+1时时向向前前作作出出的

22、的决决定定。这这样样问问题题的的状状态态转转移移方程可以描述为如下形式方程可以描述为如下形式 sk=Tk（sk+1，uk）动态规划顺序解法的基本方程为动态规划顺序解法的基本方程为20052005年年9 9月月 龙子泉龙子泉三、静态规划的动态规划解法三、静态规划的动态规划解法 对对于于某某些些静静态态规规划划问问题题，引引入入时时间间的的因因素素，把把它它看看作作是是按按阶阶段段进进行行的的一一个个动动态态规规划划问问题题，这这就就使使得得动动态态规规划划成成为为求求解解一一些些简简单单的的线线性性规规划划或或非非线线性规划的有效方法。性规划的有效方法。例例5.4 用动态规划发求解下列静态规划问

23、题用动态规划发求解下列静态规划问题 解：解：按变量划分阶段，即按变量划分阶段，即k=1，2，3；x1、x2、x3仍然为决策变量；仍然为决策变量；状态变量为状态变量为 s3=x3，s2=x2+x3，s1=x1+x2+x3=c；在上述定义的基础上，状态转移方程为：在上述定义的基础上，状态转移方程为：sk+1=sk xk；指标函数的形式为：指标函数的形式为：其其中中 v1(s1，x1)=x1，v2(s2，x2)=x22、v3(s3，x3)=x3；动态规划方程为动态规划方程为递推计算递推计算 逐步板书逐步板书例例5.5 用动态规划法求解下列静态规划问题用动态规划法求解下列静态规划问题用动态规划法求解下

24、列静态规划问题用动态规划法求解下列静态规划问题递推计算和寻优递推计算和寻优 逐步板书逐步板书20052005年年9 9月月 龙子泉龙子泉第四节第四节 动态规划应用动态规划应用 一、资源分配问题一、资源分配问题（一）一维资源分配问题（一）一维资源分配问题问问题题描描述述 设设有有某某种种资资源源,总总数数量量为为a,用用于于生生产产n种种产产品品(或或用用于于n种种生生产产),若若分分配配数数量量xi用用于于第第i种种产产品品,其其收收益益为为gi(xi)问问应应如如何何分分配配，才才能能使使生生产产n种种产产品品的的总总收收入入最最大大？该问题的静态规划数学模型为该问题的静态规划数学模型为当当

25、gi(xi)均为非线性函数时，上述问题为均为非线性函数时，上述问题为NLP问题，此时，问题，此时，若若n较大时，用非线性规划方法求解很困难。较大时，用非线性规划方法求解很困难。可将其看成一个多阶段决策问题，利用可将其看成一个多阶段决策问题，利用DP的递推关系来求的递推关系来求解。当解。当gi(xi)无具体解析式时，用无具体解析式时，用DP方法求解更显其优越。方法求解更显其优越。该问题的动态规划模型为该问题的动态规划模型为阶段阶段：按生产划分阶段，：按生产划分阶段，k=1，n；状态变量状态变量：sk表示可用于分配给第表示可用于分配给第k至第至第n阶段（生产）的阶段（生产）的资源数量；资源数量；决

26、策变量决策变量：xk表示可用于分配给第表示可用于分配给第k阶段阶段(生产生产)的资源数量；的资源数量；状态转移方程状态转移方程：sk+1=skxk允许决策集合允许决策集合：Dk(sk)=xk|0 xksk k=1，n-1；动态规划方程动态规划方程例例5.65.6 某公司现有资源某公司现有资源A五个单位，可分配给所属甲、乙、五个单位，可分配给所属甲、乙、丙三个分公司。各分公司获得不同数量的资源丙三个分公司。各分公司获得不同数量的资源A可为总公可为总公司获得不同的利润，具体数据如表司获得不同的利润，具体数据如表52所示。问如何分配所示。问如何分配资源资源A给各分公司，使总公司利润最大给各分公司，使

27、总公司利润最大 分公司分公司资源资源A 甲甲乙乙丙丙012345045709010512002045751101500507080100130解：解：（1）建立其动态规划数学模型）建立其动态规划数学模型阶段：按分公司划分阶段，阶段：按分公司划分阶段，k=1，2，3（分别代表分公司（分别代表分公司甲、乙、丙）；甲、乙、丙）；状态变量：状态变量：sk表示可用于分配给第表示可用于分配给第k至第至第3阶段（分公司）阶段（分公司）的资源的资源A的数量；的数量；决策变量：决策变量：xk表示可用于分配给第表示可用于分配给第k阶段的资源阶段的资源A的数量；的数量；状态转移方程：状态转移方程：sk+1=skxk

28、允许决策集合：允许决策集合：Dk（sk）=xk|0 xksk k=1，2；动态规划方程动态规划方程(2)递推计算递推计算 (3)寻优寻优 逐步板书逐步板书例例5.75.7 某公司计划研制三种新产品，若不增加研制投资，某公司计划研制三种新产品，若不增加研制投资，三种产品的不成功的概率分别为三种产品的不成功的概率分别为0.7、0.8和和0.7。为降低不。为降低不成功的概率，公司决定增加研制投资成功的概率，公司决定增加研制投资15万元。各产品增加万元。各产品增加研制费后，不成功的概率如表研制费后，不成功的概率如表53所示。设三种产品成功所示。设三种产品成功与否相互独立，试用动态规划法计算使三种产品均

29、不成功与否相互独立，试用动态规划法计算使三种产品均不成功的概率最小的研制费分配方案的概率最小的研制费分配方案 分公司分公司资源资源A ABC0510150.70.50.30.30.80.50.20.20.70.40.30.1解：解：（1）建立其动态规划数学模型）建立其动态规划数学模型阶段：按产品划分阶段，阶段：按产品划分阶段，k=1，2，3(产品产品A、B、C)状态变量：状态变量：sk表示可用于分配给第表示可用于分配给第k至第至第3阶段的研制费阶段的研制费；决策变量：决策变量：xk表示可用于分配给第表示可用于分配给第k阶段的研制费阶段的研制费；状态转移方程：状态转移方程：sk+1=skxk允许

30、决策集合：允许决策集合：Dk（sk）=xk|0 xksk(k=1，2)；D3（s3）=x3|x3=s3 动态规划方程动态规划方程 根据概率论的知识有根据概率论的知识有(2)递推计算递推计算 (3)寻优寻优 逐步板书逐步板书一、资源分配问题一、资源分配问题（二）二维资源分配问题（二）二维资源分配问题问问题题描描述述 设设有有某某种种资资源源,总总数数量量为为a,用用于于生生产产n种种产产品品(或或用用于于n种种生生产产),若若分分配配数数量量xi用用于于第第i种种产产品品,其其收收益益为为gi(xi)问问应应如如何何分分配配，才才能能使使生生产产n种种产产品品的的总总收收入入最最大大？该问题的静

31、态规划数学模型为该问题的静态规划数学模型为简要介绍用动态规划求解的基本思想简要介绍用动态规划求解的基本思想20052005年年9 9月月 龙子泉龙子泉第四节第四节 动态规划应用动态规划应用 二、生产与存储问题二、生产与存储问题 问问题题描描述述 设设某某公公司司对对某某产产品品要要制制定定一一个个n阶阶段段的的生生产产（或或购购买买）计计划划。已已知知第第k阶阶段段社社会会对对该该产产品品的的需需求求量量为为dk；单单位位产产品品的的存存储储费费为为hk，生生产产单单位位产产品品的的成成本本费费为为ck，生生产产每每批批产产品品的的固固定定成成本本为为C，若若不不生生产产则则为为零零；每每次次

32、生生产产的的上上限限为为m；开开始始时时库库存存量量为为零零，在在n阶阶段段末末的的终终结结库库存存量量也也为为零零。问问在在保保证证供供应应的的情情况况下下，该该公公司司如如何何制制定定每每个阶段的生产（或采购）计划个阶段的生产（或采购）计划，从而时使总成本最小。，从而时使总成本最小。该问题的动态规划模型为该问题的动态规划模型为状态变量：各阶段初的库存量，用状态变量：各阶段初的库存量，用sk表示表示决策变量：各阶段的生产量（或定购量），用决策变量：各阶段的生产量（或定购量），用uk表示；表示；状态转移方程：状态转移方程：sk+1=sk+ukdk指标函数：指标函数：Vk，n=vk(sk，uk)

33、+vn(sn，un)DP方程方程其中其中其中其中Dn（sn）=un|un=dnsn 在在库库存存无无限限制制时时 smk+1 =dk+1+dn 生产与存储问题举例生产与存储问题举例 例例5.8 某某工工厂厂要要对对一一种种产产品品制制订订今今后后四四个个时时期期的的生生产产计计划划，据据估估计计在在今今后后四四个个时时期期内内，市市场场对对于于该该产产品品的的需需求求量量如如下下表所示表所示。已已知知该该厂厂生生产产每每批批产产品品的的固固定定成成本本为为3千千元元，若若不不生生产产就就为为0；每每单单位位产产品品成成本本为为1千千元元；每每个个时时期期生生产产能能力力所所允允许许的的最最大大

34、生生产产批批量量为为不不超超过过6个个单单位位；每每个个时时期期末末未未售售出出的的产产品品，每每单单位位存存储储费费为为0.5千千元元。还还假假定定在在第第一一时时期期初初和和第第四四时时期期末末的的库库存存量量均均为为零零。试试问问该该厂厂应应如如何何安安排排各各个个时时期期的的生生产产与库存，才能在满足市场需求的条件下，使总成本最小与库存，才能在满足市场需求的条件下，使总成本最小。时期时期k1234需求量需求量dk2324解：解：（1）建立该问题的动态规划数学模型）建立该问题的动态规划数学模型状态变量：各阶段初的库存量，用状态变量：各阶段初的库存量，用sk表示表示决策变量：各阶段的生产量

35、，用决策变量：各阶段的生产量，用uk表示表示状态转移方程：状态转移方程：sk+1=sk+ukdk指标函数：指标函数：Vk，n=vk（sk，uk）+vn（sn，un）其中其中(2)递推计算递推计算 (3)寻优寻优 逐步板书逐步板书20052005年年9 9月月 龙子泉龙子泉第四节第四节 动态规划应用动态规划应用三、多阶段配置问题三、多阶段配置问题 问题描述问题描述 有某种资源，总数量为有某种资源，总数量为s1，可以用用于，可以用用于两种形式的生产：两种形式的生产：A和和B。已知这两种生产的收益。已知这两种生产的收益函数分别为函数分别为g(x)和和h(x)，其中，其中x为资源的投入量，且为资源的投

36、入量，且满足满足g(0)=h(0)=0。假设这两种资源用于生产后还。假设这两种资源用于生产后还可以回收一部分再用于生产。这两种生产的回收率可以回收一部分再用于生产。这两种生产的回收率分别为分别为a和和b(0a1，0b1)。现要求对总数量为。现要求对总数量为s1的资源进行的资源进行n个阶段的生产，每个阶段如何分配个阶段的生产，每个阶段如何分配投入到投入到A和和B的资源数量使总收益最大。的资源数量使总收益最大。设设ui为第为第i阶段投入到阶段投入到A生产的资源数量，则第生产的资源数量，则第i阶段投入到阶段投入到B生产的资源数量为生产的资源数量为siui，其中，其中si=aui1+b(si1ui1)

37、，这样该问题的，这样该问题的静态规静态规划数学模型划数学模型可描述为可描述为 该问题的该问题的动态规划数学模型动态规划数学模型如下如下状态变量：第状态变量：第k阶段可投入到阶段可投入到A、B两种生产的资源数量，用两种生产的资源数量，用sk来表示；来表示；决策变量：第决策变量：第k阶段投入到阶段投入到A生产的资源数量，用生产的资源数量，用uk表示，则表示，则skuk表示投入到表示投入到B生产的资源数量；且允许决策集合为生产的资源数量；且允许决策集合为 Dk(sk)=uk|0uksk(k=1，n)状态转移方程：状态转移方程：sk+1=auk+b(skuk)指标函数形式指标函数形式 Vk，n=g(u

38、k)+h(skuk)+g(un)+h(snun)动态规划方程动态规划方程20052005年年9 9月月 龙子泉龙子泉例例5.9 5.9 机机器器负负荷荷分分配配问问题题 某某种种机机器器可可在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产，设设机机器器在在高高负负荷荷下下的的产产量量函函数数为为g=8u，其其中中u为为投投入入生生产产的的机机器器数数量量，年年完完好好率率为为a=0.7；在在低低负负荷荷下下生生产产的的产产量量函函数数为为h=5y，其其中中y为为投投入入生生产产的的机机器器数数量量，年年完完好好率率为为b=0.9。假假 定定 开开 始始 生生 产产 时时 完完 好好

39、 的的 机机 器器 数数 量量 为为s1=1000台台，试试问问每每年年如如何何安安排排机机器器在在高高低低负负荷荷下下生产，使生产，使5年内生产的产品总产量最高年内生产的产品总产量最高 多阶段配置问题举例多阶段配置问题举例解：解：（1）建立该问题的动态规划数学模型）建立该问题的动态规划数学模型状态变量：第状态变量：第k阶段可投入到高低两种负荷的机器数量，阶段可投入到高低两种负荷的机器数量，用用sk来表示；来表示；决策变量：第决策变量：第k阶段投入到高负荷的机器数量，用阶段投入到高负荷的机器数量，用uk表示，表示，则则skuk表示投入到低负荷的机器数量；且允许决策集合表示投入到低负荷的机器数量

40、；且允许决策集合为为 Dk（sk）=uk|0uksk（k=1，5）。）。状态转移方程：状态转移方程：sk+1=0.7uk+0.9（skuk）指标函数形式指标函数形式 DP方程方程(2)递推计算递推计算 (3)寻优寻优 逐步板书逐步板书20052005年年9 9月月 龙子泉龙子泉第四节第四节 动态规划应用动态规划应用四、随机采购问题四、随机采购问题 前前面面我我们们讨讨论论的的都都是是确确定定性性的的多多阶阶段段决决策策问问题题。但但是是，在在人人们们的的实实践践活活动动中中，常常常常会会遇遇到到多多阶阶段段的的随随机机决决策策问问题题。这这里里讨讨论论的的随随机机采采购购问问题题就就是是其其中

41、中一一例例。下下面面举举两两个个简简单单的的例例子子来来说说明明此此类类问问题的求解。题的求解。例例5.10 某某部部门门打打算算在在近近五五周周内内采采购购一一批批原原料料。事事先先可可估估计计出出来来五五周周的的每每周周内内可可能能有有三三种种价价格格，而而每每种种价价格格的的概概率变化如表所示率变化如表所示 价格价格概率概率4504705000.250.350.40该该部部门门由由于于生生产产需需要要，必必须须在在这这五五周周内内采采购购此此种种原原料料。如如果果第第一一周周内内价价格格偏偏高高，可可以以等等待待到到第第二二周周或或第第三三周周或或第第四四周周，以以至至于于在最后一周（即

42、第五周）在最后一周（即第五周）进进行行采采购购；如如果果第第一一周周及及第第二二周周价价格格都都偏偏高高，可可以以等等待待到到第第三三周周或或第第四四周周后后最最后后一一周周进进行行采采购购；以以此此类类推推，如如果果认认为为前前四四周周价价格格都都偏偏高高，则则在在第第五五周周（即即最最后后一一周周）不不管管市市场场价价格格如如何何都都必必须须购购买买。现现在在的的问问题题是是，究究竟竟在在哪一周、按什么价格进行采购才是最佳的决策。哪一周、按什么价格进行采购才是最佳的决策。解：解：这里价格是一个随机变量，是按某种已知的概率分布这里价格是一个随机变量，是按某种已知的概率分布取值的。用动态规划方

43、法求解的过程如下。取值的。用动态规划方法求解的过程如下。按采购期限按采购期限5周将问题划分为周将问题划分为5个阶段；个阶段；将每周的价格看作个阶段的状态，用将每周的价格看作个阶段的状态，用sk来表示；来表示；每周是否决定采购为决策变量，用每周是否决定采购为决策变量，用uk表示，当表示，当uk=1 时，时，表示第表示第k周决定采购，当周决定采购，当uk=0时表示第时表示第k周决定等待。周决定等待。则问题的动态规划逆序递推关系式为则问题的动态规划逆序递推关系式为式中式中 fk（sk）表示第）表示第k阶段实际价格为阶段实际价格为sk时，从第时，从第k周至第周至第5周采取的最优策略所得到的最低采购费用（当然，周采取的最优策略所得到的最低采购费用（当然，这里假定前这里假定前n1周均没有进行采购）。周均没有进行采购）。Fk+1表示第表示第k周决周决定等待，而在以后采取最优决策时采购费用的期望值，定等待，而在以后采取最优决策时采购费用的期望值，用下式计算用下式计算式中式中其中其中pj表示第表示第k+1阶段在价格为阶段在价格为 时的概率时的概率 递推计算递推计算 寻优寻优 逐步板书逐步板书此外此外,例例5.11 是一个四周期的采购问题是一个四周期的采购问题,而且每周期而且每周期的价格及其概率均不同的价格及其概率均不同.可用上述类似的解法求解可用上述类似的解法求解