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

一、简答题

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

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

2． 试写出求解最短径路的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）。

二、计算题

3． 考虑采用分枝定界法求解的一个整数规划问题（目标函数为最大化问题），其中变量x 1，x 2取整数。该 问题的求解由子问题1开始，如图所示。

图

请回答，

（1）在当前状态下，如何对整数规划的最优解进行定界。

（2）如果进行分枝，应该在哪个问题（从子问题2和子问题3中选择）上附加约束? 附加的两个约束分别是什么?

【答案】（l ）设整数规划的最优目标值为Z*，则对其定界范围为:

（2）如果进行分支，从子问题2开始附加约束，附加的两个约束为:

4． 对于线性规划问题

其最优单纯形表见表

其中勒为剩余变量，x 5。为松弛变量，x 6、x 7为人工变量，试根据上表同答下述问题: （l ）写出问题的最优基B 及B ，

（2）写出三个右端常数项的对偶价格;

（3）在C l =0的情况下，分析使最优解不变的c 2/c3的变化范围;

【答案】（l ）根据最终单纯形表，可以推出原线性规划问题的标准型为:

-1

所以,

（2）由对偶理论值知，三个右端常数项的对偶价格分别为x 6，x 5，x 7的检验数的相反数，即M-4/5，0，M+4/5, 0。

（3）c l =0时，最优解不发生变化。要保持最优解不变，则应保证所有非基变量的检验数不发生变化。当c 2，c 3 均为正数时，

当c 3均为负数时，无解。

5． 用单纯形法求解以下目标规划问题的满意解。

（2）

（3）

+

【答案】 （1）在第三个约束条件中加入松弛变量x 3，该目标规划的标准型为:

建立初始单纯形表，在表中将检验数列按优先因子个数排成两行，并采用单纯形法进行进一步迭代，如表所示。

表