簡單的線性規(guī)劃問題

簡單的線性規(guī)劃問題

近年來，各級各類數(shù)學(xué)競賽中頻頻出現(xiàn)線性規(guī)劃問題。所謂線性規(guī)劃，是指求線性函數(shù)在線性(不等式或等式)約束下達最(小或大)值的問題。線性規(guī)劃廣泛應(yīng)用于工農(nóng)業(yè)、軍事、交通運輸、決策管理與規(guī)劃、科學(xué)實驗等領(lǐng)域。本文擬通過競賽試題介紹常用的解題思路和方法。 一、運用數(shù)量關(guān)系解題　　　　　　　　　　　　　　　　　　　　　　　　　 　例1某家電生產(chǎn)企業(yè)根據(jù)市場調(diào)查分析，決定調(diào)整產(chǎn)品生產(chǎn)方案，準備每周(按120個工時計算)生產(chǎn)空調(diào)器、彩電、冰箱共360臺，且冰箱至少生產(chǎn)60臺。已知生產(chǎn)這些家電產(chǎn)品每臺所需工時和每臺產(chǎn)值如下表： 問每周應(yīng)生產(chǎn)空調(diào)器、彩電、冰箱各多少臺，才能使產(chǎn)值最高？最高產(chǎn)值是多少(以千元為單位)？ (1997，第十二屆江蘇省初中數(shù)學(xué)競賽) 解：設(shè)每周生產(chǎn)空調(diào)器、彩電、冰箱分別為x臺、y臺、z臺，每周產(chǎn)值為f元，則 f=4x+3y+2z. 其中x、y、z滿足 由①、②得y=360—3x，z=2x. 則由 得30≤x≤120. 故f=3(x+y+z)+x—z=1080—x. 當(dāng)x=30時，fmax=1080—30=1050. 從而，y=270，z=60. 即每周生產(chǎn)空調(diào)器30臺，彩電270臺，冰箱60臺，才能使產(chǎn)值最高，最高產(chǎn)值為1050千元。 二、運用圖表作業(yè)解題　　　　　　　　　　　　　　　　　　　　　　　 　例2A市、B市和C市分別有某種機器10臺、10臺和8臺�，F(xiàn)在決定把這些機器支援給D市18臺、E市10臺。已知從A市調(diào)運一臺機器到D市、E市的運費分別為200元和800元；從B市調(diào)運一臺機器到D市、E市的運費分別為300元和700元；從C市調(diào)運一臺機器到D市、E市的運費分別為400元和500元。 ⑴設(shè)從A市、B市各調(diào)x臺機器到D市,當(dāng)28臺機器全部調(diào)運完畢后,求總運費W(元)關(guān)于x(臺)的函數(shù)式,并求W的最小值和最大值； ⑵設(shè)從A市調(diào)x臺到D市，B市調(diào)y臺到D市，當(dāng)28臺機器全部調(diào)運完畢后，用x、y表示總運費W(元)，并求W的最小值和最大值。 (1998，全國初中數(shù)學(xué)競賽) 解：⑴⑵這兩問都可以運用數(shù)量關(guān)系解題，具體解法參見《中等數(shù)學(xué)》1998年第3期第34頁或1999年第4期第3頁文。 下面以第⑵問為例說明運用圖表作業(yè)解題。 ⑵(表上作業(yè)法) 由題意，易得W(x，y)=17200—500x—300y. Ⅰ.求最小總運費Wmin. 表中對于D市、E市可供貨的A、B、C三地進行比較，逐次選取較小運費地，盡可能的調(diào)運，得調(diào)運方案如表1所示： 即當(dāng)x=10，y=8時，最小總運費Wmin=9800(元)。 Ⅱ.求最大總運費Wmax. 類似地，可得調(diào)運方案如表2所示： 即當(dāng)x=0，y=10時，最大總運費Wmax=14200(元)。 (圖上作業(yè)法) 由題意，易得W(x，y)=17200—500x—300y. Ⅰ.求最小總運費Wmin. 圖中所標運費可以看作是單位運量。供量用正數(shù)表示，需量則用負數(shù)表示，對于D市、E市可供貨的A、B、C三地進行比較，逐次選取單位運量較小的，盡可能的調(diào)運，得調(diào)運方案如圖1所示： 即當(dāng)x=10，y=8時，最小總運費Wmin=9800(元)。 Ⅱ.求最大總運費Wmax. 類似地，可得調(diào)運方案如圖2所示： 即當(dāng)x=0，y=10時，最大總運費Wmax=14200(元)。 三、運用圖象性質(zhì)解題　　　　　　　　　　　　　　　　　　　　　　　　 　例3某工廠制造A、B兩種產(chǎn)品，制造產(chǎn)品A每噸需用煤9噸，電力4千瓦，3個工作日；制造產(chǎn)品B每噸需用煤5噸，電力5千瓦，10個工作日。已知制造產(chǎn)品A和B每噸分別獲利7千元和12千元，現(xiàn)在該廠由于條件限制，只有煤360噸，電力200千瓦，工作日300個可以利用，問A、B兩種產(chǎn)品各應(yīng)生產(chǎn)多少噸才能獲利最大？最大利潤是多少？ 解：設(shè)A、B兩種產(chǎn)品分別生產(chǎn)x噸、y噸，利潤為f千元，則 f=7x+12y. 其中x、y滿足 如圖3所示，陰影部分即為這個線性規(guī)劃問題的可行區(qū)域。 ∵—4/5<—7/12<—3/10， ∴平行直線系f=7x+12y過點A(20，24)即當(dāng)x=20，y=24時，fmax=7×20+12×24=140+288=428(千元)。 即產(chǎn)品A生產(chǎn)20噸，產(chǎn)品B生產(chǎn)24噸，獲利最大，最大利潤為428千元。 四、運用枚舉驗證解題　　　　　　　　　　　　　　　　　　　　　　　　 　例4某人有樓房一幢，室內(nèi)面積共180m2，擬分隔成兩類房間作為旅游客房。大房間每間面積為18m2，可住游客5名，每名游客每天住宿費為40元；小房間每間面積為15m2，可住游客3名，每名游客每天住宿費為50元；裝修大房間每間需1000元，裝修小房間每間需600元。如果他只能籌款8000元用于裝修，且游客能住滿客房，他應(yīng)隔出大房間和小房間各多少間，能獲得最大收益？最大收益是多少？ 解：設(shè)隔出大、小房間分別為x間、y間，收益為f元，則 f=200x+150y. 其中x、y滿足 如圖4所示，由圖解法易得f=200x+150y過點A(23/7，63/7)時，目標函數(shù)f取得最大值。 但x、y必須是整數(shù)，還需在可行區(qū)域內(nèi)找出使目標函數(shù)f取得最大值的整點。 顯然目標函數(shù)f取得最大值的整點一定是分布在可行區(qū)域的右上側(cè)，則利用枚舉法即可求出整點最優(yōu)解。 這些整點有：(0，12)，(1，10)，(2，9)，(3，8)，(4，6)，(5，5)，(6，3)，(7，1)，(8，0)，分別代入f=200x+150y，逐一驗證，可得取整點(0，12)或(3，8)時，fmax=200×0+150×12=200×3+150×8=1800(元)。 所以要獲得最大收益，有兩種方案： Ⅰ.只隔出小房間12間； Ⅱ.隔出大房間3間，小房間8間。 最大收益為1800元。 　 練 習(xí) 題   1.20個農(nóng)場職工種50公頃田地，這些地可以種蔬菜、棉花或水稻，如果種這些農(nóng)作物每公頃所需的職工和預(yù)計的產(chǎn)值如下： 問怎樣安排，才能使每公頃地都種上作物，所有職工都工作，而且農(nóng)作物的預(yù)計總產(chǎn)值達到最高？最高預(yù)計總產(chǎn)值是多少？ 2.今年甲、乙兩礦生產(chǎn)相同的礦石，甲、乙每月的產(chǎn)量分別為10萬噸和8萬噸；又有A、B兩工廠每月分別需要礦石6萬噸和12萬噸。已知甲、乙與A、B的距離由圖5標出(單位：千米)，問怎樣調(diào)運才能使總運輸量(單位：萬噸·千米)最小？最小總運輸量是多少？怎樣調(diào)運總運輸量最大？最大總運輸量是多少？ 3.某公司在A、B兩地分別有庫存機器16臺、12臺，現(xiàn)要運往甲、乙兩地，其中甲地15臺，乙地13臺。已知從A地運一臺機器到甲地的運費為500元，到乙地的運費為400元；從B地運一臺機器到甲地的運費為300元，到乙地的運費為600元。問應(yīng)設(shè)計怎樣的調(diào)運方案，才能使這些機器的總運費最省？此時總運費是多少？ 4.甲、乙兩個糧庫要向A、B兩鎮(zhèn)運送大米，已知甲庫可調(diào)出100噸大米，乙?guī)炜烧{(diào)出80噸大米，A鎮(zhèn)需70噸大米，B鎮(zhèn)需110噸大米。兩庫到兩鎮(zhèn)的路程和運費如下表： 　 路程(千米) 運費(元/噸·千米) 甲庫 乙?guī)?/p> 甲庫 乙?guī)?/p> A鎮(zhèn) 20 15 12 12 B鎮(zhèn) 25 20 10 8 問：⑴這兩個糧庫各運往A、B兩鎮(zhèn)多少噸大米，才能使總運費最��？此時總運費是多少？ ⑵最不合理的調(diào)運方案是什么？它使國家造成不該有的損失是多少？ 5.兩個電腦倉庫供應(yīng)三所學(xué)校電腦，甲倉庫有12臺，乙倉庫有20臺；A校需9臺，B校需15臺，C校需8臺。已知甲倉庫到A、B、C三校的距離依次為10公里、5公里、6公里；乙倉庫到A、B、C三校的距離依次為4公里、8公里、15公里。若每臺每公里的運費為常數(shù)a元，則甲倉庫供應(yīng)給A校、B校、C校各多少臺，使總運輸費用最�。� (1998，上海市初中數(shù)學(xué)競賽) 6.某兩個煤廠A1、A2每月進煤數(shù)量分別為60噸和100噸，聯(lián)合供應(yīng)3個居民區(qū)B1、B2、B3.3個居民區(qū)每月對煤的需求量依次分別為50噸、70噸、40噸，煤廠A1離3個居民區(qū)B1、B2、B3的距離依次分別為10千米、5千米、6千米，煤廠A2離3個居民區(qū)B1、B2、B3的距離依次分別為4千米、8千米、12千米。問如何分配供煤量使得運輸量(單位：噸·千米)達到最�。孔钚∵\輸量是多少? 7.某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入分別為3、2千元/件。甲、乙產(chǎn)品都要在A、B兩種設(shè)備上加工，所需工時甲在A、B兩種設(shè)備上分別為1、2臺時/件，乙在A、B設(shè)備上分別為2、1臺時/件。A、B設(shè)備每月有效可使用臺時數(shù)分別為400、500。如何安排生產(chǎn)，使產(chǎn)品銷售總收入最大？最大總收入是多少? (1999，上海市第八屆中學(xué)生數(shù)學(xué)知識應(yīng)用競賽初賽) 8.某工廠在計劃內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)每件產(chǎn)品所需機時、工時、獲利情況如下表，在不超過總機時100和總工時120的條件下，應(yīng)如何安排生產(chǎn)使獲利最大？最大利潤是多少？   機時 工時 獲利(千元) Ⅰ 2 4 6 Ⅱ 3 2 4 9.投資生產(chǎn)A產(chǎn)品時，每生產(chǎn)一百噸需資金200萬元，需場地200m2，可獲利潤300萬元；投資生產(chǎn)B產(chǎn)品時，每生產(chǎn)一百米需要資金300萬元，需要場地100m2，可獲利潤200萬元，現(xiàn)某單位可使用資金1400萬元，場地900m2，問應(yīng)作怎樣的組合投資，可使所獲利潤最多？最大利潤是多少? (1998，上海市第七屆中學(xué)生數(shù)學(xué)知識應(yīng)用競賽初賽) 10.某鋼廠用A原料2噸和B原料4噸可產(chǎn)出1噸甲種鋼管；用A原料5噸和B原料3噸可產(chǎn)出1噸乙種鋼管。這兩種鋼管在北京、上海、廣州三地銷售所得單位利潤（單位：萬元/噸）如下表所示：   銷售甲種鋼管的單位利潤 （萬元/噸） 銷售乙種鋼管的單位利潤 （萬元/噸） 北京 2 6 上海 3 4 廣州 4 2 現(xiàn)根據(jù)市場供求信息：A、B原料的周供應(yīng)量分別是10噸、12噸；每周甲種鋼管生產(chǎn)不能超過2.5噸，乙種鋼管生產(chǎn)不能超過1.5噸，且只能將全部鋼管銷往同一地方。問這兩種鋼管分別生產(chǎn)多少噸，銷往何地，才能使一周的總利潤最大？最大總利潤是多少？ (《中等數(shù)學(xué)》1999年第3期，數(shù)學(xué)奧林匹克初中訓(xùn)練題38) 11.某運輸公司有7輛載重量為6噸的A型卡車與4輛載重量為10噸的B型卡車，有9名駕駛員，在建筑某段高速公路中，此公司承包了每天至少搬運360噸瀝青的任務(wù)，已知每輛卡車每天往返的次數(shù)為A型車8次，B型車6次，每輛卡車每天往返的成本費為A型車160元，B型車252元，每天派出A型車與B型車各多少輛，公司所花的成本費最低？最低成本費是多少? 答案與提示   1.種蔬菜30公頃，不種棉花，種水稻20公頃，預(yù)計總產(chǎn)值最高，最高預(yù)計總產(chǎn)值為450000元。 2.⑴甲礦不運給A廠，運給B廠10萬噸；乙礦運給A廠6萬噸，運給B廠2萬噸時，總運輸量最小，最小總運輸量為164萬噸·千米。 ⑵甲礦運給A廠6萬噸，運給B廠4萬噸；乙礦不運給A廠，運給B廠8萬噸時，總運輸量最大，最大總運輸量為176萬噸·千米。 3.從A地調(diào)往甲地3臺，乙地13臺；從B地調(diào)往甲地12臺，乙地0臺，可使總運費最省，此時總運費為10300元。 4.⑴甲庫運往A鎮(zhèn)70噸，運往B鎮(zhèn)30噸；乙?guī)觳贿\往A鎮(zhèn)，運往B鎮(zhèn)80噸時，總運費最省，總運費為37100元； ⑵甲庫不運往A鎮(zhèn)，運往B鎮(zhèn)100噸；乙?guī)爝\往A鎮(zhèn)70噸，運往B鎮(zhèn)10噸時最不合理，此時總運費最多，總運費為39200元，使國家造成不該有的損失為2100元。 5.甲倉庫供應(yīng)給A校0臺，B校4臺，C校8臺。 6.A1不運往B1，運往B220噸，運往B340噸；A2運往B150噸，運往B250噸，不運往B3，可使運輸量最小，最小運輸量為940噸·千米。 7.生產(chǎn)甲種產(chǎn)品200件，乙種產(chǎn)品100件，使產(chǎn)品銷售收入最大，最大銷售總收入為800千元。 8.生產(chǎn)第Ⅰ種產(chǎn)品20件，第Ⅱ種產(chǎn)品20件獲利最大，最大利潤是200千元。 9.A產(chǎn)品生產(chǎn)13/4百噸，B產(chǎn)品生產(chǎn)3/2百米時，可使所獲利潤最多，最大利潤是1475萬元。 10.甲、乙兩種鋼管分別生產(chǎn)5/4噸、3/2噸且全部銷往北京，可使一周的總利潤最大，最大總利潤是11.5萬元。 11.每天派出A型車5輛，B型車2輛，公司所花的成本費最低，最低成本費是1304元。