二次_動態(tài)規(guī)劃-圖論

1、§1 二次規(guī)劃模型數(shù)學(xué)模型：其中H為二次型矩陣，A、Aeq分別為不等式約束與等式約束系數(shù)矩陣，f,b,beq,lb,ub,x為向量。求解二次規(guī)劃問題函數(shù)為quadprog( )調(diào)用格式：X= quadprog(H,f,A,b)X= quadprog(H,f,A,b,Aeq,beq)X= quadprog(H,f,A,b,Aeq,beq,lb,ub)X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)x,fval= quadprog()x,fval,exitflag= qua

2、dprog()x,fval,exitflag,output= quadprog()x,fval,exitflag,output,lambda= quadprog()說明：輸入?yún)?shù)中，x0為初始點(diǎn)；若無等式約束或無不等式約束，就將相應(yīng)的矩陣和向量設(shè)置為空；options為指定優(yōu)化參數(shù)。輸出參數(shù)中，x是返回最優(yōu)解；fval是返回解所對應(yīng)的目標(biāo)函數(shù)值；exitflag是描述搜索是否收斂；output是返回包含優(yōu)化信息的結(jié)構(gòu)。Lambda是返回解x入包含拉格朗日乘子的參數(shù)。例1：求解：二次規(guī)劃問題min f(x)= x1-3x2+3x12+4x22-2x1x2s.t 2x1+x22 -x1+4x23程

3、序：f=1;-3;H=6 -2;-2 8;A=2 1;-1 4;b=2;3;X,fval,exitflag=quadprog(H,f,A,b)結(jié)果：X = -0.0455 0.3636fval = -0.5682exitflag = 1例2：求解：二次規(guī)劃問題min x12+2x22-2x1x2-4x1-12x2s.t x1+x22 -x1+2x22 2x1+x230x1, 0x2程序：H=2 -2;-2 4;f=-4;-12;A=1 1;-1 2;2 1;b=2;2;3;lb=zeros(2,1);x,fval,exitflag=quadprog(H,f,A,b,lb)結(jié)果：x = 0.66

4、67 1.3333fval = -16.4444exitflag = 1練習(xí)1 求解下面二次規(guī)劃問題sub.to 解：則，在MATLAB中實現(xiàn)如下：>>H = 1 -1; -1 2 ;>>f = -2; -6;>>A = 1 1; -1 2; 2 1;>>b = 2; 2; 3;>>lb = zeros(2,1);>>x,fval,exitflag,output,lambda = quadprog(H,f,A,b, , ,lb)結(jié)果為：x = %最優(yōu)解 0.6667 1.3333fval = %最優(yōu)值 -8.2222exi

5、tflag = %收斂 1output = iterations: 3 algorithm: 'medium-scale: active-set' firstorderopt: cgiterations: lambda = lower: 2x1 double upper: 2x1 double eqlin: 0x1 double ineqlin: 3x1 double>> lambda.ineqlinans = 3.1111 0.4444 0>> lambda.lowerans = 0 0說明 第1、2個約束條件有效，其余無效。練習(xí)2 求二次規(guī)劃的最優(yōu)解

6、max f (x1, x2)=x1x2+3sub.to x1+x2-2=0解：化成標(biāo)準(zhǔn)形式： sub.to x1+x2=2在Matlab中實現(xiàn)如下：>>H=0,-1;-1,0;>>f=0;0;>>Aeq=1 1;>>beq=2;>>x,fval,exitflag,output,lambda = quadprog(H,f, , ,Aeq,beq)結(jié)果為：x = 1.0000 1.0000fval = -1.0000exitflag = 1output = firstorderopt: 0 iterations: 1 cgiteratio

7、ns: 1 algorithm: 1x58 charlambda = eqlin: 1.0000 ineqlin: lower: upper: §2最大最小化模型基本思想：在對策論中，我們常遇到這樣的問題：在最不利的條件下，尋求最有利的策略。在實際問題中也有許多求最大值的最小化問題。例如急救中心選址問題就是要規(guī)劃其到所有地點(diǎn)最大距離的最小值。在投資規(guī)劃中要確定最大風(fēng)險的最低限度等等。為此，對每個xR,我們先求諸目標(biāo)值fi(x)的最大值，然后再求這些最大值中的最小值。最大最小化問題的數(shù)學(xué)模型：求解最大最小化問題的函數(shù)為 fminimax調(diào)用格式：x=fminimax(F,x0,)x=f

8、minimax(F,x0,A,b)x=fminimax(F,x0,A,b,Aeq,beq)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2)x,fval=fminimax()x,fval,maxfval=fminimax()x,fval,maxfval,exitflag,output=

