線性規(guī)劃的若干解法及軟件實現(xiàn)

1、多目標線性規(guī)劃的若干解法及matlab實現(xiàn)摘要：求解多目標線性規(guī)劃的基本思想大都是將多目標問題轉(zhuǎn)化為單目標規(guī)劃，本文介紹了 理想點法、線性加權(quán)和法、最大最小法、目標規(guī)劃法，然后給出多目標線性規(guī)劃的模糊數(shù) 學(xué)解法，最后對每種解法給出例子，并用mat lab軟件加以實現(xiàn)。關(guān)鍵詞：多目標線性規(guī)劃mat lab模糊數(shù)學(xué)一.引言多目標線性規(guī)劃是多目標最優(yōu)化理論的重要組成部分，由于多個目標之間的矛盾性和不 可公度性,要求使所有目標均達到最優(yōu)解是不可能的，因此多目標規(guī)劃問題往往只是求其有 效解（非劣解）。目前求解多目標線性規(guī)劃問題有效解的方法,有理想點法、線性加權(quán)和法、 最大最小法、冃標規(guī)劃法，然而這些方法

2、對多冃標偏好信息的確定、處理等方面的研究工作 較少，本文也給出多目標線性規(guī)劃的模糊數(shù)學(xué)解法。二.多目標線性規(guī)劃模型多目標線性規(guī)劃有看兩個和兩個以上的目標函數(shù)，且目標函數(shù)和約束條件全是線性函 數(shù),其數(shù)學(xué)模型表示為：max-z = 5 兀+ci2x2 +z-y =+ c22x2 +(1)約束條件為:lz=c"+cr2 兀2 +$內(nèi)+如兀2+ +。2屆2陽聲+僉2馮+%£仏旺,兀2，(2)若（1）式中只有一個zc+c-h+5百,則該問題為典型的單目標線性規(guī)劃。我們記:a =(勺)皿“，。=2幾，b = (bvb2,陽,x = xvx2, 9xn)t ,z = （zpz2,，乙）則

3、上述多目標線性規(guī)劃可用矩陣形式表示為: max z = cxax<b約束條件：彳(3)x>0三. matlab優(yōu)化工具箱常用函數(shù)在matlab軟件中，有幾個專門求解最優(yōu)化問題的函數(shù)，如求線性規(guī)劃問題的linprog> 求有約束非線性函數(shù)的fmincon求最大最小化問題的fminimax求多目標達到問題的 fgoalattain等，它們的調(diào)用形式分別為:®.x,fvalj=linprog(f,a,b,aeq,beqjb,ub)為目標函數(shù)系數(shù),a,b為不等式約束的系數(shù),aeq,beq為等式約束系數(shù),lb,ub為x的下 限和上限,fval求解的x所對應(yīng)的值。算法原理：單純

4、形法的改進方法投影法 .x,fval =fmincon(fun,xo,a,b,aeq,beq,lb,ub)fun為目標函數(shù)的m函數(shù),xo為初值,a,b為不等式約束的系數(shù),aeq,beq為等式約束 系數(shù),lb,ub為x的下限和上限,fval求解的x所對應(yīng)的值。算法原理：基于kt (kuhn-tucker)方程解的方法。 .fx,fval l=fminimax(fun,xo,a,b,aeq,beq,lb,ub)fun為目標函數(shù)的m函數(shù),xo為初值,a,b為不等式約束的系數(shù),aeq,beq為等式約束 系數(shù),lb,ub為x的下限和上限,fval求解的x所對應(yīng)的值。算法原理：序列二次規(guī)劃法。.x,fva

5、l =fgoalattain(fun,xo,goal,weight,a,b,aeq,beqjb,ub)fun為目標函數(shù)的m函數(shù)，xo為初值,goal變量為目標函數(shù)希望達到的向量值，wight 參數(shù)指定目標函數(shù)間的權(quán)重,a,b為不等式約束的系數(shù),aeq,beq為等式約束系數(shù),lb,ub為x的 下限和上限,fval求解的x所對應(yīng)的值。算法原理：目標達到法。四. 多目標線性規(guī)劃的求解方法及matlab實現(xiàn)4.1理想點法在(3)中，先求解廠個單目標問題：minz")j = l,2,廠，設(shè)其最優(yōu)值為z；,稱 z*=(z；,z；, z；)為值域屮的一個理想點，因為一般很難達到。于是，在期望的某種

6、度量 z下，尋求距離z*最近的z作為近似值。一種最直接的方法是最短距離理想點法，構(gòu)造評 價函數(shù)然后極小化（pz（x）,即求解0（z）=刃乙-z；f，min(pz(x)=xed并將它的最優(yōu)解f作為（3）在這種意義下的“最優(yōu)解”。例1：利用理想點法求解max (x) = 一 3兀+ 2x2max f2 (x) = 4 + 3x2s.t +3p <182x, +x2 < 10 x,x2 > 0解：先分別對單目標求解： 求解./；(x)最優(yōu)解的matlab程序為» f= 3；-2; a=2,3；2,l; b=18;10;lb=0;0;» x,fval=linpro

7、g(f,a,b,lb)結(jié)果輸出為：x = 0.00006.0000fval = -12.0000即最優(yōu)解為12. 求解力(兀)最優(yōu)解的matlab程序為» f=-4;-3; a=2,3；2,1j; b=18;10;lb=0;0;» x,fval=linprog(f,a,b,1b)結(jié)果輸出為：x =3.0000 4.0000fval =-24.0000即最優(yōu)解為24.于是得到理想點:(12, 24).然后求如下模型的最優(yōu)解min(pfm = 7/；(x)-122+./2(x)-242s.t 2x + 3x2 < 182x, +x2 <10xpx2 >0mat

8、lab稈序如下：» a=2,3;2,l;b=18;10; x0=l;l;lb=0;0;» x=fmincon(x(-3*x( 1 )+2*x(2)-12)八2+(4*x( 1 )+3*x(2)24)八2)八(l/2)；x0,abhb j) 結(jié)果輸出為：x = 0.5268 5.6488則對應(yīng)的目標值分別為/(x) = 9.刀72 ,(x) = 19.0536.4.2線性加權(quán)和法在具有多個指標的問題屮，人們總希望對那些相對重要的指標給予較大的權(quán)系數(shù)，因而 將多目標向量問題轉(zhuǎn)化為所有目標的加權(quán)求和的標量問題，基于這個現(xiàn)實，構(gòu)造如下評價函 數(shù)，即min z(x) = colzi(

9、x)aed 鋁將它的最優(yōu)解f作為(3)在線性加權(quán)和意義下的“最優(yōu)解”。(召為加權(quán)因子，其選取的方法很多，有專家打分法、容限法和加權(quán)因子分解法等).例2：對例1進行線性加權(quán)和法求解。(權(quán)系數(shù)分別取令=0.5,力2=05)解：構(gòu)造如下評價函數(shù)，即求如下模型的最優(yōu)解。min0.5x(3x, -2x2) + 0.5x(-4xl -3x2)s.t 2兀+ 3x2 < 182x< 10xpx2 >0matlab程序如下：» f=-0.5;-2.5;a=2,3；2,l; b=18;10j; lb=0;0;» x=li叩rog(f,a,bj,n,lb)結(jié)果輸出為：x =0

10、.0000 6.0000則對應(yīng)的目標值分別為/(兀)=12 /(x) = 18 4.3最大最小法在決策的時候，釆取保守策略是穩(wěn)妥的，即在最壞的情況下，尋求最好的結(jié)果，按照 此想法，可以構(gòu)造如下評價函數(shù)，即0(z) = max z.然后求解：min(pz(x) = min max z.(%)xedxed <i<r并將它的最優(yōu)解f作為(3)在最大最小意義下的“最優(yōu)解”。例3：對例1進行最大最小法求解：解：matlab程序如下，首先編寫目標函數(shù)的m文件：function f=myfun 12(x)f(l )=3*x( 1 )-2*x(2);f(2)=-4*x( 1 )-3*x(2);&#

11、187; xo=l;l;a=2,3;2,1 ;b=l& 10;lb=zeros(2,l);» x,fval=fminimax('myfunl2',xo,a,b,ibj)結(jié)果輸出為：x =0.00006.0000fval = -12-18則對應(yīng)的目標值分別為fx) =12,(x) = 18.4.4目標規(guī)劃法appr z(x) > z°(4)并把原多目標線性規(guī)劃(3) minz(x)稱為和目標規(guī)劃(4)相對應(yīng)的多目標線性規(guī)劃。 xed為了用數(shù)量來描述(4),我們在目標空間f中引進點z(x)與z°之間的某種“距離”dz(x),=乙(兀)-z

12、；)2嚴/=!這樣(4)便可以用單目標minpz(x), z件來描述了。xgd例4：對例1對進行目標規(guī)劃法求解：解：matlab程序如下，首先編寫目標函數(shù)的m文件：function f=myfun3(x)f( 1 )=3*x( 1 )-2*x(2);f(2)=-4*x(l )-3*x(2);» goal=l8,10; weight= 18,10; x0=l,l; a二2,3;2,1; b= 18,10; lb=zeros(2,l);» x,fval=fgoalattain('myfun3',xo,goal,weight,a,b, ,1b,)結(jié)果輸岀為：x=

