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

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

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