9、fminimax()x,fval,maxfval,exitflag,output,lambda=fminimax()說明：F為目標(biāo)函數(shù)；x0為初值； A、b為線性不等式約束的矩陣與向量；Aeq、beq為等式約束的矩陣與向量；lb、ub為變量x的上、下界向量；nonlcon為定義非線性不等式約束函數(shù)c(x)和等式約束函數(shù)ceq(x)；options中設(shè)置優(yōu)化參數(shù)。x返回最優(yōu)解；fval返回解x處的目標(biāo)函數(shù)值；maxfval返回解x處的最大函數(shù)值；exitflag描述計算的退出條件；output返回包含優(yōu)化信息的輸出參數(shù)；lambda返回包含拉格朗日乘子的參數(shù)。例1 求解下列最大最小值問題： 首先

10、編輯M文件ff14.mfunction f=ff14(x)f(1)=3*x(1)2+2*x(2)2-12*x(1)+35;f(2)=5*x(1)*x(2)-4*x(2)+7;f(3)=x(1)2+6*x(2);f(4)=4*x(1)2+9*x(2)2-12*x(1)*x(2)+20;取初值x0=(1,1)調(diào)用優(yōu)化函數(shù)x0=1 1;x,fval,maxfval=fminimax(ff14,x0)結(jié)果：x = 1.7637 0.5317fval = 23.7331 9.5621 6.3010 23.7331例2：選址問題設(shè)某城市有某種物品的10個需求點(diǎn)，第i個需求點(diǎn)Pi的坐標(biāo)為(ai,bi),道路

