《优化模型动态规划》PPT课件.ppt

《《优化模型动态规划》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《优化模型动态规划》PPT课件.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 动态规划问题及求解动态规划问题及求解81 多阶段决策问题多阶段决策问题动态规划是解决这样一类最优化问题的专门计算方法，这类问题允许把它的过程（求解）分解为一系列的单级过程（步骤）。最优化原理：达到系统某种状态的过程无论是怎样的，以这个状态为初始状态的剩余过程的求解仍是最优的规划。也就是说，当系统处于第 个状态时，只要最优规划剩余的个过程，便可逐步求出 时的最优解。为了方便讨论动态规划的求解过程，我们把动态规划问题化分为下面几个过程：1.阶段（阶段（stage）：）：把问题恰当的分为若干个相互联系的阶段；2状态（状态（State）:它是表示某段的出发位置，是某支路的起点，又是前一段

2、某支路的终点。第 个阶段的状态变量 应该包含前各阶段决策过程的全部信息，且之后作出的决策与之前的状态和决策无关。3决策（决策（Decision）:是指某阶段初从给定的状态出发决策者所作出的选择，决策变量表示第 个阶段状态为 时对方案的选择。决策允许范围记为，4策略（策略（Policy）:即决策序列。个阶段动态规划问题的策略可记为，当 时，表示从阶段开始到最后的决策序列。5状状态转态转移方程：移方程：表明后一阶段和前一阶段之间的阶段状态和决策给定之后，第 关系。当第阶段状态就确定了，记为 6.指标函数：指标函数：阶段指标函数-对应于某一阶段状态和从该状态出发的决策的某种指标度量。第 阶段指标函数

3、记为；过程指标函数-从某阶段开始到最后过程的指标度量。记为，最优策略值记为 7动态规划基本方程：动态规划基本方程：过程指标函数是各阶段指标函数的函数。82 动态规划问题的解法动态规划问题的解法 例1设某仓库有12人巡逻守卫，负责4个要害部位，对每个部位可分别派2到4人巡逻，由于巡逻人数不同，各部位预期在一段时间内可能造成的损失也不一样，具体数字见下表。问该卫队应往各部位分别派多少人巡逻才能使预期损失最小？ABCD2人3人4人181410383531242221343125把12人派往4个部位看作4个阶段（k=1,2,3,4），每个阶段初可派遣的人数是前面阶段决策的结果，也是本阶段决策的依据。用

4、 表示第 个阶段的状态变量，用 表示第 个阶段的决策变量（即在该阶段派出的人数，显然），各阶段可允许的决策集合 状态转移方程为 用 表示第 个阶段派出的巡逻人数为 时，在该部位的预期损失值过程指标函数 由于 用 表示从第 个阶段到结束时预期损失值，（1）先考虑D部位（2）先考虑C，D部位 由于，所以（3）先考虑B，C，D部位 由于，所以（4）先考虑A，B，C，D部位 由于，所以由此可见，A，B，C，D四个部位应分别派4人，2人，2人，4人，预期损失值为97。例5求从A点到G点的最段路线解：从A到G分六个阶段：A-B,B-C,C-D,D-E,E-F,F-G（1）第六阶段F-G最短路 例2（2）第

5、五阶段E-G最短路（3）第四阶段D-G最短路（4）第三阶段C-G最短路（5）第二阶段B-G最短路（6）第一阶段A-G最短路 所以最短路是：A-B1-C2-D1-E2-F2-G,最短路长为18。例3求下列非线性规划问题 解：要求 的值，我们分三个阶段，分别为第1，2，3阶段的决策变量。设状态变量为，显然 阶段指标函数 1.第三阶段2第二阶段 3第一阶段 所以 最优值为 例4 设备平行分配 某公司根据国家计划的安排拟将某种设备5台分给甲乙丙三个厂,各厂获得这种设备每年可向国家提供的利润如下表:工厂设备台数 0 1 2 3 4 5甲03791213乙0510 111111丙046111212解:分3

