2013运筹学试题及答案

1、 毕节学院考试试卷A 考试时间：第十九周星期三7月9日 题号 一 一 三 四 五 六 七 八 九 十 总分 评卷得分 单项选择题。以下每题给出的四个答案中只有一个是正确的，将表示正确 答案的字母写这答题纸上。10分，每题2分 1、使用人工变量法求解极大化线性规划问题时，当所有的检验数 Tj0,在 基变量中仍含有非零的人工变量，说明该线性规划问题 A.有唯一的最优解；B.有无穷多个最优解；C.无可行解；D.为无界解 2、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 A. b列元素不小于零 B.检验数都大于零 C .检验数都不小于零 D .检验数都不大于零 3、在产销平衡运输问题中，

2、设产地为 m m 个，销地为 n n 个，那么基可行解中非 零变量的个数 A.不能大于m+n-1; B.不能小于m+n-1; C.等于m+n-1; D.不确定。 4、如果要使目标规划实际实现值不超过目标值。那么相应的偏离变量应满足 A. d d 0 0 B. d =0d =0 C. d d- - = 0= 0 D. d d- - 0,d 00,d 0 5、以下说法正确的为 A .如果线性规划的原问题存在可行解，那么其对偶问题也一定存在可行解 B .如果线性规划的对偶问题无可行解，那么原问题也一定无可行解 C.在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原 问题可行解的目标函数

3、值都一定不超过其对偶问题可行解的目标函数 D .如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解 二、判断以下说法是否正确。正确的在括号内打，错误的打“X。18 分，每题2分 1、如线性规划问题存在最优解，那么最优解一定对应可行域边界上的一个点。 2、单纯形法计算中，如不按最小比列原那么选取换出变量，那么在下一个解中至少有一 个基变量的值为负。 毕节学院试卷出题用纸，共 4页，第2页 3、任何线性规划问题存在并具有惟一的对偶问题。 4、假设线性规划的原问题有无穷多最优解，那么其最偶问题也一定具有无穷多最优解。 5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现以下四种情况之

4、 一：有惟一最优解，有无穷多最优解，无界解，无可行解。 6、如果运输问题的单位运价表的某一行或某一列元素再乘上那个一个常数 k , 最有调运方案将不会发生变化。 7、目标规划模型中，应同时包含绝对约束与目标约束。 8、线性规划问题是目标规划问题的一种特殊形式。 9、指派问题效率矩阵的每个元素都乘上同一常数 k,将不影响最优指派方案。 三、解答题。72分 m max z =3x1 - 3x2 1、20分用单纯形法求解i x1 +x2 -4 ;并对以下情况作灵敏度分析：1求 -x1 x2 _2 6x1 +2x2 18 xi ：: 0, x2 :二 0 _ 一 5151 C C2的变化范围；2 2假

5、设右边常数向量变为5= 2 2 ，分析最优解的变化。 ：20 20 一 2、15分线性规划问题: maxz = x1 2x2 3x3 4x4 x1+2x2 + 2x3 + 3x420 s.tis.ti2x1 + x2+3x3 + 2x4 3 5、10分用大M法求解1 1 2 x1 x2 _ 2 x1 一 0, x2 一 0毕节学院试卷出题用纸，共 4页，第5页 毕节学院期末考试试卷参考答案及评分标准 A卷 课程名称: 考试时间：7月9日第19周星期 解答题 1、解: 参加人工变量，化问题为标准型式如下： maXz = 3X1 3X2 0X3 0X4 0X5 K +X2 +% =4 -Xi +X

6、2 +X4 =2 6K +2x2 +x5 =18 K,X2,X3,X4,X5 之 0 卜面用单纯形表进行计算得终表为: c cj 3 3 0 0 0 CB 基 b X X1 X X2 X X3 X X4 X X5 0 X X3 1 0 2/3 1 0 -1/6 0 X X4 5 0 4/3 0 1 1/6 3 X X1 3 1 1/3 0 0 1/6 0 0 0 0 -1/2 5 5 分 所以原最优解为 X =X =3,0,1,5,03,0,1,5,0 2 2 分 1 1设 C C2变化,将 C C2得变化带入最终单纯形表得 C C2的变化范围为6t1；、单项选择题: 1-5 CDABD 每题

7、2分 、判断题: 6-10 义 xVxV 每题2分 (3 分 5分 毕节学院试卷出题用纸，共 4页，第6页 一51 2假设右边常数向量变为b= 2，将变化带入最终单纯形表得：最优基解不变，最优解的值由3,0 巩 T变为10/3, 0 To 2、解： 1该问题的对偶问题为： min w = 20yl 20y2 ,y1 +2y2芝1 2y1+y2 22 st2必 +3y2 3 3y1+2丫2之4 %，丫2-0 将 y y =1.2, y=1.2, y2 =0.2=0.2 带入约束条件的为严格不等式，由互不松弛性得=0=02=0,0,因为 y y1,y,y2之。 故 有： * * 2x3 3x4 =

8、 20 3x3 +2x4 =20 6 分 * . * . 取后求得x3 =4,x4 =4 T 最优解：X =0,0,4,4 2 分 、 . . * 目标函数最优值：z =28 2分 3、解： 因为销量：3+5+6+4+3=21;产量：9+4+8=21;为产销平衡的运输问题。 1分 由最小元素法求初始解： 肖地 甲 乙 丙 丁 戊 里 5分 5分 毕节学院试卷出题用纸，共 4页，第7页 i 4 5 9 n 4 4 5分 毕节学院试卷出题用纸，共 4页，第8页 m 3 1 1 3 8 销量 3 5 4 6 3 5分 用位势法检验得: 销地 甲 乙 丙 丁 戊 U I 4 5 0 R 4 寇 -9

9、m 3 1 1 3 1 V 0 19 5 9 3 7分 所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。 止匕时的总运费：minz = 4M5+5M9+4x10+3Ml +1 父 20 + 1 父10 + 3父4 =150。2 分 4、解: 系数矩阵为: 12 7 9 7 9 8 9 6 6 6 I 7 17 12 14 9 3分 15 14 6 6 10 4 10 7 10 9 _ 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5_ 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 04

10、14 3_从系数矩阵的每行元素减去该行的最小元素，得: 经变换之后最后得到矩阵: 0 10 0 0 0 0 0 1 0 相应的解矩阵：0 0 0 0 1 0 0 10 0 1 0 0 0 0_ 由解矩阵得最有指派方案：甲一B ,乙一D,丙一E, 丁一 C,戊一A 或者甲一B,乙一C,丙一E, 丁一 D,戊一A 2分 所需总时间为：Minz=32 2分 5、解：将问题标准后，构造辅助为： min z =K +1.5x2 + M (x #x )6 st x +3x2x /x =5 3 X1 x2-x 4 x 6 2 x _0, | ,x6 -0 以 x x5, , 2 2 为初始基变量，列单纯形表计算如下: c cj 1 1.5 0 0 M M CB 基 b XI x x2 x x3 x x4 x x5 x x6 0 x 3 1 3 -1 0 1 0 3 x x6 2 1 1 0 -1 0 1 c cj W 1-2M 1.5-4M M M 0 0 0 x x2 1 1/3 1 -1/3 0 1/3 0 0 x 1 2/3 0 1/3 -1 -1/3 1 C Cj?j 0.5-2M/3 0 0.5-M/3 M 4M/3-0.5 0 0 x x2 1/2 0 1 -1/2