第十一講簡單的統(tǒng)籌規(guī)化問題學(xué)案

1、第十一講 簡單的統(tǒng)籌規(guī)化問題最優(yōu)化概念反映了人類實踐活動中十分普遍的現(xiàn)象， 即要在盡可能節(jié)省人 力、物力和時間的前提下，努力爭取獲得在允許范圍內(nèi)的最佳效益因此，最 優(yōu)化問題成為現(xiàn)代應(yīng)用數(shù)學(xué)的一個重要研究對象， 它在生產(chǎn)、 科學(xué)研究以及日 常生活中都有廣泛的應(yīng)用 作為數(shù)學(xué)愛好者， 接觸一些簡單的實際問題， 了解 一些優(yōu)化的思想是十分有益的例1 媽媽讓小明給客人燒水沏茶洗開水壺要用 1分鐘，燒開水要用 15分 鐘洗茶壺要用 1分鐘，洗茶杯要用 1分鐘，拿茶葉要用 2 分鐘小明估算了 一下，完成這些工作要 20 分鐘為了使客人早點(diǎn)喝上茶，按你認(rèn)為最合理的 安排，多少分鐘就能沏茶了？分析 本題取自華羅

2、庚教授 1965年發(fā)表的統(tǒng)籌方法平話 燒水沏茶的情況 是：開水要燒，開水壺要洗，茶壺茶杯要洗，茶葉要取怎樣安排工作程序最 省時間呢？辦法甲：洗好開水壺，灌上涼水， 放在火上，在等待水開的時候， 洗茶杯， 拿茶葉，等水開了，沏茶喝辦法乙：先做好一切準(zhǔn)備工作，洗開水壺，洗壺杯，拿茶葉，灌水燒水， 坐等水開了沏茶喝辦法丙：洗開水壺，灌上涼水，放在火上坐待水開，開了之后急急忙忙找 茶葉，洗壺杯，沏茶喝誰都能一眼看出第一種辦法好，因為后兩種辦法都“窩了工” 開水壺不洗，不能燒開水，固為洗開水壺是燒開水的先決條件，沒開水、 沒茶葉、不洗壺杯，我們不能沏茶，因而這些又是沏茶的先決條件它們的相 互關(guān)系可以用下

3、圖的箭頭圖來顯示箭桿上的數(shù)字表示完成這一工作所需的時間， 例如表示從把水放在爐上到水 開的時間是 15分鐘從圖上可以一眼看出， 辦法甲總共要 16分鐘，而辦法乙、 丙需 20 分鐘洗壺杯、 拿茶葉沒有什么先后關(guān)系， 而且是由同一個人來做， 因此可以將 上圖合并成下圖解 先洗開水壺用 1分鐘，接著燒開水用 15 分鐘，在等待水開的過程中， 同時 洗壺杯、拿茶葉，水開了就沏茶，總共用了 16 分鐘又因為燒開水的 15分鐘 不能減少，燒水前必須用 1 分鐘洗開水壺，所以用 16 分鐘是最少的說明：本題涉及到的統(tǒng)籌方法，是生產(chǎn)、建設(shè)、工程和企業(yè)管理中合理安 排工作的一種科學(xué)方法， 它對于進(jìn)行合理調(diào)度、

4、 加快工作進(jìn)展， 提高工作效率， 保證工作質(zhì)量是十分有效的例2 用一只平底鍋煎餅， 每次能同時放兩個餅 如果煎 1個餅需要 2分鐘（假 定正、反面各需 1 分鐘），問煎 1993個餅至少需要幾分鐘？ 分析 由于 1993數(shù)目較大，直接入手不容易 我們不妨先從較小的數(shù)目來進(jìn)行 探索規(guī)律如果只煎 1 個餅，顯然需要 2 分鐘；如果煎 2 個餅，仍然需要 2 分鐘；如果煎 3 個餅，初學(xué)者看來認(rèn)為至少需要 4 分鐘：因為先煎 2個餅要 2 分鐘；再單獨(dú)煎第 3 個餅，又需要 2分，所以一共需要 4 分鐘但是，這不是 最佳方案最優(yōu)方法應(yīng)該是：首先煎第 1 號、第 2 號餅的正面用 1 分鐘；其次煎第

