1、广东工业大学试卷用纸，共 3 页，第 1 页学 院： 专 业： 学 号： 姓 名： 装 订 线广东工业大学期中考试试卷 ( A )课程名称: 运筹学 考试时间: 第 十六 周 星期二 (12 月 17 日)题 号 一 二 三 四 五 六 七 八 九 十 总分评卷得分一、 单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确答案的字母写这答题纸上。 （10 分, 每小题 2 分）1、使用人工变量法求解极大化线性规划问题时，当所有的检验数 ，0j在基变量中仍含有非零的人工变量，表明该线性规划问题（ ）A. 有唯一的最优解； B. 有无穷多个最优解；C. 无可行解；D. 为无界解2、对偶
2、单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ ）Ab 列元素不小于零 B检验数都大于零C检验数都不小于零 D检验数都不大于零 3、在产销平衡运输问题中，设产地为 个，销地为 个，那么基可行解中mn非零变量的个数（ ）A. 不能大于(m+n-1) ； B. 不能小于(m+n-1)； C. 等于(m+n-1) ； D. 不确定。4、如 果 要 使 目 标 规 划 实 际 实 现 值 不 超 过 目 标 值 。 则 相 应 的 偏 离 变 量 应 满 足 （ ）A. B. C. D. 0d0d0d0,d5、下列说法正确的为（ ） A如果线性规划的原问题存在可行解，则其对偶问题也一定存在可
3、行解 B如果线性规划的对偶问题无可行解，则原问题也一定无可行解 C在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数D如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解广东工业大学试卷用纸，共 3 页，第 2 页二、判断下列说法是否正确。正确的在括号内打“” ，错误的打“” 。 （18 分，每小题 2 分）1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。 （ ）2、单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 （ ）3、任何线性规划问题存在并具有惟一
4、的对偶问题。 （ ） 4、若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。（ ） 5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。 （ ）6、如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数 ，k最有调运方案将不会发生变化。 （ ） 7、目标规划模型中，应同时包含绝对约束与目标约束。 （ ）8、线性规划问题是目标规划问题的一种特殊形式。 （ ）9、指派问题效率矩阵的每个元素都乘上同一常数 k，将不影响最优指派方案。 （ ） 三、解答题。 （72 分）1、 （ 20 分）用单纯形
5、法求解 ；并对以下情况作灵敏度分析：（1）2121max34680,zxx广东工业大学试卷用纸，共 3 页，第 3 页求 的变化范围；（ 2）若右边常数向量变为 ，分析最优解的变化。2c 205b2、（15 分）已知线性规划问题： 12341234.,0maxstzx其对偶问题最优解为 ，试根据对偶理论来求出原问题的最优解。12.,0.y广东工业大学试卷用纸，共 3 页，第 4 页3、（15 分）用表上作业法求下表中给出的运输问题的最优解。销地产地 甲 乙 丙 丁 产量 3 2 7 6 50 7 5 2 3 60 2 5 4 5 25销量 60 40 20 154、 （12 分）求下表所示效率
6、矩阵的指派问题的最小解，工作工人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 95、 （10 分）用大 M 法求解 023511xtsz,.min广东工业大学试卷用纸，共 3 页，第 5 页广东工业大学期中考试试卷参考答案及评分标准 ( A 卷 )课程名称: 运筹学 考试时间: 2009 年 12 月 17 日 (第 16 周 星期 四 )一、单项选择题：1-5 CDABD （每题 2 分）二、判断题：1-5 6-10 （每题 2 分）三、解答题：1、解：加入人工变量，化问题为标准型式如下：(3
7、 分)12345312453max0.68,0zxxstxx下面用单纯形表进行计算得终表为： jc3 3 0 0 0BC基 b1x23x45x3 2x3/2 0 1 3/2 0 -1/40 43 0 0 -2 1 1/23 1x5/2 1 0 -1/2 0 1/4jcz0 0 -3 0 0广东工业大学试卷用纸，共 3 页，第 6 页（5 分）所以原最优解为 *(/2,30,)TX（2 分）（1）设 变化 ，将 得变化带入最终单纯形表得 的变化范围为 ； 2c2c2c21c（5 分）（2）若右边常数向量变为 ，将变化带入最终单纯形表得：最优基解不205b变，最优解的值由（3，0） T 变为（10
8、/3，0） T。 （5 分）2、解：（1）该问题的对偶问题为：（5 分）121212min0.34,0wysty将 带入约束条件的为严格不等式，由互不松弛性得12.,.y，因为 故有：*0x12,0y（6 分）34*342,x最 后 求 得最优解： （2 分）0TX目标函数最优值： （2 分） *28z3、解：因为销量：3+5+6+4+3=21；产量：9+4+8=21 ；为产销平衡的运输问题。 （1广东工业大学试卷用纸，共 3 页，第 7 页分）由最小元素法求初始解：销地产地 甲 乙 丙 丁 戊 产量 4 5 9 4 4 3 1 1 3 8销量 3 5 4 6 3（5 分）用位势法检验得：销地
9、产地甲 乙 丙 丁 戊 U 10 1 4 5 7 0 11 4 12 30 12 -9 3 1 1 1 3 1V 0 19 5 9 3（7 分）所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。此时的总运费： 。 （2 分）min45910320134150z4、解：广东工业大学试卷用纸，共 3 页，第 8 页系数矩阵为：12798614504079（3 分） 从系数矩阵的每行元素减去该行的最小元素，得： 520317984065经变换之后最后得到矩阵：7024385140相应的解矩阵： （13 分）1001由解矩阵得最有指派方案：甲B，乙D,丙E，丁C，戊A或者甲B, 乙
10、C, 丙E ，丁D，戊A （ 2 分）所需总时间为：Minz=32 （ 2 分）5、解：将问题标准后，构造辅助为：广东工业大学试卷用纸，共 3 页，第 9 页12563461min.().0,0zxMxst以 为初始基变量，列单纯形表计算如下：56,xjc1 1.5 0 0 M MBC基 bx23x45x60 5x3 1 3 -1 0 1 03 62 1 1 0 -1 0 1jcz1-2M 1.5-4M M M 0 00 2x1 1/3 1 -1/3 0 1/3 00 61 2/3 0 1/3 -1 -1/3 1jcz0.5-2M/3 0 0.5-M/3 M 4M/3-0.5 00 2x1/2 0 1 -1/2 1/2 1/2 -1/23 13/2 1 0 1/2 -3/2 -1/2 3/2jcz0 0 1/4 3/4 M-1/4 M-3/4由于所有系数都为正，所以此为最优解， 3/210x最优目标函数值为： 。9/4z
