線性規(guī)劃中的整點問題求解方法

《線性規(guī)劃中的整點問題求解方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、線性規(guī)劃中的整點問題求解方法宜昌市一中祝海燕線性規(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é)生在解題過程中對于具體的驗算過程掌握還不夠清晰。以下為教材（人教版必修第二冊上，2006年第2版）第69頁的例4：鋼板類型規(guī)格類型A規(guī)格B規(guī)格

2、C規(guī)格第一種鋼板211第二種鋼板123要將兩種大小不同的的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如表所示，今需要A、B、C三種規(guī)格的成品分別為15，18，27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。解：設(shè)需要截第一種鋼板x張，第二張鋼板y張，則，作出可行域（如圖所示）,目標(biāo)函數(shù)為，作出在一組平行直線中（為參數(shù)）經(jīng)過可行域內(nèi)的點且和原點距離最近的直線，此直線經(jīng)過直線和直線的交點，直線方程為，由于都不是整數(shù)，而最優(yōu)解中，，必須都是整數(shù)，所以可行域內(nèi)點不是最優(yōu)解。經(jīng)過

3、可行域內(nèi)的整點（橫坐標(biāo)和縱坐標(biāo)都是整數(shù)的點）且與原點距離最近的直線是且經(jīng)過的整點是B（3，9）和C（4，8），它們都是最優(yōu)解。答：要截得所需三種規(guī)格的鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種，第一種截法是截第一種鋼板3張、第二種鋼板9張；第二種截法是截第一種鋼板4張、第二種鋼板8張。兩種方法都最少要截兩種鋼板共12張。線性規(guī)劃問題中的整點最優(yōu)解是教學(xué)中的一個難點，教材中利用圖解法比較直觀有效地突破了這一難點，但其中有兩個問題需要弄清楚：直線是怎樣確定的？整點B（3，9）和C（4，8）又是怎樣確定的？在求最優(yōu)解時，我們

4、是將平行直線向可行域內(nèi)平移，在向右上方平移時，3的值是增加的，而經(jīng)過點的直線為，當(dāng)值增加的過程中，其最小值是12，所以與原點距離最近的直線可能是。若在可行域內(nèi)直線上有整點則均是最優(yōu)解。而直線與邊界直線及的交點坐標(biāo)為（3，9）、（4.5，7.5），因此直線在可行域內(nèi)的整點只有B（3，9）和C（4，8），即為所求問題的最優(yōu)解。如果問題更復(fù)雜一點該怎么辦？下面以課本第71頁習(xí)題7.4第4題為例介紹最優(yōu)整數(shù)解問題的求解方法。某人有樓房一幢，室內(nèi)面積共180，擬分隔成兩類房間作為旅游客房，大房間每間面積為18，可住游客5名，每名游

5、客每天住宿費為40元，小房間每間面積為15，可住游客3名，每名游客每天住宿費為50元，裝修大房間每間需要1000元，裝修小房間每間需要600元，如果他們只能籌8000元用于裝修，且游客能住滿客房，它應(yīng)隔出大房間和小房間各多少間，能獲最大利益？1055oxy4x+3y=365x+3y=406x+5y=60方法一：網(wǎng)格法：設(shè)應(yīng)隔出大房間間和小房間間()，則即：，目標(biāo)函數(shù)為，作出可行域如圖：根據(jù)目標(biāo)函數(shù)，作出一組平行線。當(dāng)此線經(jīng)過直線和直線的交點，此直線方程為，由于不是整數(shù)，所以經(jīng)過整點（3，8）時，才是最優(yōu)解，同時直線上的整

6、點(0,12)也是最優(yōu)解，即應(yīng)隔大房間3間，小房間8間，或者隔大房間0間，小房間12間，所獲利益最大。如果考慮到不同客人的需要，應(yīng)隔大房間3間，小房間8間。對圖形的精度要求不高的可以用網(wǎng)格法，實際應(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ù)為得整點（3，8）和（0，12）是最優(yōu)解。當(dāng)可行域較小、邊

7、界附近的整點較少時可以用整點驗證法；先找出可行域內(nèi)非整最優(yōu)解一側(cè)邊界附近所有的整點，再將每個整點代入目標(biāo)函數(shù)確定最優(yōu)解。當(dāng)可行域較大、邊界附近的整點較多時這種方法運算量較大。方法三:調(diào)整最值法：目標(biāo)函數(shù)為：作出在一組平行直線：（為參數(shù)）,經(jīng)過的直線方程為，目標(biāo)直線在向可行域內(nèi)平移的過程中，的值是減少的，在減少的過程中因，都是整3數(shù)，因而也為整數(shù)，故最大整數(shù)可能是37。又因為直線與邊界直線和直線的交點分別為，在此兩交點間直線上沒有整點，因此目標(biāo)直線不是。須再向可行域內(nèi)平移一個單位成為。目標(biāo)直線邊界直線和直線的交點分別為及（

8、0，12）；又因為從目標(biāo)直線可得，可知若，為整數(shù)，則為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)直線”方程代入約束條件，并求變量范圍：④確定“目標(biāo)直