對線性規(guī)劃整點(diǎn)問題的探究(蔣政)

對線性規(guī)劃整點(diǎn)問題的探究精確圖解法求整數(shù)最優(yōu)解(課本P88習(xí)題16)x+y=94x+5y=30x+y=94x+5y=30160x+252y=0ABCD解：設(shè)每天派出A型車x輛、B型車y輛，公司所花的本錢為z元，那么即z=160x+252y.如圖可行域是ABCD圍成的區(qū)域，作直線160x+252y=0，圖形中兩直線160x+252y=0和4x+5y=30接近平行，比擬直線斜率k=>-,平移直線160x+252y=0，由圖可知在A〔7，〕處取到最小值，但A不是整數(shù)解。在可行域內(nèi)共有〔3，4〕，〔4，3〕，〔4，4〕，〔5，2〕，〔5，3〕，〔6，2〕，〔6，3〕，〔7，1〕，〔7，2〕整數(shù)解，經(jīng)檢驗(yàn)只有〔5，2〕是最優(yōu)解，此時(shí)z=160×5+252×2=1304元。這種方法適用于區(qū)域是封閉區(qū)域，且區(qū)域內(nèi)的整數(shù)點(diǎn)可數(shù)，坐標(biāo)網(wǎng)絡(luò)畫出來容易在圖上識別哪些整點(diǎn)在可行域內(nèi)。二、利用近似解估算整數(shù)最優(yōu)解(課本P63例4)要將兩種不同的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：規(guī)格類型鋼板類型A規(guī)格B規(guī)格C規(guī)格第一種鋼板211第二種鋼板123今需要A、B、C三種規(guī)格的成品分別為15、18、27塊，問各截這兩種鋼板多少張可得所需的三種規(guī)格成品，且所使用鋼板張數(shù)最少。xxOy解：設(shè)需截取第一種鋼板x張，第二種鋼板y張，那么目標(biāo)函數(shù)z=x+y,如圖可行域是陰影局部，目標(biāo)函數(shù)在A點(diǎn)取到最優(yōu)解。解方程組得A〔，〕但不是整數(shù)解，此時(shí),z=+=,那么在可行域內(nèi)取到整數(shù)解的z=12.即經(jīng)過可行域內(nèi)的整點(diǎn)，且與原點(diǎn)距離最近的直線是x+y=12，那么整點(diǎn)一定在B、C之間。解方程組，得B〔3，9〕；解方程組，得C〔，〕；那么整點(diǎn)的橫坐標(biāo)3≤x≤，所以滿足條件的最優(yōu)解是〔3，9〕，〔4，8〕.本來近似解z=，而=11.4也不約等于12，學(xué)生不理解為什么z=12。這不是近似解約等于多少的問題，而是由于不是可行域內(nèi)的整數(shù)解，可行域內(nèi)的整數(shù)解至少要大于。這種方法先由圖解法觀察出最優(yōu)解在哪個(gè)點(diǎn)處取到，再由精確值估算出整數(shù)解，一定注意整數(shù)解的估算不是四舍五入取整，而是在可行域內(nèi)的整數(shù)解。xOxOy3224AB例2．求以下區(qū)域內(nèi)整數(shù)點(diǎn)的個(gè)數(shù)解：如圖區(qū)域是陰影局部的直角三角形，把它補(bǔ)為矩形。那么矩形區(qū)域內(nèi)的整點(diǎn)有33×25=825個(gè)。而線段AB上的整點(diǎn)〔含端點(diǎn)〕是不定方程3x+4y=96的非負(fù)整數(shù)解。又x=32-,那么y一定被3整除，滿足條件的y有0，3，6…，24共9個(gè)，即線段AB上的整點(diǎn)有9個(gè)。那么陰影局部區(qū)域內(nèi)的整點(diǎn)有=417個(gè)。四、利用窮舉法求整數(shù)最優(yōu)解某人有樓房一幢，室內(nèi)面積共180m2，擬分隔成兩類房間作為旅游客房，大房間每間面積為18m2，可住游客5名，每名游客每天住宿費(fèi)為40元；小房間每間面積為15m2，可住游客3名，每名游客每天住宿費(fèi)為50元；裝修大房間每間需1000元，裝修小房間每間需600元。如果他只能籌款8000元用于裝修，且游客能住滿客房，他應(yīng)隔出大房間和小房間各多少間，能獲得最大收益？xyxyO18x+15y=1801000x+600y=8000A200x+150y=1800A200x+150y=1800z=200x+150y如圖可行域是陰影局部，作直線L：200x+150y=0，即4x+3y=0,將直線L平移到A點(diǎn)時(shí)與原點(diǎn)距離最大。解方程組得A〔〕，但不是整數(shù)解。此時(shí)z=200×=。又z=200x+150y=50〔4x+3y〕，那么z取到的最優(yōu)解一定被50整除，那么z的最大值是1850。即4x+3y=37，又4x+3y=37的所有整數(shù)解是〔1，11〕，〔4，7〕〔7，3〕，而〔1，11〕不滿足6x+5y≤60，舍去；〔4，7〕不滿足5x+3y≤40，舍去；〔7，3〕不滿足5x+3y≤40，舍去。所以z的最大值不可能是1850。那么z的最大值可能是1800、1750、1700…，直到在可行域內(nèi)找到滿足條件的最優(yōu)解。假設(shè)z=1800，即4x+3y=36，又4x+3y=36的所有整數(shù)解是〔0，12〕，〔3，8〕〔6，4〕，〔9，0〕，經(jīng)檢驗(yàn)只有〔0，12〕，〔3，8〕在可行域內(nèi)，所以當(dāng)x