多目標(biāo)線性規(guī)劃的若干解法及MATLAB實(shí)現(xiàn)

1、多目標(biāo)線性規(guī)劃的若干解法及 MATLAB實(shí)現(xiàn).多目標(biāo)線性規(guī)劃模型多目標(biāo)線性規(guī)劃有著兩個(gè)和兩個(gè)以上的目標(biāo)函數(shù)，且目標(biāo)函數(shù)和約束條件全是線性函數(shù),其數(shù)學(xué)模型表示為：乙=1人 +G2X2 + +GnXnZ2 =$1人 +C22X2 十+C2nXn一、max：:( 1)約束條件為：Zr =61X1 +62X2 + +CmXn11X1 +2X2 + +amXn 蘭 d821X1 +a22X2 十+a2nXn Eb2: : : (2)am1X1 +am2X2 + +amnXn EbmX1,X2,Xn 去0若(1 )式中只有一個(gè) 乙=CiXI +G2X2 + +GnXn，則該問題為典型的單目標(biāo)線性規(guī)劃。我們

2、記：人=佝)皿浙,C =(q)r疝，b=(b|,b2,bm) , (xi,x2, ,xn)Z珂乙乙,Zr)T.(3)則上述多目標(biāo)線性規(guī)劃可用矩陣形式表示為 max Z 二 Cx jAx _ b約束條件：>0二. MATLAB優(yōu)化工具箱常用函數(shù)3在MATLAB軟件中，有幾個(gè)專門求解最優(yōu)化問題的函數(shù)，如求線性規(guī)劃問題的linprog、求有約束非線性函數(shù)的fmincon、求最大最小化問題的fminimax、求多目標(biāo)達(dá)到問題的fgoalattain等，它們的調(diào)用形式分別為： .x,fval=li nprog(f,A,b,Aeq,beq,lb,ub)f為目標(biāo)函數(shù)系數(shù),A,b為不等式約束的系數(shù)，Ae

3、q,beq為等式約束系數(shù)，lb,ub為x的下 限和上限，fval求解的x所對(duì)應(yīng)的值。算法原理：?jiǎn)渭冃畏ǖ母倪M(jìn)方法投影法 .x,fval =fmi ncon(fun ,x0,A,b,Aeq,beq,lb,ub )fun為目標(biāo)函數(shù)的 M函數(shù)，x0為初值,A,b為不等式約束的系數(shù)，Aeq,beq為等式約束系數(shù)，lb,ub為x的下限和上限,fval求解的x所對(duì)應(yīng)的值。算法原理：基于 K-T ( Kuhn-Tucker )方程解的方法。 .x,fval =fmi nimax(fu n,xO,A,b,Aeq,beq,lb,ub)fun為目標(biāo)函數(shù)的 M函數(shù)，x0為初值,A,b為不等式約束的系數(shù)，Aeq,be

4、q為等式約束 系數(shù),lb,ub為x的下限和上限，fval求解的x所對(duì)應(yīng)的值。算法原理：序列二次規(guī)劃法。 .x,fval =fgoalatta in(fun, xO,goal,weight,A,b,Aeq,beq,lb,ub)fun為目標(biāo)函數(shù)的 M函數(shù)，x0為初值,goal變量為目標(biāo)函數(shù)希望達(dá)到的向量值 ，wight 參數(shù)指定目標(biāo)函數(shù)間的權(quán)重 ,A,b為不等式約束的系數(shù)，Aeq,beq為等式約束系數(shù)，lb,ub為x的 下限和上限，fval求解的x所對(duì)應(yīng)的值。算法原理：目標(biāo)達(dá)到法。三. 多目標(biāo)線性規(guī)劃的求解方法及MATLAB實(shí)現(xiàn)4.1理想點(diǎn)法在(3)中，先求解r個(gè)單目標(biāo)問題：rnin Zj(x),

5、 j =1,2 r，設(shè)其最優(yōu)值為Z*,稱Z* =(Z；,Z；,Z；)為值域中的一個(gè)理想點(diǎn)，因?yàn)橐话愫茈y達(dá)到。于是，在期望的某種度量之下，尋求距離 Z*最近的Z作為近似值。一種最直接的方法是最短距離理想點(diǎn)法，構(gòu)造評(píng) 價(jià)函數(shù)然后極小化 Z(x)，即求解niin Z(x)并將它的最優(yōu)解x作為(3)在這種意義下的“最優(yōu)解” 例1 :利用理想點(diǎn)法求解max t(x) - -3x-i ；x； max f；(x) = 4x1 3x； s.t ；捲 3x； _ 18；x1 x；乞 10x1, x- 0解：先分別對(duì)單目標(biāo)求解: 求解fjx)最優(yōu)解的MATLAB程序?yàn)?gt;> f=3;-2; A=2,3;

