線性規(guī)劃中整點(diǎn)最優(yōu)解的求解策略

郭海鷹

【摘 要】隨著中學(xué)數(shù)學(xué)教育的改革和發(fā)展，簡(jiǎn)單線性規(guī)劃問(wèn)題已經(jīng)逐漸成為中學(xué)數(shù)學(xué)教學(xué)中的一個(gè)基本內(nèi)容。簡(jiǎn)單線性規(guī)劃問(wèn)題與我們的日常生活息息相關(guān)，它主要涉及人力、物力、資金等資源的最優(yōu)配置。在中學(xué)數(shù)學(xué)教學(xué)中，整點(diǎn)最優(yōu)解問(wèn)題是簡(jiǎn)單線性規(guī)劃的核心內(nèi)容，但教材對(duì)于具體的驗(yàn)算過(guò)程并沒(méi)有作過(guò)多的描述，以致中學(xué)生在解題過(guò)程中對(duì)于具體的驗(yàn)算過(guò)程掌握還不夠清晰。在資料上也經(jīng)常見(jiàn)到有關(guān)簡(jiǎn)單線性規(guī)劃整點(diǎn)最優(yōu)解問(wèn)題的求解方法，如：網(wǎng)格法，窮舉法，篩選法，最小距離法等。本文將介紹利用平移法求整點(diǎn)最優(yōu)解的兩種具體的操作方法—平移交軌法，平移近值法。

【關(guān)鍵詞】線性規(guī)劃；平移；整點(diǎn)最優(yōu)解

【中圖分類(lèi)號(hào)】G633.6 【文獻(xiàn)標(biāo)識(shí)碼】B 【文章編號(hào)】1671-8437（2018）10-0069-02

1 平移交軌法

該方法主要是在平移直線過(guò)程中，利用直線間的交點(diǎn)來(lái)縮小最優(yōu)值的存在范圍，因此其主要思想是聯(lián)立方程求解交點(diǎn)，然后確定最優(yōu)解可能的存在范圍。

例1 要將兩種大小不同的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：

根據(jù)目標(biāo)函數(shù)作出一組平行直線：x+y=t。這些直線中經(jīng)過(guò)可行域且和原點(diǎn)距離最近的直線，此直線經(jīng)直線x+3y=27和2x+y=15的交點(diǎn)A（ ），此直線與原點(diǎn)的距離最近，z取得最小值，即：

z= x+y=

顯然和都不是整數(shù)，而最優(yōu)解中，x和y必須為整數(shù)，故A不是最優(yōu)解，故將直線x+y= 向上平移到x+y=12，最優(yōu)解可能存在于此直線上。最優(yōu)解必須在可行域內(nèi)，故應(yīng)求出直線2x+y=15和x+3y=27與x+y=12的交點(diǎn)：

可得交點(diǎn)坐標(biāo)為B（3，9），D（，），故有：3≤x≤

這樣便更進(jìn)一步的縮小了x的范圍，即x=3或4，將其代入x+y=12，可得y=9或8。即（3，9）和（4，8）均為所求的最優(yōu)解。

根據(jù)上述的分析解答過(guò)程，我們可以看到利用平移交軌法解題對(duì)于一般的簡(jiǎn)單線性規(guī)劃問(wèn)題都是適用的，其解題步驟如下：

（1）設(shè)出所求的未知數(shù)，列出約束條件，建立目標(biāo)函數(shù)；

（2）作出可行域；

（3）確定平移直線，尋找非整最優(yōu)解；

（4）聯(lián)立方程求交點(diǎn)確定x或y的范圍；

（5）對(duì)x，y進(jìn)行整點(diǎn)搜索，并確定整點(diǎn)解。

2 平移近值法

該方法也是以平移直線為基礎(chǔ)，但它并非一步一步的平移，而是在非整點(diǎn)最優(yōu)解附近搜索，同時(shí)結(jié)合網(wǎng)格（并非所有網(wǎng)格都打出），直接找出附近的整點(diǎn)來(lái)減小搜索范圍，從而求出整點(diǎn)最優(yōu)解。

例2 某人有房子一幢，室內(nèi)面積共180m2，擬分隔成兩類(lèi)房間作為游客住房。大房間每間面積為18m2，可住游客5名，每名游客每天住宿費(fèi)為40元；小房間每間面積為15m2，可住游客3名，每名游客每天住宿費(fèi)為50元；裝修大房間每間需1000元，裝修小房間每間需600元。如果他只能籌款8000元用于裝修，且游客能住滿客房，他應(yīng)隔出大房間和小房間各多少間，能獲得最大收益？（新教材65頁(yè)習(xí)題4）

分析：設(shè)他應(yīng)隔出大房間x間，小房間y間，能獲得收益為z元。

作直線：4x+3y=0，平移到B點(diǎn)時(shí)，z取得最大值，但B（，）并非整點(diǎn)，故我們要進(jìn)一步來(lái)搜索。由于B（，），我們利用B附近的網(wǎng)格，可在B附近找到A（2，9）、C（2，8）、D（3，8）這幾個(gè)整點(diǎn)。此時(shí)還必須從中選出一個(gè)最適合的點(diǎn)：z1=8+27=35；z2=8+24=32；z3=12+24=36。

故在直線平移過(guò)程中，必先過(guò)D點(diǎn)，因此A.C兩點(diǎn)被淘汰，故過(guò)D作直線：4x+3y=36此后，必需檢驗(yàn)陰影區(qū)域內(nèi)有無(wú)整點(diǎn)。此時(shí)要利用陰影區(qū)的網(wǎng)格尋找整點(diǎn)，經(jīng)檢驗(yàn)無(wú)整點(diǎn)，故直線4x+3y=36上必存在最優(yōu)整點(diǎn)解。利用網(wǎng)格知：（0，12），（3，8）為最優(yōu)整點(diǎn)解。

平移近值法可以克服在前一種方法中有可能要多次平移找解的缺陷，適用范圍廣泛。其一般步驟歸納如下：

（1）設(shè)出所求的未知數(shù)，列出約束條件，建立目標(biāo)函數(shù)；

（2）作出可行域；

（3）尋找非整點(diǎn)最優(yōu)解A，根據(jù)A點(diǎn)的坐標(biāo)在其附近尋找最近的整點(diǎn)B；

（4）過(guò)B作平移直線，通過(guò)直線確定較小的搜索范圍；

（5）利用部分網(wǎng)格在確定的范圍內(nèi)求最優(yōu)解。

總之，以上兩種基本方法都是以平移法為基礎(chǔ)，對(duì)于一般的簡(jiǎn)單線性規(guī)劃問(wèn)題都能夠求解。但對(duì)于目標(biāo)函數(shù)t=ax+by，若t，a，b經(jīng)約分后仍較大時(shí)，運(yùn)用第一種方法要調(diào)整多次才可能達(dá)到最優(yōu)。平移近值法彌補(bǔ)了這種方法的不足，直接在非整點(diǎn)最優(yōu)解附近的小范圍內(nèi)搜索，借用部分網(wǎng)格得出整點(diǎn)最優(yōu)解。兩種方法各有各的特點(diǎn)，因此有時(shí)要根據(jù)具體情況選擇合理的方法。