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

一、简答题

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

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

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

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

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

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大

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

:， 最终求到z*。

二、计算题

3． 有一运输问题，它有3个重载点和2个车场，其运输表如表所示。表中小方框内的数字为两1、2和3三项运输业务的重载里程点 间的车辆空驶距离，（己将装卸车时间折算在内）分别为7，8和9，其他有关情况如表中所示。此外，要求车辆的每条行车路线总长度（包括重驶、空驶及装卸车所用时间的折算长度）L 在45~ 60之间。试用本章给出的车辆优化调度启发式算法，求出其满意的可接受可行解，并据此排出行车路线。

表

【答案】（l ）首先只考虑重载点的情况，利用伏格尔法进行求解，并且用位势法进行检验，

得到只考虑重载点的最优解为

（2）解的扩展

按照由小到大顺序对

进行调整

（3）解的收缩 因为

所以，不需要进行解的收缩过程。从而得到可行解X （），其非零分量为:

l

,

（4）安排行车路线

以可行解X （）为依据可安排行车线路，并且考虑到行车路线总长度，安排线路如下。 ①通车数目为4，路线为4→1→3→1→5，线路总长为 6+10+12+10+（7×2+9）=60 ∈［45, 60］

②通车数目为3，路线为5→2→1→1→3→5，线路总长为 2+2+4+10+2+（7×2+8+9）=20+31=51 ∈［45, 60］ ③通车数目为3，路线为5→1→2→1→4，线路总长为 14+12+2+8+（7x2+8）=58 ∈［45, 60］

4． 用运输问题的表上作业法求解线性规划问题:

l

【答案】由题意，得到运价表为:

由此可得，该问题是个运输平衡问题。 第一步，用沃格尔法得到初始方案为

第二步，用位势法得到初始方案中非基变量的检验数为

即x ll =10，从上述计算可得，所有非基变量的检验数均大于0，所以该初始方案就是最优方案。

x 13=20，x 22=15，x 23=5

5． 利用Kuhn 一Tucker 条件求解以下问题: