第六章-动态规划PPT课件.ppt

第六章动态规划 1 期中考试分析 2 第一节多阶段的决策问题 例1 多阶段网络最短路 A B1 B2 B3 C3 C1 C2 D1 D2 E 1 2 3 4 2 4 3 7 4 6 3 2 2 4 4 1 5 1 4 6 3 3 3 3 4 3 例2 资源分配问题 4 第二节动态规划的基本概念和动态规划的基本原理 一 基本概念1 阶段 指一个问题需要做出决策的步数 用k表示阶段变量 如有时间因素 则阶段变量为时间 如是其他问题 要具体分析 2 状态 表示在任意阶段所处的位置 记作Xk 状态变量3 决策 某阶段状态给定后 从该状态演变到下一阶段某状态的选择 用uk xk 表示 意为在k阶段上处于xk状态上做一决策 转到下一阶段的某一状态上 5 4 策略 由每个阶段的决策组成的序列总体称为一个策略 记为p1n x1 5 状态转移率 从上一阶段的某一状态值到下一阶段的某一状态值的规律称为状态转移率 记作xk 1 T xk uk xk 6 指标函数 是用来衡量过程优劣的数量指标 记为vk n 意为从第k个阶段到第n个阶段的指标值7 最优效益值 fk xk 从第k个阶段起的最优效益值 6 二 动态规划的基本思想以最短路问题为例说明 最短路的子路一定是最短的 由此得到启发 求最短路是从后向前作 动态规划的基本思想在此 但有些问题也可以从前向后作 无论过去的状态和决策如何 对前面的决策所形成的状态而言 余下的储决策必须构成最优策略 三 动态规划的基本方程fk xk opt dk xk uk fk 1 xk 1 fk 1 xk 1 01 划分阶段 根据问题的性质识别出问题的多阶段特性 并按时间或空间顺序将过程划分为相互联系的阶段2 要正确的选择xk 使它能够描述过程的演变特征 并且他的值应是已知 同时要满足后效性3 确定决策变量uk 写出状态方程 写出递推关系 7 第三节动态规划的应用实例 某公司购进5套设备 要分配给下属的甲 乙 丙三个工厂 各工厂获得设备后每年为公司提供的盈利 万元 如下表 问如何分配 可使公司获利最大 例1 离散型的资源分配问题 设备 商品分配问题 8 练习 有一部货车 沿途给四个零售店送4箱货 各零售店售出货物的利润如下表所示 试求分别在各零售店卸下几箱货可使总利润最大 9 例2 机器负荷问题 某种机器可以在高低两种不同负荷下生产 在高负荷下生产时产品的年常量g x 8x 设备回收率a 0 7 在低负荷下生产时产品的年产量h y 5y 回收率b 0 9 若开始时 完好机器数x1 1000台 问每年如何安排生产使五年内总产量最高 10 作业 有某种饲料 可用于两种生产 除产生一定效益外 还可回收一部分 已知采用第一种方式生产的收益函数是0 6x 回收率是0 1 采用第二种方式的收益函数是0 5y 回收率是0 4 现有原材料100吨 连续进行3个阶段生产 问如何安排生产效益最大 11 例3 生产 库存问题 某工厂要对一种产品制定今后四个时期的生产计划 据估计在今后四个时期内 市场对于该产品的需求量如表所示 假定该厂生产每批产品的固定成本为3千元 若不生产就为0 每单位产品成本为1千元 每个时期生产能力所允许的最大生产批量为不超过6个单位 每个时期期末未售出的产品 每单位需付存储费0 5千元 还假定在第一个时期的初始库存量为0 第四个时期期末的库存量也为0 试问该厂如何安排各个时期的生产与库存 才能在满足市场需要的前提下 使总成本最小 12 例4 库存 销售问题 某公司计划在1至4月份从事某种商品经营 已知仓库最多可以存储600件这种商品 已知1月初存货200件 根据预测知1至4月份各月的单位购货成本及销售价格如表所示 每月只能销售本月初的库存 当月进货供以后各月销售 问如何安排进货量和销售量 使该公司四个月获得利润最大 假设四月底库存为0 13 例5 存储控制问题 某鞋店销售一种雪地防滑鞋 以往的销售经历表明 此种鞋的销售季节从10月1日至3月31日 下个销售季节各月的需求预测值如表所示 该鞋店的此种鞋完全从外部生产商进货 进货价每双4美元 进货批量的基本单位是箱 每箱10双 由于存储空间的限制 每次进货不超过5箱 对应不同的订货批量 进价享受一定的数量折扣 具体数值如表所示 假设需求按一定速度均匀发生 订货不需时间 但订货只能在月初办理一次 每次订货的采购费 与采购数量无关 为10美元 月存储费按每月月底鞋的存量计 每双0 2美元 由于订货不需时间 所以销售季节外的其他月份的存储量为0 试确定最佳的进货方案 以使总的销售费用最小 14 需求预测值单位 双 数量折扣数值表 15 16 例5 背包问题 一个徒步旅行者有三种物品供他放入包中 已知每种物品的重量及对旅行者的使用价值 已知这位旅行者所能承受的重量不超过5公斤 问他应该选择每种物品各多少件放入包中 才能使其获得的使用价值最大 17 设有一辆10吨的大卡车 可装载三种不同货物 已知三种货物的单件重量和装载收费如下表所示 问如何装载 可使一次收入最多 作业 18 作业 某商店准备在未来四个月里 准备利用一季度专门经销某种商品 仓库最大容量为这种商品1000个单位 假