运筹学14-动态规划II-11.pptVIP

第14讲 动态规划II 本讲提纲——动态规划应用举例 1. 资源分配问题 2. 背包问题 3. 机器负荷分配问题 4. 生产-库存问题 1. 资源分配问题 一般提法：设有某种资源，总量为a，可分配给n种生产经营活动，已知若向第i种活动分配xi数量的资源，可获得收益gi(xi)，问应如何分配资源，可获得最大收益？ 该问题的动态规划模型为： 阶段：按生产经营活动划分阶段，k=1,2,…,n 状态变量：sk表示可用于分配给第k至第n阶段的资源数量 决策变量： xk表示分配给第k阶段的资源数量 允许决策集合：Dk(sk)={xk |0≤ xk ≤sk} 状态转移方程： sk+1 = sk- xk 动态规划方程： 例：设有300万元资金用于3个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这3个工厂的投资额，使总利润增长额最大。 解：(1) 建立动态规划模型 阶段划分：把对第1，2，3个工厂的投资依次看成三个阶段的决策过程，k=1, 2, 3 状态变量：sk表示第k个阶段初所剩的投资额 决策变量： xk表示第k个阶段对第k个工厂的投资额 允许决策集合： 状态转移方程： 阶段指标： 表示第k个阶段对第k个工厂投资xk后的利润增长额，如表所示。 动态规划基本方程： (2) 用逆序法求解 k=3: 若到最后一个阶段(第3阶段)，系统所处的状态为s3(即还剩下s3数量的资金可用于对第3个工厂的投资)，则根据递归方程，最优指标函数： k = 2：根据递归方程，最优指标函数为 状态转移方程： k = 1：根据递归方程，最优指标函数为 状态转移方程： 2. 背包问题 例：有一辆最大货运量为5 t 的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如下表所示。问：应如何装载可使总价值最大？ 解：(1)动态规划建模 阶段划分：把装载第k种货物看作第k个阶段，k=1,2,3 状态变量 sk：第k个阶段装载时背包还可以装载的重量； 决策变量xk：第k个阶段装载第k种货物的件数； 决策允许集合： Dk(sk)={xk|0? xk?sk/wk，且xk为整数}； 状态转移方程：sk+1=sk-wkxk，wk为第k种货物的单位重量 阶段指标rk(sk, xk)：表示第k个阶段装载xk件第k种货物得到的价值，rk(sk, xk) = ckxk 递归方程： (2) 逆序法求解： k =3: 3. 机器负荷分配问题 某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。 解 建立动态规划模型： 阶段划分：分为5个阶段，每个阶段为1年。 状态变量：sk表示在第k阶段初拥有的完好机器数目， k=1,2,3,4,5。 决策变量：xk表示第k阶段中分配给高负荷状态下生产的机 器数目，k=1,2,3,4,5。显然sk - xk为分配给低负荷状态下生产的机器数目。 状态转移方程：sk+1=0.7 xk +0.9(sk - xk) 阶段指标： rk(sk, xk)=8 xk +5(sk - xk) 递归方程： 4. 生产-库存问题 一个工厂生产某种产品，1～7月份生产成本和产品需求量的变化情况如下表： 为了调节生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。 解：建立动态规划模型 例：书上例4-5 4 7 2 3 5 8 0 需求量(rk) 15 10 20 17 13 18 11 生产成本(ck) 7 6 5 4 3 2 1 月份(k) 阶段：以每个月份为阶段，k =1,2,...,7 状态变量：第k个月月初(发货前)的库存量，sk s1=2, s7 = r7 = 4 决策变量：第k个月的生产量，xk 决策允许集合： 状态转移方程： 阶段指标： 递归方程: 模型求解： * 0 2 6 9 3 0 3 5