交通守恒条件 3,以终点 s 路段 ij 上的交通量 ijx 为变
量。
0,点 j 为非发生,吸引点时。
?? ??
k
s
jk
i
s
ij
xx
rs
t?,点 j 为发生点 r 时。
rs
D,点 j 为吸引点 s 时。
该守恒条件仅需要在吸引点连接的路段上进行路旁调查
即可,调查项目少。但是,实际吸引点的确定较难。
第 4 节 用户均衡分配 ( U s e r E q u i l i b r i u m A s s i g n m e n t )
1,固定需求型
( 1 ) 模型化
0?
rs
k
h
时,
?????? rsKkcc
rsrsrs
k
,,
0?
rs
k
h
时,
?????? rsKkcc
rsrsrs
k
,,
?
?
?????
rs
Kk
rsrs
k
rsth,0
?????? rsKkh
rsrs
k
,,0
其中,
rs
k
h
,OD 对
rs
间第
k
条径路的交通量。
rs
k
C
,OD 对
rs
间第
k
条径路的行驶时间。
rs
C
,OD 对
rs
间最短径路的行驶时间。
rs
t
,OD 对
rs
间最短径路的行驶时间。
例, 假设图示路网中各路段的通行能力和长度相等。
将下表中按用户均衡分配法分配到网络上去。
O ╲ D 1 2 3
1 - 0 2
2 0 - 2
3 0 0 -
解:利用用户均衡分配,可以得到以下两种结果。
径路 2
径路 1
1 2 3
2
2
径路 2
径路 1
1 2 3
2
2
( 1 ) 用户均衡时的交通量与行驶时间
径路 2
径路 1
O D
交通量
时间
通行能力
?
?
?
?
?
?
?
?
???
?
???
???? ??
a
a
aaa C
xcxc 1)0()(
c )(
22 xc )( 11 xc
t
2x 'x 1x
用户均衡的概念
)( 22 xc )( 11 xcc
oc
2x 'x ox 1x
t
2,W a r dr op 第一法则的等价最优化问题
W a r dr op 法则理论上合理,实际求解非常困难。
B e c k m a nn ( 1956 )等价数理最优化模型 (有约束非
线性最优化问题)
m i n
? ?
?
?
Aa
x
a
a
dxxcZ
0
)(
.,ts
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
3, 非线性规划基础知识
a,极值问题
a) 极值条件
函数
)( xf
在 0
x
处有极值的必要条件:
0)('
0
?xf
函数
)( xf
在 0
x
处有极值的充分条件:
0)(''
0
?xf
→ 极小值
0)(''
0
?xf
→ 极大值
)(xf
0)(' ?oxf
x
0x
极小值 极大值
)(xf
0)(' ?oxf
0x
x
a) 局部极值和全局极值
设函数
)( Xf
为向量
),,,(
21 n
xxxX ???

RX ?
,若
)()(
0
XfXf ?
,则称 0
X

)( Xf
的最小点。
考虑图示情况,21
,PP
分别是
)( Xf
在领域
21
,RR
上的最
小点。但是,1
P
并非是全域
R
上的最小点。
如 21
,PP
所示,仅其附近领域上的最小点称为局部极
小点,对应的函数值为局部极小值 ( l oc a l m i nm um )。在
全域上,
)( Xf
取最小值的点为全局最小点,其值为全
局极小值 ( g l oba l m i nm u m )。图中
2
P
点既为局部最小点,
也为全局极小点。
局部极小点与全局极小点
)(xf
2x
1x
1P 2P
1R 2R
R
b, 非线性规划的种类
a ) 无约束非线性规划
m i n
)( xf
为了求出
)( xf

0
x
附近的变化,采用泰勒展开如下:
???????????? xxHxxxfxfxxf
TT
)(
2
1
)()()(
0000
其中,
?
?
?
?
?
?
?
?
?
?
?
?
??
n
T
x
xf
x
xf
x
xf
xf
)(
,,
)(
,
)(
)(
21
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
??
?
?
?
??
?
??
?
??
?
?
?
?
nnn
n
n
x
xf
xx
xf
xx
xf
xx
xf
x
xf
xx
xf
xx
xf
xx
xf
x
xf
xH
2
2
2
2
1
2
2
2
2
2
2
12
2
1
2
21
2
2
1
2
)()()(
)()()(
)()()(
)(
??
????
??
??
)( xH
为函数
)( xf
的海赛矩阵 ( H e s s i a n m a t ri x ) 。
因此,)( xf 在 0
x
处取得据局部极小值的1阶必要条件为:
0
)()()(
0
2
0
1
0
?
?
?
??
?
?
?
?
?
n
x
xf
x
xf
x
xf
??
)( xf
在 0
x
处取得据局部极小值的2阶必要条件为
0)(
0
??? XXHX
T
,并且对任意
0?? x
成立。对任意
0?x
,0?Axx
T
时,矩阵 A 正则 ( po s it ive de f in it e )。
因此,
)( xH

0
x
处必须是正则矩阵。
a ) 有约束非线性规划
m i n
)( xf
..ts
 
,0)( ?xg
i
 
),,2,1( mi ???
构造拉格朗日方程:
?
???
i
ii
xgxfx )()(),( ??
其最佳解应满足:
?
?
?
?
?
?
?
?
?
i j
i
i
jj
x
xg
x
xf
x
x )()()(
?
0)(
)(
???
?
?
xg
x
x
i
j
i
?
为拉格朗日系数。
c,非线性规划问题的解法
a) 梯度法 ( 最速下降法 s t e e pe s t de s c e n t m e t h od)
所谓梯度法是指在探索点的探索方向取该点梯度的相
反方向。假设
k
x
为探索点,其探索方向为:
T
n
kkk
k
x
xf
x
xf
x
xf
d
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
)(
,,
)(
,
)(
21
??
因为,在
k
x
附近,梯度方向为倾斜度的最大方向,所
以在局部最小点附近为使得函数取得最小值的最佳方
向.然而,探索点有偏离,则不能保证是较好的探索方
向。另外,梯度法在初期步骤的探索速度较快,之后随
着计算的进行探索速度将变得非常缓慢。
【 计算步骤 】
Step 1 令
0?k
,给出初始点
0
x

Step 2 
0)( ??
k
xf
,则结束计算。
Step 3 求出搜索方向 
)(
kk
xfd ???
Step 4 给出 搜索 步长 从使
)(
kk
dxf ??
最小的
最佳
*
?
值。
Step 5   更 新 试 行 点  
kkk
dxx
*1
???
?
。令
1?? kk
,返回 Step 2。
梯度法示意图
2x
1x
),( 11 xd
),( 00 xd
),( 11 xd
b ) 牛顿法
牛顿法不仅利用目标函数的 1 阶偏导数,而且还
利用 2 阶偏导数。
将目标函数进行泰勒展开,有:
))(()(
2
1
)()()()(
kkkkTkk
xxxHxxxfxxxfxf ???????
其中,
)(
k
xH

)( xf

k
x
点的海赛矩阵。
0))(()( ????
kkk
xxxHxf
………… (a)
所以,
)]()([
1 kkkk
xfxHxx ???
?
【 计算步骤 】
Step 1 令
0?k
,给出初始点
0
x

Step 2 
0)( ??
k
xf
,则结束计算。
Step 3 解连立方程
0)()( ???
kkk
dxHxf
,求出探索方

k
d
Step 4 更新试行点
kkk
dxx ??
? 1
。令
1?? kk
,返
回 Step 2。
牛顿法不进行一维最优化
在反复计算的初期阶段,有时步长过大,目标函数
得不到改良。
d, 有约束非线性规划问题的解法
m i n
)( xf
..ts,0)( ?xg
i  
),,2,1( mi ???
,0?
j
x
 
),,2,1( ni ???
求解有约束非线性规划问题的必要充分条件,
Kuh n- T ucher 定理是非常重要的。
【 Kuh n- T ucher 定理 】

)( xf
为凸函数,
)( xg
i
),,2,1( mi ??? 为凹函数,并且连
续可微,则 0
*
?x 为非线性问题解的必要充分条件为
),(
**
?x
成为下式的鞍点 ( saddle poin t )或KT点。
????
i
ii
xgxfx )()(),( ??
鞍点:
),(),(),(
****
??? xxx ?????
0
),( ?x?
? ),(
** ?x
?
x
K.T点示意图
),(
**
?x
为鞍点的条件:
),,2,1(,0,0
)()(),(
1
****
njx
x
xg
x
xf
x
x
j
m
j
i
i
jj
?????
?
?
??
?
?
?
?
??
?
?
?
?
),,2,1(,0
)()(
*
*
*
*
nj
x
xg
x
xf
x
j i j
i
i
j
j
????
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
? ? ?
),,2,1(,0,0)(
),(
*
**
mixg
x
x
ii
j
???????
?
??
?
?
),,2,1(,0)(
**
mixg
i
ii
????? ?
0
*
?
j
x
时,
0
),(
**
?
?
??
j
x
x ?
),,2,1( mj ???
0
*
?
j
x
时,
0
),(
**
?
?
??
j
x
x ?
0
*
?
i
? 时,0
),(
**
?
?
??
i
x
?
?
),,2,1( ni ???
0
*
?
i
?
时,
0
),(
**
?
?
??
i
x
?
?
图 库恩 - 塔克条件示意图
)(x? )(x?
0?x 0?x
)(??
)(??
0?? 0??
(3) 一维搜索
黄金分割法,斐波那契 ( Fibo nacci )法和曲线近似法
【 黄金分割法 】
黄金分割法是通过比较含有最小点的区间中两点的函
数值,将区间范围按一定比例缩小,并且将两点中的一
点与上次的函数值比较求出最小点的反复计算方法。
求图中区间
? ?ba,
中存在唯一最小点函数
)( xf
的最小点
时,
? ?ba,
中的两点
21
,xx
用以下方法确定:
??
?
?
?
?
?
ab
xb
ab
ax
12
这时,如果
)()(
12
xfxf ?
,那么,最小点处于区间
? ?
2
,xa

相反,则处于区间 ? ?bx,
1
。 ? 应满足的条件:
??
?
?
?
?
?
1
2
2
1
xb
xb
ax
ax
由第一式得:
?)(
1
abbx ???
?)(
2
abax ???
代入第二式,并整理得:
?
?
?
?
?1
6 1 8.02/)15( ????
。因为,
?
的值恰好与黄金分割比
相等,所以被称为黄金分割法。
)(xf
a 1x 2x b
x
( 4 )解的等价性与唯一性
a )解的 等价性证明
这里证明,Bechm ann 的模型与 W ar drop 的第一法
则是等价的。
对 Bechm ann 的模型构造拉格朗日方程如下:
??
???
???
rs
Kk
u r srs
k
rs
rs
thhZhL )()(),( ??
0?
rs
k
h
其中,
rs
? 为 OD
rs
的拉格朗日系数。
根据库恩-塔克条件:
0
),(
**
?
?
?
rs
k
rs
k
h
hL
h
?
 和 
???????
?
?
rsKkh
h
hL
rsrs
k
rs
k
,,0,0
),(
**
?
0
),(
**
?
?
?
rs
hL
?
?

??? rs
由第一式得,
0?
rs
k
h
时,
0
),(
**
?
?
?
rs
k
h
hL ?

????? rsKk
rs
,
0?
rs
k
h
时,
0
),(
**
?
?
?
rs
k
h
hL ?

????? rsKk
rs
,
这里,
rs
k
rs Kk
rsrs
k
rsrs
k
Aa
x
a
rs
k
hthhdwwc
h
L
rs
a
?
?
?
?
?
?
?
?
?
?
?
?
?
????
?
?
?
?
?
?
??
?
?
? ?? ?
?? ??
//)(
0
?
rs
rs
k
a
a
Aa
x
a
h
x
dxdwwcd
a
??
?
?
?
?
?
?
?
?
?
?
? ?
?
/)(
0,
????? rsKk
rs
,
AaKkrshhhx
rsrs
ka
rs
k
Kk
rs
k
rs
ka
rs
rs
ka
rs
?????????
?
?
?
?
?
?
?????
??
???
,,,//
,,
??
所以,
?
?
??????????
Aa
rsrsrs
kaaa
rs
k
rsKkxchL,,)(/
,
??
又因为,
?
?
??
Aa
rsrs
kaaa
cxc
,
)( ?
所以有,
0?
rs
k
h
时,
??????? rsKkc
rsrsrs
k
,,0?
0?
rs
k
h
时,
??????? rsKkc
rsrsrs
k
,,0?
b )解的唯一性证明
条件:式 ( 2 ) - 式 ( 4 )形成凸领域,并且式 ( 1 )为狭
义凸函数。
由式 ( 2 ) - 式 ( 4 )知都为线性函数,所以形成的领域
为凸领域。
Z
函数为凸函数的条件为:
0/
22
???
a
xZ
由式 ( 1 )知,
AaxcxZ
aaa
????? ),(/
badxxdc
aaa
?? (,0/)(
时)
?
??
?
ba
xx
Z
2
0,
ba ?(
时),
Aba ??,
所以,海赛矩阵为:
?
?
?
?
?
?
?
?
?
?
??
nnn
aaa
dxxdc
dxxdc
dxxdc
Z
/)(0
/)(
0/)(
111
2
??
??
??
因为,一般情况下,路阻函数为单增函数,所以,
Aadxxdc
aaa
???,0/)(
所以,有唯一解。