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

一、简答题

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

【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点， 每条边用两条方向相反的有向边代替，各边的权

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

2． 试写出标准指派问题的线性规划问题。

【答案】

A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:

按如下规则:

二、计算题

3． 下述论断正确与否:可行流f 的流量为零，即v （f ）=0，当且仅当f 是零流。

【答案】论断错误。

流量

，但f 不是零流。

4． 有一个运输问题有两个产地，三个销地，产地的产量，销地的需求量以及从各产地到各销地的单位运价等数据如表所示。

表

，只表明发点的净输出量为零，可能流出等于流入，

此时

若销地B 1、B 2、B 3允许缺货，产地A l 、A 2允许存储，且单位缺货费与单位存储赞均列于上表现要求:

（l ） 建立该问题的数学模型; （2）用表上作业法求解该问题。

【答案】（l ）设x ij 表示产地i 运往销地j 的运量，其中i=1，2表示A l ，A 2，j=1，2，3表示B l ，B 2，B 3则得数学模型如下:

（2）产>销，故添加一虚拟销地B 4，需求量是100，两产地运往B 4的运价分别为18。

5． 某出版单位有4500个空闲的印刷机时和4000个空闲的装订工时，拟用于下列4种图书的印刷和装订。已知各种书每册所需要的印刷和装订工时如下表所示:

设x j 表示第j 种书的出版数量（单位:千册），据此建立如下线性规划模型:

用单纯形法求解得最终的单纯形表如表所示:（x 5，x 6为松弛变量）

表

试回答以下问题:（假定各问题条件相互独立，也就是在其他条件与原问题相同时来回答本问题）

（l ）据市场调查第4种书最多能销5000册，当销量多于5000时，超量部分每册降价2元，据此假设求新的最优解

（2）经理对不出版第2种书提出意见，要求该种书必须出2000册，求此条件下的最优解; （3）作为替代方案，第2种书仍须出2000册，印刷由该厂承担，而装订工序交别的厂承担，但装订每册成 本比该厂高0.5元，求新最优解。

【答案】（l ）将5000册第4种书所需工时扣除，并将其利润降为1，重新求解得

（2）由题意在原模型的基础上，增加新的约束条件x :=2，单纯形法求解得

（3）增加了新的约束条件，则新的线性规划模型如下:

单纯形法求解得