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

一、简答题

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

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

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

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

2． 简述对偶问题的“互补松弛性”。

【答案】互补松弛性:若当且仅当为

最优解。

分别是原问题和对偶问题的可行解。那么

，

即即

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

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

二、计算题

3． 用表上作业法求解下面运输问题的最优调运方案和最小总运费:

表

【答案】此问题属于运输平衡问题，则由沃格尔法得初始方案（0内数据），并检验（［］内数据）

表

存在空格检验数为负，调整其所在回路，调整量min （8，12）=8，得新的方案，并检验之

表

所有检验数均为正。故得到最优方案。

表

最小运费是3*10+9*14+8*16+4*32+16*34=956

4． 工厂每年需某种零件6400个，每次订购费为150元，存贮费为每年每个3元。

（l ）若工厂对此零件的需求是均匀的，且不允许缺货，问:每次订购多少个零件最佳? （2）若购买量在1一999个时，零件单价为3元; 购买量在1000一1900个时，零件单价为2.9元; 购买量在2000个或2000个以上时，零件单价为2.8元。问:在此情况下，如何采购最好?

【答案】由题意得

（1）

（2）

其中Q 1=1000 Q 2

=2000

∴最佳订货批量为1000件。

5． 求解运输问题:

表

【答案】首先判断发量和收量相等; 第一步，用伏格尔法寻找得到初始基可行解

表

第二步，用位势法计算各空格处的检验数为:

表

可见，所有非基变量的检验数均不为负数，故得到最优解