运筹学课程设计 精品

运筹学课程设计

第1页 共27页

内蒙古科技大学课程设计

目录

第一章自编题------------------------------------------------------1 一、运输规划问题------------------------------------------------1 二、指派问题----------------------------------------------------4 三、最小数问题--------------------------------------------------5 第二章 上机题------------------------------------------------------8 一、线性规划问题------------------------------------------------8 1--------------------------------------------------------------8

2--------------------------------------------------------------9 3--------------------------------------------------------------10 4--------------------------------------------------------------11 5--------------------------------------------------------------12 6--------------------------------------------------------------14 7--------------------------------------------------------------15 二、、运输问题---------------------------------------------------16

8--------------------------------------------------------------15 9--------------------------------------------------------------17 10-------------------------------------------------------------17 11-------------------------------------------------------------18 三、最短路问题--------------------------------------------------18

12-------------------------------------------------------------18 13-------------------------------------------------------------19 14-------------------------------------------------------------19 四、最大流问题--------------------------------------------------20

15-------------------------------------------------------------20 16-------------------------------------------------------------21 17-------------------------------------------------------------21

第2页 共27页

内蒙古科技大学课程设计

18-------------------------------------------------------------22 五、最小支撑树问题----------------------------------------------23

19-------------------------------------------------------------23 20-------------------------------------------------------------24 参考文献-----------------------------------------------------------24

一、运输规划问题

第一章第3页 自编题

共27页

内蒙古科技大学课程设计

包头市某冰箱工厂有三个分厂，生产同一种冰箱，供应该厂在市内的四个门市部销售。已知三个分厂的日生产能力分别是50、60、50台。四个门市部的日销售量分别是40、40、60、20台。从各个分厂运往各门市部的运费如表1-11所示。试安排一个运费最低的运输计划。

表1-11

门 市 工 厂 部 1 2 3 4 供应量总计 1 2 3 需求量总计

9 7 6 40 12 3 5 40 9 7 9 60 6 7 11 20 50 60 50 解,（1）运用最小元素法求解，得初始基本可行解，如下表1-12

表1-12

产 地 销 地 1 9 7 6 40 40 2 12 3 9 30 4 6 20 7 产量 1 50 2 3 40 4 40 7 20 9 10 60 60 3 11 20 50 销量 （2）用位势法计算所有非基变量检验数，求得如下表1-13

表1-13

第4页 共27页

内蒙古科技大学课程设计

产 地 销 地 1 9 2 12 3 9 4 6 20 7 （3） 11 （5） 20 产量 1 （3） （8） 30 7 3 7 20 9 50 2 （3） 40 6 40 40 4 60 3 （-1） 10 40 60 50 销量 （3）利用闭回路法进一步求解：

表1-14

产 地 销 地 1 9 2 12 3 9 4 6 20 7 （3） 11 （5） 20 产量 1 （3） （8） 30 7 3 - （3） 40 6 4 7 + 20 9 50 2 60 3 40 40 - 10 + （-1） 40 60 50 销量 （4）得出新方案，如表1-15

表1-15

第5页 共27页

内蒙古科技大学课程设计

产 地 销 地 1 9 7 6 40 40 2 12 3 9 30 4 6 20 7 产量 1 50 2 3 30 4 10 40 7 30 9 60 60 3 11 20 50 销量 （5）经检验所有空格的检验数均大于等于零，故此方案为最优解。 最优解为：X13=30，X14=20，X22=30，X23=30，X31=40，X32=10 最优方案运费Z=30×9+20×6+30×3+30×7+40×6+10×4=970元

（6）运用软件进行检验： 最优解如下

******************************************** 起 至 销点

发点 1 2 3 4 -------- ----- ----- ----- ----- 1 0 0 30 20 2 0 30 30 0 3 40 10 0 0 此运输问题的成本或收益为: 970

二、指派问题

现有四项不同的任务，分别由四个人去完成。因四个人的专长不同，所以

第6页 共27页

内蒙古科技大学课程设计

每个人完成的任务所需的时间也不同(如 表1-21),试问如何安排他们的工作才能使总的工作时间最少？

表1-21 （单位：小时） 人 工 作 1 10 5 5 2 2 9 8 4 3 3 7 7 6 4 4 8 7 5 5 甲 乙 丙 丁 解：（1）变换效率系数矩阵，使其每行没列都出现0元素

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元素

