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

一、计算题

1． 对于运输问题:minf=CX，AX=b; 写出其对偶问题，并利用运输问题的特殊形式以及原问题检验数与对偶问题最优解之间时关系，导出运输问题位势法计算非基变量检验数的公式。 【答案】对偶问题为:

线性规划问题变量xj 的检验数可表示为

由此可写出运输问题某变量x ij （对应于运输表中的（A i ，B j ）格）的检验数如下:

现设基变量的检验数等于零，故对这组基变量可写出方程组

2． 某厂每年需要某种元件5000个，每次订购费c 3=50元，保管费每件每年c 1=1元，不允许缺货，元件单价k 随采购数量的不同而变化，问公司每次应该订购多少? 总的采购成本是多少?

【答案】利用E.O.Q 公式计算

分别计算每次订购707个和1500个元件，平均单位元件所需费用:

因为

所以，最佳订购量为1500。

一年内总的采购成本为要的时间如表所示

表

3． 考虑一个平衡流水线的设计问题。一项工作可以分解分A 、…、K 项任务，完成每项工作需

彼此工序如图所示，需要在4个工作台上实现这11项任务。试问怎样在4个工作台上安排这些任务， 在满足工序要求的前提下，整个流水线的循环周期为最小

图

【答案】设流水线的一个周期时间为T ，C i 表示工作i 所需时间，另外

建立模型如下：

说明:模型不唯一，上述只是一个模型表述。

4． 出从1节点到U 节点的最短路径

图

【答案】Dijkstra 算法，即标号法求解

（l ）对节点l 进行P 标号，即P （1）=0，其余点进行T 标号，即T （j ）=+∞ 因为

而

（2）修改节点3、5的T 标号

因为

（3）修改节点6，8的标号

因为

（4）修改节点9的标号

因为

（5）修改节点7的标号

因为

（6）修改节点9、11的标号

因为

（7）修改节点12的标号

因为

故将点12进行P 标号，

故将节点2进行P 标号，

故将点5进行P 标号，

故将点6进行P 标号，

故将点4进行P 标号，

故将点8进行P 标号，

故将点9进行P 标号，