2016年东南大学土木工程学院972运筹学考研冲刺模拟题及答案
● 摘要
一、证明题
1． 现有一个线性规划问题（P 1）:
, 其对偶问题的最优解为Y*=（y1, y2, y3, …ym ） 另有一线性规划（P 2）:
【答案】问题（P 2）的对偶问题为:
问题（P 2）的对偶问题为:
其中，d=（d 1, d 2, ...d 3） 。 求证:T
易见，问题（P 1）的对偶问题与问题（P 2）的对偶问题具有相同的约束条件，从而，问题（P 1）的对偶问 题的最优解
令问题（P 2）的对偶问题的最优解为一定是问题（P 2）的对偶问题的可行解。 ，则:
。
，试证
因为原问题与对偶问题的最优值相等，所以
2． 在M/M/1/N/∞模型中，如
应为，于是
t 。 时刻的顾客数N （t ）仍是一生灭过程，且有【答案】系统在
当t=+∞时，由系统的稳定状态概率可得
二、计算题
3． 己知线性整数规划:
相应伴随规划的最优解为:x 1=l，最优单纯形表为:
表
（l ）对x 2进行分枝，写出相应的分枝规划（不要求求解）;
（2）由最优单纯形表的第二个方程推导出割平面方程。
【答案】（1）对x 2进行分枝，将原问题分成B 1、B 2，其中B 1中，定x 2=l，再根据约束条件得出x l 的值，并计算目标函数值z 1; B 1中，定x 2=2，同样根据约束条件得出x 1的值，计算z 2; 2）比较二者大小，选择较优者，若满足 整数条件则停止分支; 否则再继续对x l 进行分支。 （2）第二个方程是:x l 一l/7u1+2/7u2=l，化为x l 一u 1=l一（6/7ul +2/7u2）
最终得割平面方程一6u 1一2u 2+u3=7。
4． 己知世界六大城市:P e ，N ，P a ，L ，T ，M 。试在表所示交通网络的数据中确定最小树。
表