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

1、多目标规划南京邮电大学理学院杨振华多目标规划南京邮电大学理学院引例1： 投资问题 某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1，2，.，m。而且一旦对第i个项目投资，就用去ai亿元；而这段时间内可得收益ci亿元。问如何如确定最佳的投资方案？ 对第i个项目投资不对第i个项目投资约束条件为：引例1： 投资问题 某公司在一段时间内有a(亿元最佳的投资方案投资最少、收益最大投资最少：收益最大双目标规划最佳的投资方案投资最少、收益最大投资最少：收益最大双目标引例2： 生产问题 某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元，产品A每单位需3小时装配时

2、间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润减去1元，根据最近的合同，厂商每周最少得向用户提供两种产品各30单位。要求:1) 必须遵守合同；2)尽可能少加班；3)利润最大. 问怎样安排生产？引例2： 生产问题 某工厂生产两种产品，产品A每约束条件为：加班最少利润最大每周正常时间生产得A产品数量x1每周正常时间生产得B产品数量x3每周加班时间生产得A产品数量x2每周加班时间生产得B产品数量x4约束条件为：加班最少利润最大每周正常时间生产得A产品数量多目标规划的模型一般形式:求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式

3、多目标规划的模型一般形式:求目标函数的最大值或约束条件为大于定义1 把满足问题中约束条件的解XRn称为可行解(或可行点)，所有可行点的集合称为可行集(或可行域)记为D即:原问题可简记为定义1 把满足问题中约束条件的解XRn称为可行解(或可行定义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绝对最优解=有效解有效解=弱有效解定义2 x*是绝对最优解fj(X)fj(x*), 任定义3 像集F(R)=F(x)|xD约束集R在映像F之下的值域

4、F*是有效点 不存在FF(D), 使得FF*；F *是弱有效点 不存在FF(R), 使得F0, 即此目标值再差也是可接受的! 缺点：当前面的问题最优解唯 多目标规划的基本解法3. 功效系数法对不同类型的目标函数统一量纲，分别得到一个功效系数函数，然后求所有功效系数乘积的最优解。 多目标规划的基本解法3. 线性型功效系数法，还有其它类型的方法，如指数型方法 线性型功效系数法，还有其它多目标规划的基本解法4. 评价函数法这是一种最常见的方法，就是用一个评价函数来集中反映各不同目标的重要性等因素，并极小化此评价函数，得到问题的最优解。常见的以下几种方法：多目标规划的基本解法4. 评价函数法这是一种最

5、常见的方法 原理：距理想点最近的点作为最优解!4.1 理想点法：定义评价函数：求解非线性规划问题： 原理：距理想点最近的点作为 4.2 平方和加权法：定义评价函数：求解非线性规划问题：先设定单目标规划的下界(想象中的最好值),即其中j为事先给定的一组权系数，满足： 4.2 平方和加权法：定 原理：平方和加权法体现了通常的“自报公议”原则那些强调各自目标重要者预先给出一个尽可能好的估计，然后“公议”给出一组表明各目标性的权系数，最后求解非线性规划给出解答。虚拟目标法 原理：平方和加权法体现了通 多目标规划的基本解法4.3 线性加权法：再定义评价函数：求解非线性规划问题：事先按目标函数f1(X)、

6、.、fp(X)的重要程度给出一组权系数j，满足： 多目标规划的基本解法4.3 多目标规划的基本解法4.4 “min-max”法(极小极大法)定义评价函数：求解非线性规划问题：原理：在最不利的情况下找出一个最有利的策略!悲观主义决策 多目标规划的基本解法4.4 “min-ma 多目标规划的基本解法4.4 “min-max”法(极小极大法)(转化)此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：但可方便转化为一个简单非线性规划问题！则该规划问题可等价为： 该技巧非常有用，将一个不可微的规划问题转化为可微的约束规划！ 多目标规划的基本解法4.4 “min-ma 多目标规划的基本解法4.5

7、乘除法考虑两个目标的规划问题：求解非线性规划问题:则定义评价函数： 最优解点 如f1(x)为投资总金额，而f2(x)为投资后的总收益，则最优结果应是单位投资的总收入最大！ 多目标规划的基本解法4.5 乘除法考虑两个 多目标规划的基本解法理论性结果以上所有方法所得到的最优解都是有效解(线性加权法当有权系数为零时得到的是弱有效解)! 多目标规划的基本解法理论性结果以上所有方法2019A投资的收益和风险2019A投资的收益和风险 市场上有n种资产Si(i=1,2n)可以选择, 现用数额为M的相当大的资金作一个时期的投资. 这n种资产在这一时期内购买Si的平均收益率为ri, 风险损失率为qi, 投资越

8、分散, 总的风险越小, 总体风险可用投资的Si中最大的一个风险来度量. 购买Si时要付交易费 (费率pi), 当购买额不超过给定值ui时, 交易费按购买ui计算. 另外, 假定同期银行存款利率是r0, 既无交易费又无风险(r0=5%). 已知n=4时相关数据如下：投资的收益和风险(2019A) 市场上有n种资产Si(i=1,2n)可以Siri(%)qi (%)pi (%)ui (元)S1282.51103S2211.52198S3235.54.552S4252.66.5401)试给设计一种投资组合方案, 即用给定的资金M, 有选择地购买若干种资产或存银行生息, 使净收益尽可能大, 使总体风险尽