6、2,1; b=18;10; lb=O;O;>> x,fval=li nprog(f,A,b,lb)結(jié)果輸出為：x = 0.00006.0000fval = -12.0000即最優(yōu)解為12. 求解f2(X)最優(yōu)解的MATLAB程序?yàn)?gt;> f=-4;-3; A=2,3;2,1; b=18;10; lb=0;0;>> x,fval=li nprog(f,A,b,lb)結(jié)果輸出為：x =3.00004.0000fval =-24.0000即最優(yōu)解為24.于是得到理想點(diǎn)：(12, 24). 然后求如下模型的最優(yōu)解mnin f(x)H，Jf1(x122 f2(x242s

7、t 2為 3x2 _182xx> -10%,x2 _ 0MATLAB程序如下：>> A=2,3;2,1; b=18;10; x0=1;1; lb=0;0;>> x=fmi ncon( '(-3*x(1)+2*x(2)-12)A2+(4*x(1)+3*x(2)-24)A2)A(1/2) ',x0,A,b,lb,) 結(jié)果輸出為：x = 0.52685.6488則對(duì)應(yīng)的目標(biāo)值分別為f/x) =9.7172, f2(x) =19.0536.4.2線性加權(quán)和法在具有多個(gè)指標(biāo)的問題中，人們總希望對(duì)那些相對(duì)重要的指標(biāo)給予較大的權(quán)系數(shù)， 因而 將多目標(biāo)向量問題轉(zhuǎn)化

8、為所有目標(biāo)的加權(quán)求和的標(biāo)量問題， 基于這個(gè)現(xiàn)實(shí)，構(gòu)造如下評(píng)價(jià)函 數(shù)，即卩rmin Z(x)八 Z/x)x.D心將它的最優(yōu)解X*作為（3）在線性加權(quán)和意義下的“最優(yōu)解” 。（為加權(quán)因子，其選取 的方法很多，有專家打分法、容限法和加權(quán)因子分解法等） 例2：對(duì)例1進(jìn)行線性加權(quán)和法求解。（權(quán)系數(shù)分別取、= 0.5, '2 = 0.5） 解：構(gòu)造如下評(píng)價(jià)函數(shù)，即求如下模型的最優(yōu)解。min0.5 (3x -2屜)0.5 (-4為3x2)s.t 2x 3x2 _ 182x x2 _ 10x-!, x2 _ 0MATLAB程序如下：>> f=-0.5;-2.5; A=2,3;2,1; b=

9、18;10; lb=0;0;>> x=li nprog(f,A,b,lb)結(jié)果輸出為：x =0.00006.0000則對(duì)應(yīng)的目標(biāo)值分別為f1(x) =12, f2(x) =18.4.3最大最小法在決策的時(shí)候，采取保守策略是穩(wěn)妥的，即在最壞的情況下，尋求最好的結(jié)果，按照 此想法，可以構(gòu)造如下評(píng)價(jià)函數(shù)，即(Z)吧乙然后求解：min :Z(x)二 minmaxZi (x)x1并將它的最優(yōu)解x*作為(3)在最大最小意義下的“最優(yōu)解”。例3:對(duì)例1進(jìn)行最大最小法求解：解：MATLAB程序如下，首先編寫目標(biāo)函數(shù)的M文件：fun ctio n f=myfu n12(x)f(1)=3*x(1)-2

10、*x(2);f(2)=-4*x(1)-3*x(2);>> x0=1;1;A=2,3;2,1;b=18;10;lb=zeros(2,1);>> x,fval=fmi nimax('myfu n12',x0,A,b,lb,)結(jié)果輸出為：x =0.00006.0000fval = -12-18則對(duì)應(yīng)的目標(biāo)值分別為f/x) =12, f2(x) =18.4.4目標(biāo)規(guī)劃法Appr Z(x)； Z0(4)xD并把原多目標(biāo)線性規(guī)劃(3)minZ(x)稱為和目標(biāo)規(guī)劃(4)相對(duì)應(yīng)的多目標(biāo)線性規(guī)劃。X中為了用數(shù)量來描述(4),我們?cè)谀繕?biāo)空間 Er中引進(jìn)點(diǎn)Z(x)與乙

