一 最優(yōu)化問題

1、第一講統(tǒng)籌與優(yōu)化戰(zhàn)國時期，齊威王與將軍田忌賽馬。規(guī)定從自己的上等馬、中等馬、下等馬中各選一匹來賽。如果按 同等馬相比，田忌的馬都不如齊威王的馬，看來田忌 要連輸三局了。后來，田忌請教了當時著名軍事家孫 臏，孫臏向田忌獻策，設計了三種馬出場的先后順序:第一場：用下等馬跟齊王的上等馬比，田忌輸了 一場；第二場：用上等馬跟齊王的中等馬比，田忌贏了 一場；第三場：用中等馬跟齊王的下等馬比，田忌又贏了一場。結果，田忌以二比一獲勝，這就是歷史上有名的“田 忌賽馬”的故事。故事中巧妙地安排上、中、下三種 馬出場參賽的順序，就是一個“最優(yōu)化”問題，這也 是著名數(shù)學家華羅庚先生生前積極推廣和普及的“統(tǒng) 籌方法”

2、和“優(yōu)選法”。通常我們所碰到的最優(yōu)化問題，就是在某些條件 的限制下，通過科學地規(guī)劃安排，合理地設計，找到 一種最佳方案，使所用的時間最少、或所耗的費用最 少、或所需的人力最少。在眾多方案中尋求一種最 合理、最科學的方案，這就是統(tǒng)籌與優(yōu)化。【例1】在一個漆黑的夜晚，A、B、C、D四個人 結伴同行，途中要經(jīng)過一座木橋，這座木橋最多能承 受兩個人的重量，如果單獨過去A要1分鐘，B要3 分鐘,C要8分鐘，D要12分鐘，而此時四個人只有 一只手電簡。請同學們幫助他們設計一種最佳的過橋 方法，使他們能在最短時間內(nèi)通過這座橋？思路點撥：由于這座橋每次只能通過兩個人，且 只有一只手電簡。所以，必須兩人同時過去

3、.然后讓 其中一人回來送手電筒。四個人要用最短的時問通過 這座橋應從以下兩方面考慮：一是返回送手電筒的人 用的時間越少越好，二是讓用的時間最多的兩個人一 起過橋。解 方案一:讓兩個用時較多的C、D 一起過橋。那 么第一次過橋的人應是A和B，用時3分鐘。然后由 A用1分鐘時問把手電筒送回來，交給C、D,這兩個 人過橋時間為12分鐘。再由B用3分鐘時間送回手 電。再由A、B同時過橋用時3分鐘，返回送手電簡 用時1分鐘。全部通過所用時問為：3+1+12+3+3 =22（分 ）.方案二:讓用時最少的A去送其余三人。A先送D 過去，用時12分鐘，然后用1分鐘回來，A再送C 過去，用時8分鐘，然后用1分鐘

4、回來；A再和B過去，用時3分鐘。全部通過所用時問為:12+1+8+1+3=25（分 ）.通過比較知，第一種方案用時較少。答：他們五人最短用22分鐘通過這座木橋。1!【例2】媽媽讓小明給客人燒水沏茶，洗開水壺 用1分鐘，燒開水要用15分鐘，洗茶壺要1分鐘， 洗茶杯要1分鐘，放茶葉要2分鐘。小明算了一下， 完成這些工作要花20分鐘。為了使客人早喝上茶， 按照你認為最合理的安排，多少分鐘就能沏茶了？1!思路點撥:題要做的事中，花時間最長的是燒開水， 要15分鐘。所以不管怎么安排，至少要15分鐘才能沏上茶。但在燒開水 的同時，可以做洗茶壺、洗茶杯、放茶葉這三件事情.解小明先洗開水壺用1分鐘，接著燒開水

