2017年昆明理工大学J002运筹学(同等学力加试)复试仿真模拟三套题
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大
; 。分支定界法就是将B 的可行域分成
:， 最终求到z*。
二、计算题
3． 在开采油井时，出现不定情况，用后悔值准则决定是否开采。益损矩阵如表所示。
表
【答案】令方案开采和不开采分别为i=l，2; 状态有油和无油分别为j=l，2; 方案i 在状态j 的收益为E ij ，其中i=l，2; j=l，2，则
因为
所以，按后悔值准则的决策方案为开采。
4． 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。
（1）
（2）
（3）以（l ）为例，具体说明当目标函数中变量的系数怎样改变时，使满足约束条件的可行域的每 一个顶点，都有可能使目标函数值达到最优。
【答案】 （1）图解法
图
该线性规划问题的可行域如图所示。由图可知该线性规划的惟一最优解为对应于图上的点A 2，其最优目标函数值z*=33/4。
②单纯形法 引入松弛变量
用单纯形法逐步迭代，求解过程如表所示。
表
得该线性规划问题的标准型
故问题的最优解单纯形表第一步迭代得单纯形表第二步迭代得单纯形表第三步迭代得（2）①图解法
最优目标函数值z*=33/4。 对应于图中的的坐标原点; 对应于图中的点A 3（4，0）; 对应于图1-5中的点A2（15/4，3/4）。
图
该线性规划的可行域如图所示，由图知该线性规划的惟一最优解为，最优目标函数值为的点A 2（2，6）
②单纯形法
在上述问题的约束条件中引入松弛变量x 3，x 4，x 5，得到该规划问题的标准型
，对应于图上
利用单纯形表进行迭代计算如表所示。
表
相关内容
相关标签