9、可能小.Siri(%)qi (%)pi (%)ui (元)S12822)使就一般情况对以上问题进行讨论，并利用下表数据进行计算:Siriqipi ui S19.6422.1181S218.5543.2407S349.4606.0428S423.9421.5549S58.11.27.6270S614393.4397S740.7685.6178S831.233.43.1220S933.653.32.7457S1036.8402.9248S1111.8315.1195S1295.55.7320S1335462.7267S149.45.34.5328S1515237.61312)使就一般情况对以上问题

10、进行讨论，并利用下表数据进行计算:基本假设：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 -同期银行利率;x

11、i -投资项目Si的资金;Q(x) -总体收益函数;P(x)-总体风险函数；符号规定：三、模型的建立与分析总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n2购买Si所付交易费是一个分段函数, 即交易费= pi*sgn(xi)*maxui, xi; 3要使净收益尽可能大,总体风险尽可能小, 这是一个多目标规划模型: 三、模型的建立与分析总体风险用所投资的Si中最大的一个风险来目标约束条件目标约束条件4. 模型简化：1) 简化总收益函数Q(x)购买Si所付交易费是一个分段函数, 即交易费= pisgn(xi)maxui, xi;而题目所给定的定值ui(单位:元)相对

12、总投资M很小, piui更小,可以忽略不计, 这样购买Si的净收益为(ri-pi)xi4. 模型简化：1) 简化总收益函数Q(x)2) 简化总体风险函数P(x): 2) 简化总体风险函数P(x): 简化后的模型双目标线性规划模型简化后的模型双目标线性规划模型四、模型求解模型1固定风险水平，极大化净收益模型2固定净收益水平,极小化风险损失模型3权衡资产风险和预期净收益两方面, 对风险、收益赋予权重s和1s(s称为投资偏好系数)四、模型求解模型1固定风险水平，极大化净收益模型2固定净收益模型1 确定风险水平a0,使每一项投资的风险损失不超过a0M,并极大化净收益，来得到最优投资组合把多目标问题转化

13、为单目标问题通常在分析问题时,需要取多组不同的风险水平a0,观察净收益的变化情况,以便给出合理的风险水平a0.模型1 确定风险水平a0,使每一项投资的风险损失不超过a对于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)对于1)(n=4),具体的模型为Mathematica软件求解将a0的值从0取到0.1,步长为0.002,用Mathematica软件编程