6、个阶段,甲第3厂,乙-第2厂,丙-第1厂 设 为第 k 厂获得的台数 为 台设备分配给第 k 个厂所得利润.表示当前 k状态下的已分的设备总数 表示当前状态下 台设备所得的最大利润第一阶段,考虑丙厂(k=1)第2阶段,考虑乙,丙厂(k=2)第3阶段,考虑甲,乙,丙厂(k=3)有两种分配方案:总最大利润21方案1:甲0,乙2,丙3方案2:甲2,乙2,丙1第九章第九章 LINGO8.0编程介绍编程介绍LINGO程序的背景及应用程序的背景及应用美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立 LINDO系统公司（LINDO Systems Inc.），网

7、址：http:/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)目前的产品有：演示(试用)版、学生版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）LINDO和和LINGO软件能求解的优化模型软件能求解的优化模型LINGOLINDO优化模型

8、优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)LINGO模型的优点模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO模型的构成：模型的构成：4个段个段目标与约束段（MODEL：END）集合段（SETS：ENDSETS）数据段（DATA：ENDDATA）初始段（INIT：ENDINIT）例1：编一个LINGO程序求解下列线性规划问题的最优解程序model:max=1.15*x41+1.4*x23+1.25*x32+1.06*x54;x11+x14=10000;-1.06*x14+x21+

9、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 Variable Value Reduced Cost X41 0.000000 0.6739130E-01 X23 10600.00 0.000000 X32 0.000000 0.4043478E-01 X

10、54 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 3 0.000000 1.4000004 0.000000 1.290435

11、5 0.000000 1.2173916 0.000000 1.0600007 19400.00 0.0000008 40000.00 0.000000例2：编一个LINGO程序求解下列线性规划问题的最优解程序一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程序二mod

12、el: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运行结果：Globaloptimalsolutionfoundatteration:0Objectivevalu

13、e:918.0000VariableValueReducedCostX11.000000-120.0000X20.000000-108.0000X31.000000-150.0000X41.000000-190.0000X51.000000-160.0000X61.000000-200.0000X71.000000-98.00000RowSlackorSurplusDualPrice1918.00001.0000002822.00000.00000030.0000000.00000041.0000000.00000051.0000000.000000例3：编一个LINGO程序求解下列线性规划问

14、题的最优解目标函数 约束条件 程序model:SETS:T/A1,A2/:tt;Endsetsinit:x11=10;x21=13;endinitmin=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运行结果：Globaloptimalsolutionfoundatiteration:1Objectivevalue:486.0000VariableValueReducedCostX119.0000080.1886861E-08X2140.

15、999990.000000X120.0000004.666667X2230.000000.000000X1345.000000.000000X230.0000003.333333TT(A1)486.00000.000000TT(A2)486.00000.0000009 91 1函数的应用函数的应用在LINGO编程中，为了使程序更加简明，可阅读性，LINGO中提供了一类函数的命令集，主要有if,if,sum,sum,max,max,min,min,for,for,bin,bin,gin,gin,bnd,bnd,freefree等，应用这些函数可以使程序变得很简明，下面介绍这些函数的应用。ifif

