高中數(shù)學(xué)解題方法系列：線性規(guī)劃中整點問題的4種方法

1、高中數(shù)學(xué)解題方法系列：線性規(guī)劃中整點問題的4 種方法線性規(guī)劃是運籌學(xué)的一個重要分支，在實際生活中有著廣泛的應(yīng)用。新教材中增加了線性規(guī)劃的內(nèi)容， 充分體現(xiàn)了數(shù)學(xué)的實際應(yīng)用，發(fā)展了學(xué)生的數(shù)學(xué)應(yīng)用意識。由于實際問題中線性規(guī)劃問題的最優(yōu)解多為整數(shù)解，也是學(xué)生學(xué)習(xí)線性規(guī)劃的難點，因而求線性規(guī)劃的整數(shù)最優(yōu)解的方法就顯得尤為重要了。但教材中對此類問題卻一帶而過，對于具體的驗算過程并沒有作必要的描述，以致學(xué)生在解題過程中對于具體的驗算過程掌握還不夠清晰。例：要將兩種大小不同的的鋼板截成a、b、c 三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如表所示，今需要a、b、c 三種規(guī)格的成品分別為15，18，27

2、 塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。解：設(shè)需要截第一種鋼板x 張，第二張鋼板y 張，則21521832700 xyxyxyxy，作出可行域（如圖所示）, 目標(biāo)函數(shù)為zxy，作出在一組平行直線xyt中（t為參數(shù)）經(jīng)過可行域內(nèi)的點且和原點距離最近的直線，此直線經(jīng)過直線327xy和直線215xy的交點18 39(,)55a，直線方程為5721155xy，由于183955和都不是整數(shù)，而最優(yōu)解( , )x y中，x，y必須都是整數(shù)，所以可行域內(nèi)點18 39(,)55a不是最優(yōu)解。經(jīng)過可行域內(nèi)的整點（橫坐標(biāo)和縱坐標(biāo)都是整數(shù)的點）且與原點距離最近的直線是12xy且經(jīng)過的

3、整點是b（3，9）和 c（4，8） ，它們都是最優(yōu)解。答：要截得所需三種規(guī)格的鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種，第一種截法是截第一種鋼板3 張、第二種鋼板9 張；第二種截法是截第一種鋼板4 張、第二種鋼板8 張。兩種方法都最少要截兩種鋼板共12 張。線性規(guī)劃問題中的整點最優(yōu)解是教學(xué)中的一個難點，教材中利用圖解法比較直觀有效地突破了這一難點，但其中有兩個問題需要弄清楚：直線12xy是怎樣確定的？整點b（ 3，9）和 c（4，8）又是怎樣確定的？在求最優(yōu)解時，我們是將平行直線: lxyt向可行域內(nèi)平移，在向右上方平移時，t的值是增加的，而經(jīng)過18 39(,)55a點的直線為572115

4、5xy，當(dāng)t值增加的過程中，其最小值是12，所以與原點距離最近的直線可能是12xy。若在可行域內(nèi)直線12xy上有整點則均是最優(yōu)解。而直線12xy與邊界直線215xy及327xy的交點坐標(biāo)為（3，9） 、 （4.5 ，7.5 ） ，因此直線12xy在可行域內(nèi)的整點只有b（3，9）和 c （ 4，8） ，即為所求問題的最優(yōu)解。如果問題更復(fù)雜一點該怎么辦？下面以課本第71 頁習(xí)題 7.4 第 4 題為例介紹最優(yōu)整數(shù)鋼板類型規(guī)格類型a規(guī)格b規(guī)格c規(guī)格第一種鋼板2 1 1 第二種鋼板1 2 3 c(4,8) b(3,9) x+y=11 x+y=12 x+y=4 18 39(,)55ax+2y=18 2x

5、+y=15 15 x+3y=27 9 27 o 解問題的求解方法。某人有樓房一幢，室內(nèi)面積共1802m，擬分隔成兩類房間作為旅游客房，大房間每間面積為 182m，可住游客5 名，每名游客每天住宿費為40 元，小房間每間面積為152m，可住游客 3 名，每名游客每天住宿費為50 元，裝修大房間每間需要1000 元，裝修小房間每間需要 600 元，如果他們只能籌8000 元用于裝修，且游客能住滿客房，它應(yīng)隔出大房間和小房間各多少間，能獲最大利益？方法一：網(wǎng)格法：設(shè)應(yīng)隔出大房間x間和小房間y間(,x yn) ，則18151801000600800000 xyxyxy即：6560534000 xyxy

