第4节一般数学模型的动态规划解法

1、 安徽科技学院安徽科技学院 最优化技术最优化技术例例1 某公司有资金某公司有资金10万元，若投资于项目万元，若投资于项目i(i=1,2,3)的投的投资额为资额为xi时，其收益分别为时，其收益分别为g1(x1)=4x1,g2(x2)= 9x2 , g3(x3)=2x32,问应如何分配投资数额才能使总收益最大？问应如何分配投资数额才能使总收益最大？一、非线性规划问题的动态规划解法一、非线性规划问题的动态规划解法 解解 静态规划模型：静态规划模型：2123123max49210. .0 (1,2,3)izxxxxxxstxi第四节第四节 一般数学模型的动态规划解法一般数学模型的动态规划解法1.连续变

2、量的一般解法连续变量的一般解法 安徽科技学院安徽科技学院 最优化技术最优化技术为了应用动态规划方法求解，人为地赋予它为了应用动态规划方法求解，人为地赋予它“时段时段”的概念，将投资项目排序，首先考虑对项目的概念，将投资项目排序，首先考虑对项目1投资，投资，然后考虑对项目然后考虑对项目2投资投资，即把问题划分为，即把问题划分为3个阶个阶段，每个阶段只决定对一个项目应投资的金额。段，每个阶段只决定对一个项目应投资的金额。通常把决策变量通常把决策变量uk定为原静态规划的变量定为原静态规划的变量xk即设即设 (1,2,3)kkuxk状态变量和决策变量有密切关系，状态变量一般状态变量和决策变量有密切关系

3、，状态变量一般为累计量或随递推过程变化的量。为累计量或随递推过程变化的量。可把每阶段可供使用的资金定为状态变量可把每阶段可供使用的资金定为状态变量sk，初始，初始状态为状态为s1=10 安徽科技学院安徽科技学院 最优化技术最优化技术u1为可分配用于第一种项目的最大资金，则第一阶为可分配用于第一种项目的最大资金，则第一阶段时有：段时有：11110sux第二阶段第二阶段(k=2)时，状态变量时，状态变量s2为余下可投资于其为余下可投资于其余两个项目的资金，即：余两个项目的资金，即：21122ssuux一般地，当第一般地，当第k段时段时11kkkkkssuux 安徽科技学院安徽科技学院 最优化技术最

4、优化技术于是有于是有状态变量状态变量sk：第第k阶段可以投资于第阶段可以投资于第k项到第项到第3个项目个项目的资金的资金决策变量决策变量xk：决定给第决定给第k项目的资金项目的资金状态转移方程：状态转移方程：sk+1=sk-uk指标函数：指标函数：最优指标函数最优指标函数fk(sk)：当可投资金为当可投资金为sk时，投资第时，投资第k-3项所得最大收益。基本方程为：项所得最大收益。基本方程为：3,3( )kiii kVg x11044()max()() 3,2,1()0kkkkkkkkxsfsgxfskfs 安徽科技学院安徽科技学院 最优化技术最优化技术0ss2x2232s当当k=2时，时，这

5、是一个函数求极值问这是一个函数求极值问题题, ,利用微分方法可求得利用微分方法可求得该函数有极小值该函数有极小值. .是极小值点。而4922 sx222222222330223022220()max 9( )max 92max 92()xsxsxsfsxf sxsxsx当当k=3时，时，显然当显然当，函数取极大值为，函数取极大值为3323330max 2,xsfsx（ ）*33xs 安徽科技学院安徽科技学院 最优化技术最优化技术要讨论要讨论s2的具体情况的具体情况:当当 时，时，当当 时，时，此时此时此时此时*20 x 292s 22222022()()xxsfsfs*22xs292s 222

