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

1、多目标规划,引例1： 投资问题,某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1，2，.，m。而且一旦对第i个项目投资，就用去ai亿元；而这段时间内可得收益ci亿元。问如何如确定最佳的投资方案？,约束条件为：,最佳的投资方案投资最少、收益最大,投资最少：,收益最大,双目标规划,引例2： 生产问题,某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元，产品A每单位需3小时装配时间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润减去1元，根据最近的合同，厂商每周最少得向用户提供两种产品各30单位。要求:1) 必须遵守合

2、同；2)尽可能少加班；3)利润最大. 问怎样安排生产？,约束条件为：,加班最少,利润最大,多目标规划的模型,一般形式:,求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式,定义1 把满足问题中约束条件的解XRn称为可行解(或可行点)，所有可行点的集合称为可行集(或可行域)记为D即:,原问题可简记为,定义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在映像

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

4、方和加权法：,定义评价函数：,求解非线性规划问题：,先设定单目标规划的下界(想象中的最好值),即,其中j为事先给定的一组权系数，满足：,原理：平方和加权法体现了通常的“自报公议”原则那些强调各自目标重要者预先给出一个尽可能好的估计，然后“公议”给出一组表明各目标性的权系数，最后求解非线性规划给出解答。,虚拟目标法,多目标规划的基本解法,4.3 线性加权法：,再定义评价函数：,求解非线性规划问题：,事先按目标函数f1(X)、.、fp(X)的重要程度给出一组权系数j，满足：,多目标规划的基本解法,4.4 “min-max”法(极小极大法),定义评价函数：,求解非线性规划问题：,原理：在最不利的情况

5、下找出一个最有利的策略!悲观主义决策,多目标规划的基本解法,4.4 “min-max”法(极小极大法)(转化),此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：,但可方便转化为一个简单非线性规划问题！,则该规划问题可等价为：,该技巧非常有用，将一个不可微的规划问题转化为可微的约束规划！,多目标规划的基本解法,4.5 乘除法,考虑两个目标的规划问题：,求解非线性规划问题:,则定义评价函数：,如f1(x)为投资总金额，而f2(x)为投资后的总收益，则最优结果应是单位投资的总收入最大！,多目标规划的基本解法,理论性结果,以上所有方法所得到的最优解都是有效解(线性加权法当有权系数为零时得到的

6、是弱有效解)!,1998A 投资的收益和风险,市场上有n种资产Si(i=1,2n)可以选择, 现用数额为M的相当大的资金作一个时期的投资. 这n种资产在这一时期内购买Si的平均收益率为ri, 风险损失率为qi, 投资越分散, 总的风险越小, 总体风险可用投资的Si中最大的一个风险来度量. 购买Si时要付交易费 (费率pi), 当购买额不超过给定值ui时, 交易费按购买ui计算. 另外, 假定同期银行存款利率是r0, 既无交易费又无风险(r0=5%). 已知n=4时相关数据如下：,投资的收益和风险(1998A),1)试给设计一种投资组合方案, 即用给定的资金M, 有选择地购买若干种资产或存银行生

7、息, 使净收益尽可能大, 使总体风险尽可能小.,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的平均收益率, 风险损失 率

8、, 交易费率; 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(单位:

9、元)相对总投资M很小, piui更小,可以忽略不计, 这样购买Si的净收益为(ri-pi)xi,2) 简化总体风险函数P(x):,简化后的模型双目标线性规划模型,四、模型求解,模型1固定风险水平，极大化净收益,模型2固定净收益水平,极小化风险损失,模型3权衡资产风险和预期净收益两方面, 对风险、收益赋予权重s和1s(s称为投资偏好系数),模型1 确定风险水平a0,使每一项投资的风险损失不超过a0M,并极大化净收益，来得到最优投资组合把多目标问题转化为单目标问题,通常在分析问题时,需要取多组不同的风险水平a0,观察净收益的变化情况,以便给出合理的风险水平a0.,对于1)(n=4),具体的模型为

10、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,步长为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;

11、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.050 0.66 0.08 0.13 0.04 0.08 0.002 0.101 0.33 0

12、.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.

13、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 cTx s.t. A xb Aeq x=beq lbxub 其中A,Aeq为矩阵,c,b,beq,lb,ub为向量. 在某些约束空缺时,可用表示.,for a0=0:0.0

14、02: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+

15、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

16、,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+68a00.2673时,上述模型无可行解.,在b00.2673时,显然有min a=1/40.4=0.02475,在0.2165b00.2673时,min a=(b0-0.1863)/3.275,以下讨论略去.,模型3 权衡投资风险和预期净收益两方面, 对风险、收益

17、赋予权重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,

18、则 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个函

19、数中,有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的值很大,上面四个小段的长度很短. 而且,如果出现上述的情况,我们简单地将小额资金改为投入到银行,产生的误差应该小于千分之一(具体误差与资金有关).,设