留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

基于满意度的不适定二层规划部分合作模型

上一篇

下一篇

朱秀利, 张俊容, 巨兴兴. 基于满意度的不适定二层规划部分合作模型[J]. 西南师范大学学报(自然科学版), 2020, 45(3): 34-39. doi: 10.13718/j.cnki.xsxb.2020.03.006
引用本文: 朱秀利, 张俊容, 巨兴兴. 基于满意度的不适定二层规划部分合作模型[J]. 西南师范大学学报(自然科学版), 2020, 45(3): 34-39. doi: 10.13718/j.cnki.xsxb.2020.03.006
Xiu-li ZHU, Jun-rong ZHANG, Xing-xing JU. A Partial Cooperative Model for Ill-Posed Bilevel Programming Problems Based on Satisfaction Degree[J]. Journal of Southwest China Normal University(Natural Science Edition), 2020, 45(3): 34-39. doi: 10.13718/j.cnki.xsxb.2020.03.006
Citation: Xiu-li ZHU, Jun-rong ZHANG, Xing-xing JU. A Partial Cooperative Model for Ill-Posed Bilevel Programming Problems Based on Satisfaction Degree[J]. Journal of Southwest China Normal University(Natural Science Edition), 2020, 45(3): 34-39. doi: 10.13718/j.cnki.xsxb.2020.03.006

基于满意度的不适定二层规划部分合作模型

  • 基金项目: 重庆市基础前沿研究项目(ctsc2016jcyjA0239);重庆市研究生创新项目(CYS18137)
详细信息
    作者简介:

    朱秀利(1995-), 硕士研究生, 主要从事最优化理论, 算法及应用的研究 .

    通讯作者: 张俊容, 博士, 副教授; 
  • 中图分类号: O221.1

A Partial Cooperative Model for Ill-Posed Bilevel Programming Problems Based on Satisfaction Degree

  • 摘要: 针对传统的求解不适定二层规划问题的部分合作优化模型提出一种新的满意度函数,并以下层满意度函数作为合作系数构造新的部分合作模型.数值算例表明在该满意度函数下,改变最小满意度水平得到的总体满意度较好,说明该满意度下的部分合作模型是可行的.
  • 加载中
  • 表 1  各模型计算结果

    μ1* μ2* F(xy) f(xy) μ(F) μ(f) D(Ff)
    乐观模型 -- -- 0 -4 1 0.040 0.209
    悲观模型 -- -- 5.333 -4.889 0.667 0.111 0.044
    0.7 0.3 3.868 -3.984 0.877 0.619 0.748
    0.7 0.4 4.029 -4.310 0.854 0.745 0.799
    0.7 0.5 3.995 -4.765 0.859 0.847 0.853
    0.7 0.6 4.131 -5.118 0.836 0.895 0.866
    0.6 0.3 3.780 -4.184 0.888 0.704 0.796
    0.6 0.4 3.878 -4.782 0.876 0.850 0.863
    0.6 0.5 4.088 -4.813 0.844 0.855 0.849
    0.6 0.6 4.475 -7.743 0.759 0.993 0.876
    0.5 0.3 3.971 -4.552 0.862 0.807 0.835
    0.5 0.4 3.842 -4.557 0.880 0.808 0.844
    本文模型 0.5 0.5 4.070 -4.884 0.847 0.866 0.856
    0.5 0.6 4.574 -4.839 0.729 0.859 0.794
    0.4 0.3 3.984 -4.301 0.861 0.742 0.801
    0.4 0.4 4.027 -4.489 0.854 0.792 0.823
    0.4 0.5 4.014 -4.207 0.856 0.712 0.784
    0.4 0.6 4.574 -5.027 0.729 0.885 0.807
    0.3 0.3 3.926 -3.823 0.869 0.525 0.697
    0.3 0.4 4.078 -4.374 0.846 0.763 0.804
    0.3 0.5 4.633 -4.605 0.71 0.818 0.764
    0.3 0.6 4.432 -5.428 0.771 0.924 0.848
    下载: 导出CSV
  • [1] 滕春贤, 李智慧.二层规划的理论与应用[M].北京:科学出版社, 2002.
    [2] doi: http://d.old.wanfangdata.com.cn/NSTLQK/10.1287-opre.21.1.37/ BRACKEN J, MCGILL J T.Mathematical Programs with Optimization Problems in the Constraints[J].Operations Research, 1973, 21(1):37-44.
    [3] DEMPE S.Foundations of Bilevel Programming[M].Boston:Kluwer Academic Publishers, 2002.
    [4] 王广民, 万仲平, 王先甲.二(双)层规划综述[J].数学进展, 2007, 36(5):513-529. doi: http://d.old.wanfangdata.com.cn/Periodical/sxjz200705001
    [5] 吴慧, 吕一兵.一类非线性二层多目标规划问题的主要目标法[J].西南大学学报(自然科学版), 2016, 38(1):109-115. doi: http://d.old.wanfangdata.com.cn/Periodical/xnnydxxb201601017
    [6] 周婉娜, 霍永亮, 胡之英.二层随机规划逼近解集上半收敛性的一个充分条件[J].西南师范大学学报(自然科学版), 2015, 40(9):17-22. doi: http://xbgjxt.swu.edu.cn/jsuns/jscnuhhse/ch/reader/view_abstract.aspx?file_no=x201509004&flag=1
    [7] 贾世会.基于满意度的不适定二层规划问题的求解策略及应用研究[D].武汉: 武汉大学, 2013.
    [8] BARD J F.Practical Bilevel Optimization[M].Boston:Springer, 1998.
    [9] doi: http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0232653249/ COLSON B, MARCOTTE P, SAVARD G.Bilevel Programming:A Survey[J].4OR, 2005, 3(2):87-107.
    [10] doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5a8e802ca1d2c877fb658dd5b907dd07 COLSON B, MARCOTTE P, SAVARD G.An Overview of Bilevel Optimization[J].Annals of Operations Research, 2007, 153(1):235-256.
    [11] 郑跃, 万仲平, 袁柳洋.基于二层规划的委托代理协调问题[J].系统工程理论与实践, 2014, 34(1):77-83. doi: http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201401009
    [12] LUCCHETTI R, MIGNANEGO F, PIERI G.Existence Theorem of Equilibrium Points in Stackelberg Games with Constraints[J].Optimization, 1987, 18(6):857-866.
    [13] doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=9fa2835990925f7a1e8907cb4579f312 CAO D, LEUNG L C.A Partial Cooperation Model for Non-Unique Linear Two-Level Decision Problems[J].European Journal of Operational Research, 2002, 140(1):134-141.
  • 加载中