6、22022()()xxsfsfs到此，第二阶段的决策已经作出到此，第二阶段的决策已经作出 安徽科技学院安徽科技学院 最优化技术最优化技术22222()9xsfss11111220( )max 4()xsf sxfs11*11120101110101110100max 49max 499max 959xxxxxsxsxsxs减函数减函数*22,xs*121109100,2xssx此结论与前矛盾，故舍去此结论与前矛盾，故舍去当当k=1时，时，时时注：此时注：此时由前面分析可知由前面分析可知而而*2229,2sxs 安徽科技学院安徽科技学院 最优化技术最优化技术*211*2231001090102s

7、sxsxx另取另取*2222202xfss，（ ）此时此时112111110max 42xsf sxsx（ ）（）又是一个求极值问题，微分求解又是一个求极值问题，微分求解111xs比较比较0,10的端点的端点当当 时，时，当当 时，时，*1110400fx（ ）110200f（ ）10 x 110 x 再由递推方程递推：再由递推方程递推：最优方案为全部资金投到第三个项目最优方案为全部资金投到第三个项目 安徽科技学院安徽科技学院 最优化技术最优化技术2.连续变量的离散化解法连续变量的离散化解法:例如投资分配问题例如投资分配问题的一般静态模型为：的一般静态模型为：11max( ). .0 (1,2

8、,., )niiiniiizg xxastxin建立它的动态规划模型，其基本方程为：建立它的动态规划模型，其基本方程为：11011()max()() ,1,.,2,1()0kkkkkkkkxsnnfsgxfskn nfs其状态转移方程为：其状态转移方程为：sk+1=sk-xk 安徽科技学院安徽科技学院 最优化技术最优化技术 由于由于sk与与xk都是连续变量，当各阶段指标都是连续变量，当各阶段指标gk(xk)，没有特没有特殊性质而较为复杂时，要求出殊性质而较为复杂时，要求出fk(sk)比较困难，因而求全过比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量程的最优策略也就相当不

9、容易，这时常常采用把连续变量离散化的方法求其数值解，具体做法如下：离散化的方法求其数值解，具体做法如下：（1）令）令sk=0, ,2,m=a，把区间把区间0,a进行分割，进行分割， 的的大小可依据问题所要求的精度及计算机的容量来定。大小可依据问题所要求的精度及计算机的容量来定。（2）规定状态变量）规定状态变量sk及决策变量及决策变量xk只在离散的点只在离散的点0,2, , m上取值，相应的指标函数上取值，相应的指标函数fk(sk)就被定义在这些离散值上，就被定义在这些离散值上，于是递推方程变为：于是递推方程变为：10,1,2,.,11()max()() ()0kkkkkpqnnfsgpfspf

10、s ,kkqspx 其中其中 安徽科技学院安徽科技学院 最优化技术最优化技术（3）按逆序方法，逐步递推求出）按逆序方法，逐步递推求出fn(sn), f1(s1)，最后求出，最后求出最优资金分配方案。最优资金分配方案。例例2 用连续变量的离散化求解用连续变量的离散化求解2123123max49210. .0 (1,2,3)izxxxxxxstxi解解 令令 ，将区间，将区间0,10分割成分割成0,2,6,8,10六个点，即状六个点，即状态变量态变量sk集合为集合为0,2,4,6,8,102 允许决策集合为允许决策集合为 均在分割点上取值。均在分割点上取值。0,kkkkxsx s 安徽科技学院安徽

11、科技学院 最优化技术最优化技术动态规划基本方程为：动态规划基本方程为：1044()max()() 3,2,1()0kkkkkkkkkxsfsgxfsxkfs当当k=3时，时，3323330( )max 2xsf sx其中其中s3和和x3的集合均为的集合均为0,2,4,6,8,10,计算结果如下表计算结果如下表s30246810f3(s3)083272128200 x3*0246810 安徽科技学院安徽科技学院 最优化技术最优化技术222223220()max 9()xsfsxf sx计算结果如下表计算结果如下表s20246810 x200 20 2 40 2 4 60 2 4 6 80 2 4