5、用15分鐘，在等待水開的過程中，同時洗茶壺、茶杯、拿茶 葉，水開7就沏茶，這樣用的時間最省，最省時間為1+15=16 （分鐘）。1!具體程序如下圖:燒開水一沏茶洗水毒分鐘）（1分鐘）洗茶壺、洗茶杯、拿茶葉（1分鐘）（1分鐘）（2分鐘）圖1 1說明：這個例子告訴我們，在做一件事時，經(jīng)常會 遇到如何統(tǒng)籌兼顧，科學安排，以加快工作進度，提 高工作效率的問題。為了省時間、提高效率，能同時 去做的事應盡量同時去做?！纠?】車間里有5臺機床同時出了故障，只有一個修理工，從第1臺到第5臺的修復，時間依次為 濟損失5萬元。那么應怎樣安排修復順序，使經(jīng)濟損 失最?。孔钚∈嵌嗌僭?？15、 8、 29、 7、10分

6、鐘。每臺機床停產(chǎn)一分鐘造成經(jīng)思路點撥：5臺機床總的修復與等待的時間越少， 經(jīng)濟損失越小，陪等修復時間長的機床越少越有利， 因此，讓修復時間長的陪等修復時間短的。解總的等待與修復時間為：7X 5+8X4+10X3 + 15X2+29X 1=156 （分鐘）損失5X156=780 （萬元）答：修復順序為第4臺、第2臺、第5臺、第1 臺，第3臺，可使經(jīng)濟損失最少，此時最少的損失為 780萬元。說明：例3是一個比較簡單的排隊問題，為了使 所用時間最少，在規(guī)劃排隊先后順序時，應盡量讓時 間用的少的排在前面。【例4】在一條公路上，每隔100千米有一個倉 庫，共有5個倉庫。1號倉庫有10噸貨物，2號倉庫 有

7、20噸貨物，5號倉庫有40噸貨物，其余兩個倉庫 是空的，現(xiàn)在想把所有的貨物集中存放在一個倉庫 里，如果每噸貨物運輸1千米需要0.5元運輸費，那 么最少需要多少運費才行？-1 | 2 | 3 | 4 | 10噸 20噸40噸圖1 3思路點撥：要使運費最少，必須綜合考慮兩個因 素：（1）運走的貨物盡可能少；（2）要運貨物運輸?shù)?路程盡可能短。一共有貨物10+20+40=70 （噸），先比 較兩端的貨物，10 40，可以先把1號倉庫中的10 噸運往2號倉庫，這樣2號倉庫就有了 30噸，30 40，所以應該把2號的貨物運往5號倉庫。解 需要把貨物都運往五號倉庫，運費為：0.5X （10X4X100+2

8、0X3X 100） =5000 （元）想一想：若一號倉庫有30噸貨物，二號倉庫有 20噸貨物，其他倉庫的貨物不變，那么應該運往哪個 倉庫集中呢說明：這是一個廠址設置問題，常見解決方法為:（1）如果只有兩個原料產(chǎn)地，它們有一條公路相 連，要在公路上找一處（包括兩個產(chǎn)地在內(nèi)）設工廠， 使原料運輸總量最少：如果兩個原料產(chǎn)地產(chǎn)量一樣，則工廠設在公路 的任一點（包括端點）都行。如果兩個原料產(chǎn)地產(chǎn)量不相等，則工廠應設在l=J|三目產(chǎn)量較大的原料產(chǎn)地，即把原料少的產(chǎn)地的原料往產(chǎn) 量大的原料產(chǎn)地運，這叫“小往大靠”。1=（2 ）如果不止兩個原料產(chǎn)地，它們分布在一個道 路設有圈的交通圖上（圖1-2）。先計算各原

