当前位置：文档库 › 城市均衡分配模型与算法

城市均衡分配模型与算法

专适于城市道路网络的交通均衡分配模型

刘灿齐

同济大学道路与交通工程系，上海，200092

摘要：由于已有的均衡分配理论中的阻抗公式不包含车流在交叉口的延误，其研究成果并不真正适用于城市道路网络。本文提出了流向、流向阻抗、流向流量的概念，找到了包含交叉口分流向延误的阻抗公式、基于新阻抗公式的交通均衡分配模型。这个模型较真实地描述了城市道路网络上的交通分配情况。

关键词：城市道路网络，流向，延误，阻抗公式，均衡分配

Traffic Equilibrium Assignment Model Special for

Urban Road Network

LIU Canqi

Road & Traffic Department, Tongji University, Shanghai 200092

Abstract: The cost formula in the existing equilibrium theory does not include the delay time at nodes. So, the researching results of the theory are unsuitable for urban road network. The conceptions of traffic direction, cost on traffic direction, and volume on traffic direction are given. The cost formula including the delay time at nodes is expressed. At last, a new equilibrium assignment model based on the cost formula is posed, which is suitable for urban road network.

Key words: Urban road network, Flow-direction, delay, cost formula, equilibrium assignment

关于交通分配，1952年Wardrop 提出了道路网均衡分配的概念，其定义是：在道路网的用户都知道网络的状态并试图选择最短路径时，网络会达到这样一种均衡状态，每对产生——吸引点（PA 点对）之间各条被利用的路径的走行时间都相等而且是最小的走行时间，而没有被利用的的路径的走行时间都大于或等于这个最小的走行时间。

这条定义通常称为“Wardrop 的第一原理”，又叫“用户均衡原理”。 1956年，Bechmann 等提出了描述这个均衡问题的一个数学规划模型，1975年LeBlanc 等学者设计出了求解Bechmann 模型的算法，从而形成了现在的实用解法。Wardrop 原理——Bechmann 模型——Leblanc 算法这三点突破是交通分配问题研究的三个里程碑，也是现在交通分配理论的基础[1]。

然而，这些均衡分配研究成果并不真正适合于城市道路网络。在交通均衡分配模型和算法中，路段阻抗函数是一个基本要素，LeBlanc 的算法中要求它单调递增。到目前为止，唯一公认的来自于实际观测的阻抗函数实例就是美国公路局（BPR ）的走行时间公式

()[]

βαa a a a a e x t x t /1)0()(+= （1）然而，这个公式是从市际公路观测得到的，对城市道路，只能描述车辆在路段部分的行驶时间。但城市道路网络上的车辆除了在路段部分要花费行驶时间外，在信号灯交叉口还往往要花时间

等待绿灯，存在排队延误。实际上，这个延误在整个出行时间中占相当大的比例（20~40%），并且不同流向的平均延误明显不同，一般是：右转<直行<左转。根据我们作的问卷调查，熟悉路网的驾驶员在出行选择路径时，对备选的各路径将要通过几个信号灯交叉口以及各交叉口的不同转向都有充分的考虑和估量。因此，如果只考虑路段行驶时间而忽略节点分流向延误时间的阻抗公式是不适合城市道路网的，基于这样的阻抗公式（如BPR 公式）进行的交通均衡分配与实际的城市道路网上的交通分配状况无疑会存在一定的出入。这种出入不是来自于数据调查和统计，而是来自于模型本身；即：不是统计和随机误差，而是理论系统的缺陷。

现在国内外交通规划的理论和应用界的状况是，仍用基于单调递增的路段走行时间函数的Bechmann 模型及其衍生模型（如随机均衡分配模型、弹性需求均衡分配模型）描述城市道路网络上的交通分配。现在一些规划者的看法是：“交通规划属于中观层面的问题，没必要微观到考虑交叉口的分流向延误”。笔者以为，不是没有必要（因为交叉口的延误占整个出行时间的20~40%，而且驾驶员们考虑到了这种延误），而是目前没有更好的模型和方法，只好转而求其次。所以，对于城市道路网络，急需研究出加入节点分流向延误的阻抗函数、相应的交通均衡分配模型和算法。论文[2]、[3]已在加入交叉口分流向延误后最短路径算法问题上做了研究，本文将探讨加入节点分流向延误的阻抗函数、和相应的交通均衡分配模型。

首先，我们介绍本文模型中使用的变量和参数。 h 、i 、j : 道路网络上的节点，即交叉口；

x ijh ：流向（含路段） (i,j,h )上的交通流量，它们组成的向量为X =(…, x ijh , …)； e ij : 表示路段(i , j )的通行能力； s ijh : 表示进口道(i , j , h ) 的饱和流量； λ

ijh ：流向

(i,j,h )上的绿信比；

c j ：交叉口j 的信号周期时间；

H ij ：路段（i , j ）的各下游交叉口的集合，即除ii 外的与节点j 相邻节点的集合； r ij (?)：路段 (i, j )的走行时间，如果节点i 与 j 不相邻，则令: r ij (?)=∞； d ijh (?)：流向 (i,j,h )的延误时间；

t ijh (?)：流向（含路段）a =(i,j,h )的总阻抗函数，t ijh (?)=r ij (?)+d ijh (?)； rs k f ：点对（r ，s ）间的第k 条路径的交通流量，其向量为f =(…, rs k f ,…)；

rs k c ：点对（r ，s ）间的第k 条路径阻抗；

rs k ijh ,δ：流向—路径相关变量， ??

?=否则

条路径上间的第在如果流向（,

0),(),,,1,k s r h j i rs k ijh δ。

rs q ：点对(r , s )间的PA 交通量。

1 已有成果回顾

近年来已有些学者已注意到了这个问题，试图对它进行改进。目前已出现三种改进做法：（1）添加延误项方法[3]。令

t ij =r ij +d j （2）式中， d j ——车辆在交叉口j 的延误，一般是各流向延误的加权平均值。

这种方法只能帮助区别不同延误等级的交叉口，十分粗糙。因为一般交叉口含有6个（三枝交

叉口）或12个（四枝交叉口）流向，不同流向的延误不同，如果用同一个d j 表示，就抹杀了各流向延误的互异性，这正是城市道路网络区别于其它交通网络的关键所在。

（2）添加逻辑边的方法。如图1中，只以交叉口j 和单向边(i , j )为例，将边根据车流的流向分化成三条逻辑边，各逻辑边的阻抗不同，分别为：

t ij 左=r ij +d ij 左， t ij 直=r ij +d ij 直， t ij 右=r ij +d ij 右（3）式中，t ij 左、t ij 直、t ij 右——各流向车流在路段(i , j )及交叉口j 的总阻抗；

d ij 左、d ij 直、d ij 右——各流向车流在交叉口的延误。

这样一来，节点i 、j 间就有三条边可以选择。一则，使网络中的边增加了两倍；再则，在进行最短路径计算时（均衡分配算法包含这步），对所有i 至j 的车辆，计算机将总是自动选择最小阻抗的那条逻辑边（一般是右转边）。（3）添加逻辑节点和逻辑边的方法。为避免上述错误，把节点j 分做三个节点j 左、j 直、j

右（见图

2）。这样一来，就使网络中的边增加两倍，节点增加四倍（垂直方向要对节点j 做另

外的分化），从而网络将变得异常的庞大，这对实际的交通网络肯定是不适用。

正因为这些方法都存在致命的缺陷，它们在理论上和实际中都没得到承认和应用。

2 基本概念

图3 路段——阴影部分