14、求解:(将问题转化为 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.uMathematica软

15、件求解将a0的值从0取到0.1,步长求解结果当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

16、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从0.026开始,最优值不再变化. x0 右图是目标函数的最优值随a0变化的图形.在a0取值0.006的左边,目标值增加较快,在其右边,目标值增加较慢,所以取a0=0.006是一个合理的选择.右图

17、是目标函数的最优值随a0变化的图形.在a0取值0.006Matlab软件求解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为向量.在某些约束空缺时,可用表示.Matlab软件求解Matlab中的命令x,fval=lfor 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

18、.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;for a0=0:0.002:0.1;理论求解此处的线性规划约束条件比较特殊,可以得到理论的结果.令(1+pi)xi=yi(xi=yi/(1+pi),可以将模型转化为理论求解此处的线性规划约束条件比较特殊,可以得到理论的结果.理论求解该模型可以理解为将数1分解为n+1个数的和,其中每个数有一个上界,最终的目标是使得这n+1个数的线性组合最大.显然,要求解该模型,只要将目标函数中的价格系数

19、(ri-pi)/(1+pi)进行排序,价格系数大的,其变量尽量的大.理论求解该模型可以理解为将数1分解为n+1个数的和,其中每个理论求解不失一般性,假设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理论求解不失一般性,假设(hi=a0(1+pi)/qi)n=4的理论结果max 0.05y0+0.2673y1+0.1863y2+0.1770y3+0.1737y4s.t. y140.4a0,y268a0,y319a0,y

20、440.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+68a00.2673时,上述模型无可行解.在b00.2673时,显然有min a=1/40.4=0.02475在0.2165b00.2673时,min a=(b0-0.1863)/3.275以下讨论略去.模型2是一个线性规划,可以直接用软件求解.借助于模型1的理论模型3 权衡投资风险和预期净收益两方面,

21、对风险、收益赋予权重s和1s(s称为投资偏好系数)取多组不同的偏好系数s，观察风险和收益的变化情况，以便给出合理的偏好系数s。注意这里决策变量为x和a！模型3 权衡投资风险和预期净收益两方面, 对风险、收益赋予模型3的理论求解模型3可以通过计算机软件求解.借助于模型1的结果,我们可以对模型3进行理论求解.在模型1中我们求得了收益函数Q(a)(自变量为风险a0)模型3的理论求解模型3可以通过计算机软件求解.模型3的理论求解因此,求解模型3,只要求解min s a0+(1-s)Q(a0)在a0的每个区间上,sa0+(1-s)Q(a0)都是a0的线性函数,因此只可能在区间的两端取最小值.模型3的理论

22、求解因此,求解模型3,只要求解min s 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模型3的理论求解因此,求解模型3,只要求解min s a0+a01/168.36显然类似地我们可以讨论a0在其它取值下,目标函数的最小值.其结果可以写为右边两个函数的最小值,即min(-0.05+0.05s,-0.2019+0.2076s)a01/168.36显然类似地我们可以讨论a0在其它取值下1/168.3

23、6a01/127.41/127.4a01/108.41/168.36a01/127.41/127.4a01/108.4a01/40.41/40.4a01/108.4a01/40.41/40.4a0针对a0的不同范围,可以画出上述5个s的函数.对这5个函数求最小值,即可得到目标函数的最小值.针对a0的不同范围,可以画出上述5个s的函数.对这5个函数求事实上,目标函数的最小值是5个线性函数的最小值(9个函数中,有4对是对应相等的):-0.05+0.05s, -0.2019+0.2076 s,-0.2106+0.2184 s,-0.2165+0.2257 s,-0.2673+0.2921 s显然很容

24、易求得这5个函数的最小值.其详细数据结果在此略去.与前面两个模型所不同的是,模型3的最优解必然在a0的临界点处取得.事实上,目标函数的最小值是5个线性函数的最小值(9个函数中,误差讨论在前面的简化过程中,将 maxui, xi取为xi,理由是ui一般比xi小.根据上面几种模型的理论求解,在有些条件下，会出现xi比ui小的情况.比如在模型1中,中间的三条线段的最右端必然对应着某个投资项目的费用很少的情况.所以实际的图形在三个小段要比左图低一些.误差讨论在前面的简化过程中,将 maxui, xi取为x误差讨论比如在模型1中,中间的三条线段的最右端以及原点的右端必然对应着某个投资项目的费用很少的情况.所以实际的图形在四个小段要比左图低一些误差讨论比如在模型1中,中间的三条线段的最右端以及原点的右端误差讨论由于M的值很大,上面四个小段的长度很短.而且,如果出现上述的情况,我们简单地将小额资金改为投入到银行,产生的误差应该小于千分之一(具体误差与资金有关).设资金为1千万元,其收益至少为50万,小额资金最多为