簡單的線性規劃問題

簡單的線性規劃問題

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