2017年西南科技大学运筹学考研复试核心题库
● 摘要
一、简答题
1． 试写出M/M/1排队系统的Little 公式。
【答案】M/M/1排队系统的Little 公式为
2． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。
二、计算题
3． 某规划线性规划问题:
（1）写出其对偶问题;
（2）推导出原问题与对偶问题中目标函数之间的关系。 【答案】（1）其对偶问题为:
（2）若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。
证明:由于两者均有可行解，根据弱对偶性的推论，对原问题的目标函数值具有上界，对偶问题的目标函数 值具有下界，因此两者均具有最优解。又知当原问题为最优解时，其对偶问题的解为可行解，且有z=w。由最优 性知，这时两者的解均为最优解。
4． 在图中，分别求v 1至v 6，v 1至V 4，v 6至v Z 和v Z 至vs 的最短路和最短距离。
图
【答案】用Floyd 方法求解 令网络的权矩阵为
其中，
为
到
的距离
由表示从v i 到v j 点的或
直接有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得
表示从vi 到vj 点最多经v l ，v 2的最短路长，得
以此类推，
所以v l 至v 6的最短路是v 1一v 3一v 5一v 6，最短距离是-1; v l 至v 4的最短路是v 1一v 3一v 5一v 4，最短距离是3; v 6至v 2的最短路是v 6一v 4一v 2，最短距离是3: v 2至v 5的最短路是v 2一v3一v 5，最短距离1;
5． 利用库恩一塔克条件求解以下问题:
（l ）试写出库恩一塔克条件。
（2）a 满足什么条件以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（l ）所求问题变形为