最短路问题

最短路问题

摘要

若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，也是应用最广泛的问题之一。在实际生活应用中许多优化问题都可以使用这个模型。如管路铺设、线路安装、厂区布局和设备更新等。在运筹学的介绍中求最短路问题的方法有很多，在本次论文研究中，我们主要介绍几种已成熟的最短路问题求解的方法并运用Matlab软件进行数学建模对问题运用Floyd算法进行求解。

关键词：最短路问题;求解方法;Floyd法;MATLAB软件

THE PROBLEM OF SHORT-PATH PROBLEM

ABSTRACT

If the network each edge has a value (the length, cost, time, etc.), then find the two-node (usually the source node and well nodes) between the right and the smallest total path is the shortest path problem. The shortest path problem is a typical network theory to solve the problem is one of the most widely used one of the issues. Many applications in real life optimization problems can use this model. Such as pipeline laying, line installation, plant layout and equipment updates. In the introduction to operations research problems for the most short-circuit a lot, in this thesis, we introduce some of the most mature way to short-circuit problem solving and mathematical modeling using Matlab software using Floyd algorithm for the problem Solution

Key words: The shortest path problem;Solution;Floyd method;MATLAB software

目录

1 问题的提出 (1)

2 最短路问题 (1)

3 最短路问题解法介绍 (2)

3.1迪克施特拉(dijkstra)算法. (2)

3.2逐次逼近算法.............................. . (2)

3.3 Floyd算法.............................. (3)

4 问题假设 (3)

5 符号说明 (4)

6 模型的建立 (4)

6.1 模型的准备工作 (4)

6.2 建立模型 (5)

7 模型求解 (5)

8 模型验证及结果分析 (7)

8.1 模型验证 (7)

8.2 问题分析 (8)

参考文献 (9)

附录 (10)

1 问题提出

有9点S、

2

A、

3

A、

1

B、

2

B、

1

C、

2

C、T，各点之间的路程如下图所示，各

点到T的最短路。

2 最短路问题

运用运筹学中的最短路问题模型：设)

,

(E

V

G=为连通图，图中各边（

i

v，

j

v）有

权

ij

l（

ij

l=∞表示

i

v，

j

v间无边）。

s

v，

t

v为图中的任意两点，求一条道路u，使它是从s

v到

t

v的所有路中总权时最小的路。即：)

(u

l=∑

∈u

v

v

ij

i

i

l

)

,

(

最小。

最短路问题即两个指定定点之间的最短路径。下面通过一个例子来认识：

例如，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定的城镇间，找到一最短铁路线。以个城镇为图G的定点。两城镇间的直通铁路为图G相应两定点间的边，得到图G。对于G的每一边e，赋以一个实数)

(e

w一直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定

的两点

,v

u之间具有较小权的轨，这条轨叫做

,v

u间的最短路，它的权叫

,v

u间的距离，亦记作)

,

(

v

u

d。

5

6

7

7

49

6

8

6

5

8

3

3

6

C1

B1

C2

B2

A1

A2

A3

T S

6

3 最短路问题解法介绍

求最短路已有成熟的算法： 3.1 迪克施特拉(dijkstra)算法

其基本思路是按距0u 从近到远为顺序，依次求得0u 到G 各顶点间路程和距离，直到0v （或者直到G 的所有定点），算法结束。为避免算法重复并保留每一步的计算信息，采用了标号算法。下面是算法：

1）令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 2）对于每一个i S v ∈（i i S V S \=）用

)}()(),({m in uv w u l v l i

S u +∈

代替)(v l 。计算)}({min v l i

s u ∈，把得到这个最小值的一个定点记为1+i u ，令

}{11++=i i i u S S

1）若1-=V i ，停止。若1-

算法结束时，从0u 到各定点v 的距离由v 得最后一次标号)(v l 给出。在v 进入i S 之前的标号)(v l 叫T 标号，v 进入i S 时的标号)(v l 叫P 标号。算法是不断修改个顶点的T 标号，直到获得P 标号。若在算法运行过程中，将每一定点获得P 标号所由来的边在图上标明，则算法结束时，0u 至个顶点最短路也在图上标出来了。

这种算法只适用于全是正权的图。 3.2逐次逼近算法

算法的基本思路是基于以下事实：如果1v 到j v 的最短路总沿着该路从1v 先到某一点

i v ，然后再沿边（i v ，j v ）到达j v ，则1v 到i v 这条路必然也是1v 到i v 的最短路。若令j P 1

表示从1v 到j v 的最短路长，i P 1表示1v 到i v 的最短路长，则必有下列方程：

)

min(

1

1ij

i

j

l

P

P+

=

用迭代方法解这个方程。开始时令

j

j

l

P

1

)1(

1

=（j=1,2，………）

即用

1

v到

j

v的季节距离做初始解，若

1

v与

j

v间无边，则记

1

v，

j

v间的最短路长为+∞。

从第二步起，适用迭代公式

]

m i n[)1

(

1

)

(

1ij

k

i

k

j

l

P

P+

=-（k=2,3，……..）

求)(

1

k

j

P，当进行到第t步，若出现

)1

(

1

)

(

1

-

=t

j

t

j

p

p（j=1,2，…..，n）

则停止，)(

1

t

j

p（j=1,2，…..，n）即为

i

v点到各点的最短路长。

3.3Floyd算法

令网络的权矩阵为

n

m

ij

d

D

?

=)

(，

ij

l为

i

v到

j

v的距离。

其中

?

?

?

∞

∈

=

其他

当（E

v

l

d j

i

ij

ij

)

,

v

算法基本步骤为：

（1）输入权矩阵D

=

)0(

D。

（2）计算

n

m

k

ij

k d

D

?

=)

()(

)

(（k=1,2,3，…n）

其中]

,

min[)1

(

)1

(

)1

(

)

(-

-

-+

=k

kj

k

ik

k

ik

k

ij

d

d

d

d

（3）

n

m

n

ij

n d

D

?

=)

()(

)

