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

一、简答题

1． 什么是关于可行流f 的增广链?

【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若

满足下列条件: （l ）在弧（2）在弧称

是关于可行流f 的一条增广链。

即即

中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。

是从v s 到v t ，的一条链，

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

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

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

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

二、计算题

3． 某厂准备将具有下列成分的几种现成合金混合起来，成为一种含铅30%，含锌20%，含锡50%的新合金。有关数据见表。

表

应如何混合这些合金，使得既满足新合金的要求又花费最小? 试建立此问题的线性规划模型。【答案】设1kg 新合金需要A ，B ，C ，D ，E 这5种合金分别为x 1，x 2，x 3，x 4，x 5公斤，则线性规划模型为而

第 2 页，共 48 页

4． 某工程由六道工序构成，有关资料如表所示，其中时间单位为天，费用单位为元

（1）画出工程网络图

（2）求出工程完工期及关键工序

（3）现若要求工程在正常工期基础上再提前二天完成. 求使应急费用量少的应急压缩方案

表 某工程有关资料表

【答案】（1）

图

（2）各工序的时间参数:

表

工程兄工期为45，关键工序为A ，C ，E ，F （3）要使工期缩短，即缩短关键工序的工期

第 3 页，共 48 页

若缩短A 的工期，费用增加240; 若缩短E 的工期，费用减少860; 若缩短F 的工期，费用不变。

故要使费用最少，应选择缩短E 的工期。

5． 将下列线性规划问题变换成标准型，并列出初始单纯形表。

（1）

（2）

【答案】（1）

且

在第一个约束条件两边同时乘以-1后引入人

工变量x 5，在第二个约束条件右端加上松弛变量x 6; 在第三个约束条件右端减去剩余变量x 7，同时加入人工变量x 8，将目标函数最小化变换为最大化，得该线性规划的标准型

其中，M 为充分大的正数，对应的初始单纯形表如表所示。

表

（2）在上述约束条件两边同时乘以-1，然后分别引入人工变量x 1, x 2, …, x n ，得该线性规划的标准型

第 4 页，共 48 页