第7页 共27页

内蒙古科技大学课程设计

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

5 4 1 2 6 2

3 7 2 3 4 3 5

2 6

7 5 2

4 8

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

第8页 共27页

内蒙古科技大学课程设计

图1-32

5 4 1 2 6 2

3 7 2 3 4 3 5

2 6

7 5 2

× 4 8

图1-33

5 4 1 2 6 2

3 7 2 3 4 3 5

2 6 × 5 2

4 8

图1-34

4 × 5 1 2 6 2

3 7 2 3 4 3 5

2 5 2

4 8

图1-35

4 1 2 6 2

3 7 2 3 4 3 5

2 × 5 2

4 8

第9页 共27页

内蒙古科技大学课程设计

图1-36

4 × 1 2 6 2

3 7 2 3 4 3 5

2

2

4 8

图1-37

1 2 6 2

3 2 7 3 4 3 5

2 2

4 8

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

之和也为18

图1-38

4 1 2 6 2

3 3 7 2

3 5

2

2

4 8

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

第10页 共27页

内蒙古科技大学课程设计

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 =3x12x2

2x14x222 x14x210 s. t. x1x27 x13x21 x1,x20

运算检验：

目标函数最优值为 : 21

变量 最优解 相差值 ------- -------- -------- x1 5 0 x2 3 0 约束 松弛/剩余变量 对偶价格 ------- ------------- -------- 1 0 .7 2 3 0

第11页 共27页

内蒙古科技大学课程设计

3 0 .8 4 5 0 目标函数系数范围 :

变量 下限 当前值 上限 ------- -------- -------- -------- X1 1 3 无上限 X2 -1.5 2 6 常数项数范围 :

约束 下限 ------- -------- -------- -------- 1 12 22 26.286 2 7 10 3 4.5 7 12 4 -4 1 2. max z=2x1x2 x210 2x15x260

s.t. x1x218 3x1x244 x1,x20

运算检验：

目标函数最优值为 : 31

变量 最优解 ------- -------- -------- x1 13 0 x2 5 0 约束 松弛/剩余变量 第12页 共27页当前值 相差值 对偶价格上限 无上限 无上限

内蒙古科技大学课程设计

------- ------------- -------- 1 5 0 2 9 0 3 0 .5 4 0 .5 目标函数系数范围 :

变量 下限 ------- -------- -------- -------- x1 1 2 3 x2 .667 1 2 常数项数范围 :

约束 下限 ------- -------- -------- -------- 1 5 10 2 51 60 3 14.667 18 19.385 4 38 44 54

3. min z=20x115x2 2x1x25

s.t. 2x12x23 x1x23 x1,x20

运算检验：

目标函数最优值为 : 55

变量 最优解 ------- -------- -------- x1 2 0

第13页 共27页当前值 当前值 相差值 上限 上限 无上限无上限

内蒙古科技大学课程设计

x2 1 0 约束 松弛/剩余变量 对偶价格 ------- ------------- -------- 1 0 -5 2 7 0 3 0 -10 目标函数系数范围 :

变量 下限 ------- -------- -------- -------- x1 15 20 30 x2 10 15 20 常数项数范围 :

约束 下限 ------- -------- -------- -------- 1 3.6 5 6 2 -4 3 3 2.5 3 4

4． max z=2x1x2x3 3x12x22x315

s.t. x1x2x33 x1x2x34 x1,x2,x30

运算检验：

目标函数最优值为 : 18

变量 最优解 ------- -------- -------- x1 21 0

第14页 共27页当前值 当前值 相差值 上限 上限 无上限

内蒙古科技大学课程设计

x2 24 0 x3 0 2 约束 松弛/剩余变量 对偶价格 ------- ------------- -------- 1 0 1 2 0 1 3 7 0 目标函数系数范围 :

变量 下限 ------- -------- -------- -------- x1 1.5 2 x2 -1.333 -1 x3 无下限 1 3 常数项数范围 :

约束 下限 ------- -------- -------- -------- 1 -6 15 2 无下限 -3 4 3 -3 4 5. min z=3x1x2x3 2x13x24x312

s.t. 4x1x2x38 3x1x23x36 x10,x2无约束，x30

运算检验：

目标函数最优值为 : 6

