優(yōu)化模型動(dòng)態(tài)規(guī)劃

1、第八章第八章 動(dòng)態(tài)規(guī)劃問(wèn)題及求解動(dòng)態(tài)規(guī)劃問(wèn)題及求解81 多階段決策問(wèn)題多階段決策問(wèn)題動(dòng)態(tài)規(guī)劃是解決這樣一類最優(yōu)化問(wèn)題的專門計(jì)算方法，這類問(wèn)題允許把它的過(guò)程（求解）分解為一系列的單級(jí)過(guò)程（步驟）。最優(yōu)化原理：達(dá)到系統(tǒng)某種狀態(tài)的過(guò)程無(wú)論是怎樣的，以這個(gè)狀態(tài)為初始狀態(tài)的剩余過(guò)程的求解仍是最優(yōu)的規(guī)劃。也就是說(shuō)，當(dāng)系統(tǒng)處于第 i個(gè)狀態(tài)時(shí)，只要最優(yōu)規(guī)劃剩余的in 個(gè)過(guò)程，便可逐步求出 1i時(shí)的最優(yōu)解。為了方便討論動(dòng)態(tài)規(guī)劃的求解過(guò)程，我們把動(dòng)態(tài)規(guī)劃問(wèn)題化分為下面幾個(gè)過(guò)程： 1.階段（階段（stage）：）：把問(wèn)題恰當(dāng)?shù)姆譃槿舾蓚€(gè)相互聯(lián)系的階段；2狀態(tài)（狀態(tài)（State）:它是表示某段的出發(fā)位置，是某支路的起

