2007运筹学试题及答案(1).doc

2007年运筹学期末试题 一、选择题（本题共5小题，每小题3分，满分15分，把答案填在题后括号内.） 1．使用人工变量法求解极大化线性规划问题时，当所有的检验数，在基变量中仍含有非零的人工变量，表明该线性规划问题（ C ） A. 有唯一的最优解； B. 有无穷多个最优解；C. 无可行解；D. 为无界解 2、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ D ） A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零 3、对于线性规划问题，下列说法正确的是（ D ） A 线性规划问题可能没有可行解 B 在图解法上，线性规划问题的可行解区域都是“凸”区域 C 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达 D 上述说法都正确 4、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（ B ） A. B. C. D. 5、下列说法正确的为（ D ） A．如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 B．如果线性规划的对偶问题无可行解，则原问题也一定无可行解 C．在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可 行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D．如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解 二、判断题：正确的在括号内打“√”，错误的打“×”。(本题共5小题，每小题3分，满分15分，) 1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ √ ） 2、单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 （ √ ） 3、任何线性规划问题存在并具有惟一的对偶问题。 （ √ ） 4、目标规划模型中，应同时包含绝对约束与目标约束。 （ × ） 5、如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解。 （ × ） 三（15分）、已知线性规划问题： 其对偶问题最优解为，试根据对偶理论来求出原问题的最优解。 解：该问题的对偶问题为： （ 分） 将带入约束条件的①②为严格不等式，由互不松弛性得，因为 故有： （ 分） 最优解： （ 分） 目标函数最优值： 四（10分）、已知目标规划模型为： 试用图解法求满意解。 五（10分）、 求下表所示效率矩阵的指派问题的最小解， 工作 工人 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 解：系数矩阵为： 从系数矩阵的每行元素减去该行的最小元素，得： 经变换之后最后得到矩阵： 相应的解矩阵： 由解矩阵得最有指派方案：甲—B，乙—D,丙—E，丁—C，戊—A 或者甲—B,乙—C,丙—E，丁—D，戊—A 所需总时间为：Minz=32 六（20分）、用表上作业法求下表中给出的运输问题的最优解。 销地 产地 甲 乙 丙 丁 产量 Ⅰ 3 2 7 6 50 Ⅱ 7 5 2 3 60 Ⅲ 2 5 4 5 25 销量 60 40 20 15 解： 因为销量：3+5+6+4+3=21；产量：9+4+8=21；为产销平衡的运输问题。 （ 分） 由最小元素法求初始解： 销地 产地 甲 乙 丙 丁 戊 产量 Ⅰ 4 5 9 Ⅱ 4 4 Ⅲ 3 1 1 3 8 销量 3 5 4 6 3 （ 分） 用位势法检验得： 销地 产地 甲 乙 丙 丁 戊 U Ⅰ 4 5 0 Ⅱ 4 -9 Ⅲ 3 1 1 3 1 V 0 19 5 9 3 （ 分） 所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。 此时的总运费：。（ 分） 七（15分）、计算下图所示的从 A 到 E 的最短路。 1 4 3 4 1 1 3 2 2 2 4 3 3 5 5 3 A 3 B1 B2 B3 C1 C2 D1 D2 D3 E 3 1 5