6、xy，目標(biāo)函數(shù)為540350zxy，作出可行域如圖：根 據(jù) 目 標(biāo) 函 數(shù)200150zxy， 作 出 一 組 平 行 線200150 xyt。當(dāng)此線經(jīng)過直線1815180 xy和直線10006008000 xy的 交 點20 60(,)77a， 此 直 線 方 程 為130002001507xy，由于20 60(,)77不是整數(shù)，所以經(jīng)過整點（ 3，8）時，才是最優(yōu)解，同時直線上的整點(0,12) 也是最優(yōu)解，即應(yīng)隔大房間3 間，小房間 8 間，或者隔大房間0 間，小房間 12 間，所獲利益最大。 如果考慮到不同客人的需要，應(yīng)隔大房間3 間，小房間8 間。對圖形的精度要求不高的可以用網(wǎng)格法，

7、實際應(yīng)用中常利用坐標(biāo)紙作圖；先作出可行域內(nèi)的網(wǎng)格，再平移目標(biāo)直線確定最優(yōu)解。方法二：整點驗證法：找出可行域內(nèi)靠近非整點最優(yōu)解一側(cè)邊界附近所有的整點:（ 0，12） 、 （1，10） 、 （2， 9） 、 （3，8） 、 （4，6） 、 （5，5） 、 （6， 3） 、 （7，1） 、 （8，0） ，分別代入目標(biāo)函數(shù)為540350zxy得整點（ 3， 8）和（ 0，12）是最優(yōu)解。當(dāng)可行域較小、 邊界附近的整點較少時可以用整點驗證法；先找出可行域內(nèi)非整最優(yōu)解一側(cè)邊界附近所有的整點，再將每個整點代入目標(biāo)函數(shù)確定最優(yōu)解。當(dāng)可行域較大、 邊界附近的整點較多時這種方法運算量較大。方法三 : 調(diào)整最值法：

8、目標(biāo)函數(shù)為：20015050(43 )zxyxy作出在一組平行直線：43xyt（50zt為參數(shù)）, 經(jīng)過20 60(,)77a的直線方程為2601433777xy，目標(biāo)直線43xyt在向可行域內(nèi)平移的過程中，t的值是減少的，在減少的過程中因x，y都是整數(shù)，因而t也為整數(shù)， 故最 大 整 數(shù)t可 能 是37 。 又 因 為 直 線4337xy與邊界直線5340 xy和直線6560 xy的交點分別為255(3,)(,9)32和，在此兩交點間直線4337xy上沒有整點，因此目標(biāo)直線不是4337xy。須再向可行域內(nèi)平移一個單位成為4336xy。目標(biāo)直線4336xy邊界直線5340 xy和直線6560

9、xy的交10 5 5 o x y 4x+3y=36 5x+3y=40 6x+5y=60 b(3,8) 5x+3y=40 6x+5y=60 4x+3y=36 c(0,12) 20 60(,)77ao 4034x+3y=1377點分別為20(4,)3及（ 0，12） ；又因為從目標(biāo)直線4336xy可得4123yx，可知若x，y為整數(shù)，則x為 3 的倍數(shù)； 在 0 ，4 中滿足條件只有0 與 3，故得最優(yōu)解 （0，12）及（3，8） 。當(dāng)目標(biāo)函數(shù) （或提取公倍數(shù)后）系數(shù)不大時可以用調(diào)整最值法，一般步驟為：平移直線尋找非整最優(yōu)解；調(diào)整最值，確定“目標(biāo)直線”由“目標(biāo)直線”方程代入約束條件，并求變量范圍：

10、確定“目標(biāo)直線”上整數(shù)解。但目標(biāo)直線在向可行域內(nèi)平移過程中，若需平移多次才能達到目的，將十分麻煩。方法四：縮小可行域法：作出一組平行直線：43xyt（50zt為參 數(shù) ） , 經(jīng) 過20 60(,)77a的 直 線 方 程 為2601433777xy，我們利用 b 附近的網(wǎng)格，可在可行域內(nèi)20 60(,)77a附近找到b（3，8）這幾個整點。過b作直線：4336xy，然后檢驗直線4336xy與邊界直線5340 xy和直線6560 xy圍成的陰影區(qū)域內(nèi)有無整點，經(jīng)檢驗無整點。故直線4336xy上的整點b（3，8） 、c（0，12）為最優(yōu)整點解。(若陰影區(qū)域內(nèi)的有整點可利用解法二確定最優(yōu)解) 縮小可行域方法的思路是先將題目作為一般的線性規(guī)劃最優(yōu)解來求,通過解出的非整數(shù)最優(yōu)解來排除部分可行域,從而達到縮小可行域的目的.可以克服在前方法三中有可能要多次平移找解的缺陷，適用范圍廣泛。 一般步驟為： 根據(jù)非整點最優(yōu)解a點的坐標(biāo)在其附近尋找最近的整點b；過 b作