资源预览内容
第1页 / 共42页
第2页 / 共42页
第3页 / 共42页
第4页 / 共42页
第5页 / 共42页
第6页 / 共42页
第7页 / 共42页
第8页 / 共42页
第9页 / 共42页
第10页 / 共42页
第11页 / 共42页
第12页 / 共42页
第13页 / 共42页
第14页 / 共42页
第15页 / 共42页
第16页 / 共42页
第17页 / 共42页
第18页 / 共42页
第19页 / 共42页
第20页 / 共42页
亲,该文档总共42页,到这儿已超出免费预览范围,如果喜欢就下载吧!
点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 动态规划问题及求解,81 多阶段决策问题,动态规划是解决这样一类最优化问题的专门计算方法,这类问题允许把它的过程(求解)分解为一系列的单级过程(步骤)。,最优化原理:达到系统某种状态的过程无论是怎样的,以这个状态为初始状态的剩余过程的求解仍是最优的规划。也就是说,当系统处于第,个状态时,只要最优,规划剩余的,个过程,便可逐步求出,最优解。,为了方便讨论动态规划的求解过程,我们把动态规划,问题化分为下面几个过程:,1,阶段(,stage):,把问题恰当的分为若干个相互联系,的阶段;,2状态(State):,它是表示某段的出发位置,是某支路,的起点,又是前一段某支路的终点。第,个阶段的状态,变量,应该包含前各阶段决策过程的全部信息,且之后,作出的决策与之前的状态和决策无关。,3决策(Decision):,是指某阶段初从给定的状态出发,决策者所作出的选择,决策变量,表示第,个阶段,状态为,时对方案的选择。决策允许范围记为,,,4策略(Policy):,即决策序列。,个阶段动态规划问题,的策略可记为,2,,当,时,,表示从,阶段开始到最后的决策,序列。,5状态转移方程:,表明后一阶段和前一阶段之间的,阶段状态和决策给定之后,第,关系。当第,阶段状态就确定了,记为,6.指标函数:,阶段指标函数-对应于某一阶段状态和从该,状态出发的决策的某种指标度量。第,阶段指标函数记,为,;过程指标函数-从某阶段开始到最后,过程的指标度量。记为,,最优策略值记为,3,7动态规划基本方程:,过程指标函数是各阶段指标函数,的函数。,82 动态规划问题的解法,例1设某仓库有12人巡逻守卫,负责4个要害部位,对每个部位可分别派2到4人巡逻,由于巡逻人数不同,各部位预期在一段时间内可能造成的损失也不一样,具体数字见下表。问该卫队应往各部位分别派多少人巡逻才能使预期损失最小?,4,把12人派往4个部位看作4个阶段(k=1,2,3,4),每个阶段初可派遣的人数是前面阶段决策的结果,也是本阶段决策的依据。用 表示第,个阶段的状态变量,用,表示第,个阶段的决策变量(即在该阶段派出的,人数,显然,),各阶段可允许的决策集合,状态转移方程为,用,表示第,个阶段派出的巡逻人数为,时,在该部位的预期损失值,5,过程指标函数,由于,用,表示从第,个阶段到结束时预期损失值,,(1)先考虑D部位,(2)先考虑C,D部位,由于,,所以,6,(3)先考虑B,C,D部位,由于,,所以,(4)先考虑A,B,C,D部位,由于,,所以,由此可见,A,B,C,D四个部位应分别派4人,2人,,2人,4人,预期损失值为97。,例5求从A点到G点的最段路线,7,解:从A到G分六个阶段:A-B,B-C,C-D,D-,E,E-F,F-G,(1)第六阶段F-G最短路,例2,8,(2)第五阶段E-G最短路,(3)第四阶段D-G最短路,(4)第三阶段C-G最短路,9,(5)第二阶段B-G最短路,(6)第一阶段A-G最短路,所以最短路是:A-B1-C2-D1-E2-F2-G,最短路长为18。,例3求下列非线性规划问题,10,解:要求,的值,我们分三个阶段,,分别为第1,2,3阶段的决策变量。,设状态变量为,,显然,阶段指标函数,第三阶段,2第二阶段,11,3第一阶段,所以,最优值为,12,例4 设备平行分配,某公司根据国家计划的安排拟将某种设备5台分给甲乙丙三个厂,各厂获得这种设备每年可向国家提供的利润如下表:,工厂,设备台数,0 1 2 3 4 5,甲,0,3,7,9,12,13,乙,0,5,10,11,11,11,丙,0,4,6,11,12,12,13,解:分3个阶段,甲第3厂,乙-第2厂,丙-第1厂,设 为第 k 厂获得的台数,为 台设备分配给第 k 个厂所得利润.,表示当前 k状态下的已分的设备总数,表示当前状态下 台设备所得的最大利润,第一阶段,考虑丙厂(k=1),14,第2阶段,考虑乙,丙厂(k=2),15,16,第3阶段,考虑甲,乙,丙厂(k=3),有两种分配方案:总最大利润21,方案1:甲0,乙2,丙3,方案2:甲2,乙2,丙1,17,第九章 LINGO8.0编程介绍,LINGO程序的背景及应用,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立 LINDO系统公司(LINDO Systems Inc.),网址:,LINDO:Linear INteractive and Discrete Optimizer (V6.1),LINGO:Linear INteractive General Optimizer (V8.0),LINDO API:LINDO Application Programming Interface(V2.0),Whats Best!:(SpreadSheet e.g.EXCEL)(V7.0),目前的产品有:演示(试用)版、学生版、高级版、超级版、工业版、扩展版(求解问题规模和选件不同),18,LINDO,和,LINGO,软件能求解的优化模型,LINGO,LINDO,优化模型,线性规划,(LP),非线性规划,(NLP),二次规划,(QP),连续优化,整数规划(IP),19,LINGO模型的优点,包含了LINDO的全部功能,提供了灵活的编程语言(矩阵生成器),LINGO模型的构成:4个段,目标与约束段(MODEL:END),集合段(SETS:ENDSETS),数据段(DATA:ENDDATA),初始段(INIT:ENDINIT),例1:编一个LINGO程序求解下列线性规划问题的最优解,20,程序,model:,max=1.15*x41+1.4*x23+1.25*x32+1.06*x54;,x11+x14=10000;,-1.06*x14+x21+x23+x24=0;,-1.15*x11-1.06*x24+x31+x32+x34=0;,-1.15*x21-1.06*x34+x41+x44=0;,-1.15*x31-1.06*x44+x54=0;,x23=30000;,x32=40000;,End,运行结果:,Global optimal solution found at iteration:2,Objective value:14840.00,21,Variable Value Reduced Cost,X41 0.000000 0.6739130E-01,X23 10600.00 0.000000,X32 0.000000 0.4043478E-01,X54 0.000000 0.000000,X11 0.000000 0.000000,X14 10000.00 0.000000,X21 0.000000 0.000000,X24 0.000000 0.3213913E-01,X31 0.000000 0.7143478E-01,X34 0.000000 0.000000,X44 0.000000 0.9379130E-01,Row Slack or Surplus Dual Price,1 14840.00 1.000000,2 0.000000 1.484000,22,3 0.000000 1.400000,4 0.000000 1.290435,5 0.000000 1.217391,6 0.000000 1.060000,7 19400.00 0.000000,8 40000.00 0.000000,例2:编一个LINGO程序求解下列线性规划问题的最优解,23,程序一,model:,max=120*x1+108*x2+150*x3+190*x4+160*x5+200*x6+98*x7;,100*x1+98*x2+130*x3+160*x4+130*x5+170*x6+88*x7=1600;,x1+x2+x3=1;,x6+x7=1;,bin(x1);bin(x2);bin(x3);bin(x4);,bin(x5);bin(x6);bin(x7);,End,24,程序二,model:,sets:,AA/1.7/:x,b,c;,endsets,data:,b=120,108,150,190,160,200,98;,c=100,98,130,160,130,170,88;,enddata,max=sum(AA(j):b(j)*x(j);,sum(AA(j):c(j)*x(j)=1600;,x(1)+x(2)+x(3)=1;,x(6)+x(7)=1;bin(x(1);,bin(x(2);bin(x(3);bin(x(4);bin(x(5);,bin(x(6);bin(x(7);End,25,运行结果:,Global optimal solution found at teration:0,Objective value:918.0000,Variable Value Reduced Cost,X1 1.000000 -120.0000,X2 0.000000 -108.0000,X3 1.000000 -150.0000,X4 1.000000 -190.0000,X5 1.000000 -160.0000,X6 1.000000 -200.0000,X7 1.000000 -98.00000,26,Row Slack or Surplus Dual Price,1 918.0000 1.000000,2 822.0000 0.000000,3 0.000000 0.000000,4 1.000000 0.000000,5 1.000000 0.000000,例3:编一个LINGO程序求解下列线性规划问题的最优解,目标函数,约束条件,27,程序,model:,SETS:,T/A1,A2/:tt;,Endsets,init:,x11=10;x21=13;,endinit,min=max(T(j):tt(j);,x11+x21=50;,x12+x22=30;,x13+x23=45;,tt(1)=4*x11+10*x12+10*x13;,tt(2)=6*x21+8*x22+20*x23;,End,28,运行结果:,Global optimal solution found at iteration:1,Objective value:486.0000,Variable Value Reduced Cost,X11 9.000008 0.1886861E-08,X21 40.99999 0.000000,X12 0.000000 4.666667,X22 30.00000 0.000000,X13 45.00000 0.000000,X23 0.000000 3.333333,TT(A1)486.0000 0.000000,TT(A2)486.0000 0.000000,29,91,函数的应用,在,LINGO,编程中,为了使程序更加简明,可阅读性,,LINGO,中提供了一类函数的命令集,主要有,if,sum,max,min,for,bin,gin,bnd,free,等,应用这些函数可以使程序变得很简明,下面介绍这些函数的应用。,if:-用于分段函数的编程,格式:if(A,B,C),含义:条件A成立时,取B,否则取C,例1,LINGO,的编程如下:,F=if(x1#GE#0#and#x1#LE#70,-505,124);,30,例2,引入决策,0-1,变量,则,31,LINGO,的编程如下:,g11=if(x1#GT#0#AND#x1#LE#70,1,0);,g12=if(x1#GT#70#AND#x1#LE#120,1,0);,g13=if(x1#GT#120#AND#x1#LE#150,1,0);,g14=if(x1#GT#150#AND#x1#LE#190,1,0);,f1=-g11*505+124*g12+252*g13+489*
点击显示更多内容>>

最新DOC

最新PPT

最新RAR

收藏 下载该资源
网站客服QQ:3392350380
装配图网版权所有
苏ICP备12009002号-6