当前位置：问答库＞考研试题

一、简答题

1． 简述割平面法的基本思想。

【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。

2． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。

（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

二、计算题

3． 已知世界六大城市:P e ，N ，P a ，L ，T ，M 。试在表所示交通网络的数据中确定最小树。

表

【答案】将表用图形的形式表示出来，如图所示。

图

（1）采用避圈法。从图中选取权数最小的边[L，P a ]; 从未选的边中，选取权最小的边[Pe ，T]:依次进行，并使得它们相互不构成圈，直到再也不能选取出边为止。经过五次选边，得到边集合 {[L，P a ]，[Pe ，T]，[M，N]，[L，N]，[Pe ，L]}构成了唯一的最小支撑树，如图所示，此最小支撑树的总权为119。

图

（2）采用破圈法。应用破圈法的原理，依次进行破圈，直到所有边构成的图中不含有圈为止。所得到的结 果与上述避圈法的相同。

4． 甲、乙、丙三个城市每年需要煤炭分别为:320、250、350万吨，由A 、B 两处煤矿负责供应。已知煤 炭的年供应量分别为:A —400万吨，B 一450万吨。由煤矿至各城市的单位运价（万元/万吨）见表1。由于需大于供，经研究平衡决定，甲城市供应量可减少0~30万吨，乙城市需求量应全满足，丙城市供应量不少于270 万吨。试求将供应量分配完又使总运费为最低的调运方案。

表

1

【答案】甲、乙、丙三个城市每年的煤炭总需求量为:320+250+350=920（万吨），A 、B 两处煤矿年煤炭总供应量 为850万吨。可见供少于需，故虚拟一个产地煤矿C ，其供应量为70万吨，由题意可构造如表2的运价表。 问题变为求解表2的最优调运方案。

表2

第一步:用伏格尔法求初始可行解，求得的初始解，如表3科所示。

表

3

第二步: 用位势法进行最优解的判断。在对应于表3的数字格处填入单位运价，并增加一行一列，在行中填入vj ，在列中填入

并依据。令u 1=0，按照表

4 求出所有的和vj ，计算所有空格处的检验数，计算结果如表4所示。

由表4可知，所有空格处的检验数均为非负。所以，表3中的运输方案即为此问题的最优调运方案， 最小运价为14650万元。

5． 某厂有一种新产品，其推销策略有S 1，S 2，S 3三种可供选择，但各方案所需的资金、时间都不同， 加上市场情况的差别，因而获利和亏损情况不同。而市场情况也有三种:Q l （需要量大），Q 2（需要量一般），Q 3（需要量低）。市场情况的概率并不知道，其益损矩阵见表，（1）用乐观法进行决策。（2）用悲观准则进行决策。

表 单位：万元