精选整数规划试题

精选整数规划试题

一、选择题 （在下列各题中，从备选答案中选出1个或多个正确答案） 1. maxZ?3x1?2x2,2x1?3x2?14,x1?0.5x2?4.5,x1,x2?0且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是( )

A.(4，1) B.(4，3)C.(3，2) D.(2，4)

2. 下列说法正确的是 ( )

A.整数规划问题最优值优于其相应的线性规划问题的最优值

B.用分枝定界法求解一个极大化的'整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝

C.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解。

D.以上说法都不对

3. 分枝定界法中( )

A. 最大值问题的目标值是各分枝的下界

B. 最大值问题的目标值是各分枝的上界

C. 最小值问题的目标值是各分枝的上界

D. 以上结论都不对

二、填空题

1．求解纯整数规划的两种方法是（）

2. 已知基变量x1=3.25，x1要求取整数，则添加分枝约束（）和（ ）。

三、判断题

1. 整数规划的最优解是先求相应的线性规划的最优解然后取整得到；

2. 部分变量要求是整数的规划问题称为纯整数规划；

3. 求最大值问题的目标函数值是各分枝函数值的上界；

4. 求最小值问题的目标函数值是各分枝函数值的下界；

5. 变量取0或1的规划是整数规划；

6. 整数规划的可行解集合是离散型集合；