13、0.00006.0000fval= -12-18則對應(yīng)的目標值分別為= 12,(x) = 18.4.5模糊數(shù)學(xué)求解方法由于多目標線性規(guī)劃的目標函數(shù)不止一個，要想求得某一個點作使得所有的目標函 數(shù)都達到各自的最大值，這樣的絕對最優(yōu)解通常是不存在的。因此,在具體求解時，需要采取 折衷的方案，使各h標函數(shù)都盡nj能的大。模糊數(shù)學(xué)規(guī)劃方法可對其各h標函數(shù)進行模糊化 處理，將多h標問題轉(zhuǎn)化為單目標，從而求該問題的模糊最優(yōu)解。/ajv < b 下各個單目標zj = 1,2,廠的最大值z；和 x>0'最小值z）仲縮因子為4=z；-zzz = tx廠工 cgxj> z； dj = 1

14、,2,得到./=!工cikjxj= 1,2, ,mj=2>0,xpx2,x >0式（5）是一個簡單的單目標線性規(guī)劃問題。最后求得模糊最優(yōu)解為：z"=c（x；9,x；t）t.利用（5）式來求解的關(guān)鍵是對伸縮指標的d,確定，/是我們選擇的一些常數(shù)，由于在多 目標線性規(guī)劃中，各子li標難以同時達到最大值z；,但是可以確定的是各子忖標的取值范 圍，它滿足：z7<z,<z；,所以，伸縮因子為/可以按如下取值：jz=z；-z7.例5：對例1進行模糊數(shù)學(xué)方法求解：解：分別求得./；(x),.a(x)在約束條件下的最大值為：z* =(12,24).分別求得土(力，龍(勸在約束

15、條件下的最小值為：z_=(-15,0). 伸縮因子為0=(27,24)然后求如下模型的最優(yōu)解：max z = as.t 3xj + 2 兀2 27 2 n 15+ 3x? 24a a 02x + 3x2 < 182x, + x2 < 10jq,x2,2> 0matlab程序如下：»f=0;0;-l; a=3,-2,27;-4,-3,24;2,3,0;2,l,0; b=15;0;l8;10; lb=0;0;0 » x,fval=linprog(f,a,b,lb)結(jié)果輸出為：x 二 1.02535.3165 0.8354fval =-0.8354于是原多目標規(guī)

