文档介绍：该【双层规划模型 】是由【guoxiachuanyue010】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【双层规划模型 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。双层规划法
双层规划的一般形式
设X,Y分别为n,m维欧式空间,XxY为X与Y的叉积空间。双层规划模型的一般形式如下:
(P1)optF(x,y)
x
(P2)optf(x,y)(1)
y
(x,y)<0
其中,xeX,yeY分别为上层(Pl)与下层(P2)的决策变量;FG,y)与fG,y)是
定义于凸区域G匸XxY上取值于实数集的上、下层的目标函数,
匕,y)g(x,y)<°}:g(x,y)为XxY的实函数。令S=存在y,使C,y)eg!
称为允许集,xeS为允许元。
,满足下层目标函数及约束条件
的最优解,可以表示为:
2)
屮(x)=Argoptf(x,y):g(x,y)<0)
y
此时,若屮O为单点集,即存在唯一的y=y(x)e屮G)与之相对应,称它为下层
xeS,
对上层的反馈函数(这里我们假设y=yG鼻屮G)的唯一性,即要求对每
存在唯一的yG),但一般讲这是不必要的。如果不唯一,这时yG)就成为数集,y=yG)就成为的x反馈“集”函数。本文不再讨论。这个问题称为下层规划问
题(P2)。可以看出,下层的决策y是依赖于上层决策x的。对每一上层决策xeS,
满足上层目标函数的最优解可以表示为:
(3)
opt^F(x,y(x)):g(x,y)<0)
若存在x*eS,使得FC*,y(x*》=opt^F(x,y(x))},称C*,y*)为双层规划的最优解。
x
即:
F,y》二optF(x,y(x))二optFx,Argoptf(x,y)
综上所述,双层规划问题是由两个单一规划问题(Pl)、(P2)组成的决策变量相互关联的如下规划问题:
(P1)optF(x,y)
x
其中y=yG)如下决定
(P2)optf(x,y)(4)
y
(x,y)<0
双层规划问题可以有效地应用于管理部门来组织生产,既充分发挥生产部门的潜力又能得到宏观控制,达到持续、稳定、健康的发展。下面就文章开始的一个以效益兼具公平性为双层目标的双层规划问题建立双层规划模型。分配—选址模型
总公司下面有N个分公司,每一个分公司记为i(i=1,…,N),经过多因素分析后,在第j(j=1,…,M)个城市中,初步确定备选地址,标号为k(k=1,…,L)。已知第i个公司所管辖的第j个城市选择第k个地址后的成本与收益分别为c,ijkw(可以用货币单位或者其他数量折算,见表1)。规定每一城市至少要选建一
ijk
个超市,即在每一城市的所有备选点中至少要选一个。。使得分公司的效益最大?而对于位于上层的总公司来说,就是要考虑如何分配专项投资资金T,即如何决策资金分配向量
(S,S,…,S)£S<T,使得资金的分配最为“公平合理”?详细分析如下:
12Ni
i=1
一方面,对于每一个分公司i(i=1,…,N),根据总公司所分配的投资额度S,
确立以效益最大为目标的下层规划问题(P2),即:给定i,满足(5)。其中,目标函数表示第个i分公司在所管辖城市j中通过选择合适的备选点k而获利最大,反映了下层决策者对所分配资金的最佳“使用”:第一个约束条件表示第i个分公司为筹建各超市所投入的总成本不低于从总公司所获得的资金分配;第二个约束条件表示在第j个城市中至少要保证筹建一个超市;决策变量x=1表示第iijk
个分公司在第j个城市选择第k个备选点。xijk二0表示第i个分公司在第j个城市中第k个备选点未被选中。
ML
max乙乙x
ijk
j=1k=1
w
ijk
(P2)
艺另xc<S,
ijkijki
j=1k=1
匚n1,
ijk
x-0,x=0or1,
ijkijk
、j=1,2,…,M,k=1,2,…,L
(5)
(S,S,…,S)
12N
反映出上层对下层分公司资金分配的公平性(即如何以“公平合理”为目标)。利
用遗憾值函数,作为上层决策者的目标函数。这里我们虽也用minmaxr-minr?iiii
作为目标函数,但给予了新的解释,即目标函数表示公司间的差异最小化,称为
公平指数。原因如下:任何资金T的一个分配方案,都会给各分公司带来或多或
少的遗憾。即分公司本能达到而因资金不充分未能实现的效益。如果一个资金分
配方案(S,S,…,S)£s<T,能使N个分公司留下的遗憾值。即不满意程度
12Ni
i=1
差距最小.
显示此项资金分配的公平性。可以用如下规划问题表示:
minmaxr-minr
iiii
6)
7)
(pi)st.£Si<T,
i=1
iS>0
i
其中:
r=^£w-艺艺xw]/艺艺w
iijkijkijkijk
'j=1k=1j=1k=1丿j=1k=1
i=1,2,…,N
目标函数是分公司中具有最大遗憾值与最小遗憾值的差。称为差异化,总公
司的目标就是寻求合理的资金分配方案(S,S,…,S),使差异化最小。下面给出
12N
此双层规划模型的算法。
分配一选址模型的求解步骤
按上述双层规划的定义,分配一选址模型的求解可以按以下几步进行。
(1)给出分公司及所管辖城市拟建超市的各备选点的成本与收益(见表1)。
表1分公司及所管辎城市拟建超市的各备选点拘成本与收益
分公司
一
I址地选备H..L
-
备„
-色备L
戡一
*威
一
益
_r
■
本成
盍
It
r1
z
6
5
R
L
CI
L
2
1
2
2
2
12w
3L
1C
L
2
TJt
-ir
k-
-Jw
2
-
2u
L.
万
C1
L-J
ML
Iw
2IMcl
2
w一
LflC
L
M
F—
3U
“・
IK
2
mcl
一!
nl
iw
2t2c
2
2w
F
L
02C
2d!rl!-7
2
2
2
2
2
2
22w
L
2
2C
3LI
1-rr
I
&c
IK
c
2/2
L
L
2M
MiC2
1i
3
M
C2-
2M
2
U
*卜
亠
-
■
■
■
-
-」
-L一一_一•
•
V
一一
□
■-
L—_
-
-
11
VI
•
VI
f
Nn—
PL
-
-
--
LmlN
N
1N
11
21
Nw
2
2CN
22
N
L
2N
C
2L
呵
.1-
nWJw
2
2町
LW
u
NM
Nc
2
M一
CN
2
M「W一
U
(2)对于总公司的每一投资分配决策S=(S,S,…,S),分公司i(i=1,…,N)根
12N
据投资S来寻找回报最大的备选点(x(S)=1),并计算出该分公司在投资分配iijki
S下的遗憾值r(S),见表2。
iii
表2第i亍公司获再投资s,后的最大收益及遗憾值
第f分眩
■
Ha屈歸
^i1L(Si>
■>
■1
fl;%%
H>-1
—£左%W左左吟
;»tJut上诃*
(3)根据分公司的遗憾程度,调整上层决策,从而经过若干轮上、下层的互
动与协调,最终确定一资金分配向量
S*,S*,…,S丄[(S
12N
,S,…,S)兰S<T
12N'i
i=1
,使差异化
(S)
maxr£*丿一
ii
i
小,即
minr'S*
i(i
minminr(S)-maxr(S/
©…,Sn)°iiii'
上述步骤可以用逐次逼近法来实现。逐次逼近法的思想是先在可行域中取一个初值。。
分配一选址问题算例
设总公司现有总数为T二19的资金。要分配给下属的三个分公司,每个分公司管辖二个城市,。依上述计算步骤及表3,可得如下结果,见表5-8。
表3备分公則初始投进值、收益值及遗矗值表
-分公司
城甫
1
备选
点2
备选点L
1
I投资
£
「分公甬遗燃値
r\
1
IE
12
U
1M
曲
111
ui
IMI
112
122
仇
IM2
UL
12L
1JL
1ML
SKljlCMl
MAtL
U-为切用廿Jf%
2
21
22
打
2M
111
m
缈
2U
222羽2M2
1
211-22L輕3ML
»石|切1
1戶1
1
M
2乜1怜」
M,tft
{—工乜叫"工工叫
J^ijalf
・・・「|
—
^4>l
NJ
N2
Ni
N
M
筋
FO1即NM1
Nii
NM2
■1
ML禅
严1
乙工单1W巒
护E
MML\
°-Xr叫J迟工%>1户甲
表4分公司拟在所管辖城市筹建超市的成本与收益
T
备
2点选备
5~一一一
□
S
12
.5
d
33-
一
32
-..
i2
r2
5
0,1
R
□
12
31
O
!412
强5分公司1投资久后眾大收益及遗憾值
Si
xau
Xi壮
X⑵
Xg
巔大収菰
^(Si)
[)
无可行解
[)
I
o:
1
0
23
[)
1
0
0
1
3
[5,6)
0
1
1
0
拠
1
11
I
1
<0
55
[7向
1
1
0
1.
6
[8,9)
Q
1
I
1
043
[9
1
1
I
1
」
0
注:每一分公司根据不同数目的投资,寻求回报最大的决策变量和收益值,见表5。如投资在范围[3,4]中,实际作用为3,小数部分投资不可能产生新的备选点建设,自然也不产生效益。
表右分公司2投资禺启最大搜益及遗變值
s2
Xgi]
X陀
^221
^222
.益
1於J
无可■疔解
五4),
1
0
0
1
r空
?'
0
1
0
1
6
[5,6)
1
1
0
i』
6-5
0J2
[6,7)
0
1
1
1
7
0,07
1
1
1
!
0
表7第3令分公司投凌西后巖大收益及遗撼值
X”
^Jl2
◎
^22
毘大吹
n<Si)
无可行解
(4,5)
!--
11
0
1
0
I-4
(5,6)
0
1
1
0J
5-5
0,48'
[6,7)1
1
0
11
1
”7
P,8)
10
\
1
&,
[)
0
1
1
1-
;
0J9
19,10)
0
i
I
:1
醯
0A9
[10
1
1
1
1
G
表呂上层投资分配向量,总投資额及各公司差异化值
T=Sj+
Si
務
3
3
4
0167
a53
(U4
[[
4
3
4
aeo
ass
&09为最小
h
|3
4
4
Q62
047
1
'a
3
5
ftff7
ai?
‘12
4
3
5
ftffl
0•唸殛小
4
4
4
0l60
0J62
0l42
5
3
4
040
Q53
13
5
3
5
23为慕小
4
3
6
aeo
Ol53
033
027
14「
5
4
5
cu«
0,28
5
3
6
Q53
033
Q20为银小
15
5
4
6
020
033
Q2O为最小
6
4
5
027■:
ft20
Q48
緒
5
3
.7
ft40
0,53
16
6
4
6
027
G.^>
5
4
7
0-40
0,20
0J9
020
17
6
4
7
<E7
a19
aos为最小
7
4
6
0,20
0^0
0J5
L8
7
4
7
020
049
0,01
19
8
4
7
ai3
ai?
7
5
7
ft20
fti9
QC7
7
4
8
020
aao