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

1、南京邮电大学理学院杨振华引例引例1：投资问题投资问题 某公司在一段时间内有某公司在一段时间内有a(亿元亿元)的资金可用的资金可用于建厂投资。若可供选择的项目记为于建厂投资。若可供选择的项目记为1，2，.，m。而且一旦对第。而且一旦对第i个项目投资，就用个项目投资，就用去去ai亿元；而这段时间内可得收益亿元；而这段时间内可得收益ci亿元。问亿元。问如何如确定最佳的投资方案？如何如确定最佳的投资方案？mixxaxaiimiii,2,1,011 01ix对第对第i个项目投资个项目投资不对第不对第i个项目投资个项目投资约束条件为：约束条件为：最佳的投资方案最佳的投资方案投资最少、收益最大投资最少、收益

2、最大投资最少：投资最少：miiimxaxxxf1211),(min收益最大收益最大 miiimxcxxxf1212),(max双目标规划双目标规划引例引例2：生产问题生产问题 某工厂生产两种产品，产品某工厂生产两种产品，产品A每单位利润每单位利润为为10元，而产品元，而产品B每单位利润为每单位利润为8元，产品元，产品A每每单位需单位需3小时装配时间而小时装配时间而B为为2小时，每周总装小时，每周总装配有效时间为配有效时间为120小时。工厂允许加班，但加小时。工厂允许加班，但加班生产出来的产品利润减去班生产出来的产品利润减去1元，根据最近的元，根据最近的合同，厂商每周最少得向用户提供两种产品各合

3、同，厂商每周最少得向用户提供两种产品各30单位。要求单位。要求:1)必须遵守合同；必须遵守合同；2)尽可能少尽可能少加班；加班；3)利润最大利润最大.问怎样安排生产？问怎样安排生产？0120233030314321ixxxxxxx约束条件为：约束条件为：加班最少加班最少4223minxx 利润最大利润最大432178910maxxxxx 每周正常时间生产得每周正常时间生产得A产品数量产品数量x1每周正常时间生产得每周正常时间生产得B产品数量产品数量x3每周加班时间生产得每周加班时间生产得A产品数量产品数量x2每周加班时间生产得每周加班时间生产得B产品数量产品数量x4多目标规划的模型多目标规划的

4、模型一般形式一般形式:XfXfXfV-pRXn,min 21 .,.,2,1 0;1,2,.,0.lkXhmjXgtskj满足满足函数函数kjihgf,R:RR,h:RR,g:Rfnknjni求目标函数的最大值或约束条件为大于等于求目标函数的最大值或约束条件为大于等于零的情况零的情况，都可通过取其相反数化为上述一都可通过取其相反数化为上述一般形式般形式2 p nkjRXXhXgXD ,0,0|定义定义1 把满足问题中约束条件的解把满足问题中约束条件的解XRn称为可行解称为可行解(或可行点或可行点)，所有可行点的集，所有可行点的集合称为可行集合称为可行集(或可行域或可行域)记为记为D即即:原问题

5、可简记为原问题可简记为 XfXfXfV-pDX,min 21 定义定义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,即

