青岛大学运筹学2013(1)考研试题研究生入学考试试题考研真题
● 摘要
青岛大学2013年硕士研究生入学考试试题
科目代码：824科目名称：运筹学(1)（共2页）
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
第一题（15分）：简答题
（1）简述线性规划问题的可行解、基可行解以及最优解三者之间的关系。（10分）
（2）简述整数规划问题的最优解与它的松弛问题的最优解之间的关系。（5分）第二题（20分）：判断对错，并将错误的论断改正过来：（每题5分）
（1）线性规划问题一定存在可行解。
（2）若线性规划问题存在可行解，其对偶问题不一定存在可行解。
（3）产销平衡运输问题中，用最小元素法求得的初始基可行解一定是最优解。
（4）线性规划问题的目标函数中系数的变化不会影响到检验数的变化。
第三题（35分）：设有如下线性规划问题：
max Z=4x 1+2x 2
⎧x 1≤2⎪⎨x 1+2x 2≤4
⎪x , x ≥0⎩12
（1）
（2）
（3）
（4）
（5）将该线性规划问题化为标准形式；（5分）用图解法求解该线性规划问题；（5分）利用单纯形法求解该线性规划问题；（10分）说明该线性规划问题有唯一最优解、无穷多最优解、还是无界解；（5分）指出单纯形法求解过程中每一步所得基可行解分别对应图解法中的哪一个顶点；（5分）
（6）设目标函数中x 2的系数1有扰动，即（1+λ），其他条件不变。试分析λ在什么范围
内变化时，问题的最优基不变。（5分）
第四题（20分）：若线性规划的原问题如下：
max z =CX
⎧AX ≤b ⎨⎩X ≥0
（1）写出其对偶问题；（8分）
（2）若为原问题的可行解，为其对偶问题的可行解，证明：C ≤b ' ；（6分）
（3）若为原问题的可行解，为其对偶问题的可行解，且有C =b ' ，证明：为