資源描述：
《線性規(guī)劃中整點問題的求解策略.docx》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、線性規(guī)劃中整點問題的求解策略四川省武勝飛龍中學校梁洪斌鄭秋華（）在有關線性規(guī)劃的求解問題中，經(jīng)常會碰到最優(yōu)化決策的整點問題，而解決此類問題一般以線性規(guī)劃為其重要的理論基礎。然而在實際求解中，對于最優(yōu)解(x,y)通常要滿足x,y∈N，這種最優(yōu)解稱為整點最優(yōu)解時，很多同學感到束手無策，下面通過具體例子談談如何求整點最優(yōu)解的問題.1．平移找解法作出可行域后，先打網(wǎng)格，描出整點，然后平移直線l，直線l最先經(jīng)過或最后經(jīng)過的那個整點便是整點最優(yōu)解.例1、某木器廠生產(chǎn)圓桌和衣柜兩種產(chǎn)品，現(xiàn)有兩種木料，第一種有72m3，第二種有56m3，假設生產(chǎn)每種產(chǎn)品都需要用兩種木料，生產(chǎn)一只
2、圓桌和一個衣柜分別所需木料如下表所示.每生產(chǎn)一只圓桌可獲利6元,生產(chǎn)一個衣柜可獲利10元.木器廠在現(xiàn)有木料條件下,圓桌和衣柜各生產(chǎn)多少,才使獲得利潤最多?產(chǎn)品木料(單位m3)第一種第二種圓桌0.180.08衣柜0.090.28解：設生產(chǎn)圓桌x只,生產(chǎn)衣柜y個,利潤總額為z元,那么而z=6x+10y.如圖所示,作出以上不等式組所表示的平面區(qū)域,即可行域.作直線l:6x+10y=0,即l:3x+5y=0,把直線l向右上方平移至l1的位置時,直線經(jīng)過可行域上點M,且與原點距離最大,此時z=6x+10y取最大值。解方程組,得M點坐標(350,100).答：應生產(chǎn)圓桌350
3、只,生產(chǎn)衣柜100個,能使利潤總額達到最大.點評：本題的最優(yōu)點恰為直線0.18x+0.09y=72和0.08x+0.28y=56的交點M。例2有一批鋼管，長度都是4000mm，要截成500mm和600mm兩種毛坯，且這兩種毛坯按數(shù)量比不小于配套，怎樣截最合理？解：設截500mm的鋼管x根，600mm的y根，總數(shù)為z根。根據(jù)題意，得，目標函數(shù)為，作出如圖所示的可行域內的整點，作一組平行直線x+y=t，經(jīng)過可行域內的點且和原點距離最遠的直線為過B（8，0）的直線，這時x+y=8.由于x,y為正整數(shù)，知（8，0）不是最優(yōu)解。顯然要往下平移該直線，在可行域內找整點，使x+
4、y=7，可知點（2，5），（3，4），（4，3），（5，2），（6，1）均為最優(yōu)解．答：略．點評：本題與上題的不同之處在于，直線x+y=t經(jīng)過可行域內且和原點距離最遠的點B（8，0）并不符合題意，此時必須往下平移該直線，在可行域內找整點，比如使x+y=7，從而求得最優(yōu)解。從這兩例也可看到，平移找解法一般適用于其可行域是有限區(qū)域且整點個數(shù)又較少，但作圖要求較高。二、整點調整法先按“平移找解法”求出非整點最優(yōu)解及最優(yōu)值，再借助不定方程的知識調整最優(yōu)值，最后篩選出整點最優(yōu)解．例3．已知滿足不等式組，求使取最大值的整數(shù)．解：不等式組的解集為三直線：，：，：所圍成的三角形內
5、部（不含邊界），設與，與，與交點分別為，則坐標分別為，，，作一組平行線：平行于：，當往右上方移動時，隨之增大，∴當過點時最大為，但不是整數(shù)解，又由知可取，當時，代入原不等式組得，∴；當時，得或，∴或；當時，，∴，故的最大整數(shù)解為或．3.逐一檢驗法由于作圖有時有誤差，有時僅有圖象不一定就能準確而迅速地找到最優(yōu)解，此時可將若干個可能解逐一校驗即可見分曉．例4一批長4000mm的條形鋼材，需要將其截成長分別為518mm與698mm的甲、乙兩種毛坯，求鋼材的最大利用率．解：設甲種毛坯截x根，乙種毛坯截y根，鋼材的利用率為P，則①，目標函數(shù)為②，線性約束條件①表示的可行域是
6、圖中陰影部分的整點．②表示與直線518x+698y=4000平行的直線系。所以使P取得最大值的最優(yōu)解是陰影內最靠近直線518x+698y=4000的整點坐標．如圖看到(0，5)，(1，4)，(2，4)，(3，3)，(4，2)，(5，2)，(6，1)，(7，0)都有可能是最優(yōu)解，將它們的坐標逐一代入②進行校驗，可知當x=5,y=2時，．答：當甲種毛坯截5根，乙種毛坯截2根，鋼材的利用率最大，為99.65%．解線性規(guī)劃問題的關鍵步驟是在圖（可行域）上完成的，所以作圖時應盡可能精確，圖上操作盡可能規(guī)范，但考慮到作圖時必然會有誤差，假如圖上的最優(yōu)點并不十分明顯易辨時，不妨
7、將幾個有可能是最優(yōu)點的坐標都求出來，然后逐一進行校驗，以確定整點最優(yōu)解.