6、即此目标值再差此目标值再差也是可接受也是可接受的的!多目标规划的基本解法多目标规划的基本解法3.功效系数法功效系数法对不同类型的目标函数统一对不同类型的目标函数统一量纲，分别得到一个功效系数函数，然后求所量纲，分别得到一个功效系数函数，然后求所有功效系数乘积的最优解。有功效系数乘积的最优解。XfXfXfV-pDX,min 21 XffXffjDXjjDXj maxminmaxmin1,0)()(minmaxmax jjjjjffXffXdpj,2,1 pjjDXXd1)(max pjjDXXd1)(max或或线性型线性型功效系数法，还有其它类型的方法，功效系数法，还有其它类型的方法，如指数型方

7、法如指数型方法多目标规划的基本解法多目标规划的基本解法4.评价函数法评价函数法这是一种最常见的方法，就这是一种最常见的方法，就是用一个评价函数来集中反映各不同目标的重是用一个评价函数来集中反映各不同目标的重要性等因素，并极小化此评价函数，得到问题要性等因素，并极小化此评价函数，得到问题的最优解。常见的以下几种方法：的最优解。常见的以下几种方法：XfXfXfV-pDX,min 21 XffjDXj min*pj,2,1 pjjjpfXfffhXFh121*)(),()()(minXFhDX 原理：距理想点最近的点作为最优解原理：距理想点最近的点作为最优解!4.1 理想点法：理想点法：定义评价函数

8、：定义评价函数：求解非线性规划问题：求解非线性规划问题：XfXfXfV-pDX,min 21 XffjDXj min0pj,2,1 pjjjjfXfXFh120)()()(minXFhDX 4.2 平方和加权法：平方和加权法：定义评价函数定义评价函数：求解非线性规划问题：求解非线性规划问题：先设定单目标规划的下界先设定单目标规划的下界(想象中的最好值想象中的最好值),即即其中其中j为为事先给定的一组权系数，满足：事先给定的一组权系数，满足：1;,2,1,01 pjjjpj 原理：平方和加权法体现了通常的原理：平方和加权法体现了通常的“自报公自报公议议”原则原则那些强调各自目标重要者预先那些强调

9、各自目标重要者预先给出一个尽可能好的估计，然后给出一个尽可能好的估计，然后“公议公议”给给出一组表明各目标性的权系数，最后求解非出一组表明各目标性的权系数，最后求解非线性规划给出解答。线性规划给出解答。211200)()(pjjjjffXfXFh虚拟目标法虚拟目标法 多目标规划的基本解法多目标规划的基本解法 XfXfXfV-pDX,min 21 pjjjXfXFh1)()()(minXFhDX 4.3 线性加权法：线性加权法：再定义评价函数：再定义评价函数：求解非线性规划问题：求解非线性规划问题：事先按目标函数事先按目标函数f1(X)、.、fp(X)的重要程度给出的重要程度给出一组权系数一组权

10、系数j，满足：，满足：1;,2,1,01 pjjjpj )(RF1f2f*2f*1f,21 ,21 多目标规划的基本解法多目标规划的基本解法 XfXfXfV-pDX,min 21 )(max)(1XfXFhjpj )(maxmin)(min1XfXFhjpjDXDX4.4 “min-max”法法(极小极大极小极大法法)定义评价函数：定义评价函数：求解非线性规划问题：求解非线性规划问题：xf)(1xf)(2xf )(),(max21xfxf*x原理：原理：在最不利的情况在最不利的情况下找出一个最有利的策下找出一个最有利的策略略!悲观主义决策悲观主义决策 多目标规划的基本解法多目标规划的基本解法

11、)(maxmin)(min1XfXFhjpjDXDX4.4 “min-max”法法(极小极大法极小极大法)(转化转化)此非线性规划问题目标函数不可微，不能直接此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：用基于梯度的算法：但可方便转化为一个简单非线性规划问题但可方便转化为一个简单非线性规划问题！)(max1Xftjpj 令令则该规划问题可等价为：则该规划问题可等价为：1 2,min(),X tjtfXt jpXD 该技巧非常有用，将该技巧非常有用，将一个不可微的规划问题转一个不可微的规划问题转化为可微的约束规划！化为可微的约束规划！多目标规划的基本解法多目标规划的基本解法)()()

12、(12XfXfXFh)()(max)(max12XfXfXFhDXDX 4.5 乘除法乘除法考虑两个目标的规划问题：考虑两个目标的规划问题：求解非线性规划问题求解非线性规划问题:则定义评价函数：则定义评价函数：max)(min)(21XfXfDXXfXf ,0)(0)(21，且且1f2f*2f*1f 最优解点最优解点 如如f1(x)为投资总金额，为投资总金额，而而f2(x)为投资后的总收益，为投资后的总收益，则最优结果应是单位投资则最优结果应是单位投资的总收入最大！的总收入最大！多目标规划的基本解法多目标规划的基本解法理论性结果理论性结果以上所有方法所得到的最优解都是以上所有方法所得到的最优解

13、都是有效有效解解(线性加权法当有权系数为零时得到的是弱线性加权法当有权系数为零时得到的是弱有效解有效解)!2019A投资的收益和风险 市场上有市场上有n种资产种资产Si(i=1,2n)可以选择可以选择,现用数额为现用数额为M的相当大的资金作一个时期的投的相当大的资金作一个时期的投资资.这这n种资产在这一时期内购买种资产在这一时期内购买Si的平均收益的平均收益率为率为ri,风险损失率为风险损失率为qi,投资越分散投资越分散,总的风险总的风险越小越小,总体风险可用投资的总体风险可用投资的Si中最大的一个风险中最大的一个风险来度量来度量.购买购买Si时要付交易费时要付交易费(费率费率pi),当购买额

14、当购买额不超过给定值不超过给定值ui时时,交易费按购买交易费按购买ui计算计算.另外另外,假定同期银行存款利率是假定同期银行存款利率是r0,既无交易费又无风既无交易费又无风险险(r0=5%).已知已知n=4时相关数据如下：时相关数据如下：投资的收益和风险投资的收益和风险(2019A)1)试给设计一种投资组合方案试给设计一种投资组合方案,即用给定即用给定的的资金资金M,有选择地购买若干种资产或存银行有选择地购买若干种资产或存银行生息生息,使净收益尽可能大使净收益尽可能大,使总体风险尽可使总体风险尽可能小能小.2)使就一般情况对以上问题进行讨论，并利用使就一般情况对以上问题进行讨论，并利用下表数据

