簡單線性規(guī)劃整點最優(yōu)解問題研究

1、簡單線性規(guī)劃整點最優(yōu)解問題研究黃建華摘要: 本文主要介紹簡單線性規(guī)劃整點最優(yōu)解的幾種搜索方法，它們都是在圖解平移法的基礎(chǔ)上運用交軌，換元，近值的方法來對整點進行搜索定位。關(guān)鍵詞：簡單線性規(guī)劃；整點最優(yōu)解；平移交軌法；平移換元法；平移近值法中圖分類號：o221The Research Into Simple Linear Programmings Optimal To Integral Point Huangjianhua (Class200001,mathematics departmeat of Huanggang Normal University Huangzhou,438000,HuB

2、ei,China) Abstruct: This topie mainly intrduces several methods about simple liner programmings optimal solution to integral point .They all based the graphic translating on the joint,tranform and approximate value method to search for and fix the integral point.Key words: Simple linear programming;

3、optimal solution to integral point;The method of graphic translating on the joint;transform and approximate value.隨著中學數(shù)學教育的改革和發(fā)展，簡單線性規(guī)劃問題已經(jīng)逐漸成為中學數(shù)學教學的一個基本內(nèi)容。簡單線性規(guī)劃問題與我們的日常生活息息相關(guān)，它主要涉及人力、物力、資金等資源的最優(yōu)配置。作為中學數(shù)學教學，整點最優(yōu)解問題是簡單線性規(guī)劃的核心內(nèi)容，但教材對于具體的驗算過程并沒有作過多的描述，以致中學生在解題過程中對于具體的驗算過程掌握還不夠清晰。在資料上也經(jīng)常見到有關(guān)簡單線性規(guī)劃整點最優(yōu)

4、解問題的求解方法，如：網(wǎng)格法，窮舉法，篩選法，最小距離法等。本文將介紹利用平移法求整點最優(yōu)解的幾種具體的操作方法平移交軌法，平移換元法，平移近值法。一 平移交軌法該方法主要是在平移直線過程中，利用直線間的交點來縮小最優(yōu)值的存在范圍，因此其主要思想是聯(lián)立方程求解交點，然后確定最優(yōu)解可能的存在范圍。例1 要將兩種大小不同的鋼板截成A、B、C三種規(guī)格,每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示： 規(guī)格類型鋼板類型A規(guī)格B規(guī)格C規(guī)格第一種鋼板211第二種鋼板123今需要A、B、C三種規(guī)格的成品分別為15、18、27塊,問各截這兩種鋼板多少張可得所需三種規(guī)格成品,且使所用鋼板張數(shù)最少? (新教材

5、63頁例4)分析：這類問題涉及物資的優(yōu)化配置,在任務(wù)一定的條件下,使物資用量最少。設(shè)需截第一種鋼板x張,第二種鋼板y張,設(shè)所用鋼板的張數(shù)為z張，則： Yy yy2x+y15 x+2y18 x+3y27x0,y0目標函數(shù)為：z=x+y可行域如圖所示(圖1) 根據(jù)目標函數(shù)作出一組平行直線:x+y=t。這些直線中經(jīng)過可行域且和原點距離最近的直線,此直線經(jīng)直線x+3y=27和2x+y=15的交點A(),此直線與原點的距離最近,z取得最小值,即：z=x+y=顯然和都不是整數(shù),而最優(yōu)解中,x和y必須為整數(shù),故A不是最優(yōu)解,故將直線x+y=向上平移到x+y=12,最優(yōu)解可能存在于此直線上。最優(yōu)解必須在可行域

6、內(nèi),故應求出直線2x+y=15和x+3y=27與x+y=12的交點： 2x+y=15 x+3y=27 x+y=12 x+y=12可得交點坐標為B(3,9),D()，故有：3x這樣便更進一步的縮小了x的范圍，即x=3或4，將其代入x+y=12 ，可得y=9或8。即（3，9）和（4，8）均為所求的最優(yōu)解。根據(jù)上述的分析解答過程，我們可以看到利用平移交軌法解題對于一般的簡單線性規(guī)劃問題都是適用的，其解題步驟如下：1 設(shè)出所求的未知數(shù)，列出約束條件,建立目標函數(shù)；2 作出可行域；3 確定平移直線,尋找非整最優(yōu)解；4 聯(lián)立方程求交點確定x或y的范圍；5 對x，y進行整點搜索，并確定整點解。二 平移換元法

