运
筹
学
考
卷
1 / 51 / 5
考试时间: 第十六周
题号一二三四五六七八九十总分
评卷得分
:
名
一、单项选择题。
下列每题给出的四个答案中只有一个是正确的,将表示正确
姓
答案的字母写这答题纸上。
(10 分, 每小题2 分)
1、使用人工变量法求解极大化线性规划问题时,当所有的检验数j 0 ,在
线
基变量中仍含有非零的人工变量,表明该线性规划问题()
A. 有唯一的最优解;
B. 有无穷多个最优解;
C. 无可行解;
D. 为无界解
2、对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中():
号
A.b 列元素不小于零B.检验数都大于零
学
C.检验数都不小于零D.检验数都不大于零
3、在产销平衡运输问题中,设产地为m 个,销地为n 个,那么基可行解中非
零变量的个数()
订
A. 不能大于(m+n-1);
B. 不能小于(m+n-1);
C. 等于(m+n-1);
D. 不确定。
4、如果要使目标规划实际实现值不超过目标值。
则相应的偏离变量应满足()
A. d 0
B. d 0
C. d 0
D. d 0,d 0
5、下列说法正确的为()
:
业
A.如果线性规划的原问题存在可行解,则其对偶问题也一定存在可行解
专
B.如果线性规划的对偶问题无可行解,则原问题也一定无可行解
装
C.在互为对偶的一对原问题与对偶问题中,不管原问题是求极大或极小,原
问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数
D.如果线性规划问题原问题有无界解,那么其对偶问题必定无可行解
:
院
学
2 / 52 / 5
二、判断下列说法是否正确。
正确的在括号内打“√”,错误的打“×”。
(18 分,每
小题2 分)
1、如线性规划问题存在最优解,则最优解一定对应可行域边界上的一个点。
()
2、单纯形法计算中,如不按最小比列原则选取换出变量,则在下一个解中至少有一
个基变量的值为负。
()
3、任何线性规划问题存在并具有惟一的对偶问题。
()
4、若线性规划的原问题有无穷多最优解,则其最偶问题也一定具有无穷多最优解。
()5、运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列四种情况之
一:有惟一最优解,有无穷多最优解,无界解,无可行解。
()
6、如果运输问题的单位运价表的某一行(或某一列)元素再乘上那个一个常数k ,
最有调运方案将不会发生变化。
()
7、目标规划模型中,应同时包含绝对约束与目标约束。
()
8、线性规划问题是目标规划问题的一种特殊形式。
()
9、指派问题效率矩阵的每个元素都乘上同一常数k,将不影响最优指派方案。
()
三、解答题。
(72 分)
max z 3x 3x
1 2
1、(20分)用单纯形法求解
x x
1 2
x x
1 2
4
2
;并对以下情况作灵敏度分析:(1)求
6x 2 x 18
1 2
x 0, x 0
1 2
5
c 的变化范围;(2)若右边常数向量变为2 b ,分析最优解的变化。
2
20
2、(15 分)已知线性规划问题:
max z x 2x 3x 4x
1 2 3 4
s. t. x 2x 2x 3x 20
1 2 3 4
2x x 3x 2x 20
1 2 3 4
x x x x
, , , 0
1 2 3 4
其对偶问题最优解为y1 1.2, y2 0.2 ,试根据对偶理论来求出原问题的最优解。
3 / 53 / 5
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 工人
甲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
min z x
1 1.5x
2
5、(10分)用大M 法求解s.t. x
1
x
1
3x
2
x
2
3
2
x
1
0, x
2
4 / 54 / 5
参考答案及评分标准( A 卷)
课程名称: 运筹学
考试时间: 2 ( 第16 周
一、单项选择题:
1-5 CDABD (每题2 分)
二、判断题:
1-5 √√√√×6-10 ××√×√(每题2 分)
三、解答题:
1、解:
加入人工变量,化问题为标准型式如下:
max z 3x 3x 0x 0x 0x
1 2 3 4 5
x x x
1 2 3
4
s.t
x x x
2
1 2 4
6x 2x x 18
1 2 5
x ,x ,x ,x ,x 0
1 2 3 4 5
(3 分)
下面用单纯形表进行计算得终表为:
c 3 3 0 0 0
j
C 基b B x x2 x3 x4 x5 1
0 x 1 0 2/3 1 0 -1/6
3
0 x 5 0 4/3 0 1 1/6
4
3 x 3 1 1/3 0 0 1/6
1
c z 0 0 0 0 -1/2
j j
(5 分)
所以原最优解为
* T
X (3,0,1,5,0) (2 分)
(1)设c2 变化,将c2 得变化带入最终单纯形表得c2 的变化范围为c2 1;
(5 分)
5
(2)若右边常数向量变为b,将变化带入最终单纯形表得:最优基解不
2
5 / 55 / 5
20
变,最优解的值由(3,0)T 变为(10/3,0)T。
(5 分)。