15、进行计算下表数据进行计算:基本假设基本假设：1.投资数额投资数额M相当大相当大,为了便于计算，假设为了便于计算，假设M=1；2.投资越分散，总的风险越小；投资越分散，总的风险越小；3.总体风险用投资项目总体风险用投资项目Si中最大的一个风险来中最大的一个风险来度量；度量；4.n种资产种资产Si之间是相互独立的；之间是相互独立的；5.在投资的这一时期内在投资的这一时期内,ri,pi,qi,r0为定值为定值,不受不受意外因素影响意外因素影响;6.净收益和总体风险只受净收益和总体风险只受 ri,pi,qi影响，不受影响，不受其他因素干扰。其他因素干扰。二、基本假设和符号规定二、基本假设和符号规定符号

16、规定符号规定：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所付交易费是一个分段函数所付交易费是一个分段函数,即

17、交易即交易费费=pi*sgn(xi)*maxui,xi;3要使净收益尽可能大要使净收益尽可能大,总体风险尽可能小总体风险尽可能小,这这是一个多目标规划模型是一个多目标规划模型:0max()sgn()max,niiiiiiiQ xr xpxu x nixqxPii,2,1max)(min 0(sgn()max(,)niiiiiixpxu xM 00 1 2,ixin 目目标标约约束束条条件件4.模型简化：模型简化：00()sgn()max,nniiiiiiiiiiiQ xr xpxu xrpx1)简化总收益函数简化总收益函数Q(x)购买购买Si所付交易费是一个分段函数所付交易费是一个分段函数,即

18、交易费即交易费=pisgn(xi)maxui,xi;而题目所给定的定值而题目所给定的定值ui(单位单位:元元)相对总投资相对总投资M很很小小,piui更小更小,可以忽略不计可以忽略不计,这样购买这样购买Si的净收益的净收益为为(ri-pi)xi2)简化总体风险函数简化总体风险函数P(x):则则令令;,2,1maxnixqii nixqxPii,2,1max)(min nixqtsxPii,2,1,.),(min 简化后的模型简化后的模型双目标线性规划模型双目标线性规划模型 iniiixprxQ 0)(maxnixqtsxPii,2,1 ,.),(min Mxpniii 0)1(00 1 2,i

19、xin 四、模型求解四、模型求解 iniiixprxQ 0)(maxnixqtsxPii,2,1 ,.),(min Mxpniii 0)1(00 1 2,ixin 模型模型1固定风险固定风险水平，极大化水平，极大化净收益净收益模型模型2固定净收固定净收益水平益水平,极小化极小化风险损失风险损失模型模型3权衡资产风险和预期净收益两方面权衡资产风险和预期净收益两方面,对风对风险、收益赋予权重险、收益赋予权重s和和1s(s称为投资偏好系数称为投资偏好系数)iniiixprxQ 0)(maxniMaxqtsii,2,1 ,.0 Mxpniii 0)1(00 1 2,ixin 模型模型1 确定风险水平确

20、定风险水平a0,使每一项投资的风险使每一项投资的风险损失不超过损失不超过a0M,并极大化净收益，来得到最优并极大化净收益，来得到最优投资组合投资组合把多目标问题转化为单目标问题把多目标问题转化为单目标问题通常在分析问通常在分析问题时题时,需要取多需要取多组不同的风险组不同的风险水平水平a0,观察净观察净收益的变化情收益的变化情况况,以便给出合以便给出合理的风险水平理的风险水平a0.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

21、 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.9

22、9 0 0 0 0.026 0.267 0 0.99 0 0 0 0.028 0.26700.020.040.060.080.10.050.10.150.20.250.3aQ iniiixprxQ 0)(max01 2.,iis tq xain Mxpniii 0)1(00 1 2,ixin 1000111 200 1 2max()().,niiiiiiiiniiirpQ yypaps tyinqyMyin 1000111 2100 1 2max()().,niiiiiiiiniiirpQ yypaps tyinqyyin 1000111 2100 1 2max()().,niiiiiiiin

23、iiirpQ yypaps tyinqyyin 0000000000 0525 531 168 360 17374 71 168 361 127 40 17704 2771 127 41 108 40 18633 2751 108 41 40 40 26731 40 4.,/.,/./.,/./.,/./.,/.aaaaQaaaaa 0.0050.010.0150.020.0250.030.050.10.150.20.25模型模型1结果分析：结果分析：3.3.曲线上的任一点都表示该风险水平的最大可曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风能收益和该收益要求的

24、最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资险的承受能力，选择该风险水平下的最优投资组合。组合。2.2.当投资越分散时，投资者承担的风险越小，当投资越分散时，投资者承担的风险越小，这与题意一致。即这与题意一致。即:冒险的投资者会出现集中冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。风险大，收益也大。模型模型2 确定净收益水平下限确定净收益水平下限b0，使每一项投资的净，使每一项投资的净收益不低于收益不低于b0，并极小化风险，来得到最优投资组，并极小化风险，来得到最优投资组合合把多目标问题转化为单目

25、标问题把多目标问题转化为单目标问题 同样在分析同样在分析问题时，取多问题时，取多组不同的收益组不同的收益水平下限水平下限b0，观，观察风险的变化察风险的变化情况，以便给情况，以便给出合理的收益出合理的收益水平下限水平下限b0。00bxpriniii nixqtsxPii,2,1 ,.),(min Mxpniii 0)1(00 1 2,ixin 注意这里决策注意这里决策变量为变量为x和和！00bxpriniii nixqtsxPii,2,1 ,.),(min Mxpniii 0)1(00 1 2,ixin 模型模型3 权衡投资风险和预期净收益两方面权衡投资风险和预期净收益两方面,对风对风险、收益

26、赋予权重险、收益赋予权重s和和1s(s称为投资偏好系数称为投资偏好系数)取多组不同的取多组不同的偏好系数偏好系数s，观，观察风险和收益察风险和收益的变化情况，的变化情况，以便给出合理以便给出合理的偏好系数的偏好系数s。注意这里决策注意这里决策变量为变量为x和和！00 1 2,ixin nixqtsxprssiiniiii,2,1 ,.)1(min0 Mxpniii 0)1(0000000000 0525 531 168 360 17374 71 168 361 127 40 17704 2771 127 41 108 40 18633 2751 108 41 40 40 26731 40 4.

27、,/.,/./.,/./.,/./.,/.aaaaQaaaaa 0000000000 0525 531 168 360 17374 71 168 361 127 40 17704 2771 127 41 108 40 18633 2751 108 41 40 40 26731 40 4.,/.,/./.,/./.,/./.,/.aaaaQaaaaa 0000000000 0525 531 168 360 17374 71 168 361 127 40 17704 2771 127 41 108 40 18633 2751 108 41 40 40 26731 40 4.,/.,/./.,/./

28、.,/./.,/.aaaaQaaaaa 00 1/168.36min0.05(1)(26.5325.53)00.05(1)26.5325.530.05(1)(26.5325.53)/168.3626.5325.53assasssss 1/168.360 1/127.4min0.1737(1)(5.74.7)00.1737(1)(5.74.7)/168.36 5.74.70.1737(1)(5.74.7)/127.45.74.7assassssss 1/127.40 1/108.4min0.1770(1)(5.2774.277)00.1770(1)(5.2774.277)/127.45.2777

29、4.2770.1770(1)(5.2774.277)/108.45.2774.277assassssss 1/108.40 1/40.4min0.1863(1)(4.2753.275)00.1863(1)(4.2753.275)/108.4 4.2753.2750.1863(1)(4.2753.275)/40.44.2753.275assassssss 1/40.40min0.2673(1)00.2673(1)/40.4ass ass 0.20.40.60.81-0.25-0.2-0.15-0.1-0.050.0050.010.0150.020.0250.030.050.10.150.20.250.0050.010.0150.020.0250.030.20.40.60.810.0050.010.0150.020.0250.030.050.10.150.20.250.0050.010.0150.020.0250.030.050.150.20.250.0050.010.0150.020.0250.030.0020.0040.0060.0080.010.0050.010.0150.020.0250.030.00010.00020.00030.00040.00050.0050.010.0150.020.0250.03210-6410-6610-6810-60.00001