線性規劃是運籌學的乙個重要分支，在實際生活中有著廣泛的應用。新教材中增加了線性規劃的內容，充分體現了數學的實際應用，發展了學生的數學應用意識。由於實際問題中線性規劃問題的最優解多為整數解，也是學生學習線性規劃的難點，因而求線性規劃的整數最優解的方法就顯得尤為重要了。
但教材中對此類問題卻一帶而過，對於具體的驗算過程並沒有作必要的描述，以致學生在解題過程中對於具體的驗算過程掌握還不夠清晰。
例1：要將兩種大小不同的的鋼板截成a、b、c三種規格，每張鋼板可同時截得三種規格的小鋼板的塊數如表所示，今需要a、b、c三種規格的成品分別為15，18，27塊，問各截這兩種鋼板多少張可得所需三種規格成品，且使所用鋼板張數最少。
解：設需要截第一種鋼板x張，第二張鋼板y張，則，作出可行域（如圖所示）,目標函式為，作出在一組平行直線中（為引數）經過可行域內的點且和原點距離最近的直線，此直線經過直線和直線的交點，直線方程為，由於都不是整數，而最優解中，，必須都是整數，所以可行域內點不是最優解。
經過可行域內的整點（橫座標和縱座標都是整數的點）且與原點距離最近的直線是且經過的整點是b（3，9）和c（4，8），它們都是最優解。
答：要截得所需三種規格的鋼板，且使所截兩種鋼板的張數最少的方法有兩種，第一種截法是截第一種鋼板3張、第二種鋼板9張；第二種截法是截第一種鋼板4張、第二種鋼板8張。兩種方法都最少要截兩種鋼板共12張。
線性規劃問題中的整點最優解是教學中的乙個難點，教材中利用**法比較直觀有效地突破了這一難點，但其中有兩個問題需要弄清楚：直線是怎樣確定的？整點b（3，9）和c（4，8）又是怎樣確定的？
在求最優解時，我們是將平行直線向可行域內平移，在向右上方平移時，的值是增加的，而經過點的直線為，當值增加的過程中，其最小值是12，所以與原點距離最近的直線可能是。若在可行域內直線上有整點則均是最優解。而直線與邊界直線及的交點座標為（3，9）、（4.
5，7.5），因此直線在可行域內的整點只有b（3，9）和c（4，8），即為所求問題的最優解。
如果問題更複雜一點該怎麼辦？下面以課本第71頁習題7.4第4題為例介紹最優整數解問題的求解方法。
某人有樓房一幢，室內面積共180，擬分隔成兩類房間作為旅遊客房，大房間每間面積為18，可住遊客5名，每名遊客每天住宿費為40元，小房間每間面積為15，可住遊客3名，每名遊客每天住宿費為50元，裝修大房間每間需要1000元，裝修小房間每間需要600元，如果他們只能籌8000元用於裝修，且遊客能住滿客房，它應隔出大房間和小房間各多少間，能獲最大利益？
方法一：網格法： 設應隔出大房間間和小房間間()，則即：，目標函式為，作出可行域如圖：
根據目標函式，作出一組平行線。當此線經過直線和直線的交點，此直線方程為，由於不是整數，所以經過整點（3，8）時，才是最優解，同時直線上的整點(0,12)也是最優解，即應隔大房間3間，小房間8間，或者隔大房間0間，小房間12間，所獲利益最大。如果考慮到不同客人的需要，應隔大房間3間，小房間8間。
對圖形的精度要求不高的可以用網格法，實際應用中常利用座標紙作圖；先作出可行域內的網格，再平移目標直線確定最優解。
方法二：整點驗證法：找出可行域內靠近非整點最優解一側邊界附近所有的整點:
（0，12）、（1，10）、（2，9）、（3，8）、（4，6）、（5，5）、（6，3）、（7，1）、（8，0），分別代入目標函式為得整點（3，8）和（0，12）是最優解。
當可行域較小、邊界附近的整點較少時可以用整點驗證法；先找出可行域內非整最優解一側邊界附近所有的整點，再將每個整點代入目標函式確定最優解。當可行域較大、邊界附近的整點較多時這種方法運算量較大。
方法三:調整最值法：目標函式為：
作出在一組平行直線：（為引數）,經過的直線方程為，目標直線在向可行域內平移的過程中，的值是減少的，在減少的過程中因，都是整數，因而也為整數，故最大整數可能是37。又因為直線與邊界直線和直線的交點分別為，在此兩交點間直線上沒有整點，因此目標直線不是。
須再向可行域內平移乙個單位成為。目標直線邊界直線和直線的交點分別為及（0，12）；又因為從目標直線可得，可知若，為整數，則為3的倍數；在[0，4]中滿足條件只有0與3，故得最優解（0，12）及（3，8）。
當目標函式（或提取公倍數後）係數不大時可以用調整最值法，一般步驟為：①平移直線尋找非整最優解；②調整最值，確定「目標直線」③由「目標直線」方程代入約束條件，並求變數範圍：④ 確定「目標直線」上整數解。
但目標直線在向可行域內平移過程中，若需平移多次才能達到目的，將十分麻煩。
方法四：縮小可行域法：
作出一組平行直線：（為引數）,經過的直線方程為，
我們利用b附近的網格，可在可行域內附近找到b（3，8）這幾個整點。過b作直線：，然後檢驗直線與邊界直線和直線圍成的陰影區域內有無整點，經檢驗無整點。
故直線上的整點b（3，8）、c（0，12）為最優整點解。(若陰影區域內的有整點可利用解法二確定最優解)
縮小可行域方法的思路是先將題目作為一般的線性規劃最優解來求,通過解出的非整數最優解來排除部分可行域,從而達到縮小可行域的目的. 可以克服在前方法三中有可能要多次平移找解的缺陷，適用範圍廣泛。一般步驟為：
①根據非整點最優解a點的座標在其附近尋找最近的整點b；②過b作與目標直線平行的直線，與原邊界圍成的陰影區域即縮小了最優解所在可行域；③找出陰影區域內的所有整點再利用解法二確定最優解。
總之，以上四種基本方法各有各的特點，因此有時要根據具體情況選擇合適的方法。
線性規劃中的整點問題求解方法
如果問題更複雜一點該怎麼辦？下面以課本第71頁習題7.4第4題為例介紹最優整數解問題的求解方法。某人有樓房一幢，室內面積共180，擬分隔成兩類房間作為旅遊客房，大房間每間面積為18，可住遊客5名，每名遊客每天住宿費為40元，小房間每間面積為15，可住遊客3名，每名遊客每天住宿費為50元，裝修大房間每...
線性規劃中整點最優解的求解策略
在工程設計 經營管理等活動中，經常會碰到最優化決策的實際問題，而解決此類問題一般以線性規劃為其重要的理論基礎。然而在實際問題中，最優解 x,y 通常要滿足x,y n 這種最優解稱為整點最優解，下面通過具體例子談談如何求整點最優解 1 平移找解法 作出可行域後，先打網格，描出整點，然後平移直線l，直線...
用matlab求解線性規劃問題
實驗四用matlab求解線性規劃問題 一 實驗目的 了解matlab的優化工具箱，能利用matlab求解線性規劃問題。二 實驗內容 線性規劃的數學模型有各種不同的形式，其一般形式可以寫為 目標函式 約束條件 這裡稱為目標函式，稱為價值係數，稱為價值向量，為求解的變數，由係數組成的矩陣 稱為不等式約束...