5、1 號餅的反面及第 3 號餅的正面又用 1 分鐘；最后煎第 2 號、第 3號餅的反面再用 1 分鐘；這樣總共只用 3分鐘就煎好 了 3 個餅解：如果煎 1993 個餅，最優(yōu)方案應(yīng)該是：煎第 1、2、3號餅用“分析”中的方法只需要 3 分鐘；煎后面 1990個餅 時，每兩個餅需要 2 分鐘，分 1990÷2=995（次）煎完，共需要 2× 995=1990 （分鐘）；這樣總共需要 3+1990=1993（分鐘）說明：通過本例可以看出，掌握優(yōu)化的思想，合理統(tǒng)籌安排操作程序，就 能夠節(jié)省時間，提高效率例 3 5 個人各拿一個水桶在自來水龍頭前等候打水，他們打水所需的時間分 別是

6、1 分鐘、 2分鐘、 3分鐘、 4分鐘和 5分鐘如果只有一個水龍頭，試問 怎樣適當(dāng)安排他們的打水順序， 才能使每個人排隊和打水時間的總和最??？并 求出最小值分析 5 個人排隊一共有 5×4×3×2×1=120 種順序，把所有情形的時間總和 都計算出來， 就太繁瑣了 憑直覺，應(yīng)該把打水時間少的人排在前面所費(fèi)的總 時間會省些考慮用“逐步調(diào)整”法來嚴(yán)格求解解：首先證明要使所費(fèi)總時間最省， 應(yīng)該把打水時間需 1 分鐘的人排在第一位 置假如第一位置的人打水時間要 a 分鐘（其中 2a5），而打水需 1 分鐘 的人排在第 b 位（其中 2 b5）我們將這兩個人位置交

7、換，其他三人位置 不變動這樣調(diào)整以后第 b 位后面的人每人排隊打水所費(fèi)的時間與調(diào)整前相 同，并且前 b個人每人打水所費(fèi)時間也未受影響， 但是第二位至第 b 位的人排 隊等候的時間都減少了（ a-1 ）分鐘，這說明調(diào)整后五個人排隊和打水時間的 總和減少了換言之，把打水需 1 分鐘的人排在第一位置所費(fèi)總時間最省其次，根據(jù)同樣道理， 再將打水需 2 分鐘的人調(diào)整到第二位置； 將打水需 3、4、5分鐘的人逐次調(diào)整到第三、四、五位所以將五人按照打水所需時間 由少到多的順序排隊， 所費(fèi)時間最省 這樣得出 5 人排隊和打水時間總和的最 小值是1×5+2×4+3×3+4×

8、;2+5×1=35（分鐘） 說明：本題涉及到排序不等式， 有興趣的讀者可參閱高年級的數(shù)學(xué)奧林匹 克教材排隊提水的問題，在其他一些場合也是會遇到的例如，有一臺機(jī)床 要加工 n 個工件，每個工件需要的加工時間不一樣， 問應(yīng)該按照什么次序加工， 才能使總的等待時間最短例4 有157噸貨物要從甲地運(yùn)往乙地，大卡車的載重量是 5噸，小卡車的載 重量是 2噸，大卡車與小卡車每車次的耗油量分別是 10公升與 5 公升問如 何選派車輛才能使運(yùn)輸耗油量最少？這時共需用油多少公升？ 解： 依題意，大卡車每噸耗油量為 10÷5=2（公升）；小卡車每噸耗油量為 5 ÷2=2.5 （公升）

9、為了節(jié)省汽油應(yīng)盡量選派大卡車運(yùn)貨，又由于157=5×31+2，因此，最優(yōu)調(diào)運(yùn)方案是：選派 31 車次大卡車及 1 車次小卡車即可將貨物 全部運(yùn)完，且這時耗油量最少，只需用油10×31+5×1=315（公升）說明：本題是 1960 年上海市數(shù)學(xué)競賽試題上述解法是最樸素的優(yōu)化思 想選派每噸耗油量較少的卡車下面用代數(shù)的知識來解題：設(shè)選派大卡車 a 車次，小卡車 b 車次，依題意：5a+2b=157，即 10a=314-4b于是總耗油量為：W=10a+5b=314=4b+5b=314+b顯然，當(dāng) b 越小時， W也越小又由 5a+2b=157易知，b最小值是 1，故 W的

