数学建模优化

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,-,数学建模基地系列课件,-,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,数学建模,优化专题,专题板块系列,概率统计专题,1,优化专题,2,模糊方法及微分方程专题,3,图论方法专题,4,2,优化专题,一,线性规划模型,二,非线性规划模型,三,动态规划,3,生产计划问题,线性规划模型,4,2x,1,+,x,2,8,s.t . x,1,3,x,2,4,x,1,，,x,2,0,max,f,=,5x,1,+,2x,2,求最大利润,三种材料量的限制,生产量非负,线性规划模型,5,运输问题,线性规划模型,6,解：,设,A,1,A,2,调运到三个粮站的大米分别为,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,吨。,题设量可总到下表：,线性规划模型,7,结合存量限制和需量限制得数学模型,：,线性规划模型,8,m,个产地,A,1,A,m,联合供应,n,个销地,B,1,B,n,各产,地至各销地单位运价,(,单位,:,元,/,吨,),为,c,ij,，问如何调运使,总运费最少,?,一般运输问题,总运价,产量限制,需量限制,运量非负,线性规划模型,9,假设,产销平衡,:,在很多实际问题中,解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题,.,线性规划模型,10,设有,n,件工作,B,1, B,2, B,n,分派给,n,人,A,1, A,2, A,n,去,做,每人只做一件工作且每件工作只派一个人去做,设,A,i,完成,B,j,的工时为,c,ij,问应如何分派才能完成全部工作的,总工时最少,.,每件工作只派,1,人,每个人只派做,1,件,变量,x,i,只取,0,和,1,故建立,的模型也称,0-1,规划,.,分派问题,线性规划模型,11,选址问题,线性规划模型,12,现要做,100,套钢架,用长为,2.9m,、,2.1m,和,1.5m,的元,钢各一根,已知原料长,7.4m,问如何下料,使用的原材料,最省,?,分析,:,下料方式：,最省：,1.,所用刚架根数最少；,2.,余料最少,下料问题,线性规划模型,13,原料截成所需长度的根数,下料方法,所需根长,2.9m,2,1,1,1,0,0,0,0,2.1m,0,2,1,0,3,2,1,0,1.5m,1,0,1,3,0,2,3,4,剩余料头,0.1,0.3,0.9,0,1.1,0.2,0.8,1.4,线性规划模型,14,不同方法截得每种根长的总数至少,100,例,3,4,中的此例的变量,x,i,只取正整数,故建立的模型也称,整数规划,.,0-1,规划是整数规划的特殊情形,.,线性规划模型,15,某公司生产某产品,最大生产能力为,100,单位,每单位,存储费,2,元,预定的销售量与单位成本如下,:,月份,单位成本,(,元,),销售量,1,2,3,4,70 60,72 70,80 120,76 60,求一生产计划,使,1),满足需求,; 2),不超过生产能力,;,3),成本,(,生产成本与存储费之和,),最低,.,阶段生产问题,线性规划模型,16,解,:,假定,1,月初无库存,4,月底买完,当月生产的不库,存,库存量无限制,.,第,j+1,个月的库存量,第,j+1,个月的库存费,共,3,个月的库存费,到本月总生产量大于等于销售量,4,个月总生产量等于总销售量,4,个月总生产成本,线性规划模型,17,线性规划模型,18,月份,单位成本,(,元,),销售量,1,2,3,4,70 60,72 70,80 120,76 60,线性规划模型,19,76,82,76,76,-,-,-,80,-,-,74,72,-,74,72,70,生产月,100,100,100,100,产量,60,4,120,70,60,销量,4,3,2,1,3,2,1,需求月,费用,c,ij,线性规划模型,20,本题,3,个模型为整数规划模型,.,线性规划模型,21,线性规划模型特点,决策变量：向量,(,x,1,x,n,),T,决策人要考虑和控制的因素非负；,约束条件：线性等式或不等式；,目标函数：,Z=(,x,1,x,n,),线性式，求,Z,极大或极小；,线性规划模型,22,一般形式,目标函数,约束条件,线性规划模型,23,矩阵形式,线性规划模型,24,满足约束条件的变量的值称为,可行解,，,可行解的集合称为,可行域,。,使目标函数达到最大（小）值的可行解称为,最优解,，,相应的目标函数的值称为,最优值,。,线性规划模型,25,线性规划问题的性质,:,比例性,每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比,.,可加性,每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关,.,连续性,每个决策变量的取值都是连续的,.,线性规划模型,26,应 用,市场营销,(,广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划,),生产计划制定,(,合理下料，配料，“生产计划、库存、劳力综合”,),库存管理,(,合理物资库存量，停车场大小，设备容量,),运输问题,财政、会计,(,预算，贷款，成本分析，投资，证券管理,),人事,(,人员分配，人才评价，工资和奖金的确定,),设备管理,(,维修计划，设备更新,),城市管理,(,供水，污水管理，服务系统设计、运用,),线性规划模型,27,线性规划问题的基本理论,用图解法求解线性规划问题,是一簇斜率为,-5/2,的平行直线族,斜率为,-2,C/2,为直线与,y,轴的交点,x,1,0,x,2,8,4,4,3,28,x,2,4,0,x,1,8,3,4,如图所示,:,显然直线向右上移动时，,与,y,轴交点越高，从而,c/2,越,大，使得目标函数值,c,越大。,线性规划问题的基本理论,29,从上述几何直观可看出：,线性规划问题的任意两个可行解,联线上的点,都是可行解,；,线性规划问题的任意两个最优解,联线上的点,都是最优解；,线性规划问题的最优值若存在，则一定,在某个顶点达到,。,线性规划问题的基本理论,30,任何一个线性规划问题都可以化为标准形式，我们的求解方法都是针对标准形式的。,线性规划问题的基本理论,标准形式,:,31,如果给定的,LP,问题是极大化问题,即,可化为极小化问题,约束条件不变,其最优解是,一致,的,但目标函数值的符号,相反,.,则,:,结论,:,如果问题是求目标函数的最大值,则化为求,f,的最小值,;,1.,关于目标函数,线性规划问题的基本理论,32,2.,关于约束条件,(1),如果给定的,LP,有约束不等式,线性规划问题的基本理论,33,注意,:,新引入的变量在目标函数和约束条件中的系数均为,0.,(2),如果给定的,LP,有约束不等式,线性规划问题的基本理论,34,3.,关于变量,在标准形式中,所有的变量都有非负限制,如果某些,变量没有非负限制,则称这些变量为,自由的,.,两种处理办法,:,线性规划问题的基本理论,35,线性规划问题的基本理论,36,线性规划问题的基本理论,37,相应的典式如下,:,最优值为,5.,非基可行解,是最优解，,线性规划问题的基本理论,38,1 2 3 4 5 6 7 8 9,6 5 4 3 2 1,（,2.25,，,3.75,）,1 2 3 4 5 6 7 8 9,6 5 4 3 2 1,分枝定界法,线性规划问题的基本理论,39,隐枚举法,过滤条件,检验,可行目标值,可行检验,过滤检验,(0,0,0),0,(0,0,1),5,5,(0,1,0),- 2,(0,1,1),3,(1,0,0),3,(1,0,1),8,8,（最优）,(1,1,0),1,(1,1,1),6,线性规划问题的基本理论,40,连续投资,10,万元,A,：从第,1,年 到第,4,年每年初要投资，次年末回收本利,1.15,B,：,第3年初投资，到第5年末回收1.25,，最大投资,4,万元,C,：,第2年初投资，到第5年末回收1.40,，最大投资,3,万元,D,：,每年初投资，每年末回收1.11,。,求：,5,年末总资本最大。,练习,1,:,连续投资,41,练习,2,某服务部门一周中每天需要不同数目的雇员，,周一到周四每天至少需要,50,人，周五至少需要,80,人，,周六和周日至少需要,90,人，现规定应聘者需连续工,作,5,天，试确定聘用方案。,42,练习,3,某班准备从,5,名游泳员中选择人组成接力队，,藏家学校的,4100m,混合泳接力比赛，,5,名队员,4,种泳,姿的百米平均成绩如表，问如何选拔队员。,队员,甲,乙,丙,丁,戊,蝶泳,1068,572,118,110,1074,仰泳,1156,106,1142,1142,111,蛙泳,127,1064,1096,1096,1238,自由泳,586,53,594,572,1024,43,线性模型题目,1,生产计划问题,某工厂计划安排生产,，,两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及,A,B,两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：,）怎么安排生产使得工厂获利最大？,）产品,的单位利润降低到,1.8,万元，要不要改变生产计划，如果降低到,1,万元呢？,）产品,的单位利润增大到,5,万元，要不要改变生产计划？,）如果产品,，,的单位利润同时降低了,1,万元，要不要改变生产计划？,产品,产品,最大资源量,设备,1,2,8,台时,原材料,A,4,0,16kg,原材料,B,0,4,12kg,单位产品利润,2,3,44,线性模型建立,45,线性模型求解,程序编写,model,:,title,生产计划问题,;,maxf,max,=2*x1+3*x2;,Ax1+2*x28;,B4*x116;,TIME4*x212;,END,46,线性模型求解,运行结果,Model Title:,生产计划问题,Variable Value Reduced Cost,X1 4.000000 0.000000,X2 2.000000 0.000000,Row Slack or Surplus Dual Price,MAXF 14.00000 1.000000,A 0.000000 1.500000,B 0.000000 0.1250000,TIME 4.000000 0.000000,对问题,1,，安排是生产产品,4,单位，产品,2,单位，最大盈,利为,14,万元,。,47,线性模型敏感性理论,1,目标函数的系数变化的敏感性分析,如果目标函数的系数发生变化，将会影响目标函数,f,斜率的变化，但是只要,f,的斜率小于等于,-1/2,（也就是直线,l,夹在,l,1,与,l,2,之间时），最优解都在,(4,2),上取到，最优解不变，从而生产计划不会变,.,48,线性模型,敏感性分析,1,要使用敏感性分析,必须要在这里选择,Prices & Ranges,然后,保存,退出,路径：,LINGOOptionsGeneral Solver,(,通用求解程序,),选项卡,49,线性模型,敏感性分析,1,要调出敏感性分析的结果，必须,先求解,后再,在程序窗口下,点击,LINGO,Range,，,50,线性模型,敏感性分析,1,Ranges in which the basis is unchanged:,Objective Coefficient Ranges,Current Allowable Allowable,Variable Coefficient Increase Decrease,X1 2.000000 INFINITY 0.5000000,X2 3.000000 1.000000 3.000000,Righthand Side Ranges,Row Current Allowable Allowable,RHS Increase Decrease,A 8.000000 2.000000 4.000000,B 16.00000 16.00000 8.000000,TIME 12.00000 INFINITY 4.000000,当前变量系数,允许增加量,允许减少量,对问题,2,，产品,的单位利润降低到,1.8,万元，在（,1.5,，）之间，所以不改变生产计划。如果降低到,1,万元，不在（,1.5,，）内，要改变生产计划。在程序中将目标函数的系数“,2”,改为“,1”,，可得新的计划为,安排是生产产品,2,单位，产品,3,单位，最大盈利为,11,万元,.,对问题,3,，要改变生产计划，更改程序得新计划为生产产品,2,单位，产品,3,单位，最大盈利为,19,万元,.,对问题,4,，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到,8,万元,.,51,线性模型敏感性理论,2,52,线性模型影子价格理论,把,y,1,y,2,y,3,作为三种原料的定价，,定价的目标是在比生产产品获得更多利润的前提下的最小利润,.,在最优情况下，,y,的值就是资源的,影子价格，,影子价格有意义是有范围的,。,影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量,53,线性模型综合讨论,Ranges in which the basis is unchanged:,Objective Coefficient Ranges,Current Allowable Allowable,Variable Coefficient Increase Decrease,X1 2.000000 INFINITY 0.5000000,X2 3.000000 1.000000 3.000000,Righthand Side Ranges,Row Current Allowable Allowable,RHS Increase Decrease,A 8.000000 2.000000 4.000000,B 16.00000 16.00000 8.000000,TIME 12.00000 INFINITY 4.000000,运行结果,Model Title:,生产计划问题,Variable Value Reduced Cost,X1 4.000000 0.000000,X2 2.000000 0.000000,Row Slack or Surplus,Dual Price,MAXF 14.00000,1.000000,A 0.000000,1.500000,B 0.000000,0.1250000,TIME 4.000000,0.000000,54,线性模型题目,2,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,加工奶制品的生产计划,55,线性模型建立,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,获利,243,x,1,获利,164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),56,线性模型求解,Max=72*x1+64*x2;,x1+x250,;,12*x1+8*x2480;,3*x1100;,OBJECTIVE FUNCTION VALUE,1) 3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2) 0.000000 48.000000,3) 0.000000 2.000000,4) 40.000000 0.000000,NO. ITERATIONS= 2,20,桶牛奶生产,A,1, 30,桶生产,A,2,，利润,3360,元。,57,线性模型影子价格,OBJECTIVE FUNCTION VALUE,1) 3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW SLACK OR SURPLUS,DUAL PRICES,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,35,元可买到,1,桶牛奶，要买吗？,35 0,，初始可行点,x,k,初始步长,k,0,在,x,k,线性化得线性规划问题：,非线性规划有约束问题,71,求出此线性规划问题得最优解,x,k,1,，检验,是否为原问题的的可行解，若是转，否则缩短,步长转；,判断精度。,则取,最优解,x,*=,x,k,+1,停，否则令,k,=,k,+1,转。,非线性规划有约束问题,72,（,2,）罚函数法,转化为无约束最优化问题：,M,为足够大的正数。称为,罚因子,。,算法分析：,设可行域为,S,，构造函数：,非线性规划有约束问题,73,求无约束问题得最优解为,X,(,M,),直观看出，,只有当,X,(,M,) S,才可能真正取得极小值，若,就,加大,罚因子,M,，使,X,(,M,),向,S,逼近，,当,M,时，点列,非线性规划有约束问题,74,计算步骤,：（第,k,次迭代）,非线性规划有约束问题,75,露天矿里铲位已分成矿石和岩石,:,平均铁含量不低于,25%,的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间,5,分钟。,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时,不应发生卡车等待,的情况。,矿石卸点需要的铁含量要求都为,29.5%,1%(,品位限制），搭配量在一个班次（,8,小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为,154,吨，平均时速,28km,平均卸车时间为,3,分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次,?,露天矿生产的车辆安排,(CUMCM-2003B),76,露天矿生产的车辆安排,(CUMCM-2003B),77,距离,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石漏,5.26,5.19,4.21,4.00,2.95,2.74,2.46,1.90,0.64,1.27,倒装,1.90,0.99,1.90,1.13,1.27,2.25,1.48,2.04,3.09,3.51,岩场,5.89,5.61,5.61,4.56,3.51,3.65,2.46,2.46,1.06,0.57,岩石漏,0.64,1.76,1.27,1.83,2.74,2.60,4.21,3.72,5.05,6.10,倒装,4.42,3.86,3.72,3.16,2.25,2.81,0.78,1.62,1.27,0.50,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石量,0,95,1,05,1,00,1,05,1,10,1,25,1,05,1,30,1,35,1,25,岩石量,1,25,1,10,1,35,1,05,1,15,1,35,1,05,1,15,1,35,1,25,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,露天矿生产的车辆安排,(CUMCM-2003B),78,与典型的运输问题明显有以下不同：,这是运输矿石与岩石两种物资的问题；,属于产量大于销量的不平衡运输问题；,为了完成品位约束，矿石要搭配运输；,产地、销地均有单位时间的流量限制；,运输车辆只有一种，每次满载运输，,154,吨,/,车次；,铲位数多于铲车数意味着要最优的选择不多于,7,个产地作为最后结果中的产地；,最后求出各条路线上的派出车辆数及安排。,近似处理：,先求出产位、卸点每条线路上的运输量,(MIP,模型,),然后求出各条路线上的派出车辆数及安排,问题分析,79,卡车在一个班次中不应发生等待或熄火后再启动的情况；,在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；,空载与重载的速度都是,28km/h,，耗油相差很大；,卡车可提前退出系统，等等。,模型假设,80,(,近似,),xij,：从,i,铲位到,j,号卸点的石料运量 （车）,单位： 吨；,cij,：从,i,号铲位到,j,号卸点的距离,公里；,Tij,:,从,i,号铲位到号,j,卸点路线上运行一个周期平均时间,分；,Aij,：从号铲位到号卸点最多能同时运行的卡车数,辆；,Bij,：从号铲位到号卸点路线上一辆车最多可运行的次数,次；,pi,：,i,号铲位的矿石铁含量,p=(30,28,29,32,31,33,32,31,33,31),%,qj,: j,号卸点任务需求，,q=(1.2,1.3,1.3,1.9,1.3)*10000,吨,cki,：,i,号铲位的铁矿石储量 万吨,cyi,：,i,号铲位的岩石储量 万吨,fi,:,描述第,i,号铲位是否使用的,0-1,变量，取,1,为使用；,0,为关闭,符号说明,81,（,4,）铲位储量约束,（,1,）道路能力,(,卡车数,),约束,（,2,）电铲能力约束,（,3,）卸点能力约束,模型建立,优化模型,82,x,ij,为非负整数,f,i,为,0-1,整数,（,5,）产量任务约束,（,8,）整数约束,（,7,）电铲数量约束,（,6,）铁含量约束,模型建立,83,程序编写,model,:,title,CUMCM-2003B-01;,sets,:,cai / 1.10 /:crate,cnum,cy,ck,flag;,xie / 1 . 5 /:xsubject,xnum;,link( xie,cai ):distance,lsubject,number,che,b;,endsets,data,:,crate=30 28 29 32 31 33 32 31 33 31;,xsubject= 1.2 1.3 1.3 1.9 1.3 ;,distance= 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27,1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51,5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57,0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10,4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50;,cy = 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;,ck = 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25;,enddata,84,程序编写,!,目标函数,;,min,=,sum,( cai (i):,sum,( xie (j):,number (j,i)*154*distance (j,i);,!,卡车每一条路线上最多可以运行的次数,;,for,(link (i,j):,b(i,j)=,floor,(8*60-(,floor,(distance(i,j)/28*60*2+3+5)/5)-1)*5)/(distance(i,j)/28*60*2+3+5);,!,每一条路线上的最大总车次的计算,;,for,( link (i,j):,lsubject(i,j)=(,floor,(distance(i,j)/28*60*2+3+5)/5)*b(i,j);,!,计算各个铲位的总产量,;,for,(cai(j):,cnum(j)=,sum,(xie(i):number(i,j);,!,计算各个卸点的总产量,;,for,(xie(i):,xnum(i)=,sum,(cai(j):number(i,j);,85,程序编写,!,道路能力约束,;,for,(link (i,j):,number(i,j)=lsubject(i,j);,!,电铲能力约束,;,for,(cai (j) :,cnum(j) = flag(j)*8*60/5 );,!,电铲数量约束,- added by Xie Jinxing, 2003-09-07,;,sum,(cai(j): flag(j) ) =7;,!,卸点能力约束,;,for,(,xie,(i):,xnum (i)=8*20);,!,铲位产量约束,;,for,(cai (i): number(1,i)+number(2,i)+number(5,i)=ck(i)*10000/154);,for,(cai (i): number(3,i)+number(4,i)= xsubject (i)*10000/154);,86,程序编写,!,铁含量约束,;,sum,(cai (j):,number(1,j)*(crate(j)-30.5) )=0;,sum,(cai (j):,number(2,j)*(crate(j)-30.5) )=0;,sum,(cai (j):,number(5,j)*(crate(j)-30.5) )=0;,sum,(cai (j):,number(2,j)*(crate(j)-28.5) )=0;,sum,(cai (j):,number(5,j)*(crate(j)-28.5) )=0;,!,关于车辆的具体分配,;,for,(link (i,j):,che (i,j)=number (i,j)/b(i,j);,87,程序编写,!,各个路线所需卡车数简单加和,;,hehe=,sum,(link (i,j): che (i,j);,!,整数约束,;,for,(link (i,j):,gin,(number (i,j);,for,(cai (j):,bin,(flag (j);,!,车辆能力约束,;,hehe=20;,ccnum=,sum,(cai (j): cnum(j) );,end,88,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿漏,13,54,11,倒,42,43,岩场,70,15,岩漏,81,43,倒,13,2,70,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石漏,0.867,1.862,0.314,倒场,1.077,1.162,岩场,1.892,0.326,岩石漏,1.841,1.229,倒场,0.684,0.1,1.489,求解结果,89,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石漏,1 (29),倒场,1 (39),1 (37),岩场,1 (37),岩石漏,1(44),1 (35),倒场,1 (47),结论：,铲位,1,、,2,、,3,、,4,、,8,、,9,、,10,处各放置一台电铲。,一共使用了,13,辆卡车；总运量为,85628.62,吨公里；,岩石产量为,32186,吨；矿石产量为,38192,吨。,求解结果,90,例：最短线路问题：,动态规划,阶段,k,k,1,状态,决策,报酬函数,状态转移规律,子策略,目标函数,最优目标函数,E,0,5,4,3,11,8,6,7,11,13,16,最优原理：一个策略的子策略总是最优的。,91,1 2 3,92,s,k,表示为分配给,第,k,个公司至第,3,个公司,的设,备台数,.,x,k,表示分配给,第,k,个公司,的设备台数,.,状态转移方程为：,s,k,+1,=,s,k,-,x,k,.,g,k,(,x,k,),表示,x,k,台设备分配到第,k,个公司所得,的盈利值,.,f,k,(,s,k,),表示为,s,k,台设备分配给第,k,个公司至,第,3,个公司时所得到的最大盈利值,.,f,k,(,s,k,) = max ,g,k,(,x,k,) +,f,k,+1,(,s,k,-,x,k,),|,0,x,k,s,k,k,=,2 , 1.,f,3,(,s,3,) =,g,3,(,x,3,).,分析：,93,Thank You !,