9、料產(chǎn)地的原料總和，然后看各原料產(chǎn)地的產(chǎn)量， 若小于總和的一半，則把它運往前一站， 這叫“抓各端，小半進一站”。反復運用 這一原理，最后看原料都集中何處，這 處便是廠址，它能使原料運輸總量最少。【例5】甲、乙兩廠生產(chǎn)同一型號的西服，甲廠每 月用16天的時間生產(chǎn)上衣，用14天的時間生產(chǎn)褲子， 共生產(chǎn)896套西服；乙廠每月用12天的時間生產(chǎn)上 衣，用18天的時間生產(chǎn)褲子，共生產(chǎn)1440套西服。 現(xiàn)在兩個工廠合并，問每月（按30天計算）最多能 生產(chǎn)多少套西服？思路點撥：安排生產(chǎn)時要發(fā)揮每個廠子的生產(chǎn)優(yōu) 勢，讓善于生產(chǎn)上衣的去生產(chǎn)上衣，讓善于生產(chǎn)褲子 的去生產(chǎn)褲子。甲廠每天生產(chǎn)上衣：89616=56（件

10、）， 褲子：896! 14=64 （條）；乙廠每天生產(chǎn)上衣：1440 4-12=120 （件），褲子：1440! 18=80 （條）?？芍?， 甲廠生產(chǎn)褲子快，乙廠生產(chǎn)上衣快。讓甲廠專門生產(chǎn) 褲子，乙廠先生產(chǎn)上衣與之配套，然后再獨立生產(chǎn)。解 甲廠一個月可生產(chǎn)褲子：896 -14 X 30=1920 （條）乙廠先生產(chǎn)上衣1920件與之配套，需1920 -（1440+12 ） =16 （天）乙廠在剩下的30-16=14 （天）中，可生產(chǎn)（1440 + 30）X 14=672 （套）兩廠共生產(chǎn)：1920+672=2592 （套）答每月最多能生產(chǎn)2592套西服。I=J說明：科學安排要堅持兩個原則：一是效

11、率優(yōu)先， 即讓每個車間生產(chǎn)比另一個車間產(chǎn)量高的那種產(chǎn)品； 二是成套生產(chǎn)，生產(chǎn)的上衣和褲子必須完全配套。的裝卸工太多會造 部分工人跟車。那么 田人固定，才能使裝【例6】某公司運輸隊有2輛汽車，為4個工廠 作循環(huán)運輸，每個工廠需配備的裝卸工如圖1-6所示。 如果每個工廠固定 成人力浪費，可以讓 派多少人跟車，怎樣 卸工的總人數(shù)最少？思路點撥：先假定所有的裝卸工都在各點等車， 我們從每一個點抽出一名裝卸工（共抽4人），每輛 車上安排一人（共2人），則汽車到各點的裝卸工的 人數(shù)未變，但裝卸工的人數(shù)可節(jié)約2人。裝卸工人數(shù)最少的工廠是4人，這樣抽了 4次后， 各點人數(shù)為A（4人）、B（2人）、C（0人）、

12、D（1人）, 此時人數(shù)不為0的點還有3個：A、B、D，多于車輛 數(shù)2,可以再從這三個點各抽1人，每輛車上再多派 1人，又可節(jié)約1人。若再繼續(xù)抽調(diào)調(diào)整的話，裝卸工人總數(shù)不會再減少， 這時裝卸工的總數(shù)是：5X2+3+1=14 （人）其中每輛車上5人。每個工廠的 人數(shù)分別為:A （3人）、B （1人）、C （0人）、D （0人） 想一想：若車隊派出3輛車，怎樣安排才能使裝 卸工的人數(shù)最少？說明：這類題我們可以采用“逐步調(diào)整法”來驗 證這一調(diào)整方案是否最優(yōu)的。注意，只有當人數(shù)不為 0的工廠的數(shù)量不大于車的數(shù)量時，才停止抽調(diào)。【例7】倉庫里存有一批8米長的鋼筋，現(xiàn)在要截 出3米長的毛坯40根，2米長的毛

13、坯40根，試設計 最省料的下料方案。問要幾根原材料？思路點撥：最合理下料方案就是8米長的鋼筋截取后所余下的廢料最少?？梢园岩桓?米長的鋼筋截 成兩種毛坯的不同方法一一枚舉，如下表所示。然后 把不同方法綜合起來，便達到題目的要求，構成一個 下料方案。毛云數(shù)3米2102米124殘料010解要使原材料最省，應該盡量不用有殘料的方 案二。從表上看出，要截3米毛坯40根，如果用方 案一截20根原材料，這時得到了 3米毛坯40根，2 米毛坯20根，再用方法三截5根原材料，可得2米 毛坯20根，合起來正好滿足題目要求。說明：一般來說，一定長度的材料要截取幾種毛 坯的下料問題，常常先通過枚舉法列出幾種截取方

14、法，通過分析、比較，看哪幾種方法殘料比較少，然 后得出最佳的下料方案?！纠?】北京和上海同時制成計算機若干臺，北京i=可調(diào)運外地10臺，上海可調(diào)運 外地4臺，現(xiàn)決定給重慶8臺， 漢口 6臺，若每臺計算機的運 費如下表，怎樣調(diào)運使運費最 省？r=i思路點撥：先作圖（見圖1-7），使題中的條件集 中在圖上反映出來，便于分析。根據(jù)“就近分配”的 原則，先就近分配，然后進行適當調(diào)整。假如上海的 4臺全發(fā)運漢口，北京10臺發(fā)重慶8臺，發(fā)漢口 2臺, 這時總運費為 800 X 8+400 X 2+300 X 4=8400 （元）。這 時我們設想，北京一臺改發(fā)漢口，節(jié)省運費400元， 上海發(fā)漢口改為發(fā)重慶，

15、經(jīng)費增加200元，合計節(jié)省 運費200元，于是將上海4臺全發(fā)往重慶，北京發(fā)重 慶的4臺改發(fā)漢口，一共可節(jié)省200X4=800 （元） 這時總運費為8400-800=7600元。解上海4臺發(fā)往重慶，北京發(fā)4臺至重慶，6臺 至漢口，總運費為：500 X 4+800 X 4+400 X 6=7600（元）答：上海4臺發(fā)往重慶，北京發(fā)4臺至重慶，6臺 至漢口。說明：在確定最佳方案的過程中，要注意調(diào)整、 比較的方法，本題中應該先比較一下需要量多運費也 多的地方如何運最省。練習一用一只平底鍋煎餅，每次只能放2個餅，煎一個 需要2分鐘（正、反面各1分鐘）。問：（1）煎三個 餅至少需要幾分鐘？怎樣煎？（2）煎

16、n個餅（nN3） 至少需要幾分鐘？煎三個餅需要3分鐘.方法:兩個餅先煎一面，1分 鐘后，拿下一個餅,另一個翻面并放上第三個餅，再煎 1分鐘，一個餅已煎好,把拿下去的餅及第三個餅都翻 一面再煎1分鐘就都煎好了.煎n個餅用n分鐘，當n為奇數(shù)時，先用上法煎 三個餅，用去3分.余下偶數(shù)個餅，每兩個餅用2分 鐘煎。1!1!小明騎在牛背上趕牛過河，共有甲、乙、丙、丁 4 頭牛。甲牛過河需2分鐘。乙牛過河需3分鐘，丙牛 過河需6分鐘，丁牛過河需7分鐘。每次只能趕兩頭 牛過河，那么小明要把這4頭牛都趕到對岸，最少要 用幾分鐘？18分鐘提示：甲、乙先過，甲回來，丙、丁 起過，乙回來，最后甲、乙過。1!小明早晨起

17、來淘米要2分鐘，插上開關用電飯鍋燒 飯要18分鐘，背外語單詞要12分鐘，刷牙洗臉要3分鐘，吃早飯要8分鐘，小明經(jīng)過合理安排，起床后多少分鐘就能上學了？他是怎樣合理安排的?28分鐘，安排順序如圖:燒飯分鐘2W吃飯8分鐘上學某加油站能夠?qū)奢v車同時進行加油，現(xiàn)在有6 輛車同時來到加油站加油，各輛車加油所需時間分別為：A車7分鐘，B車5分鐘，C車4分鐘，D車10分鐘，E車3分鐘，F(xiàn)車2分鐘,問：加油站怎樣安排加油順序，才能使這6輛車加油總共需要的時間最 短？這6輛車分兩組加油，順序是F、C、A和E、B、D 一共需要的時間是：3 X (2+3)+2 X (44-5) + (7+10)=50(分),也可

18、以分為 F、B、A 和 E、C、 D兩組，并按此順序加油總時間也是50分.李鄉(xiāng)長下鄉(xiāng)召開甲、乙、丙、丁四個村的干部會議,這些村都相距4千米，如圖1-8。參加會議的人數(shù)分別為7人、6人、2人、8人，請你想一想，李鄉(xiāng)長在哪個村召開會議最為合理。乙處如圖，是某個城市的部分街道圖，相鄰兩個交點 之間的連線表示道路，連線旁標注的數(shù)表示該道路在 單位時間內(nèi)最多可以通過的汽車數(shù).現(xiàn)從A點向B點 發(fā)車,汽車可以分開沿不同的路線行駛,那么,在單位時間內(nèi)最多可以通過多少輛汽車?19 輛 提示：3+4+6+6=19（輛）l=J|三目l=J有284噸貨物運往“希望工程”，大卡車載重量為8 噸，小卡車載重量為4噸，它們

19、的耗油量分別為12 升和7升，用大小車各多少輛參加運輸，耗油量最少？35輛大卡車，1輛小卡車提示：大卡車每噸耗油 量少，應盡量安排大卡車工地上有手推車20輛，其中10輛從A到B運垃圾， 要60車次運完，另外10輛從C到D運磚塊，要40 車次運完。各地距離如圖所示（單位：米）。有人說 這樣的安排不合理，因為跑空車的路程可以再少些。 那么，怎樣安排才合理呢？運垃圾和運轉頭的車都不必返回，按ABCDA 的順序循環(huán)運輸，使運垃圾和運轉頭交替進行。每走 一圈空車路程由360米、300米分別縮短為90米、240 米。彩虹服裝公司的A, B兩個制衣車間，生產(chǎn)同 澈式的西服。A車間每月生產(chǎn)這種西服600套，其

20、中生產(chǎn)上衣需18天，生產(chǎn)褲子需12天。B車間每月 也可以生產(chǎn)這種西服600套，其中生產(chǎn)上衣和褲子各 需15天。如果讓兩個車間合作，則可以提高每個月 的產(chǎn)量。A, B兩個車間應怎樣合作生產(chǎn)，可以使每 月產(chǎn)量達到最大？最大月產(chǎn)量是多少套？(每月按30 天計算)1320套 提示:比較可知,A生產(chǎn)褲子的效率比B高,B生產(chǎn)上衣的效率比A高，讓B用30天時間生產(chǎn)上 衣，共生產(chǎn)上衣1200件，A生產(chǎn)褲子與之配套，用時 1200+ (600+12)= 24天，剩下6天可生產(chǎn)西服(600 + 30 ) X 6=120 (套)，因此，最大月產(chǎn)量是1200+120=1320 （套）。解放軍某部有4輛汽車，要陸續(xù)派往A、B、C、 D、E五個地方執(zhí)行循環(huán)運輸任務，各 點所需裝卸戰(zhàn)士人數(shù)如圖1-9所示。裝 卸的戰(zhàn)士可以固定在裝卸地，也可以跟 車流動，問怎樣安排才能使裝卸戰(zhàn)士人 數(shù)最少？最少要多少人？每輛車跟車4人，A、C各固定1人，B固定2人，共 需 4X4+1 X2+2=20（人） 11.倉庫內(nèi)有一批14米長的鋼筋，把它們割成3米 長的和5米長的各50根。試設計最省料的下料方案， 問最少要幾根鋼筋？最少要30根提示：割成3根3米和1根5米的鋼筋 需10根，割