《多目标规划与数学模型复习课程》由会员分享，可在线阅读，更多相关《多目标规划与数学模型复习课程（72页珍藏版）》请在金锄头文库上搜索。
1、多目标规划,南京邮电大学理学院 杨振华,引例1： 投资问题,某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1，2，.，m。而且一旦对第i个项目投资，就用去ai亿元；而这段时间内可得收益ci亿元。问如何如确定最佳的投资方案？,约束条件为：,最佳的投资方案投资最少、收益最大,投资最少：,收益最大,双目标规划,约束条件为：,加班最少,利润最大,多目标规划的模型,一般形式:,求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式,定义1 把满足问题中约束条件的解XRn称为可行解(或可行点)，所有可行点的集合称为可行集(或可行域)记为D即:,原问题可
2、简记为,定义2 x*是绝对最优解fj(X)fj(x*), 任意XD, j=1 p x*是有效解不存在XD , 使得fj(X)fj(x*), j=1 p x*是弱有效解 不存在XD , 使得fj(X)fj(x*), j=1 p,定义3 像集F(R)=F(x)|xD约束集R在映像F之下的值域 F*是有效点 不存在FF(D), 使得FF*； F *是弱有效点 不存在FF(R), 使得FF.,有效点弱有效点,有效点,弱有效点,基本思想转换为单目标规划问题,多目标规划的基本解法,(1)约束法 (2)分层序列法 (3)功效系数法 (4)评价函数法,多目标规划的基本解法,1. 约束法在多个目标中选定一个主要
3、目标，而对其他目标设定一个期望值，在要求结果不比此期望值坏的条件下，求主要目标的最优值。,多目标规划的基本解法,2. 分层序列法把多个目标按其重要程度排序，先求出第一个目标的最优解，再在达到此目标的条件下求第二个目标的最优解，依此类推直到最后一个求解结束即得到最优解。,缺点：当前面的问题最优解唯一时，后面的求解失去意义！,改进宽容分层序列法：给前面的最优值设定一定的宽容值0, 即此目标值再差也是可接受的!,多目标规划的基本解法,3. 功效系数法对不同类型的目标函数统一量纲，分别得到一个功效系数函数，然后求所有功效系数乘积的最优解。,线性型功效系数法，还有其它类型的方法，如指数型方法,多目标规划
4、的基本解法,4. 评价函数法这是一种最常见的方法，就是用一个评价函数来集中反映各不同目标的重要性等因素，并极小化此评价函数，得到问题的最优解。常见的以下几种方法：,原理：距理想点最近的点作为最优解!,4.1 理想点法：,定义评价函数：,求解非线性规划问题：,4.2 平方和加权法：,定义评价函数：,求解非线性规划问题：,先设定单目标规划的下界(想象中的最好值),即,其中j为事先给定的一组权系数，满足：,原理：平方和加权法体现了通常的“自报公议”原则那些强调各自目标重要者预先给出一个尽可能好的估计，然后“公议”给出一组表明各目标性的权系数，最后求解非线性规划给出解答。,虚拟目标法,多目标规划的基本
5、解法,4.3 线性加权法：,再定义评价函数：,求解非线性规划问题：,事先按目标函数f1(X)、.、fp(X)的重要程度给出一组权系数j，满足：,多目标规划的基本解法,4.4 “min-max”法(极小极大法),定义评价函数：,求解非线性规划问题：,原理：在最不利的情况下找出一个最有利的策略!悲观主义决策,多目标规划的基本解法,4.4 “min-max”法(极小极大法)(转化),此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：,但可方便转化为一个简单非线性规划问题！,则该规划问题可等价为：,该技巧非常有用，将一个不可微的规划问题转化为可微的约束规划！,多目标规划的基本解法,4.5 乘除
6、法,考虑两个目标的规划问题：,求解非线性规划问题:,则定义评价函数：,如f1(x)为投资总金额，而f2(x)为投资后的总收益，则最优结果应是单位投资的总收入最大！,多目标规划的基本解法,理论性结果,以上所有方法所得到的最优解都是有效解(线性加权法当有权系数为零时得到的是弱有效解)!,1998A投资的收益和风险,市场上有n种资产Si(i=1,2n)可以选择, 现用数额为M的相当大的资金作一个时期的投资. 这n种资产在这一时期内购买Si的平均收益率为ri, 风险损失率为qi, 投资越分散, 总的风险越小, 总体风险可用投资的Si中最大的一个风险来度量. 购买Si时要付交易费 (费率pi), 当购买
7、额不超过给定值ui时, 交易费按购买ui计算. 另外, 假定同期银行存款利率是r0, 既无交易费又无风险(r0=5%). 已知n=4时相关数据如下：,投资的收益和风险(1998A),1)试给设计一种投资组合方案, 即用给定的资金M, 有选择地购买若干种资产或存银行生息, 使净收益尽可能大, 使总体风险尽可能小.,2)使就一般情况对以上问题进行讨论，并利用下表数据进行计算:,基本假设： 1. 投资数额M相当大, 为了便于计算，假设M=1； 2. 投资越分散，总的风险越小； 3. 总体风险用投资项目Si中最大的一个风险来度量； 4. n种资产Si之间是相互独立的； 5. 在投资的这一时期内, ri
8、, pi, qi, r0为定值, 不受意外因素影响; 6. 净收益和总体风险只受 ri, pi, qi影响，不受其他因素干扰。,二、基本假设和符号规定,符号规定： Si -第i种投资项目，如股票，债券; ri, pi, qi -分别为Si的平均收益率, 风险损失 率, 交易费率; ui -Si的交易定额; r0 -同期银行利率; xi -投资项目Si的资金; Q(x) -总体收益函数; P(x)-总体风险函数；,三、模型的建立与分析,总体风险用所投资的Si中最大的一个风险来衡量,即 max qixi|i=1，2,n,2购买Si所付交易费是一个分段函数, 即交易费= pi*sgn(xi)*max
9、ui, xi;,3要使净收益尽可能大,总体风险尽可能小, 这是一个多目标规划模型:,目标,约束条件,4. 模型简化：,1) 简化总收益函数Q(x) 购买Si所付交易费是一个分段函数, 即交易费= pisgn(xi)maxui, xi; 而题目所给定的定值ui(单位:元)相对总投资M很小, piui更小,可以忽略不计, 这样购买Si的净收益为(ri-pi)xi,2) 简化总体风险函数P(x):,简化后的模型双目标线性规划模型,四、模型求解,模型1固定风险水平，极大化净收益,模型2固定净收益水平,极小化风险损失,模型3权衡资产风险和预期净收益两方面, 对风险、收益赋予权重s和1s(s称为投资偏好系
10、数),模型1 确定风险水平a0,使每一项投资的风险损失不超过a0M,并极大化净收益，来得到最优投资组合把多目标问题转化为单目标问题,通常在分析问题时,需要取多组不同的风险水平a0,观察净收益的变化情况,以便给出合理的风险水平a0.,对于1)(n=4),具体的模型为 max 0.05x0+0.27x1+0.19x2+0.185x3+0.185x4 s.t.0.025x1a0 0.015x2a0 0.055x3a0 0.026x4a0 x0+1.01x1+1.02x2+1.045x3+1.065x4=1 xi0,(i=0,1,2,3,4),Mathematica软件求解,将a0的值从0取到0.1,
11、步长为0.002,用Mathematica软件编程求解: (将问题转化为 min cTx s.t. Axb,x0) Fora0 = 0, a0=0.1,a0=a0 + 0.002, c = -0.05, -0.27, -0.19, -0.185, -0.185; A = -0,0.025,0,0,0,0,0,0.015,0,0,0,0,0,0.055,0,0, 0, 0,0,0.026,1,1.01,1.02,1.045,1.065,-1,-1.01,-1.02, -1.045,-1.065; b=-a0,-a0,-a0,-a0,-1,1;u=LinearProgrammingc, A, b;
12、 Printa0, u, -c.u,求解结果,当a0从0.026开始,最优值不再变化.,x0 x1 x2 x3 x4 a0 Q(x) 1.00 0 0 0 0 0 0.050 0.66 0.08 0.13 0.04 0.08 0.002 0.101 0.33 0.16 0.27 0.07 0.15 0.004 0.152 0 0.24 0.40 0.11 0.22 0.006 0.202 0 0.32 0.53 0.13 0 0.008 0.211 0 0.40 0.58 0 0 0.01 0.220 0 0.48 0.51 0 0 0.012 0.226 0 0.56 0.43 0 0 0.
13、014 0.232 0 0.64 0.35 0 0 0.016 0.239 0 0.72 0.27 0 0 0.018 0.245 0 0.80 0.19 0 0 0.020 0.252 0 0.88 0.11 0 0 0.022 0.258 0 0.96 0.03 0 0 0.024 0.265 0 0.99 0 0 0 0.026 0.267 0 0.99 0 0 0 0.028 0.267,右图是目标函数的最优值随a0变化的图形.,在a0取值0.006的左边,目标值增加较快, 在其右边,目标值增加较慢,所以取a0=0.006是一个合理的选择.,Matlab软件求解,Matlab中的命令x
14、,fval=linprog(c,A,b,Aeq,beq,lb,ub)用来求解规划min cTx s.t. A xb Aeq x=beq lbxub 其中A,Aeq为矩阵,c,b,beq,lb,ub为向量. 在某些约束空缺时,可用表示.,for a0=0:0.002:0.1; c=-0.05;-0.27;-0.19;-0.185;-0.185; A = 0,0.025,0,0,0; 0,0,0.015,0,0; 0,0,0,0.055,0; 0,0,0,0,0.026; b=a0;a0;a0;a0; Aeq=1,1.01,1.02,1.045,1.065; beq=1; lb=zeros(5,1
15、);x,fval=linprog(c,A,b,Aeq,beq,lb) end;,理论求解,此处的线性规划约束条件比较特殊,可以得到理论的结果.,令(1+pi)xi=yi (xi=yi/(1+pi), 可以将模型转化为,理论求解,该模型可以理解为将数1分解为n+1个数的和,其中每个数有一个上界,最终的目标是使得这n+1个数的线性组合最大.,显然,要求解该模型,只要将目标函数中的价格系数(ri-pi)/(1+pi)进行排序,价格系数大的,其变量尽量的大.,理论求解,不失一般性,假设 d1d2dnd0 (di=(ri-pi)/(1+pi) 则可以得到该模型的解为,(hi=a0(1+pi)/qi) y1=min(1,h1),y2=min(1-y1,h2), yk=min(1-y1-yk-1,hk),y0=1-y1-yn,n=4的理论结果,max 0.05y0+0.2673y1+0.1863y2+0.1770y3+0.1737y4 s.t. y140.4a0,y268a0,y319a0,y440.96a0 y0+y1+y2+y3+y4=1, y0,y1,y2,y3,y40.,若40.4a01,则最优解为y1=1,y2=y3=y4=y0=0 若40.4a01,40.4a0+68a01,则最优解为y1=40.4a0,y2=1-y1=1-40.4a0,y3=y4=y
