冰岛人怎样出行？
变分不等式的双层平衡表示及其在交通流分配中的应用 傅白白 刘法胜 夏尊铨 摘要: 给出了Hartman-stampacchia变分不等式的一种双层平衡等价表示，指出了变分不等式与系统平衡之间的深刻联系，并讨论了它们在交通流分配用户平衡(UE)和随机用户平衡(SUE)模型中的应用。 关键词: 变分不等式; 双水平规划; 网络平衡; 随机用户平衡 An Equivalent Bi-level Equilibrium Representation for Variational Inequality and Its Applications in Traffic...全部
变分不等式的双层平衡表示及其在交通流分配中的应用 傅白白 刘法胜 夏尊铨 摘要: 给出了Hartman-stampacchia变分不等式的一种双层平衡等价表示，指出了变分不等式与系统平衡之间的深刻联系，并讨论了它们在交通流分配用户平衡(UE)和随机用户平衡(SUE)模型中的应用。
关键词: 变分不等式; 双水平规划; 网络平衡; 随机用户平衡 An Equivalent Bi-level Equilibrium Representation for Variational Inequality and Its Applications in Traffic Assignment Problems FU Bai-bai, LIU Fa-sheng, XIA Zun-quan (Department of Applied Mathematics, Dalian University of Technology,Dalian 116024) Abstract: An equivalent bilevel equilibrium representation for variational inequality (VI) is presented and the profound relation between VI and bilevel equilibrium is clarified。
Their applications in traffic assignment problems (TAP) are discussed for both user equilibrium (UE) and stochastic user equilibrium(SUE) models。
Keywords: variational inequality(VI); bilevel programming; user equilibrium; stochastic user equilibrium(SUE) 1 引言 Hartman-Stampacchia变分不等式是指求x*∈K，使得 其中KRn为一非空闭凸集，F(x):K→Rn是一连续映射。
变分不等式(1)是本世纪60年代中期Hartman, Stampacchia等人在创建变分不等式理论的基础时提出和研究的第一个变分不等式，它在经济数学、对策论、最优化理论及网络平衡模型中有着广泛而重要的应用[1,2]。
公式(1)与数学规划之间的联系一开始就受到很大重视。当F(x)为一凸函数的梯度时，显然(1)式可以转化为一等价的可微数学规划问题，Carey详细论述了这一关系在经济平衡中的应用[3]。
一般非对称情况下(1)式不再有上述意义下的最优化等价表示。Fukushima 1992年通过引进正则化方法给出了(1)式的一种可微最优化等价表示[4]；T。Larsson和M。Patriksson 1994年又给出了更一般的一类可最优化等价表示，从而从理论上回答了(1)式与可微数学规划之间的关系，并依此给出了相应的(1)式的优化解法[4,5]。
上述转换要么条件要求高，要么不再具有优化建模的直观特点，因而，这种转换有时无益于实际问题的模型建立与求解分析。 对策论在经济、管理及生物学等领域有着广泛的背景和应用。数学规划明确的目标追求及较成熟的算法使其在各个领域中的应用日趋广泛和深入，但传统的优化模型只考虑单一决策者在一定约束条件下的目标最优问题，将对策论与数学规划的特点结合起来形成多决策者参与的竞争优化模型具有理论和实践的重要意义，Nash平衡、Minmax解及Stackelberg解模型等是基本的对策规划模型[6]。
我们发现建立变分不等式与对策规划之间的联系有利于实际问题的模型建立与求解分析。变分不等式与Nash平衡及不动点之间有着深刻的联系：任意一个Nash平衡问题均可表示为一个变分不等式；Zuhovickii 1969年就指出了Nash平衡与鞍点之间的关系：x*是(1)式的解当且仅当(x*,x*)为F(x)T(y-x)的一个鞍点[2]。
双水平规划(Bilevel Programming 又称Two-level Programming)的层次性给问题建模及求解分析带来了直观明晰性，其特点在网络平衡模型分析中更为明显。本文第二节讨论(1)式与双水平规划之间的关系；第三节讨论它们在交通网络平衡分配中的应用，并给出Wardrop原则下用户平衡(UE)和随机用户平衡(SUE)分配的双水平规划模型。
2 变分不等式的双水平规划等价表示 双水平规划是一种考虑存在对策因素的决策模型。决策系统含有两个层次：下层(Follower)依据上层宣布的决策考虑自己的目标最优而采取对策，上层(Leader)事先考虑到这种对策信息而宣布自己的决策并尽量使自己的目标最优。
双水平规划大致又分为两类：一类是以下层问题的解(决策本身)作为响应反馈到上层，另一类是以下层的目标值(决策的效应)作为响应反馈到上层[7]。我们下面给出(1)式在这两种意义下的双水平规划等价表示。
定理 设KRn是一非空闭凸集，F(x):K→Rn是一连续映射，构造下述双水平规划： 由于问题的特殊性，上下层解相一致，我们称这类双水平规划问题为双层平衡，记为BE。则下述结论等价 (Ⅰ) x*是(1)式的解； (Ⅱ) x*是BE(Ⅰ)的解； (Ⅲ) x*是BE(Ⅱ)的解。
证明 事实上BE(Ⅱ)等价于(1)可由是一gap函数得到[1，2]。故我们只需要证明(Ⅰ)?(Ⅱ)。 设x*为(1)的解，则x*亦为min F(x*)Ty的解，故x*为BE(Ⅰ)的解；反之，若x*为BE(Ⅰ)的解，则有 故x*为(1)的解 。
定理证毕。 由上述结果我们可以对(1)作下述经济平衡含义解释：F(x)为单位费用向量函数，上层宣布一种状态x，下层寻求此信息下的总费用最小，上下层一致时的结果对应着(1)式的解。由此可见变分不等式(1)与经济平衡之间有着深刻的联系。
由上述等价表示结果，我们还可以得到变分不等式(1)与Nash平衡(NE)之间的关系。 推论 (1)式与下述Nash平衡(NE)等价： 其中，K含义同前。 对推论的经济含义可解释为系统平衡解对应着单位费用F(x)下的总费用最小时的循环反馈平衡结果。
3 交通流分配问题的双层平衡模型 网络平衡模型与变分不等式的关系已被深入地研究过[1,2]。用双层平衡表述网络平衡模型可以更好地利用网络的特点和性质，有利于实际问题建模与求解分析。
以下我们以交通网络平衡分配为例，建立用户平衡(UE)与随机用户平衡(SUE)分配的双层平衡模型。 用一个有向图G(N，A)代表交通网络，其中N是节点集合，A是有向线段集合。设交通需求矩阵为(dqp)，路段a上的单位费用为Ca(xa),其中xa为路段a上的交通流量，则出行者寻求各自最小费用(Wardrop第一原则)的模型为用户平衡模型。
用双层平衡规划方法可以方便地刻划该模型：将用户平衡系统人为地划分为二层次：规划管理者宣布路网上的流量状态，出行者在该状态信息下寻求最短路径出行，二者一致时即为用户平衡分配结果。故其双层平衡模型为 其中K为网络流约束集，若记frpq为从p到q经过路径r的流量， 则K由下述关系给出：(下层约束与上层约束相同) 容易证明(4)的解满足Wardrop条件。
事实上， 设fr*pq为满足Wardrop条件的交通流，相应的单位费用为Cr*pq，最小费用为π*pq，则Wardrop条件可表述为： 用frpq乘(5b)与(5a)相减并对r及(pq)作和得 由费用函数的可加性得 其中x*a为满足Wardrop条件的路段上a的流量，由变分不等式的BE表示定理知Wardrop条件包含着(4)。
反之，若(x*a,y*a)为(4)之解，则x*a=y*a，且x*a为 的解，(5e)对应着最短路径交通分配(All-or-Nothing)情形，故Wardrop条件满足。 在交通流分配问题中，用户出行在考虑了路段拥挤因素后不是严格地按最短路径出行，而是依据概率最短路径选择，我们称该模型为随机用户平衡(SUE)[8]。
将该模型化为双层平衡模型，上层为交通规划管理者，宣布道路网络上的交通量状态信息，下层为交通出行者在上层宣布的道路网络交通量信息下寻求概率最短路出行，二者的平衡一致结果即为随机用户平衡解。 当概率最短路分配模型确定后，即可给出SUE的双层平衡模型。
如基于logit意义下的SUE模型的双层平衡表示为 其中θ＞0，K由(4)的约束条件界定。 由SUE的双层平衡表示，容易设计和分析其计算过程，如常用的MSA(Method of Successive Averages)算法： step 0:Initialization,进行随机最短路分配 set n:=1 step 1:Update,对于任意路段a计算此时的交通费用Cnα=Cα(xnα) step 2:确定搜索方向，在Cnα下进行概率最短路分配得ynα step 3: step 4:停止检验：若xnα=xn+1α则停止，否则set n:=n+1转step1。
上述算法中的step3反映了二层平衡过程的信息。 概率最短路分配算法视随机概型而定，一般情形只有进行Monte Carlo模拟，实际计算时，最后只关心均值信息，可不考虑分布信息[8]。
此外，交通工程人员更关心交通网络用户平衡模型的直观含义解释[9,10]，UE与SUE的双层平衡表示有利于对其直观经济含义的进一步解释。收起
