2017年西安工业大学工学运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧 这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;
第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。
二、计算题
3． 在某单人理发店顾客到达为泊松流，平均到达间隔为20 min，理发时间服从负指数分布，平均时间为 15 min。求:
（l ）顾客来理发不必等待的概率; （2）理发店内顾客平均数; （3）顾客在理发店内平均逗留时间;
（4）若顾客在店内平均逗留时间超过1.25h ，则店主将考虑增加设备及理发员，问平均到达率提高多少时，店主才做这样的考虑?
【答案】该系统为M/M/1模型，
第 2 页，共 28 页
4． 有A 、B 、C 、D 四种零件均可在设备甲或设备乙上加工。已知这两种设备上分别加工一个零件的费用 如表5一12所示。又知设备甲或设备乙只要有零件加工就需要设备的启动费用，分别为100元和巧0元。现要求 加工四种零件各3件，问应如何安排生产使总的费用最小? 请建立该问题的线性规划模型（不需求解）。加工一个 零件的费用（单位:元）
表
【答案】设i=1，2，3，4分别表示产品A 、B 、C 、D ; j=1，2表示设备甲、乙; x ij 表示产品i 在设备j 上生产的个数，
则得线性规划模型如下:
其中
5． 判断表1和表2中给出的调运方案能否作为用表上作业法求解时的初始解? 为什么?
表1 表
2
【答案】 表1中有5个基格，而要作为初始解，应有出的调运方案不能 作为表上作业法的初始解;
表 2中，有10个数基格，而理论上只应有
第 3 页，共 28 页
个基格，所以表给
个，多出了一个，所以表2给出的调
运方案不能作为表上作业法的初始解。
6． 某制造厂每周购进某种机械零件50件，订购费为40元，每周保管费为3.6元。试求:
（l ）E ，O ，Q ;
（2）该厂为少占用流动资金，希望存储量达到最低限度，决定宁可使总费用超过最低费用的4%作为存储 策略，问这时订购批量为多少?
【答案】已知R=50，C 3=40，C 1=3.6。 （l ）E ，O ，Q 公式，可求得
（2）由题意，有
该厂为了少占用流动资金，应取
件。
，解得Q=44件，Q=25件。所以
7． 证明如下序列不可能是某个简单图的次的序列:
（l ）7，6，5，4，3，2; （2）6，6，5，4，3，2，l ; （3）6，5，5，4，3，2，l 。 【答案】（1）由定理知
，不可能是图的次序列。
（2）此序列中，奇点为5，3，1，个数是奇数，所以此序列不可能为图的次的序列。 （3）对于七个顶点的图，若依次假定d （v 1）=6，d （v 2）=5，…，d （v 7）=l。
； v 2与v 1之间存在边e 12，①假定G 中无重复边，则v 1与其他六个顶点皆有连线（包括与v 7） 而v 7的次为1，所以必不与v 1外的其他点相连。因而，v 2与除v 1，v 7外的四点之间各有一条连线。
至此，v l 、v 2与v 3、v 4、v 5和v 6中任意一个就组成了环，则G 不是简单图。
②假定G 中无环，则根据情形①的分析，v 1的关联边中必存在重复边。从而G 不是简单图。由上可知，该图中必有环或多重边，不可能是简单图的次的序列。
为偶数，而在此序列中，
为奇数，所以此序列
第 4 页，共 28 页