也談線性規劃中的整點問題

　　摘要：線性規劃在實際生活中有著廣泛的應用，新教材中增加了線性規劃的內容，體現了數學的實際應用，發展了學生的數學應用意識. 由于實際背景所限，所求的問題可能會在整數的前提條件下才有實際意義，本文為筆者在教學實踐和研究中歸納的解決這類問題的兩種行之有效的方法，供大家參閱.
　　關鍵詞：線性規劃；整點問題；格點微調；最值微調
　　
　　線性規劃是運籌學的一個重要分支，在實際生活中有著廣泛的應用. 新教材中增加了線性規劃的內容，充分體現了數學的實際應用，發展了學生的數學應用意識. 常見的類型有二類：第一類，給定一定數量的人力、物力資源，問怎樣安排運用這些資源，才能使完成的任務量最大；第二類，給定一項任務，問怎樣統籌安排，才能使完成這項任務的人力、物力資源最小. 由于實際背景所限，所求的問題會在整數的前提條件下才有實際意義，筆者在教學中經過多次的教學實踐和研究，找到了解決這類問題的方法，以下是筆者在教學實踐和研究中歸納的行之有效的方法，供大家參考參閱.
　　【問題】兩類藥片有效成份如下：
　　■
　　若要求至少提供12 mg阿司匹林，70 mg小蘇打，28 mg可待因，兩類藥片的最小總數是多少？怎樣搭配價格最低？
　　【解法一】 （格點微調法）
　　經分析，假設A，B類藥片分別使用x，y片.用藥的總數為P片，價格總數為Q元，則線性約束條件為2x+y≥12，5x+7y≥70，x+6y≥28，x，y∈N■*. 線性目標函數為P=x+y，Q=0.1x+0.2y.
　　我們可根據以上線性約束條件畫出如下的可行域：
　　對于線性目標函數P=x+y，我們的目標是求P的最小值，我們將線性目標函數作一變形得y=－x+P，此時的P代表的是斜截式直線方程y=kx+b中的參數b，即直線在縱軸上的截距，顯然要求P的最小值，只要求直線y=－x+P在縱軸上的截距的最小值即可.
　　為了作圖的方便，我們可以先令P=0，得到線性目標函數的初始狀態線P0，然后將初始狀態線P0逐步向可行域平行移動，直到得到線性目標函數線滿足題意為止，我們將此時的位置稱為理論理想位置.我們發現此時線性目標函數在點A■，■處取得理論最小值，但顯然此時的理論最小值并不符合題意（整點）的要求，故要將目標函數線繼續向可行域的右上方移動. 我們可以從圖形上發現，最靠近A■，■點的整點有B（1，10），C（2，9），D（3，8）等，而且我們發現線性目標函數在此三點處同時取得實際最小值11，從而我們就找到了三個最優解B（1，10），C（2，9），D（3，8）.
　　【解法二】 （最值微調法）
　　仿照解法一，我們可以根據線性約束條件畫出可行域，同時我們發現線性目標函數在點A■，■處取得理論最小值P=x+y=■+■=■，因題中要求x，y∈N*，故此時的理論最小值顯然沒有實際意義，故我們應該在此理論最小值的基礎之上通過微調找到實際最小值，顯然實際最小值應該比理論最小值要大一點，故可取比理論最小值稍大一點的最小整數作為可能的實際最小值，此處我們可取P=x+y=11，將其變形得y=11－x，重新回代入線性約束條件可得2x+（11－x）≥12，5x+7（11－x）≥70，x+6（11－x）≥28，x，（11－x）∈N*， ?圯x≥1，x≤■，x≤■，x，（11－x）∈N*， ?圯1≤x≤■，x∈N*. ，故x可取的值有三個：1，2，3.
　　即滿足題意的最優解為B（1，10），C（2，9），D（3，8）.
　　讀者可以仿照以上解法解答第二小問. 當然第二小問的目標函數應該變形為Q=0.1（x+2y）后在微調（真正起決定性作用的是因式x+2y）
　　在遇到線性規劃的整點問題時，我們通常的處理辦法就是上面的兩種. 對于解法一，因找整點畫網格線比較麻煩又不夠精確，所以我們只在格點較少、網格線易畫的前提條件下才會采用. 對于解法二，必須理解兩個最值：理論最值和實際最值，當所求的最值為最大值時，如果得到的理論最大值沒有實際意義，則應該適當調小理論最大值得到可能的實際最大值；同理當所求的最值為最小值時，如果得到的理論最小值沒有實際意義，則應該適當調大理論最小值得到可能的實際最小值. 在可能的實際最小（大）值的基礎之上還應將線性目標函數回代入線性約束條件驗證求解，如找不到最優解，則再次調大（小）可能實際最小（大）值后再回代，直到找到符合題意的實際最值為止.