第15页 共27页当前值 当前值 上限 无上限无上限上限 无上限无上限

内蒙古科技大学课程设计

变量 最优解 相差值 ------- -------- -------- x1 2 0 x2 0 0 x3 0 3.286 约束 松弛/剩余变量 ------- ------------- -------- 1 8 0 2 0 -0.857 3 0 0.143 目标函数系数范围 :

变量 下限 ------- -------- -------- -------- x1 -1.6 3 x2 无下限 1 1 x3 无下限 -2 1.286 常数项数范围 :

约束 下限 ------- -------- -------- -------- 1 4 12 2 -6 8 8 3 6 6

6.minz=-3x1+x2+x3-x4 x1x2x3x40 s.t．2x12x23x33x49

第16页 共27页对偶价格 当前值 当前值 上限 无上限 上限 无上限 无上限

内蒙古科技大学课程设计

. x1x22x3x6

x1,x2,x3,x40

运算检验：

目标函数最优值为 : 7

变量 最优解 相差值 ------- -------- --------

x1 1 0 x2 1 0 x3 3 0 x4 0 32.333

约束 松弛/剩余变量 对偶价格 ------- ------------- -------- 1 0 .667 2 0 7

3 0 -11.667 目标函数系数范围 :

变量 下限 当前值 上限 ------- -------- -------- -------- x1 无下限 -3 3.929 x2 -6.462 1 无上限 x3 -3.467 3 无上限 x4 -33.333 -1 无上限 常数项数范围 :

约束 下限 当前值 上限

------- -------- -------- --------

1 -3 0 无上限 2 8 9 10 3 5.4 6 6.75

7. min z=5x12x23x32x4 x12x23x34x47

第17页 共27页

内蒙古科技大学课程设计

s.t. 2x12x2x32x43 xj0 (j=1,…,4)

运算检验：

目标函数最优值为 : 5

变量 最优解 相差值 ------- -------- -------- x1 0 9 x2 0 0 x3 1 0 x4 1 0 约束 松弛/剩余变量 ------- ------------- -------- 1 0 -2 2 0 3 目标函数系数范围 :

变量 下限 ------- -------- -------- -------- x1 -4 5 x2 -2 -2 x3 3 3 x4 无下限 2 2 常数项数范围 :

约束 下限 ------- -------- -------- -------- 1 6 7 9 2 2.333 3 3.5

第18页 共27页对偶价格 当前值 当前值 上限 无上限 无上限 无上限上限

内蒙古科技大学课程设计

二、运输问题

8.下列表中的数据是某公司的甲、乙、丙三个分厂向公司所属四个门市部运送单位产品的运费。请给出总运费最低的运费值。

表2-7

销产 地 地 1 8 5 15 5 2 2 2 1 10 3 9 3 8 10 4 7 8 15 15 供应量 5 20 15 甲 乙 丙 需求 运算检验： 最优解如下

******************************************** 起 至 销点

发点 1 2 3 4 -------- ----- ----- ----- ----- 1 0 0 0 5 2 5 0 5 10 3 0 10 5 0

此运输问题的成本或收益为: 205

9.运输问题 产 销 地 地 B1 2 B2 11 B3 4 B4 4 供应量 6 A1 第19页 共27页

内蒙古科技大学课程设计

A2 A3 需求量 运算检验：最优解如下

******************************************** 起 至 销点

发点 1 2 3 4 -------- ----- ----- ----- ----- 1 5 0 0 1 2 0 3 2 0 3 0 0 2 6

此运输问题的成本或收益为: 47 10.运输问题 产 销 地 地 10 7 5 3 8 3 5 1 4 9 2 7 5 8 B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 6 5 6 供应量 7 4 9 A1 A2 A3 需求量 运算检验：最优解如下

******************************************** 起 至 销点

发点 1 2 3 4 -------- ----- ----- ----- ----- 1 2 0 5 0 2 1 0 0 3 3 0 6 0 3 此运输问题的成本或收益为: 79

第20页 共27页

内蒙古科技大学课程设计

11.运输问题 产 销 地 地 B1 8 6 5 10 B2 4 9 3 10 B3 1 4 4 20 B4 2 7 3 15 供应量 7 25 26 A1 A2 A3 需求量 运算检验：最优解如下

******************************************** 起 至 销点

