3.3 动态规划的应用举例(南航).pptVIP

第三节 动态规划的应用举例 定价问题 资源分配问题 生产存储问题 一、定价问题 某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。 建立数学模型 按年划分阶段，k=1,2,...,5 每阶段的状态变量为本年(上一年已确定)的价格，状态变量的可行集合Sk=(5,6,7,8)。 决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是： 采用逆序算法，因此状态转移方程是 最优值函数递推方程为 进行各阶段的计算 采用逆序法，设 当k=5时，S5=(5,6,7,8)，由表3-1得到 当k=4时， S4=(5,6,7,8)，由递推方程 得 继续求解 同理得其它各阶段的最优解 反推得最优路线 按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。即从第一年单价应为8元开始，向后推算。 得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。 最大利润值为92万元。 也可用决策图求解 二、资源分配问题 某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂或设备后可产生如表3-2所示的利润，应怎么分配设备可使公司总利润最大？ 建立数学模型 按工厂次序划分阶段，k=1，2，3，4 状态变量为各阶段可用于分配的设备总台数 决策变量是分配给第k工厂的设备数 采用逆序算法，状态转移方程 最优值函数递推方程 第4阶段的最优解 当k=4时，S4=(0,1,2,3,4,5) 第3阶段的最优解 当k=3时，S3=(0,1,2) 第3阶段的最优解（续） 当k=3时，S3=3 第3阶段的最优解（续） 第3阶段的最优解（续） 第2阶段的最优解 当k=2时，S2=(0,1,2) 第2阶段的最优解（续） 第2阶段的最优解（续） 第2阶段的最优解（续） 第1阶段的最优解（续） 反向求最佳状态路线 三、生产存储问题 某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。 已知的其它条件 已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元；每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。 设第k月的生产量uk，存储量为Sk,则总成本为 建立数学模型 以月划分阶段，k=1,2,3,4 各阶段决策变量为该阶段生产量uk，状态变量为该阶段的存储量Sk。 采用逆序算法，则状态转移方程为 最低成本递推公式是 第四阶段的最优解 当k=4时，d4=4,因第四阶段末无存货，因此S4=(0,1,2,3,4) 第三阶段最优解 当k=3时，由于 ，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6) 第三阶段最优解:S3=1 第三阶段最优解:S3=2 第三阶段最优解:S3=3,4 第三阶段最优解:S3=5,6 第二阶段最优解 当k=2时，d2=3，由于最大生产能力为6，而d1=2，因此S2=(0,1,2,3,4) 第二阶段最优解:S2=1 第二阶段最优解:S2=2 第二阶段最优解:S2=3 第二阶段最优解:S2=4 第一阶段最优解 当k=1时，d1=2，S1=0 最优解 从第一阶段向后反推最优路线，总结可得 习题 P.264，习题2、3、4、5。 16.5 17 15.5 16.5 17.5 11.0 10.5 8.0 8.0 8.0 0 1 2 3 4 5.5 6.5 7.5 8.5 9.5 0.5 0.5 0.5 0.5 0.5 5 6 7 8 9 2 3 4 5 6 1 存储 生产 f2(S2) f3(S3) S3 C2 本期成本 u2 S2 16.0 16.5 15.0 16.0 17.0 18.0 11.0 10.5 8.0 8.0 8.0 8.0 0 1 2 3 4 5 5 6 7 8 9 10 1 1 1 1 1 1 4 5 6 7 8 9 1 2 3 4 5 6 2 存储 生产 f2(S2) f3(S3) S3 C2 本期成本 u2 S2 12.5 16.0 14.5 15.5 16.5 17.5 15.5 11.0 10.5 8.0 8.0 8.0 8.0 5.0 0 1 2 3 4 5 6 1.5 5.5 6.5 7.5 8.5 9.5 10.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 0 4 5 6 7 8 9 0 1 2 3 4 5 6 3 存储 生产 f2(S2) f3(S3) S3 C2 本期成本 u2 S2 12.5 14 15 16 17 15 10.5 8.0 8.0 8.0 8.0 5.0 1 2 3 4 5 6 2 6 7