2017年河南理工大学850运筹学(同等学力加试)考研复试核心题库
● 摘要
一、简答题
1． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。
2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大
; 。分支定界法就是将B 的可行域分成
:， 最终求到z*。
二、计算题
3． 给出如下线性规划问题的最优单纯型表如表所示，其中S 1、S 2分别为两个约束条件的松弛变量
表
要求:（l ）求出使最优基不变的b 2的变化范围; （2）求出使最优解不变的c 2的变化范围; （3）在原线性规划的约束条件上，增加约束条件:变化，试求出最优解。
【答案】（l ）假设b 2变化后的最优解为X B ，只要X B ≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化。
，其最优解是否变化? 如
设b 2变化了λ，则
所以
当b ≥0时问题最优基不变，解得λ≥0故b 2≥30 （2）由题意知c 2-4≥0得c 2≥4
（3）约束条件可变为x 1+2x2+2x3+s3=12
列出单纯形表
最优解（12/5, 0, 24/5）
4． 对于运输问题:minf=CX，AX=b; 写出其对偶问题，并利用运输问题的特殊形式以及原问题检验数与对偶问题最优解之间时关系，导出运输问题位势法计算非基变量检验数的公式。
【答案】对偶问题为:
线性规划问题变量xj 的检验数可表示为
由此可写出运输问题某变量x ij （对应于运输表中的（A i ，B j ）格）的检验数如下:
现设基变量的检验数等于零，故对这组基变量可写出方程组
5． 图中V s 表示仓库，V t 表示商店. 现要从仓库运10单位的物资到商店，应如何调运才能使运费最省（图 中弧表示交通线，弧旁的数字为（C ij ，b ij ），其中C ij ，表示交通线上运输能力限制，b ij 表示单位运价）。
图
【答案】（l ）从f （）={0}开始，做L （f （））如图1，用Dijkastra 算法求得L （f （
中最短路为的调整，结果见
，在网络中相应的可增广链
，如图2所示:
0）
）网络
上用最大流算法进行流
图
1
图2
（2）作
2
如图1，找出最短路为，在网络内相应的可增广链上进行调整，得
到流f （）， 如图2所示: