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

2009-08-31 12:15:57網(wǎng)絡(luò)來(lái)源

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

　近年來(lái)，各級(jí)各類(lèi)數(shù)學(xué)競(jìng)賽中頻頻出現(xiàn)線性規(guī)劃問(wèn)題。所謂線性規(guī)劃，是指求線性函數(shù)在線性(不等式或等式)約束下達(dá)最(小或大)值的問(wèn)題。線性規(guī)劃廣泛應(yīng)用于工農(nóng)業(yè)、軍事、交通運(yùn)輸、決策管理與規(guī)劃、科學(xué)實(shí)驗(yàn)等領(lǐng)域。本文擬通過(guò)競(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)值如下表：

問(wè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í)，f_max=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)賽)

解：⑴⑵這兩問(wèn)都可以運(yùn)用數(shù)量關(guān)系解題，具體解法參見(jiàn)《中等數(shù)學(xué)》1998年第3期第34頁(yè)或1999年第4期第3頁(yè)文。

下面以第⑵問(wèn)為例說(shuō)明運(yùn)用圖表作業(yè)解題。

⑵(表上作業(yè)法)

由題意，易得W(x，y)=17200—500x—300y.

Ⅰ.求最小總運(yùn)費(fèi)W_min.

表中對(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)W_min=9800(元)。

Ⅱ.求最大總運(yùn)費(fèi)W_max.

類(lèi)似地，可得調(diào)運(yùn)方案如表2所示：

即當(dāng)x=0，y=10時(shí)，最大總運(yùn)費(fèi)W_max=14200(元)。

(圖上作業(yè)法)

由題意，易得W(x，y)=17200—500x—300y.

Ⅰ.求最小總運(yùn)費(fèi)W_min.

圖中所標(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)W_min=9800(元)。

Ⅱ.求最大總運(yùn)費(fèi)W_max.

類(lèi)似地，可得調(diào)運(yùn)方案如圖2所示：

即當(dāng)x=0，y=10時(shí)，最大總運(yùn)費(fèi)W_max=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è)可以利用，問(wèn)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ī)劃問(wèn)題的可行區(qū)域。

∵—4/5<—7/12<—3/10，

∴平行直線系f=7x+12y過(guò)點(diǎn)A(20，24)即當(dāng)x=20，y=24時(shí)，f_max=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)面積共180m²，擬分隔成兩類(lèi)房間作為旅游客房。大房間每間面積為18m²，可住游客5名，每名游客每天住宿費(fèi)為40元；小房間每間面積為15m²，可住游客3名，每名游客每天住宿費(fèi)為50元；裝修大房間每間需1000元，裝修小房間每間需600元。如果他只能籌款8000元用于裝修，且游客能住滿客房，他應(yīng)隔出大房間和小房間各多少間，能獲得最大收益？最大收益是多少？

解：設(shè)隔出大、小房間分別為x間、y間，收益為f元，則

f=200x+150y.

其中x、y滿足

如圖4所示，由圖解法易得f=200x+150y過(guò)點(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í)，f_max=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)值如下：

問(wè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)出(單位：千米)，問(wèn)怎樣調(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元。問(wèn)應(yīng)設(shè)計(jì)怎樣的調(diào)運(yùn)方案，才能使這些機(jī)器的總運(yùn)費(fèi)最�。看藭r(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

問(wèn)：⑴這兩個(gè)糧庫(kù)各運(yùn)往A、B兩鎮(zhèn)多少噸大米，才能使總運(yùn)費(fèi)最��？此時(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è)煤廠A₁、A₂每月進(jìn)煤數(shù)量分別為60噸和100噸，聯(lián)合供應(yīng)3個(gè)居民區(qū)B₁、B₂、B₃.3個(gè)居民區(qū)每月對(duì)煤的需求量依次分別為50噸、70噸、40噸，煤廠A₁離3個(gè)居民區(qū)B₁、B₂、B₃的距離依次分別為10千米、5千米、6千米，煤廠A₂離3個(gè)居民區(qū)B₁、B₂、B₃的距離依次分別為4千米、8千米、12千米。問(wèn)如何分配供煤量使得運(yùn)輸量(單位：噸·千米)達(dá)到最�。孔钚∵\(yùn)輸量是多少?

7.某廠擬生產(chǎn)甲、乙兩種適銷(xiāo)產(chǎn)品，每件銷(xiāo)售收入分別為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)品銷(xiāo)售總收入最大？最大總收入是多少?

(1999，上海市第八屆中學(xué)生數(shù)學(xué)知識(shí)應(yīng)用競(jìng)賽初賽)

8.某工廠在計(jì)劃內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)每件產(chǎn)品所需機(jī)時(shí)、工時(shí)、獲利情況如下表，在不超過(guò)總機(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)地200m²，可獲利潤(rùn)300萬(wàn)元；投資生產(chǎn)B產(chǎn)品時(shí)，每生產(chǎn)一百米需要資金300萬(wàn)元，需要場(chǎng)地100m²，可獲利潤(rùn)200萬(wàn)元，現(xiàn)某單位可使用資金1400萬(wàn)元，場(chǎng)地900m²，問(wèn)應(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噸乙種鋼管。這兩種鋼管在北京、上海、廣州三地銷(xiāo)售所得單位利潤(rùn)（單位：萬(wàn)元/噸）如下表所示：

銷(xiāo)售甲種鋼管的單位利潤(rùn)
（萬(wàn)元/噸）

銷(xiāo)售乙種鋼管的單位利潤(rùn)
（萬(wàn)元/噸）

北京

2

6

上海

3

4

廣州

4

2

現(xiàn)根據(jù)市場(chǎng)供求信息：A、B原料的周供應(yīng)量分別是10噸、12噸；每周甲種鋼管生產(chǎn)不能超過(guò)2.5噸，乙種鋼管生產(chǎn)不能超過(guò)1.5噸，且只能將全部鋼管銷(xiāo)往同一地方。問(wèn)這兩種鋼管分別生產(chǎn)多少噸，銷(xiāo)往何地，才能使一周的總利潤(rùn)最大？最大總利潤(rùn)是多少？

(《中等數(shù)學(xué)》1999年第3期，數(shù)學(xué)奧林匹克初中訓(xùn)練題38)

11.某運(yùn)輸公司有7輛載重量為6噸的A型卡車(chē)與4輛載重量為10噸的B型卡車(chē)，有9名駕駛員，在建筑某段高速公路中，此公司承包了每天至少搬運(yùn)360噸瀝青的任務(wù)，已知每輛卡車(chē)每天往返的次數(shù)為A型車(chē)8次，B型車(chē)6次，每輛卡車(chē)每天往返的成本費(fèi)為A型車(chē)160元，B型車(chē)252元，每天派出A型車(chē)與B型車(chē)各多少輛，公司所花的成本費(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.A₁不運(yùn)往B₁，運(yùn)往B₂20噸，運(yùn)往B₃40噸；A₂運(yùn)往B₁50噸，運(yùn)往B₂50噸，不運(yùn)往B₃，可使運(yùn)輸量最小，最小運(yùn)輸量為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件獲利最大，最大利潤(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噸且全部銷(xiāo)往北京，可使一周的總利潤(rùn)最大，最大總利潤(rùn)是11.5萬(wàn)元。

11.每天派出A型車(chē)5輛，B型車(chē)2輛，公司所花的成本費(fèi)最低，最低成本費(fèi)是1304元。