论文研究-线性一二次双层规划问题.pdf

所需积分/C币:10 2019-09-20 15:39:23 574KB .PDF
6
收藏 收藏
举报

论文研究-线性一二次双层规划问题.pdf,  本文利用对偶理论和Kuhn-Tucker条件来研究线性一二次双层规划问题, 给出一些二层规划解的最优性条件和一个求解二层规划解的算法。这些最优性条件丰富了非线性多层规划的理论, 而其求解算法为求解实际问题提供了有力的工具。一些数值试验结果将在本文未给出, 这些结果表明算法对于小规模问题的求解是相当有效的。
第4期 线性一二次双层规划问题 max F(x,y) (2) Ax+By-r≤0 (22) By) (2.3 ey+20,x+d=B (24) ≥0 证明先证必要性。若(xy)为LQP的最优解,则由定义3知,(xy)S',且对任意的(x, y)∈S都有a^x+by≥ax+b'y 由于Q1是负定的,所以对每个容许的x,下层规划问题(FP)有唯一的解y=o(x)(如果有最优 解存在的话),且Kuhn- Tucker充分必要条件成立。因此,(xy)eS'的充分必要条件是存在o≥0使得 (xy,O)满足(22)~(2.5) 于是,存在≥0使得(x,y,)满足(22)~(25) ax+by"≥a'x+by,对任意(xy,)满足(22)-(25) 所以,(x,y,)为P2)的最优解 再证充分性。若存在≥0使得(x,y,0)为(P2)的解,则(xy,)满足(22)~(25)且对任意 的满足(22)~(2.5)的(x,y,),都有a1x+by‘≥ax+b1y 由前面讨论可知,若存在≥0使得(xy,o)满足(22)~(25),则(x,y)∈S。所以ax+by max a x+by。由定义3知,(xy)为(LQP)的最优解。 证毕 对于Q≥0,记S(ω)={(x,y)Ax+By≤r,D(4x+By-r)=0,291y+2Q2x+d=Bo)}, 则(P2)与下列max-max问题 (P3) max max F(x,y)=a'x+b 冋解。 (P)的内层极值同题是 max F(x,y)=ax+b'y (3,1) Ax+By≤r 3.2) (Ax+By-r)=0 (3.3 2, x+ 20 y+ d= B 因为≥0,由(32)、(3.3)可知:约束u(Ax+By-r)=0与o(Ax+By)≥'r是等价的。所以 P的对偶规划为 (D) ,142)r+u,(B'c min (u A+23Q2=a )B+2u3Q1=b M,≥0 ≥0 其中1ER",2∈R,,∈R 于是有如下最大最小问题 P4) nax in (u 2)r+w,(B )A+23Q (42) ω)B+2u3Q1=b (4.3) 4 系统工程理论与实践 1994年7月 ≥0 ≥0 ≥0 4 对于≥0,记S(o)={(m123)(n1-v2)A+2u3Q2=a,(1-u20)B+2n3Q1=b M,≥0,以,≥0}。于是,问题(P)可简写为 (P max (u, -u, o)r+u,(B0-d)y 对于给定的ω≥0,假设S(ω)≠Φ且问题(P)的最优解存在,则问题①D)存在最优解。由线性规划 的对偶定理、二者的最优目你函数值相等。 以上仅对如上假设考虑(P3)(或(P4))的内层极值问题,我们可证如下对偶关系。 定理2设(x,y,O),(1M22o)分别是间题(P)和(P4)的可行解,则 (u, -u,o)r+u(B0-d>a'x+b'y 证明(42和43两边分别右乘x,y后相加得 1-"2m)(Ax+By)+"3(2Q2x+2Q1y)=ax+by 所以(u 1-u,)(Ax+ By-r)+(u,-u2o)r+u(222 -x+2Q,y+d-BG)+u,(B-d) 注意到o(Ax-B1-)=0,u1(Ax+By-r)≤0和u32(2Q2x+2Q1 y db a)=0, u-u,o)r+u3(Bod)>ax+by 证毕 定理3设(xy,)),(41,M2,3,D)分别为问题(P)和(P4)的可行解,则它们分别是问题 P3)(P)的最优解的充分必要条件是: ()r+u,"(B d-a x +b (n1-a2))(4x+By-)+3(2Q2x+2Q1y+d-B)≤0,对任意(x,y)S 证明先证必要性。由(P)和(D)的对偶性,对于每个≥0,有 Inin (u, -u2w)r+u(Bw-d)]=max a x+bv3 所以 max min (u, -u, o)r+u,(B-d);=max max a'x+byl 因此,如果[u1,2,a3,D)和(x,v,)分别是间题(P)和(P3)的最优解,则(6)式必成立。而且,对 于仃总的(x,yeS,由(4.2)、(4.3)可得 1-"2)(Ax+By)+3(2Q2x+2Q1y)=ax+by FTLA (u,-u,o )r+(u,-u,O)(Ax+ By -r)+u,(Bo -d)+u,(222 x+22,y+d Bo=atb 由(6)式可得 ))(Ax+ By-r)+u,(20,x+2Q,y+d-BO )sO 即(7)式成立。 再让充分性设(6)、(7)成立,则对任意的{xES,由(42)、(4.3)和(44)有 a'x +by=(u-u,or+u(B -d) a'x+b'y-Hu-u200)(Ax+ By-r)+u,(202*+ 20,y+d-BO ) 因此,(x,y,a)是(P3)的解 第4期 线性一二次双层规划问题 由(8)式知,(,,M2,u、)是(P4)的最优解。 证毕 定理4(双层规划(LQP)的最优性充分必要条件)(x,y)∈S是LQP)的一个最优解的充分 必要条件是:存在O≥0,M.≥0,u,≥0和u1使得 2Q2x+291y+4=Bc (9.1) Ax +By -r)=0 (9.2) 1-2)A+23Q2=a 93) B+2u,g (94 M,(Ax +By -r)=0 (9.5) (u1-u2)(Ax+By-)+u3(2Q2x+2Q1y+d-Bm)≤0,对任意(x)∈S (96) 证明先证必要性,若(x,)是LQP)的最优解,则存在∈R",≥0,使得(x,p 是(P)的最优解。所以(x,y,o)满足(33),(34,囚而(9.1)、(9,2)成立。而此时对偶河题(P4)必存 在最优解(u1M2,3)满足(42)-(44),因而(93、(94成立 将(93)、(9.4)分别右乘x、y再相加得: v;-n2o)r+u3(Bo-d+ui-u2')'(Ax‘+By-r)+u;"(22x·+2,p +d-Bo) + b 由(6)、(9.1)和(92)可得 (Ax By 即(95)成立。(9,6)可由定理3直接得到 再证充分性。1≥0,u2≥0、≥0及(9.1)-(94)表明(x,yC)和(u12,3,)分别是 问题(P和(P4)的可行解。将(9.3),(94)分别右乘x、y后相加,再利用(9.1).(9,2)和(9.5)可得: (u,-u20)r-u,(Bo -d)=ax +b 由(96)和定理3可知(xy)和(u1,2,M3))分别是(P和(P4)的最优解 由于(P2)与(P3同解,所以(x,,ω)是(P2)的一个最优解。由定理1可知x",是(IQP的一个 最优解 证毕 4.算法 分枝定界法是目前求解混合整数规划问题的最有效的方法。我们通过引入0-1变量n,先将双层规 划冋题(LQP)化为一个混合整数规划问题,再利用分枝定界法求解这个混合整数规划问题。这对于 求解中小型的(LQP)问题是较有效的。 由定理1知,(LQP)的解就是问题 P2) max F(x, v)=a'x+b'y t.AX+By-r≤0 (Ax+By 22 r +20,x+d-Bo 的最优解(x",y,o)中的分量(xy) 引入松弛变量z∈R",z≥0,(P2可转化为 系统工程理论与实践 1994年7月 (P,) axF(,y) x+ b (2.1) x少如) Ax+ By-r+z=0 (2.2) z=0 0,x+2Q,yt d ≥0,z≥0 (2.5) 显然,(x'y',o'为(P2)的最优解台存在z≥0使得(x,y',z,)为(P)的最优解 引入01变量n=(12…n),η,E{0,1},i=1,…,m,由(23)化为0,≤Mn,,z;≤(1 n 即 ≤Mn ≤M(e 其中e=(1,1,…,1)∈R",M为一充分大的正数 于是有 (P max F(x,)=a x+b'y 2″.1) Ax By-r+z=o (2″2) 2Q2x+291y+d=B0 0≤Mn (2”4) z≤M(e-n) (2"5) ①≥0,z≥0 (2n6) n=(n1…,n),n,∈{0,1} (2n.7 少·易证A、·:m)为P2)的解妒存在η=(n;,“n),m∈{0],使得(xyxz, ,)为P"2)的解 于是,我们有 定理5(xy')为LQP最优解存在≥0,z≥0,η=(n,…,)(n;∈i01 使得(x",y,z",,)为(P2)的最优解 因此,我们利用分枝定界法求解混合整数规划(P2),其最优解(xy,,)所对应的分量 (x,y)即为原问题(①LQP)的最优解 下面我们给出M取值一个估计 假设从实际问题中我们可以得知‖x≤X,y≤Y,则当矩阵B是行(或列满秩时,我们可对M 的取值做出估计。 由Ax+By-r+z=0可得z≤‖A‖X+|By+lr‖ 由Bo=22x+2,y+可知,当B行满秩时,有 BBO=2B2,x+2B,y+ Bd 因为(B)存在,所以 W=(BB)B[,x +2Q,y+d 因此,|o≤BB)E2|Q2x+2Q,y+ad 当B列满秩时,由于(BB)存在,所以由Bc=2Q2x+2Q1y+可知 B(BB)(20,x+20,y+ d) 所以ol≤B(BB)(2|Q2x+2g,1Y+l 因此,取M≥max{zl‖,lo}即可 第4期 线性二次双层规划问题 7 于是,我们有 定理6设x≤x,≤Y,若B为行(或列)满秩的,则有M=max{M1,M2}.其中M1= A‖x+‖B|Y+|r, (BB)‖B(2|Q2‖x+2g,‖Y+|d),当B为行满秩 (BB)‖‖B|(2iQ2,X+2g1‖Y+|dl),当B为列满秩 以下我们将通过两个数例来说明这个算法 例1max1+x2+3y1-y2其中(y1y2)求解 320 x max5y,+8y,+(x,x2, 12//31 y 0-215 . x,+x,+y, +y x+x ≤2 41 ≤5 y1+y1≤4 转化上述问题为混合整数规划 xx,+x+31 2 s.x1+x2+y1+y2+21=12 x, +x -4y1 4x,+8x,-4y,+2y,-30,1+4a1+5=0 4x2+2y1+ +8=0 ≤M ≤M(-, ≥0 n,e{0,1} 取M=10,在PC机(286)上运行软件Pc-Prog200版,求得原问题的最优解为x1,x2) (5.31250,1.68750,(v1y2)=(4000算时间为406秒 例2max3x1+2x2+y1+2y2+2y3其中(y123)求解 + 100 10020 2003 8 系统工程理论与实践 1994年7月 s.t. +2 +2x2-y1-2y2-≤3 十 转化上述问题为混合整数规划 max3x1+2x2+y1+2y2+y3 S D +2y1-y 1 2 x2-y1y2-2v3+2,=2 4x,+2x,-2y,-2o,-0,+m1+2=0 十4y,十0,+20 +1=0 2x1-4x2+6y:-1+m2+2o3-1=0 ≤M(1-1,) z≥0 n,∈{01 取M=102,与例1运行环境相同,求得原问题的最优解为(x1x2)=(05,2.5),(y1,F2,y) (1.5,00),计算时间为209秒。 参考文献 Bard,JF. An Algorithm for Sloving the General Bilevel Programming Problem. Mathematics of Operations Re- search,l983,(8)260~272 2 Bard, JF Convex Two-Level Optimization, Mathematical Programming 1988,(40): 15-27 3 Bazaraa, MS and Shetty, CM. Nonlinear Progranuning: Theory and Algorithms. John Wilcy Sons New York, 1979 4 Fletcher,R, Practical Methods of Optimization, John Wiley Sons, New York, 1980 5 Wang Shougang and lootsma, FA. a hierarchical Optimization model of resource allocation Optimization, 1993, 14(5)417~432 6 Wang Shouyang. Truthtalking in resource allocation, in Qualitative Reasoning and Decision Technologies(ed. by Carrctc, N P and Singh, M.G. ) CiMNE, Barcelona, 1993, PP145-152 7 Wen, UP and Yang, YII. Algorithms for Solving the Mixcd Intcgcr Two-Level Linear Programming Problem Computers and Operations Research. 1990, (17): 133-142 阮国桢。线性二级规划解的最优性条件与线性规划解法。多目标决策进展。北京:万国学术出版杜,1993 9魏权龄,土日爽,徐兵。数学规划引论。北京航空航天大学出版社,1991 10张建中,许绍吉。线性规划。北京:科学出版社,1990

...展开详情
试读 8P 论文研究-线性一二次双层规划问题.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744435 欢迎大家使用并留下宝贵意见
2019-09-20
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
最新推荐
论文研究-线性一二次双层规划问题.pdf 10积分/C币 立即下载
1/8
论文研究-线性一二次双层规划问题.pdf第1页
论文研究-线性一二次双层规划问题.pdf第2页

试读结束, 可继续读1页

10积分/C币 立即下载 >