吉林大学本科运筹学课件-动态规划应用举例吉林大学本科运筹学课件-动态规划应用举例.pptVIP

清华大学出版社 第七章 动态规划 动态规划的基本方法 动态规划应用举例 动态规划应用举例 第1节 资源分配问题 第2节 生产与存储问题 第3节* 背包问题 第4节* 复合系统工作可靠性问题 第5节 排序问题 第6节 设备更新问题 第7节* 货郎担问题 第1节 资源分配问题 所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地分配给若干个使用者，而使目标函数为最优。 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 1.1资源分配问题 第2节 生产与存贮问题 企业一年中的产品生产往往是分期分批生产的。 组织每批产品的生产，都要花费一些生产准备费和存贮费用。 若某一时期增大生产批量则可减少生产批次，从而降低生产成本。 与此同时，批量大了，必然增加库存而使存贮费用增加。 在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。 2.1 生产与存贮问题 设某公司对某种产品要制定一项多阶段的生产(或购买)计划。已知它的初始库存量为零，每阶段生产(或购买)该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产(或采购)计划，从而使总成本最小。 生产计划周期分为n个阶段，即k=1~n； 已知最初库存量为S1=0； 阶段需求量为dk； 单位产品的消耗费用为Lk； 单位产品的阶段库存费用为hk； 仓库容量为Mk； 阶段生产能力为Bk； 生产的准备费用为： 例5 某工厂与用户签订了4个月的交货合同如表所示 动态规划的数学模型 每个月为一个阶段，即阶段变量 k=1,2,3,4分别表示这四个月; 状态变量sk 表示第k 月初的产品库存量，0≤ sk ≤4; 决策变量xk 表示第k月的生产量 ， 允许决策集合Xk (sk)={ xk ︱0≤ xk ≤5}; 状态转移方程为 sk+1 = sk + xk – dk ; 阶段指标vk(sk, xk) 表示第k月的费用 ：本月若不安排生产，则仅需支出保管费；本月若安排生产，则需支出生产费用和固定费，同时还需交付保管费。 当xk =0时， vk(sk, xk)=h ·sk =0.2sk 当xk ＞0时， vk(sk, xk)=b+c·xk+h·sk =2+xk +0.2sk 最优指标函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优生产策略实现的最低生产费用。 逆序求解 K=4 k=3 k=2 k=1 2.2 不确定性的采购问题 2.2 不确定性的采购问题 2.2 不确定性的采购问题 2.2 不确定性的采购问题 2.2 不确定性的采购问题 2.2 不确定性的采购问题 2.2 不确定性的采购问题 2.2 不确定性的采购问题 第3节 背 包 问 题 第3节 背 包 问 题 第3节 背 包 问 题 第3节 背 包 问 题 第3节 背 包 问 题 第3节 背 包 问 题 第3节 背 包 问 题 第3节 背 包 问 题 第4节复合系统工作可靠性问题 第4节复合系统工作可靠性问题 第4节复合系统工作可靠性问题 第4节复合系统工作可靠性问题 第4节复合系统工作可靠性问题 第4节复合系统工作可靠性问题 第4节复合系统工作可靠性问题 第4节复合系统工作可靠性问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第5节 设备更新问题 第6节* 货郎担问题 第7节* 货郎担问题 第7节 货郎担问题 第7节* 货郎担问题 第7节 货郎担问题 第7节* 货郎担问题 当j=5时，由于设T=1 ，故从第5年开始计算时，机器使用了1、2、3、4、5年，则递推关系式为 因此 同理 当j=4时，递推关系为 故 同理 依照上述最优策略进行采购时，价格(单价)的数学期望值为 f1(s1)=0.3*f1(500)