2016年哈尔滨理工大学管理学院运筹学复试笔试仿真模拟题
● 摘要
一、计算题
1． 求解下列矩阵对策，其中赢得矩阵A 分别为
【答案】（l ）令矩阵对策为G={S1，S 2; A}，
其中表示在策略
，与策略
下的赢得值，则
，矩阵A 中
2． 对于线性规划问题:
（l ）用单纯形法求解最优解，最优值; （2）写出最优基，最优基的逆阵;
（3）写出对偶规划，对偶规划的最优解。
【答案】加入松弛变量后，用单纯形表计算如表所示:
表
得最优解最优基是
-1
, 逆阵是B =
（3）对偶规划模型是
由最终单纯形表可知
3． 对于线性规划问题:
设A 中存在可行基B ，其对应的基变量和非基变量分别为X B 和X N ，C B 和C N 为它们在目标函数中的系数， 则对应干基B 的单纯形表如表所示
表
若B 为最优基，则上述单纯形表为最优单纯形表。当原问题的某右端常数项b k 变为b k +△b k 时，
-1-1
试推导出使 最优基不变的△b k 的变化范围。（提示，自己假定B 及B b 的具体形式）
【答案】设
，且
, 其中Pi 为列向量,
，则有
, 其中为正数
4． 证明如下序列不可能是某个简单图的次的序列: （l ）7，6，5，4，3，2; （2）6，6，5，4，3，2，l ; （3）6，5，5，4，3，2，l 。 【答案】（1）由定理知，能是图的次序列。
（2）此序列中，奇点为5，3，1，个数是奇数，所以此序列不可能为图的次的序列。 （3）对于七个顶点的图，若依次假定d （v 1）=6，d （v 2）=5，…，d （v 7）=l。
； v 2与v 1之间存在边e 12:，而①假定G 中无重复边，则v 1与其他六个顶点皆有连线（包括与v 7）
v 7的次为1，所以必不与v 1外的其他点相连。因而，v 2与除v 1，v 7外的四点之间各有一条连线。 至此，v l 、v 2与v 3、v 4、v 5和v 6中任意一个就组成了环，则G 不是简单图。
②假定G 中无环，则根据情形①的分析，v 1的关联边中必存在重复边。从而G 不是简单图。由上可知，该图中必有环或多重边，不可能是简单图的次的序列。
5． 下表给出了12种工件在设备A 和B 上的加工时间，试求:
（l ）若所有工件都先在设备A 上加工，再在设备B 上加工，试确定使总加工时间最短的工件加工顺序，并计算总加工时间;
（2）若工件8~12先在设备B 上加工，再在设备A 上加工，其他条件同上，试设计一启发式算法，以计算最小总加工时间和安排相应的工件最优加工顺序。
表
为偶数，而在此序列中，
为奇数，所以此序列不可
【答案】（l ）采用启发式算法进行计算，计算过程如下表所示。