多目标规划与数学模型.ppt

多目标规划,南京邮电大学理学院杨振华,引例1：投资问题,某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1，2，.，m。而且一旦对第i个项目投资，就用去ai亿元；而这段时间内可得收益ci亿元。问如何如确定最佳的投资方案？,约束条件为：,最佳的投资方案投资最少、收益最大,投资最少：,收益最大,双目标规划,引例2：生产问题,某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元，产品A每单位需3小时装配时间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润减去1元，根据最近的合同，厂商每周最少得向用户提供两种产品各30单位。要求:1)必须遵守合同；2)尽可能少加班；3)利润最大.问怎样安排生产？,约束条件为：,加班最少,利润最大,多目标规划的模型,一般形式:,求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式,定义1 把满足问题中约束条件的解XRn称为可行解(或可行点)，所有可行点的集合称为可行集(或可行域)记为D即:,原问题可简记为,定义2 x*是绝对最优解fj(X)fj(x*),任意XD,j=1 px*是有效解不存在XD,使得fj(X)fj(x*),j=1 px*是弱有效解 不存在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.约束法在多个目标中选定一个主要目标，而对其他目标设定一个期望值，在要求结果不比此期望值坏的条件下，求主要目标的最优值。,多目标规划的基本解法,2.分层序列法把多个目标按其重要程度排序，先求出第一个目标的最优解，再在达到此目标的条件下求第二个目标的最优解，依此类推直到最后一个求解结束即得到最优解。,缺点：当前面的问题最优解唯一时，后面的求解失去意义！,改进宽容分层序列法：给前面的最优值设定一定的宽容值0,即此目标值再差也是可接受的!,多目标规划的基本解法,3.功效系数法对不同类型的目标函数统一量纲，分别得到一个功效系数函数，然后求所有功效系数乘积的最优解。,线性型功效系数法，还有其它类型的方法，如指数型方法,多目标规划的基本解法,4.评价函数法这是一种最常见的方法，就是用一个评价函数来集中反映各不同目标的重要性等因素，并极小化此评价函数，得到问题的最优解。常见的以下几种方法：,原理：距理想点最近的点作为最优解!,4.1 理想点法：,定义评价函数：,求解非线性规划问题：,4.2 平方和加权法：,定义评价函数：,求解非线性规划问题：,先设定单目标规划的下界(想象中的最好值),即,其中j为事先给定的一组权系数，满足：,原理：平方和加权法体现了通常的“自报公议”原则那些强调各自目标重要者预先给出一个尽可能好的估计，然后“公议”给出一组表明各目标性的权系数，最后求解非线性规划给出解答。,虚拟目标法,多目标规划的基本解法,4.3 线性加权法：,再定义评价函数：,求解非线性规划问题：,事先按目标函数f1(X)、.、fp(X)的重要程度给出一组权系数j，满足：,多目标规划的基本解法,4.4“min-max”法(极小极大法),定义评价函数：,求解非线性规划问题：,原理：在最不利的情况下找出一个最有利的策略!悲观主义决策,多目标规划的基本解法,4.4“min-max”法(极小极大法)(转化),此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：,但可方便转化为一个简单非线性规划问题！,则该规划问题可等价为：,该技巧非常有用，将一个不可微的规划问题转化为可微的约束规划！,多目标规划的基本解法,4.5 乘除法,考虑两个目标的规划问题：,求解非线性规划问题:,则定义评价函数：,如f1(x)为投资总金额，而f2(x)为投资后的总收益，则最优结果应是单位投资的总收入最大！,多目标规划的基本解法,理论性结果,以上所有方法所得到的最优解都是有效解(线性加权法当有权系数为零时得到的是弱有效解)!,1998A投资的收益和风险,市场上有n种资产Si(i=1,2n)可以选择,现用数额为M的相当大的资金作一个时期的投资.这n种资产在这一时期内购买Si的平均收益率为ri,风险损失率为qi,投资越分散,总的风险越小,总体风险可用投资的Si中最大的一个风险来度量.购买Si时要付交易费(费率pi),当购买额不超过给定值ui时,交易费按购买ui计算.另外,假定同期银行存款利率是r0,既无交易费又无风险(r0=5%).已知n=4时相关数据如下：,投资的收益和风险(1998A),1)试给设计一种投资组合方案,即用给定的资金M,有选择地购买若干种资产或存银行生息,使净收益尽可能大,使总体风险尽可能小.,2)使就一般情况对以上问题进行讨论，并利用下表数据进行计算:,基本假设：1.投资数额M相当大,为了便于计算，假设M=1；2.投资越分散，总的风险越小；3.总体风险用投资项目Si中最大的一个风险来度量；4.n种资产Si之间是相互独立的；5.在投资的这一时期内,ri,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)*maxui,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称为投资偏好系数),模型1 确定风险水平a0,使每一项投资的风险损失不超过a0M,并极大化净收益，来得到最优投资组合把多目标问题转化为单目标问题,通常在分析问题时,需要取多组不同的风险水平a0,观察净收益的变化情况,以便给出合理的风险水平a0.,对于1)(n=4),具体的模型为max 0.05x0+0.27x1+0.19x2+0.185x3+0.185x4s.t.0.025x1a00.015x2a00.055x3a00.026x4a0 x0+1.01x1+1.02x2+1.045x3+1.065x4=1xi0,(i=0,1,2,3,4),Mathematica软件求解,将a0的值从0取到0.1,步长为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;Printa0,u,-c.u,求解结果,当a0从0.026开始,最优值不再变化.,x0 x1 x2 x3 x4 a0 Q(x)1.00 0 0 0 0 0 0.0500.66 0.08 0.13 0.04 0.08 0.002 0.1010.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.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,fval=linprog(c,A,b,Aeq,beq,lb,ub)用来求解规划min cTxs.t.A xbAeq x=beqlbxub其中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);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.1737y4s.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=y0=0若40.4a0+68a01,40.4a0+68a0+19a01,最优解为y1=40.4a0,y2=68a0,y3=1-108.4a0,y4=y0=0.以下讨论略去.,可以看出,在1/168.36=0.005940左右,最优值的变化率发生比较大的变化,n=4的理论结果,根据以上的讨论,还可以得出目标函数的最优值随a0的变化的解析函数,最优值随a0变化的图形为,模型1结果分析：,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,模型2 确定净收益水平下限b0，使每一项投资的净收益不低于b0，并极小化风险，来得到最优投资组合把多目标问题转化为单目标问题,同样在分析问题时，取多组不同的收益水平下限b0，观察风险的变化情况，以便给出合理的收益水平下限b0。,注意这里决策变量为x和a！,模型2是一个线性规划,可以直接用软件求解.,借助于模型1的理论求解，我们也可以给出模型2的理论结果.,在b00.2673时,上述模型无可行解.,在b00.2673时,显然有min a=1/40.4=0.02475,在0.2165b00.2673时,min a=(b0-0.1863)/3.275,以下讨论略去.,模型3 权衡投资风险和预期净收益两方面,对风险、收益赋予权重s和1s(s称为投资偏好系数),取多组不同的偏好系数s，观察风险和收益的变化情况，以便给出合理的偏好系数s。,注意这里决策变量为x和a！,模型3的理论求解,模型3可以通过计算机软件求解.借助于模型1的结果,我们可以对模型3进行理论求解.在模型1中我们求得了收益函数Q(a)(自变量为风险a0),模型3的理论求解,因此,求解模型3,只要求解min s a0+(1-s)Q(a0),在a0的每个区间上,sa0+(1-s)Q(a0)都是a0的线性函数,因此只可能在区间的两端取最小值.,模型3的理论求解,因此,求解模型3,只要求解min s a0+(1-s)Q(a0),若a01/168.36,则 sa0+(1-s)Q(a0)=sa0+(1-s)(0.05+25.53a0)=-0.05(1-s)+(26.53s-25.53)a0,a01/168.36,显然,类似地我们可以讨论a0在其它取值下,目标函数的最小值.,其结果可以写为右边两个函数的最小值,即min(-0.05+0.05s,-0.2016+0.2076s),1/168.36a01/127.4,1/127.4a01/108.4,1/108.4a01/40.4,1/40.4a0,针对a0的不同范围,可以画出上述5个s的函数.对这5个函数求最小值,即可得到目标函数的最小值.,事实上,目标函数的最小值是5个线性函数的最小值(9个函数中,有4对是对应相等的):-0.05+0.05s,-0.2016+0.2076 s,-0.2106+0.2184 s,-0.2165+0.2257 s,-0.2673+0.2921 s,显然很容易求得这5个函数的最小值.其详细数据结果在此略去.,与前面两个模型所不同的是,模型3的最优解必然在a0的临界点处取得.,误差讨论,在前面的简化过程中,将 maxui,xi取为xi,理由是ui一般比xi小.根据上面几种模型的理论求解,在有些条件下，会出现xi比ui小的情况.,比如在模型1中,中间的三条线段的最右端必然对应着某个投资项目的费用很少的情况.所以实际的图形在三个小段要比左图低一些.,误差讨论,比如在模型1中,中间的三条线段的最右端以及原点的右端必然对应着某个投资项目的费用很少的情况.所以实际的图形在四个小段要比左图低一些,误差讨论,由于M的值很大,上面四个小段的长度很短.而且,如果出现上述的情况,我们简单地将小额资金改为投入到银行,产生的误差应该小于千分之一(具体误差与资金有关).,设资金为1千万元,其收益至少为50万,小额资金最多为549元,收益小于50,约为200元,所以最多误差为万分之四左右。,误差讨论,如果出现小额投资的情况,求解原来的规划是相当复杂的(即使化为单目标规划,一般也要分情况讨论,求解多个线性规划,而且需要知道M的具体数值)事实上,如果出现有小额投资的情况,不妨将这一部分投资按照一定比例分散到其它投资项目中(投资的方案是我们优化的目标!).这样做的效果是使投资项目减少一个,使得风险略微增加,而受益也略微增加.,左图是取资金为1000元时,简化后的模型与精确的模型的结果比较.红线是精确的模型的结果.蓝色是简化模型的结果.,如果选取1万元以上的资金,两条曲线已看不出区别.,资金为1000元时,简化的模型得到的利润在某些地方比精确的模型要大一些.见左图所示.,资金为1万元时的误差图.数量级为10-4,资金为10万元时的误差图.误差的数量级在10-6.,总结,对于多目标规划,一般的求解方法为:约束法:留下一个作为目标,其余放入约束条件中;加权平均法:对各个目标给出加权系数,得到一个目标函数乘除法(双目标,一个为极大,另一个为极小):将两个目标相除.在本题中,可以将(Q-0.1)/a作为目标函数(求极大,0.1是可以接受的最小利益),求得的最优解为风险为a=0.0594对应的模型1的最优解.,总结,在数学建模中,对于可以用计算机软件解决的问题,应力争从理论上解决.理论分析得到的结果,往往比软件求得的结果有深度,而且更具有说服力.,