多目标规划与数学模型.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 把满足问题中约束条件的解X∈Rn 称为可行解(或可行点)，所有可行点的集 合称为可行集(或可行域)．记为D．即:原问题可简记为定义2 x*是绝对最优解fj(X)≥fj(x*), 任意 X∈D, j=1~ p x*是有效解不存在X∈D , 使得fj(X)≤fj(x*), j=1~ p x*是弱有效解 不存在X∈D , 使得fj(X)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,2……n)可以选择选择 , 现现用数额为额为 M的相当大的资资金作一个时时期的投 资资. 这这n种资产资产 在这这一时时期内购买购买 Si的平均收 益率为为ri, 风险损风险损 失率为为qi, 投资资越分散, 总总的 风险风险 越小, 总总体风险风险 可用投资资的Si中最大的一 个风险风险 来度量. 购买购买 Si时时要付交易费费 (费费率pi), 当购买额购买额 不超过给过给 定值值ui时时, 交易费费按购买购买 ui 计计算. 另外, 假定同期银银行存款利率是r0, 既无交 易费费又无风险风险 (r0=5%). 已知n=4时时相关数据如 下：投资的收益和风险(1998A)Siri(%)qi (%)pi (%)ui (元)S1282.51103S2211.52198 S3235.54.552 S4252.66.5401)试给设计试给设计 一种投资组资组 合方案, 即用给给定 的资资金M, 有选择选择 地购买购买 若干种资产资产 或存 银银行生息, 使净净收益尽可能大, 使总总体风险风险 尽可能小.2)使就一般情况对以上问题进行讨论，并利用 下表数据进行计算:Siriqipi ui S19.6422.1181 S218.5 543.2407 S349.4 606.0428 S423.9 421.5549 S58.1 1.27.6270 S614393.4397 S740.7 685.6178S831.2 33.4 3.1220 S933.6 53.3 2.7457 S1036.8402.9248 S1111.8315.1195 S1295.55.7320 S1335462.7267 S149.45.34.5328 S1515237.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中最大的一个风险来 衡量,即 max{ qixi|i=1，2,…n}2．购买Si所付交易费是一个分段函数, 即交易 费= pimax{ui, xi}; 3．要使净收益尽可能大,总体风险尽可能小, 这 是一个多目标规划模型: 目 标约 束 条 件4. 模型简化：1) 简化总收益函数Q(x) 购买Si所付交易费是一个分段函数, 即交易费= pimax{ui, xi}; 而题目所给定的定值ui(单位:元)相对总投资M很 小, piui更小,可以忽略不计, 这样购买Si的净收益 为(ri-pi)xi2) 简化总体风险函数P(x): 简化后的模型——双目标线性规划模型四、模型求解模型1固定风险 水平，极大化 净收益模型2固定净收 益水平,极小化 风险损失模型3权衡资产风险和预期净收益两方面, 对风 险、收益赋予权重s和1－s(s称为投资偏好系数)模型1 确定风险水平a0,使每一项投资的风险 损失不超过a0M,并极大化净收益，来得到最优 投资组合——把多目标问题转化为单目标问题通常在分析问 题时,需要取多 组不同的风险 水平a0,观察净 收益的变化情 况,以便给出合 理的风险水平 a0.对于1)(n=4),具体的模型为 max 0.05x0+0.27x1+0.19x2+0.185x3+0.185x4 s.t.0.025x1≤a0 0.015x2≤a0 0.055x3≤a0 0.026x4≤a0 x0+1.01x1+1.02x2+1.045x3+1.065x4=1 xi≥0,(i=0,1,2,3,4)Matlab软件求解Matlab中的命令 [x,fval]=linprog(c,A,b,Aeq,beq,lb,ub) 用来求解规划min cTx s.t. A x≤b Aeq x=beq lb≤x≤ub 其中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;右图是目标函数的 最优值随a0变化的 图形. 在a0取值0.006的左 边,目标值增加较快 , 在其右边,目标值增 加较慢,所以取 a0=0.006是一个合 理的选择.理论求解此处的线性 规划约束条 件比较特殊, 可以得到理 论的结果.令(1+pi)xi=yi (xi=yi/(1+pi)),可以将模型 转化为理论求解该模型可以理解为 将数1分解为n+1个 数的和,其中每个数 有一个上界,最终的 目标是使得这n+1个 数的线性组合最大.显然,要求解该模型,只要将目标函数中的价 格系数(ri-pi)/(1+pi)进行排序,价格系数大的, 其变量尽量的大.理论求解不失一般性,假设 d1≥d2≥···≥dn≥d0 (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的理论结果 max 0.05y0+0.2673y1+0.1863y2+0.1770y3+0.1737y4 s.t. y1≤40.4a0,y2≤68a0,y3≤19a0,y4≤40.96a0y0+y1+y2+y3+y4=1, y0,y1,y2,y3,y4≥0. 若40.4a0≥1,则最优解为y1=1,y2=y3=y4=y0=0 若40.4a0 >0.26730.2673时时, ,上述模型无可行解上述模型无可行解. . 在在b b0 0＝＝0.26730.2673时时, ,显然有显然有min min a a=1/40.4=0.02475=1/40.4=0.02475 在在0.2165

注意这里决策 变量为x和a！该模型除了软件求解外,也可 以讨论理论解.误差讨论 在前面的简化过程中,将 max{ui, xi}取为xi,理 由是ui一般比xi小. 根据上面几种模型的理论求解,在有些条件下 ，会出现xi比ui小的情况.比如在模型比如在模型1 1中中, ,中中 间的三条线段的最间的三条线段的最 右端必然对应着某右端必然对应着某 个投资项目的费用个投资项目的费用 很少的情况很少的情况. . 所以实际的图形在所以实际的图形在 三个小段要比左图三个小段要比左图 低一些低一些. .误差讨论比如在模型1中,中间的三条线段的最右端以及 原点的右端必然对应着某个投资项。