2011-2012-2运筹学试卷A

：名 姓 线 ： 号 学 订 ： 业 专 装 ：院 学广东工业大学考试试卷 ( A ) 课程名称: 运筹学 试卷满分 100 分 考试时间: 2012年 7月 3日 (第 20 周 星期 三 ) 题 号 一 二 三 四 五 六 七 八 九 十 总分 评卷得分 评卷签名 复核得分 复核签名 一、判断题（每小题2分，共20分） 1、若线性规划问题的最优解同时在可行域的两个顶点达到，则最优解必有无穷多个。（ ） 2、某线性规划问题有n个变量，m个约束条件，则该线性规划问题全部基解的个数一定是Cmn. （ ） 3、 已知yi*为线性规划的对偶问题的最优解，如果yi*=0， 说明在最优生产计划中，第i种资源一定有剩余。（ ） 4、对偶问题的对偶问题一定是原问题。（ ） 5、在用表上作业法求解运输问题时，表中每个空格都有唯一的一条闭回路。 ( ) 6、目标规划中的正偏差变量应取正值，负偏差变量应取负值。（ ） 7、整数规划解的目标函数最优值一般优于其对应的松弛问题目标函数最优值。 （ ） 8、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（ ） 9、动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已经做出的决策。（ ） 10、在所有顶点数相同的无圈图中，树的边数最多。（ ） 二、填空题（共12分） 1、线性规划目标函数中各变量的系数cij发生变化，可能会影响到 ，如果导致不满足最优性，则后续步骤是用 继续迭代求最优解。（每空2分） 2、下图中，A点到E点的最短距离为 。（4分） B1512137C17A5D11B210C2751E153D24B31046C3 广东工业大学试卷用纸，共 3 页，第 页

3、已知目标规划问题 minz?{P1(d1??d1?),P2(2d2??d3?)}???x1?10x2?d1?d1?50?3x1?5x2?d2??d2??20?st????8x1?6x2??d3?d3?100????x1,x2,di,di?0,i?1,2,3(1)(2) (3)作图如下： x2I(3)AOHB(1)CDEF(2)Gx1 则该目标规划问题的满意解在 点。（填入字母） (4分) 三、已知线性规划问题 maxz?x1?3x2x3?5?x1??x1?2x2?x4?10?st??x5?4?x2??x1,x2,x3,x4,x5?0序号 （a） （b） （c） （d） （e） （f） x1 2 10 3 1 0 0 (1)(2) (3)下表中所列的解（a）——（f）均满足约束条件（1）（2）（3）， x2 4 0 0 4.5 2 4 x3 3 -5 2 4 5 5 x4 0 0 7 0 6 2 x5 0 4 4 -0.5 2 0 （1）哪些是可行解？哪些是基解？哪些是基可行解？（写出恰当的序号）。（6分） （2）用单纯形法求解该线性规划问题。（9分） 广东工业大学试卷用纸，共 3 页，第 页

四、已知线性规划问题 minz?2x1?x2?2x3??x1?x2?x3?4? ??x1?x2?kx3?6?x1?0,x2?0,x3无约束?其最优解为x1??5,x2?0,x3??1 请写出其对偶问题，求出对偶问题的最优解，求出k的值。 （13分） 五、已知运输表中的单位运价、产量、销量，求最优调运方案，并指出最优解是否唯一。（15分） 销地 产地 I II III 销量 A 10 20 30 25 B 15 40 35 115 C 20 15 40 60 D 20 30 55 30 E 40 30 25 70 产量 50 100 150 六、用隐枚举法求解以下0-1型整数规划问题，（10分） maxZ?4x1?3x2?x3?5x1?2x2?x3?6 ?st?4x1?2x2?x3?7?x1,x2,x3?0或1? 七、（1）不考虑边的方向性，假设括号里的第一个数字表示权，求最小生成树。（5分） （2）假设括号里的数字分别表示容量和流量，求vs到vt的最大流。（10分） v4 (1,1) v 1 (7,6) (4,3) (4,3) (3,2) vt (2,2) v (3,2) sV5 (3,2) (5,3) (8,3) (10,4) (4,2) v2 V3

广东工业大学试卷用纸，共 3 页，第 页

本文来源：https://www.bwwdw.com/article/myh3.html