运筹学试卷及答案
运
筹
学
考
卷
二、判断下列说法是否正确。正确的在括号内打“√”，错误的打“×”。（18分，每小题2分）
1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（）
2、单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。（）
3、任何线性规划问题存在并具有惟一的对偶问题。（）
7、目标规划模型中，应同时包含绝对约束与目标约束。（）
8、线性规划问题是目标规划问题的一种特殊形式。（）
9、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（）
三、解答题。（72分）
1、（20分）用单纯形法求解 ；并对以下情况作灵敏度分析：（1）求 的变化范围；（2）若右边常数向量变为 ，分析最优解的变化。
最优目标函数值为： 。
2、（15分）已知线性规划问题：
其对偶问题最优解为 ，试根据对偶理论来求出原问题的最优解。
3、（15分）用表上作业法求下表中给出的运输问题的最优解。
销地
产地
甲
乙
丙
丁
产量
Ⅰ
3
2
7
6
50
Ⅱ
7
5
2
3
60
Ⅲ
2
5
4
5
25
销量
60
40
20
15
4、（12分）求下表所示效率矩阵的指派问题的最小解，
工作
工人
A
B
C
D
E
0
1
0
3
2
1
1
0
-1
0
1
1-2M
1.5-4M
M
M
0
0
0
1Hale Waihona Puke 1/31-1/3
0
1/3
0
0
1
2/3
0
1/3
-1
-1/3
1
0.5-2M/3
0
0.5-M/3
M
4M/3-0.5
0
0
1/2
0
1
-1/2
1/2
1/2
-1/2
3
3/2
1
0
1/2
-3/2
-1/2
3/2
0
0
1/4
3/4
M-1/4
M-3/4
由于所有系数都为正，所以此为最优解，
4、若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。
（）
5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。（）
6、如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数 ，最有调运方案将不会发生变化。（）
Ⅰ
4
5
9
Ⅱ
4
4
Ⅲ
3
1
1
3
8
销量
3
5
4
6
3
（5分）
用位势法检验得：
销地
产地
甲
乙
丙
丁
戊
U
Ⅰ
4
5
0
Ⅱ
4
-9
Ⅲ
3
1
1
3
1
V
0
19
5
9
3
（7分）
所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。
此时的总运费： 。（2分）
4、解：
系数矩阵为：
（3分）
从系数矩阵的每行元素减去该行的最小元素，得：
经变换之后最后得到矩阵：
相应的解矩阵： （13分）
由解矩阵得最有指派方案：甲—B，乙—D,丙—E，丁—C，戊—A
或者甲—B,乙—C,丙—E，丁—D，戊—A（2分）
所需总时间为：Minz=32（2分）
5、解：将问题标准后，构造辅助为：
以 为初始基变量，列单纯形表计算如下：
1
1.5
0
0
M
M
基
0
3
1
3
-1
2、解：
（1）该问题的对偶问题为：
（5分）
将 带入约束条件的①②为严格不等式，由互不松弛性得 ，因为 故有：
（6分）
最优解： （2分）
目标函数最优值： （2分）
3、解：
因为销量：3+5+6+4+3=21；产量：9+4+8=21；为产销平衡的运输问题。（1分）
由最小元素法求初始解：
销地
产地
甲
乙
丙
丁
戊
产量
甲
12
7
9
7
9
乙
8
9
6
6
6
丙
7
17
12
14
9
丁
15
14
6
6
10
戊
14
10
7
10
9
5、（10分）用大M法求解
参考答案及评分标准 ( A卷 )
课程名称:运筹学
考试时间: 2 (第16周
一、单项选择题：
1-5 CDABD（每题2分）
二、判断题：
1-5√√√√×6-10××√×√（每题2分）
三、解答题：
1、解：
加入人工变量，化问题为标准型式如下：
(3分)
下面用单纯形表进行计算得终表为：
3
3
0
0
0
基
0
1
0
2/3
1
0
-1/6
0
5
0
4/3
0
1
1/6
3
3
1
1/3
0
0
1/6
0
0
0
0
-1/2
（5分）
所以原最优解为 （2分）
（1）设 变化 ，将 得变化带入最终单纯形表得 的变化范围为 ；（5分）
（2）若右边常数向量变为 ，将变化带入最终单纯形表得：最优基解不变，最优解的值由（3，0）T变为（10/3，0）T。（5分）