怎樣求最優整數解

提問： 線性規劃應用題中經常有要求最優整數解的題目，有沒有什么通法來解決呢？

回答：讓我們先來看一道題.

某營養師要為某個兒童預訂午餐和晚餐．已知一個單位的午餐含12個單位的碳水化合物、6個單位的蛋白質和6個單位的維生素C，一個單位的晚餐含8個單位的碳水化合物、6個單位的蛋白質和10個單位的維生素C． 該兒童的午餐和晚餐至少應含有64個單位的碳水化合物、42個單位的蛋白質和54個單位的維生素C．

如果一個單位的午餐的費用是2.5元，一個單位的晚餐的費用是4元，那么要滿足上述營養要求，并且花費最少，應當為該兒童分別預訂多少個單位的午餐和晚餐？

設營養師為該兒童分別預訂x個單位的午餐和y個單位的晚餐，共花費z元，則目標函數z=2.5x+4y，且x，y應滿足不等式組12x+8y≥64，6x+6y≥42，6x+10y≥54，x∈N*，y∈N*，即3x+2y≥16，x+y≥7，3x+5y≥27，x∈N*，y∈N*.

不等式組表示的平面區域如圖1中的陰影部分所示. 圖中的直線為l1：3x+2y=16，l2：x+y=7，l3：3x+5y=27． 其中，l1與y軸的交點為D（0，8），l1與l2的交點為C（2，5），l2與l3的交點為B（4，3），l3與ｘ軸的交點為A（9，0）．把目標函數化為截距式，得ｌ：ｙ＝-ｘ+，令ｚ＝0，畫出基線ｌ0：ｙ＝-ｘ 的圖象．

∵ 0＞ｋｌ3＞ｋｌ0＞ｋｌ2＞ｋｌ1， ∴由圖1可知，當直線l自l0處沿著y軸正方向平移至點B（4，3）時，ｚ＝2.5ｘ+4ｙ有最小值，ｚｍｉｎ＝ｚB＝2.5×4+4×3＝22（元）．

很明顯，該題的解法與一般線性規劃問題的解法相同． 究其原因，是目標函數表示的直線l所經過的可行域內的最低點碰巧是整點（橫坐標和縱坐標均為整數的點）B（4，3），這自然就成為問題的最優整數解了！

那么，如果目標函數表示的直線經過可行域的最低點或最高點不為整點，該如何處理呢？

讓我們修改一下題目條件，將原題改為“該兒童的午餐和晚餐至少應含有64個單位的碳水化合物、42個單位的蛋白質和52個單位的維生素C”. 那么，原來的解法依舊可行嗎？……