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

一、简答题

1． 简述目标规划单纯形法求解的基本思想。

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;

第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;

第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。

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

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

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

二、计算题

3． 有4个工人，要指派他们分别完成4项工作，每个人做各项工作所消耗的时间如表所示。问指派哪个人去完成哪项工作，可使总的消耗时间为最小?

表

【答案】第一步:将系数矩阵进行变换为

第二步:进行试指派，得到

因为m=3

第三步：做最少的直线覆盖所有的0元素，并进行再指派

指派成功，此项工作有多种指派方案，minz=70，指派矩阵如下:

由解矩阵得最优指派方案为: （1） （2）

甲→A ，乙→D ，丙→C ，丁→B ; 甲→B ，乙→A ，丙→C ，丁→D 。

4． 某产品每月用量为4件，装配费为50元，存储费每月每件为8元，求产品每次最佳生产量及最小费用。若生产速度为每月可生产10件，求每次生产量及最小费用。

【答案】（l ）用“不允许缺货，生产时间很短”的模型求解。已知C 3=50，R=4，C 1=8。则

以月为单位的平均费用为

（2）用“不允许缺货，生产需一段时间”的模型求解。已知C 3=50，C 1=8，P=10，R=4，则最佳批量为

最小费用为

所以，如果生产时间足够短，那么最佳生产量为7件，最小费用为56.6元; 如果生产速度为每月可生产10件，那么最佳生产量为9件，最小费用为43.8元。

5． 求图中，从任意一点到另外任一点的最短路。

【答案】用Dijtstra 算法寻求最短路，计算结果如表所示。

表

从表可以得出任意一点到另外任一点的最短路。 （l ）从v 1开始到各点的最短路。