教你如何做出最佳選擇——簡單線性規(guī)劃求最優(yōu)解.doc

教你如何做出最佳選擇簡單的線性規(guī)劃求最優(yōu)解在線性約束條件下，求線性目標函數(shù)最值問題，稱為“線性規(guī)劃”。目標函數(shù)取得最值時，變量的對應解稱為最優(yōu)解。若時，z 取得最值，稱為最優(yōu)整數(shù)解，簡稱整解。點的橫、縱坐標都是整數(shù)，稱為整點。求最優(yōu)整解問題出現(xiàn)在高中數(shù)學新教材中，常見的實際應用題型有兩種，（1）給出一定數(shù)量的人力、物力資源，問怎樣安排能使完成的任務量最大，收益最大；（2）給出一項任務，問怎樣統(tǒng)籌安排，能使完成這項任務投入的人力、物力最小。因為研究的對象是人、物等個體，故往往是整數(shù)，較不是整數(shù)時求解困難，所以這是一個應用數(shù)學知識解決實際問題的新難點，加之教材介紹較為籠統(tǒng)簡略，對教師和學生的理解掌握造成了一定的困難，針對這一問題，總結兩種尋找最優(yōu)整解的方法與大家探討。這兩種求解方法分別是：調(diào)整優(yōu)值法(簡稱調(diào)值法)、枚舉整點法(簡稱枚舉法)。調(diào)值法是先求非整點最優(yōu)解，再借助不定方程，調(diào)整最優(yōu)解，最后篩選出最優(yōu)解；枚舉法，因為取得最值的整點分布在可行域內(nèi)，可從中選取系數(shù)的絕對值較大的一個對其逐一取值，以此為標準分類討論，取得另一變量的最值，代入目標函數(shù)，比較函數(shù)值大小，找到最優(yōu)解。下面通過幾個典型例題，介紹一下這幾種方法的具體運用。 例1（調(diào)整優(yōu)值法）要將兩種大小不同的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示： 今需A、B、C三種規(guī)格的成品分別為15、18、27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少？ 解析：設需要第一種鋼板x張，第二種鋼板y張，鋼板總數(shù)z張，則 目標函數(shù) 作出可行域如圖所示，作出直線。作出一組平行直線（其中為參數(shù)）。 其中經(jīng)過可行域內(nèi)的點且和原點距離最近的直線，經(jīng)過直線 和直線 的交點，直線方程為。 由于和都不是整數(shù)，而最優(yōu)解中，必須都是整數(shù)，所以，可行域內(nèi)點不是最優(yōu)解。 經(jīng)過可行域內(nèi)的整點（橫坐標和縱坐標都是整數(shù)的點），且與原點距離最近的直線是。 經(jīng)過的整點是B（3，9）和C(4，8)，它們是最優(yōu)解。 故要截得所需三種規(guī)格的鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種，第一種截法是截第一種鋼板3張、第二種鋼板9張；第二種截法是截第一種鋼板4張、第二種鋼板8張。兩種方法都最少要截兩種鋼板共12張。點評：在解線性規(guī)劃問題時，常有一些實際問題需要變量取整數(shù)解時才有實際意義，而當可行域中的最優(yōu)解不是整數(shù)解時，需作出可行域的整點作出判斷。當直接觀察比較困難時，應對可能的情況進行檢驗。線性規(guī)劃整數(shù)解問題的一般處理方法是：若區(qū)域“頂點”處恰為整點，那么它的最優(yōu)解在“頂點”處取得（在包括邊界的情況下）；若區(qū)域的“頂點”不是整數(shù)點也不包括邊界時，可以先算出目標函數(shù)的值，在可行域內(nèi)適當放縮目標函數(shù)的值，使他為整數(shù)，且與最接近，在這條對應的直線，取可行域內(nèi)的整點。如果沒有整點，繼續(xù)放縮，直至取到整點為止。這種方法稱為調(diào)整優(yōu)值法。也可以通過畫出網(wǎng)格，平移直線，運用圖解法求得。例2(枚舉法) 某人有樓房一棟，室內(nèi)面積共180 ,擬分隔成兩類房間作為旅游客房，大房間每間面積為18 ，可住游客5名，每名游客每天住宿費為40元，小房間每間面積為15 ，可住旅客3名，每名游客每天住宿費為50元，裝修大房間每間需1000元，裝修小房間每間需600元，如果他只能籌款8000元用于裝修，且假設游客能住滿客房，它隔出大房間和小房間各多少間會獲得最大收益？最大收益是多少？解：設隔出大、小房間分別為間，間，收益為元， 則，其中滿足如圖所示，由圖解法易得，過點時，目標函數(shù)取得最大值。但必須是整數(shù)，還需在可行區(qū)域內(nèi)找出使目標函數(shù)取得最大值的整點。顯然目標函數(shù)取得最大值的整點一定是分布在可行區(qū)域的右上側，則利用枚舉法即可求出整點最優(yōu)值。這些整點有：(0, 12), (1, 10),(2, 9), (3, 8), (4, 6), (5, 5), (6, 3), (7,1 ), (8, 0)，分別代入。 逐一驗證，當取整點(0, 12)或(3, 8)時，獲得最大收益。所以獲得最大收益有兩種方案：I只隔出小房間12間。II隔出大房間3間，小房間8間，最大收益均為1800元。注：如果把裝修考慮在內(nèi)，則選擇第一方案好。 枚舉整點法的主要步驟是驗算-篩選，而優(yōu)值調(diào)整法更注重推理計算。它們的共同步驟是：1.建模(審題