动态规划应用举例.ppt

1、第九章：动态规划应用实例，第一节：资源分配问题分配问题：将一定数量的资源(如原材料、资金、机械设备、劳动、食品等)适当地分配给多名用户，优化利润函数。1.1多元投资分配问题(离散)安装了某种原料，总数量为A，用于生产N种产品。分配数量Xi用于生产我的I产品时，其收入是gi(xi)，如何分配以最大限度地提高生产N个产品的总收入？静态计划，决策变量uk表示分配用于生产第K个产品的原料数量(例如，UK=XK)。状态变量sk表示分配用于将第K个产品生产为第N个产品的原料数量。状态转换方程：sk 1=sk-uk=sk-xk决策集：Dk(sk)=uk|0uk=xksk最佳函数fk(sk)表示将sk数量的原

2、料分配给第k个产品时可以获得的最大总利润。5个牙齿的设备是如何分配给每个工厂的，解决：根据工厂将问题分为3个阶段，将甲方分别编号为1，2，3。用k表示，即步骤变量决策变量uk表示分配给第k工厂的设备数(例如，uk=xk)。状态变量sk显示从第K个工厂到第3个工厂分配的设备数。状态转换方程：sk 1=sk-uk=sk-xk决策集：Dk(sk)=uk|0uk=x3(s3最佳函数fk(sk)表示sk单位的设备数从k工厂分配到第n个工厂的最大总利润，结果如下表所示k=步骤2，s3=s2-x2，0s25，0 x2s2，范例，结果如下表所示。k=步骤1，s2=s1-x1，S1=；即得甲工厂分配0台，乙工厂

3、分配2台，兵工厂分配3台。据调查，由于X1*=2，因此s2=s1-x1*=5-2=3，x2*=2，s3=s2-x2*=3-2=1，因此有2家得甲工厂，2家乙工厂上述两个茄子分配方案获得的总利润共21万元。问题：如果原来的设备数量是4台，你会寻找最佳分配方案吗？如果原来设备代数是3台，那么求最优分配方案吗？1.2资源的连续分配问题：一般问题的提法是如何确定N年内投入A的资源量u1，un，使总收入最大化。(威廉莎士比亚、Northern Exposure(美国电视电视剧)和资源)，牙齿问题的静态计划问题模型如下：动态规划逆推关系方程如下：最后得出的f1(s1)牙齿问题的最大收入。例2机器负荷分配问

4、题有些机器可以在高低两个茄子不同的负荷下生产。在高负荷情况下设置机器的产量为g=8x，其中x是投入生产的机器数，年完税率为a=0.7，在低负荷情况下，产量为函数h=5y。这里，y是投入生产的机器数，年完税率为b=开始生产时完整的机器数为1000台，那么每年高低两个茄子负荷下，如何安排机器的生产，5年内生产的产品总产量最高？允许决策集合0uksk，解决方案：设置步骤数k表示年。状态变量sk是K年年初拥有的良好机器数量。决策变量uk是在K年分配高负荷下生产的机器数。因此，低负荷下生产的机器数量是sk-uk。状态转移方程，k年产量，指标函数，迭代方程，类比，双节生产和存储问题，所谓生产和库存问题是生

5、产部门。在已知生产成本、库存成本和每个阶段的市场需求条件下确定每个阶段的产量，使计划内成本总和最小的方法。很多问题可以转化为这样的问题来解决。生产和库存问题本身是多阶段的决策过程。设定生产部门，生产周期分为n个阶段，初始库存量x1，阶段市场需求为dk，生产固定成本为k，单位产品冲销成本为l，单位产品阶段存货成本为h，仓库容量为m，阶段产能为b。询问如何安排各阶段的产量，以最小化计划周期内的总成本。状态变量xk被选择为步骤k的初始现有量。x1牙齿是已知的。xn 1=0。阶段K的现有库存量不能超过库存容量M，阶段K至阶段N的总需求金额(即决策变量uk)不能超过为阶段K的产量选择的值。阶段生产不得超

6、过生产能力与从k阶段到n阶段的总需求减去k阶段初的现有量，并且必须大于该阶段需求与现有量之间的差额。也就是说，状态转移方程是阶段成本等于阶段生产成本与库存成本之和的阶段k的生产成本，k阶段末的库存成本，动态规划基本方程，示例已知的n=3，k，解：使用上述递归方程，如果是这样的话，结果请参阅下表。，随着使用年限的增加，设备陈旧，处理价钱数量低，维修和更新成本增加。不同阶段的设备总是面临保留或更新问题。预留或更新，必须在整个计划期间的总收回金额中考虑，在某些阶段的收回金额中不考虑是多阶段决策问题。第三节：设备更新问题、设备更新问题(例如一台机器):n是设备的计划使用年限。Ik(t)是K年(阶段)机

7、器服务年龄为T年的一台机器运行(再使用一年)所得。Ok(t)是第K年机器服务年龄为T年的一台机器运行(再使用一年)所需的运营费(或修理费)。Ck(t)是更新K年机器服务年龄为T年的一台机器所需的净费用(处理一台服务年龄为T的旧设备和购买新设备的净费用)。打折因素，表示一年后的收入是上一年的单位。N年内每年年初要求决策，继续使用旧设备或一台更换的新的，能最大限度地提高N年内的总效益吗？将动态规划模型设置为：步骤k(k=1，2，n)表示设备使用计划期间数。状态变量sk: K秒，设备已使用的年数，即服务年龄。决策变量xk:是更新k秒(Replacement)还是保留现有设备(Keep)(分别用k、r表示)。状态转移方程：阶段收益：最佳指标函数fk(sk): K年初，已使用sk年的设备，到N年末为止的最大收益，动态规划基本方程，事实上，例如，新设备的年度收益和年度维修成本，更新净成本下表