3.1.5 解决整数规划问题
在实际应用的过程中，按照图解法求解线性规划问题的最优解决方案时，有时求得的结果中包含小数，条件要求则是整数。对于这些要求最优解必须是整数的线性规划问题，运筹学上称为整数规划问题。整数规划问题是比较特殊的线性规划问题。
对于整数规划问题的求解，如果按照图解法求得的最优解有小数，需要进行处理，才能求得最终符合整数条件的最优解决方案。可以按照分支定界的方法进行处理，分支就是将规划问题细分为两个小的规划问题，定界就是进一步压缩未知数的选择范围。
上面问题的最优解决方案：
x=34.4，y=0
由于x是小数，不符合整数条件，虽然我们不能确定x的具体值，但可以排除掉34<x<35这个范围，因为这个范围内都是小数。因此，可以得到x的选择范围是：
x≥35和x≤34
这就是压缩未知数选择范围的过程，也就是定界的过程。
根据上面确定的x的选择范围，将x≥35和x≤34当作两个条件分别加入原来的数学模型之中，得到两个小的规划问题的模型，也就是分支的过程。两个小问题如下：
问题（1）
目标：10x+5y，求最小值；
条件：5x+2y≥172；
0≤x≤34，y≥0；
x，y是整数。
问题（2）
目标：10x+5y，求最小值；
条件：5x+2y≥172；
x≥35，y≥0；
x，y是整数。
最后，分别求解这些问题，通过比较，即可得到符合整数条件的最优解决方案。
对问题（1），同样可以用图解法求解。可以发现，x的范围比原来小，也就是需要在图3-1中加入x≤34这一条件。其中问题（1）的最优方案的可选范围变为直线5x+2y=172和直线x=34的中间阴影部分，如图3-3所示。
图3-3 问题（1）中最优方案的可选范围
在图3-3中也可以用虚线将问题（1）的目标10x+5y表示出来，可以上下移动。通过移动虚线可以发现，将代表目标的虚线移动到图中直线5x+2y=172与x=34的交点，即A1点，这时整个目标值达到最小，A1点的坐标表示问题（1）的最优解决方案，如图3-4所示。
图3-4 问题（1）的线性规划
考虑到A1点是直线5x+2y=172和x=34的交点，将x=34代入5x+2y=172中，可以得到y=1，即A1点的坐标是（34，1），目标10x+5y的值是345。由于要求最优解决方案中的所有数必须是整数，满足所有条件。所以x=34，y=1问题（1）的最优解决方案，且目标值达到最小，是345。
也可以求得线性规划问题的最优解是x=4，y=12。此时的目标值能达到最大：17x+9y=176。并且x和y也满足必须都是整数的条件。
对于问题（2），同样可以按照图解法求得最优解决方案。问题（2）相较原来的问题需要考虑x≥35的条件，可以在图3-1中加入这一条件。其中直线表示x=35，该直线右边和x轴上方的阴影部分是问题（2）最优解决方案的选择范围，如图3-5所示。
图3-5 问题（2）中最优解决方案的选择范围
将目标10x+5y用虚线表示，加入图3-5中上下移动。这时可以发现，当移动到直线x=35和x轴的交点A2点时，目标达到最小值，A2点的坐标即为问题（2）的最优解决方案，并且方案在选择范围之内，如图3-6所示。
图3-6 问题（2）的线性规划
根据上面的分析可知，A2点是直线x=35与x轴的交点，得到y=0。因此，A2点的坐标是（35，0）。即x=35，y=0是问题（2）的最优解决方案，此时目标10x+5y的值达到最小，最小值为350。显然，此时的最优解符合整数y条件。
至此，已经分别求出问题（1）和问题（2）的最优解决方案，并且都满足整数条件。因此，可以在两种方案中选择一种作为最终方案。通过比较这两种方案目标值的大小可知，问题（1）的目标值是345，问题（2）的目标值是350，可知问题（1）是最优方案，即x=34，y=1。
因此，此次运输可安排34辆大卡车和1辆小卡车，能够使运输过程的耗油量达到最低，是345升。