整数线性规划的特点
整数规划不同于线性规划,这不仅因为它的决策变量只能取整数值,而且它的数模方程可以是非线性的。
1.可行解域为离散点集
整数线性规划的可行解域仅是凸集中的整数点集,相邻整数点之间的区域不是可行解域。
2.不能用舍入取整法
用图解法或单纯形法求解的线性规划问题中,有些最优解可能是分数或小数,为了满足整数解的要求,初看起来,似乎只要把已得到的带有分数或小数的最优解“舍入化整”就可以了,但这样通常是不行的。因为化整后的解很可能不是可行解;或虽是可行解,但也不一定是最优解。
3.目标函数值的优劣
整数最优解目标函数值劣于同问题(即舍去决策变量取整数这一约束后的松弛问题)非整数最优解目标函数值,即当目标要求为极大时,整数解目标函数值下降;当目标要求为极小时,整数解目标函数值增大。
设整数规划的可行解域为 D 1 ,同问题非整数规划的可行解域为 D 2 ,虽然有 D1 ∈ D 2 ,可以很容易证明:对于建立在可行解域 D 1 、 D 2 上的同一目标函数的规划问题,若 D 1 ∈ D 2 ,则建立在 D 2 上的目标值优于建立在 D 1 上的目标值。