線性規劃中的整點問題例1、某人有樓房一座，室內面積共180m2，擬分隔成兩類房間作為旅游客房，大房間每間面積為18m2，可住游客5名，每名游客每天住宿費為40元；小房間每間面積為15m2，可住游客3名，每名游客每天住宿費為50元；裝修大房間每間需1000元，裝修小房間每間需600元。如果他只能籌款8000元用于裝修，且游客能住滿客房，他應隔出大房間和小房間各多少間，能獲得最大收益？解：設隔出大房間x間，小房間y間，收益為z元，則Z=200x+150y，且x,y滿足如圖，可行域為陰影部分，作直線l0：200x+150y=0，即4x+3y=0,將直線l0平移到A點時z最大。解方程組4x+3y=00248101418612162612144108xy6x+5y=605x+3y=40A由圖可知目標函數取得最大值的整點分布在可行域上側靠近邊界的區域，考察可能的整點(0，12),(1，10),

(2，9),

(3，8),(4，6),

(5，5),

(6，3),(7，1),(8，0)將這些點分別代入Z=200x+150y,求出各點對應的值，得整點(0，12),(3，8)是最優解，此時z的最大值為1800。4x+3y=00248101418612162612144108xy6x+5y=605x+3y=40A答：他應隔出大房間0間、小房間12間或者大房間3間、小房間8間，能獲得最大收益每天1800元例2、要將兩種大小不同的鋼板截成Ａ．Ｂ．Ｃ三種規格，每張鋼板可同時截得三種規格的小鋼板的塊數如下表所示：A規格Ｂ規格Ｃ規格第一種鋼板211第二種鋼板123今需要Ａ、Ｂ、Ｃ三種規格的成品分別為15，18，27塊，各截這兩種鋼板多少張可以滿足需要且使所用鋼板數目最少？解：設需要截第一種鋼板x張，第二種鋼板y張，共需這兩種鋼板z

張，則z=x+y,且2x+y≥

15x+2y≥

18x+3y≥

27x≥0,y≥0作出可行域如圖所示2x+y=15x+2y=18x+3y=27y+x=002481014186121626121422410816182024xyA作出直線l0:x+y=0并平移，由圖可知，當直線z=x+y經過可行域上的點A時，截距z最小。解方程組得點A的坐標為.答：滿足題意的截法有兩種：截第一種鋼板3張，第二種鋼板9張，或者截第一種鋼板4張，第二種鋼板8張方法一：調整最值法：

當目標函數系數不大時可以用調整最值法，一般步驟為：①平移直線尋找非整最優解；②調整最值，確定“目標直線”③由“目標直線”方程代入約束條件，并求變量范圍：④確定“目標直線”上整數解。

但目標直線在向可行域內平移過程中，若需平移多次才能達到目的，將十分麻煩。方法二：整點驗證法：

當可行域較小、邊界附近的整點較少時可以用整點驗證法；將每個可能的整點代入目標函數確定最優解。

但當可行域較大、邊界附近的整點較多時運算量較大

規律總結：典例:某學校預算2000元購買單價為100元的桌子和40元的凳子，希望購買的桌凳總數盡可能多，但凳子不少于桌子，且不多于桌子的2倍，求該學校所購買的桌、凳數分別為多少？解：設學校購買的桌、凳數分別為x、y，總數為z，則z=x+y,且x、y滿足：

即作出可行域如圖所示02481014186121626121422410816182024xy5x+2y=1002x－y=0x-y=0x+y=0A答：該學校應購買11張桌子，22個凳子.

02481014186121626121422410816182024xy5x+2y=1002x－y=0x-y=0x+y=0A課后作業：

某商店計劃同時銷