11、網(wǎng)與坐標(biāo)軸平行，彼此正交?，F(xiàn)打算建一個該物品的供應(yīng)中心，且由于受到城市某些條件的限制，該供應(yīng)中心只能設(shè)在x界于5,8，y界于5.8的范圍之內(nèi)。問該中心應(yīng)建在何處為好?P點(diǎn)的坐標(biāo)為：ai1435912620178bi2108181451089建立數(shù)學(xué)模型：設(shè)供應(yīng)中心的位置為(x,y)，要求它到最遠(yuǎn)需求點(diǎn)的距離盡可能小，此處采用沿道路行走計算距離，可知每個用戶點(diǎn)Pi到該中心的距離為 |x-ai|+|y-bi|，于是有： 編程：首先編輯M文件：ff15.mfunction f = ff15(x)a=1 4 3 5 9 12 6 20 17 8;b=2 10 8 18 1 4 5 10 8 9;f(1

12、) = abs(x(1)-a(1)+abs(x(2)-b(1);f(2) = abs(x(1)-a(2)+abs(x(2)-b(2);f(3) = abs(x(1)-a(3)+abs(x(2)-b(3);f(4) = abs(x(1)-a(4)+abs(x(2)-b(4);f(5) = abs(x(1)-a(5)+abs(x(2)-b(5);f(6) = abs(x(1)-a(6)+abs(x(2)-b(6);f(7) = abs(x(1)-a(7)+abs(x(2)-b(7);f(8) = abs(x(1)-a(8)+abs(x(2)-b(8);f(9) = abs(x(1)-a(9)+ab

13、s(x(2)-b(9);f(10) = abs(x(1)-a(10)+abs(x(2)-b(10);然后 用以下程序計算 ：x0 = 6; 6; AA=-1 0 1 0 0 -1 0 1;bb=-5;8;-5;8;x,fval = fminimax(ff15,x0,AA,bb)結(jié)果：x = 8 8fval = 13 6 5 13 8 8 5 14 9 1即：在坐標(biāo)為(8,8)處設(shè)置供應(yīng)中心可以使該點(diǎn)到各需求點(diǎn)的最大距離最小，最小的最大距離為14單位。練習(xí) 求下列函數(shù)最大值的最小化問題其中：解：先建立目標(biāo)函數(shù)文件，并保存為ff16.m：function f = ff16(x)f(1)= 2*x(

14、1)2+x(2)2-48*x(1)-40*x(2)+304; f(2)= -x(1)2 - 3*x(2)2;f(3)= x(1) + 3*x(2) -18;f(4)= -x(1)- x(2);f(5)= x(1) + x(2) - 8;然后，在命令窗口鍵入命令：x0 = 0.1; 0.1; % 初始值x,fval,maxf = fminimax(ff16,x0)結(jié)果為：x = 4.0000 4.0000fval = 0.0000 -64.0000 -2.0000 -8.0000 -0.0000 maxf = 2.2737e-013§3動態(tài)規(guī)劃模型AB1B2C1C2C3D1D

15、2E536337263871如圖所示，給定一個線路網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間距離，試求一條從A到E的路線，使總距離為最短。Mattlab求解：首先利用Excel建立工作表edge存儲圖的上三角陣。其中edge=9999952999999999999999999999999999999999999999999999379999999999999999999999999999999999999999639999999999999999999999999999999999999999999996999999999999999999999999999999999999999938999999

16、99999999999999999999999999999999991999999999999999999999999999999999999999999999399999999999999999999999999999999999999997999999999999999999999999999999999999999999999,然后在Matlab調(diào)入以上數(shù)據(jù)。同時將調(diào)用自編的動態(tài)規(guī)劃程序函數(shù)“dongtaigh.m”，即在Matlab命令窗口輸入n=9;distance,path=dongtaigh(edge,n),回車后則在窗口顯示出路徑Path和距離distance§4最小

17、生成樹725314650604565524050703042例1 某工廠要架設(shè)局域網(wǎng)聯(lián)通工廠各個部門。已知工廠有7個部門，各個部門間鋪設(shè)網(wǎng)線的距離如上圖所示，計算出鋪設(shè)網(wǎng)線的最短距離。Matlab的算法： 首先，將上圖的鄰接矩陣存儲為G；即：G=999995060999999999999999999995099999999996540999999999960999999999952999999999945999996552999995030429999940999995099999709999999999999999999930709999999999999999999945429999999

18、99999999,然后調(diào)入到Matlab命令窗口中，另外將調(diào)用自編程序shengcs.m，即:n=7;result=shengcs(G,n)即可看見最小生成樹的連接方式。 例2 某六個城市之間的道路網(wǎng)如下圖所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使得電話線的總長度最短。v5v6v2v4627535441V1v3 §5最短路例3 如下圖所示的交通網(wǎng)絡(luò)，邊上的權(quán)重代表城市之間的距離，求城市1到其他城市的最短路徑。12354101003010502060Matlab的算法： 首先，將上圖的鄰接矩陣存儲為H；即：H=99999109999930100999999999950999

19、9999999999999999999999999991099999999992099999999999999999999999996099999然后調(diào)入到Matlab命令窗口中，另外將調(diào)用自編程序zuiduanlu.m,即：n=5;path=zuiduanlu(H,n)即可看見最最短路的連接方式。例4: 如下圖所示的單行線交通網(wǎng)，每個弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在有一個人要從v1出發(fā)，經(jīng)過這個交通網(wǎng)到達(dá)v8，要尋求是總路程最短的線路。v6v4v2v8v7v963623410231262410V1V3v5§6網(wǎng)絡(luò)最大流VsV2V3VtV1V4(3,x1)(1,x3)(4,x4

20、)(5,x7)(5,x2)(2,x6)(1,x5)(2,x8)如上圖所示，每條弧相關(guān)的括號中，第一個數(shù)據(jù)表示該條弧的容量，第二個表示該弧流量，最大流量必須滿足以下條件的限制：1. 可行性條件：xi>=0, x1<=3, x2<=5, x3<=1, x4<=4, x5<=1,x6<=2, x7<=5, x8<=22. 始點(diǎn)Vs和收點(diǎn)Vt容量的要求：x1+x2<=8, x7+x8<=73. 流量平衡要求總流入量和總流出量相同：x1+x2-x7-x8=04. 內(nèi)節(jié)點(diǎn)流入量和流出量相同：x1+x5-x3-x4=0x2+x3-x6=0x6

21、-x5-x8=0x4-x7=0目標(biāo)函數(shù)為：max z=x1+x2軟件求解：Matlab函數(shù)：linprog(線性規(guī)劃), ip（整數(shù)規(guī)劃） Lindo軟件求解結(jié)果如下： OBJECTIVE FUNCTION VALUE 1) 5.000000 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 2.000000 0.000000 X3 0.000000 1.000000 X4 3.000000 0.000000 X5 0.000000 0.000000 X6 2.000000 0.000000 X7 3.000000 0.000000 X8 2.000000 0.000000例5.如下圖所示為一城市水管網(wǎng)絡(luò)流量圖，試求一條從始點(diǎn)Vs到收點(diǎn)Vt的最大流v3v1vtv2v4vs1735108611453 §6最小費(fèi)用最大流問題網(wǎng)絡(luò)最大流只考慮了流量的問題，實際在運(yùn)用時還有“費(fèi)用”因素存在。人們總是希望在得到最大流的同時，使費(fèi)用最少，這就是最小費(fèi)用最大流問題VsV2V3VtV1V4(3,2，x1)(1,1，x3)(4,，5，