12、 6 8 10g2+f30 8 18 32 26 36 72 50 44 54 128 90 68 62 72 200 146 108 86 80 90f20183672128200 x2*024000当当k=2时，时，1111211010( )max 4()xf sxfsx计算结果如下表计算结果如下表s110 x10246810g1 +f220013688605040f1200 x1*0当当k=1时，时， 安徽科技学院安徽科技学院 最优化技术最优化技术计算结果表明，最优决策为：计算结果表明，最优决策为：*1230,0,10 xxx最大收益为：最大收益为：1(10)200f与例与例5结论完全相

13、同。结论完全相同。注意：这种方法有可能丢失最优解，一般得到原问注意：这种方法有可能丢失最优解，一般得到原问题的近似解题的近似解 安徽科技学院安徽科技学院 最优化技术最优化技术练练 习习用连续变量的离散化方法求解下面的非线性规划用连续变量的离散化方法求解下面的非线性规划2123123max4. .0 (1,2,3)izx xxxxxstxi令令sk=0,1,2,3,4，列表求解列表求解逆序解法逆序解法:,(,)nk njjjj kVv s u基本方程基本方程:1111()(,)() ,1,2,1()1kkkkkkkkuDnnfsopt v s ufskn nfs注意到注意到目标函目标函数是乘数是

14、乘积的形积的形式：式： 安徽科技学院安徽科技学院 最优化技术最优化技术 背包问题的一般提法是：一位旅行者携带背包去登山、已背包问题的一般提法是：一位旅行者携带背包去登山、已知他所能承受的背包重量限度为知他所能承受的背包重量限度为a千克，现有千克，现有n种物品可供他选种物品可供他选择装入背包。第择装入背包。第i种物品的单件重量为种物品的单件重量为ai干克、其价值干克、其价值(可以是表可以是表明本物品对登山的重要性的数量指标明本物品对登山的重要性的数量指标)是携带数量是携带数量xi的函数的函数ci(xi) (i1,2,n),问旅行者应如何选择携带各种物品的件数，以使总问旅行者应如何选择携带各种物品

15、的件数，以使总价值最大？价值最大？ 其他如车、船、飞机、潜艇、人造卫星等工具的最优装载其他如车、船、飞机、潜艇、人造卫星等工具的最优装载问题，机床加工中零件最优加工、下料问题、投资决策问题，问题，机床加工中零件最优加工、下料问题、投资决策问题，均等同于背包问题。均等同于背包问题。三、背包问题的动态规划解法三、背包问题的动态规划解法 安徽科技学院安徽科技学院 最优化技术最优化技术背包问题的动态规划模型背包问题的动态规划模型1、阶段、阶段k：将可装入物品按：将可装入物品按1,2,.,n排序，共划分为排序，共划分为n个阶段，即个阶段，即 k1,2,.,n。2、状态变量、状态变量sk+1：在第：在第k

16、段开始时，背包中允许装入前段开始时，背包中允许装入前k种物品的种物品的 总重量。总重量。3、决策变量、决策变量xk：装入第：装入第k种物品的件数。种物品的件数。4、状态转移方程：、状态转移方程：sk=sk+1-akxk5、允许决策集合为：、允许决策集合为： Dk(sk+1)xk|0 xk sk+1/ak，xk为整数整数6、最优指标函数、最优指标函数 fk(sk+1)表示在背包中允许装入物品的总重量不表示在背包中允许装入物品的总重量不 超过超过sk+1千克，采用最优策略只装前千克，采用最优策略只装前k种物品时的最大使用价值种物品时的最大使用价值7、顺序递、顺序递 推方程：推方程：1110,1,.

17、,/01()max()(), 1,2,.,( )0kkkkkkkkkkkrsafscxfsa xknf s 安徽科技学院安徽科技学院 最优化技术最优化技术例例3:3: 有一辆最大货运量为有一辆最大货运量为1010吨的卡车，用以装载吨的卡车，用以装载3 3种货种货物每种货物的单位重量及相应单位价值如表所示。应如何物每种货物的单位重量及相应单位价值如表所示。应如何装载可使总价值最大装载可使总价值最大? ?货物编号货物编号i123单位重量（单位重量（t）345单位价值单位价值ci456设第设第i种货物装载的件数为种货物装载的件数为xi (i1,2,3)，则问题可表为，则问题可表为123123max4

