簡(jiǎn)單的線(xiàn)性規劃問(wèn)題

簡(jiǎn)單的線(xiàn)性規劃問(wèn)題

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