第8章-交通量分配(二)

交通守恒条件3：以终点s路段ij上的交通量ijx为变量。0：点j为非发生，吸引点时。ksjkisijxxrst：点j为发生点r时。rsD：点j为吸引点s时。该守恒条件仅需要在吸引点连接的路段上进行路旁调查即可，调查项目少。但是，实际吸引点的确定较难。第4节用户均衡分配(UserEquilibriumAssignment)1.固定需求型（1）模型化0rskh时，rsKkccrsrsrsk,,0rskh时，rsKkccrsrsrsk,,rsKkrsrskrsth,0rsKkhrsrsk,,0其中，rskh：OD对rs间第k条径路的交通量。rskC：OD对rs间第k条径路的行驶时间。rsC：OD对rs间最短径路的行驶时间。rst：OD对rs间最短径路的行驶时间。例:假设图示路网中各路段的通行能力和长度相等。将下表中按用户均衡分配法分配到网络上去。O╲D1231-0220-2300-解：利用用户均衡分配，可以得到以下两种结果。径路2径路112322径路2径路112322（1）用户均衡时的交通量与行驶时间径路2径路1OD交通量时间通行能力aaaaaCxcxc1)0()(c)(22xc)(11xct2x'x1x用户均衡的概念)(22xc)(11xccoc2x'xox1xt２．Wardrop第一法则的等价最优化问题Wardrop法则理论上合理，实际求解非常困难。Beckmann（1956）等价数理最优化模型（有约束非线性最优化问题）min　　AaxaadxxcZ0)(..tsrsKkrsrskrsth,rsrskrskaKkaAahxrs,,0,0arskxh3．非线性规划基础知识a.极值问题a)极值条件函数)(xf在0x处有极值的必要条件：0)('0xf函数)(xf在0x处有极值的充分条件：0)(''0xf→极小值0)(''0xf→极大值)(xf0)('oxfx0x极小值极大值)(xf0)('oxf0xxa)局部极值和全局极值设函数)(Xf为向量),,,(21nxxxX，RX，若)()(0XfXf，则称0X为)(Xf的最小点。考虑图示情况，21,PP分别是)(Xf在领域21,RR上的最小点。但是，1P并非是全域R上的最小点。如21,PP所示，仅其附近领域上的最小点称为局部极小点，对应的函数值为局部极小值（localminmum）。在全域上，)(Xf取最小值的点为全局最小点，其值为全局极小值（globalminmum）。图中2P点既为局部最小点，也为全局极小点。局部极小点与全局极小点)(xf2x1x1P2P1R2RRb．非线性规划的种类a）无约束非线性规划min)(xf为了求出)(xf在0x附近的变化，采用泰勒展开如下：xxHxxxfxfxxfTT)(21)()()(0000其中，nTxxfxxfxxfxf)(,,)(,)()(21nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxH2222122222212212212212)()()()()()()()()()()(xH为函数)(xf的海赛矩阵(Hessianmatrix)。因此，)(xf在0x处取得据局部极小值的１阶必要条件为：0)()()(02010nxxfxxfxxf)(xf在0x处取得据局部极小值的２阶必要条件为0)(0XXHXT，并且对任意0x成立。对任意0x，0AxxT时，矩阵A正则（positivedefinite）。因此，)(xH在0x处必须是正则矩阵。a）有约束非线性规划min)(xf..ts　,0)(xgi　),,2,1(mi构造拉格朗日方程：iiixgxfx)()(),(其最佳解应满足：ijiijjxxgxxfxx)()()(0)()(xgxxiji为拉格朗日系数。c.非线性规划问题的解法a)梯度法(最速下降法steepestdescentmethod)所谓梯度法是指在探索点的探索方向取该点梯度的相反方向。假设kx为探索点，其探索方向为：Tnkkkkxxfxxfxxfd)(,,)(,)(21因为，在kx附近，梯度方向为倾斜度的最大方向，所以在局部最小点附近为使得函数取得最小值的最佳方向．然而，探索点有偏离，则不能保证是较好的探索方向。另外，梯度法在初期步骤的探索速度较快，之后随着计算的进行探索速度将变得非常缓慢。【计算步骤】Step１　令0k，给出初始点0x。Step２　0)(kxf，则结束计算。Step３　求出搜索方向　)(kkxfdStep４　给出搜索步长　从使)(kkdxf最小的最佳*值。Step５　更新试行点　kkkdxx*1。令1kk，返回Step２。梯度法示意图2x1x),(11xd),(00xd),(11xdb）牛顿法　　牛顿法不仅利用目标函数的1阶偏导数，而且还利用2阶偏导数。　　将目标函数进行泰勒展开，有：))(()(21)()()()(kkkkTkkxxxHxxxfxxxfxf其中，)(kxH为)(xf在kx点的海赛矩阵。0))(()(kkkxxxHxf…………（ａ）所以，)]()([1kkkkxfxHxx【计算步骤】Step１　令0k，给出初始点0x。Step２　0)(kxf，则结束计算。Step３　解连立方程0)()(kkkdxHxf，求出探索方向kdStep４　更新试行点kkkdxx1。令1kk，返回Step２。牛顿法不进行一维最优化在反复计算的初期阶段，有时步长过大，目标函数得不到改良。ｄ.有约束非线性规划问题的解法min)(xf..ts,0)(xgi　),,2,1(mi,0jx　),,2,1(ni求解有约束非线性规划问题的必要充分条件，Kuhn-Tucher定理是非常重要的。【Kuhn-Tucher定理】设)(xf为凸函数，)(xgi),,2,1(mi为凹函数，并且连续可微，则0*x为非线性问题解的必要充分条件为),(**x成为下式的鞍点（saddlepoint）或ＫＴ点。iiixgxfx)()(),(鞍点：),(),(),(****xxx0),(x),(**xxK.T点示意图),(**x为鞍点的条件：),,2,1(,0,0)()(),(1****njxxxgxxfxxjmjiijj),,2,1(,0)()(****njxxgxxfxjijiijj),,2,1(,0,0)(),(***mixgxxiij),,2,1(,0)(**mixgiii0*jx时，0),(**jxx),,2,1(mj0*jx时，0),(**jxx0*i时，0),(**ix),,2,1(ni0*i时，0),(**ix图库恩-塔克条件示意图)(x)(x0x0x)()(00(3)一维搜索黄金分割法，斐波那契（Fibonacci）法和曲线近似法【黄金分割法】黄金分割法是通过比较含有最小点的区间中两点的函数值，将区间范围按一定比例缩小，并且将两点中的一点与上次的函数值比较求出最小点的反复计算方法。求图中区间ba,中存在唯一最小点函数)(xf的最小点时，ba,中的两点21,xx用以下方法确定：abxbabax12这时，如果)()(12xfxf，那么，最小点处于区间2,xa。相反，则处于区间bx,1。应满足的条件：1221xbxbaxax由第一式得：)(1abbx)(2abax代入第二式，并整理得：1618.02/)15(。因为，的值恰好与黄金分割比相等，所以被称为黄金分割法。)(xfa1x2xbx（4）解的等价性与唯一性a）解的等价性证明这里证明，Bechmann的模型与Wardrop的第一法则是等价的。对Bechmann的模型构造拉格朗日方程如下：rsKkursrskrsrsthhZhL)()(),(0rskh其中，rs为ODrs的拉格朗日系数。根据库恩－塔克条件：0),(**rskrskhhLh　和　rsKkhhhLrsrskrsk,,0,0),(**0),(**rshL，rs由第一式得，0rskh时，0),(**rskhhL，rsKkrs,0rskh时，0),(**rskhhL，rsKkrs,这里，rskrsKkrsrskrsrskAaxarskhthhdwwchLrsa//)(0rsrskaaAaxahxdxdwwcda/)(0，rsKkrs,AaKkrshhhxrsrskarskKkrskrskarsrskars,,,//,,所以，AarsrsrskaaarskrsKkxchL,,)(/,又因为，Aarsrskaaacxc,)(所以有，0rskh时，rsKkcrsrsrsk,,00rskh时，rsKkcrsrsrsk,,0b）解的唯一性证明条件：式（2）-式（4）形成凸领域，并且式（1）为狭义凸函数。由式（2）-式（4）知都为线性函数，所以形成的领域为凸领域。Z函数为凸函数的条件为：0/22axZ由式（1）知，AaxcxZaaa),(/badxxdcaaa(,0/)(时）baxxZ20，ba(时），Aba,所以，海赛矩阵为：nnnaaadxxdcdxxdcdxxdcZ/)(0/)(0/)(1112因为，一般情况下，路阻函数为单增函数，所以，Aadxxdcaaa,0/)(所以，有唯一解。