试题--整数规划

第3章 整数规划

一、选择题 （在下列各题中，从备选答案中选出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. 以上结论都不对

Z?3x1?x2,4x1?3x2?7,x1?2x2?4,x1,x2?0或1，最优解是( ) 4. max A.(0,0） B.(0,1） C.(1,0） D.(1,1)

二、填空题

4x1?x2?18，5x1?x2?30至少一个满足，用0－1变量表示的一般1．x1?2x2?5，线性约束条件是（ ）

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

3. 已知基变量x1=3.25，x1要求取整数，则添加分枝约束（ ）和（ ）。 三、判断题

1. 整数规划的最优解是先求相应的线性规划的最优解然后取整得到； 2. 部分变量要求是整数的规划问题称为纯整数规划； 3. 求最大值问题的目标函数值是各分枝函数值的上界； 4. 求最小值问题的目标函数值是各分枝函数值的下界； 5. 变量取0或1的规划是整数规划； 6. 整数规划的可行解集合是离散型集合；

7. 将指派问题的效率矩阵每行分别加上一个数后最优解不变； 8. 匈牙利法求解指派问题的条件是效率矩阵的元素非负； 9. 匈牙利法可直接求解极大化的指派问题；

参考答案： 一、选择题 1. A ， 2. D ， 3. B ， 4 . D

二、填空题 1.

2. （分枝定界法和割平面法） 3.（x1≤3），（x1≥4）

三、判断题 1.× 取整后不一定是原问题的最优解 2.× 称为混和整数规划 3.√ 4.√ 5.√ 6.√ 7.√ 8.√ 9.× 是求解极小化的指派问题