用“小范圍搜索法”求“線性規(guī)劃問題”的最優(yōu)整數(shù)解)

1、用 “小范圍搜索法”求 “線性規(guī)劃問題”的最優(yōu)整數(shù)解筆者對(duì)教科書中的全部7 個(gè)線性規(guī)劃的實(shí)際應(yīng)用問題進(jìn)行了研究和分類。其中1 個(gè)問題（教科書第61 頁例 3）的最優(yōu)解不是整數(shù)解，最優(yōu)解有且只有一個(gè)，最優(yōu)解顯然在邊界折線的頂點(diǎn)處，此為第一類問題；有3 個(gè)問題（教科書第 64 頁練習(xí)第2 題、第 65 頁習(xí)題 7.4 第 3 題，第 66 頁研究課題與實(shí)習(xí)作業(yè)）的最優(yōu)解為整數(shù)解，最優(yōu)整數(shù)解有且只有一個(gè)，最優(yōu)解整點(diǎn)顯然在邊界折線的頂點(diǎn)處，此為第二類問題；另有3 個(gè)問題（教科書第63 頁例 4、第 65頁習(xí)題 7.4 第 4 題、第 87 頁復(fù)習(xí)參考題七 A 組第 16 題）的最優(yōu)解為整數(shù)解，最優(yōu)整數(shù)

2、解可能不止一個(gè)，最優(yōu)解整點(diǎn)不在邊界折線的頂點(diǎn)處，或雖在邊界折線的頂點(diǎn)處但并不顯然，此為第三類問題。第一、第二類問題的最優(yōu)解可以通過解一個(gè)二元一次方程組直接得到，學(xué)生比較容易掌握。第三類問題的最優(yōu)解不能通過解一個(gè)二元一次方程組直接得到，必須通過觀察圖形或計(jì)算檢驗(yàn)去尋找，學(xué)生不容易掌握，學(xué)習(xí)困難比較大。為了解決這類尋找最優(yōu)整數(shù)解的困難，筆者采用“小范圍搜索法”進(jìn)行教學(xué)。該方法的優(yōu)點(diǎn)在于，把在大范圍同尋找最優(yōu)整數(shù)解轉(zhuǎn)化為在小范圍內(nèi)尋找最優(yōu)整數(shù)解，而且在通過觀察圖形作出準(zhǔn)確判斷有困難的情況下，通過計(jì)算檢驗(yàn)作出準(zhǔn)確判斷的工作量比較小。其步驟為（1）在邊界折線頂點(diǎn)附近的小范圍內(nèi)搜索一個(gè)可行域內(nèi)的年整點(diǎn)；（

3、 2）過該點(diǎn)作一條斜率為（其中 A，B 分別為目標(biāo)函數(shù)中變量x，y 的系數(shù)）的直線，與可行域邊界折線相交得到一個(gè)小范圍的區(qū)域；（3）在這個(gè)小范圍區(qū)域內(nèi)繼續(xù)搜索全部最優(yōu)整數(shù)解。用“小范圍搜索法”成功解題的關(guān)鍵是分析，要把分析貫徹于解題的全過程，觀察圖形要分析，計(jì)算檢驗(yàn)也要分析，通過分析充分發(fā)掘線性約束條件和線性目標(biāo)函數(shù)的特殊性，使搜索范圍縮到最小，計(jì)算的工作量減到最小。下面以教科書中的題目為例，說明“小范圍搜索法”的運(yùn)用。例 1 教科書第 65 頁習(xí)題 7.4 題，題目略。本題的線性約束條件線性目標(biāo)函數(shù)z=200x+150y ，其中 x， y 分別為大房間與小房間的間數(shù)。作出可行域如圖1。（ 1

4、）搜索一個(gè)可行域內(nèi)鄰近邊界折線頂點(diǎn)的整點(diǎn)。解方程組得到點(diǎn) A（，），由于點(diǎn)A 的坐標(biāo)不是整數(shù)，故不是最優(yōu)解。由于要使目標(biāo)函數(shù)取最大值，因此要尋找可行域右上側(cè)靠近邊界或邊界上的整點(diǎn)。與點(diǎn)A 鄰近的整點(diǎn)共有4 個(gè)（ 2， 8），（ 2， 9），（ 3， 8）與（ 3，9），顯然點(diǎn)（ 2，8）是可行域內(nèi)的整點(diǎn)，點(diǎn)（3，9）不是可行域內(nèi)的整點(diǎn)。記點(diǎn)（a， b）處的目標(biāo)函數(shù)的值為z（ 2， 8），所以還應(yīng)檢驗(yàn)點(diǎn)（2，9）與（ 3， 8）是否在可行域內(nèi)。注意到目標(biāo)函數(shù)z=200x+150y=150(x+y)+50x，而 2+9=3+8，所以必有 z（ 3，8）>z（ 2，9），所以應(yīng)先檢驗(yàn)點(diǎn)（3，8

5、）是否在可行域內(nèi)。觀察與計(jì)算都表明該點(diǎn)在可行域內(nèi)。記點(diǎn)（3，8）為 B，B 即為搜索到的可行域內(nèi)鄰近邊界折線頂點(diǎn)的整點(diǎn)。（ 2）作出可行域內(nèi)的小范圍搜索區(qū)域。精選文檔算出 z（ 3， 8） =1800，過 B 作直線 200x+150y=18004x+3y=36.解方程組得到點(diǎn) C（ 0， 12）， C 為整點(diǎn)。解方程組得到點(diǎn) D（ 4， ）， ACD即是新的搜索區(qū)域，在 SACD（包括邊）內(nèi)可以搜索到全部最優(yōu)解整點(diǎn)，該搜索區(qū)域比可行域大大縮小，如圖 2。（ 3）在 ACD（包括邊）內(nèi)整點(diǎn)只有 B（ 3， 8）與 C（ 0，12），由于 B，C 在一直線上，所以 z（0，12）= z（ 3，8

