[第10讲多目标规划模型]多目标规划模型

引例1：投资问题

某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1，2，...，m。而且一旦对第i个项目投资，就用去ai亿元；而这段时间内可得收益ci亿元。问如何如确定最佳的投资方案？

⎧1对第i个项目投资

xi=⎨

⎩0不对第i个项目投资

约束条件为：⎧⎪

∑⎨

m

⎪⎩xi(1−xi)=0,i=1,2,L,m

最佳的投资方案——投资最少、收益最大投资最少：minf1(x1,x2,L,xm)=收益最大maxf2(x1,x2,L,xm

≤axaiii=1

双目标规划

∑

)=∑

m

axiii=1

m

cxiii=1

引例2：生产问题

某工厂生产两种产品，产品A每单位利润为10元，而产品B每单位利润为8元，产品A每单位需3小时装配时间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润的减去1元，根据最近的合同，厂商每周最少得向用户提供两种产品各30单位。要求:1) 必须遵守合同；2)尽可能少加班；3)利润最大. 问怎样安排生产？每周正常时间生产得A产品数量——x1约束条件为：每周加班时间生产得A产品数量——x2

⎧x1+x2≥30⎪每周正常时间生产得B产品数量——x3

⎪x+x≥30

3

4

每周加班时间生产得B产品数量——x4加班最少

利润最大

⎨

⎪3x1+2x3≤120⎪⎩xi≥0

min3x2+2x4

max10x1+9x2+8x3+7x4

多目标规划的模型

一般形式:

()()() V-minfX,fX,L,fX12pn

X∈R

{}

⎧gj(X)≤0 j=1,2,...,m;

s.t.⎨

⎩hk(X)=0 k=1,2,...,l.

函数fi,gj,hk满足

fi: R→R, gj: R→R, hk: R→R,p≥2

n

n

n

求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式．

多目标规划的基本解法

2. 分层序列法——把多个目标按其重要程度排序，先求出第一个目标的最优解，再在达到此目标的条件下求第二个目标的最优解，依此类推直到最后一个求解结束即得到最优解。

V-minf1(X),f2(X),L,fp(X)

X∈D

}

⇒(1):f1*=minf1(X)X∈D

L

X∈DI{x|f1(X)≤f1*}

{

改进——宽容分层序列法：给前面的

最优值设定一定的宽容值ε>0, 即此可接受的!

(2)f2*=

(p)fp*=

min

f2(X)

fp(X)目标值再差ε也是

X∈DI{x|fj(X)≤fj*,j=1,2,L,p−1}

min

缺点：当前面的问题最优解唯一时，后面的求解失去意义！

多目标规划的基本解法

4.4 “min-max”法(极小极大法)(转化)

此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：⎧⎫

minh(F(X))=min⎨maxfj(X)⎬

X∈DX∈D⎩1≤j≤p⎭

但可方便转化为一个简单非线性规划问题！

令t=maxfj(X)则该规划问题可等价为：

1≤j≤p

⎧mint

X,t⎪⎪

⎨fj(X)≤t,j=1,2,L,p⎪

X∈D⎪⎩

该技巧非常有用，将一个不可微的规划问

题转化为可微的约束规划！

多目标规划的基本解法

理论性结果

以上所有方法所得到的最优解都是有效解(线性加权法当有权系数为零时得到的是弱有效解)!

权系数的确定方法：

专家打分法：多个专家对不同目标打分, 然后计算平均值, 计算各人给分的偏差, 让偏差大的专家发表意见, 并通过充分讨论最终达成共识等等. (而在理论分析时往往选取不同的权系数, 观察结果, 给用户提供方便决策!)

α方法：

⎧∑λfi=β,j=1,2,L,p⎪j=1jj⎨p

⎪∑j=1λj=1⎩

p