33-动态规划的应用举例(南航)课件

第三节动态规划的应用举例定价问题资源分配问题生产存储问题一、定价问题某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。单价第一年第二年第三年第四年第五年5元6元7元8元1012141612131415151616152020181425241814表3-2每年预计利润额建立数学模型按年划分阶段，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所示的利润，应怎么分配设备可使公司总利润最大？工厂设备数甲乙丙丁012345067101215037912130510111111046111212建立数学模型按工厂次序划分阶段，k=1，2，3，4状态变量为各阶段可用于分配的设备总台数决策变量是分配给第k工厂的设备数采用逆序算法，状态转移方程最优值函数递推方程第4阶段的最优解当k=4时，S4=(0,1,2,3,4,5)012345012345046111212046111212012345第3阶段的最优解当k=3时，S3=(0,1,2)000000010105404551201205106406910102第3阶段的最优解（续）当k=3时，S3=3301230510111164011111411142第3阶段的最优解（续）当k=3时，S3=44012340510111112116401216161511161，2第3阶段的最优解（续）当k=3时，S3=550123450510111111121211640121721171511212第2阶段的最优解当k=2时，S2=(0,1,2)000000010103505350201203710501087100第2阶段的最优解（续）当k=2时，S2=33012303791410501413129140第2阶段的最优解（续）当k=2时，S2=4401234037912161410501617171412171，2第2阶段的最优解（续）当k=2时，S2=55012345037912132116141050211921191715210，2第1阶段的最优解（续）当k=1时，S1=5

50123450671012152117141050212321201715231反向求最佳状态路线方案一方案二工厂名分配设备数工厂名分配设备数甲乙丙丁1121甲乙丙丁1220三、生产存储问题某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。时期（月）需求量（dk）12342324已知的其它条件已知生产一件产品的成本是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)S4u4本期成本C4S5f5(S5)f4(S4)生产存储01234432107654000.511.5276.565.52000000000076.565.52第三阶段最优解当k=3时，由于，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6)S3u3本期成本C3S4f4(S4)f3(S3)生产存储0234565678900000567890123476.565.521212.51313.511第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生产存储112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生产存储2012340456711111156780123476.565.52811.512.012.510.0第三阶段最优解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生产存储3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第三阶段最优解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生产存储501042.52.52.56.5345.5288.560033425第二阶段最优解当k=2时，d2=3，由于最大生产能力为6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生产存储03456678900006789012311.010.58.08.01717.51617第二阶段最优解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生产存储123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5第二阶段最优解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生产存储2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0第二阶段最优解:S2=3S2u2本期成本C2S3f3(S3)f2(S2)生产存储3012345604567891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5第二阶段最优解:S2=4S2u2本期成本C2S3f3(S3)f2(S2)生产存储4012345045678222222267891012345610.58.08.08.08.05.012.51415161715第一阶段最优解当k=1时，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生产存储0234565678900000567890123416.015.515.012.512.52121.5