11、6;之間的某種“距離”rDZ(x), Z0 =、i(Zi(x)-Z；)21/2i d這樣(4)便可以用單目標(biāo) min DZ(x), Z°來描述了。x 二D例4:對(duì)例1對(duì)進(jìn)行目標(biāo)規(guī)劃法求解：解：MATLAB程序如下，首先編寫目標(biāo)函數(shù)的M文件：fun ctio n f=myfu n3(x)f(1)=3*x(1)-2*x(2);f(2)=-4*x(1)-3*x(2);>> goal=18,10; weight=18,10; x0=1,1; A=2,3;2,1; b=18,10; lb=zeros(2,1);>> x,fval=fgoalattai n( 'm

12、yfu n3',xO,goal,weight,A,b,lb,)結(jié)果輸出為：x =0.00006.0000fval =-12-18則對(duì)應(yīng)的目標(biāo)值分別為f,(x) =12, f2(x) =18.4.5模糊數(shù)學(xué)求解方法由于多目標(biāo)線性規(guī)劃的目標(biāo)函數(shù)不止一個(gè)，要想求得某一個(gè)點(diǎn)作 x*,使得所有的目標(biāo)函數(shù)都達(dá)到各自的最大值,這樣的絕對(duì)最優(yōu)解通常是不存在的。因此，在具體求解時(shí)，需要采取折衷的方案，使各目標(biāo)函數(shù)都盡可能的大。模糊數(shù)學(xué)規(guī)劃方法可對(duì)其各目標(biāo)函數(shù)進(jìn)行模糊化 處理，將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)，從而求該問題的模糊最優(yōu)解。一Ax 蘭 b*具體的方法為：先求在約束條件：下各個(gè)單目標(biāo)Zi,i =1,2/

13、 r的最大值Zi和x_ 0最小值 乙一，伸縮因子為dZ* -Z",i =1,2/ rmaxZ =九n£ q Xj _ dj 九啟 Zj _ dj j =1,2，r得到:(5)遲 aqXj 蘭bk,k = 1,2，,mj#一0,洛公2,Xn -0式(5)是一個(gè)簡(jiǎn)單的單目標(biāo)線性規(guī)劃問題。最后求得模糊最優(yōu)解為：Z* = C(x1 / , x*)T .利用式來求解的關(guān)鍵是對(duì)伸縮指標(biāo)的di確定，dj是我們選擇的一些常數(shù)，由于在多目標(biāo)線性規(guī)劃中，各子目標(biāo)難以同時(shí)達(dá)到最大值Z*，但是可以確定的是各子目標(biāo)的取值范圍，它滿足：Z乞Zj，所以，伸縮因子為 dj可以按如下取值：dZi -Zi_.

14、例5:對(duì)例1進(jìn)行模糊數(shù)學(xué)方法求解:Z* =(12,24).解：分別求得 f,(x), f2(x)在約束條件下的最大值為：分別求得f,(x),f2(x)在約束條件下的最小值為：Z-=：(-15,0).伸縮因子為di =(27,24)然后求如下模型的最優(yōu)解：maxZ = st -3x2x2 - 27，_ -154人 3x2 -24' - 02x-| 3x2 _182為 x2 _ 10治必， 一0MATLAB程序如下：>>f=0;0;-1; A=3,-2,27;-4,-3,24;2,3,0;2,1,0; b=15;0;18;10; lb=0;0;0>> x,fval=li nprog(f,A,b,lb)結(jié)果輸出為：x = 1.02535.31650.8354fval =-0.8354于是原多目標(biāo)規(guī)劃問題的模糊最優(yōu)值為Z* =(7.5571,20.0507).四. 結(jié)論多目線性標(biāo)規(guī)劃是優(yōu)化問題的一種 ，由于其存在多個(gè)目標(biāo)，要求各目標(biāo)同時(shí)取得較優(yōu)的 值,使得求解的方法與過程都相對(duì)復(fù)雜 .通過將目標(biāo)函數(shù)進(jìn)行模糊化