(中元素)(n

ij

d就是

i

v到

j

v的最短路长。

我们现在用于解决这个问题并且讨论的是第三种方法——Floyd算法。

4 问题假设

假设个点间的距离如图所示，且无特殊情况下任意两点最少能找到一条使他们相连

的线路。

5 符号说明

S

2

A

3

A

1

B

2

B

1

C

2

C T：表示网络中的个点，“0”表示同一点没有距离，“∞”

表示两点间不能直接到达。

ij

d表示权矩阵的数，

ij

b表示线路矩阵里的数。

6 模型的建立

6.1 模型的准备工作

1）明确模型目的即求各点到T点的最短路。

2）翻阅资料，查找关于Dijkstra法的介绍。并进行分析对比，择优选择好的资料

做为建模理论基础。

3）同组成员相互合作正式开始准备进行数学建模

4）表格一——各点间的原始权矩阵

S A1 A2 A3 B1 B2 C1 C2 T S 0 6 3 3 ∞∞∞∞∞A1 6 0 ∞∞ 3 5 ∞∞∞A2 3 ∞0 ∞8 6 ∞∞∞A3 3 ∞∞0 7 4 ∞∞∞B1 ∞ 3 8 7 0 ∞ 6 7 ∞B2 ∞ 5 6 4 ∞0 8 9 ∞C1 ∞∞∞∞ 6 8 0 ∞ 5 C2 ∞∞∞∞7 9 ∞0 6 T ∞∞∞∞∞∞ 5 6 0 5）表格二——线路矩阵原始

S A1 A2 A3 B1 B2 C1 C2 T

S 0 2 3 4 5 6 7 8 9 A1 1 0 3 4 5 6 7 8 9 A2 1 2 0 4 5 6 7 8 9 A3 1 2 3 0 5 6 7 8 9 B1 1 2 3 4 0 6 7 8 9 B2 1 2 3 4 5 0 7 8 9 C1 1 2 3 4 5 6 0 8 9 C2 1 2 3 4 5 6 7 0 9 T 1

2

3

4

5

6

7

8

6.2 建立模型

运用MATLAB 软件对模型进行求解：

在上述表格一中要求第m 行m 列上的数必需满足jm m i ij d d d +≤，当

jm m i ij d d d +>时jm m i ij d d d +=，同时而表格二的中m b ij =，直到所有的ij d 都满足条件jm m i ij d d d +≤。

在MATLAB 中中实现编程如下（具体程序见附录） for m=1:9 for j=1:9 for i=1:9

if a(i,j)>a(m,i)+a(j,m) a(i,j)=a(m,i)+a(j,m); b(i,j)=m; end end end end

得到两个新矩阵既是计算结果。

7 模型求解

MATLAB 软件求解结果：

运用MATLAB 软件中的for if 函数（具体程序见附件） 对所得结果进行分析得：

各点间相互到达的最短路程如下表：

S

A1

A2

A3

B1

B2

C1

C2

T

S 0 6 3 3 10 7 15 16 20 A1 6 0 9 9 6 5 12 13 17 A2 3 9 0 6 8 6 14 15 19 A3 3 9 6 0 7 4 12 13 17 B1 10 6 8 7 0 11 6 7 11 B2 7 5 6 4 11 0 8 9 13 C1 15 12 14 12 6 8 0 11 5 C2 16 13 15 13 7 9 11 0 6 T

20

17

19

17

11

13

5

6

由上表格可以知道T 点到个点（以S 1A 2A 3A 1B 2B 1C 2C 为顺序）间的距离：

d =

0 20 17 19 17 11 13 5 6

且各点之间的最短路线所经过点如下图

S

A1

A2

A3

B1

B2

C1

C2

T

S 0 2 3 4 4 4 6 6 7 A1 1 0 1 1 5 6 5 5 7 A2

1

1

1

5

6

5

5

7

A3 1 1 1 0 5 6 6 6 7 B1 4 2 3 4 0 2 7 8 7 B2 4 2 3 4 2 0 7 8 7 C1 6 5 5 6 5 6 0 9 9 C2 6 5 5 6 5 6 9 0 9 T

7

7

7

7

7

7

7

8

所以由上表格可以得到各点到T 点的最短路路线：

S 点到T 点：S →3A →2B →1C →T 1A 点到T 点：1A →1B →1C →T

2A 点到T 点：2A →1B →1C →T

3A 点到T 点：3A →2B →1C →T 1B 点到T 点：1B →1C →T 2B 点到T 点：2B →1C →T 1C 点到T 点：1C →T 2C 点到T 点：2C →T

8 模型验证及结果分析

8.1 模型验证

8.1.2 MATLAB 软件求解结果验证

运用MATLAB 软件求解，根据所得结果可知：

T 点到个点（以S 1A 2A 3A 1B 2B 1C 2C 为顺序）间的距离：

d =

0 20 14 19 17 11 13 5 6

各点到点T 最短路线路：

S 点到T 点：S →3A →2B →1C →T 1A 点到T 点：1A →1B →1C →T 2A 点到T 点：2A →1B →1C →T

3A 点到T 点：3A →2B →1C →T 1B 点到T 点：1B →1C →T

2B 点到T 点：2B →1C →T 1C 点到T 点：1C →T 2C 点到T 点：2C →T

求得结果为可行解，经过验算所得结果为最优解。

8.2 结果分析

现在对两个表格进行分析 各点间相互到达的最短路程为： S

A1

A2

A3

B1

B2

C1

C2

T

S 0 6 3 3 10 7 15 16 20 A1 6 0 9 9 6 5 12 13 17 A2 3 9 0 6 8 6 14 15 19 A3 3 9 6 0 7 4 12 13 17 B1 10 6 8 7 0 11 6 7 11 B2 7 5 6 4 11 0 8 9 13 C1 15 12 14 12 6 8 0 11 5 C2

16

13

15

13

7

9

11

6

T 20 17 19 17 11 13 5 6 0

各点之间的最短路线所经过点如下图：

S

A1

A2

A3

B1

B2

C1

C2

T

S 0 2 3 4 4 4 6 6 7 A1 1 0 1 1 5 6 5 5 7 A2 1 1 0 1 5 6 5 5 7 A3 1 1 1 0 5 6 6 6 7 B1 4 2 3 4 0 2 7 8 7 B2 4 2 3 4 2 0 7 8 7 C1 6 5 5 6 5 6 0 9 9 C2 6 5 5 6 5 6 9 0 9 T

7

7

7

7

7

7

7

8

对于表格一中的数学表示两个点间的最短路距离，表格二中的数字表示两点间最短路要经过的点（1~9分别按顺序表示S 1A 2A 3A 1B 2B 1C 2C 点）

参 考 文 献

[1] 姜启源,谢金星,叶俊编．数学模型（第三版）[M]．北京：高等教育出版社，2005：1-202.

[2] 何坚勇编著. 运筹学基础（第二版）[M]. 北京：清华大学出版社，2008 [3] 刘卫国编著.MATLAB 程序设计教程 中国水利水电出版社，2005 1-180

[4] 胡运权编著.运筹学教程（第三版）[M]．北京：清华大学出版社，2007：1-256.

[5] 韩中庚编著.实用运筹学模型、方法与计算[M]．北京：清华大学出版社，2007：1-232. [6] 张明辉,王学辉等编注．MATLAB6.1最新应用详解[M]．北京：中国水利水电出版社，2001：1-180.

[7] 谢金星,薛毅编注．优化建模与LINGO 软件[M]．北京：清华大学出版社，2005：1-280.

附 录

源程序：

clear;

clc;

Inf=100000;

a(1,:)=[0,6,3,3,Inf,Inf,Inf,Inf,Inf];

a(2,:)=[zeros(1,2),Inf,Inf,6,5,Inf,Inf,Inf];

a(3,:)=[zeros(1,3),Inf,8,6,Inf,Inf,Inf];

a(4,:)=[zeros(1,4),7,4,Inf,Inf,Inf];

a(5,:)=[zeros(1,5),Inf,6,7,Inf];

a(6,:)=[zeros(1,6),8,9,Inf];

a(7,:)=[zeros(1,7),Inf,5];

a(8,:)=[zeros(1,8),6];

a(9,:)=zeros(1,9);

a=a+a';

b(1,:)=[0,2,3,4,5,6,7,8,9];

b(2,:)=[1,0,3,4,5,6,7,8,9];

b(3,:)=[1,2,0,4,5,6,7,8,9];

b(4,:)=[1,2,3,0,5,6,7,8,9];

b(5,:)=[1,2,3,4,0,6,7,8,9];

b(6,:)=[1,2,3,4,5,0,7,8,9];

b(7,:)=[1,2,3,4,5,6,0,8,9];

b(8,:)=[1,2,3,4,5,6,7,0,9];

b(9,:)=[1,2,3,4,5,6,7,8,0];

for m=1:9

for j=1:9

for i=1:9

if a(i,j)>a(m,i)+a(j,m)

a(i,j)=a(m,i)+a(j,m);

b(i,j)=m;

end

end

end

end

a

b

程序计算结果：

a =

0 6 3 3 10 7 15 16 20

6 0 9 9 6 5 12 13 17

3 9 0 6 8 6 1

4 1

5 19

3 9 6 0 7

4 12 13 17

10 6 8 7 0 11 6 7 11

7 5 6 4 11 0 8 9 13

15 12 14 12 6 8 0 11 5

16 13 15 13 7 9 11 0 6

20 17 19 17 11 13 5 6 0

b =

0 2 3 4 4 4 6 6 7

1 0 1 1 5 6 5 5 7

1 1 0 1 5 6 5 5 7

1 1 1 0 5 6 6 6 7

4 2 3 4 0 2 7 8 7

4 2 3 4 2 0 7 8 7

6 5 5 6 5 6 0 9 9

6 5 5 6 5 6 9 0 9

7 7 7 7 7 7 7 8 0

短路电流计算方法

供电网络中发生短路时,很大的短路电流会使电器设备过热或受电动力作用而遭到损坏,同时使网络内的电压大大降低,因而破坏了网络内用电设备的正常工作.为了消除或减轻短路的后果,就需要计算短路电流,以正确地选择电器设备、设计继电保护和选用限制短路电流的元件。 二.计算条件 1.假设系统有无限大的容量.用户处短路后,系统母线电压能维持不变.即计算阻抗比系统阻抗要大得多。 具体规定: 对于3~35KV级电网中短路电流的计算,可以认为110KV及以上的系统的容量为无限大.只要计算35KV及以下网络元件的阻抗。 2.在计算高压电器中的短路电流时,只需考虑发电机、变压器、电抗器的电抗,而忽略其电阻;对于架空线和电缆,只有当其电阻大于电抗1/3时才需计入电阻,一般也只计电抗而忽略电阻。 3. 短路电流计算公式或计算图表,都以三相短路为计算条件.因为单相短路或二相短路时的短路电流都小于三相短路电流.能够分断三相短路电流的电器,一定能够分断单相短路电流或二相短路电流。 三.简化计算法 即使设定了一些假设条件,要正确计算短路电流还是十分困难,对于一般用户也没有必要.一些设计手册提供了简化计算的图表.省去了计算的麻烦.用起来比较方便.但要是手边一时没有设计手册怎么办?下面介绍一种“口诀式”的计算方法,只要记牢7句口诀,就可掌握短路电流计算方法. 在介绍简化计算法之前必须先了解一些基本概念. 1.主要参数 Sd三相短路容量 (MVA)简称短路容量校核开关分断容量 Id三相短路电流周期分量有效值(KA)简称短路电流校核开关分断电流 和热稳定 IC三相短路第一周期全电流有效值(KA) 简称冲击电流有效值校核动稳定 ic三相短路第一周期全电流峰值(KA) 简称冲击电流峰值校核动稳定 x电抗(Ω) 其中系统短路容量Sd和计算点电抗x 是关键. 2.标么值

短路电流限制技术的原理

短路电流限制的原理 电力系统中的短路故障是不可避免的，除了故障点附近的损坏。例如，由于强烈的电弧的影响，流经故障回路的短路电流会对架空线、电缆、变压器和开关设备等设备施加较高的电动力和热应力。系统中的断路器还必须能够（选择性地）遮断和隔离故障点。 然而随着全球对电力能源需求不断增长，用户需要更大容量的变压器或者新增的发电接入现有系统，以满足负荷的增长，同时越来越多的系统进行互联，这就会导致客户电力系统短路电流水平升高，导致电力系统在短路电流承受能力方面接近甚至超过其极限。因此，短路电流限制成为行业所面临的挑战，这个挑战主要的难度在于：（一）如何在确保系统可靠性、供电连续性的前提下，有效地限制短路电流 （二）在有效限制短路电流的前提下如何尽可能提高系统效能减低损耗 （三）如何尽可能降低工程投资造价 图1a）显示一个简化的等效电路，用于讨论与电力系统中短路电流限制相关的问题。与故障之前流动的负荷电流无关。短路电流在故障0秒后从0kA开始以一定的上升速率迅速增大，具体取决于电路参数（电源电压U0和电源阻抗ZS以及故障初始相位角，当短路电流未被限制时，波形如图1b）中波形为i1，也就是系统预期的短路电流。如果其短路电流水平处于CB的遮断能力之内，则该短路电流将在t3处由CB遮断。

图1：短路电流限制 a）短路故障等效电路图 b）短路电流典型波形图 由于 是包括故障部分在内的电路中电阻的总和L是电路中全部电感所以限制短路电流的最简单方法是使用适当高值的阻抗ZS，即：（一）实时的在系统内增加网络阻抗，如电网分层分区、母线分段、提升电压等级等电网拓扑结构级手段，此解决方案是最为常用的解决办法，该方法的弊端是降低了系统的可靠性、增大了复杂性，降低了系统的效能，例如：母线分段。 （二）采用限流电抗器或者高阻抗变压器等，以限制短路电流的上升。该解决方案的缺点在于，它显然会在正常运行期间影响系统，降低系统的效能，而且在高负载电流下会导致相当大的电压降。 （三）采用狭义上的故障电流限制器，在正常的情况下，阻抗非

短路电流的危害及防范措施

电力系统在运行中相与相之间或相与地(或中性线)之间发生非正常连接(短路)时流过的电流称为短路电流。在三相系统中发生短路的基本类型有三相短路、两相短路、单相对地短路和两相对地短路。三相短路因短路时的三相回路依旧是对称的，故称为对称短路；其他几种短路均使三相电路不对称，故称为不对称短路。 在中性点直接接地的电网中，以一相对地的短路故障为最多，约占全部短路故障的90。在中性点非直接接地的电力网络中，短路故障主要是各种相间短路。发生短路时，由于电源供电回路阻抗的减小以及忽然短路时的暂态过程，使短路回路中的电流大大增加，可能超过回路的额定电流许多倍。 短路电流的大小取决于短路点距电源的电气距离，例如，在发电机端发生短路时，流过发电机的短路电流最大瞬时值可达发电机额定电流的10～15倍，在大容量的电力系统中，短路电流可高达数万安培。短路电流的危害短路电流将引起下列严重后果：短路电流往往会有电弧产生，它不仅能烧坏故障元件本身，也可能烧坏四周设备和伤害四周人员。巨大的短路电流通过导体时，一方面会使导体大量发热，造成导体过热甚至熔化，以及绝缘损坏；另一方面巨大的短路电流还将产生很大的电动力作用于导体，使导体变形或损坏。短路也同时引起系统电压大幅度降低，非凡是靠近短路点处的电压降低得更多，从而可能导致部分用户或全部用户的供电遭到破坏。网络电压的降低，使供电设备的正常工作受到损坏，也可能导致工厂的产品报废或设备损坏，如电动机过热受损等。 电力系统中出现短路故障时，系统功率分布的忽然变化和电压的严重下降，可能破坏各发电厂并联运行的稳定性，使整个系统解列，这时某些发电机可能过负荷，因此，必须切除部分用户。短路时电压下降的愈大，持续时间愈长，破坏整个电力系统稳定运行的可能性愈大。短路电流的限制措施为保证系统安全可靠地运行，减轻短路造成的影响，除在运行维护中应努力设法消除可能引起短路的一切原因外，还应尽快地切除短路故障部分，使系统电压在较短的时间内恢复到正常值。 为此，可采用快速动作的继电保护和断路器，以及发电机装设自动调节励磁装置等。此外，还应考虑采用限制短路电流的措施，如合理选择电气主接线的形式或运行方式，以增大系统阻抗，减少短路电流值；加装限电流电抗器；采用分裂低压绕阻变压器等。主要措施如下： 一是做好短路电流的计算，正确选择及校验电气设备，电气设备的额定电压要和线路的额定电压相符。 二是正确选择继电保护的整定值和熔体的额定电流，采用速断保护装置，以便发生短路时，能快速切断短路电流，减少短路电流持续时间，减少短路所造成的损失。 三是在变电站安装避雷针，在变压器四周和线路上安装避雷器，减少雷击损害。 四是保证架空线路施工质量，加强线路维护，始终保持线路弧垂一致并符合规定。 五是带电安装和检修电气设备，注重力要集中，防止误接线，误操作，在带电部位距离较近的部位工作，要采取防止短路的措施。 六是加强治理，防止小动物进入配电室，爬上电气设备。 七是及时清除导电粉尘，防止导电粉尘进入电气设备。 八是在电缆埋设处设置标记，有人在四周挖掘施工，要派专人看护，并向施工人员说明电缆敷设位置，以防电缆被破坏引发短路。 九是电力系统的运行、维护人员应认真学习规程，严格遵守规章制度，正确操作电气设备，禁止带负荷拉刀闸、带电合接地刀闸。线路施工，维护人员工作完毕，应立即拆除接地线。要经常对线路、设备进行巡视检查，及时发现缺陷，迅速进行检修。

最短路问题及其应用——最短路径

最短路问题及应用 摘要:主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法以及这两种算法在实际问题中的应用和比较。 关键词：最短路获克斯特拉(Dijkstra)，弗罗伊德(Floyd)算法 1.引言 图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数 学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等。这些古老的难题，当时吸引了很多学者的注意。在这些问题研究的基础上又继续提出了著名的四色猜想 和汉米尔顿（环游世界）数学难题。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学 等各个领域的问题时，发挥出越来越大的作用在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点 间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学 与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2.最短路算法 2.1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0 w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的，该ij 算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短

最短路问题

§ 3最短路问题 在实践中常遇到的一类网络问题是最短路问题。给定一个有向赋权图D=（V，A），对每一个弧a =（ ,），相应有权≥0，指定D中的为发点，为终点。最短路问题就是要在所有到的路中，求出一条总权数最小的路。这里权数可以是距离，也可以是时间，或者是费用等等。 最短路问题是最重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一个基本工具，用于解决其它优化问题。 3.1 狄克斯拉（Dijkstra）算法 最短路问题可以化为线性规划问题求解，也可以用动态规划方法求解，这里介绍一种有效算法—狄克斯拉（Dijkstra）算法，这一算法是1959年首次被提出来的。该算法适用于每条弧的权数≥0情形。 算法的基本思路：从发点出发，有一个假想的流沿网络一切可能的方向等速前进，遇到新节点后，再继续沿一切可能的方向继续前进，则最先到达终点的流所走过的路径一定是最短的。为了实现这一想法，对假想流依次到达的点，依次给予p标号，表示到这些点的最短距离。对于假想流尚未到达的点给予T标号，表示到这些点的最短距离的估计值。具体作法如下： 1°标p（）=0，其余点标T（）=+∞; 2°由刚刚获得p标号的点出发，改善它的相邻点的T标号,即 新的T（）=min{老的T（），p（）+ } 若T（）= p（）+ ωij ，则记k（）=（前点标记）; 3°找出具有最小T标号的点，将其标号改为p标号。若已获得p标号，则已找到最短路，由k （）反向追踪，就可找出到的最短路径，p（）就是到的最短距离。否则，转2°。 例2 求图下中v1 到v8 的最短路。

短路电流计算的基本步骤和注意事项教学内容

短路电流计算的基本步骤和注意事项

短路电流计算方法的基本步骤和注意事项 一.概述 供电网络中发生短路时,很大的短路电流会使电器设备过热或受电动力作用而遭到损坏,同时使网络内的电压大大降低,因而破坏了网络内用电设备的正常工作.为了消除或减轻短路的后果,就需要计算短路电流,以正确地选择电器设备、设计继电保护和选用限制短路电流的元件. 二.一般计算条件 1.假设系统有无限大的容量.用户处短路后,系统母线电压能维持不变.即计算阻抗比系统阻抗要大得多. 具体规定: 对于3~35KV级电网中短路电流的计算,可以认为110KV及以上的系统的容量为无限大.只要计算35KV及以下网络元件的阻抗. 2.在计算高压电器中的短路电流时,只需考虑发电机、变压器、电抗器的电抗,而忽略其电阻;对于架空线和电缆,只有当其电阻大于电抗1/3时才需计入电阻,一般也只计电抗而忽略电阻. 3. 短路电流计算公式或计算图表,都以三相短路为计算条件.因为单相短路或二相短路时的短路电流都小于三相短路电流.能够分断三相短路电流的电器,一定能够分断单相短路电流或二相短路电流. 三、短路电流计算步骤 1．确定计算条件，画计算电路图

1）计算条件：系统运行方式，短路地点、短路类型和短路后采取的措施。 2运行方式：系统中投入的发电、输电、变电、用电设备的多少以及它们之 间的连接情况。 3)根据计算目的确定系统运行方式，画相应的计算电路图。 4）选电气设备：选择正常运行方式画计算图； 5）短路点取使被选择设备通过的短路电流最大的点。 6）继电保护整定：比较不同运行方式，取最严重的。 2．画等值电路，计算参数； 分别画各段路点对应的等值电路。 标号与计算图中的应一致。 3．网络化简，分别求出短路点至各等值电源点之间的总电抗。 ⑴. 星—角变换公式 角—星变换公式 23131231121X X X X X X n ++?=n n n n n X X X X X X 3212112?++= 23131232122X X X X X X n ++?= n n n n n X X X X X X 1323223?++= 23131231323X X X X X X n ++?=n n n n n X X X X X X 2131331?++= ⑵.等值电源归算 （1） 同类型且至短路点的电气距离大致相等的电源可归并； （2） 至短路点距离较远的同类型或不同类型的电源可归并； 直接连于短路点上的同类型发电机可归并； 四、注意事项

