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

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

1、線性規(guī)劃中的整點(diǎn)問題求解方法宜昌市一中祝海燕線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，在實(shí)際生活中有著廣泛的應(yīng)用。新教材中增加了線性規(guī)劃的內(nèi)容，充分體現(xiàn)了數(shù)學(xué)的實(shí)際應(yīng)用，發(fā)展了學(xué)生的數(shù)學(xué)應(yīng)用意識(shí)。由于實(shí)際問題中線性規(guī)劃問題的最優(yōu)解多為整數(shù)解，也是學(xué)生學(xué)習(xí)線性規(guī)劃的難點(diǎn)，因而求線性規(guī)劃的整數(shù)最優(yōu)解的方法就顯得尤為重要了。但教材中對(duì)此類問題卻一帶而過，對(duì)于具體的驗(yàn)算過程并沒有作必要的描述，以致學(xué)生在解題過程中對(duì)于具體的驗(yàn)算過程掌握還不夠清晰。以下為教材（人教版必修第二冊(cè)上，2006年第2版）第69頁的例4：鋼板類型規(guī)格類型A規(guī)格B規(guī)格C規(guī)格第一種鋼板211第二種鋼板123要將兩種大小不同的的鋼板截成A

2、、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如表所示，今需要A、B、C三種規(guī)格的成品分別為15，18，27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。解：設(shè)需要截第一種鋼板x張，第二張鋼板y張，則，作出可行域（如圖所示）,目標(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)解。答：要截得

3、所需三種規(guī)格的鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種，第一種截法是截第一種鋼板3張、第二種鋼板9張；第二種截法是截第一種鋼板4張、第二種鋼板8張。兩種方法都最少要截兩種鋼板共12張。線性規(guī)劃問題中的整點(diǎn)最優(yōu)解是教學(xué)中的一個(gè)難點(diǎn)，教材中利用圖解法比較直觀有效地突破了這一難點(diǎn)，但其中有兩個(gè)問題需要弄清楚：直線是怎樣確定的？整點(diǎn)B（3，9）和C（4，8）又是怎樣確定的？在求最優(yōu)解時(shí)，我們是將平行直線向可行域內(nèi)平移，在向右上方平移時(shí)，3的值是增加的，而經(jīng)過點(diǎn)的直線為，當(dāng)值增加的過程中，其最小值是12，所以與原點(diǎn)距離最近的直線可能是。若在可行域內(nèi)直線上有整點(diǎn)則均是最優(yōu)解。而直線與邊界直線及的

4、交點(diǎn)坐標(biāo)為（3，9）、（4.5，7.5），因此直線在可行域內(nèi)的整點(diǎn)只有B（3，9）和C（4，8），即為所求問題的最優(yōu)解。如果問題更復(fù)雜一點(diǎn)該怎么辦？下面以課本第71頁習(xí)題7.4第4題為例介紹最優(yōu)整數(shù)解問題的求解方法。某人有樓房一幢，室內(nèi)面積共180，擬分隔成兩類房間作為旅游客房，大房間每間面積為18，可住游客5名，每名游客每天住宿費(fèi)為40元，小房間每間面積為15，可住游客3名，每名游客每天住宿費(fèi)為50元，裝修大房間每間需要1000元，裝修小房間每間需要600元，如果他們只能籌8000元用于裝修，且游客能住滿客房，它應(yīng)隔出大房間和小房間各多少間，能獲最大利益？1055oxy4x+3y=36

5、5x+3y=406x+5y=60方法一：網(wǎng)格法：設(shè)應(yīng)隔出大房間間和小房間間()，則即：，目標(biāo)函數(shù)為，作出可行域如圖：根據(jù)目標(biāo)函數(shù)，作出一組平行線。當(dāng)此線經(jīng)過直線和直線的交點(diǎn)，此直線方程為，由于不是整數(shù)，所以經(jīng)過整點(diǎn)（3，8）時(shí)，才是最優(yōu)解，同時(shí)直線上的整點(diǎn)(0,12)也是最優(yōu)解，即應(yīng)隔大房間3間，小房間8間，或者隔大房間0間，小房間12間，所獲利益最大。如果考慮到不同客人的需要，應(yīng)隔大房間3間，小房間8間。對(duì)圖形的精度要求不高的可以用網(wǎng)格法，實(shí)際應(yīng)用中常利用坐標(biāo)紙作圖；先作出可行域內(nèi)的網(wǎng)格，再平移目標(biāo)直線確定最優(yōu)解。方法二：整點(diǎn)驗(yàn)證法：找出可行域內(nèi)靠近非整點(diǎn)最優(yōu)解一側(cè)邊界附近所有的整點(diǎn):

6、（0，12）、（1，10）、（2，9）、（3，8）、（4，6）、（5，5）、（6，3）、（7，1）、（8，0），分別代入目標(biāo)函數(shù)為得整點(diǎn)（3，8）和（0，12）是最優(yōu)解。當(dāng)可行域較小、邊界附近的整點(diǎn)較少時(shí)可以用整點(diǎn)驗(yàn)證法；先找出可行域內(nèi)非整最優(yōu)解一側(cè)邊界附近所有的整點(diǎn)，再將每個(gè)整點(diǎn)代入目標(biāo)函數(shù)確定最優(yōu)解。當(dāng)可行域較大、邊界附近的整點(diǎn)較多時(shí)這種方法運(yùn)算量較大。方法三:調(diào)整最值法：目標(biāo)函數(shù)為：作出在一組平行直線：（為參數(shù)）,經(jīng)過的直線方程為，目標(biāo)直線在向可行域內(nèi)平移的過程中，的值是減少的，在減少的過程中因，都是整3數(shù)，因而也為整數(shù)，故最大整數(shù)可能是37。又因?yàn)橹本€與邊界直線和直線的交點(diǎn)分別為

7、，在此兩交點(diǎn)間直線上沒有整點(diǎn)，因此目標(biāo)直線不是。須再向可行域內(nèi)平移一個(gè)單位成為。目標(biāo)直線邊界直線和直線的交點(diǎn)分別為及（0，12）；又因?yàn)閺哪繕?biāo)直線可得，可知若，為整數(shù)，則為3的倍數(shù)；在[0，4]中滿足條件只有0與3，故得最優(yōu)解（0，12）及（3，8）。當(dāng)目標(biāo)函數(shù)（或提取公倍數(shù)后）系數(shù)不大時(shí)可以用調(diào)整最值法，一般步驟為：①平移直線尋找非整最優(yōu)解；②調(diào)整最值，確定“目標(biāo)直線”③由“目標(biāo)直線”方程代入約束條件，并求變量范圍：④確定“目標(biāo)直