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

一、简答题

1． 试写出求解最短径路的Dijkstra 算法的步骤。

【答案】Dijkstra 算法的步骤为:

（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。

（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]

（3）比较所有具有T 标号的点，把最小者改为P 标号，即:

当存在两个以

上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

2． 简述求解整数规划分枝定界法的基本思想。

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界

; 。分支定界法就是将B 的可行域分成

子区域（称为分支）的方法，逐步减小和增大:， 最终求到z*。

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

【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因

，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:

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

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

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;

第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

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

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

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。

二、计算题

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

为阶梯函数）

，则

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

按E.O.Q 计算，得

分别计算每次订购707个和1500个电感平均每单位电感所需费用:

因为

，所以取

个，即该公司每次应采购1500个。

6． 某工厂的100台机器，拟分四个周期使用，在每一周期有两种生产任务。据经验，把x 1台机器投入第一种生产任务，则在一个生产周期中将有x 1/3台机器报废; 余下的机器全部投入第二种生产任务，则有1/10机器报废，如果于第一种生产任务每台机器可收益10，于第二种生产任务每台机器可收益7，问怎样分配机器，使总收入最大?

【答案】按周期将该问题划分为四个阶段，第k 阶段为第k 周期分配机器; 状态变量第k 周期初的完好机器数:决策变量

状态转移方程为:

;

阶段指标种任务的总收益，

益最大值。于是有递推关系：

其中k=3, 2, 1；f 5（s 5）=0。

表示表

表示第k 个周期用于第一种任务的机器台数，

示第k 周期用于第二种任务的机器台数;

表示第k 个周期台机器用于第一种任务，

台机器用于第二

最优值函数f k （s k ）表示第k 周期初完好机器台数为s k 时，从第k 周期至第4个周期的总收

，最优解为

，最优解为

，最优解为

因为s 1=100，所以最大总收益

反推出最优策略为:第1周期100台机器全部用于第二种生产任务; 第2周期90台机器全部用于第二种生 产任务; 第3周期81台机器全部用于第一种生产任务; 第4周期54台机器全部用于第一种生产任务。

7． 已知矩阵对策

的解为

对策的解，其赢得矩阵A 分别为

【答案】（l ）因为

所以可由定理7可知

，最优解为

，对策值为24/l3。求下列矩阵