图论+网络优化

1、求解（lingo 编程）

min

L =∑l j (X 1j +X nj ) +∑∑∑C i j ⋅X k i ⋅X k +1, j

j =1

k =1i =1j =1

n n -1n n

⎧n

⎪∑X kj =1, k =1,2, , n ⎪j =1

n ⎪⎪X =1, j =1,2, , n s.t. ⎨∑kj

⎪k =1

⎪X kj =0或1⎪⎪⎩其它约束条件

N=10;

Lj=71,56,27,30,28,26,15,9,30,27;

C= 0,15,44,47,64,83,86,75,93,98 15,0,29,32,49,68,71,60,78,83 44,29,0,20,37,53,42,31,49,54 47,32,20,0,17,36,42,39,60,57 64,49,37,17,0,19,37,37,58,55 83,68,53,36,19,0,18,35,56,47 86,71,42,42,37,18,0,24,38,29 75,60,31,39,37,35,24,0,21,26 93,78,49,60,58,56,38,21,0,29 98,83,54,57,55,47,29,26,29,0; 2、求A 到E 的最短路径。

3、求A 到其他节点的最短路径。

4、今有a, b, c, d, e, f, g 7人，其中

a 会讲英语；

b 会讲英语和汉语；

c 会讲英语、意大利语和俄语； d 会讲日语和汉语；

e 会讲意大利语和西班牙语； f 会讲法语、日语和俄语； g 会讲法语和西班牙语；

这7个人应该如何安排圆桌座位，才能使每个人都能与他身边的人交谈？

（必须用图论知识作, 答案： a,b,d,f,g,e,c, 然后c 到a 。）

5、某城市要建立一所医院，该市的7个区如下图所示，问：应该设在哪个区，才能使它至最远区的路径最短。

6、如图所示，某城市要建立一所医院，该市的7个区如下图所示，问：应该设在哪个区，才能使它至最远区的路径最短。

7、现有21个点，其横坐标为：x=17.6， 13.8， 3.8， 3.8， 7.3， 11.1， 14.2， 14.2， 17.0 ，19.4， 5.8， 11.1， 11.1， 14.1， 14.1， 17.0， 17.0， 19.6， 19.6， 12.0， 17.8;纵坐标为：y=15.4， 12.7， 10.0， 8.0， 9.0， 9.0， 10.0，8.0， 9.0， 9.0， 4.9， 6.2， 4.6， 6.2， 4.6， 6.2， 4.6 ，6.2， 4.6， 2.8 ，2.8; 要建立一所医院，问：应该设在哪个点，才能使它至最远区的路径最短

时间

9、某项物流业务所含工作、时间、前项工作如下所示，请画出网络图，并求最短工期，且求作业F 的最早和最迟作业开始时间

10、表中给出一个汽车库及引道的施工计划：

问：1）该工程从施工开始到结束的最短工期

2）如果引道混凝土施工拖延10天，对整个工程进度有无影响

3）若装天花板的施工时间从12天缩短到8天，对整个工程进度有何影响 4）为保证工期不拖延，装门这项工作最晚从那天开始开工

11某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

12、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

工序代号

A B C D E F G H I J K

作业时间

5 6 10 12 15 6 8 9 20 25 8

紧前工序 ---- A A B B E A D 、C E F 、G 、H I 、J

13、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

7 6 6 3 8 4 4 6 3

14、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线

与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

15、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

16、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4

）求作业F 的最早和最迟作业开始时间

17、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

18、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

19、

某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

20、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

21、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

22、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

23、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

24、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求时间的关键路线与路长；（3）求关键工序（极限不用，后两列不用） （4）求作业F 的最早和最迟作业开始时间

25、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求时间关键路线与路长；（3）求关键工序（（极限不用，后两列不用）） （4）求作业F 的最早和最迟作业开始时间

26、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

27\某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

28、

某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

29、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

30、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序（只选择a,m,b 中一个） （4）求作业F 的最早和最迟作业开始时间

31、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

32、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

33、

某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

34、

某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

35、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

36、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

37、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

38、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

39、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

40、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

41、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

42、某工程项目作业明细表如下 ，（1）绘制计划网络图 ；（2）求关键路线与路长；（3）求关键工序 （4）求作业F 的最早和最迟作业开始时间

43

、

求最优运送路线和运送费用

44、

45、

46、

47、

48、