表( 1)
计量
  • 文章访问数:  656
  • HTML全文浏览数:  656
  • PDF下载数:  92
  • 施引文献:  0
出版历程
  • 收稿日期:  2019-01-18
  • 刊出日期:  2020-03-20

基于满意度的不适定二层规划部分合作模型

    通讯作者: 张俊容, 博士, 副教授; 
    作者简介: 朱秀利(1995-), 硕士研究生, 主要从事最优化理论, 算法及应用的研究
  • 西南大学 数学与统计学院, 重庆 400715
基金项目:  重庆市基础前沿研究项目(ctsc2016jcyjA0239);重庆市研究生创新项目(CYS18137)

摘要: 针对传统的求解不适定二层规划问题的部分合作优化模型提出一种新的满意度函数,并以下层满意度函数作为合作系数构造新的部分合作模型.数值算例表明在该满意度函数下,改变最小满意度水平得到的总体满意度较好,说明该满意度下的部分合作模型是可行的.

English Abstract

  • 二层规划问题(bilevel programming problems,BPP)[1-2]是一类具有二层递阶结构的系统优化问题,它包含两个规划问题,即上层规划问题和下层规划问题.由于求解二层规划问题是一个强NP难问题,因此不少学者针对部分特殊的BPP模型提出求解算法.当下层问题的最优解唯一时,上、下层目标一致,得到唯一解,这时称二层规划问题是适定的.当下层问题的最优解不唯一时,通常采用乐观模型、悲观模型等数学模型[3-12].但是乐观模型和悲观模型是两种极端情况,与现实不一定相符,因此有学者在两者之间找到一种中间状态,平衡上、下层完全合作与完全不合作的极端情形,采用合作度将上、下层目标函数联立,创建了部分合作模型[13].由于合作度不满足下层决策需依赖上层决策这一条件,也就是说上、下层依然是分离的,因此文献[7]对具有不适定性的二层规划问题模型采用合作系数建立部分合作模型,并考虑了下层问题的合作度依赖于上层决策这一因素.文献[4]对二层规划模型(BLP)作了比较详细的介绍.文献[5-6]分别对BLP模型的算法、收敛性作了研究.

    部分合作模型已被广泛应用到经济、工业等各个方面,也由用单纯的合作度连接上、下两层目标函数变为用含上层问题的自变量的合作度系数构建部分合作模型.受文献[11]的启发,本文对BLP的部分合作模型进行探讨,定义了一种新的满意度函数,该满意度函数相比文献[7]中的变量少,计算较为简易,并在此满意度函数下构建了新的部分合作模型,最后通过求解算例,验证了模型的可行性.

  • 在本文中,考虑如下的二层规划模型(BLP):

    其中y是下层问题的解,

    其中:x$\mathbb{R}$sy$\mathbb{R}$t分别为上、下层规划问题的决策变量;Ff$\mathbb{R}$s×$\mathbb{R}$t$\mathbb{R}$分别为上、下层规划问题的目标函数;Gg$\mathbb{R}$s×$\mathbb{R}$t$\mathbb{R}$分别为上、下层规划问题的约束函数.定义XY分别为上、下层问题的可行集,即

    对于任意一个xX,BLP问题的下层规划问题的最优解集合称为反应集ψ(x),即

    对任意的xXψ(x)中的元素唯一时,称下层最优解唯一.当存在一点x0X,使得ψ(x0)中的元素不唯一时,那么下层最优解不唯一,则称该二层规划问题不适定.

    对于不适定二层规划问题,存在两种极端情况.一种是乐观模型,即上层决策者认为下层完全配合上层目标,总是将对上层目标函数最有利的解反馈给上层,使得上层目标函数最优,设其乐观解为(x0y0),则有

    另一种是悲观模型,即上层决策者认为下层完全不配合上层目标,总是将对上层目标函数最不利的解反馈给上层,使得上层目标函数最差,设其悲观解为(xpyp),则有

    如果下层与上层的合作情况并非上述两种极端情况,而是采取部分合作的态度与上层合作,即为部分合作模型.定义β为下层问题的合作度,0≤β≤1(β=1为乐观模型,β=0为悲观模型).部分合作模型为:

    上、下层目标函数都是使自身达到最优.当下层反馈给上层的解最不理想时,记F表示F(xy),FL为上层目标函数的容忍极限值.同理,记f表示f(xy),fL为下层目标函数的容忍极限值,即它们分别是下面优化问题的最优值:

    本文利用FLfL定义了上、下层目标函数的满意度,针对部分合作模型,在符合满意度函数所需的条件下,引入了一种新的合作度.该满意度函数变量较少,计算时较为简易,且保证了下层问题的合作度也依赖于上层决策.

  • 定义1  记

    μ(F),μ(F)为目标函数Ff的隶属函数,即上、下层目标函数的满意度,其中0≤μ(F)≤1,0≤μ(F)≤1.当目标函数值越接近决策者的容忍极限值时,μ(F),μ(F)越接近0直至等于0.反之,当目标函数值越远离容忍极限值时,μ(F),μ(F)越接近1直至等于1.

    定义如下的总体满意度函数:

    其中:0≤d(Ff)≤1.随着目标函数值Ff的减小,d(Ff)的值逐渐接近1或等于1.当目标函数值Ff越接近决策者的容忍极限值FLfL时,d(Ff)越接近0直至等于0,因此,利用d(Ff)的值来刻画上、下层函数的总体满意度也是合理的.

    为了顾及下层决策者的利益,本文将下层问题的满意度函数作为部分合作模型中的合作度来构建新的部分合作模型.

    根据上述隶属函数,定义下层问题的合作度如下:

    如果直接以下层满意度作为合作系数来求解不适定二层规划问题,会不同程度地破坏二层规划问题中上层在主体中的结构,最后得到的协调解极大可能会偏向下层.因此,为了保证上层的利益,首先让上层决策者选取适当的最小满意度水平μ1*,在此满意度水平下,下层决策者再选取一个自己可能的满意度水平μ2*,然后构造约束条件,限制xy的范围.于是,以下层满意度作为合作度的部分合作模型构建如下:

    得到如下等价模型:

    需要注意的是,当上层或者下层的理想值和容忍极限值相等时,上、下层满意度的定义没有意义,这时(4)式不能用于求解此类不适定二层规划问题.

    下面的定理保证基于满意度的部分合作模型总存在介于乐观值和悲观值之间的函数值,即在新的部分合作模型中总能找到好于悲观值的函数值.记满足(4)式的约束条件的xy的范围分别为X1Y1.

    定理1 对∀xX1,总有下式成立,

     由于F(x0y0),F(xPyP)分别为乐观模型和悲观模型的最优值,因此有

    故对∀xX1,0≤β(x)≤1,有

    即有

    同理可得:

    即有

    由(5),(6)式可知,定理成立.

    为了使上、下层决策者都可以得到比较满意的结果且不影响二层规划的主从递阶性,给出以下算法.

    首先假设总体满意度区间为[dLdU],其中dLdU分别为悲观模型和乐观模型所对应的总体满意度,若计算出的总体满意度不属于[dLdU],那么上层决策者须调整最小满意度水平μ1*.更新最小满意度μ1*的规则如下:

    1) 若D(Ff) < dL,则上层决策者需要减少自己的最小满意度水平μ1*.

    2) 若D(Ff)>dU,则上层决策者需要增加自己的最小满意度水平μ1*.

    算法1模糊交互式协调算法

    步骤1选取满足式(1),(2)的FLfL

    步骤2上层决策者首先宣布自己可能的最小满意度水平μ1*

    步骤3根据上层决策者宣布的最小满意度水平μ1*,下层决策者给定其可能的最小满意度水平μ2*

    步骤4用MATLAB求解模型(4),得到上、下层函数最优值Ff

    步骤5计算对应函数值的总体满意度D(Ff),如果D(Ff)∈[dLdU],停止运算.否则,根据更新上层决策者的最小满意度规则,得到新的μ1*,转步骤3.

  • 下面通过算例验证以下层满意度函数作为合作系数的部分合作模型的可行性.

    例1

    对∀xX,下层问题的反应集ψ(x)={(y1y2y3)|x1+x2+y1+y2+y3=4}.乐观最优解(x0y0)=(x1x2y1y2y3)=(0,0,0,0,0),乐观值F(x0y0)=0;悲观最优解$\left( {{x_p}, {y_p}} \right) = \left( {{x_1}, {x_2}, {y_1}, {y_2}, {y_3}} \right) = \left( {\frac{4}{3}, \frac{4}{3}, 0, \frac{4}{3}, 0} \right)$,悲观值$F\left( {{x_p}, {y_p}} \right) = \frac{{16}}{3}$.

    上、下层目标函数的容忍极限值为:

    所以下层满意度函数为:

    带入模型(4)得:

    各模型计算结果见表 1.

    通过表 1可以看出,在以本文定义的下层满意度函数作为合作系数的部分模型中,随着上、下层目标函数的最小满意度水平值的不断改变,相应的上、下层函数的函数值也发生改变,而且总能找到比悲观解更好的解,且在μ1*=0.6, μ2*=0.6时总体满意度最高,D(Ff)=0.876.

    在本文研究的BLP模型下,传统的满意度函数为

    其中:FUfU为目标函数的理想值;FLfL为目标函数的容忍极限值.显然,该满意度函数变量较多,计算更为复杂.在传统满意度函数下,求出算例所需变量FUFLfUfL的值,然后通过逐步调整μ1*得到一系列的值,当μ1*=0,μ2*=0.75时获得最大的总体满意度, D(Ff)=0.744,0.744<0.876,由此说明,在本文定义的满意度函数下建立的部分合作模型求得的总体满意度更高,结果更好.

  • 本文针对部分合作模型采取了一种新的满意度函数.该满意度函数变量少,利于求解运算,并以下层满意度函数作为合作系数建立新的部分合作模型.通过改变上、下层问题的最小满意度水平,得到一系列的解,计算相应的总体满意度.算例结果表明在该满意度函数下的部分合作模型是可行的.

参考文献 (13)

目录

/

返回文章
返回