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

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