铁球成本20，售价50，铝球成本10，售价30，球数≤12，售价≤450，怎样获利最大？

luyuanhong

luyuanhong

求线性规划问题的整数解，通常可以暂时不考虑正整数条件，按照普通线性规划

问题的解法，先求出最优实数解，然后在最优实数解的附近寻找最优的整数解。

那么，在实数解附近寻找整数解时，要取几个整数点呢？这没有一个固定的解答。

一般来说，可以先取最近的几个点，看最优解变化的趋势。如果看不出明显的趋势，

就逐步扩大搜寻的范围，再多取几个点；如果能看出最优解变化的趋势，能看出再

扩大搜寻的范围，得到的解只会越来越差，那就停止搜寻，不用再找更多的整数点了。

例如，在本题中，按照普通线性规划问题的解法，先求出最优实数解 (9/2,15/2) 。

然后在它的附近寻找最优整数解。

一开始，可以只取 4 个点：(3,9)，(4,8)，(5,6)，(6,5)，在这 4 个点处，目标函数

值为 270，280，270，280 ，还看不出明显的变化趋势。

所以，可以扩大搜寻范围，取 6 个点：(2,10)，(3,9)，(4,8)，(5,6)，(6,5)，(7,3)，

在这 6 个点处，目标函数值为 260，270，280，270，280 ，270 。这就可以看出变化

趋势来了，如果 x 取得比 2 更小，或取得比 7 更大，看趋势目标函数值只会变得更小，所以

可停止搜索，认为在 (4,8) 和 (6,5) 处的目标函数值 280 就是本题要求的整数解最大值。

当然，如果不放心，又不怕计算麻烦，还可以再扩大一点搜寻的范围，再多取几个点，这样

目标函数的变化趋势还可以看得更清楚，得出的最优整数解也就更保险了。