第5章动态规划

1、管理运营计划学，讲师：马越峰，第五章动态计划，5.1 .动态计划的基本概念和优化原理，5.2 .动态计划模型的构建和解决，5.3 .动态计划在经济管理中的应用，5.1 .动态计划的基本概念和优化原理，例1最短路径问题的下图将起点a到终点e的各点的距离求从a到e的最短路径。 讨论： 1，以上从a到e的最短路径问题，4个性质完全相同，但可以改变为规模较小的子问题，即Di、Ci、Bi、从a到e的最短路径问题。 第四阶段：发现两个起点D1和D2，终点只有一个，从D1和D2到e的最短路径是唯一的。 第三阶段：有三个起点C1、C2、C3，有终点D1、D2，分析起点和终点，分别求出从C1、C2、C3到D1、

2、D2的最短路径问题：通过C1后，知道最短短路为C1-D2-E，经过C2后第二阶段：有四个起点B1、B2、B3、B4、终点C1、C2、C3。 分析并讨论起点和终点，分别是从B1、B2、B3、B4到C1、C2、C3的最短路径问题：第一阶段：起点a只有一个，终点为B1、B2、B3、B4。 分析和讨论起点和终点，分别求出从a到B1、B2、B3、B4的最短路径问题：最后，从a到e的最短路径可以用AB4C3D1E，一，基本概念： 1，阶段k :表示决策顺序的离散量，阶段可以用时间和空间来划分。 2、状态sk :表示各阶段开始的自然状况和客观条件。 状态可以是数量或文字，数量状态可以是连续的或离散的。 3、

3、决定xk :从某个状态转移到下一个状态时的选择。 决策是某个状态的函数，记为xk(sk )。 决策许可集合Dk(sk ) :在状态sk中，许可整个决策。 D3(C1)=D1，D2，基本概念，基本方程式和优化原理，s3=？ 4、策略Pk，n(sk ) :从第k阶段到最后第n阶段的决策序列，称为k子策略。 P1，n(s1)是全过程战略。 5、状态迁移方程式sk 1=Tk(sk，xk ) :某个状态和该状态下的决定，与下一个状态的函数关系。 6、阶段指标函数vk(sk，xk ) :从状态sk中选择基于决策xk的第k阶段指标。 过程指标函数Vk，n(sk，xk，xk 1，xn ) :从状态sk中选择基

4、于确定xk，xk 1，xn的过程指标。 二、对于根据基本方程：最佳指标函数fk(sk ) :状态sk的所有策略Pk，n、过程指标Vk，n的最佳值，即，加性指标函数，上式必须设定最佳指标的终端条件以使终端条件：以上的递归方程具有递归起点三、优化原理作为整个过程的最佳策略，无论该最佳策略上的某个状态以前的状态和决策，对于该状态，今后的所有决策都有一定构成最佳子策略的性质。 也就是说，最佳战略的子战略都是最佳的。 一、资源分配问题示例2:某公司计划将某设备分配给5台，所属甲、乙、丙三个工厂，各工厂获得该设备后，预测可创造的利润如表所示，如何将这5台设备分配给这三个工厂，以最大化所创造的总利润。5.2

5、动态计划模型的构建和解决、解决：问题按工厂分为三个阶段，甲、乙、丙三个工厂各有一、二、三个工厂号。 假设sk=分配给第三个工厂的设备台数(k=1，2，3 )被分配给第sk=第三个设备台数。 由于已知s1=5，有这样的定义，所以如下从第三阶段开始计算。 第三阶段：显然是给第三工厂分配了设备，也就是说，因为第三阶段的指标值(即第三工厂的利益)最大，即第三阶段是最后的阶段，所以其中可以取0、1、2、3、4、5的值。 其数值计算如表所示。、第二阶段：将设备分配给第二工厂和第三工厂时，按值有最佳分配方案，以最大利润，即最佳第二子流程的最佳指标函数值。 上式也表示了其数值计算。、第一阶段：将设备分配给第一

6、、第二、第三工厂的情况下，最大利润是看其中理想的值0、1、2、3、4、5 .根据计算表的顺序推算，可知最佳分配方案有2个：甲： 0台乙： 2台丙： 3台乙： 2台第I种商品每件重量为wi公斤，每件价值为ci元。 现在，能装载重量为w公斤的背包，要求把各种各样的物品放在背包里，背包中的物品的价值最高。 这个问题可以用整数规划模型描述。 设xi是第I个物品装在背包里的件数(I=1，2，n )，设背包里的物品的合计价值为z，则以maxz=c 1x1 C2 x2cn xns.t.w 1x1 w2 x2 wnxnwx 1，x2，xn0为整数。 5.3动态计划的应用，示例3:中的一家咨询公司可以在10个工

7、作日内处理4种咨询项目，并表示各种咨询项目中处理的客户数量、每个客户所需的工作日、利润。 显然该公司在10天内处理不了所有顾客。 它可以自己选择客户，委托其他咨询公司，如何选择客户在这10个工作日内最大化利益？ 解：用动态计划解决这个问题。 我们把这个问题分成四个阶段，第一阶段处理多少第一咨询项目类型的顾客，第二阶段处理多少第二咨询项目类型的顾客，第三阶段、第四阶段也作出同样的决定。 我们设定分配给第k个咨询项目到第4个咨询项目的所有客户的总工作日(第k阶段的状态变量)。=在第k个咨询项目中处理客户数量(第k阶段的决策变量)。 已知最多为10，其数值计算为表、第四阶段：第三阶段：第二阶段：第一阶段：最佳解：1 .石油输送配管铺设最佳方案的选择问题询问敷设管道的方法总费用最小。 练习. B3，B1，B2，a，C1，C2，C3，D1，D2，3，5，4，6，3，3，2，4，4，1，5，2，5，7，4，5，4，3，4，2 .某公司为a， b有400万元资金的c3个项目追加投资，3个项目可以具有不同的投资额，各自的利润值如下，第一次询问如何分配资金使总利润最大化，3 .某工厂为了扩大生产能力，将某一套设备计划分配2、3个工厂使用，各工厂