5. 多目标规划
多目标规划建模——引例
多目标规划模型
多目标规划的示意图
多目标规划的性质
多目标规划重要算法
引例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*是有效解(Pareto解) 不存在X∈D , 使得fj(X)≤fj(x*), j=1~ p
x*是弱有效解 不存在X∈D , 使得fj(X)<fj(x*), j=1~ p
绝对最优解＝有效解
有效解=弱有效解
定义3 像集F(R)={F(x)|x∈R}约束集R在映像F之下的值域
F*是有效点 不存在F∈F(R), 使得F≤F*；
F *是弱有效点 不存在F∈F(R), 使得F<F；
有效点＝弱有效点
有效点
弱有效点
基本思想——转换为单目标规划问题
多目标规划的基本解法
(1)约束法 (2)分层序列法
(3)功效系数法 (4)评价函数法
1. 约束法——在多个目标中选定一个主要目标，而对其他目标设定一个期望值，在要求结果不比此期望值坏的条件下，求主要目标的最优值。
多目标规划的基本解法
2. 分层序列法——把多个目标按其重要程度排序，先求出第一个目标的最优解，再在达到此目标的条件下求第二个目标的最优解，依此类推直到最后一个求解结束即得到最优解。
缺点：当前面的问题最优解唯一时，后面的求解失去意义！
改进——宽容分层序列法：给前面的最优值设定一定的宽容值ε>0, 即此目标值再差ε也是可接受的!
多目标规划的基本解法
3. 功效系数法——对不同类型的目标函数统一量纲，分别得到一个功效系数函数，然后求所有功效系数乘积的最优解。例如：
线性型功效系数法，还有其它类型的方法，如指数型方法
多目标规划的基本解法
4. 评价函数法——这是一种最常见的方法，就是用一个评价函数来集中反映各不同目标的重要性等因素，并极小化此评价函数，得到问题的最优解。常见的以下几种方法：
原理：距理想点最近的点作为最优解!
理想点法：
定义评价函数：
求解非线性规划问题：
原理：平方和加权法体现了通常的“自报公议”原则——那些强调各自目标重要者预先给出一个尽可能好的估计，然后“公议”给出一组表明各目标性的权系数，最后求解非线性规划给出解答。
平方和加权法：
定义评价函数：
求解非线性规划问题：
先设定单目标规划的下界(想象中的最好值)，即
其中λj为事先给定的一组权系数，满足：
虚拟目标法
多目标规划的基本解法
线性加权法：
再定义评价函数：
求解非线性规划问题：
事先按目标函数f1(X)、...、fp(X)的重要程度给出一组权系数λj，满足：
多目标规划的基本解法
“min-max”法(极小极大法)
定义评价函数：
求解非线性规划问题：
原理：在最不利的情况下找出一个最有利的策略!——悲观主义决策
多目标规划的基本解法
“min-max”法(极小极大法)
此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：
但可方便转化为一个简单非线性规划问题！
则该规划问题可等价为：
该技巧非常有用，将一个不可微的规划问题转化为可微的约束规划！
多目标规划的基本解法
乘除法
考虑两个目标的规划问题：
求解非线性规划问题：
则定义评价函数：
最优解点
如f1(x)为投资总金额，而f2(x)为投资后的总收益，则最优结果应是单位投资的总收入最大！
多目标规划的基本解法
理论性结果
以上所有方法所得到的最优解都是有效解(线性加权法当有权系数为零时得到的是弱有效解)!
权系数的确定方法：
专家打分法：多个专家对不同目标打分, 然后计算平均值, 计算各人给分的偏差, 让偏差大的专家发表意见, 并通过充分讨论最终达成共识等等. (而在理论分析时往往选取不同的权系数, 观察结果, 给用户提供方便决策!)
α方法：
市场上有n种资产Si(i=1,2……n)可以选择, 现用数额为M的相当大的资金作一个时期的投资. 这n种资产在这一时期内购买Si的平均收益率为ri, 风险损失率为qi, 投资越分散, 总的风险越小, 总体风险可用投资的Si中最大的一个风险来度量. 购买Si时要付交易费 (费率pi), 当购买额不超过给定值ui时, 交易费按购买ui计算. 另外, 假定同期银行存款利率是r0, 既无交易费又无风险(r0=5%). 已知n=4时相关数据如下：
40
25
S4
52
23
S3
198
2
21
S2
103
1
28
S1
ui (元)
pi (%)
qi (%)
ri(%)
Si
建模示例——投资的收益和风险(1998A)
1)试给设计一种投资组合方案, 即用给定达到资金M, 有选择地购买若干种资产或存银行生息, 使净收益尽可能大, 使总体风险尽可能小.
2)使就一般情况对以上问题进行讨论，并利用下表数据进行计算:
248
40
S10
457
S9
220
S8
178
68
S7
397
39
14
S6
270
S5
549
42
S4
428
60
S3
407
54
S2
181
42
S1
ui (元)
pi (%)
qi (%)
ri(%)
Si
ui (元)
pi (%)
qi (%)
ri(%)
Si
131
23
15
S15
328
S14
267
46
35
S13
320
9
S12
195
)
31
S11
