2017年青岛大学运筹学(同等学力加试)复试实战预测五套卷
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以
上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
二、计算题
3． 利用优超原则求解下列矩阵对策。
（1） （2）
【答案】（l ）由于第1列优超于第3列与第4列，故可划去第3、4列，得到新的赢得矩阵
在A l 中，第3行优超于第1行，第4行优超于第2行，故可划去第1、2行，得到新的赢得矩阵
在A 2中，第1列优超于第2列，故可划去第2列，得到新的赢得矩阵
。
在A 3中，第1行优超于第3列，故可划去第2行，得到新的赢得矩阵策的解为
，
。
，故原矩阵对
（2）由于第3行优超于第2行，第4行优超于第1行，故可划去第1、2行，得到新的赢得矩阵
在A l 中，由于第1列优超于第3列，第2列优超于第4、5列，故可划去第3、4、5列，得到新的赢得矩阵
在A 2中，由于第l 行优超于第3行，故可划去第3行，得到新的赢得矩阵
易知
没有鞍点，所以有
解得
又因为A 3是由A 的第3、4行和第1、2列组成的矩阵，所以，原矩阵对策的解为
4． 某整数规划模型如下:
其最优解为x=（18/7，19/7）。试用分枝定界法写出后续的两个分枝模型。 【答案】选择x l =18/7进行分支，问题B
l
则得问题B l ，B 2
T
问题B
2
5． 如表是某线规划问题计算过程中的一个单纯形表，目标函数为max z =5xl +3 x2，变量均≥0，约束条件为“≤”类型，x 3，x 4为松弛变量。
表
要求: （1）求出表中的a 、b 、e 、d 、e 、f 和g ; （2）完整写出该线性规划问题的数学模型; （3）写出此问题的对偶问题;
（4）表中的解是线性规划问题的最优解吗? 对偶问题的最优解是什么?
【答案】（l ）该过程中，x3，xl 为基变量，因此可得出:e=0，d=1，b=f=0；
a= -10/5= -2
×1= -5