2017年陕西科技大学943运筹学复试仿真模拟三套题

2017年陕西科技大学943运筹学复试仿真模拟三套题（一） ............................................... 2

2017年陕西科技大学943运筹学复试仿真模拟三套题（二） ............................................. 11

2017年陕西科技大学943运筹学复试仿真模拟三套题（三） ............................................. 21

第 1 页，共 31 页

2017年陕西科技大学943运筹学复试仿真模拟三套题（一）

说明：本资料为2017复试学员内部使用，严格按照2017复试常考题型及难度全真模拟预测。 ————————————————————————————————————————

一、简答题

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

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

，使切割后最终得到这样的可行域，它的一个有整数坐标的极点的割平面（不见得一次就找到）

恰好是问题的最优解。

2．用表上作业法解运输问题时，在什么情况下会出现退化解?当出现退化解时如何处理?

【答案】当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。

当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-l）个。

二、计算题

3．给一个连通的赋权图G，类似于求G的最小支撑树的Kruskal方法，给出一个求G的最大支撑树的方法。

【答案】类似于避圈法。

第一步选一条最大权边，之后每步均从未被选取的边中选最大权边，加入到树的边的集合中，并要求不能与已选取的边构成圈（若在某步中存在两条及以上的边都是最大权边，则从中任选一条）。

4．某产品有12道加工工序，它们之间的顺序关系如下:工序A、B、C是同时开始的工序;工序A、B的紧后工序是D;工序B的紧后工序是E、F、H;工序F、C的紧后工序是G;工序E、H的紧后工序是I、J;工序C、D、F、J的紧后工序是K;工序K的紧后工序是L;产品在工序I、G、L完成后完工。画出该问题的网络计划图。

【答案】该问题的网络计划图如图所示。

第 2 页，共 31 页

图

5．开发公司拟为一企业承包新产品的研制与开发任务，但为得到合同必须参加投标。已知投标的准备费用为4万元，能得到合同的可能性是40%。如果得不到合同，准备费用得不到补偿。如果得到合同，可采用两种方法进行研制开发:方法1成功的可能性为80%，费用为26万元;方法2成功的可能性为50%，费用为16万元。如果研制开发成功，按合同开发公司可得到60万元，如果得到合同但未研制开发成功，则开发公司许赔偿 10万元。问题是:

（1）是否参加投标?

（2）若中标了，采用哪种方法研制开发?

【答案】D点处的值为:

E点处的值为:

由于

B点处的值为:

又因

总期望收益为40000元。

,故在A点处的决策为选择投标。 ,故在C点处的决策为方法l 计算结果表明该开发公司首先应该参加投标，在中标的条件下应采用方法1进行开发研制，

图

6．某规划线性规划问题:

（1）写出其对偶问题;