优化模型动态规划

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

2、点，又是前一段某支路的终点。第 i个阶段的状态变量 ix应该包含前各阶段决策过程的全部信息，且之后作出的决策与之前的状态和决策无关。3决策（决策（Decision）:是指某阶段初从给定的状态出发决策者所作出的选择，决策变量)(kkxu表示第 i个阶段状态为 ix时对方案的选择。决策允许范围记为 )(kkxD)()(kkkkxDxu， 4策略（策略（Policy）:即决策序列。 n个阶段动态规划问题的策略可记为 )(),.,(),(2211nnxuxuxu，当 2k时， )(),.,(),(11nnkkkkxuxuxu表示从k阶段开始到最后的决策序列。5状态转移方程：状态转移方程：表明后一阶段和

3、前一阶段之间的k阶段状态和决策给定之后，第 关系。当第1k阶段状态就确定了，记为 )(,(1kkkkxuxTx6.指标函数：指标函数：阶段指标函数-对应于某一阶段状态和从该状态出发的决策的某种指标度量。第 k阶段指标函数记为)(,(kkkkxuxV；过程指标函数-从某阶段开始到最后过程的指标度量。记为 ),.,(11,nnkkkknkuxuxuxV，最优策略值记为 nkkkVxf,max(min)(7动态规划基本方程：动态规划基本方程：过程指标函数是各阶段指标函数的函数。)(),(max(min)(,)(),(max(min)(,11,11,kkkkkkknkiinkkkkkkkknkiink

4、xfuxVxfvVxfuxVxfvV有时若有时若 82 动态规划问题的解法动态规划问题的解法 例1设某仓库有12人巡逻守卫，负责4个要害部位，对每个部位可分别派2到4人巡逻，由于巡逻人数不同，各部位预期在一段时间内可能造成的损失也不一样，具体数字见下表。问该卫队应往各部位分别派多少人巡逻才能使预期损失最小？ABCD2人3人4人181410383531242221343125把12人派往4个部位看作4个阶段（k=1,2,3,4），每个阶段初可派遣的人数是前面阶段决策的结果，也是本阶段决策的依据。用 表示第 kxk个阶段的状态变量，用 ku表示第 k个阶段的决策变量（即在该阶段派出的人数，显然42

5、ku），各阶段可允许的决策集合 4 , 3 , 2 , 1,42|)(kuuxDkkkk状态转移方程为 3 , 2 , 1,1kuxxkkk用 )(kkuP表示第 k个阶段派出的巡逻人数为 ku时，在该部位的预期损失值过程指标函数 由于 44,)(kikikuPV用 )(kkxf表示从第 k个阶段到结束时预期损失值， )()(min)(11kkkkkkxfuPxf（1）先考虑D部位 )()(min)(, 4554444xfuPxfk0)(55xf42 , 42),(min)(444444xuuPxf25)4(,31) 3(,34)2(444fff（2）先考虑C，D部位 )()(min)(, 3

6、443333xfuPxfk由于 843 x，所以 462521min)4()4(min)8(473121,2522min)3()4(),4()3(min)7(493421,2524,3122min)2()4(),4()2(),3()3(min)6(553124,3422min)3()2(),2()3(min)5(583424)2()2(min)4(43343433434343343433433fPffPfPffPfPfPffPfPffPf（3）先考虑B，C，D部位 )()(min)(, 2332222xfuPxfk由于 1082 x，所以 804931,4735,4638min)6() 4()

7、,7() 3 (),8 () 2(min)10(845531,4935,4738min)5 () 4(),6() 3 (),7() 2(min) 9 (875831,5535,4938min)4() 4(),5 () 3 (),6() 2(min) 8 (323232232323223232322fPfPfPffPfPfPffPfPfPf（4）先考虑A，B，C，D部位 )()(min)(, 1221111xfuPxfk由于 121x，所以978710,8414,8018min)8()4(),9() 3(),10()2(min)12(2121211fPfPfPf由此可见，A，B，C，D四个部位应

8、分别派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最短路 3)(, 4)(2616FfFf例2（2）第五阶段E-G最短路735 , 43min)(),(),(),(min)(2621161115FfFEdFfFEdEf532 , 45min)(),(),(),(min)(2622161225FfFEdFfFEdEf936 , 46min)(),(),(),(min)(2623161335FfFEdFfFEdEf（3）第四阶段D-G最短路752 , 72min)(),(),(),

9、(min)(2521151114EfEDdEfEDdDf692 , 51min)(),(),(),(min)(3532252224EfEDdEfEDdDf893 , 53min)(),(),(),(min)(3533252334EfEDdEfEDdDf（4）第三阶段C-G最短路1368 , 76min)(),(),(),(min)(2421141113DfDCdDfDCdCf1065 , 73min)(),(),(),(min)(2422141223DfDCdDfDCdCf983 , 63min)(),(),(),(min)(3433242333DfDCdDfDCdCf1284 , 68min

10、)(),(),(),(min)(3434242443DfDCdDfDCdCf（5）第二阶段B-G最短路1396 ,103 ,131min)(),(),(),(),(),(min)(33312321131112CfCBdCfCBdCfCBdBf16126 , 97 ,108min)(),(),(),(),(),(min)(43423332232222CfCBdCfCBdCfCBdBf（6）第一阶段A-G最短路 18163 ,135min)(),(),(),(min)(2221212BfBAdBfBAdAf所以最短路是：A-B1-C2-D1-E2-F2-G,最短路长为18。例3求下列非线性规划问题

11、 0,12236max321321321xxxxxxxxxz解：要求 321,xxx的值，我们分三个阶段， 321,xxx分别为第1，2，3阶段的决策变量。 设状态变量为 4321,ssss，显然 33422311212,3,12xssxssxsss20 ,30 ,0332211sxsxsx阶段指标函数 1)(),(max)(4411sfsfkxsfkkkkk1.第三阶段2,2)(3max)(3*334432/03333sxssfxsfsx当达到最大值时2第二阶段 6,4)3(232max)(2max)(2*2222223/03323/0222222sxsxsxsfxsfsxsx当达到最大值时

12、3第一阶段 4,64)(41max)(max)(xsxsfxsfxx当达到最大值时所以 最优值为 2, 4334, 8, 4,123223211211xxssxxssxs6423446z例4 设备平行分配 某公司根据国家计划的安排拟将某种设备5台分给甲乙丙三个厂,各厂获得这种设备每年可向国家提供的利润如下表: 工厂设备台数 0 1 2 3 4 5甲03791213乙0510 111111丙046111212解:分3个阶段,甲第3厂,乙-第2厂,丙-第1厂 设 为第 k 厂获得的台数 为 台设备分配给第 k 个厂所得利润. 表示当前 k状态下的已分的设备总

13、数 表示当前状态下 台设备所得的最大利润第一阶段,考虑丙厂(k=1) kx)(kkxpkx)(kkbf)()(max)(001111bfxpbfkbkb5 ,4, 3 ,2, 1 ,0, 5 ,4, 3 ,2, 1 ,0,0)(1100 xbbf.12)5(,12)4(,11)3(,6)2(,4)1(,0)0(111111ffffff第2阶段,考虑乙,丙厂(k=2)()(max)(112222bfxpbf5 ,4, 3 ,2, 1 ,0, 5 ,4, 3 ,2, 1 ,022xb2,3,2112,17,21,17,15,12max)5(1,3.2,2,1612,516,16,15,11max)

14、4(2;1,1411,11,14,11max)3(,2,0,106,9,10max)2(1,0,54,5max)1(,0)0(212212122122122122xxfxxorxxfxxfxxfxxff第3阶段,考虑甲,乙,丙厂(k=3)5),()(max)(3223333bbfxpbf2,2,1.0,2,3,2113,17,19,21,19,21max)5(3213213xxxorxxxf有两种分配方案:总最大利润21方案1:甲0,乙2,丙3方案2:甲2,乙2,丙1第九章第九章 LINGO8.0编程介绍编程介绍LINGO程序的背景及应用程序的背景及应用美国芝加哥(Chicago)大学的Lin

15、us Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：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)目前的产品有：演示(试用)版、学生版、高级版、超

16、级版、工业版、扩展版 （求解问题规模和选件不同） LINDO和和LINGO软件能求解的优化模型软件能求解的优化模型 LINGO LINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)LINGO模型的优点模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO模型的构成：模型的构成：4个段个段目标与约束段（MODEL： END）集合段（SETS： ENDSETS）数据段（DATA： ENDDATA）初始段（INIT： ENDINIT）例1：编一个LINGO程序求解下列线性规划问题的最

17、优解04000030000006.115.1006.115.1006.115.1006.110000.015.1max322354443144413421343231241124232114141154322341ijxxxxxxxxxxxxxxxxxxxxxtsxxxxz程序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;

18、-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 X54 0.000000 0.000000 X11 0.000000 0.000000 X14 10000.00 0.000000 X2

19、1 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.2904355 0.000000 1.2173916 0.000000 1.0600007 19400.00 0.0000008 40000.00

20、 0.000000例2：编一个LINGO程序求解下列线性规划问题的最优解1 . 011216008817013016013098100. .98200160190150108120max765432176543217654321orxxxxxxxxxxxxxxxtsxxxxxxxzi程序一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

21、(x3); bin(x4); bin(x5); bin(x6); bin(x7);End程序二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); b

22、in(x(7); End运行结果：Global optimal solution found at teration: 0Objective value: 918.0000Variable 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.00000Row Slack or Surplus Dual Price 1

23、 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程序求解下列线性规划问题的最优解目标函数 min),max(21ttT约束条件 3 , 2 , 1, 2 , 1, 0453050231322122111jixxxxxxxij23222121312111208610104xxxtxxxt程序model: SETS: T/A1,A2/: tt; Endsetsinit: x11=10;x21=13;endinitmin =max(

24、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运行结果：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

25、 X13 45.00000 0.000000 X23 0.000000 3.333333 TT( A1) 486.0000 0.000000 TT( A2) 486.0000 0.0000009 91 1 函数的应用函数的应用 在LINGO编程中，为了使程序更加简明，可阅读性，LINGO中提供了一类函数的命令集，主要有if, if, sum, sum, max, max, min, min, for, for, bin, bin, gin, gin, bndbnd, ,freefree等，应用这些函数可以使程序变得很简明，下面介绍这些函数的应用。 ifif：-用于分段函数的编程用于分段函数的编

26、程 格式：格式：ifif（A A，B B，C C） 含义：条件含义：条件A A成立时，取成立时，取B B，否则取，否则取C C例1 其它124700505)(11xxfLINGO的编程如下：F=if(x1#GE#0#and#x1#LE#70,-505,124);例2 19015048915012025212070124700505)(11111xxxxxf引入决策0-1变量 ikg,则 141312111489252124505)(ggggxf其它其它其它其它01901501,01501201,0120701,07001114113112111xgxgxgxgLINGO的编程如下：g11=if

27、(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*g14;sumsum：-用于循环求和函数的编程用于循环求和函数的编程 格式：格式：sumsum（A:BA:B） 含义：含义：A A表示求和的变量及范围，表示求和的变量及范围，B B表示单项表达式。表示单项表达式。例3 wxciii201LINGO的编程如下：Model

28、: Sets: Var/1.20/:c,x; Endsetw=sum(Var(I): c(I)*x(I);end例4 wxcjiiji201j151LINGO的编程如下：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);endforfor：-用于循环函数的编程用于循环函数的编程 格式：格式：for(A:Bfor(A:B） 含义：含义：A A表示循环的变量及范围，表示循环的变量及范围，B B表示单项表达式。表示单项表达式。例5 wxcjiiji201j1

29、51,其中 ijx均为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 1 . 11 . 35 . 29 . 26 . 27 . 37 . 25 . 28 . 15 . 11 . 23 . 25 . 44 . 33 . 202111A2.32.521.21.35.325.26.22B,求 BACLINGO的编程如下：Model: Sets:

30、 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,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, ma

31、x, minmin：-用于求最大，最小函数的用于求最大，最小函数的编程编程格式：格式：max(A:B), max(A:B), min(A:Bmin(A:B） 含义：含义：A A表示循环的变量及范围，表示循环的变量及范围，B B表示单项表达式表示单项表达式。例7 1 . 11 . 35 . 29 . 26 . 27 . 37 . 25 . 28 . 15 . 11 . 23 . 25 . 44 . 33 . 202111A2 . 32 . 521 . 21 . 327 . 23 . 229 . 25 . 325 . 26 . 22BBAC求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.