6、）=1800，B，C均為最優(yōu)解整點(diǎn)， 1800 為目標(biāo)函數(shù)的最大值。 若要通過計(jì)算檢驗(yàn)在 ACD（包括邊） 內(nèi)搜索， 由于 x 0， 4) ，y(， 12，所以選擇x 的整數(shù)值檢驗(yàn)可使計(jì)算量小些，令x=0， 1， 2， 3，即可得到 ACD（包括邊）內(nèi)的全部整點(diǎn)只有B（ 3，8）與 C（ 0， 12）。顯然，“小范圍搜索法”的計(jì)算量要比把可行域內(nèi)的整點(diǎn)逐一代入計(jì)算檢驗(yàn)大大減少。至此用“小范圍搜索法”解題已全部完成，但在此解題過程中還可以有新的發(fā)現(xiàn)。注意到點(diǎn)C（ 0， 12）即為直線 6x+5y=50 與 y 軸的交點(diǎn)，直線 5x+3y=40 與 x 軸的交點(diǎn)為（ 8， 0），這兩個(gè)點(diǎn)都在可行域

7、內(nèi)，且都是可行域邊界折線的頂點(diǎn)，又z（ 8，0） =1600<z（0， 12），所以在以實(shí)施“小范圍搜索法”的第一步操作時(shí)，即可選定點(diǎn)C，再過點(diǎn) C 作直線 200x+150y=18004x+3y=36 ，同樣可以得到 ACD。 這就是第二種搜索方法。顯然第二種搜索方法比前面的第一種搜索方法更簡便。只是第二種搜索方法在觀察圖形時(shí)不易發(fā)現(xiàn)，因?yàn)橛^察圖1 總讓人覺得應(yīng)該在點(diǎn) A（， ）附近找一個(gè)整點(diǎn)比較好。這正是觀察的局限性。 觀察是認(rèn)識(shí)事物的開端和基礎(chǔ)，其重要性是不容忽視的。但觀察不容易深入事物的本質(zhì)，總不如思維的深刻嚴(yán)密，也不如計(jì)算的準(zhǔn)確可靠。例 2 教科書第 85 頁復(fù)習(xí)參考題七 A

8、組第 16 題，題目略。本題的線性約束條件線性目標(biāo)函數(shù)z=160x+252y ，其中 x， y 分別為 A 型車和 B 型車的輛數(shù)。作出可行域如圖3。（ 1）搜索一個(gè)可行域內(nèi)鄰近邊界折線頂點(diǎn)的整點(diǎn)。2精選文檔解方程組得到點(diǎn) A（7，）.解方程組得到點(diǎn) A（，4）.A， B 兩點(diǎn)都是可行域邊界折線的頂點(diǎn)，但它們都不是整點(diǎn)，所以不是最優(yōu)解。由于要使目標(biāo)函數(shù)取最小值，因此要尋找可行域左下側(cè)靠近邊界上的整點(diǎn)。顯然點(diǎn)（ 7，1）與（ 3，4）都是可行域內(nèi)的整點(diǎn)，又 z（ 7，1）=160×7+252×1=1372，z（ 3， 4）=160×3+252×4=1488

9、，z（ 7， 1） <z（ 3， 4），故點(diǎn)（ 7， 1）優(yōu)于點(diǎn)（ 3， 4）。記點(diǎn)（ 7， 1）為 C，點(diǎn)C 即為搜索到的可行域內(nèi)鄰近邊界折線頂點(diǎn)的整點(diǎn)。（ 2）作出可行域內(nèi)的小范圍搜索區(qū)域。過 C點(diǎn)直線 160x+252y=137240x+63y=343.解方程組得到設(shè)點(diǎn)（ 3.4 ， 3.3 ）為 D，得到 ACD，在 ACD（包括邊）內(nèi)可以搜索到全部最優(yōu)解整點(diǎn)，該搜索范圍比可行域大大縮小，如圖 4。（ 3）在 ACD（包括邊）內(nèi)，整點(diǎn)只有（ 7， 1）與（ 5， 2），由于點(diǎn)（ 5， 2）在線段 CD的下方，故必有 z（ 5，2） <z（7， 1），記點(diǎn)（ 5，2）為 E，E 即為最優(yōu)解整點(diǎn)。 z（ 5， 2）=160×5+252×2=1304 即為目標(biāo)函數(shù)的最小值。若要通過計(jì)算檢驗(yàn)在 ACD（包括邊）內(nèi)搜索，由于x(3.4 ， 7 ，y1 ， 3.3) ，所以選擇y 的整數(shù)值檢驗(yàn)可以使計(jì)算量小些，令 y=1，2， 3，即可得到 ACD（包括邊）內(nèi)的全部整點(diǎn)只有 C（7，1）與 E（ 5， 2）。顯然，“小范圍搜索法”的計(jì)算量比將可行域內(nèi)的整點(diǎn)逐一代入計(jì)算檢驗(yàn)大大減少。從上面的兩個(gè)例子中可以看到，用“小范圍搜索法”解線性規(guī)劃應(yīng)用問題，目標(biāo)明確，思路清晰，步驟簡明，