也談線性規(guī)劃中整點(diǎn)最優(yōu)解的一種處理方法*

甘肅省會(huì)寧縣第二中學(xué)(730799) 李平

也談線性規(guī)劃中整點(diǎn)最優(yōu)解的一種處理方法*

甘肅省會(huì)寧縣第二中學(xué)(730799) 李平

線性規(guī)劃是解決現(xiàn)實(shí)生產(chǎn)、生活中遇到的資源利用、人力調(diào)配、生產(chǎn)安排等問題的一種數(shù)學(xué)思想方法.高中人教A版數(shù)學(xué)書中,將其安排在必修5第三章.在對(duì)線性規(guī)劃的教學(xué)中,我發(fā)現(xiàn)學(xué)生對(duì)最優(yōu)解是整數(shù)點(diǎn)的這類問題的解答存在困難,教科書對(duì)這類問題的解答也比較模糊(主要是最優(yōu)解產(chǎn)生過程),通過查閱資料,筆者發(fā)現(xiàn)解決整點(diǎn)問題的方法也比較多,但這些方法有的簡單而適用范圍窄(如文獻(xiàn)[2]中的解法,要求目標(biāo)函數(shù)也取整數(shù)),有的適用范圍大但卻比較麻煩(如文獻(xiàn)[3]中的方法,網(wǎng)格法和篩選法),那么有沒有一種適用性廣,且簡單易于理解的方法呢?筆者通過仔細(xì)琢磨,發(fā)現(xiàn)了一種方法,下面通過兩個(gè)題目做一說明.

在介紹方法之前,我們先做一點(diǎn)準(zhǔn)備工作—清楚下面的結(jié)論.

結(jié)論:對(duì)于平面內(nèi)兩條平行直線l1,l2,設(shè)兩線間的距離為d,則:

①l1(l2)上的任意一點(diǎn),到l2(l1)的距離等于d;

②夾在兩平行線之間的點(diǎn),到兩平行線的距離都小于d;

③不夾在兩平行線之間也不在線上的點(diǎn),到離它較遠(yuǎn)的平行線的距離大于d.

圖1

用圖形(圖1)和代數(shù)式子表示如下:

在同一平面內(nèi),直線l1//l2,它們之間的距離為d,則:AD=d,BE＜d,BF＜d,CG＞d.

下面我們看如何求線性規(guī)劃中的整點(diǎn)問題:

題目1(高中數(shù)學(xué)人教A版必修5,第89頁例6)要將兩種大小不同的鋼板截成A,B,C三種規(guī)格,每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示:

A規(guī)格B規(guī)格C規(guī)格第一種鋼板2 1 1第二種鋼板1 2 3

今需要A,B,C三種規(guī)格的成品分別15,18,27塊,問各截這兩種鋼板多少張可得所需A,B,C三種規(guī)格成品,且使所用鋼板數(shù)最少?

解析設(shè)需截第一種鋼板x張,第二種鋼板y張,可得

且x,y都是整數(shù).

圖2

求目標(biāo)函數(shù)z=x+y取最小值時(shí)的x,y.將目標(biāo)函數(shù)變形為y=?x+z,則z表示直線y=?x+z在y軸上的截距.作出由不等式組確定的區(qū)域及直線y=?x,如圖2:平移直線y=?x,在平移過程中(由圖2)在不等式表示的區(qū)域內(nèi)碰到的第一個(gè)(或同時(shí)幾個(gè))整數(shù)點(diǎn),就是此題的最優(yōu)整點(diǎn),即最優(yōu)整點(diǎn)是所有可行解中到直線y=?x距離最小的.

如果不考慮x,y都是整數(shù)這一條件,則平移直線y=?x,當(dāng)其過點(diǎn)A時(shí),z的值最小,但A是方程組的解,其坐標(biāo)為不是整數(shù)點(diǎn).

在A點(diǎn)(非整點(diǎn)最優(yōu)解)附近(越近越好)找到一個(gè)整點(diǎn)B(在不等式組確定的區(qū)域內(nèi)):因?yàn)锳點(diǎn)橫坐標(biāo)滿足:我取B的橫坐標(biāo)為4(本題也可取3),將4代入?yún)^(qū)域邊界線方程得為了讓B是整點(diǎn)且在不等式組確定的區(qū)域內(nèi),取B的縱坐標(biāo)為8,這樣確定B(4,8).

圖3

平移直線y=?x,讓其過點(diǎn)B,這樣確定一條直線l:x+y?12=0,如圖3,直線x+y?12=0會(huì)和不等式表示的區(qū)域邊界交于D,C兩點(diǎn),現(xiàn)在我們能確定最優(yōu)解必定落在△ACD(包括邊界)表示的區(qū)域內(nèi)(由前面給的結(jié)論可知,在直線x+y?12=0右上方區(qū)域內(nèi)的所有點(diǎn)到y(tǒng)=?x的距離大于點(diǎn)B到直線y=?x距離,所以到直線y=?x距離最小的整點(diǎn)必在△ACD(包括邊界)表示的區(qū)域內(nèi)).

題目2某人有樓房一幢,室內(nèi)面積共180m2,擬分隔成兩類房間作為旅游客房.大房間每間面積為18m2,可住游客5名,每名游客每天住宿費(fèi)為40元;小房間每間面積15m2,可住游客3名,每名游客每天住宿費(fèi)為50元;裝修大房間每間需1000元,裝修小房間每間需600元.如果他只能籌款8000元用于裝修,且游客能住滿客房,他應(yīng)隔出大房間和小房間各多少間,能獲得最大收益?

圖4

圖5

故在不等式表示的區(qū)域內(nèi),到直線4x+3y=0距離最遠(yuǎn)的整數(shù)點(diǎn)有(0,12)和(3,8)兩個(gè),因此使z最大的最優(yōu)整數(shù)解是(0,12)或(3,8),代入z=200x+150y得,zmax=1800.

根據(jù)以上題目的解答可見,對(duì)于目標(biāo)函數(shù)是形如z=ax+by的整點(diǎn)線性規(guī)劃問題,我們可以通過下面幾步求得整點(diǎn)最優(yōu)解:

1.作出不等式組所約束的區(qū)域(能將不等式組化簡的先化簡再作圖),將目標(biāo)函數(shù)變形成

3.過B作直線的平行線,并求出其方程l,l會(huì)縮小最優(yōu)整點(diǎn)所在區(qū)域.

4.在已經(jīng)縮小的區(qū)域內(nèi)找出所有整點(diǎn),代入驗(yàn)證得最優(yōu)整數(shù)點(diǎn),即最優(yōu)解.

[1]劉紹學(xué).普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)(數(shù)學(xué)必修5)[M].人民教育出版社A版,2004.

[2]賈耕,張弢.線性規(guī)劃中最優(yōu)整解的一種尋找方法[J].數(shù)學(xué)通報(bào), 2005(12).

[3]徐國文.談線性規(guī)劃中“整點(diǎn)最優(yōu)解”處理方法[J].中學(xué)生數(shù)學(xué), 2003(01).

本文系“甘肅省‘十三五’教育科學(xué)規(guī)劃課題研究成果,網(wǎng)絡(luò)申報(bào)號(hào)：BY2017_26”.