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

一、简答题

1． 用表上作业法解运输问题时，在什么情况下会出现退化解? 当出现退化解时如何处理?

【答案】当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。

当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个 格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-l）个。

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

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧

这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。

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

二、计算题

3． 已知有m 个生产地点A i ，i=1，…，m ，可供应某种物资，其供应量为a i ，i=1，…，m ; 有n 个销售地B j ，j=l，…，n ，需要该种物资，其需要量为b j ，j=l，…，n ; 从各生产点往需求点发运时，均需经过P 个中间编组站之一转运，若启用第k 个编组站，不管转运量多少，均发生固定费用f k ，而第k 个编组站的转运容量为Q k （k=1，…，p ）。从A i 到P k 及P k 到B i 运输单位物资的运价分别为c ik 和c kj ，现要制定一个使总运费最小的调运方案。建立该问题的混合整数规划数学模型。

【答案】设

示编组站k 运往销售点j 的运量。则得模型

表示销售点i 运往编组站k 的运量，x kj 表

4． 某工程公司在未来L4月份内需完成三项工程:第一项工程的工期为1-3月份，总计需劳动力80人月; 第二项工程的工期为1-4月份，总计需劳动力100人月; 第三项工程的工期为3一4月份，总计需劳动力120人月。 该公司每月可用劳力为80人，但任一项工程上投入的劳动力任一月内不准超过印人。问该工程公司能否按期完 成上述三项工程任务，应如何安排劳力? （请将该问题归结为网络最大流问题求解）

【答案】可以构建图所示的网络图（弧上数字为最大流量）。

图

其中，结点1、2、3、4分别代表l 、2、3、4月份，结点5、6、7分别代表第一、二、三项工程。通过标号与调整，得到的最大流如图所示。

图

该最大流问题有多重最优解，上图仅给出一种。

所以该公司能按期完成上述三项工程任务，安排劳力的方案可以为:1月份，安排60人做第一

项任务、20 人做第二项任务; 2月份，安排60人做第二项任务; 3月份，安排60人做第三项任务、20人做第一项任务; 4 月份，安排60人做第四项任务、20人做第三项任务。

5． 某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，其所需劳动力、原材料等有关数据如下:每件产品Ⅰ分别需要劳动力和 原材料6个小时和3公斤，每件产品Ⅱ分别需要劳动力和原材料为3小时和4公斤，每件产品m 分别需要劳动力 和原材料为5小时和5公斤; 拥有的劳动力和原材料总数分别为45小时和30公斤; 又知Ⅰ、Ⅱ、Ⅲ三种产品的 单件利润分别为3、1、4元。

要求:（l ）写出该厂获得最大的生产计划问题的线性规划模型并求出最优解;

（2）写出该线性规划问题的对偶问题，并求对偶问题的最优解;

（3）产品I 的利润在什么范围内变化时，上述最优计划不变?

（4）如果设计一种新产品W ，单件产品消耗劳动力8小时，原材料2公斤，每件可获利3元，问该产品是否值得生产?

（5）如果劳动力数量不变，原材料可以从市场购买，每公斤0.4元，问该厂是否购买原材料来扩大生产，以购买多少为宜?

【答案】（l ）设三种产品的产量分别为x l ，x 2，x 3。则可建立如下线性规划模型:

将上述线性规划模型化为标准型，并用单纯形法计算如表所示。

表

于是得到最优解x*=（5，0，3，0，0），即分别生产I 、Ⅲ 5件和3件。

（2）上述线性规划问题的对偶问题为:

T