第8章-交通量分配二课件.ppt

1、第 4 节 用户均衡分配(User Equilibrium Assignment)1.固定需求型（1）模型化0rskh时，rsKkccrsrsrsk,0rskh时，rsKkccrsrsrsk,rsKkrsrskrsth,0rsKkhrsrsk,0其中，rskh：OD 对rs间第k条径路的交通量。rskC：OD 对rs间第k条径路的行驶时间。rsC：OD 对rs间最短径路的行驶时间。rst：OD 对rs间最短径路的行驶时间。例:假设图示路网中各路段的通行能力和长度相等。将下表中按用户均衡分配法分配到网络上去。OD1231-0220-2300-解：利用用户均衡分配，可以得到以下两种结果。径路2径路

2、112322径路2径路112322（1）用户均衡时的交通量与行驶时间径路2径路1OD交通量时间通行能力aaaaaCxcxc1)0()(c)(22xc)(11xct2xx1x用户均衡的概念)(22xc)(11xccoc2xxox1xtWardrop 第一法则的等价最优化问题Wardrop 法则理论上合理，实际求解非常困难。Beckmann（1956）等价数理最优化模型（有约束非线性最优化问题）min AaxaadxxcZ0)(.ts rsKkrsrskrsth,rsrskrskaKkaAahxrs,0,0arskxh3 非线性规划基础知识a.极值问题a)极值条件函数)(xf在0 x处有极值的必要

3、条件：0)(0 xf函数)(xf在0 x处有极值的充分条件：0)(0 xf极小值0)(0 xf极大值)(xf0)(oxfx0 x极小值 极大值)(xf0)(oxf0 xxa)局部极值和全局极值设函数)(Xf为向量),(21nxxxX，RX，若)()(0XfXf，则称0X为)(Xf的最小点。考虑图示情况，21,PP分别是)(Xf在领域21,RR上的最小点。但是，1P并非是全域R上的最小点。如21,PP所示，仅其附近领域上的最小点称为局部极小点，对应的函数值为局部极小值（local minmum）。在全域上，)(Xf取最小值的点为全局最小点，其值为全局极小值（global minmum）。图中2P

4、点既为局部最小点，也为全局极小点。局部极小点与全局极小点)(xf2x1x1P2P1R2RRb非线性规划的种类a）无约束非线性规划min)(xf 为了求出)(xf在0 x附近的变化，采用泰勒展开如下：xxHxxxfxfxxfTT)(21)()()(0000其中，nTxxfxxfxxfxf)(,)(,)()(21nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxH2222122222212212212212)()()()()()()()()()()(xH为函数)(xf的海赛矩阵(Hessian matrix)。因此，)(xf在0 x处取得据局部极小值的阶必要条件为：0)

5、()()(02010nxxfxxfxxf)(xf在0 x处取得据局部极小值的阶必要条件为0)(0XXHXT，并且对任意0 x成立。对任意0 x，0AxxT时，矩阵 A 正则（positive definite）。因此，)(xH在0 x处必须是正则矩阵。a）有约束非线性规划min)(xf.ts,0)(xgi),2,1(mi构造拉格朗日方程：iiixgxfx)()(),(其最佳解应满足：ijiijjxxgxxfxx)()()(0)()(xgxxiji为拉格朗日系数。c.非线性规划问题的解法a)梯度法(最速下降法 steepest descent method)所谓梯度法是指在探索点的探索方向取该点