最短路问题及最速下降问题

§1 变分法简介 作为数学的一个分支，变分法的诞生，是现实世界许多现象不断探索的结果，人们可以追寻到这样一个轨迹： 约翰·伯努利（Johann Bernoulli ，1667－1748）1696年向全欧洲数学家挑战，提出一个难题：“设在垂直平面内有任意两点，一个质点受地心引力的作用，自较高点下滑至较低点，不计摩擦，问沿着什么曲线下滑，时间最短？” 这就是著名的“最速降线”问题（The Brachistochrone Problem ）。它的难处在于和普通的极大极小值求法不同，它是要求出一个未知函数（曲线），来满足所给的条件。这问题的新颖和别出心裁引起了很大兴趣，罗比塔（Guillaume Francois Antonie de l'Hospital 1661-1704）、雅可比·伯努利（Jacob Bernoulli 1654-1705）、莱布尼茨（Gottfried Wilhelm Leibniz,1646-1716）和牛顿（Isaac Newton1642—1727）都得到了解答。约翰的解法比较漂亮，而雅可布的解法虽然麻烦与费劲，却更为一般化。后来欧拉（Euler Lonhard ，1707～1783）和拉格朗日(Lagrange, Joseph Louis ，1736-1813)发明了这一类问题的普遍解法，从而确立了数学的一个新分支——变分学。 有趣的是，在1690年约翰·伯努利的哥哥雅可比·伯努利曾提出著名的悬链线问题 (The Hanging Chain Problem)向数学界征求答案，即，固定项链的两端，在重力场中让它自然垂下，问项链的曲线方程是什么。在大自然中，除了悬垂的项链外，我們还可以观察到吊桥上方的悬垂钢索，挂着水珠的蜘蛛网，以及两根电线杆之间所架设的电线，这些都是悬链线（catenary ）。 伽利略（Galileo, 1564～1643）比贝努利更早注意到悬链线，他猜测悬链线是抛物线，从外表看的确象，但实际上不是。惠更斯（Huygens, 1629～1695）在1646年（当时17岁），经由物理的论证，得知伽利略的猜测不对，但那时，他也求不出答案。到1691年，也就是雅可比·伯努利提出悬链线问题的第二年，莱布尼兹、惠更斯（以62岁）与约翰·伯努利各自得到了正确答案，所用方法是诞生不久的微积分，具体说是把问题转化为求解一个二阶常微分方程 解此方程并适当选取参数，得 )(21ax ax e e a y -+= （1） 即为悬链线。 悬链线问题本身和变分法并没有关系，然而这和最速降线问题一样都是贝努利兄弟间的相互争强好胜、不断争吵的导火索，虽然雅可比·贝努利在解决悬链线问题时略占下风，但他随后所证明的“悬挂于两个固定点之间的同一条项链，在所有可能的形状中，以悬链线的重心最低，具有最小势能”，算是扳回了一局，俩兄弟扯平了！之所以提到悬链线问题，有两方面考虑，其一，这是有关数学史上著名的贝努利家族内的一个趣闻，而这是一个在变分法乃至整个数学物理领域有着巨大贡献的家族，其二，有关悬链线的得几个结论，可以用变 ???????='=+=0)0()0()(102 2 2y y y dx dy a dx y d

最短路问题(整理版)

最短路问题(short-path problem) 若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径） 1、Dijkstra算法： 用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度 代码： procedure dijkstra（v0：longint）；//v0为起点做一次dijkstra begin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongint for i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里 visit[v0]:=true;//已经连接v0结点 for i:=1 to n-1 do//剩下n-1个节点未加入路径里； begin min:=maxlongint;//初始化min for j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小 begin min:=d[j];k:=j;end; visit[k]:=true;//连接进去 for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值， if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k]; end; writeln(d[n]);//结点v0到结点n的最短路。 思考：在实现步骤时，效率较低需要O(n)，使总复杂度达到O(n^2)。对此可以考虑用堆这种数据结构进行优化，使此步骤复杂度降为O(log(n))(总复杂度降为O(n log(n))。 实现：1. 将与源点相连的点加入堆（小根堆），并调整堆。 2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。 3. 处理与u相邻（即下一个）未被访问过的，满足三角不等式的顶点 1):若该点在堆里，更新距离，并调整该元素在堆中的位置。 2):若该点不在堆里，加入堆，更新堆。 4. 若取到的u为终点，结束算法；否则重复步骤2、3。 **优化代码：(DIJKSTRA+HEAP) program SSSP;{single source shortest path} {假设一个图的最大节点数为1000，所有运算在integer范围内} {程序目标：给定有向图的邻接表，求出节点1到节点n的最短路径长度} const maxn=1000;{最大节点数} var n:integer;{节点个数} list:array[1..maxn,1..maxn] of integer;{邻接矩阵，表示边的长度}

最短路问题

最短路问题 何谓最短路？ 最短路问题考虑的是有向网络N=（V，A，W），其中弧（i,j）∈A 对应的权又称为弧长或费用。对于其中的两个顶点s，t∈V,以s 为起点，t 为终点的有向路称为s-t 有向路，其所经过的所有弧上的权（或弧长、费用）之和称为该有向路的权（或弧长、费用）。所有s-t 有向路中权最小的一条称为s-t 最短路。 ij w 如何得到最短路？ 最短路问题的线性规划描述如下： (,)m i n i j i j i j A w x ∈∑ (1):(,):(,)1,,.. 1,,0,,ij ji j i j A j j i A i s s t x x s i s t ∈∈=??t ?=?=??≠? ∑∑ (2) 0ij x ≥ (3) 其中决策变量表示弧（i,j）是否位于s-t 路上：当=1时，表示弧（i,j）位于s-t 路上，当=0时，表示弧（i,j）不在s-t 路上。本来，应当是0-1变量，但由于约束（2）的约束矩阵就是网络的关联矩阵，它是全幺模矩阵，因此0-1变量可以松弛为区间[0，1]中的实数（当用单纯形法求解时，将得到0-1整数解）。 ij x ij x ij x ij x 值得注意的是，我们这里将变量直接松弛为所有非负实数。实际上，如果可以取0-1以外的整数，则约束条件并不能保证对应于非零的弧所构成的结构（记为P）一定是一条路，因为这一结构可能含有圈。进一步分析，我们总是假设网络本身不含有负圈，而任何正圈不可能使目标函数最小，因此上面的约束条件（2），（3）可以保证当达到最优解时，P 如果包含圈，该圈一定是零圈，我们从P 中去掉所有的零圈，就可以得到最短路。 ij x ij x ij x 无圈网络与正费用网络一般采用标号设定算法。 Bellman 方程（最短路方程） 将约束条件（2）两边同时乘以-1，得到其对偶问题为： m ax()t s u u ? （4） ..,(,)j i ij s t u u w i j A ?≤?∈ （5） 根据互补松弛条件，当x 和u 分别为原问题和对偶问题的最优解时：

短路电流的危害及限制措施

短路电流的危害及限制 措施 集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289-

短路电流的危害及限制措施电力系统在运行中相与相之间或相与地(或中性线)之间发生非正常连接(短路)时流过的电流称为短路电流。在三相系统中发生短路的基本类型有三相短路、两相短路、单相对地短路和两相对地短路。三相短路因短路时的三相回路依旧是对称的，故称为对称短路；其他几种短路均使三相电路不对称，故称为不对称短路。在中性点直接接地的电网中，以一相对地的短路故障为最多，约占全部短路故障的90%。在中性点非直接接地的电力网络中，短路故障主要是各种相间短路。发生短路时，由于电源供电回路阻抗的减小以及突然短路时的暂态过程，使短路回路中的电流大大增加，可能超过回路的额定电流许多倍。短路电流的大小取决于短路点距电源的电气距离，例如，在发电机端发生短路时，流过发电机的短路电流最大瞬时值可达发电机额定电流的10～15倍，在大容量的电力系统中，短路电流可高达数万安培。 短路电流的危害 短路电流将引起下列严重后果：短路电流往往会有电弧产生，它不仅能烧坏故障元件本身，也可能烧坏周围设备和伤害周围人员。巨大的短路电流通过导体时，一方面会使导体大量发热，造成导体过热甚至熔化，以及绝缘损坏；另一方面巨大的短路电流还将产生很大的电动力作用于导体，使导体变形或损坏。短路也同时引起系统电压大幅度降低，特别

是靠近短路点处的电压降低得更多，从而可能导致部分用户或全部用户的供电遭到破坏。网络电压的降低，使供电设备的正常工作受到损坏，也可能导致工厂的产品报废或设备损坏，如电动机过热受损等。电力系统中出现短路故障时，系统功率分布的突然变化和电压的严重下降，可能破坏各发电厂并联运行的稳定性，使整个系统解列，这时某些发电机可能过负荷，因此，必须切除部分用户。短路时电压下降的愈大，持续时间愈长，破坏整个电力系统稳定运行的可能性愈大。 短路电流的限制措施 为保证系统安全可靠地运行，减轻短路造成的影响，除在运行维护中应努力设法消除可能引起短路的一切原因外，还应尽快地切除短路故障部分，使系统电压在较短的时间内恢复到正常值。为此，可采用快速动作的继电保护和断路器，以及发电机装设自动调节励磁装置等。此外，还应考虑采用限制短路电流的措施，如合理选择电气主接线的形式或运行方式，以增大系统阻抗，减少短路电流值；加装限电流电抗器；采用分裂低压绕阻变压器等。主要措施如下： 一是做好短路电流的计算，正确选择及校验电气设备，电气设备的额定电压要和线路的额定电压相符。

(完整版)最短路径习题

13.4课题学习最短路径问题 1、①如右图是一个棱长为4的正方体木块，一只蚂蚁要从木块的点A沿木块侧面爬到点B 处，则它爬行的最短路径是。 B A ②如右图是一个长方体木块，已知AB=3，BC=4，CD=2，假设一只蚂蚁在点A处，它要沿着木块侧面爬到点D处，则蚂蚁爬行的最短路径是。 D C A B 2．①如图，要在河边修建一个水泵站，分别向张村、李庄送水，水泵站修在河边什么地方可使所用的水管最短。 李庄 张村 ②如图，直线L同侧有两点A、B，已知A、B到直线L的垂直距离分别为1和3，两点的水平距离为3，要在直线L上找一个点P，使PA+PB的和最小。请在图中找出点P的位置，并计算PA+PB的最小值。 B A L ③要在河边修建一个水泵站，向张村、李庄铺设管道送水，若张村、李庄到河边的垂直距离分别为1Km和3Km，张村与李庄的水平距离为3Km，则所用水管最短长度 为。

3．如图是一个长方体木块，已知AB=5，BC=3，CD=4，假设一只蚂蚁在点A 处，它要沿着木块侧面爬到点D 处，则蚂蚁爬行的最短路径是 。 4．现要在如图所示的圆柱体侧面A 点与B 点之间缠一条金丝带（金丝带的宽度忽略不计），圆柱体高为6cm ，底面圆周长为16cm ，则所缠金丝带长度的最小值为 。 5．如图是一个圆柱体木块，一只蚂蚁要沿圆柱体的表面从A 点爬到点B 处吃到食物，知圆柱体的高为5 cm ，底面圆的周长为24cm ，则蚂蚁爬行的最短路径为 。 6．正方形ABCD 的边长为8，M 在DC 上，且DM ＝2，N 是AC 上的一动点，DN ＋MN 的最小值为 。 7．在菱形ABCD 中，AB=2，∠BAD=60°，点E 是AB 的中点，P 是对角线AC 上的一个动点，则PE+PB 的最小值为 。 张村 李庄 A B C D A B A B

短路电流计算方法

供电网络中发生短路时，很大的短路电流会使电器设备过热或受电动力作用而遭到损坏，同时使网络内的电压大大降低，因而破坏了网络内用电设备的正常工作? 为了消除或减轻短路的后果，就需要计算短路电流，以正确地选择电器设备、设计继电保护和选用限制短路电流的元件。 二.计算条件 1?假设系统有无限大的容量?用户处短路后，系统母线电压能维持不变?即计算阻抗比系统阻抗要大得多。 具体规定：对于3~35KV级电网中短路电流的计算,可以认为110KV及以上的系统的容量为无限大.只要计算35KV及以下网络元件的阻抗。 2. 在计算高压电器中的短路电流时，只需考虑发电机、变压器、电抗器的电抗，而忽略其电阻；对于架空线和电缆，只有当其电阻大于电抗1/3时才需计入电阻，一般也只计电抗而忽略电阻。 3. 短路电流计算公式或计算图表，都以三相短路为计算条件.因为单相短路或二相短路时的短路电流都小于三相短路电流.能够分断三相短路电流的电器，一定能够分断单相短路电流或二相短路电流。 三.简化计算法 即使设定了一些假设条件，要正确计算短路电流还是十分困难，对于一般用户也没有必要.一些设计手册提供了简化计算的图表.省去了计算的麻烦.用起来比较方便.但要是手边一时没有设计手册怎么办？下面介绍一种“口诀式”的计算方法,只要记牢7句口诀,就可掌握短路电流计算方法. 在介绍简化计算法之前必须先了解一些基本概念. 1. 主要参数 Sd三相短路容量（MVA）简称短路容量校核开关分断容量 Id三相短路电流周期分量有效值（KA）简称短路电流校核开关分断电流 和热稳定 IC三相短路第一周期全电流有效值（KA）简称冲击电流有效值校核动稳定 ic三相短路第一周期全电流峰值（KA）简称冲击电流峰值校核动稳定 x电抗（Q） 其中系统短路容量Sd和计算点电抗x是关键.

短路电流大小的限制方法

限制短路电流的方法 2008-06-14 20:18 目前在电力系统中，用得较多的限制短路电流的方法有以下几种：选择发电厂和电网的接线方式；采用分裂绕组变压器和分段电抗器；采用线路电抗器；采用微机保护及综合自动化装置等。 1 选择发电厂和电网的接线方式 通过选择发电厂和电网的电气主接线，可以达到限制短路电流的目的。 在发电厂内，可对部分机组采用长度为40km及以上的专用线路，并将这种发电机—变压器—线路单元连接到距其最近的枢纽变电所的母线上，这样可避免发电厂母线上容量过份集中，从而达到降低发电厂母线处短路电流的目的。 为了限制大电流接地系统的单相接地短路电流，可采用部分变压器中性点不接地的运行方式，还可采用星形—星形接线的同容量普通变压器来代替系统枢纽点的联络自耦变压器。 在降压变电所内，为了限制中压和低压配电装置中的短路电流，可采用变压器低压侧分列运行方式；在输电线路中，也可采用分列运行的方式。在这两种情况下，由于阻抗大，可以达到限制短路电流的目的，不过为了提高供电可靠性，应该加装备用电源自动投入装置。 对环形供电网，可将电网解列运行。电网解列可分为经常解列和事故自动解列两种。电网经常解列是将机组和线路分配在不同的母线系统或母线分段上，并将母线联络断路器或母线分段断路器断开运行，这样可显著减小短路电流。电网事故自动解列，是指在正常情况下发电厂的母线联络断路器或分段断路器闭合运行，当发生短路时由自动装置将母线(或分段) 断路器断开，从而达到限制短路电流的目的。 2 采用分裂绕组变压器和分段电抗器 在大容量发电厂中为限制短路电流可采用低压侧带分裂绕组的变压器，在水电厂扩大单元机组上也可采用分裂绕组变压器。为了限制6～10 kV配电装置中的短路电流，可以在母线上装设分段电抗器。分段电抗器只能限制发电机回路、变压器回路、母线上发生短路时的短路电流，当在配电网络中发生短路时则主要由线路电抗器来限制短路电流。 3 采用线路电抗器 线路电抗器主要用于发电厂向电缆电网供电的6～10kV配电装置中，其作用是限制短路电流，使电缆网络在短路情况下免于过热，减少所需要的开断容量。 4 采用微机保护及综合自动化装置 从短路电流分析可知，发生短路故障后约0.01s时间出现最大短路冲击电流，采用微机保护仅需0.005s就能断开故障回路，使导体和设备避免承受最大短路电流的冲击，从而达到限制短路电流的目的。

限制短路电流的方法

限制短路电流的方法 1．选择适当的主接线形式和运行方式 （1）对具有大容量机组的发电厂中采用单元接线； （2）在降压变电所中，可采用变压器低压侧分列运行方式，即所谓母线硬分段接线； （3）对具有双回路电路，在负荷允许条件下可按单回路运行； （4）对环形供电网络，可在环网中穿越功率最小处开环运行。 2．加装限流电抗器 （1）加装普通电抗器 1）出线端加装出线电抗器用来限制电缆馈线支路短路电流。它只能在电抗器后面临近点短路时才有限制短路电流的作用。通常在架空线路上不装设电抗器。 线路电抗器不仅限制短路电流，而且能在母线上能维持较高的剩余残压（大于65％UN）。通常线路电抗器的百分电流值为3％～6％。 2）母线电抗器装设在母线分段的地方，其目的是让发电机出口断路器、变压器低压侧断路器、母联断路器和分段断路器等都能按各回路额定电流来选择，不因短路电流过大而升级。 一般设计主接线时，为了限制发电机电压母线短路电流，应首先考虑在分段断路器回路或联络断路器回路中以及主变压器回路中安装电抗器，只有经过计算认为限制效果不够时，才考虑装设线路电抗器。一般当电厂和系统容量较大时，两种电抗器都需要安装。为了运行操作方便和减小母线各段之间电压差，母线分段不宜超过三段，母线电抗器的电抗百分值应取8％～12％。 （2）分裂电抗器 分裂电抗器在结构上与普通电抗器相似，只是线圈中心有一个抽头3，中间抽头一般用来连接电源、两个分支（又称两臂）和用来连接大致相等的两组负荷。 当分裂电抗器的电抗值与普通电抗器的电抗值相同时，两者在短路时的限流作用一样，但正常运行时电压损失只有普通电抗器的一半，而且比普通电抗器多供一倍的出线，减少了电抗器的数目。 运行中当两个分支负荷不等或者负荷变化过大时，将引起两臂电压偏差，造成电压波动，甚至可能出现过电压。所以一般分裂电抗器的电抗百分值取8％～12％。 分裂电抗器在主接线中，可以装设在电缆馈线上，每个臂可以接一回出线或几回出线。分裂电抗器串接在发电机回路中，不仅起着出线电抗器的作用，而且也起着母线电抗器的作用。 3．采用分裂低压绕组变压器 当发电机容量较大时，采用分裂低压绕组变压器组成扩大单元接线。分裂绕组变压器在正常工作和低压侧短路时其电抗值不相同，从而起到限制短路电流效果。 低压分裂绕组正常运行时的电抗值，只相当两分裂绕组短路电抗的1/4。当一

最短路问题例题

问题： 求出A-F之间最短路线；（1）写出思路于算法；（2）Matlab 编程找出最短路径。 答案：A-F之间的最短路线有A-B3-D3-E1-F，A-B3-D3-E1-E2-F；A-B2-C1-D1-D2-E2-F 这三条路线的最短距离均为8。 方案一：思路：

对于是否返回的分析： 如图可以看出只有B端才能跨越C端的点直接到达D端的，其余的各端点都是必须按照字母顺序一路下来。若如D端返回到C端或B端这是不可能的，因为这样无疑增加了路程，如图可以看出C端的点能到达D端的各个点，所以要求的直接命中想到达的该点；而D端出发去到E端后有图可以看出不可能再返回D端了，因为这只会增加路线的长度，而且E 端的各点是相通的，也没必要再返回D端；同样B端到达C端或D端的，因为B2,B2到能直接到达C端的各点，只有B1只能到达C1，但B1它到D1的距离和B1点到C1的距离同样为4但也不可能经过C1后返回B端的，因为C1也是联系D端的各点，而且你要返回B 段端，还不如在A端的时候就选择好一个理想的B点，这样距离会更加短。所以不能进行返回。 如图将我们本来所需要的的路线分成两半，以D字母的为中间端。 后半部分：后半部分主要由D端连接到E端最后才连接到F端的,同时D端无法越过E 端直接连接到F端。更为重要的是前半部分，也必须要经过D端才能与F端相接，所以构成他们之间的枢纽定在D端是最好不过的。 首先的是先分析D端的三个点D1，D2，D3分别到点F的最短距离。 一、已经从D端出发去到E端后有图可以看出不可能再返回D端了，因为这只会增加路线的长度，而且E端的各点是相通的，也没必要再返回D端； 二、由图可以看出E端到点F最好的路线是E2-F距离为1，除E2外的E1，E3他们到F点 的方式（E1-F, E1-E2-F ,E3-F ,E3-E2-F）的距离均为2；所以如果能先到达E2则可以只考虑E2到F这条路线。若先到达了E1，或E3、则这路线的最短路径必定变化为两条。 三、由于D3到E端的三条路线D3-E2，D3-E5的距离均为5，与D3-E1的距离为2相差着 3的距离点，而即使E2-F的距离是1，比E1,E3到F的距离都少了1的距离点，但依然无法补充3个距离点的差距，对于E3-F就跟不用说了，所以D3连接E1是众望所归的。 所以归纳D3到F的最短路线可为（D3-E1-F, D3-E1-E2-F）距离均为4. 四、面对D2到E端的线路，它可以先经过D1点再过E端的点，但D2点到E2点也只是1 的距离，已经是最少了距离线了，更加重要的是E2点到F点的距离也只是1比E1，E3点都要短， 所以D2到F的最短线路是(D2-E2-F;)距离为2 五、对于D1点到F点的路线，首先可以先看出D1能直接到达E端的E,1，E2两点，但经 分析若选择D1直接经过E1点的路径（D1-E1-F或D1-E1-E2-F）但他们的距离长也为4； D1直接经过E2，则由E2到达F点，路径（D1-E2-F）总距离也是为4；但同时别把D1

短路电流的危害及限制措施(通用版)

短路电流的危害及限制措施 (通用版) Security technology is an industry that uses security technology to provide security services to society. Systematic design, service and management. ( 安全管理 ) 单位：______________________ 姓名：______________________ 日期：______________________ 编号：AQ-SN-0106

短路电流的危害及限制措施(通用版) 电力系统在运行中相与相之间或相与地(或中性线)之间发生非正常连接(短路)时流过的电流称为短路电流。在三相系统中发生短路的基本类型有三相短路、两相短路、单相对地短路和两相对地短路。三相短路因短路时的三相回路依旧是对称的，故称为对称短路；其他几种短路均使三相电路不对称，故称为不对称短路。在中性点直接接地的电网中，以一相对地的短路故障为最多，约占全部短路故障的90%。在中性点非直接接地的电力网络中，短路故障主要是各种相间短路。发生短路时，由于电源供电回路阻抗的减小以及突然短路时的暂态过程，使短路回路中的电流大大增加，可能超过回路的额定电流许多倍。短路电流的大小取决于短路点距电源的电气距离，例如，在发电机端发生短路时，流过发电机的短路电流最大瞬时值可达发电机额定电流的10～15倍，在大容量的电力系统中，短

路电流可高达数万安培。 短路电流的危害 短路电流将引起下列严重后果：短路电流往往会有电弧产生，它不仅能烧坏故障元件本身，也可能烧坏周围设备和伤害周围人员。巨大的短路电流通过导体时，一方面会使导体大量发热，造成导体过热甚至熔化，以及绝缘损坏；另一方面巨大的短路电流还将产生很大的电动力作用于导体，使导体变形或损坏。短路也同时引起系统电压大幅度降低，特别是靠近短路点处的电压降低得更多，从而可能导致部分用户或全部用户的供电遭到破坏。网络电压的降低，使供电设备的正常工作受到损坏，也可能导致工厂的产品报废或设备损坏，如电动机过热受损等。电力系统中出现短路故障时，系统功率分布的突然变化和电压的严重下降，可能破坏各发电厂并联运行的稳定性，使整个系统解列，这时某些发电机可能过负荷，因此，必须切除部分用户。短路时电压下降的愈大，持续时间愈长，破坏整个电力系统稳定运行的可能性愈大。 短路电流的限制措施

限制短路电流的方法

行业资料：________ 限制短路电流的方法 单位：______________________ 部门：______________________ 日期：______年_____月_____日 第1 页共9 页

限制短路电流的方法 目前在电力系统中，用得较多的限制短路电流的方法有以下几种：选择发电厂和电网的接线方式；采用分裂绕组变压器和分段电抗器；采用线路电抗器；采用微机保护及综合自动化装置等。 1选择发电厂和电网的接线方式 通过选择发电厂和电网的电气主接线，可以达到限制短路电流的目的。 在发电厂内，可对部分机组采用长度为40km及以上的专用线路，并将这种发电机—变压器—线路单元连接到距其最近的枢纽变电所的 母线上，这样可避免发电厂母线上容量过份集中，从而达到降低发电厂母线处短路电流的目的。 为了限制大电流接地系统的单相接地短路电流，可采用部分变压器中性点不接地的运行方式，还可采用星形—星形接线的同容量普通变压器来代替系统枢纽点的联络自耦变压器。 在降压变电所内，为了限制中压和低压配电装置中的短路电流，可采用变压器低压侧分列运行方式；在输电线路中，也可采用分列运行的方式。在这两种情况下，由于阻抗大，可以达到限制短路电流的目的，不过为了提高供电可靠性，应该加装备用电源自动投入装置。 对环形供电网，可将电网解列运行。电网解列可分为经常解列和事故自动解列两种。电网经常解列是将机组和线路分配在不同的母线系统或母线分段上，并将母线联络断路器或母线分段断路器断开运行，这样可显著减小短路电流。电网事故自动解列，是指在正常情况下发电厂的母线联络断路器或分段断路器闭合运行，当发生短路时由自动装置将母 第 2 页共 9 页

最短路径问题专项练习题

最短路径问题专项练习 共13页，全面复习与联系最短路径问题 一、具体内容包括： 蚂蚁沿正方体、长方体、圆柱、圆锥外侧面吃食问题； 线段（之和）最短问题； 二、原理： 两点之间，线段最短；垂线段最短。（构建“对称模型”实现转化） 1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A ，B 分别是直线l 异侧的两个点，在l 上找一个点C ，使CA ＋CB 最短，这时点C 是直线l 与AB 的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于 这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求． 如图所示，点A ，B 分别是直线l 同侧的两个点，在l 上找一个点C ，使CA ＋CB 最短，这时先作点B 关于直线l 的对称点B ′，则点C 是直线l 与AB ′的交点． 为了证明点C 的位置即为所求，我们不妨在直线上另外任取一点C ′，连接AC ′，BC ′， B ′ C ′，证明AC ＋CB ＜AC ′＋C ′B .如下： 证明：由作图可知，点B 和B ′关于直线l 对称， 所以直线l 是线段BB ′的垂直平分线． 因为点C 与C ′在直线l 上， 所以BC ＝B ′C ，BC ′＝B ′C ′. 在△AB ′C ′中，AB ′＜AC ′＋B ′C ′， 所以AC ＋B ′C ＜AC ′＋B ′C ′， 所以AC ＋BC ＜AC ′＋C ′B . 【例1】 在图中直线l 上找到一点M ，使它到A ，B 两点的距离和最小． 分析：先确定其中一个点关于直线l 的对称点，然后连接对称点和另一个点，与直线l 的交点M 即为所求的点． 解：如图所示：(1)作点B 关于直线l 的对称点B ′； (2)连接AB ′交直线l 于点M . (3)则点M 即为所求的点． 点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题.

电力系统短路电流的限制措施

电力系统短路电流的限制措施 电力系统在运行中相与相之间或相与地(或中性线)之间发生非正常连接(短路)时流过的电流称为短路电流。在三相系统中发生短路的基本类型有三相短路、两相短路、单相对地短路和两相对地短路。三相短路因短路时的三相回路依旧是对称的，故称为对称短路；其他几种短路均使三相电路不对称，故称为不对称短路。在中性点直接接地的电网中，以一相对地的短路故障为最多，约占全部短路故障的90%。在中性点非直接接地的电力网络中，短路故障主要是各种相间短路。发生短路时，由于电源供电回路阻抗的减小以及突然短路时的暂态过程，使短路回路中的电流大大增加，可能超过回路的额定电流许多倍。短路电流的大小取决于短路点距电源的电气距离，例如，在发电机端发生短路时，流过发电机的短路电流最大瞬时值可达发电机额定电流的10～15倍，在大容量的电力系统中，短路电流可高达数万安培。为保证系统安全可靠地运行，减轻短路造成的影响，除在运行维护中应努力设法消除可能引起短路的一切原因外，还应尽快地切除短路故障部分，使系统电压在较短的时间内恢复到正常值。为此，可采用快速动作的继电保护和断路器，以及发电机装设自动调节励磁装置等。此外，还应考虑采用限制短路电流的措施，如合理选择电气主接线的形式或运行方式，以增大系统阻抗，减少短路电流值；加装限电流电

抗器；采用分裂低压绕阻变压器等。主要措施如下： 一是做好短路电流的计算，正确选择及校验电气设备，电气设备的额定电压要和线路的额定电压相符。 二是正确选择继电保护的整定值和熔体的额定电流，采用速断保护装置，以便发生短路时，能快速切断短路电流，减少短路电流持续时间，减少短路所造成的损失。 三是在变电站安装避雷针，在变压器附近和线路上安装避雷器，减少雷击损害。 四是保证架空线路施工质量，加强线路维护，始终保持线路弧垂一致并符合规定。 五是带电安装和检修电气设备，注意力要集中，防止误接线，误操作，在带电部位距离较近的部位工作，要采取防止短路的措施。 六是加强管理，防止小动物进入配电室，爬上电气设备。 七是及时清除导电粉尘，防止导电粉尘进入电气设备。 八是在电缆埋设处设置标记，有人在附近挖掘施工，要派专人看护，并向施工人员说明电缆敷设位置，以防电缆被破坏引发短路。 九是电力系统的运行、维护人员应认真学习规程，严格遵守规章制度，正确操作电气设备，禁止带负荷拉刀闸、带电合接地刀闸。线路施工，维护人员工作完毕，应立即拆除接地线。要经常对线路、设备进行巡视检查，及时发现缺陷，迅速进行检修。