第八章 动态规划.ppt

三、货物存储问题 例8.7．考虑下面三个月的库存问题，在每月初，公司必须决定在本月内，应生产多少产品。在一个月内生产x 单位的产品，所需成本为，其中，当时，。每月最多生产4个单位，每月的需求是随机的，或为1或为2单位。如果生产的数量大于需求，就出现库存。每个月末检查库存，1个单位的库存费用是1元。因为库存能力有限，每月末的库存量不能超过3单位。但同时要求必须及时满足需求。在第3个月末要把现有的库存以每单位2元的价格售出。在第1月的月初，公司有1单位的库存。如何制定生产策略使三个月内的期望费用最小。 解：划分阶段：将三个月份为三个阶段，每个月为一个阶段 状态变量：sk表示第k 个月初的库存数。则s1=1。 决策变量：xk表示第k月生产的单位数。 显然有状态转移方程：sk+1=sk+ xk - ak，其中ak为一随机需求量或为1或为2。 fk ( sk )表示第k个月初的库存是sk 时，第k 个月至第3个月内的最小期望费用。 则第3个月的期望费用是： 其中 当k=1，2时，有动态规划的基本方程： 其中 用逆序法求解得最优策略是 即第一个月生产3个单位，第二、第三个月不生产。最小成本是 元。 四、设备更新问题 现有一台效益函数为r(t)的设备，其维修费用为u(t)、更新费用为c(t)，需要在n 年内的每年年初做出决策，是继续使用旧设备还是更换一台新设备，使n年总效益最大。 设r(t)：在第k年设备已使用过t年，再使用1年时的效益。 uk(t)：在第k年设备已使用过t年，再使用1年时的维修费用。 ck(t)：在第k年卖掉一台已使用t年的设备，买进一台新设备的更新净费用。 a：折扣因子（0≤a≤ 1），表示一年以后的单位收入价值相当于现年的a单位。 如果年初决定把使用t年的旧设备再继续使用1年，则在这一年内所得回收额为： 如果年初决定把使用t年的旧设备卖掉购买一台新设备，则在这一年内所得回收额为： 建立动态规划模型 划分阶段：k（k=1,…,n）表示计划使用该设备的年限数。 状态变量sk：第k年初，设备已使用过的年数。 决策变量xk：第 k 年初更新，还是继续使用旧设备，分别用R 和 K 表示。 状态转移方程为： 动态规划的基本方程为： 五、资源分配问题 设有一原料，总量为a，用于生产n种产品。若分配数量xi 用于生产第i种产品，其产生的效益为ri(xi)。问如何分配，才能使生产n种产品的总收入最大？ 建立动态规划 划分阶段：将n 种产品按的序号排列，每种产品为一个阶段，分为n个阶段，k=1, … , n。 状态变量：sk表示分配给第k个产品至第n 种产品的资源数。 决策变量：xk表示分配给第k个产品的资源数。 状态转移方程：sk+1 = sk - xk fk (sk )表示在拥有资源sk，分配给第k种产品至第n 种产品所得到的最大总收入。 则有动态规划的基本方程： 边界条件：因为在第1阶段时的资源为总资源，到第n+1阶段时资源已分配完毕，所以s1=a，sn+1=0，fn+1(sn+1)=0。 六、复合系统可靠性问题 例8.9．某厂设计一种电子设备，由三种元件D1，D2，D3组成，已知这三种元件的价格和可靠性如表8-8所示。要求在设计中所使用元件的费用不超过105元，试问应如何设计使设备的可靠性达到最大(不考虑重量的限制)。 解：按元件种类划分为三个阶段，设状态变量sk(k=1,2,3)表示能容许用在Dk元件至D3元件的总费用；决策变量xk表示在Dk元件上的并联个数；Pk表示一个元件正常工作的概率，则 为xk个Dk元件不正常工作的概率，令最优值函数fk (sk)表示由状态sk开始从Dk元件至D3元件组成的系统的最大可靠性，因而有 由于s1=105，故此问题求只要出f1(105)即可. 同理 从而求得最优方案： ，即D1元件用1个，D2元件用2个，D3元件用2个，其总费用为100元，可靠性为0.648。 第四节 Lingo软件对几类特殊动态规划问题的实现 略 谢 谢！ 二、顺推法 逆推法是从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。如果过程是可逆的，即对每一状态，都可从状态转移方程 得到 ，则可用顺推法，由第一阶段开始，逐阶段向后，直至最后一个阶段。 下面再用顺推法求解例8.2。 例8.4．用顺推法求解例8.2 基本方程为： 第1阶段 ： 最优策略是 ： 第2阶段： 最优策略是： 第3阶段： 最优策略是： 第2