典型例題：線性規(guī)劃中的整點(diǎn)問題

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

(2，9),

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

(5，5),

(6，3),(7，1),(8，0)將這些點(diǎn)分別代入Z=200x+150y,求出各點(diǎn)對應(yīng)的值，得整點(diǎn)(0，12),(3，8)是最優(yōu)解，此時z的最大值為1800。4x+3y=00248101418612162612144108xy6x+5y=605x+3y=40A答：他應(yīng)隔出大房間0間、小房間12間或者大房間3間、小房間8間，能獲得最大收益每天1800元例2、要將兩種大小不同的鋼板截成Ａ．Ｂ．Ｃ三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：A規(guī)格Ｂ規(guī)格Ｃ規(guī)格第一種鋼板211第二種鋼板123今需要Ａ、Ｂ、Ｃ三種規(guī)格的成品分別為15，18，27塊，各截這兩種鋼板多少張可以滿足需要且使所用鋼板數(shù)目最少？解：設(shè)需要截第一種鋼板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并平移，由圖可知，當(dāng)直線z=x+y經(jīng)過可行域上的點(diǎn)A時，截距z最小。解方程組得點(diǎn)A的坐標(biāo)為.答：滿足題意的截法有兩種：截第一種鋼板3張，第二種鋼板9張，或者截第一種鋼板4張，第二種鋼板8張方法一：調(diào)整最值法：

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

但目標(biāo)直線在向可行域內(nèi)平移過程中，若需平移多次才能達(dá)到目的，將十分麻煩。方法二：整點(diǎn)驗(yàn)證法：

當(dāng)可行域較小、邊界附近的整點(diǎn)較少時可以用整點(diǎn)驗(yàn)證法；將每個可能的整點(diǎn)代入目標(biāo)函數(shù)確定最優(yōu)解。

但當(dāng)可行域較大、邊界附近的整點(diǎn)較多時運(yùn)算量較大

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

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

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

某商店計(jì)劃同時銷