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

一、简答题

1． 简述求解最小费用最大流的赋权网络设置方法。

，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）

每条边用两条方向相反的有向边代替，各边的权

②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令

2． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。

【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:

可见，当Cr 变化成△Cr 后，最终表中的检验数是:

按如下规则:

二、计算题

3． 某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，其所需劳动力、原材料等有关数据如下:每件产品Ⅰ分别需要劳动力和 原材料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

-1由Y*=CB B ，及上述最终单纯形表可知，

（3）要保持最优计划不变，即保持各非基变量的检验数非正，则

解得:, 于是

了，在最终单纯形表中为

所以，产品I 的利润在［2.4，4.8］范围内变化时，上述最优计划不变。 （4）设新产品的产量为x 6，则约束矩阵多一个列向量

其检验数为, 故新产品值得生产。

（5）从最终单纯形表可知，原材料的影子价格为0.6，而其市场价格为0.4，故可以通过购买原材料来扩大生产。 设购买

所以 , 则 , 即购买15公斤时可获得最大效益。

4． 某百货公司去外地采购A 、B 、C 、D 四种规格的服装，数量分别为:A —1500套，B 一2000套，C 一3000 套，D 一3500套。有三个城市可供应上述规格的服装，供应数量为城市I 一2500套，城市II 2500套，城市III —5000套，由于这些城市的服装质量、运价及销售情况不一，预计售出后的利润（元/套）也不同，详见表1。 请帮助该公司确定一个预期盈利最大的采购方案。

表

1

【答案】 用10减去利润表上的数字，使之变成一个运输问题，如表2所示。

表

2

利用伏格尔法求出表37运输问题的初始解，求解结果见表3。

表3