发点 1 2 3 4 -------- ----- ----- ----- ----- 1 0 0 7 0 2 12 0 13 0 3 0 10 0 15

此运输问题的成本或收益为: 206

三、最短路问题

12.最短路问题

A 7 D 4 1 5 6 6 S B T 4 1 5 E 2 8 C 5 从节点S到节点T的最短路 ************************* 起点 终点 距离 ---- ---- ---- S A 4 A B 1

第21页 共27页

内蒙古科技大学课程设计

B D 5 D T 6

此问题的解为:16

13.最短路问题

1 3 1 9 2 3 5 7 4 V1 V2 8 5 3 8 10 2 4 7

运算检验：

从节点 v1到节点v2的最短路 ************************* 起点 终点 距离 ---- ---- ---- 7 1 9 1 3 1 3 6 3

此问题的解为:13 14.最短路问题

V1 V2 2 2

4 3 Vt 5 1 Vs

3 V3 V4

运算检验：

从节点 Vs到节点Vt的最大流 ************************* 起点 终点 距离 ---- ---- ----

第22页 共27页

1 2 内蒙古科技大学课程设计

Vs V1 2 V1 V3 1 V1 V2 2 V3 V1 0 V3 V4 0 V2 V4 0 V2 V3 0 V2 Vt 3 V4 Vt 0

此问题的解为:3

四、最大流问题

15.最大流问题

2 60 50 5 80 40 70 1 3 7 50 6 40 70 30 4

从节点 1到节点7的最大流

*************************

起点 终点 距离

---- ---- ---- 1 2 70 1 3 50 1 4 30 2 5 30 2 6 40 3 5 50 4 6 30 5 7 80 6 7 70

此问题的解为:150

第23页 共27页

内蒙古科技大学课程设计

16.最大流问题

A D （0,3） （0,4） (0,5)

（(0,1) S T ） （0,5） (0,2) （ 0,2 B ） C (0,2) 0,1

运算检验：

从节点 1到节点6的最大流 ************************* 起点 终点 距离 ---- ---- ---- S A 3 S B 2 A C 0 B D 3 B C 2 C A 0 C D 0 C T 2 D T 3

此问题的解为:5 17.最小费用最大流问题

1 (4,1) (7,6) s t

2

第24页 共27页

(8,4) (3,2) (2,3) (5,2) (6,1) 3 内蒙古科技大学课程设计

运算检验：

从节点 4到节点5的最大流 *************************

起点 终点 流量 费用 ---- ---- ---- ---- s 1 4 1 s 2 8 4 1 2 2 2 1 3 2 3 2 3 3 1 2 t 7 6 3 t 5 2 此问题的最大流为:12

此问题的最小费用为:101

18.最小费用最大流问题

(7,7) 1 2 (7,2) （10,9） (5,1) (5,3) s t (7,2) (10,10) （5,3） 3 4 (8,4) 运算检验： 从节点 s到节点t的最大流 *************************

起点 终点 流量 费用 ---- ---- ---- ---- s 1 7 2 s 2 8 10 1 3 2 7

第25页 共27页

内蒙古科技大学课程设计

1 2 5 3 2 3 5 1 2 4 8 4 3 4 5 2 3 t 10 9 4 t 5 3 此问题的最大流为:15

此问题的最小费用为:275

五、最小支撑树问题

19.最小支撑树问题

4 1 4

1

2 3

2 2 3 3 5 7 3

2 4

5 2 6

运算检验：

此问题的最小生成树如下： ************************* 起点 终点 距离 ---- ---- ---- 1 3 1 3 2 2 3 5 2 5 4 2 5 6 3 4 7 3 此问题的解为:13

第26页 共27页

内蒙古科技大学课程设计

20.最小支撑树问题 2

7 2 5 5

1 3 5 7 5 1 3 1 4 4

4 6 运算检验：

此问题的最小生成树如下： ************************* 起点 终点 距离 ---- ---- ---- 1 2 2 2 3 2 3 4 1 3 6 3 6 5 1 5 7 5 此问题的解为:14

参考文献：

《运筹学》 作者：宋学峰 东南大学出版社 2011年一月出版

《运筹学基础及应用》 作者：胡运权 高等教育出版社 2008年6月出版 《运筹学实用教程》 作者：宁宣熙 科学出版社 2007年4月出版

2 第27页 共27页