如何選取線性規(guī)劃問題中的最優(yōu)整數(shù)解

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

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

所謂線性規(guī)劃問題是在線性約束條件下，求目標(biāo)函數(shù)的最值問題，它是優(yōu)化的數(shù)學(xué)模型之一，通過二元一次不等式刻畫平面區(qū)域直觀地解決實(shí)際生活中的數(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ī)格，每張鋼板可同時(shí)截得三種規(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)的點(diǎn)M時(shí)，截距最小。

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

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

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

在這里，問題處理是籠統(tǒng)的，學(xué)生對(duì)于所取的這兩個(gè)最優(yōu)整數(shù)解是心存疑慮的，首先它們是怎么被找到的，其次最優(yōu)整數(shù)解是否找全，當(dāng)整數(shù)點(diǎn)位于可行域的邊界時(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)的點(diǎn)M時(shí)，截距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ù)點(diǎn)都位于小方格的頂點(diǎn)上，那么對(duì)于可行域中的整數(shù)點(diǎn)，哪些是最優(yōu)的整數(shù)點(diǎn)呢？我們可以先畫出經(jīng)過原點(diǎn)的直線y=-54x，然后利用直角三角尺和直尺平移，由于任一條斜率為-54的直線上，y軸上截距都是固定的，所以我們要找截距最大的直線，又要獲得整數(shù)解，只要在與可行域有公共點(diǎn)的平移直線中，找與直線y=-54x+18.24最近的平移直線，它們之間的整數(shù)點(diǎn)，即為最優(yōu)整數(shù)解。此題易得最優(yōu)整數(shù)解為（3，0）。

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

二、 調(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，所以實(shí)際的情況只可能是比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時(shí)代入得y=32，顯然yN，當(dāng)x=3時(shí)代入得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ù)解有時(shí)會(huì)計(jì)算量較大，但其結(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）開始，分別沿圖示的三個(gè)方向同時(shí)一一代入目標(biāo)函數(shù) 進(jìn)行檢驗(yàn)，當(dāng)把（3，2）代入目標(biāo)函數(shù)時(shí)，得z=23，此時(shí)z的值超出理想最優(yōu)值18.2，顯然不可能，那是由于不在可行域而引起的，（3，1）亦然，于是繼續(xù)沿圖示的三個(gè)方向代入目標(biāo)函數(shù)，注意三個(gè)方向輪換進(jìn)行檢驗(yàn)，若z的值小于理想最優(yōu)值18.2時(shí)，需檢驗(yàn)是否滿足不等式組的條件，如（2，2）代入得z=18，但（2，2）不滿足不等式（1），通過這種方法，找到合適的條件停止，否則向里層繼續(xù)尋找。按照這種順序?qū)ふ铱梢詼p少計(jì)算量，易得最優(yōu)整數(shù)解為（3，0），從而zmax=15。

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

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

參考文獻(xiàn)：

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

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

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

作者簡介：

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