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

一、简答题

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

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

满足下列条件:

（l ）在弧（2）在弧称是关于可行流f 的一条增广链。

即即中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。 是从v s 到v t ，的一条链，

若2． 试写出M/M/1排队系统的Little 公式。 【答案】M/M/1排队系统的Little 公式为

3． 简述目标规划单纯形法求解的基本思想。

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;

第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 4． 用表上作业法解运输问题时，在什么情况下会出现退化解? 当出现退化解时如何处理?

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

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

二、计算题

5． 表是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a l 、a 2、a 3、d 、c l 、c 2为 待定常数。试说明这些常数分别取何值时，以下结论成立。

（l ）表中解为惟一最优解;

（2）表中解为最优解，但存在无穷多最优解;

（3）该线性规划问题具有无界解;

（4）表中解非最优，为对解改进，换入变量为x 1，换出变量为x 6。

表

【答案】（l ）当

（2）当（3）当

（4）当且时，表中解为惟一最优解; 时，表中的解为最优解，且原问题有无穷多个最优解; 时，该线性规划问题具有无界解; 时，表中的解非最优，且满足对解进行改进，换入变量为x 1， 换出变量为x 6。

6． 试用0.618法重做习题7.4，并将计算结果与用斐波那契法所得计算结果进行比较。

=0.08，

由【答案】

由可确定试点的个数n=9，计算得最终区间

为

，近似极小点为t=3.05，近似最小值为-6.9975。与用斐波那契法进行比较，

用0.618法求解，试点数n 值大一些， 但求值更接近于精确值。

7． 某人在未来四年中需要一辆汽车代步，一辆新车的购买价格为36000元，每年的使用和维护费用如表所示。在每年末，他可选择继续使用现有汽车或再买新车，若再买新车，他可将现有旧车折价出售，出售价格如 表所示。

（l ）试建立求解此四年间最佳购车计划的图论模型;

（2）试用图论方法确定什么样的购车策略（每年末继续使用旧车还是购买新车）才能使总费用最少? 该费 用为多少?

表 购车数据（单位：元）

【答案】

（1）构建图论模型，如图所示。

图

（2）最优方案为第二年末换新车，这样费用最少，具体为31500x2=63000元。

8． 某公司采用无安全存量的存储策略，每年需电感5000个，每次订购费500元，保管费用每年每个10 元，不允许缺货。若采购少量电感每个单价18元，若一次采购1500个以上，则每个单价18元，问该公司每次应采购多少个? （提示:本题属于订购量多，价格有折扣的类型，即订购费为为阶梯函数）

，则

【答案】R=5000，C 3=500，C 1=10。设电感单价为K （Q ）

按E.O.Q 计算，得

分别计算每次订购

用:

因为，所以取个，即该公司每次应采购1500个。 707个和1500个电感平均每单位电感所需费

9． 在《运筹学》教材第331页的例9中，如售票处使用自动售票机，顾客在窗口前的服务时间将减少20%。这时认为服务时间分布的概率密度为

（这里的服务时间z 与例9中的（2）的y 关系很相似，即z=0.8y）再求顾客的逗留时间和等待时间。 【答案】

因为