【精编完整版】运筹学毕业论文

10 9 7 8 （-7） 3 2 0 1 Cij = 5 8 7 7 （-5） 0 3 2 2 5 4 6 5 （-4） 1 0 2 5 2 3 4 5 （-2） 0 1 2 3 （2）进行试指派

3 2 0 1 0 3 2 2 1 0 2 5 0 1 2 3

（3）作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多0元素

3 2 0 1 0 3 2 2 1 0 2 5 0 1 2 3

（4）对矩阵进行变换，以增加0元素

3 2 0 1 4 2 0 0 0 3 2 2 0 2 1 0 1 0 2 5 2 0 2 0 0 1 2 3 0 0 1 1 （5）重复第二步，找到最优解

4 2 0 0 4 2 0 0 0 2 1 0 或 0 2 1 0 2 0 2 0 2 0 2 0 0 0 1 1 0 0 0 1 最优方案1：乙→1，丁→2，甲→3，丙→4

最少时间Z=7+5+5+3=20小时

最优方案2：丁→1，丙→2，甲→3，乙→4 最少时间Z=7+7+4+2=20小时

因为软件原因，无法进行检验

三、最小支撑树问题

某网络公司为沿着友谊大街8个居民点架设网线，连接8个居民点的道路如图1-31所示，边表示可架设网络道路，边权为道路的长度，设计一网线网络连通这8个居民点，并使总的输电线长度最短。

图1-31

1 2 6

7

3 5

4 8

解：（1）利用破圈法求解： 1 2 6

7

3 5

4 8

1 2 6

7

3 5

4 8

1 2 6

7

图1-32

图1-33

图1-34

3 5

4 8

图1-35

1 2 6

7

3 5

4 8

图1-36

1 2 6

7

3 5

4 8

图1-37

1 2 6

7

3 5

4 8

至此，无圈，图1-37为最小树，各边权之和为18,或如下1-38图：各边权之和也为18

图1-38

1 2 6

7

3 5

4 8

（2）运用软件进行检验： 此问题的最小生成树如下： ************************* 起点 终点 距离 ---- ---- ---- 1 3 2 3 4 2 1 2 4 2 5 2 5 7 3 7 8 2 7 6 3

此问题的解为:18

第二章 上机题

一、线性规划 1. max z =

s. t.

运算检验：

目标函数最优值为 : 21

变量 最优解 相差值 5 0 3 0 约束 松弛剩余变量 对偶价格