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

一、简答题

1． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。

【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。

（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。

（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不 使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，行流水作业，同时消耗人、机、材等资源也合理。

2． 简述求解整数规划分枝定界法的基本思想。

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大

; 。分支定界法就是将B 的可行域分成

:， 最终求到z*。

二、计算题

3． 已知某个运输问题的产销平衡表、最优运输方案及单位运价表分别如表和表所示。由 于道路维修的原因，从产地戊到销售地残的运输暂时封闭，因此需要对表中的运输方案进行调整。试用尽可能简便的方法重新找最优运输方案。

表

表

【答案】由于产地A 2到销售地B 2的运输暂时封闭，因此两地运价定为∞，利用伏格尔法计算各行列的差额见表

表

选择最大差额4（第2行），确定所在行最小元素2，即先选择A 2供给B l ，得表

表

划掉B 2所在行，对上表反复利用伏格尔法进行表上作业法，最终求得产销平衡表如表所示:

表

4． 证明如下序列不可能是某个简单图的次的序列:

（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 不是简单图。由上可知，该图中必有环或多重边，不可能是简单图的次的序列。

5． 某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间（单位:天）如表所示，试求最优的加工顺序和总加工天数。

表

【答案】加工天数矩阵为

根据最优排序规则，其最优加工顺序为J 4→J 1→J 3→J 2→J 5→J 6，总加工时间为44天。

6． 某公司兴建一座港口码头，只有一个装卸船只的位置。设船只到达的间隔时间和装卸时间都服从负指数 分布，预计船只的平均到达率为3只/天，船只到港后如不能及时装卸，停留一日公司将损失1500元。现需设 计该港口码头的装卸能力（即每日可以装卸的船只数），已知单位装卸能力每日平均生产费用为2000元，问装卸 能力为多大时，每天的总支出最少? 在此装卸能力之下，求:

（l ）装卸码头的利用率;

（2）船只到港后的平均等候时间;

（3）船只到港后总停留时间大于一天的概率。

【答案】设装卸能力为刀，公司的支出则令所以

解得

时，每天的总支出最少。