双层规划模型.pdf

该【双层规划模型 】是由【小屁孩】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【双层规划模型 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。双层规划模型--第1页
双层规划法
双层规划的一般形式
设X,Y分别为n,m维欧式空间,XY为X与Y的叉积空间。双层规划模型的
一般形式如下:
(P1)optFx,y
x

(P2)optfx,y(1)
y

,y0
其中,xX,yY分别为上层(P1)与下层(P2)的决策变量;Fx,y与fx,y是
定义于凸区域GXY上取值于实数集的上、下层的目标函数,
Gx,ygx,y0:gx,y为XY的实函数。令Sx存在y,使x,yG,
称为允许集,xS为允许元。
S,满足下层目标函数及约束条件
的最优解,可以表示为:
xArgoptfx,y:gx,y0(2)
y
此时,若x为单点集,即存在唯一的yyxx与之相对应,称它为下层
对上层的反馈函数(这里我们假设yyxx的唯一性,即要求对每一xS,
存在唯一的yx,但一般讲这是不必要的。如果不唯一,这时yx就成为数集,
yyx就成为的x反馈“集”函数。本文不再讨论)。这个问题称为下层规划问
题(P2)。可以看出,下层的决策y是依赖于上层决策x的。对每一上层决策xS,
满足上层目标函数的最优解可以表示为:
optFx,yx:gx,y0
x
(3)

若存在xS,使得Fx,yxoptFx,yx,称x,y为双层规划的最优解。
x
即:
双层规划模型--第1页
双层规划模型--第2页

Fx,yxoptFx,yxoptFx,Argoptfx,y
xxy
综上所述,双层规划问题是由两个单一规划问题(P1)、(P2)组成的决策变量
相互关联的如下规划问题:
(P1)optFx,y
x
其中yyx如下决定

(P2)optfx,y(4)
y

,y0
双层规划问题可以有效地应用于管理部门来组织生产,既充分发挥生产部门
的潜力又能得到宏观控制,达到持续、稳定、健康的发展。下面就文章开始的一
个以效益兼具公平性为双层目标的双层规划问题建立双层规划模型。
分配—选址模型
总公司下面有N个分公司,每一个分公司记为ii1,,N,经过多因素分
析后,在第jj1,,M个城市中,初步确定备选地址,标号为kk1,,L。
已知第i个公司所管辖的第j个城市选择第k个地址后的成本与收益分别为c,
ijk
w(可以用货币单位或者其他数量折算,见表1)。规定每一城市至少要选建一
ijk
个超市,即在每一城市的所有备选点中至少要选一个。对于下层的每一分公司来

选择合适的备选点k。使得分公司的效益最大而对于位于上层的总公司来说,就
是要考虑如何分配专项投资资金T,即如何决策资金分配向量
N
S,S,,S,ST,使得资金的分配最为“公平合理”详细分析如下:
12Ni
i1
一方面,对于每一个分公司ii1,,N,根据总公司所分配的投资额度S,
确立以效益最大为目标的下层规划问题(P2),即:给定i,满足(5)。其中,目标
函数表示第个i分公司在所管辖城市j中通过选择合适的备选点k而获利最大,
反映了下层决策者对所分配资金的最佳“使用”:第一个约束条件表示第i个分
双层规划模型--第2页
双层规划模型--第3页
公司为筹建各超市所投入的总成本不低于从总公司所获得的资金分配;第二个约
束条件表示在第j个城市中至少要保证筹建一个超市;决策变量x1表示第i
ijk
个分公司在第j个城市选择第k个备选点。x0表示第i个分公司在第j个城
ijk
市中第k个备选点未被选中。
ML
maxxw
ijkijk
j1k1
ML
xcS,
ijkijki
j1k1
L
(P2)St.x1,(5)
ijk
k1
x0,x0or1,
ijkijk
j1,2,,M,k1,2,,L
S,S,,S
12N
反映出上层对下层分公司资金分配的公平性(即如何以“公平合理”为目标)。利
用遗憾值函数,作为上层决策者的目标函数。这里我们虽也用minmaxrminr
ii
ii
作为目标函数,但给予了新的解释,即目标函数表示公司间的差异最小化,称为
公平指数。原因如下:任何资金T的一个分配方案,都会给各分公司带来或多或
少的遗憾。即分公司本能达到而因资金不充分未能实现的效益。如果一个资金分
N
配方案S,S,,S,ST,能使N个分公司留下的遗憾值。即不满意程度
12Ni
i1
。可以用如下规划问题表示:
minmaxrminr
ii
ii
N
ST,
(P1)St.i(6)
i1S0
i
其中:
MLMLML
rwxw/w
iijkijkijkijk
j1k1j1k1j1k1
i1,2,,N
双层规划模型--第3页
双层规划模型--第4页
(7)
目标函数是分公司中具有最大遗憾值与最小遗憾值的差。称为差异化,总公
司的目标就是寻求合理的资金分配方案S,S,,S,使差异化最小。下面给出
12N
此双层规划模型的算法。
分配—选址模型的求解步骤
按上述双层规划的定义,分配一选址模型的求解可以按以下几步进行。
(1)给出分公司及所管辖城市拟建超市的各备选点的成本与收益(见表1)。
(2)对于总公司的每一投资分配决策SS,S,,S,分公司ii1,,N根
12N
据投资S来寻找回报最大的备选点(xS1),并计算出该分公司在投资分配
iijki
S下的遗憾值rS,见表2。
iii
双层规划模型--第4页
双层规划模型--第5页
(3)根据分公司的遗憾程度,调整上层决策,从而经过若干轮上、下层的互
动与协调,最终确定一资金分配向量
N
SS,S,,SS,S,,SST,使差异化
12N12Ni
i1

maxrSminrS最小,即
iiii
ii
minminrSmaxrS
iiii
S,,Sii
1N
上述步骤可以用逐次逼近法来实现。逐次逼近法的思想是先在可行域中取一
个初值。。
分配—选址问题算例
设总公司现有总数为T19的资金。要分配给下属的三个分公司,每个分公
司管辖二个城市,
资后的收益与成本见表4。依上述计算步骤及表3,可得如下结果,见表58。
双层规划模型--第5页
双层规划模型--第6页
表4分公司拟在所管辖城市筹建超市的成本与收益
双层规划模型--第6页
双层规划模型--第7页
注:每一分公司根据不同数目的投资,寻求回报最大的决策变量和收益值,
见表5。如投资在范围[3,4]中,实际作用为3,小数部分投资不可能产生新的备
选点建设,自然也不产生效益。
双层规划模型--第7页
双层规划模型--第8页
双层规划模型--第8页