《动态规划问题课件.ppt》由会员分享，可在线阅读，更多相关《动态规划问题课件.ppt（14页珍藏版）》请在三一办公上搜索。
1、第一节 动态规划问题,1.1 多阶段决策问题,1.2 动态规划问题举例,2023/1/18,1.1 多阶段决策问题,所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优.,2023/1/18,动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。需指出：动态规划是求解某类问题的一种方法，是考察问题的
2、一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。,1.1 多阶段决策问题,2023/1/18,即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；,动态决策问题的特点：,系统所处的状态和时刻是进行决策的重要因素；,找到不同时刻的最优决策以及整个过程的最优策略。,2023/1/18,每个阶段都要进行决策,目的是使整个过程的决策达到最优效果。,多阶段决策问题：,是动态决策问题的一种特殊形式；,在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段；,2023/1/18,多阶
3、段决策问题的典型例子：1.生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。,1.2 动态规划问题举例,2023/1/18,生产决策问题,某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示：,2023/1/18,生产决策问题,假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足
4、夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要16元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？,2023/1/18,生产决策问题(续),2023/1/18,生产决策问题(续),5,2023/1/18,2.机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的
5、关系为g=g(u1),1.2 动态规划问题举例,这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au,0a1。,2023/1/18,在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为 h=h(u2),假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。,相应的机器年完好率b,0 b1。,机器负荷分配问题,2023/1/18,3.航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。,不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。,4.线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。,2023/1/18,5.最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。,
