动态规划课件.ppt

《动态规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§5.4动态规划的应用举例§5.4.1资源分配问题假设有某种资源，总数量为a,用于生产n种产品，若分配数量用于生产第i种产品，其收益为要求如何分配使得生产n种产品的总收入最大？上述问题的数学模型为静态规划问题分析：这类问题称为资源分配问题，可用动态规划来求解。通常将资源分配给一个或几个使用者的过程作为一个阶段，将问题中的变量作为决策变量，进行递推，再将随之累计的量作为状态变量。设状态变量分配给第k种产品至第n种产品的原料数量决策变量分配给生产第k种产品的原料数，即状态转移方程：允许决策集：最优值函数以数量为的原料分配给第k种产品至第n种产品所得到的最大总收

2、入。故有动态规划的递推关系：利用这个递推关系式进行逐阶段计算，最终求得为所求问题的最大总收入。例5.4.1某企业集团购置了3台设备，分配给所属的甲、乙、丙3个工厂使用。由于各工厂外部环境及内部条件有差异，在获得这些设备后所得盈利也各有不同，如表5.4.1所示。问：该集团应如何分配，使所得的利益最大？设备台数盈利甲厂乙厂丙厂00001354281063131114表5.4.1解：用动态规划求解。将该问题分为3个阶段，丙3个工厂分别为编号1、2、3。甲、乙、设分配给第k个工厂至第n个工厂的设备台数；分配给第k个工厂的设备台数；分配给第k+1个工厂至第n个工厂的

3、设备台数；台设备分配到第k个工厂所得的盈利值；台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。因而可写出逆推式：下面从最后一个阶段开始向前逆推计算。第三阶段：此时已给甲乙两厂分配完毕，现在要丙厂进行分配，而目前所剩设备套数为这样，允许决策为具体的数值计算可归结为表5.4.2。00——————00104————412046——62304614143表5.4.2因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值。在这个表中，当时，则也对应为3，这时取得最大赢利而最优解为第二阶段：此时，已给甲厂分配完毕，还剩套设备需要

4、分给乙、丙厂。现在要给乙厂分配套设备。如表5.4.3所示。列表求解00——————0010+45+0————5120+65+410+0——10230+145+610+411+0140或2表5.4.3因为给乙厂台，其盈利为余下的就给丙工厂，台则它的盈利最大值为第一阶段：由于最初有3台设备可供分配，因而是固定的。同时，我们可列出表5.4.4进行数值分析。30+143+108+513+0140表5.4.4从而，可以得到如下解：或者由于在时，从表5.4.3中可以看出，或有两个不同的解。因此，虽然有两个不同的最优解，应的最优值但相是相同的，均为14。§5.4.2生产

5、经营问题例5.4.2采购问题状态转移出现了随机性的因素，不能完全确定随机性的决策过程随机性动态规划可用动态规划方法处理某厂必须在今后的5周之内购买一批原材料，根据过去的资料统计，概率如表5.4.5所示。未来5周之内的浮动价格和概价格（元）概率5000.36000.37000.4表5.4.5问应该在哪一周以什么价格购入，才能使其采购原材料的价格最低？解：用动态规划的方法。将每周的价格看作该阶段的状态。按采购期限分为5个阶段，表示今后每周的序号。设状态变量第k周的原料实际价格；决策变量时，表示采购；时，表示等待第k周决定等待，而在以后采取最优策略时采购价格的期

6、望值；第k周价格为时，从第k周到第5周采取最优策略所得的最小期望值。得到逆推关系式为其中并且得出最优决策为从最后一周开始，逐步向前递推计算，过程如下：当k=5时，因为是最后一周，所以如果还没有买入原料，则无论市场价格如何，都必须购买。当k=4时，所以第四周的最优决策为同理可得所以而所以而所以因此，我们可以知道，最优策略为：在第一、第二、第三周若原材料价格为500时，就应该立即采购，否则等待，等以后再采购；在第四周的时候，若价格为500或600时，就应该立即采购，否则等到第五周再采购；在第五周时，无论原材料什么价格，都应该按价采购。采购的期望值为525.38

7、2元例：用动态规划方法求解非线性规划问题：§5.4.3设备更新问题设备（含机器、仪器等）更新改造使用年限增加发生损坏和老化维修购置新设备花费较大的维修费用影响到企业的经济效益花费比较大的投资但效益往往相当可观如何寻求设备更新的最优策略？基本假设：设备已使用过的年限，即它的机龄（役龄）；机龄为t的一台设备运行一年带来的收入额；机龄为t的一台设备每年所需的维修费；卖掉一台机龄为t的旧设备所得的折价费；购置一台新设备的费用，T为更新周期；不考虑货币现值的折扣率，即假设折扣率为1。假定有一台机龄为t的设备，若使用一年，则这一年的纯收入为若将它卖掉而买一台新的，则这

8、一年的纯收入为考虑到今后第n年为止，则有这里f(t)表示一台已使用