在工程設計、經營管理等活動中，經常會碰到最優化決策的實際問題，而解決此類問題一般以線性規劃為其重要的理論基礎。然而在實際問題中，最優解 (x,y) 通常要滿足x,y∈n ，這種最優解稱為整點最優解，下面通過具體例子談談如何求整點最優解 .
1．平移找解法
作出可行域後，先打網格，描出整點，然後平移直線l，直線l最先經過或最後經過的那個整點便是整點最優解.
例1、某木器廠生產圓桌和衣櫃兩種產品，現有兩種木料，第一種有72m3，第二種有56m3，假設生產每種產品都需要用兩種木料，生產乙隻圓桌和乙個衣櫃分別所需木料如下表所示.每生產乙隻圓桌可獲利6元,生產乙個衣櫃可獲利10元.木器廠在現有木料條件下,圓桌和衣櫃各生產多少,才使獲得利潤最多?
解：設生產圓桌x只,生產衣櫃y個,利潤總額為z元,那麼而z=6x+10y.
如圖所示,作出以上不等式組所表示的平面區域,即可行域.
作直線l:6x+10y=0,即l:3x+5y=0,把直線l向右上方平移至l1的位置時,直線經過可行域上點m,且與原點距離最大,此時z=6x+10y取最大值。
解方程組,得m點座標(350,100).
答：應生產圓桌350只,生產衣櫃100個,能使利潤總額達到最大.
點評：本題的最優點恰為直線0.18x+0.09y=72和0.08x+0.28y=56的交點m。
例 2 有一批鋼管，長度都是4000mm，要截成500mm和600mm兩種毛坯，且這兩種毛坯按數量比不小於配套，怎樣截最合理？
解：設截500mm的鋼管x根，600mm的y根，總數為z根。根據題意，得 ，目標函式為 ，
作出如圖所示的可行域內的整點，
作一組平行直線x+y=t，經過可行域內的點且和原點距離最遠的直線為過b（8，0）的直線，這時x+y=8.由於x,y為正整數，知（8，0）不是最優解。顯然要往下平移該直線，在可行域內找整點，使x+y=7，可知點（2，5），（3，4），（4，3），（5，2），（6，1）均為最優解．
答：略．
點評：本題與上題的不同之處在於，直線x+y=t經過可行域內且和原點距離最遠的點b（8，0）並不符合題意，此時必須往下平移該直線，在可行域內找整點，比如使x+y=7，從而求得最優解。
從這兩例也可看到，平移找解法一般適用於其可行域是有限區域且整點個數又較少，但作圖要求較高。
二、整點調整法
先按「平移找解法」求出非整點最優解及最優值，再借助不定方程的知識調整最優值，最後篩選出整點最優解．
例3．已知滿足不等式組，求使取最大值的整數．
解：不等式組的解集為三直線：，：，：所圍成的三角形內部（不含邊界），設與，與，與交點分別為，則座標分別為，，，
作一組平行線：平行於：，
當往右上方移動時，隨之增大，
∴當過點時最大為，但不是整數解，
又由知可取，
當時，代入原不等式組得， ∴；
當時，得或， ∴或；
當時，， ∴，
故的最大整數解為或．
3.逐一檢驗法
由於作圖有時有誤差，有時僅有圖象不一定就能準確而迅速地找到最優解，此時可將若干個可能解逐一校驗即可見分曉．
例4 一批長4000mm 的條形鋼材，需要將其截成長分別為518mm與698mm的甲、乙兩種毛坯，求鋼材的最大利用率．
解：設甲種毛坯截 x 根，乙種毛坯截 y 根，鋼材的利用率為 p ，則 ①，目標函式為 ②，線性約束條件①表示的可行域是圖中陰影部分的整點．②表示與直線518x+698y=4000平行的直線系。所以使p取得最大值的最優解是陰影內最靠近直線518x+698y=4000的整點座標．如圖看到(0，5)，(1，4)，(2，4)，(3，3)，(4，2)，(5，2)，(6，1)，(7，0)都有可能是最優解，將它們的座標逐一代入②進行校驗，可知當x=5,y=2時， ．
答：當甲種毛坯截5根，乙種毛坯截2根，鋼材的利用率最大，為99.65%．
解線性規劃問題的關鍵步驟是在圖（可行域）上完成的，所以作圖時應盡可能精確，圖上操作盡可能規範，但考慮到作圖時必然會有誤差，假如圖上的最優點並不十分明顯易辨時，不妨將幾個有可能是最優點的座標都求出來，然後逐一進行校驗，以確定整點最優解.
線性規劃中的整點問題求解方法
如果問題更複雜一點該怎麼辦？下面以課本第71頁習題7.4第4題為例介紹最優整數解問題的求解方法。某人有樓房一幢，室內面積共180，擬分隔成兩類房間作為旅遊客房，大房間每間面積為18，可住遊客5名，每名遊客每天住宿費為40元，小房間每間面積為15，可住遊客3名，每名遊客每天住宿費為50元，裝修大房間每...
線性規劃中的整點問題求解方法
線性規劃是運籌學的乙個重要分支，在實際生活中有著廣泛的應用。新教材中增加了線性規劃的內容，充分體現了數學的實際應用，發展了學生的數學應用意識。由於實際問題中線性規劃問題的最優解多為整數解，也是學生學習線性規劃的難點，因而求線性規劃的整數最優解的方法就顯得尤為重要了。但教材中對此類問題卻一帶而過，對於...
線性規劃模型中MATLAB的求解實現
用matlab程式實現了線性規劃問題數學模型的求解方法,並進一步通過對例項模型求解方法的分析比較,證明所 採用的程式方法有效快捷.文中的程式簡單明瞭且具有通用性,只需輸入規劃模型中對應的相關矩陣,立即得到最優解和最優值.結果表明,matlab可以高效 方便地解決線性規劃問題.線性規劃 簡記lp 是合...