2017年苏州大学管理学和物流管理之运筹学复试实战预测五套卷
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐次求解k 个线性规划（k 为优先级的个数），即可求出目标规划的满意解。
二、计算题
3． 利用库恩一塔克条件求解以下问题:
（l ）试写出库恩一塔克条件。
（2）a 满足什么条件以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（l ）所求问题变形为
故库恩一塔克条件为
（2）由约束条件可知，（3）
时，存在最优解
时，时，解得
由且
目标函数值
目标函数值为
，故
其余情况均不符合 故当当
时，最优解为
时，最优解为
4． 用标号法计算图中v 1到解v 9的最短距离与最短路径，图中箭线数字为两点之间的距离。要求写出 计算过程。
图
【答案】（l ）首先给v l 以P 标号，P （v 1）=0，给其余所有点T 标号，
（2）
比较所有T 标号，T （v 2）最小，所以令（3）考察点V2
，并记录路径（V ，V ）
12
比较所有T 标号，T （v 5）最小，所以令P （v 5）=5，并记录路径（V 1，V 5） （4）考察点V
5
比较所有T 标号，T （v 7）最小，所以令P （V 7）=6，并记录路径（V 1，V 7） （5）考察点V
7
比较所有T 标号，T （v 8）最小，所以令P （V 8）=7，并记录路径（V 5，V 8） （6）考察点V
8
比较所有T 标号，T （v 6）最小，所以令P （V 6）=8，并记录路径（v 7，v 6） （7）考察点v
6
比较所有T 标号，T （v 3）最小，所以令P （v 3）=9，并记录路径（v 5，v 3） （8）考察点v
3
比较所有T 标号，T （v 4）最小，所以令p （v 4）=11，并记录路径（v 6，v 4） （9）考察点v
4
比较所有T 标号，T （v 9）最小，所以令p （v 9）=13，并记录路径（v 6，v 9） 全部计算结果如上过程，v 1到v 9的最短路为
，最短路长为13.
5． 在有互相排斥的约束条件的问题中，如果约束条件是（≤）型的，我们可用加以y i M 项（y i 是0-1变量， M 是很大的常数）的方法统一在一个问题中。如果约束条件是（≥）型的，我们将怎样利用y i 和M 呢?
【答案】在互相排斥的约束条件问题中，如果约束条件是（≥）型，我们可以分别在m 个约束条件右端减去y i M ， 其中y i 是0-1变量，M 是充分大的正数，且
。
相关内容
相关标签