第五章动态规划建模与求解作业题解答

第五章动态规划建模与求解—作业题解答2.（2）某公司从事某种商品的经营，现欲制定本年度10月至12月的进货及销售计划。已知该种商品的初始库存量为2000件，公司库存最多可存放该种商品10000件。公司拥有的经营资金为80万元，据预测，10月至12月的进货及销售价格如表5.29所示。若每个月在1号进货1次，且要求年底时商品的库存量达到3000件。在以上条件下，问如何安排进货及销售计划，使公司获得最大利润？（不用考虑库存费用）（只建模，不求解）月份101112进货价格（元／件）909598销售价格（元／件）100100115解：（0）阶段划分：按月份划分阶段，阶段变量k=1,2,3。（1）条件1：状态及状态变量用kx表示k阶段的库存量，12000x件,43000x，最大库存量M＝10000件。0≤k阶段的库存量≤M,所以状态可能集：0kxM（2）条件2：决策及决策变量设ku，kv是k阶段的进货量和销售量，全部流动资金＝800000＋上一阶段的盈利＝800000元＋2,111,11()kkkkPvPu其中1,1kP，2,1kP是k－1阶段的进货价格和销售价格；1ku，1kv是k－1阶段的进货量和销售量（000,0uv）；1,kP，2,kP是k阶段的进货价格和销售价格（见数据表）。则：12,1,01,800000()0min{,}kmmmmmkkkPvPuuMxP，0kkkvxu。（3）条件3：状态转移方程1kkkkxxuv（k阶段的库存量＋k阶段的进货量－k阶段的销售量）（4）阶段效应和目标函数2,1,kkkkkrPvPu31kkRr（5）动态规划的基本方程2,1,11,44()max{()}()0kkkkkkkkkkuvfxPvPufxfx第五章动态规划建模与求解—作业题解答2.（4）某公司计划用100万元对其三个分厂进行投资，三个分厂的投资方式各不相同，其投资和收益测算如表5.31所示，试用动态规划方法为该公司制定最佳投资方案（不求解）。分厂投资方式投资数量预期收益一分厂115102201533020二分厂12010225203352544530三分厂11062151133018解：（0）阶段划分：按照三个分厂的投资活动分为三个阶段，阶段变量k=1,2,3;（1）条件1：状态及状态变量设kx为k阶段初期拥有的资金量，1100x万元，40x。状态可能集：0100kx（2）条件2：决策变量及决策允许集合设ku为k阶段对第k个分厂的实际投资方式。kkuU，1{1,2,3}U，2{1,2,3,4}U，3{1,2,3}U设第k阶段对第k分厂的投资方式为ku时，实际投资额为()kkIu，收益为()kkgu。（3）条件3：状态转移方程1()kkkkxxIu（4）条件4：阶段效应和目标函数()kkkrgu31()kkkRgu（5）动态规划基本方程：1144()max{()()}()0kkkkkkkufxgufxfx第五章动态规划建模与求解—作业题解答3).某旅行者希望从s地到t地，其间的道路系统如图5.9所示，图上圆圈表示途经的地方，连接两地的箭线表示道路，其上数字表示该道路的长度，箭头表示通行的方向。试求s到t的最短路。解：方法1—分步计算法（从第3阶段开始）①当k=3时，{,,}idef，{}jt；4()0ft若id，则344()max{()}()505ijdtjtfdcfjcft，*3()jdt若ie，则344()max{()}()707ijetjtfecfjcft，*3()jet若if，则344()max{()}()404ijftjtffcfjcft，*3()jft②当k=2时，{,,}iabc，{,,}jdef；若ia，则32,,3()75()minmin8()44adjdefafcfdfacff，*2()jaf若ib，则32,3()55()minmin10()67bdjdebecfdfbcfe，*2()jbd若ic，则323,,3()45()min()min579()64cdcejdefcfcfdfccfecff，*2()jcd③当k=1时，{}is，{,,}jabc；212,,2()98()min()min81016()79sasbjabcsccfafscfbcfc，*1()jsc故从s地到t地的最短路线是：scdt即{,,,}scdt。sabcdeft9874757464565第五章动态规划建模与求解—作业题解答最优策略是****{(),(),()}Puscucdudt目标函数最优值为*1()16Rfs方法2：表格法阶段k阶段kj决策i状态集t3()fi*3()ji3d5+05te7+07tf4+04tdef2()fi*2()ji2a7+54+48db5+56+710ec4+55+76+49fabc1()fi*1()ji1s8+88+107+916c方法3：标号法7)某公司拟将50万元投放到下属A,B,C三个企业，各企业在获得资金后的收益如表5.32所示，用动态规划方法求总收益最大的投资分配方案（投资数以10万元为单位）。投资资金（万元）01020304050收益（万元）A01520252830B0010254570C01020304050sabcdeft98747574645650810916745第五章动态规划建模与求解—作业题解答解：设kx是k阶段初期公司拥有的资源量，ku是k阶段资源的实际投放量。①当k＝3时，由333050,0xux确定了状态可能集和决策允许集合，且动态规划基本方程的边界条件为44()0fx。(1)当330,{0}xu时，333344(0)max{()()}ufgufx0，*3(0)0u(2)当3310,{0,10}xu时，33334400(10)max{()()}max10100ufgufx，*3(10)10u(3)当3320,{0,10,20}xu时，33334400(20)max{()()}max10020200ufgufx，*3(20)20u(4)当3330,{0,10,20,30}xu时，33334400100(30)max{()()}max30200300ufgufx，*3(30)30u(5)当3340,{0,10,20,30,40}xu时，33334400100(40)max{()()}max40200300400ufgufx，*3(40)40u(6)当3350,{0,10,20,30,40,50}xu时，第五章动态规划建模与求解—作业题解答33334400100200(50)max{()()}max50300400500ufgufx，*3(50)50u②当k＝2时，由222050,0xux确定了状态可能集和决策允许集合。(1)2230,{0},{0}xux222233(0)max{()()}max000ufgufx，*2(0)0u（2）22310,{0,10},{10,0}xux2232223323(0)(10)(10)max{()()}maxmax10(10)(00100)0ugffgufxgf,*2(10)0u（3）22320,{0,10,20},{20,10,0}xux223232223323(0)(20)(10)(10)(20)max{()()}maxmax20010(20)(0020)100ugfgffgufxgf，*2(20)0u（4）22330,{0,10,20,30},{30,20,10,0}xux22323222332323(0)(30)(10)(20)020(30)max{()()}maxmax30(20)(10)031010250(300)(0)ugfgffgufxgfgf，*2(30)0u（5）22340,{0,10,20,30,40},{40,30,20,10,0}xux2232323222332323(0)(40)040(10)(30)030(20)(20)(40)max{()()}maxmax451020(30)(10)2510(40)(0)450ugfgfgffgufxgfgf，*2(40)40u（6）22350,{0,10,20,30,40,50},{50,40,30,20,10,0}xux第五章动态规划建模与求解—作业题解答223232322233232323(0)(50)050(10)(40)040(20)(30)1030(50)max{()()}maxmax70(30)(20)25204510(40)(10)(50)(0700)ugfgfgffgufxgfgfgf，*2(50)50u③当k＝1时，由12250,{0,10,20,30,40,50},{50,40,30,20,10,0}xux。112121211122121212(0)(50)(10)(40)1545(20)(30)2030(50)max{()()}maxmax70(30)(20)25202810(40)(07010)300(50)(0)ugfgfgffgufxgfgfgf，*1(50)0u最优策略是：*10u，*250u，*30u最优路线是：150x，250x，30x最优目标函数值：*70R（万元）即50万元全部投资到企业B，该公司可获最大收益70万元。