整数线性规划的特点

2020年11月1日15:16:47整数线性规划的特点已关闭评论

整数线性规划的特点

整数规划不同于线性规划,这不仅因为它的决策变量只能取整数值,而且它的数模方程可以是非线性的。

1.可行解域为离散点集

整数线性规划的可行解域仅是凸集中的整数点集,相邻整数点之间的区域不是可行解域。

2.不能用舍入取整法

用图解法或单纯形法求解的线性规划问题中,有些最优解可能是分数或小数,为了满足整数解的要求,初看起来,似乎只要把已得到的带有分数或小数的最优解“舍入化整”就可以了,但这样通常是不行的。因为化整后的解很可能不是可行解;或虽是可行解,但也不一定是最优解。

3.目标函数值的优劣

整数最优解目标函数值劣于同问题(即舍去决策变量取整数这一约束后的松弛问题)非整数最优解目标函数值,即当目标要求为极大时,整数解目标函数值下降;当目标要求为极小时,整数解目标函数值增大。

设整数规划的可行解域为 ,同问题非整数规划的可行解域为 ,虽然有 D∈ ,可以很容易证明:对于建立在可行解域 、 上的同一目标函数的规划问题,若 ∈ ,则建立在 上的目标值优于建立在 上的目标值。

  • 版权声明:本篇文章(包括图片)来自网络,由程序自动采集,著作权(版权)归原作者所有,如有侵权联系我们删除,联系方式(QQ:452038415)。