如何選取線性規劃問題中的最優整數解

摘要：線性規劃是運籌學的一個重要組成部分，是輔助人們進行科學管理的一種數學方法，在實際生活中有著廣泛的應用。本文就線性規劃問題中的最優整數解給出了若干可操作的方法，使學生在學習中胸有成竹，有的放矢，從而激發學生興趣，激活學生思維，培養學生創新精神和實踐能力，達到應用和優化的目的。

關鍵詞：線性規劃；最優解；整數解；數學

所謂線性規劃問題是在線性約束條件下，求目標函數的最值問題，它是優化的數學模型之一，通過二元一次不等式刻畫平面區域直觀地解決實際生活中的數學問題。它融入了金融、教育投資、工廠生產、飲食營養等，體現數學源于生活，讓學生感受生活中的二元一次不等關系。通過平面區域的直觀聯系，讓學生去解決資源利用，人力調整，生產安排等方面的優化問題。然而既然是生活中的數學，那就必須考慮問題的可行性，如人員的分配中，人數必須是非負整數等等。

如：要將兩種大小不同的鋼板截成A、B、C三種規格，每張鋼板可同時截得三種規格的小鋼板的塊數如表所示。今需要A、B、C三種規格的成品分別為15、18、27塊，問各截這兩種鋼板多少張可得所需三種規格成品，且使所用鋼板張數最少？

規格類型鋼板類型規格A規格B規格C

第一種鋼板211

第二種鋼板123

教材中作了如下解答

解：設需截第一種鋼板x張，第二種鋼板y張，則線性約束條件為

2x+y≥15x+2y≥18x+3y≥27x≥0，x∈Ny≥0，y∈N可行域如圖

目標函數為z=x+y，把它變形為y=-x+z，得到斜率為-1，在y軸上的截距為z的一簇平行直線，由圖可知，當直線經過可行域內的點M時，截距最小。

解方程組x+3y=272x+y=15得M185，395

由于185，395都不是整數，而此問題中的最優解（x，y）中的x，y必須是整數，所以點185，395不是最優解。經過可行域內的整點（橫坐標和縱坐標都是整數的點）且截距z最小的直線是x+y=12，經過的整點是B（3，9）和C（4，8），它們是最優解。zmin=12。

答：要截得所需三種規格的鋼板，且使所截兩種鋼板的張數最少的方法有兩種，第一種截法是截第一種鋼板3張、第二種鋼板9張；第二種截法是截第一種鋼板4張、第二種鋼板8張。兩種方法都最少要截這兩種鋼板共12張。

在這里，問題處理是籠統的，學生對于所取的這兩個最優整數解是心存疑慮的，首先它們是怎么被找到的，其次最優整數解是否找全，當整數點位于可行域的邊界時是否可行，問題的發現源于筆者布置的一題課后作業題：

求z=5x+4y的最大值，使x，y滿足約束條件3x+4y<10x+4y≤11x≥0，x∈Ny≥0，y∈N

下面以此題為例就如何調整最優整數解加以詳細說明。

解：根據線性約束條件畫出可行域，

把目標函數z=5x+4y變形為y=-54x+z4，它表示斜率為-54的一簇平行直線，當直線經過可行域內的點M時，截距z4最大，即z最大，解方程組

3x+2y=10x+4y=11得M（1.8，2.3）

Zmax=5×1.8+4×2.3=18.2。

顯然1.8N，2.3N，而此題需要得到整數解。筆者就此給出了3種較可操作的方法：

一、 打網格法

利用坐標軸中的刻度畫出網格線，凡整數點都位于小方格的頂點上，那么對于可行域中的整數點，哪些是最優的整數點呢？我們可以先畫出經過原點的直線y=-54x，然后利用直角三角尺和直尺平移，由于任一條斜率為-54的直線上，y軸上截距都是固定的，所以我們要找截距最大的直線，又要獲得整數解，只要在與可行域有公共點的平移直線中，找與直線y=-54x+18.24最近的平移直線，它們之間的整數點，即為最優整數解。此題易得最優整數解為（3，0）。

用網格法求最優整數解的要求是作圖必須精確，這樣得到的結論才是準確的。由于學生都是手工作圖，所以要求學生在作圖過程中最好以厘米為單位打網格線，對于邊界的整點，可以借助計算進行檢驗是否在可行域內。若是平時作業可以借助厘米紙，刻度較為精確。此方法的特點是直觀。

二、 調整優值法

先求得理論最優值，然后根據需要，適當調整，也可以是多次調整，直到找到理想的最優結論，稱為調整優值法。上題中z=18.2是理論最優值，由于x∈N，y∈N，所以實際的情況只可能是比18.2小的整數，所以我們從18開始調整，即

（1）5x+4y=18則y=18-5x4代入3x+2y<10x+4y≤1174≤x<2，顯然在x∈N中無解，需繼續調整。

（2）5x+4y=17則y=17-5x4代入3x+2y<10x+4y≤1132≤x<3，x∈N，則x=2代入得y=74，顯然yN，需繼續調整。

（3）5x+4y=16則y=16-5x4代入3x+2y<10x+4y≤1154≤x<4，x∈N，則x=2或x=3，當x=2時代入得y=32，顯然yN，當x=3時代入得y=14，顯然yN，需繼續調整。

（4）5x+4y=15則y=15-5x4代入3x+2y<10x+4y≤111≤x<5，x∈N，則x=1或2或3或4，從而得到4組解。依次為x=1y=52，x=2y=54，x=3y=0，x=4y=-54，由于x∈N，y∈N，所以只有x=3y=0符合條件，于是停止調整，得zmax=15。

用調整優值法求最優整數解有時會計算量較大，但其結果是最精確的，學生也感覺這種方法最為可靠。

三、 代數列舉法

由不等式組3x+4y<10x+4y≤11x≥0，x∈Ny≥0，y∈N可以粗略地得0≤x≤3，0≤y≤2，所以x=0，1，2，3，y=0，1，2，所以所有的整數解可能是

從右下角的（3，2）開始，分別沿圖示的三個方向同時一一代入目標函數 進行檢驗，當把（3，2）代入目標函數時，得z=23，此時z的值超出理想最優值18.2，顯然不可能，那是由于不在可行域而引起的，（3，1）亦然，于是繼續沿圖示的三個方向代入目標函數，注意三個方向輪換進行檢驗，若z的值小于理想最優值18.2時，需檢驗是否滿足不等式組的條件，如（2，2）代入得z=18，但（2，2）不滿足不等式（1），通過這種方法，找到合適的條件停止，否則向里層繼續尋找。按照這種順序尋找可以減少計算量，易得最優整數解為（3，0），從而zmax=15。

用代數列舉法求最優整數解過程中，根據不等式，粗略地解出整數解范圍，會導致超出可行域，應在三個方向同時進行，然后把三個方向中使取得最大值的那個整數點x，y的值代入不等式檢驗，若滿足不等式，則找到最優解，否則繼續檢驗。若找目標函數取最小值的最優整數解，檢驗的方向需反之。

上述三種方法求最優整數解，各有其優勢，對于不同的題目及題目類型，學生可以根據自己的實際水平和熟練程度，合理選擇。

參考文獻：

[1]劉繼寬.談新教材中簡單線性規劃的認識[J].基教瞭望，2008.

[2]廖宇波.《線性規劃》課程教學的實踐與體會[J].華東交通大學學報，2007（12）.

[3]田繼安，王國立.線性規劃問題中的整點最優解[J].商丘職業技術學院學報，2007，6（5）：20-22.

作者簡介：

朱玲娣，浙江省紹興市，紹興市技工學校。