在Bechmann 模型中，最基本的流量和阻抗是关于“路段”的，加入交叉口分流向延误后，

j 左

j 直 j 右

图1 添加逻辑边图2 添加逻辑节点和逻辑边

最基本的流量和阻抗应该是关于“流向（Flow-direction ）”的，这里的“流向”包括路段部分和进口道部分。如图3所示，“路段”是指：上游交叉口的出口道起始断面与相邻的下游交叉口停车线之间的（半幅）道路空间；而“流向”则是指：上游交叉口的出口道起始断面与相邻交叉口各个方向的出口道起始断面之间的道路空间（见图4）。图4 各个流向——阴影部分

用二维向量(i , j )可以表示“路段”，而流向须用三维向量(i , j , h )表示。

流向的流量——单位时间内通过下游交叉口各个流向出口道起始断面车辆的数目。用x ijh 表示流向(i , j , h )的流量。

流向的阻抗——车辆在流向(i , j , h )上的阻抗是车辆离开交叉口i 的停车线到离开交叉口j 的停车线之间的时间，即

t ijh (…,x ijh ,…) =r ij (x ij )+d ijh (x ijh ) （4a ）其中，路段流量等于该路段下游交叉口各流向流量之和： j i x x ij

H h ijh ij ,,?=∑∈ （4b ）

这里，t ijh (…,x ijh ,…)表示总阻抗不仅与本流向的流量有关，还与同一路段上的其它流向的流量有关。

3 阻抗函数

