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

關(guān)鍵詞：線性規(guī)劃；最優(yōu)解；整數(shù)解；數(shù)學(xué)

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

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

規(guī)格類型鋼板類型規(guī)格A規(guī)格B規(guī)格C

第一種鋼板211

第二種鋼板123

教材中作了如下解答

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

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

目標(biāo)函數(shù)為z=x+y，把它變形為y=-x+z，得到斜率為-1，在y軸上的截距為z的一簇平行直線，由圖可知，當(dāng)直線經(jīng)過可行域內(nèi)的點M時，截距最小。

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

由于185，395都不是整數(shù)，而此問題中的最優(yōu)解（x，y）中的x，y必須是整數(shù)，所以點185，395不是最優(yōu)解。經(jīng)過可行域內(nèi)的整點（橫坐標(biāo)和縱坐標(biāo)都是整數(shù)的點）且截距z最小的直線是x+y=12，經(jīng)過的整點是B（3，9）和C（4，8），它們是最優(yōu)解。zmin=12。

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

在這里，問題處理是籠統(tǒng)的，學(xué)生對于所取的這兩個最優(yōu)整數(shù)解是心存疑慮的，首先它們是怎么被找到的，其次最優(yōu)整數(shù)解是否找全，當(dāng)整數(shù)點位于可行域的邊界時是否可行，問題的發(fā)現(xiàn)源于筆者布置的一題課后作業(yè)題：

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

下面以此題為例就如何調(diào)整最優(yōu)整數(shù)解加以詳細(xì)說明。

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

把目標(biāo)函數(shù)z=5x+4y變形為y=-54x+z4，它表示斜率為-54的一簇平行直線，當(dāng)直線經(jīng)過可行域內(nèi)的點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，而此題需要得到整數(shù)解。筆者就此給出了3種較可操作的方法：

一、 打網(wǎng)格法

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

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

二、 調(diào)整優(yōu)值法

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

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

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

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

（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符合條件，于是停止調(diào)整，得zmax=15。

用調(diào)整優(yōu)值法求最優(yōu)整數(shù)解有時會計算量較大，但其結(jié)果是最精確的，學(xué)生也感覺這種方法最為可靠。

三、 代數(shù)列舉法

由不等式組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，所以所有的整數(shù)解可能是

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

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

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

參考文獻：

[1]劉繼寬.談新教材中簡單線性規(guī)劃的認(rèn)識[J].基教瞭望，2008.

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

[3]田繼安，王國立.線性規(guī)劃問題中的整點最優(yōu)解[J].商丘職業(yè)技術(shù)學(xué)院學(xué)報，2007，6（5）：20-22.

作者簡介：

朱玲娣，浙江省紹興市，紹興市技工學(xué)校。