7、該方法仍然是以平移法為基礎(chǔ)，主要是利用換元來減少線性約束條件的元數(shù)，以得出參數(shù)的范圍，從而確定出變量x，y的取值，再來確定最優(yōu)解的可能值。例2 某人有房子一幢，室內(nèi)面積共180m2，擬分隔成兩類房間作為游客住房。大房間每間面積為18m2，可住游客5名，每名游客每天住宿費為40元；小房間每間面積為15m2，可住游客3名，每名游客每天住宿費為50元；裝修大房間每間需1000元，裝修小房間每間需600元。如果他只能籌款8000元用于裝修，且游客能住滿客房，他應隔出大房間和小房間各多少間，能獲得最大收益？（新教材65頁習題4）分析：這類問題涉及物資的優(yōu)化運用，在物資一定的條件下，要求獲利最大。設(shè)他應隔

8、出大房間x間，小房間y間，能獲得收益為z元。18x+15y1801000x+600y8000x0，y0目標函數(shù)：z=200x+150y約束條件化簡：6x+5y605x+3y40x0，y0可行域如圖所示（圖2）根據(jù)目標函數(shù)作一組平行直線：4x+3y=t，這些直線中經(jīng)過B（）的直線與原點的距離最大。此時z=200x+150y取最大值 ，z=200×+150×=。但此時x，y均不為整數(shù)，故不是最優(yōu)解，因此又要進行調(diào)整。故因?qū)⒅本€4x+3y=37，向左下方平移，又z為整數(shù)，故應平移至4x+3y=37 （1）由（1）知y=，將其代入約束條件：6x+5×605x+3×

9、;40可得x3。又x為整數(shù)，則x=3，此時y為非整數(shù)，故在直線4x+3y=37時無最優(yōu)解，又向下方平移一個單位：4x+3y=36（2）由（2）知y=，將其代入約束條件：6x+5×605x+3×40可得0x4，x為整數(shù)則x=0，1，2，3或4，代入（2）求得它們對應的y=12，8，。故可得最優(yōu)解有（0，12）和（3，8），此時z=1800。平移換元法對一般的簡單線性規(guī)劃問題也都適用，根據(jù)上面的例題分析我們將其一般步驟歸納如下：1 設(shè)出所求的未知數(shù)，列出約束條件，建立目標函數(shù)；2 作出可行域；3 確定平移直線，尋找非整最優(yōu)解；4 由直線方程換元代入約束條件，并求變量范圍：5 對

10、x，y進行整點搜索，并確定整點解。三 平移近值法該方法也是以平移直線為基礎(chǔ)，但它并非一步一步的平移，而是在非整點最優(yōu)解附近搜索，同時結(jié)合網(wǎng)格（并非所有網(wǎng)格都打出），直接找出附近的整點來減小搜索范圍，從而求出整點最優(yōu)解。下面以例2求解介紹此法。分析：設(shè)他應隔出大房間x間，小房間y間，能獲得收益為z元。6x+5y605x+3y40x0，y0 目標函數(shù)：z=200x+150y可行域如圖所示（圖3）作直線：4x+3y=0，平移到B點時，z取得最大值，但B（）并非整點，故我們要進一步來搜索。由于B（），我們利用B附近的網(wǎng)格，可在B附近找到A（2，9）、C（2，8）、D（3，8）這幾個整點。此時還必須從中

11、選出一個最適合的點： z1=8+27=35 ; z2=8+24=32 ; z3=12+24=36故在直線平移過程中，必先過D點，因此A.C兩點被淘汰，故過D作直線：4x+3y=36此后，必需檢驗陰影區(qū)域內(nèi)有無整點，此時要利用陰影區(qū)的網(wǎng)格尋找整點。經(jīng)檢驗無整點。故直線4x+3y=36上必存在最優(yōu)整點解。利用網(wǎng)格知：（0，12），（3，8）為最優(yōu)整點解。平移近值法可以克服在前兩種方法中有可能要多次平移找解的缺陷，適用范圍廣泛。其一般步驟歸納如下：1 設(shè)出所求的未知數(shù)，列出約束條件，建立目標函數(shù)；2 作出可行域；3 尋找非整點最優(yōu)解A，根據(jù)A點的坐標在其附近尋找最近的整點B；4 過B作平移直線，通過直線確定較小的搜索范圍；5 利用部分網(wǎng)格在確定的范圍內(nèi)求最優(yōu)解。總之，以上三種基本方法都是以平移法為基礎(chǔ)，對于一般的簡單線性規(guī)劃問題都能夠求解。前兩種方法的相似點很多，首先它們的基點相同，適用范圍幾乎相同，但對于目標函數(shù)t=ax+by，若t，a，b經(jīng)約分后仍較大時，運用以上兩種方法均要調(diào)整多次才可能達到最優(yōu)。平移近值法彌補了前兩種方法的不足，直接在非整點最優(yōu)解附近的小范圍內(nèi)搜索，借用部分網(wǎng)格得出整點最優(yōu)解。三種方法各有各的特點，因此有時要根據(jù)具體情況選擇合理的方法。參考文獻1安培錄. 如何尋找線性規(guī)劃問題的整點最優(yōu)解. 數(shù)學通報，2000年第3期：18-21.2