动态规划问题课件

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