18、5634510. .0(1,2,3)izxxxxxxstxi且为整数 安徽科技学院安徽科技学院 最优化技术最优化技术建立动态规划模型，由于决策变量取离散值，故可建立动态规划模型，由于决策变量取离散值，故可利用列表法求解利用列表法求解基本方程：基本方程：1110,1,.,/01()max()() 1,2,.,( )0kkkkkkkkkkkxsafscxfsa xknf s当当k=1时，时， 或或121210 3()max4xsf sx1212120 3()max44/3xsf sxss2012345678910f1(s2)0004448881212x1*00011122233 安徽科技学院安徽科

19、技学院 最优化技术最优化技术当当k=2时，时，2322321320 4( )max5(4)xsxzfsxf sxs30 1 2 345678910 x20 0 0 0 0 1 0 1 0 1 0 10 1 20 1 20 1 2c2 +f10 0 0 4 4 5 4 5 8 5 8 9 8 9 10 12 9 10 12 13 10f2(s3)0 0 05589101213x2*0 0 0 01101201当当k=3时，时，333230,1,2(10)max 6(105)xfxfx222max(10) 6(5),12(0)fff，max 13 65,12013，此时此时x3*=0，逆推可得全部

20、策略为，逆推可得全部策略为x1*=2,x2*=1,x3*=0最大价值为最大价值为13 安徽科技学院安徽科技学院 最优化技术最优化技术三、生产经营问题的动态规划解法三、生产经营问题的动态规划解法 在生产和经营管理中经常遇到如何合理地安排生产在生产和经营管理中经常遇到如何合理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。益最高的问题。例例4 4：某工厂生产并销售某种产品，已知今后四个月市场需某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产单位产品费用为：求预测如表，又每月生产单位产品费用为：0(0)(

21、 ) 3(1,2,.,6)jC jjj每月库存每月库存j单位产品的费用为单位产品的费用为E(j)0.5j (干元干元)，该厂最大，该厂最大库存容量为库存容量为3单位，每月最大生产能力为单位，每月最大生产能力为6单位，计划开始单位，计划开始和计划期末库存量都是零。和计划期末库存量都是零。 安徽科技学院安徽科技学院 最优化技术最优化技术试制定四个月的生产计划，在满足用户需求条件下总费用最小。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第假设第j+1个月的库存量是第个月的库存量是第j个月可销售量与该月用户需求量个月可销售量与该月用户需求量之差；而第之差；而第i个月的可销售量是本月初库

22、存量与产量之和。个月的可销售量是本月初库存量与产量之和。 i（月）1234gi（需求） 2324解：建立动态规划模型解：建立动态规划模型(1)阶段：阶段：每个月为一个阶段，每个月为一个阶段，k1,2,3,4。(2)状态变量状态变量:sk为第为第k个月初的库存量。个月初的库存量。(3)决策变量决策变量:uk为第为第k个月的生产量。个月的生产量。(4)状态转移方程：状态转移方程：sk+1=sk+uk-gk 安徽科技学院安徽科技学院 最优化技术最优化技术(5)最优指标函数最优指标函数：fk(sk)表示第表示第k月状态为月状态为sk时，采用最佳时，采用最佳策略生产，从本月到计划结束（第策略生产，从本月

23、到计划结束（第4个月末）的生产与存个月末）的生产与存贮最低费用。贮最低费用。(6)基本方程基本方程：155()min ()()() k1,2,3,4( )0kkkkkkkkfsc uE sfsugf s当当k=4时，时，44444444,0,1,2,3.()min()()us sfsC uE ss40123f4(s4)76.565.5u4(s4)4321 安徽科技学院安徽科技学院 最优化技术最优化技术当当k=3时，时，30,1,2,3.s 3333max0,2min(6,5,6)suss33334333( )min ()( )() f sc uE sfsugs30123u3(s3)234512340123012C+