6、梯度的相反方向。假设kx为探索点，其探索方向为：Tnkkkkxxfxxfxxfd)(,)(,)(21因为，在kx附近，梯度方向为倾斜度的最大方向，所以在局部最小点附近为使得函数取得最小值的最佳方向然而，探索点有偏离，则不能保证是较好的探索方向。另外，梯度法在初期步骤的探索速度较快，之后随着计算的进行探索速度将变得非常缓慢。【计算步骤】Step令0k，给出初始点0 x。Step0)(kxf，则结束计算。Step求出搜索方向)(kkxfdStep给出搜索步长从使)(kkdxf最小的最佳*值。Step 更 新 试 行 点 kkkdxx*1。令1 kk，返回 Step。梯度法示意图2x1x),(11x

7、d),(00 xd),(11xdb）牛顿法牛顿法不仅利用目标函数的 1 阶偏导数，而且还利用 2 阶偏导数。将目标函数进行泰勒展开，有：)()(21)()()()(kkkkTkkxxxHxxxfxxxfxf其中，)(kxH为)(xf在kx点的海赛矩阵。0)()(kkkxxxHxf（）所以，)()(1kkkkxfxHxx【计算步骤】Step令0k，给出初始点0 x。Step0)(kxf，则结束计算。Step解连立方程0)()(kkkdxHxf，求出探索方向kdStep更新试行点kkkdxx1。令1 kk，返回 Step。牛顿法不进行一维最优化在反复计算的初期阶段，有时步长过大，目标函数得不到改良

8、。.有约束非线性规划问题的解法min)(xf.ts,0)(xgi),2,1(mi,0jx),2,1(ni 求解有约束非线性规划问题的必要充分条件，Kuhn-Tucher 定理是非常重要的。【Kuhn-Tucher 定理】设)(xf为凸函数，)(xgi),2,1(mi为凹函数，并且连续可微，则0*x为非线性问题解的必要充分条件为),(*x成为下式的鞍点（saddle point）或点。iiixgxfx)()(),(鞍点：),(),(),(*xxx0),(x),(*xxK.T点示意图),(*x为鞍点的条件：),2,1(,0,0)()(),(1*njxxxgxxfxxjmjiijj),2,1(,0)

9、()(*njxxgxxfxjijiijj),2,1(,0,0)(),(*mixgxxiij),2,1(,0)(*mixgiii0*jx时，0),(*jxx),2,1(mj0*jx时，0),(*jxx0*i时，0),(*ix),2,1(ni0*i时，0),(*ix图 库恩-塔克条件示意图)(x)(x0 x0 x)()(00(3)一维搜索黄金分割法，斐波那契（Fibonacci）法和曲线近似法【黄金分割法】黄金分割法是通过比较含有最小点的区间中两点的函数值，将区间范围按一定比例缩小，并且将两点中的一点与上次的函数值比较求出最小点的反复计算方法。求图中区间ba,中存在唯一最小点函数)(xf的最小点时

10、，ba,中的两点21,xx用以下方法确定：abxbabax12这时，如果)()(12xfxf，那么，最小点处于区间2,xa。相反，则处于区间bx,1。应满足的条件：1221xbxbaxax由第一式得：)(1abbx)(2abax代入第二式，并整理得：1618.02/)15(。因为，的值恰好与黄金分割比相等，所以被称为黄金分割法。)(xfa1x2xbx（4）解的等价性与唯一性a）解的等价性证明 这里证明，Bechmann 的模型与 Wardrop 的第一法则是等价的。对 Bechmann 的模型构造拉格朗日方程如下：rsKkursrskrsrsthhZhL)()(),(0rskh其中，rs为 O

11、Drs的拉格朗日系数。根据库恩塔克条件：0),(*rskrskhhLh 和rsKkhhhLrsrskrsk,0,0),(*0),(*rshL，rs由第一式得，0rskh时，0),(*rskhhL，rsKkrs,0rskh时，0),(*rskhhL，rsKkrs,这里，rskrsKkrsrskrsrskAaxarskhthhdwwchLrsa/)(0rsrskaaAaxahxdxdwwcda/)(0，rsKkrs,AaKkrshhhxrsrskarskKkrskrskarsrskars,/,所以，AarsrsrskaaarskrsKkxchL,)(/,又因为，Aarsrskaaacxc,)(所以有，0rskh时，rsKkcrsrsrsk,00rskh时，rsKkcrsrsrsk,0b）解的唯一性证明条件：式（2）-式（4）形成凸领域，并且式（1）为狭义凸函数。由式（2）-式（4）知都为线性函数，所以形成的领域为凸领域。Z函数为凸函数的条件为：0/22axZ由式（1）知，AaxcxZaaa),(/badxxdcaaa(,0/)(时）baxxZ20，ba(时），Aba,精品课件精品课件！精品课件精品课件！所以，海赛矩阵为：nnnaaadxxdcdxxdcdxxdcZ/)(0/)(0/)(1112因为，一般情况下，路阻函数为单增函数，所以，Aadxxdcaaa,0/)(所以，有唯一解。