舍入化整法与穷举整数法：优化方法

舍入化整法采用类似四舍五入的方法对整数规划问题求解。对于【例4-1】的模型,可以用舍入化整法求解,步骤如下:

视频-4．2．1整数规划问题求解-1-舍入化整法

①求出对应松弛问题的最优解。所谓松弛问题,是指整数规划问题有决策变量解除整数限制后的线性规划问题(某一整数规划对应的线性规划问题称为松弛问题,即不考虑决策变量整数限制的整数规划问题)。本例可使用图解法求解,结果如图4-1所示。

图4-1

对于本例,松弛问题的最优解为X∗＝(28/9,25/9)T,Z∗＝293/9。

②对松弛问题的最优解做四舍五入处理。显然,当x1＝3,x2＝3时,不满足约束条件“5x1＋7x2≤35”,因此不可行。(https://www.xing528.com)

③对变量依次取值。

对于“x1＝3,x2＝2,Z＝28”,满足约束条件,是可行解。

对于“x1＝4,x2＝1,Z＝29”,满足约束条件,是最优解。

虽然,从数学模型上看,整数规划是线性规划的一种特殊形式,求解只需在线性规划的基础上,通过舍入化整,寻求满足整数要求的解,但实际上两者却有很大的不同,通过舍入化整得到的整数解也不一定就是最优解,有时甚至不能保证所得到的解是整数可行解。因此,舍入化整法并不是对整数规划问题对应松弛问题的最优解进行四舍五入就可以获得的。

穷举整数法是指找出松弛问题所有的整数解并通过比较函数值获得最优解的方法。对于【例4-1】的模型,可以用穷举整数法求解,步骤①与舍入化整法相同,在此基础上列出所有整数可行解(包括可行域边界),然后比较函数值,在D点获得最优解,如图4-2所示。

图4-2