16、劃問題的模糊最優(yōu)值為z" =(7.5571,20.0507).五. 結(jié)論多目線性標規(guī)劃是優(yōu)化問題的一種，由于其存在多個忖標，要求各目標同時取得較優(yōu)的值，使得求解的方法與過程都相對復(fù)雜.通過將目標函數(shù)進行模糊化處理，可將多目標問題 轉(zhuǎn)化為單目標，借助工具軟件,從而達到較易求解的目標。the multi-objective linear programming some solutions and matlababstract: solve the multi-objective linear programming basic idea is mostly will multitarg

17、et problem into single objective programming, this paper introduces the method of ideal-point, linear weighted and method, the maximum minimum method, object planning, then give multi-objective fuzzy mathematics method of linear programming of each method, finally, give examples with matlab software

18、 realization.keywords: multi-objective linear programming matlab fuzzy mathwithin a.multi-objective linear programming is multi-objective optimization theory, due to an important part of the contradiction between multiple objectives or not sexual, asks to make public degrees all goals are reaching t

19、he optimal solution is impossible, so multi-objective programming problem often only for its efficient solution (non-inferior solution). currently multi-objective linear programming problem solving methods of efficient solutions ideal-point, linear weighted and method, the maximum minimum method, ob

20、ject planning, however these methods of multi-objective preference information of the determination, the research work processing, etc, this paper also gives less multi-objective linear programming method of fuzzy mathematics.2. multi-objective linear programming modelmulti-objective linear programm

21、ing has two and two more objective function, and the target function and constraints are all linear function, its mathematical model expressed as:(1)constraint conditions for:if (1) type, the only one of the problems for the typical single-objective linear programming. we remember：","the a

22、bove multi-objective linear programming available matrix forms expressed as:constraint conditions: (3)three matlab optimal toolbox common functionsin matlab software, a few special solving the function optimization problems, such as linear programming problems linprog; nonlinear function, let a bind

23、ing fmincon, maximum of fminimax, let the minimization problem fgoalattain multi-objective achieve problems, they call form respectively is:(1) , fval. x = linprog (f, a, b, aeq, beq, lb, ub)f for target function coefficient, a, b for inequality constraints, aeq beq coefficients, for equality constr

24、aint coefficients, lb lower for x, lib fval solution, and lipper limit value of the corresponding x.algorithm principle: the simplex method and improvement methods projection method(2) fval. x, there xo fmincon (=, a, b, and aeq beq, lb” ub)there as objective function for the initial value xo functi

25、on, and maliki, a, b, aeq coefficient of the inequality constraints, beq for equality constraint coefficients, lb lower for x, ub fval solution, and upper limit value of the corresponding x.algorithm based on the principle: k t (kuhn tucker) equation method(3) fvaljx, there xo fminimax (=, a, b, and

26、 aeq beq, lb” ub)there as objective function for the initial value xo function, and maliki, a, b, aeq coefficient of the inequality constraints, beq for equality constraint coefficients, lb lower for x, ub fval solution, and upper limit value of the corresponding x.sequential quadratic programming a

27、lgorithm theory:.(4) fval. x, there xo fgoalattain (= of weight, called goal, a, b, aeq, beq, lb, ub)there as objective function for the initial value xo function, and m. variable is the objective function, called goal desired vector-valued wight parameters, the weight of the specified target functi

28、on rooms for, a, b, aeq coefficient of the inequality constrainls, beq for equality constraint coefficients, lb lower for x, ub fval solution, and upper limit value of the corresponding x. algorithm theory: target methodfou匚 multi-objective linear programming method to solve and matlab4.1 ideal-poin

29、tin (3), solve a single objective problem first, put its optimal: the value of a domain, says ideal points for, because generally difficult to meet. and so, in some measure, expectations for the nearest under as approximate. one of the most direct way is the most short idealpoint, tectonic evaluatio

30、n functionthen minimization, namely the solutionand will it optimal solution as (3) in this sense "optimal solution0.ex 1: using the method of ideal-point solutionsolution: first to solve: single objective respectively(1) solving the optimal solution of the matlab for>>f=3;-2;a= two or th

