2011-2012学年第二学期研究生期末考
- 格式：doc
- 大小：206.00 KB
- 文档页数：10
2011-2012学年第二学期
国际工商学院研究生《运筹学》期末考试卷
姓名: 学号:
一．思辨简答（每题3分，共24分）
1. 线性规划的四大假设及其经济学涵义是什么？
2. 单纯形算法中，判定无可行解、唯一最优解、无穷多解、无界解的判据分别是什么？
3. 简述极点可行解、基本可行解与最优解之间的关系。
4. 简述“退化解”产生的原因、造成的后果、克服的方法。
5. 影响单纯形法计算性能的主要因素是什么？
6. “改进单纯形法”是单纯形法的主流程序实现形式，简述其特点。
7. 影子价格y 的经济学涵义？当0y >、0y =、0y <时，其经济学涵义及成因分别是什么？
8. 根据当前互补解对的性态，可以采用不同方法求解线性规划模型，填充下表：
二．分析计算（共64分） 1.（13分）对于下列LP
12341234134121234
1234max 2433241..22
222
,,0
Z x x x x x x x x x x x s t x x x x x x x x x x =-+-++++≤⎧⎪
-+≥-⎪⎪+≤⎨⎪+++=⎪⎪∈≥⎩ ,且
（1）（3分）写出其典式。
（2）（5分）用大M 法求解。
（3）（5分）用两阶段法求解。
2.（15分）推导单纯形表的矩阵形式：
（1）（5分）利用基矩阵B表示出一步单纯形迭代后的基向量
x和目标值Z。
B
（2）（10分）利用写出单纯形表的矩阵形式，完善下表中第n次迭代的系数矩阵及右端项，并写出详细推导过程。
3.（10分）已知模型：
121212123max 354224..3218,,0
Z x x x x s t x x x x x =+≤⎧⎪≤⎪⎨
+≤⎪⎪≥⎩ 其最终单纯形表为：
审核模型，发现参数有变：
（1）（5分）若考虑漏了约束122324x x +≤，请添加该约束，并在上表基础上继续计算，求得新的最优解。
（2）（5分）若1c 由3变为5，31a 由3变为2，请在上表基础上继续计算，求得新的最优解。
4.（12分）分别写出最短路径问题、最小支撑树问题、最大流问题、最小费用问题的线性规划模型。
5.（14分）已知拓扑图，其边上的记号意义是{边长|容量}。
（1）（7分）求节点s v 到t v 的最短路径，写出过程。
（2）（7分）求节点s v 到t v 的最大流量分配，写出过程。
三．证明（12分）
（互补松弛性）若(,)s x x 是线性规划{}m a x ,0c x A x b x ≤≥
的基可行解，(,)s y y 是对偶规划{}m i n ,0y b y A c y ≥≥的基可行解。
求证：(,)s x x 和(,)s y y 分别是互为对偶问题的最优解的充要条件
是0s s yx y x ==。
