用“调整估算验证法”求“线性规划最优整数解”的问题

整数最优解是线性规划应用问题中的一个难点，也是培养学生探索能力，加强数学实际应用的很好素材。由于求整数最优解比较复杂和困难，教材对如何求最优整数解只是原则性地点拨了一下，没有明确给出操作性强的具体方法，从而回避了如何求最优整数解这个问题。笔者在“简单的线性规划”的教学过程中，深感学生最难把握的就是如何求最优整数解。为了解决这类寻找最优整数解问题的难题，笔者采用“调整估算验证法”进行教学。其操作程序是：（1）根据可行域确定使Z取得最值的点A（x, y）；（2）若x, y都是整数，则点A即为所求的最优解，若x, y不都是整数，则将x, y的值代入目标函数中算出Z的理想值；（3）根据题意对Z的理想值进行微调并结合目标函数得出x, y的整数解，或者根据Z的理想值估算出x或y的整数取值范围，根据此范围结合目标函数进一步得到x,y的整数解；（4）将（3）中得到的整数解依次代入可行域中检验得到最优整数解。

下面以题目为例，说明“调整估算验证法”的运用。

例1 要将甲乙两种长短不同的钢管截成A,B,C三种规格的短钢管，一根甲钢管可同时截得A,B,C三种规格的钢管数量分别是2，1，4根，一根乙钢管可同时截得A,B,C三种规格的钢管数量分别是2，3，1根，今需要A,B,C三种规格的钢管各13，16，18根，问截甲乙这两种钢管各多少根可得所需的三种规格的钢管，且使用的甲乙钢管根数之和最小？

令Z＝10，得整数解为x＝0, y＝5；x＝2, y＝2.将这两组整数解依次代入可行域中检验得x＝2, y＝2.

所以最优整数解为x＝2, y＝2，即用甲种规格的原料2张，乙种规格的原料2张.

例3 某人有楼房一幢，室内面积共180m2，拟分隔成两类房间作为旅游客房. 大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元. 装修大房间每间需1000元，装修小房间每间需600元，如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，才能获得最大收益？

所以最优整数解为x＝0, y＝12或x＝3, y＝8，即应隔出大房间和小房间0间、12间或3间、8间.

注：以上3题中，Z的理想值都比较小或者不太大，所以对理想值进行微调可以较便捷地得到最优整数解，若Z的理想值比较大，则不宜采用此法.

例4 某实验室需购某种化工原料106克，现在市场上该原料有两种包装，一种是每袋35千克，价格为140元;另一种是每袋24千克，价格为120元，在满足需要的条件下，最少花费多少元？

所以最优整数解为x＝1，y ＝3，即购买35千克的原料1袋，24千克的原料3袋，此时花费最少为Z＝500元.

例5 某运输公司有7辆载重量为6 t的A型卡车与4辆载重量为10 t的B型卡车，有9名驾驶员. 在建筑某段高速公路中，此公司承包了每天至少搬运360 t沥青的任务，已知每辆卡车每天往返的次数为A型卡车8次，B型卡车6次，每辆卡车每天往返的成本费为A型车160元，B型车252元，每天派出A型车与B型车各多少辆公司所花的成本最低？

解：设每天派出A型车x辆，B型车y辆，则

48x＋60y≥360，x＋y≤9，x≤7，y≤4，x,y∈N.

目标函数Z＝160x＋252y.

所以最优整数解为x=5, y=2，即每天排派出A型车5辆，B型车2辆.

注：在例4、例5中，Z的理想值比较大，此时不宜对Z的理想值进行微调，应采取估算方法得出x 或y的整数取值范围，从而进一步得到x，y的最优整数解.

“调整估算验证法”的关键在于第（3）步，第（3）步中有两种方法，如果Z的理想值较小则对Z的理想值进行调整，如果Z的理想值较大则用Z的理想值除以x或y的系数（一般选择系数较大的那个）估算出x或y的整数取值范围，然后进一步得出x，y的整数解.

从上面的例子可以看到，用“调整估算验证法”解线性规划应用问题，目标明确，思路清晰，步骤简明，操作性强，计算量小，准确可靠，既不会增解也不会漏解，笔者在用此法进行“简单线性规划”教学时，收到了很好的效果，学生容易理解和接受，运用起来也很方便。事实上，这种调整估算验证法对培养学生的探索精神，进行思维训练，提高分析问题、解决问题的能力也很有好处。