2、點(diǎn)，又是前一段某支路的終點(diǎn)。第 i個(gè)階段的狀態(tài)變量 ix應(yīng)該包含前各階段決策過(guò)程的全部信息，且之后作出的決策與之前的狀態(tài)和決策無(wú)關(guān)。3決策（決策（Decision）:是指某階段初從給定的狀態(tài)出發(fā)決策者所作出的選擇，決策變量)(kkxu表示第 i個(gè)階段狀態(tài)為 ix時(shí)對(duì)方案的選擇。決策允許范圍記為 )(kkxD)()(kkkkxDxu， 4策略（策略（Policy）:即決策序列。 n個(gè)階段動(dòng)態(tài)規(guī)劃問(wèn)題的策略可記為 )(),.,(),(2211nnxuxuxu，當(dāng) 2k時(shí)， )(),.,(),(11nnkkkkxuxuxu表示從k階段開(kāi)始到最后的決策序列。5狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：表明后一階段和

3、前一階段之間的k階段狀態(tài)和決策給定之后，第 關(guān)系。當(dāng)?shù)?k階段狀態(tài)就確定了，記為 )(,(1kkkkxuxTx6.指標(biāo)函數(shù)：指標(biāo)函數(shù)：階段指標(biāo)函數(shù)-對(duì)應(yīng)于某一階段狀態(tài)和從該狀態(tài)出發(fā)的決策的某種指標(biāo)度量。第 k階段指標(biāo)函數(shù)記為)(,(kkkkxuxV；過(guò)程指標(biāo)函數(shù)-從某階段開(kāi)始到最后過(guò)程的指標(biāo)度量。記為 ),.,(11,nnkkkknkuxuxuxV，最優(yōu)策略值記為 nkkkVxf,max(min)(7動(dòng)態(tài)規(guī)劃基本方程：動(dòng)態(tài)規(guī)劃基本方程：過(guò)程指標(biāo)函數(shù)是各階段指標(biāo)函數(shù)的函數(shù)。)(),(max(min)(,)(),(max(min)(,11,11,kkkkkkknkiinkkkkkkkknkiink

4、xfuxVxfvVxfuxVxfvV有時(shí)若有時(shí)若 82 動(dòng)態(tài)規(guī)劃問(wèn)題的解法動(dòng)態(tài)規(guī)劃問(wèn)題的解法 例1設(shè)某倉(cāng)庫(kù)有12人巡邏守衛(wèi)，負(fù)責(zé)4個(gè)要害部位，對(duì)每個(gè)部位可分別派2到4人巡邏，由于巡邏人數(shù)不同，各部位預(yù)期在一段時(shí)間內(nèi)可能造成的損失也不一樣，具體數(shù)字見(jiàn)下表。問(wèn)該衛(wèi)隊(duì)?wèi)?yīng)往各部位分別派多少人巡邏才能使預(yù)期損失最小？ABCD2人3人4人181410383531242221343125把12人派往4個(gè)部位看作4個(gè)階段（k=1,2,3,4），每個(gè)階段初可派遣的人數(shù)是前面階段決策的結(jié)果，也是本階段決策的依據(jù)。用 表示第 kxk個(gè)階段的狀態(tài)變量，用 ku表示第 k個(gè)階段的決策變量（即在該階段派出的人數(shù)，顯然42

5、ku），各階段可允許的決策集合 4 , 3 , 2 , 1,42|)(kuuxDkkkk狀態(tài)轉(zhuǎn)移方程為 3 , 2 , 1,1kuxxkkk用 )(kkuP表示第 k個(gè)階段派出的巡邏人數(shù)為 ku時(shí)，在該部位的預(yù)期損失值過(guò)程指標(biāo)函數(shù) 由于 44,)(kikikuPV用 )(kkxf表示從第 k個(gè)階段到結(jié)束時(shí)預(yù)期損失值， )()(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由此可見(jiàn)，A，B，C，D四個(gè)部位應(yīng)

8、分別派4人，2人，2人，4人，預(yù)期損失值為97。 例5求從A點(diǎn)到G點(diǎn)的最段路線解：從A到G分六個(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,最短路長(zhǎng)為18。例3求下列非線性規(guī)劃問(wèn)題

11、 0,12236max321321321xxxxxxxxxz解：要求 321,xxx的值，我們分三個(gè)階段， 321,xxx分別為第1，2，3階段的決策變量。 設(shè)狀態(tài)變量為 4321,ssss，顯然 33422311212,3,12xssxssxsss20 ,30 ,0332211sxsxsx階段指標(biāo)函數(shù) 1)(),(max)(4411sfsfkxsfkkkkk1.第三階段2,2)(3max)(3*334432/03333sxssfxsfsx當(dāng)達(dá)到最大值時(shí)2第二階段 6,4)3(232max)(2max)(2*2222223/03323/0222222sxsxsxsfxsfsxsx當(dāng)達(dá)到最大值時(shí)

12、3第一階段 4,64)(41max)(max)(xsxsfxsfxx當(dāng)達(dá)到最大值時(shí)所以 最優(yōu)值為 2, 4334, 8, 4,123223211211xxssxxssxs6423446z例4 設(shè)備平行分配 某公司根據(jù)國(guó)家計(jì)劃的安排擬將某種設(shè)備5臺(tái)分給甲乙丙三個(gè)廠,各廠獲得這種設(shè)備每年可向國(guó)家提供的利潤(rùn)如下表: 工廠設(shè)備臺(tái)數(shù) 0 1 2 3 4 5甲03791213乙0510 111111丙046111212解:分3個(gè)階段,甲第3廠,乙-第2廠,丙-第1廠 設(shè) 為第 k 廠獲得的臺(tái)數(shù) 為 臺(tái)設(shè)備分配給第 k 個(gè)廠所得利潤(rùn). 表示當(dāng)前 k狀態(tài)下的已分的設(shè)備總

13、數(shù) 表示當(dāng)前狀態(tài)下 臺(tái)設(shè)備所得的最大利潤(rùn)第一階段,考慮丙廠(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有兩種分配方案:總最大利潤(rùn)21方案1:甲0,乙2,丙3方案2:甲2,乙2,丙1第九章第九章 LINGO8.0編程介紹編程介紹LINGO程序的背景及應(yīng)用程序的背景及應(yīng)用美國(guó)芝加哥(Chicago)大學(xué)的Lin

15、us Schrage教授于1980年前后開(kāi)發(fā), 后來(lái)成立 LINDO系統(tǒng)公司（LINDO Systems Inc.）， 網(wǎng)址：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)目前的產(chǎn)品有：演示(試用)版、學(xué)生版、高級(jí)版、超

16、級(jí)版、工業(yè)版、擴(kuò)展版 （求解問(wèn)題規(guī)模和選件不同） LINDO和和LINGO軟件能求解的優(yōu)化模型軟件能求解的優(yōu)化模型 LINGO LINDO優(yōu)化模型優(yōu)化模型線性規(guī)劃線性規(guī)劃(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)LINGO模型的優(yōu)點(diǎn)模型的優(yōu)點(diǎn)包含了LINDO的全部功能提供了靈活的編程語(yǔ)言（矩陣生成器）LINGO模型的構(gòu)成：模型的構(gòu)成：4個(gè)段個(gè)段目標(biāo)與約束段（MODEL： END）集合段（SETS： ENDSETS）數(shù)據(jù)段（DATA： ENDDATA）初始段（INIT： ENDINIT）例1：編一個(gè)LINGO程序求解下列線性規(guī)劃問(wèn)題的最

17、優(yōu)解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運(yùn)行結(jié)果：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：編一個(gè)LINGO程序求解下列線性規(guī)劃問(wèn)題的最優(yōu)解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運(yùn)行結(jié)果：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：編一個(gè)LINGO程序求解下列線性規(guī)劃問(wèn)題的最優(yōu)解目標(biāo)函數(shù) 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運(yùn)行結(jié)果：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 函數(shù)的應(yīng)用函數(shù)的應(yīng)用 在LINGO編程中，為了使程序更加簡(jiǎn)明，可閱讀性，LINGO中提供了一類函數(shù)的命令集，主要有if, if, sum, sum, max, max, min, min, for, for, bin, bin, gin, gin, bndbnd, ,freefree等，應(yīng)用這些函數(shù)可以使程序變得很簡(jiǎn)明，下面介紹這些函數(shù)的應(yīng)用。 ifif：-用于分段函數(shù)的編程用于分段函數(shù)的編

26、程 格式：格式：ifif（A A，B B，C C） 含義：條件含義：條件A A成立時(shí)，取成立時(shí)，取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：-用于循環(huán)求和函數(shù)的編程用于循環(huán)求和函數(shù)的編程 格式：格式：sumsum（A:BA:B） 含義：含義：A A表示求和的變量及范圍，表示求和的變量及范圍，B B表示單項(xiàng)表達(dá)式。表示單項(xiàng)表達(dá)式。例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：-用于循環(huán)函數(shù)的編程用于循環(huán)函數(shù)的編程 格式：格式：for(A:Bfor(A:B） 含義：含義：A A表示循環(huán)的變量及范圍，表示循環(huán)的變量及范圍，B B表示單項(xiàng)表達(dá)式。表示單項(xiàng)表達(dá)式。例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：-用于求最大，最小函數(shù)的用于求最大，最小函數(shù)的編程編程格式：格式：max(A:B), max(A:B), min(A:Bmin(A:B） 含義：含義：A A表示循環(huán)的變量及范圍，表示循環(huán)的變量及范圍，B B表示單項(xiàng)表達(dá)式表示單項(xiàng)表達(dá)式。例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.