10、最小值是 314+1=31（5 公升）若 取 b=0，則需派 32 車次大卡車，耗油量則需 320 公升例5 有1993名少先隊員分散在一條公路上值勤宣傳交通法規(guī)， 問完成任務(wù)后 應(yīng)該在公路的什么地點(diǎn)集合， 可以使他們從各自的宣傳崗位沿公路走到集合地 點(diǎn)的路程總和最小？分析 由于 1993 數(shù)目較大，不易解決我們先從人數(shù)較小的情況入手當(dāng)只有 2個人時，設(shè) 2人宣傳崗位分別為 A1和 A2（如上圖），顯然集合地 點(diǎn)選在 A1 點(diǎn)或 A2點(diǎn)或者 A1A2 之間的任何一個地點(diǎn)都可以因為由 A1、A2 出發(fā)的 人走過的路程總和都等于 A1A2當(dāng)有 3 個人時，則集合地點(diǎn)應(yīng)該選在 A2點(diǎn)（如右圖）因為若

11、集合地點(diǎn)選 在 A1A2之間的 B點(diǎn)，那時 3 個人所走的路程總和是A1B+A2B+A3B=（ A1B+A3B）+A2B=A1A3+A2B；若集合地點(diǎn)選在 A2A3之間的 C點(diǎn)，那時 3 個人所走的路程總和是：A1C+A2C+A3C=（ A1C+A3C）+A2C=A1A3+A2C；而集合地點(diǎn)選在 A2點(diǎn)時，3個人所走路程總和僅是 A1A3當(dāng)然 A1A3比 A1A3+A2B 及 A1A3+A2C都小當(dāng)有 4 個人時，由于集合地點(diǎn)無論選在 A1A4之間的任何位置，對 A1、 A4崗 位上的人來說，這 2 人走的路程和都是 A1A4（如下圖）因此，集合地點(diǎn)的選 取只影響 A2、A3崗位上的人所走的路

12、程，這就是說，問題轉(zhuǎn)化為“ 2 個人站在 A2和 A3崗位的情形”根據(jù)上面已討論的結(jié)論可知，集合地點(diǎn)應(yīng)選在A2或 A3或者 A2A3 之間任何地點(diǎn)當(dāng)有 5 個人時，類似地可把問題轉(zhuǎn)化為“ 3 個人站在 A2、A3、A4 崗位的情 形”（如下圖）根據(jù)已討論的結(jié)論可知，集合地點(diǎn)應(yīng)選在A3 點(diǎn)依此遞推下去，我們就得到一個規(guī)律：當(dāng)有偶數(shù)（ 2n ）個人時，集合地點(diǎn)應(yīng)選在中間一段 AnAn+1 之間的任何 地點(diǎn)（包括 An和 An+1點(diǎn)）；當(dāng)有奇數(shù)（ 2n+1）個人時，集合地點(diǎn)應(yīng)選在正中間崗位 An+1點(diǎn)本題有 1993=2×996+1（奇數(shù)）個人，因此集合地點(diǎn)應(yīng)選在從某一端數(shù)起 第 997

13、個崗位處說明：本題的解題思路值得掌握， 那就是先從簡單的較少的人數(shù)入手， 通 過逐步遞推，探索一般規(guī)律，從而解決某些數(shù)字較大的問題課堂練習(xí)：1媽媽殺好魚后，讓小明幫助燒魚他洗魚、切魚、切姜片蔥花、洗鍋煎燒，各道 工序共花了 17 分鐘（如下圖），請你設(shè)計一個順序，使花費(fèi)的時間最少2一只平底鍋只能煎兩只餅，用它煎 1 只餅需要 2分鐘（正、反面各 1 分鐘），問： 煎 3 只餅需要幾分鐘？怎樣煎？如果需要煎 N（ N3）只餅，至少需要多少分鐘？3小明、小華、小強(qiáng)同時去衛(wèi)生室找張大夫治病小明打針要5 分鐘小華換紗布要 3 分鐘，小強(qiáng)點(diǎn)眼藥水要 1 分鐘問張大夫如何安排治病次序， 才能使他們耽誤上 課的時間總和最少？并求出這個時間4趙師傅要加工某項工程急需的 5 個零件，如果加工零件 A、B、C、D、 E所需時間 分別是 5 分鐘、3分鐘、4 分鐘、 7分鐘、 6分鐘問應(yīng)該按照什么次序加工，使工程 各部件組裝所耽誤的時間總和最少？這個時間是多少？ 課后作業(yè)：1、有 7個滿杯水， 有 7個半杯水和有 7個空杯， 不許倒掉水， 你能把這些東西平均分給 3個人， 使得每個人有 7只杯子和 3 杯半水嗎？2、理發(fā)店只有一位理發(fā)師，同時來了5位顧客，根據(jù)顧客所要理的發(fā)型，分別需要10 分鐘，12分鐘， 15 分鐘， 20 分鐘和 24 分鐘，怎樣安排他們理發(fā)