【强烈推荐】运筹学毕业论文
运筹学课程设计
目录
第一章自编题
一、运输规划问题
包头市某冰箱工厂有三个分厂，生产同一种冰箱，供应该厂在市内的四个门市部销售。已知三个分厂的日生产能力分别是50、60、50台。四个门市部的日销售量分别是40、40、60、20台。从各个分厂运往各门市部的运费如表1-11所示。试安排一个运费最低的运输计划。
表1-11
解,（1）运用最小元素法求解，得初始基本可行解，如下表1-12
表1-12
（2）用位势法计算所有非基变量检验数，求得如下表1-13
表1-13
（3）利用闭回路法进一步求解：
表1-14
（4）得出新方案，如表1-15
表1-15
（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
二、指派问题
现有四项不同的任务，分别由四个人去完成。因四个人的专长不同，所以每个人完成的任务所需的时间也不同(如表1-21),试问如何安排他们的工作才能使总的工作时间最少？
表1-21 （单位：小时）
解：（1）变换效率系数矩阵，使其每行没列都出现0元素
10 9 7 8 （-7） 3 2 0 1
C ij = 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-32
1 2 6
7
3 5
4 8
图1-33
1 2 6
7
3 5
4 8
图1-34
1 2 6
7
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
约束松弛剩余变量对偶价格
1 0 .7
2 3 0
3 0 .8
4 5 0
目标函数系数范围 :
变量下限当前值上
限
X1 1 3 无上限
X2 -1.5 2 6
常数项数范围 :
约束下限当前值
上限
1 1
2 22
26.286
2 7 10 无上限
3 4.5 7 12
4 -4 1 无上限
2. max z=
s.t.
运算检验：
目标函数最优值为 : 31
变量最优解相差值
13 0
5 0
约束松弛剩余变量对偶价格
1 5 0
2 9 0
3 0 .5
4 0 .5
目标函数系数范围 :
变量下限当前值上
限
1 2 3
.667 1 2
常数项数范围 :
约束下限当前值
上限
1 5 10 无上限
2 51 60 无上限
3 14.667 18 19.385
4 38 44 54
3. min z=
s.t.
运算检验：
目标函数最优值为 : 55
变量最优解相差值
2 0
1 0
约束松弛剩余变量对偶价格
1 0 -5
2 7 0
3 0 -10
目标函数系数范围 :
变量下限当前值上
限
15 20 30
10 15 20
常数项数范围 :
约束下限当前值
上限
1 3.6 5 6
2 -4
3 无上限
3 2.5 3 4
4． max z=
s.t.
运算检验：
目标函数最优值为 : 18
变量最优解相差值
21 0
24 0
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=
s.t.
,无约束，
运算检验：
目标函数最优值为 : 6
变量最优解相差值
2 0
0 0
0 3.286
约束松弛剩余变量对偶价格
1 8 0
2 0 -0.857
3 0 0.143
目标函数系数范围 :
变量下限当前值上
限
-1.6 3 无
上限
无下限 1 1
无下限-2 1.286
常数项数范围 :
约束下限当前值
上限
1 4 1
2 无上限
2 -6 8 8
3 6 6 无上限
6.minz=-3x1+x2+x3-x4
s.t．
.
运算检验：
目标函数最优值为 : 7
变量最优解相差值
1 0
1 0
3 0
0 32.333
约束松弛剩余变量对偶价格
1 0 .667
2 0 7
3 0 -11.667
目标函数系数范围 :
变量下限当前值上
限
无下限-3 3.929
-6.462 1 无
上限
-3.467 3 无
上限
-33.333 -1 无
上限
常数项数范围 :
约束下限当前值上
限
1 -3 0 无上限
2 8 9 10
3 5.
4 6
6.75
7. min z=
s.t.
(j=1, (4)
运算检验：
目标函数最优值为 : 5
变量最优解相差值
0 9
0 0
1 0
1 0
约束松弛剩余变量对偶价格
1 0 -2
2 0 3
目标函数系数范围 :
变量下限当前值上
限
-4 5 无
上限
-2 -2 无
上限
3 3 无
上限
无下限 2 2
常数项数范围 :
约束下限当前值
上限
1 6 7 9
2 2.33
3 3
3.5
二、运输问题
8.下列表中的数据是某公司的甲、乙、丙三个分厂向公司所属四个门市部运送单位产品的运费。请给出总运费最低的运费值。
表2-7
运算检验：
最优解如下
********************************************
起至销点
发点 1 2 3 4
1 0 0 0 5
2 5 0 5 10
3 0 10 5 0
此运输问题的成本或收益为: 205
9.运输问题
运算检验：最优解如下
********************************************
起至销点
发点 1 2 3 4
1 5 0 0 1
2 0
3 2 0
3 0 0 2 6
此运输问题的成本或收益为: 47
10.运输问题
运算检验：最优解如下
********************************************
起至销点
发点 1 2 3 4