31、ree; 2, 1; b = 18; 10; lb = 0, 0;> > x, fval = linprog (f, a, b, , u, lb)output 0.0000 6.0000 for: x =fval = - 12.0000namely, the optimal solution is 12.(2) the solution of optimal solution for the matlab> > f = - 4; - 3j; a = two or three; 2, 1j; b = 18; 10; lb = 0, 0;> > x, fval

32、= linprog (f, a, b, , , lb)output 3.0000 4.0000 for: x =fval = - 24.0000the optimal solution is for 24.so get ideal point: (12,24)then ask below model optimal solutionmatlab program is as follows:> > a = two or three; 2, 1; b = 18; 10;x0 = l, l;lb = 0, 0;>>x = fmincon ('( 3 * x (1) +

33、 2 * x (2) 12)人 2 + (4 * x (1) + 3 * x (2) - 24) a 2) a (”2)xo, a, b, , lhis), lboutput 0.5268 5.6488 for: x =the corresponding to the target, respectively.the problem with multiple indexes in, people always hope for those relatively important index gives greater weight coefficient and will thus be

34、more objective vector problem into all of the target of weighted summation of scalar problem, based on this fact, tectonic below evaluation function, namelywill its optimal solution as (3) in the linear weighted and meaning ofnunder the optimal solution11, (for the weighting factor, its selection me

35、thod is very much, have expert scoring method, tolerance method and weighted factor decomposition method, etc.).example 2: for example 1 for linear weighted and method to solve. (weight coefficient were taken,)solution: structure, namely the evaluating function as follows; the optimal solution of th

36、e following models.matlab program is as follows:>>f= - 0.5;- 2.5; a =3; 2, 1 ;b = l 8; 10;lb = 0, 0;>>x = linprog (f, a, b, , lb)output 0.0000 6.0000 for: x =the corresponding to the target, respectively.4.3 maximum minimum methodin decision-making, adopt conservative strategy is safe, n

37、amely in the worst case, seeking the best results, according to this idea, can tectonic below evaluation function, namelythen solving:and will it optimal solution as (3) in the maximum minimum under the meaning of hoptimal solution11.ex 3: for example 1 for the maximum minimum method to solve the:so

38、lution: matlab program is as follows, first writing goal function m files:myfunl2 are f = (x)f (1) = 3 * x (1) - 2 * x (2);f(2) = 4*x(l)3 *x(2);> > xo = 1, 1； a = two or three; 2, 1; b = fl8; 10; lb = zeros (2, 1);> > x, fval = fminimax (' myfunl2 xo, a, b, , his), lboutput 0.0000 6.

39、0000 for: x =fval = 12 to 18the corresponding to the target, respectively.4.4 goal programmingand the original multi-objective linear programming (3) called and goal programming (4) corresponding multiobjective programming.in order to quantify the description (4), we bring in point in target space b

40、etween a certain distance11such (4) can use to describe the single target.example 4: for example 1 to target planning solution:solution: matlab program is as follows, first writing goal function m files:myfun3 are f = (x)f(l) = 3 *x(l ) 2 * x (2);f(2) = -4*x(l)-3*x (2);> > called goal 18,10 =;

41、 weight = 18,10; x0 = 1,1; a = two or three; 2, 1; b = 18,10; lb =zeros (2, 1);> > x, fval = fgoalattain (f myfun3 ； xo, called goal, weight, a, b, , , his), lboutput 0.0000 6.0000 for: x =fval = - 12 to 18the corresponding to the target, respectively.4.5 fuzzy mathematics solutionbecause of m

42、ulti-objective linear programming target function more than one, want to seek a certain point for, make all the objective function is reached their maximum, such absolute optimal solution is usually don't exist. therefore, in a specific problem, need to take a compromise plan, make each target function as far as possible big. fuzzy mathematical programming method for its each can be fuzzed aim function, will multi-objective problem into a single goal for this problem, and the fuzzy optimal solutions.specific means is: seeking first under the constraint condition