如果采用美国联邦公路局（BPR ）的走行时间公式作为路段部分的走行时间r ij (x ij )，采用美国《通行能力手册》的延误公式作为交叉口延误d ijh (x ijh )，就有：

)0,(,1)0()(>???

????????

? ??+=ij ij ij ij

ij ij ij ij ij

e x

r x r βααβ （5a ） ????

?????+???

? ??-+?

??? ??-?????

??+--=

ijh ijh ijh ijh ijh ijh ijh ijh ijh ijh

ijh ijh

ijh j ijh ijh ijh s x s x s x s x x s c s x d λλλλλ22

21611173)1(38.0)( （5b ） r ij (x ij )是x ij 的单增连续可微函数，易知也是各个x ijh 的单增连续可微函数。下面考察d ijh (x ijh )的数学性质：它是单个变量x ijh 的函数，由两项组成，显然第一项是x ijh 的单增连续可微函数；第二项是两个因子的乘积，第一个因子是正的，且是x ijh 的单增连续可微函数，如果第二个因子也是正的和单增连续可微的，则第二项也是x ijh 的单增连续可微函数，从而d ijh (x ijh )是x ijh 的单增连续可微函数。现在就考察第二项的第二个因子，令（暂省去下标，并让m 表示流向的通行能力，即m =s λ）

()()?

???+-+

-=)/(161/1/)(2sm x m x m x x f 易知，f(x )>0。对它求导，

()????

????

+-+-+

=)/(161//81/11)('2

sm x m x s

m x m x f

当x ≥m （超饱和）时，x/m ≥1，显然f ’(x )>0；当0< x

x m x m s m x m x sm x m x s m x sm x m x m

x f /161//81/1//161//81//161/1)('2

222+-+-+->

+-+-++-?

()()

0/161//8/161//81/)/1(2

>+-=+-+-+-=sm

x m x m

sm x m x m s m x m x

综上所述，t ijh (…,x ijh ,…)是各个x ijh 的单增连续可微函数。

4 均衡分配模型

现在我们模仿Bechmann 模型构造新的均衡分配模型： ∑∑?

∑?

∈+=j i H h x ijh j

i x

ij ij

ijh

ij u u d u u r X Z ,0

,0d )(d )()(:Min （6a ）

s. t. :

s r q f

rs k

k ,,

?=∑ （6b ）

s r f rs k ,,

0?≥ （6c ）

ij s

r k

rs k

ijh rs k ijh H h j i f x ∈???=∑∑;,,,δ （6d ）

j i x

x ij

H h ijh

ij ,,

∑∈ （6e ）

现在的问题是：该模型是否真正满足Wardrop 第一均衡分配原理？以及它有多少最优解？下面证明之。

4.1 均衡性

首先，先给出Wardrop 第一均衡分配原理的数学表达。它等价于：

rs rs k u c ≥， 0≥rs k f ， 0=?>rs k rs rs

k f u c （rs W k s r ∈??;,）（7）

此式等价于： rs rs k u c ≥ ， 0≥rs k f ， 0)(=-rs rs

k rs k u c f （rs W k s r ∈??;,）（8）

式中，u rs 为点对(r , s )间的最小阻抗。

另外，路径的阻抗应等于它途径的各个流向的阻抗之和：

∑∑∈=j i H h rs k

ijh ijh ijh rs k ij

x t c ,,)(δ （9）把式（6d ）、（6e ）代入（6a ），消去（6a ）中的x ij 和x ijh ，使目标函数变成以f =(…,rs k f ,…)为自变量的函数：Z [X (f )]。根据非线性规划理论，由模型（6a ）—（6c ）构造Lagrange 函数：

∑∑∑∑∈--+=s

r k

rs W k rs k

rs k rs k rs rs rs

f v f q u f X Z L ,)()]([ （10）

其中，是rs u 、rs k v 是Lagrange 乘子。根据Kuhn —Tucher 条件，L 在极值点必须满足下列条件：

0=??rs

f L ， 0=rs k rs k f v ， 0≥rs

k v （11）由于 rs k n m l mn l

mn mn rs k rs k rs k v f q u f f Z f L -??

? ??-??

+??=??∑∑, rs k

m l mn l mn mn

rs k ijh rs

ijh ijh v f q u

f f x x Z -??

? ??-??+????=∑∑∑, （12）

)()()(d )(d )(,0

,0ijh ijh ijh ijh ij ij j i H h x ijh j i x ij ijh

ijh x t x d x r w w d w w r x x Z ij ijjh

ij =+=???

?????+??

=??∑∑?∑?∈ （13）

rs k

ijh rs

ijh f

x ,δ=?? （14）另外，式（12）第二项中， ??

?====??其它

若,

0,,,

1k l s n r m f f rs k mn l

故第二项简化成

∑∑-=??

? ??-??n m rs l mn l

mn mn rs k u f q u f , （15）将式（13）、（14）、（15）代入式（12），并注意到式（9），得：

rs k rs rs k ijh rs k rs rs k ijh ijh rs

k v u c v u t f L --=--=??∑,δ （16）根据式（11），得

0=--rs k rs rs k v u c ， 0=rs k rs k f v ， 0≥rs

k v （17）

由此知

1）当0>rs k f 时，必有0=rs k v ，从而0)(=-rs rs k u c （18a ）

2）当0=rs k f 时，有0≥rs k v ，从而0)(≥-rs rs k u c （18b ）

以上式（11）~（18）对任意的k 、r 、s 都成立。

易见，式（18）与式（8）是等价的。因此，我们提出的模型（6）的解等价于Wardrop 均衡原理。证毕。

4.2 解的唯一性

对目标函数求导：

)()()()(ijh H l ijl ijh ij ijh

x d x r x d x r x Z ij

+=+=??∑∈

)(')('2

ijh ij ijh

x d x r x Z +=??

ij ij ijl

ijh H l h x r x x Z

∈=???,)

('2

故雅可比矩阵为：

??????

?????????+++=?

212

''''0''''0

''''0

0)(ij ij ij

ij ij ij ij ij ij

ij ij d r r r r d r r r r d r X Z （19）在该矩阵中，处于对角线位置的是若干个二维（对应于三枝交叉口）或三维（对应于四枝交叉口）对称（子）方阵，其它元素均为0。易证对角线上这些子方阵都是正定的，其中二维子方阵的行列式为：)(')(')](')(')[('2121ij ij ij ij ij x d x d x d x d x r ?++，三维子方阵的行列式为：

)(')(')(')](')(')(')(')(')(')[('321133221ij ij ij ij ij ij ij ij ij ij x d x d x d x d x d x d x d x d x d x r +++，由上面2目对阻抗函数

的分析知，)(ij x r 是x ij 的严格单调递增函数、)(ijh x d 是x ijh 的严格单调递增函数，故所有的)('ij x r 和)('ijh x d 都大于0，从而上面二维和三维子方阵都为正。所以，雅可比矩阵为：)(2X Z ?是正定的，模型（6）中的目标函数Z 是严格凸函数。又由于（6）中的约束条件都是线性的，因此（6）是一个凸规划模型，根据非线性规划理论，它的最优解是唯一的。

5 算法

1975年由Leblanc 等学者将Frank-Wolfe 算法用于求解Bechmann 模型，现在也考虑用F-W 算法解模型（6）。首先简要介绍F-W 算法。

F-W 法适用于某些约束条件为线性的凸规划问题，是用线性规划逐步迭代逼近非线性规划的方法。在每步迭代中，先找到一个目标函数的最速下降方向，然后再找到一个最优步长，在最速方向上截取最优步长得到下一步迭代的起点，重复迭代直到找到最优解。

设非线性规划模型：

)(:min X f Z = 0,≥=X B AX 其中，X 、B 是向量，A 是矩阵。

f (X )在X 0处的一阶泰勒展开))(()()(000X X X f X f X f -?+=将f (X )近似地表达成线性函数，目标函数变为))(()(000X X X f X f Z -?+=，去掉目标函数中的常数项，这等价于线性规划：

X X f Z )(:min 0?= （20a ） s . t . 0,≥=X B AX （20b ）解该线性规划问题，得最优解Y 。F-W 方法认为X 0与Y 的连线为最速下降方向，故只须解一维极值问题 )]([:min 00X Y X f -+λλ

，将其最优解λ作为步长，即令)(001X Y X X -+=λ，

而得到下一步迭代的起点X 1。如此循环，直至X n 与X (n +1)十分接近为止。

由上可见，该法在每次迭代时都要求解一组线性规划问题的解，我们知道，求解线性规划的通用的单纯型法计算量很大，故在一般情况下，F-W 方法因计算量太大而不适用。只有当以

上的近似线性规划问题易于求解时，该法才有价值。

设迭代起点为X n ，对应于式（20）的目标函数为

∑∑∈??=?=ij H h ijh ijh n

y x X Z Y X Z Y Z )()()( 由式（13）可知n ijh n ijh ijh ijh t x t x Z ==??)(，上式可变换为∑∑∈=ij H h ijh ijh n ij

y t Y Z )(，因此，在每次迭

代中的线性规划问题为

∑

∑∈=ij H h ijh ijh

n ij

y t

Y Z )(:min （21a ）

s . t . :s r q g rs k

rs k ,,

?=∑ （21b ） s r g rs

k ,,

0?≥ （21c ）

其中，ij s

r k

rs k

ijh rs k ijh H h j i g y ∈??=∑∑,,,,δ ；

y ijh ——第n 次迭代时流向(i, j, h )的附加的流量; rs k g ——第n 次迭代时路径k 的附加的流量。

以上各式中，n ijh t 只与n ijh x 有关，与ijh y 无关数，因此，该模型实际上是在各路段阻抗为常值

的情况下网络总阻抗最小的交通分配问题。这只要将 OD 量全部沿OD 点对间的最短路径上

分配即可使目标函数最小化，而这正是全有全无分配方法。因此线性规划问题（21）可以通过一次全有全无分配而简单地解出，而不必象用单纯形法经过繁杂的求解步骤，这一点使得F-W 方法在求解均衡分配模型（6）变得有应用价值。

用全有全无分配方法求得模型（21）求出的解),,( n ijh y Y =，得最速下降方向（X n -Y n ）

，剩下的就是确定最佳迭代步长的问题了。迭代步长λ由下式决定：

∑

∑?

∈-+-++=j i H h x y x ijh j

i x y x ij ij

ijh n ijh n ijh n

ij n ij n ij

w w d dw w r Z ,)

d )()()(:min λλλ

λ （22）

如果直接令0=??λ

Z ，用解此方程得到的λ作迭代：)(1n

ijh n ijh n ijh n ijh x y x x -+=+λ可能会使某些1+n ijh

x 可能为负值，这就不合乎实际了，因为实际上路段上的流量最少为0，不可能为负值。因此首先应该对λ确定一个合理的取值范围。现分别用λtop 、λbot 表示合理取值的上、下限，首先令

top =1000,λbot =-1000。合理的λ

应该保障：

),,(0

)(ij n

ijh n ijh n ijh H h j i x y x ∈?≥-+λ

式中)(n ijh n ijh x y -可能取正值、零、负值。当0)(>-n ijh n ijh x y 时，λ应该)/(n

ijh n ijh n ijh y x x -≥，如目前

)/(n ijh n ijh n ijh bot y x x -<λ，则应让)/(n ijh n ijh n ijh bot y x x -=λ；当0)(<-n ijh n ijh x y 时，λ应该

)/(n ijh n ijh n ijh y x x -≤，如目前)/(n ijh n ijh n ijh top y x x ->λ，则应让)/(n

ijh n ijh n ijh top y x x -=λ。对每个（i, j, h ）

，

做以上工作，最后得到一个尺度最小的λ合理取值范围：[λ

bot ,λtop ]。

令：λλ??=/)(Z f ，则

()

∑

∑∑∈-+?-+-+?-=j i H h n ijh n ijh n ijh ijh n ijh n

ijh j

i n

ij n ij n ij ij n ij n ij ij

x y x d x y

x y x r x y f ,,)()()()()(λλλ

()

∑

∑∑∈-+?-+-+?-=j i H h n ijh n ijh n ijh ijh n ijh n

ijh j

i n

ij n ij n ij ij n ij n ij ij

x y x d x y

x y x r x y f ,2,2)(')()(')()('λλλ

由上面第2目分析知，对所有的流向(i, j, h )，0)('>?ij r ，0)('>?ijh d ，故0)('>λf ，)(λf 是严格单调递增函数，)(λZ 是严格凸函数。总共有图1所示的三种情况（一般情况下，)(λf 不一定是直线，为简单计，这里将它画成直线）：

bot top bot top

bot top

(1) (2) (3) 图1 [λbot ,λtop ]的三种情况

在第一种情况下，取λ=λ

top

就使目标函数Z (λ)达到最小值；在第三种情况下，取λ=λ

bot 就使目标函数

Z (λ)达到最小值。这两种情况下，λ??/Z 都不为0。只有第二种情况下，才须

用二分法求解方程0/=??λZ 。

综上所述，均衡分配方法的步骤可归纳为：算法7-8：

步1、初始化：按照)0()0(0

ijh ij ijh d r t +=，实行一次全有全无分配，得到各路段的流量，

);,(1

ij ijh H h j i x ∈??；令 n =1。

步2、更新各路段的阻抗：)()(n

ijh ijh n ijh ij n ijh x d x r t += );,(ij H h j i ∈??。

步3、寻找下一步迭代方向：按照};,:{ij n ijh H h j i t ∈??实行一次全有全无分配，得到一组

附加的流量);,(ij n

ijh H h j i y ∈??。

步4、确定迭代步长λ：

4-1 确定λ合理取值范围：[λbot ,λtop ]；

4-2 f (λtop )<0时，让λ=λtop ； 4-3 f (λ

bot )>0

时，让λ=λ

bot ；

4-4 用二分法求方程0/=??λZ ，得解λ。

步5、确定新的迭代起点：)(1n

ijh n ijh n ijh n ijh x y x x -+=+λ。

步6、合乎收敛条件则停止计算；否则，令n =n +1，返回第2步。算法结束。

5 算例

假设一个城市道路网络如图2，其中1、4、7、9、12是出行发生点，也是交叉口，其它节点都只是交叉口；流量分布矩阵如表1，其中走行时间公式中的参数α=1.0, β=4.0（对?i 、j ），0流量走行时间—— r ij (0): r 12, r 34, r 56, r 59, r 78, r 8 12=50 (s)

r 15, r 26, r 37, r 48, r 6 10, r 7 11, r 9 10, r 11 12 =45 (s) r 23, r 67, r 10 11 =40 (s)

路段通行能力——e ij =3000(PCU/h) （对?i 、j ）流向绿信比

四肢：左转= 0.15，直行=0.30，右转=1.0 三肢：左转= 0.45，右转=1.0

流向饱和流量——s ij =2000(PCU/h) （对?i 、j 、h ）周期——c j =80(s) （对?j ）

根据上述算法在VB6.0上编制程序，运行得出结果是：各路段流量如表2，各交叉口分流向的流量如表3。

1 4

5 8

图2 算例中的道路网络

5 结语

本文提出了流向、流向阻抗、流向流量的概念，给出了包含交叉口分流向延误的阻抗公式（4），和基于新阻抗公式的交通均衡分配模型（6），并证明了该模型等价于Wardrop第一均衡分配原理。这个模型真正描述了城市道路网络上的交通分配情况。以后要进一步研究的问题是探讨这个模型的解法。

参考文献

[1] 刘灿齐（2001）.现代交通规划学.北京：人民交通出版社

[2] 刘灿齐（2002），考虑各流向车流在交叉口延误的最短路径及算法，同济大学学报，2002（1）

[3] LIU Canqi（2002）Algorithm of shortest path special for urban road network—Based on delay of each flow at intersection. Transportation Science.

[4] 李旭宏（1997）.道路交通规划.南京：东南大学出版社

最优化理论与算法(第八章)

第八章约束优化最优性条件 §8.1 约束优化问题一、问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=?L L （8.1）特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。记 {} 1()0 (1,,);()0 ,,i e i e X x c x i m c x i m m +===≥=L L ，称之为可行域（约束域）。 {}1,,e E m =L ，{}1,,e I m m +=L ，{}()()0 i I x i c x i I ==∈ 称()E I x U 是在x X ∈处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。应该指出的是，如果x * 是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x *> 则将此约束去掉，x * 仍是余下问题的局部最优解。事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ*-<，且()()f x f x δ*<，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小点矛盾。因此如果有某种方式，可以知道在最优解x * 处的积极约束指标集()()A x E I x * *=U ，则问题可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x *∈ （8.2）一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。

流线优化模型与算法研究及应用

配套的处理方式；果蔬采后商品化处理量几乎达到了100％，形成了完整的果蔬冷链体系。而我国的产地基础设施不完善，未能解决分选、分级、预冷、冷藏运输和保鲜等采后果蔬的处理问题。我国果蔬冷链存在许多问题：产地预冷环节薄弱；冷藏运输工具落后；冷库发展水平低；缺乏有影响力的第三方冷链物流。我国果蔬冷链发展水平要赶上发达国家还有较长的路要走。要完善我国的果蔬冷链业，除了大力研发性价比合理、符合国情的相关冷链设备、设施以外；还需要全面的对整个果蔬冷链过程中存在的影响果蔬产品质量的风险因素进行分析和评价，从而一一破解；更需要系统地梳理整个果蔬冷链链条，是指实现协同化，构建果蔬冷链质量质量保障体系。这样才能真正确保果蔬产品的质量安全，确保千万消费者食用上安全放心的果蔬产品。流线优化模型与算法研究及应用张锦*（交通与物流学院） 1 研究背景目前我国物流产业正处于高速发展期，理论体系与应用研究正在不断完善。物流活动的目的就是使物流服务来满足物流需求，即通过仓储、加工、运输、配送、包装、装卸搬运等活动来满足社会经济活动中供应商、制造商、零售商、消费者等需求方的对物的移动、储存与服务的需求。在宏观层面的区域及城市经济和微观层面的制造、贸易、消费等典型社会经济活动中的物流活动可抽象为具有特定需求的空间结构，称作物流需求网络。在物流系统中，由若干特定的点、线和特定的权构成的，反映物流服务与需求关系的供需网络称之为流线网络，它具有以下典型特征。 1．反映了仓储、加工、运输、配送、包装、装卸搬运等物流服务与需求方在物品数量、到达时间、物流费用等方面的物流需求间的供需关系。 2．具有嵌套、多层、多级、多维、多准则、拥塞等典型的超网络结构特征，并且具有连接供需两个物流网络的超网络结构。 3．当实际需求为特定值时，物流服务追求的目标为用恰当的费用，在恰当的时间把恰当数量的恰当物品，经恰当的路线送到恰当的地点。物流供应网络与物流需求网络之间的关系可由超网络结构进行刻画，用匹配度刻画物流服务与物流需求之间的适应程度。 2 国内外研究现状目前，国内外学者对流线的组织与优化问题研究较少，与此问题相关的内容包括物流网络、物流网络分配、动线优化、超网络理论与应用、变分不等式算法及其在供应链网络中的应用等内容。 2.1 物流网络研究现状国外的学者大都倾向从微观的企业角度去研究物流网络的资源配置和协调问题,如物流基础设施、市场竞争机制以及配送运输等问题。这类研究大多利用数学规划法、系统仿真法、启发式 *作者简介：张锦，男，教授。

基于数学模型的网络优化方法研究

基于数学模型的网络优化方法研究赵鹏通信一团技术室摘要为了提高网络链路的利用率，解决网络传输中的最大流问题，该文利用建立数学模型的方法来求解网络的传输路径，研究了基于路径的网络优化方法。该方法能够极大地提高网络的链路利用率，从而降低网络的拥塞，使得网络的性能得到较大改善。关键词网络优化最大流数学模型 1 引言随着网络技术的进步和人们对多媒体综合业务需求，传统的数据网络逐渐转向多媒体网络，在这过程中，除了相关服务以外，我们还面临许多极具战性的网络设计和优化问题。网络优化的目标是提高或保持网络质量，而网络质量是各种因素相互作用的结果，随着网络优化工作的深入开展和优化技术的提高，优化的范围也在不断扩大。在计算机网络优化设计中，各条链路的容量分配和各节点间的路由选择是两个重要问题。在给定网络拓扑结构和各节点间传输流量的条件下，如何确定各条链路的容量大小和选择各节点间的最佳路由，使整个网络成本费用最低并能满足规定的性能指标呢？许多网络优化的文献，研究针对CDMA 网络、GPRS 网络、GSM 网络、PHS 网络等具体网络在投入运行后，对网络进行参数采集、数据分析，找出影响网络质量的原因，通过技术手段或参数调整使网络达到最佳运行状态，涉及到交换网络技术、无线参数、小区参数配置、信令和设备技术等方面。本文针对目前许多网络传输链路和网络设备没有得到充分利用，从而影响网络性能的问题，利用网络优化方法从理论上进行分析，研究了用于提高网络链路利用率的基于路径的网络优化方法，该方法能够充分地利用网络链路进行流量传输，从而改善网络的整体性能。 2 网络优化理论很多情况下可以将网络优化问题转化成数学问题进行研究和分析。从根本上讲，优化问题包含三个基本要素：决策变量集合或向量：n R x ∈（本文，x 代表在一条或多条路径上的流量）目标函数R R x f n →:)( 一组约束条件g(x)和h(x)，用来定义x 的范围。解决优化问题实际上就是找出一个点x*，使得f(x)最大化或最小化。典型的网络优化问题包含找出一组路由和该路由上的流量值以便达到最大或最小化目标函数的目的。目标函数可以代表最大链路利用率、平均延迟或其他指标。基于路径的问题首先要计算出网络流可能流经的路径，要最大限度的利用网络链路，同时路径上的流量不能超过链路容量。对于基于路径的网络优化问题可以简单表示成： max f(x) s.t. ∑∈=P p p b x

交通分配之用户均衡分配模型二(matlab源码)

例总流量为100,走行函数为： ??? ??+=40)(6.04)(111t x x c ?? ? ??+=40)(9.06)(222t x x c ?? ? ??+=60)(3.02)(333t x x c ??? ??+=40)(75.05)(444t x x c ?? ? ??+=40)(45.03)(555t x x c 模型求解的Matlab 源码： syms lambda ; tt =[0 0 0 ]; xx = [0 0 0 0 0] ; t1 = 4 + (0.6/40)*xx(1,1); t2 =6 + (0.9/40) *xx(1,2); t3 = 2 + (0.3/60) *xx(1,3); t4 = 5 + (0.75/40) *xx(1,4) ; t5 = 3 + (0.45/40) *xx(1,5) ; Q = 100; N=8 ; % 迭代次数，本例只设置最大迭代次数。也可另外设置收敛条件 tt(1,1)= t1 +t4 ; tt(1,2) = t2 + t5 ; tt(1,3) =t1+ t3 +t5 ; y = [0 0 0]; %置初值 Min = 50000; for j = 1 : 3 if tt(1 ,j)

% y(1,index) = Q; if index ==1 xx(1,1)= Q; xx(1,4)=Q; elseif index ==2 xx(1,2)= Q; xx(1,5)=Q; else xx(1,1)= Q; xx(1,3)=Q; xx(1,5)=Q; end for i =1 :N y = [0 0 0 0 0 ]; t1 = 4 + (0.6/40)*xx(1,1); t2 =6 + (0.9/40) *xx(1,2); t3 = 2 + (0.3/60) *xx(1,3); t4 = 5 + (0.75/40) *xx(1,4) ; t5 = 3 + (0.45/40) *xx(1,5) ; tt(1,1)= t1 +t4 ; tt(1,2) = t2 + t5 ; tt(1,3) =t1+ t3 +t5 ; fprintf('第%d 次迭代的路径时间值：' , i); tt Min = 50000; for j = 1 : 3 if tt(1 ,j)

遗传算法优化的BP神经网络建模[精选.]

遗传算法优化的BP神经网络建模十一月匆匆过去，每天依然在忙碌着与文档相关的东西，在寒假前一个多月里，努力做好手头上的事的前提下多学习专业知识，依然是坚持学习与素质提高并重，依然是坚持锻炼身体，为明年找工作打下基础。遗传算法优化的BP神经网络建模借鉴别人的程序做出的仿真，最近才有时间整理。目标：对y=x1^2+x2^2非线性系统进行建模，用1500组数据对网络进行构建网络，500组数据测试网络。由于BP神经网络初始神经元之间的权值和阈值一般随机选择，因此容易陷入局部最小值。本方法使用遗传算法优化初始神经元之间的权值和阈值，并对比使用遗传算法前后的效果。步骤：未经遗传算法优化的BP神经网络建模 1、随机生成2000组两维随机数(x1,x2)，并计算对应的输出y=x1^2+x2^2，前1500组数据作为训练数据input_train，后500组数据作为测试数据input_test。并将数据存储在data中待遗传算法中使用相同的数据。 2、数据预处理：归一化处理。 3、构建BP神经网络的隐层数，次数，步长，目标。 4、使用训练数据input_train训练BP神经网络net。 5、用测试数据input_test测试神经网络，并将预测的数据反归一化处理。 6、分析预测数据与期望数据之间的误差。遗传算法优化的BP神经网络建模 1、读取前面步骤中保存的数据data； 2、对数据进行归一化处理； 3、设置隐层数目； 4、初始化进化次数，种群规模，交叉概率，变异概率 5、对种群进行实数编码，并将预测数据与期望数据之间的误差作为适应度函数； 6、循环进行选择、交叉、变异、计算适应度操作，直到达到进化次数，得到最优的初始权值和阈值； 7、将得到最佳初始权值和阈值来构建BP神经网络； 8、使用训练数据input_train训练BP神经网络net; 9、用测试数据input_test测试神经网络，并将预测的数据反归一化处理； 10、分析预测数据与期望数据之间的误差。算法流程图如下：

最优化理论与算法 fibonacci法

function [a,b,n,x]=fibonacci(fname,a,b,d,L) % fname函数句柄，d辨别常数，L最终区间长度a(1)=a; b(1)=b; F=zeros(1,10); %选择fibonacci数列k值为10，可任意更改 F(1)=1; F(2)=2; for k=2:10 %k取到10，生成fibonacci数列 F(k+1)=F(k)+F(k-1); F(k); end Fn=(b(1)-a(1))/L; Fk=[F Fn]; N=sort(Fk); n=find(Fn==N); %查找计算函数值的次数n t(1)=a(1)+F(n-2)*(b(1)-a(1))/F(n); %计算试探点t(1),u(1) u(1)=a(1)+F(n-1)*(b(1)-a(1))/F(n); for k=1:n-2 ft=feval(fname,t(k)); fu=feval(fname,u(k)); if ft>fu a(k+1)=t(k); b(k+1)=b(k); t(k+1)=u(k); u(k+1)=a(k+1)+F(n-k-1)*(b(k+1)-a(k+1))/F(n-k); while k==n-2 t(n)=t(n-1); u(n)=t(n-1)+d; ft=feval(fname,t(n)); fu=feval(fname,u(n)); if ft>fu a(n)=t(n); b(n)=b(n-1); else a(n)=a(n-1); b(n)=t(n); end end else a(k+1)=a(k); b(k+1)=u(k); u(k+1)=t(k); if k~=n-2 t(k+1)=a(k+1)+F(n-k-2)*(b(k+1)-a(k+1))/F(n-k); ft=feval(fname,t(k));

图论与网络优化课程设计_Matlab实现

图论与网络优化课程设计四种基本网络（NCN、ER、WS、BA）的构造及其性质比较摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。

四种基本网络（NCN、ER、WS、BA）的构造及其性质比较 1.概述 1.网络科学的概述网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 2.最近邻耦合网络的概述如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每K个邻居节点相连，这里K是一个偶数。这类网络的一个重要特征个节点都与它左右各/2 就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。 NCN的Matlab实现： %function b = ncn(N,K) %此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络 %返回结果b为该最近邻耦合网络对应的邻接矩阵 function b = ncn(N,K) b=zeros(N); for i = 1:N for j = (i+1):(i+K/2) if j<=N b(i,j)=1; b(j,i)=1; else b(i,j-N)=1;

基于有限理性的方式划分和交通分配组合模型

基于有限理性的方式划分和交通分配组合模型出行者作为城市交通系统的主体,其出行行为影响整个网络的运行效果。传统的出行行为研究通常假定出行者是绝对理性的,其决策行为遵循效用理论,以出行阻抗最小或者效用最大作为决策依据,很少考虑出行者的有限理性特点。本文以出行者的出行行为为研究对象,结合问卷调查标定前景理论的参数体系,在有限理性的框架下讨论方式选择和路径选择行为,并建立方式划分和交通分配组合模型,最后通过算例分析组合模型的特点、出行者参考点依赖效应以及模型参数的敏感性。本文首先明确了有限理性的概念,详细介绍了前景理论和TODIM方法的基本观点以及相关研究和应用。随后对比了前景理论中不同函数形式的差异,分析了前景理论各个参数的内涵,将出行者或者出行情景按照风险水平高低划分为3类,并通过问卷调查得到了前景理论在出行路径选择问题中的参数体系,同时验证了该参数体系的有效性。紧接着结合离散选择模型和TODIM方法提出了有限理性条件下的方式划分模型,结合离散选择模型和前景理论提出了有限理性条件下的随机交通分配模型,最终在有限理性的基础之上提出了改进的方式划分和交通分配组合模型。最后,利用Nguyen & Dupuis网络作为算例,验证组合模型的有效性研究结果表明,组合模型能够体现总出行需求对私家车出行选择概率的影响,两者呈负相关的关系；私家车的实际出行需求、出行者对不同路径的感知具有明显的参考点依赖效应,而出行者路径选择行为的参考点依赖效应不显著；私家车的实际出行需求随着参数θ的增大而减小,各条路径之间的差异随着参数κ的增大而增大, 参数θ可在(0,6)中取值,参数K可在(0,1)之间取值。

基于遗传算法的参数优化估算模型

基于遗传算法的参数优化估算模型【摘要】支持向量机中参数的设置是模型是否精确和稳定的关键。固定的参数设置往往不能满足优化模型的要求，同时使得学习算法过于死板，不能体现出来算法的智能化优点，因此利用遗传算法（Genetic Algorithm，简称GA）对估算模型的参数进行优化，使得估算模型灵活、智能，更加符合实际工程建模的需求。【关键词】遗传算法；参数优化；估算模型 1.引言随着支持向量机估算模型在工程应用的不断深入。研究发现，支持向量机算法(包括LS-SVM算法)存在着一些本身不可避免的缺陷，最为突出的是参数的选取和优化问题，以往在参数选取方面，一般依靠专家系统或者设定初始值盲目搜寻等等，在实际应用必然会影响模型的精准度，造成一定影响。如何选取合理的参数成为支持向量机算法应用过程中应用中关注的问题，同时也是目前应用研究的重点。而常用的交叉验证试算的方法，不仅耗时，且搜索目的不清，使得资源浪费，耗时耗力。不能有效的对参数进行优化。针对参选取的问题，本文使用GA算法对模型中的参数设置进行优化。 2.遗传算法 2.1 遗传算法的实施过程遗传算法的实施过程中包括了编码、产生群体、计算适应度、复制、交换、变异等操作。图1详细的描述了遗传算法的流程。其中，变量GEN是当前进化代数；N是群体规模；M是算法执行的最大次数。遗传算法在参数寻优过程中，基于生物遗传学的基本原理，模拟自然界生物种群的“物竞天则，适者生存”的自然规律。把自变量看作生物体，把它转化成由基因构成的染色体（个体），把寻优的目标函数定义为适应度，未知函数视为生存环境，通过基因操作（如复制、交换和变异等），最终求出全局最优解。 2.2 GA算法的基本步骤遗传算法操作的实施过程就是对群体的个体按照自然进化原则（适应度评估）施加一定的操作，从而实现模型中数据的优胜劣汰，使得进化过程趋于完美。从优化搜索角度出发，遗传算法可使问题的解，一代一代地进行优化，并逼近最优解。通常采用的遗传算法的工作流程和结果形式有Goldberg提出的，常用的GA 算法基本步骤如下： ①选择编码策略，把参数集合X和域转换为位串结构空间S。常用的编码方法有二进制编码和浮点数编码。 ②定义合适的适应度函数，保证适应度函数非负。 ③确定遗传策略，包括选择群体大小，选择、交叉、变异方法，以及确定交叉概率、变异概率等其它参数。 ④随机初始化生成群体N，常用的群体规模：N＝20～200。 ⑤计算群体中个体位串解码后的适应值。 ⑥按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体。 ⑦判断群体性能是否满足某一个指标，或者以完成预订迭代次数，若满足则

交通分配及其算法

V 为网络节点集，即：道路交叉点；A 为路段集，即：道路交通量—人的个数—OD 矩阵 ,a C a A ∈：路段a 的通行能力 ()a a t x ：路段a 的阻抗，a x 为流量，通常以时间记，假设仅与路段a 有关系统最优是系统规划者所期望得到的一种平衡状态，其前提是所有网络用户必须互相协作，遵从网络管理者的统一调度，所以是计划指向型分配准则。出行者的出行决策过程是相互独立的，路网上的交通流的状态是出行者独立选择的结果。出行者必然转向费用较小的路径.其结果，路网上的交通量分布最终必然趋于用户平衡状态。所以，用户平衡状态最接近实际的交通状态。 Wardrop 准则的提出标志着网络流平衡分配概念从描述转为严格刻画，不但假设司机都力图选择阻抗最小的路径，而且还假设司机随时掌握整个网络的状态，精确计算每条路径的阻抗，还假设了司机的计算能力与水平是相同的。在这些假设条件下进行的配流被称为确定性配流，得到的用户平衡条件被称为确定性平衡条件，简称UE 条件。User Equilibrium System Optimal rs k rs a f q ∑=且0rs k f ≥（rs k f —O-D 对r-s 之间路径k 上的流量）rs q 等于连接rs 之间各路径上的路段的交通量的总和。 ,rs rs a k a k r s k x f σ=∑∑∑（,rs a k σ—如果弧a 在连接O-D 对r-s 的路径k 上，其值为1，否则为0）路段a 上的流量等于通过a 的路径上分配到a 上的交通量的总和。 1. 目标函数本身并没有什么直观的经济含义或行为含义。 2. 没必要直接求解用户平衡条件方程组，平衡状态可以由求解等价都极小值问题得到。 3. 模型的解关于路段流量唯一，关于路径流不唯一 4. 等价性与唯一性证明略

最优化理论与算法

最优化理论与算法笔记在老师的指导下，我学习了最优化理论与算法这门课程。最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多方案中什么样的方案最优以及怎样找出最优方案。由于生产和科学研究突飞猛进的发展，特别是计算机的广泛应用，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此迅速发展起来形成一个新的学科。至今已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。整个学习安排如下，首先介绍线性与非线性规划问题，凸集和凸函数等基本知识及线性规划的基本性质；然后再这个基础上学习各种算法，包括单纯形法、两阶段法、大M 法、最速下降法、牛顿法、共轭梯度法等，以及各种算法相关的定理和结论；最后了解各种算法的实际应用。主要学习的基础知识： 1、一般线性规划问题的标准形式 1min n j j j c x =∑ 1 .., 1,...,, 0, 1,...,. n ij j i j j s t a x b i m x j n ===≥=∑ 学会引入松弛变量将一般问题化为标准问题；同时掌握基本可行解的存在问题，通过学习容易发现线性规划问题的求解，可归结为求最优基本可行解的问题。 2、熟练掌握单纯形法、两阶段法和大M 法的概念及其计算步骤。单纯形法是一种是用方便、行之有效的重要算法，它已成为线性规划的中心内容。其计算步骤如下： 1）解,B Bx b =求得1B x B b b -==，令0,N x =计算目标函数值B B f c x =；

2)求单纯形乘子ω，解B B c ω= ，得到1B c B ω-=； 3)解k k By p =，若0k y ≤，即k y 的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤（4）； 4)确定下标r ，使min{0}r r rk rk rk b b y y y =>，得到新的基矩阵B ，返回第一步。两阶段法：第一阶段是用单纯形法消去人工变量，即把人工变量都变换成非基变量，求出原来问题的一个基本可行解；第二阶段是从得到的基本可行解出发，用单纯形法求线性规划的最优解。大M 法：在约束中增加人工变量a x ，同时修改目标函数，加上罚项T a Me x ，其中M 是很大的正数，这样，在极小化目标函数的过程中，由于M 的存在，将迫使人工变量离基。 3、掌握最速下降法的概念及其算法，并且能够讨论最速下降算法的收敛性。掌握牛顿法，能够熟练运用牛顿迭代公式：(1) ()2()()()()k k k k x x f x x x +=-?- ，掌握共轭梯度法及其相关结论，以及其收敛性的讨论，掌握最小二乘法及其基本步骤。最速下降法：迭代公式为(1) ()()k k k k x x d λ+=-。计算步骤：1）给定点(1)n x R ∈，允许误差0,ε>臵1k =； 2）计算搜索方向() ()()k k d f x =-?； 3）若() k d ε≤，则停止计算，否则，从()k x 出发，沿()k d 进行一维搜索，求k λ，使()()()() ()min ()k k k k k f x d f x d λλλ≥+=+； 4）令(1) ()()k k k k x x d λ+=-，臵:1k k =+，转步骤（2）。

数学建模常用算法模型

按模型的数学方法分：几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等按模型的特征分：静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等按模型的应用领域分：人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。按建模的目的分：预测模型、优化模型、决策模型、控制模型等一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应按对模型结构的了解程度分：有白箱模型、灰箱模型、黑箱模型等比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。按比赛命题方向分：国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策）数学建模十大算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）

3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理）算法简介 1、灰色预测模型（必掌握）

最优化理论与算法

最优化理论与算法（数学专业研究生）第一章引论 § 引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。二、最优化问题的一般形式 1、无约束最优化问题 min ()n x R f x ∈ （） 2、约束最优化问题 min () ()0, ..()0, i i f x c x i E s t c x i I =∈?? ≥∈? （）这里E 和I 均为指标集。 §数学基础一、范数 1. 向量范数 max i x x ∞= （l ∞范数）（） 11n i i x x ==∑ （1l 范数）（） 122 21 ()n i i x x ==∑ （2l 范数）（）

11 ()n p p i p i x x ==∑ （p l 范数）（） 12 ()T A x x Ax = （A 正定）（椭球范数）（）事实上1－范数、2－范数与∞-范数分别是 p －范数当 p ＝1、2和p →∞时情形。 2．矩阵范数定义方阵A 的范数是指与A 相关联并记做A 的一个非负数，它具有下列性质： ① 对于0A ≠都有0A >，而0A =时0A =； ② 对于任意k R ∈，都有kA k A =； ③ A B A B +≤+； ④ AB A B ≤；若还进一步满足： ⑤ p p Ax A x ≤ 则称之为与向量范数p g 相协调（相容）的方阵范数。若令 max x Ax A x ≠= （这里x 是某一向量范数）（）可证这样定义的范数是与向量范数g 相协调的，通常称之为由向量范数g 诱导的方阵范数。特别地，对方阵()ij n n A a ?=，有： 11max n ij j i A a ==∑（列和的最大者）（） 1 max n ij i j A a ∞ ==∑（行和的最大者）（） 1 22()T A A A λ=（T A A λ表示T A A 的特征值的最大者）称为谱范数（注：方阵A 的特征值的模的最大者称为A 的谱半径，记为()A ρ）。对于由向量诱导的方阵范数，总有：

(完整版)DTA动态交通分配

(2005) 西安交通大学对具有排队的多模式动态交通分配问题及其相关应用进行研究。本文对动态交通分配模型发展进行了介绍和总结，并详细讨论了模型中的路段动态函数、流量传播约束、FIFO等相关特性。将单一交通模式的点排队路段动态模型扩展到多模式动态路段模型，并且证明了各种模式的路段行程时间函数合乎模式内的FIFO特性，以及在拥挤情况下各模式车辆的速度收敛特性。将多模式随机动态同时的路径与出发时间选择平衡条件描述为变分不等式问题，提出了两个不同的算法用于求解变分不等式问题：算法一是基于路段的算法，这个算法给出了基于logit的同时的路径与出发时间选择的随机动态网络配载方法，并证明了这个方法的正确性；算法二是基于路径的启发式算法。仿真试验验证了模型以及两个算法的有效性。提出了多模式多用户动态交通分配模型，用于评估ATIS对不同模式出行者和交通系统的影响。将每一模式的出行者分为两类：一类是装配ATIS的出行者，另一类是未装配ATIS的出行者。由于所能获得的交通信息质量的差异，他们将遵循不同的动态用户平衡条件。同时，每一种模式出行者在选择路径和出发时间时，不但考虑出行费用和进度延误费用的影响，而且还考虑油耗费用的影响。将多模式多用户动态用户平衡条件描述为统一的变分不等式问题，利用对角化算法计算相应的平衡流量状态，并通过仿真试验验证了模型与算法的有效性。使用nested-logit模型模拟ATIS的市场渗透率与服从率，模型的上层模拟了驾驶小汽车出行者的购买行为(市场渗透率)，底层主要描述了装配ATIS设备的小汽车出行者的服从行为(服从率)。设计了固定点算法计算ATIS的平衡市场渗透率与服从率。并在简单的路网上进行了仿真研究，结果证明算法与模型是正确和有效的。提出了组合模式动态交通分配模型，模型中假设有两类出行者：一类是纯模式出行者，他们自己驾驶小汽车完成一次出行。另一类是组合模式出行者，在其一次出行的第一部分是自己驾驶小汽车完成的，剩余部分是乘公交车完成的。使用nested-logit模型模拟出行者的复杂出行选择行为。将各种不同的选择行为描述为一个变分不等式问题。并给出了启发式算法求解相应的变分不等式问题。最后，利用仿真研究验证了模型与算法的有效性。交通分配： (2005)所谓交通分配是指按照一定的原则，将各OD (Origin-Destination)对间的出行量分配到具体的交通网络上去，从而得到各路段的交通量，以判断各路段的负荷水平。近半个世纪以来，国内外学者对交通分配问题进行了大量的研究，提出了不少交通流分配模型与软件。总体来看，这些模型可以分为两大类: 平衡分配模型：遵循War drop用户最优(UO, User Optimum)准则或系统最优(SO, System Optimum)准则。它们或者使得个别交通参与者的出行费用最低，或者使得交通网络上所有出行者的总出行费用最低。非平衡分配模型：运用启发式解法或其他近似解法的分配模型则统称为非平衡分配模型，如全有全无分配模型、容量受限分配模型、多路径概率分配模型、随机分配模型和嫡分配模型等。静态模型不能反映交通流的时变特性，相反，动态交通分配考虑了交通需求随时间变化和出行费用随交通负荷变化的特性，能够给出瞬间的交通流分布状态。 DTA（Dynamic Traffic Assignment）所谓动态交通分配, 就是将时变的交通出行合理分配到不同的路径上, 以降低个人的出行费用或系统总费用。动态交通分配是在交通供给状况以及交通需求状况均为已知的条件下, 分析其最优的交通流量分布模式, 从而为交通流管理、动态路径诱导等提供依据。交通供给状况：网络拓扑结构、网段特性、既定控制策略等。

交通流分配模型综述

华中科技大学研究生课程考试答题本考生姓名陈菀荣考生学号M201673159 系、年级交通运输工程系、研一类别科学硕士考试科目交通流理论考试日期2017 年 1 月10日

交通流分配模型综述摘要：近些年，交通流分配模型已经广泛应用到了交通运输工程的各个领域，并且在交通规划中起到了很重要的作用。本文对交通流分配模型研究现状进行了综述，并分别对静态交通流分配模型、动态分配模型以及公交网络进行了阐述和讨论。同时对相关的交通仿真还有网络优化问题研究现状进行了探讨。最后结合自身学习经验做出了一些评价和总结。关键词：交通流分配；模型；公交网络 0引言随着经济和科技的发展，城市化进程日益加快，城市也因此被赋予更多的工程，慢慢聚集大量的人口。而人口数量的增加而直接带来的城市出行量增加，不管是机动车出行还是非机动车出行量都相较以前增加了很多，从而引发了一系列的交通问题。因为在城市整体规划中，交通规划已经成为了十分突出的问题。在整个交通规划过程中，交通分配在其中占有很重要的地位，为相关公交路线，具体道路宽度规划等都有很大作用。 1交通流分配及研究进程 1.1交通流分配简介由于连接OD之间的道路有很多条，如何将OD交通量正确合理的分配到O 和D之间的各条路线上，是交通流分配模型要解决的首要问题。交通流分配是城市交通规划的一个重要组成部分也是OD量推算的基础。交通流分配模型分为均衡模型和非均衡模型。 1.2交通流模型研究进程以往关于交通流分配模型的研究多是基于出行者路径偏好的，主要有以Wardrop第一和第二原则为分配依据建立的交通分配模型，Wardrop第一原则假定所有出行者独立做出令自己出行时间最小的决策，最终达到纳什均衡的状态，此时的流量为用户最优解，在这种状态下，同一个起始点时间所有有流路径的通行时间相等，并且大于无流路径的通行时间；Wardrop第二原则假定存在一个中央组织者协调所有出行者的路径选择行为，使得所有出行者的总出行时间最小，对应的状态称为系统最优，此时分布的流量称为系统最优流。交通流分配模型最早要追述到Beckmann等[1]于1956年首先提出了满足

最优化理论与算法(第九章)

第九章二次规划 §9.1 二次规划问题称形如 1m in ()2 T T Q x x H x g x = + 1,,. 1,,T i i e T i i e a x b i m s t a x b i m m ?==??≥=+?? （9.1）的非线性规划问题为二次规划问题。对二次规划问题，有如下的最优性条件。定理9.1 设x *是（9.1）的局部极小点，则必存在乘子(1,,)i i m λ*= ，使得 1 0 1,, 0 1,,m i i i T i i i e i e g H x a a x b i m m i m m λλλ**=*** ?+=? ?? ??-==+????≥=+??? ∑ （9.2）且对于一切满足于： 0, ()T i d a i E I x * =∈ 的n d R ∈，都有0T d Hd ≥。注：1）上述定理的前后两部分分别对应于一、二阶的必要条件； 2）满足上述条件的d ，都有(,)d S x λ* * ∈； 3）当约束条件均为线性函数时，容易证明： (,)(,) (,F D x X S F D x X L F D x X * * *= =及(,)(,)S x G x λλ**** = 上面给出的是二次规划的必要性条件，下面给出充分性条件。定理9.2 设x * 是K-T 点，λ* 是相应的Lagrange 乘子，如果对满足 0 0 () 0 () 0 T i T i T i i d a i E d a i I x d a i I x λ* **?=∈?≥∈??=∈>? 且（9.3）的一切非零向量n d R ∈，都有0T d Hd >，则x * 是（9.1）的局部严格极小点。

城市均衡分配模型与算法

专适于城市道路网络的交通均衡分配模型刘灿齐同济大学道路与交通工程系，上海，200092 摘要：由于已有的均衡分配理论中的阻抗公式不包含车流在交叉口的延误，其研究成果并不真正适用于城市道路网络。本文提出了流向、流向阻抗、流向流量的概念，找到了包含交叉口分流向延误的阻抗公式、基于新阻抗公式的交通均衡分配模型。这个模型较真实地描述了城市道路网络上的交通分配情况。关键词：城市道路网络，流向，延误，阻抗公式，均衡分配 Traffic Equilibrium Assignment Model Special for Urban Road Network LIU Canqi Road & Traffic Department, Tongji University, Shanghai 200092 Abstract: The cost formula in the existing equilibrium theory does not include the delay time at nodes. So, the researching results of the theory are unsuitable for urban road network. The conceptions of traffic direction, cost on traffic direction, and volume on traffic direction are given. The cost formula including the delay time at nodes is expressed. At last, a new equilibrium assignment model based on the cost formula is posed, which is suitable for urban road network. Key words: Urban road network, Flow-direction, delay, cost formula, equilibrium assignment 关于交通分配，1952年Wardrop 提出了道路网均衡分配的概念，其定义是：在道路网的用户都知道网络的状态并试图选择最短路径时，网络会达到这样一种均衡状态，每对产生——吸引点（PA 点对）之间各条被利用的路径的走行时间都相等而且是最小的走行时间，而没有被利用的的路径的走行时间都大于或等于这个最小的走行时间。这条定义通常称为“Wardrop 的第一原理”，又叫“用户均衡原理”。 1956年，Bechmann 等提出了描述这个均衡问题的一个数学规划模型，1975年LeBlanc 等学者设计出了求解Bechmann 模型的算法，从而形成了现在的实用解法。Wardrop 原理——Bechmann 模型——Leblanc 算法这三点突破是交通分配问题研究的三个里程碑，也是现在交通分配理论的基础[1]。然而，这些均衡分配研究成果并不真正适合于城市道路网络。在交通均衡分配模型和算法中，路段阻抗函数是一个基本要素，LeBlanc 的算法中要求它单调递增。到目前为止，唯一公认的来自于实际观测的阻抗函数实例就是美国公路局（BPR ）的走行时间公式 ()[] βαa a a a a e x t x t /1)0()(+= （1）然而，这个公式是从市际公路观测得到的，对城市道路，只能描述车辆在路段部分的行驶时间。但城市道路网络上的车辆除了在路段部分要花费行驶时间外，在信号灯交叉口还往往要花时间

城市均衡分配模型与算法

最优化理论与算法(第八章)

流线优化模型与算法研究及应用

基于数学模型的网络优化方法研究

交通分配之用户均衡分配模型二(matlab源码)

遗传算法优化的BP神经网络建模[精选.]

最优化理论与算法 fibonacci法

图论与网络优化课程设计_Matlab实现

基于有限理性的方式划分和交通分配组合模型

基于遗传算法的参数优化估算模型

交通分配及其算法

最优化理论与算法

数学建模常用算法模型

最优化理论与算法

(完整版)DTA动态交通分配

交通流分配模型综述

最优化理论与算法(第九章)

最新数学建模常用算法模型资料

城市均衡分配模型与算法