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

多目标规划南京邮电大学理学院杨振华引例引例1：投资问题投资问题 某公司在一段时间内有某公司在一段时间内有a(亿元亿元)的资金可的资金可用于建厂投资。若可供选择的项目记为用于建厂投资。若可供选择的项目记为1，2，.，m。而且一旦对第。而且一旦对第i个项目投资，就用个项目投资，就用去去ai亿元；而这段时间内可得收益亿元；而这段时间内可得收益ci亿元。问亿元。问如何如确定最佳的投资方案？如何如确定最佳的投资方案？对第对第i个项目投资个项目投资不对第不对第i个项目投资个项目投资约束条件为：约束条件为：最佳的投资方案最佳的投资方案投资最少、收益最大投资最少、收益最大投资最少：投资最少：收益最大收益最大双目标规划双目标规划引例引例2：生产问题生产问题 某某工工厂厂生生产产两两种种产产品品，产产品品A每每单单位位利利润润为为10元元，而而产产品品B每每单单位位利利润润为为8元元，产产品品A每每单单位位需需3小小时时装装配配时时间间而而B为为2小小时时，每每周周总总装装配配有有效效时时间间为为120小小时时。工工厂厂允允许许加加班班，但但加加班班生生产产出出来来的的产产品品利利润润减减去去1元元，根根据据最最近近的的合合同同，厂厂商商每每周周最最少少得得向向用用户户提提供供两两种种产产品品各各30单单位位。要要求求:1)必必须须遵遵守守合合同同；2)尽尽可可能能少少加加班；班；3)利润最大利润最大.问怎样安排生产？问怎样安排生产？约束条件为：约束条件为：加班最少加班最少利润最大利润最大每周正常时间生产得每周正常时间生产得A产品数量产品数量x1每周正常时间生产得每周正常时间生产得B产品数量产品数量x3每周加班时间生产得每周加班时间生产得A产品数量产品数量x2每周加班时间生产得每周加班时间生产得B产品数量产品数量x4多目标规划的模型多目标规划的模型一般形式一般形式:求目标函数的最大值或约束条件为大于等于求目标函数的最大值或约束条件为大于等于零的情况零的情况，都可通过取其相反数化为上述一都可通过取其相反数化为上述一般形式般形式定义定义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),使得使得F0,即即此目标值再差此目标值再差也是可接受也是可接受的的!多目标规划的基本解法多目标规划的基本解法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)Siri(%)qi(%)pi(%)ui(元元)S1282.51103S2211.52198S3235.54.552S4252.66.5401)试试给给设设计计一一种种投投资资组组合合方方案案,即即用用给给定定的的资资金金M,有有选选择择地地购购买买若若干干种种资资产产或或存存银银行行生生息息,使使净净收收益益尽尽可可能能大大,使使总总体体风风险险尽尽可可能能小小.2)使使就就一一般般情情况况对对以以上上问问题题进进行行讨讨论论，并并利利用用下表数据进行计算下表数据进行计算:Siriqipi ui S19.6422.1181S218.5 543.2407S349.4 606.0428S423.9 421.5549S58.1 1.27.6270S614393.4397S740.7 685.6178S831.2 33.4 3.1220S933.6 53.3 2.7457S1036.8402.9248S1111.8315.1195S1295.55.7320S1335462.7267S149.45.34.5328S1515237.6131基本假设基本假设：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)-总体风险函数；总体风险函数；三、模型的建立与分析三、模型的建立与分析1.总体风险用所投资的总体风险用所投资的Si中最大的一个风险来中最大的一个风险来衡量衡量,即即2.max qixi|i=1，2,n2购买购买Si所付交易费是一个分段函数所付交易费是一个分段函数,即交易即交易费费=pi*sgn(xi)*maxui,xi;3要使净收益尽可能大要使净收益尽可能大,总体风险尽可能小总体风险尽可能小,这是一个多目标规划模型这是一个多目标规划模型:目目标标约约束束条条件件4.模型简化：模型简化：1)简化总收益函数简化总收益函数Q(x)购买购买Si所付交易费是一个分段函数所付交易费是一个分段函数,即交易费即交易费=pisgn(xi)maxui,xi;而题目所给定的定值而题目所给定的定值ui(单位单位:元元)相对总投资相对总投资M很小很小,piui更小更小,可以忽略不计可以忽略不计,这样购买这样购买Si的净的净收益为收益为(ri-pi)xi2)简化总体风险函数简化总体风险函数P(x):简化后的模型简化后的模型双目标线性规划模型双目标线性规划模型四、模型求解四、模型求解模型模型1固定风险固定风险水平，极大化净水平，极大化净收益收益模型模型2固定净收固定净收益水平益水平,极小化极小化风险损失风险损失模模型型3权权衡衡资资产产风风险险和和预预期期净净收收益益两两方方面面,对对风风险、收益赋予权重险、收益赋予权重s和和1s(s称为投资偏好系数称为投资偏好系数)模模型型1 确确定定风风险险水水平平a0,使使每每一一项项投投资资的的风风险险损损失失不不超超过过a0M,并并极极大大化化净净收收益益，来来得得到到最最优优投资组合投资组合把多目标问题转化为单目标问题把多目标问题转化为单目标问题通通常常在在分分析析问问题题时时,需需要要取取多多组组不不同同的的风风险险水水平平a0,观观察察净净收收益益的的变变化化情情况况,以以便便给给出出合合理理的的风风险水平险水平a0.对于1)(n=4),具体的模型为x0 x1x2x3x4s.tx1a0 x2a0 x3a0 x4a0 x0 x1x2x3x4=1xi0,(i=0,1,2,3,4)Mathematica软件求解将将a a0 0的值从的值从0 0取到取到0.1,0.1,步长为步长为0.002,0.002,用用MathematicaMathematica软件编软件编程求解程求解:(将问题转化为将问题转化为 min c min cT Tx s.t.Axx s.t.Axb,x0)b,x0)Fora0=0,a0=0.1,a0=a0+0.002,Fora0=0,a0=0.1,a0=a0+0.002,c=-0.05,-0.27,-0.19,-0.185,-0.185;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,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,-0,0,0,0,0.026,1,1.01,1.02,1.045,1.065,-1,-1.01,-1.02,-1.045,-1.065;1.02,-1.045,-1.065;b=-a0,-a0,-a0,-a0,-1,1;u=LinearProgrammingc,A,b;b=-a0,-a0,-a0,-a0,-1,1;u=LinearProgrammingc,A,b;Printa0,u,-c.u Printa0,u,-c.u求解结果当a0从开始,最优值不再变化.x0 x1 x2 x3 x4 a0 Q(x)1.00 0 0 0 0 0.66 0.08 0.13 0.04 0.08 0.33 0.16 0.27 0.07 0.15 0 0.32 0.53 0.13 0 0 0.40 0.58 0 0 0 0.48 0.51 0 0 0 0.56 0.43 0 0 0 0.64 0.35 0 0 0 0.72 0.27 0 0 0 0.80 0.19 0 0 0 0.88 0.11 0 0 0 0.96 0.03 0 0 右图是目标函数的最优值随a0变化的图形.在a0取值的左边,目标值增加较快,在其右边,目标值增加较慢,所以取是一个合理的选择.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-ynn=4的理论结果max01234 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+68a0时,上述模型无可行解.在b0时,显然有min a在0.2165b0时,min a以下讨论略去.模模型型3 权权衡衡投投资资风风险险和和预预期期净净收收益益两两方方面面,对对风风险险、收收益益赋赋予予权权重重s和和1s(s称称为为投投资资偏偏好好系系数数)取取多多组组不不同同的的偏偏好好系系数数s，观观察察风风险险和和收收益益的的变变化化情情况况，以以便便给给出出合合理理的偏好系数的偏好系数s。注注意意这这里里决决策策变量为变量为x和和a 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显然类似地我们可以讨论a0在其它取值下,目标函数的最小值.其结果可以写为右边两个函数的最小值,即min(-0.05+0.05s,-0.2016+0.2076s)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作为目标函数(求极大是可以接受的最小利益),求得的最优解为风险为a对应的模型1的最优解.总结在数学建模中,对于可以用计算机软件解决的问题,应力争从理论上解决.理论分析得到的结果,往往比软件求得的结果有深度,而且更具有说服力.