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