运筹学复习题市公开课一等奖百校联赛优质课金奖名师赛课获奖课件.pptVIP

某大学城工程，包含结构形式相同四栋单体建筑，A施工单位拟对四栋单体建筑某分项工程组织流水施工，其流水施工参数以下表：

其中施工次序为一、二、三，在此形式下，最宜采取哪种形式流水施工，绘制该流水施工横道图，并计算流水工期，除此之外，还有哪些形式流水施工

组织形式？

施工过程

单体建筑1

单体建筑2

单体建筑3

单体建筑4

一

2

2

2

2

二

2

2

2

2

三

2

2

2

2

流水节拍表

1/53

最短路问题求解方法

求最短路有三种算法:

狄杰斯特拉(Dijkstra)算法（略）

Floyd算法

2/53

每一对顶点间最短路径（Floyd算法）

Dijkstra算法是求指定点到其它顶点最短路径。怎样求任意两个顶点之间最短路径？我们能够把Dijkstra算执行n次，每次从不一样顶点开始

弗洛伊德给出了另一个算法，即floyd算法

3/53

算法过程（P257）

1，从任意一条单边路径开始。全部两点之间距离是边权，假如两点之间没有边相连，则权为无穷大。（定义权矩阵）

2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知路径更短。假如是更新它。

4/53

从演示中看算法思想

一个简单图及其权矩阵以下：

a

b

c

11

6

4

2

3

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cb,∞)

(cc,0)

D(-1)

5/53

从上面D（-1）开始，对于每两个顶点u、v，在D（-1）中存放着一条路径u…v。现在我们考查，试着把a加到u、v路径上能否，得到一条更短路径，即假如u…a+a…vu…v话，能够找到一条更短路6/53

a

b

c

11

6

4

2

3

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cb,∞)

(cc,0)

D(-1)

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

c

(ca,3)

(cc,0)

D(0)

原来路径上源点或终点就有a无须考虑。

对角线上也无须考虑

7/53

a

b

c

11

6

4

2

3

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cb,∞)

(cc,0)

D(-1)

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

c

(ca,3)

(cc,0)

D(0)

D[b][a]+D[a][c]=6+11D[b][c]=2，所以假如从a绕，反而远，那么这一项不变。

8/53

a

b

c

11

6

4

2

3

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cb,∞)

(cc,0)

D(-1)

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

c

(ca,3)

(cc,0)

D(0)

D[b][a]+D[a][c]=6+11D[b][c]=2，所以假如从a绕，反而远，那么这一项不变。

9/53

a

b

c

11

6

4

2

3

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cb,∞)

(cc,0)

D(-1)

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cc,0)

D(0)

10/53

a

b

c

11

6

4

2

3

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cb,∞)

(cc,0)

D(-1)

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cc,0)

D(0)

D[c][a]+D[a][b]=3+4D[c][b]=∞，所以假如从a绕，更近，那么应该更新。

11/53

a

b

c

11

6

4

2

3

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cb,∞)

(cc,0)

D(-1)

a

b

c

a

(aa,0)

(ab,4)

(ac,11)

b

(ba,6)

(bb,0)

(bc,2)

c

(ca,3)

(cab,7)

(cc,0)

D(0)

12