16、：-用于分段函数的编程用于分段函数的编程 格式：格式：ifif（A A，B B，C C）含义：条件含义：条件A A成立时，取成立时，取B B，否则取，否则取C C例1 LINGO的编程如下：F=if(x1#GE#0#and#x1#LE#70,-505,124);例2 引入决策0-1变量,则 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=

17、-g11*505+124*g12+252*g13+489*g14;sumsum：-用于循环求和函数的编程用于循环求和函数的编程 格式：格式：sumsum（A:BA:B）含义：含义：A A表示求和的变量及范围，表示求和的变量及范围，B B表示单项表达式。表示单项表达式。例3 LINGO的编程如下：Model:Sets:Var/1.20/:c,x;Endsetw=sum(Var(I):c(I)*x(I);end例4 LINGO的编程如下：Model:Sets:Var1/1.20/:a;Var2/1.15/:b;Var(Var1,Var2):c,x;Endsetw=sum(Var(I,J):c(I，

18、J)*x(I,J);endforfor：-用于循环函数的编程用于循环函数的编程 格式：格式：for(A:Bfor(A:B）含义：含义：A A表示循环的变量及范围，表示循环的变量及范围，B B表示单项表达式。表示单项表达式。例5,其中 均为0或1LINGO的编程如下：Model:Sets:Var1/1.20/:a;Var2/1.15/:b;Var(Var1,Var2):c,x;Endsetw=sum(Var(I,J):c(I，J)*x(I,J);for(Var(I,J):BIN(x(I,J);end例6,求 LINGO的编程如下：Model:Sets:Var1/1.5/:II;Var2/1.4/

19、:JJ;Var3/1.3/:KK;Link1(Var2,Var1):A;Link2(Var1,Var3):B;Link3(Var2,Var3):C;EndsetsData:A=1,1,1,2,0,2.3,3.4,4.5,2.3,2.1,1.5,1.8,2.5,2.7,3.7,2.6,2.9,2.5,3.1,1.1;B=2,2.6,2.5,2,3.5,2.9,2,2.3,2.7,2,3.1,2.1,2,5.2,3.2;Enddatafor(Link3(I,J):C(I,J)=sum(Var1(K):A(I,K)*B(K,J);endmax,max,minmin：-用于求最大，最小函数的用于求最大

20、，最小函数的编程编程格式：格式：max(A:B),max(A:B),min(A:Bmin(A:B）含义：含义：A A表示循环的变量及范围，表示循环的变量及范围，B B表示单项表达式。表示单项表达式。例7 求C中最大和最小的元素。LINGO的编程如下：Model:Sets:Var1/1.5/:II;Var2/1.4/:JJ;Var3/1.3/:KK;Link1(Var2,Var1):A;Link2(Var1,Var3):B;Link3(Var2,Var3):C;EndsetsData:A=1,1,1,2,0,2.3,3.4,4.5,2.3,2.1,1.5,1.8,2.5,2.7,3.7,2.6,

21、2.9,2.5,3.1,1.1;B=2,2.6,2.5,2,3.5,2.9,2,2.3,2.7,2,3.1,2.1,2,5.2,3.2;EnddataM=max(Link3(I,J):sum(Var1(K):A(I,K)*B(K,J);N=min(Link3(I,J):sum(Var1(K):A(I,K)*B(K,J);endbndbnd：-用于边界限制函数的编程用于边界限制函数的编程格式：格式：bnd(A1,B,A2)bnd(A1,B,A2)含义：含义：A1,A2A1,A2表示边界表示边界1 1，边界，边界2 2，B B表示变量。表示变量。例8 例9用LINGO编写“求下列各点到T的最短路”

22、的程序56774968658336C1B1C2B2A1A2A3TS6model:SETS:!CITIES表示由19组成的集合，是一个基本集合;CITIES/1.9/:L;!属性L(i)表示城市i到城市1的最优行驶路线的路长;ROADS(CITIES,CITIES)/!ROADS表示网络中的弧，是由CITIES派生的集合;9,6 9,7 9,8!由于并非所有城市间都有道路直接连接，所以将弧具体列出;6,4 6,5 7,4 7,5 8,4 8,5 4,2 4,3 5,2 5,3 2,1 3,1/:D;!属性D(i,j)是城市i到j的直接距离（已知）;ENDSETSDATA:D=!D赋值的顺序对应于

23、ROADS中的弧的顺序;6 3 3 6 5 8 6 7 4 6 7 8 9 5 6;ENDDATAL(1)=0;!边界条件;FOR(CITIES(i)|i#GT#1:!集合循环语句,#GT#表示逻辑关系大于;L(i)=MIN(ROADS(i,j):D(i,j)+L(j)!这就是动态规划基本方程;);endFeasiblesolutionfoundatiteration:0VariableValueL(1)0.000000L(2)5.000000L(3)6.000000L(4)11.00000L(5)13.00000L(6)17.00000L(7)19.00000L(8)17.00000L(9)20.00000