1、第九章 圖論模型,在生產(chǎn)生活中，人們常常用圖或網(wǎng)絡(luò)來刻畫、解釋和處理某些實(shí)際問題,常見的如車輛流通圖、電路網(wǎng)絡(luò)圖、賽事安排圖和工程進(jìn)度管理圖等.這種表示方式不僅使實(shí)際問題變得直觀、簡潔、明了，而且也為實(shí)際問題的研究提供了一種有效的方法 .近幾十年來，隨著運(yùn)籌學(xué)、信息論和計(jì)算機(jī)科學(xué)的發(fā)展，人們對圖論和網(wǎng)絡(luò)的研究也越來越廣泛和深入，并且迅速地產(chǎn)生了一門新興的數(shù)學(xué)分支圖論.在這一章里，我們將簡略地介紹一些與此有關(guān)的實(shí)際問題以及解決這些問題的巧妙方法.,9.1 一筆畫問題,9.1.1 七橋問題 18世紀(jì)，東普魯士的哥尼斯堡是一座景致迷人的城市，普勒格爾河橫貫其境，并在這兒形成兩條支流，把整座城市分割成

2、4個(gè)區(qū)域 （如圖）,河的兩岸(c和d），河中的島(a)和兩條支流之間的半島(b).當(dāng)時(shí)有7座橋橫跨普勒格爾河及其支流，,把河岸、半島和河心島連接起來.有趣的橋群和哥城4區(qū)域的的迷人景色吸引了眾多的的游客.有人在游覽時(shí)提出這樣的問題：能否從某個(gè)地方出發(fā)，穿過所有的橋各一次后再回到出發(fā)點(diǎn)？很多人做了嘗試，但沒有一個(gè)人成功.是否存在成功的可能性呢？人們既拿不出成功的方案，又找不到否定的理由.后來這個(gè)令人困惑的問題被年輕的瑞士數(shù)學(xué)家歐拉（leonhard eular）知道了，他在1736年向圣彼得堡學(xué)院遞交的一篇論文中巧妙的解決了這個(gè)問題. 他是怎么解決這個(gè)問題的呢？,他首先把哥尼斯堡的4個(gè)區(qū)域分別用

3、a,b,c,d表示，,7座橋表示成7條連接這4個(gè)點(diǎn)的線，于是哥尼斯堡七橋的情形就轉(zhuǎn)化為下圖的情形,這個(gè)由4個(gè)點(diǎn)和7條連線（也叫邊）組成.問題相應(yīng)地變?yōu)椋涸谏鲜瞿M圖中，從a,b,c,d中任何一點(diǎn)出,發(fā)，筆不離紙，但又不能重復(fù)任何一條邊地畫出模擬圖，且起點(diǎn)與終點(diǎn)重合，這樣的畫法存在嗎？這就是眾所周知的“一筆畫”問題. 接下來，歐拉研究了能夠“一筆畫”的圖形所應(yīng)具有的性質(zhì).他注意到，這類圖中的點(diǎn)倘若不是“一筆畫”的起點(diǎn)和終點(diǎn)，那它作為“一筆畫”的“中途點(diǎn)”應(yīng)該具有這樣的特性：筆沿著某條邊“進(jìn)入”點(diǎn)后，必定要沿著另一條邊“出去”.于是， “中途點(diǎn)”的邊必定成對出現(xiàn).也就是說，與“中途點(diǎn)”相連的邊的條

4、數(shù)必是偶數(shù).,我們把與點(diǎn)v相連接的邊的條數(shù)稱為該點(diǎn)的度數(shù)，,記作d（v）.d（v）為偶數(shù)時(shí)，點(diǎn)v稱為偶點(diǎn)，否則稱為奇點(diǎn).按歐拉的分析，能“一筆畫”的圖的“中途點(diǎn)”的度數(shù)為偶點(diǎn)，而奇點(diǎn)只能作為“一筆畫”的起點(diǎn)或終點(diǎn).當(dāng)起點(diǎn)和終點(diǎn)重合時(shí)，該圖不存在奇點(diǎn).概括起來，就是這樣一個(gè)結(jié)論：如果一個(gè)圖形可以“一筆畫”，那么其奇點(diǎn)個(gè)數(shù)必為0（起點(diǎn)和終點(diǎn)重合）或2（起點(diǎn)和終點(diǎn)不重合）.,9.1.2 有關(guān)圖的基本概念,為了便于說明，我們簡要的介紹一下圖的基本概念及其性質(zhì). 我們經(jīng)常遇到這樣一些問題，他們僅包含兩方面的內(nèi)容：一是一些“對象”（如七橋問題中的島和河岸），二是這些對象之間的某種關(guān)系（如島與島、島和河岸之

5、間是否有橋連接，有幾座橋連接）.為表示這些對象和它們之間的關(guān)系，可以在紙上畫一些點(diǎn)，每一點(diǎn)代表一個(gè)對象，稱這些點(diǎn)為頂點(diǎn)，如果兩個(gè)對象之間有所討論的關(guān)系，就在相應(yīng)的兩點(diǎn)之間連一條線，這些線稱為邊，這樣有若干個(gè)點(diǎn)和若干條邊就構(gòu)成了一個(gè)圖.,由若干個(gè)不同的頂點(diǎn)與連接其中某些頂點(diǎn)的邊所組成的圖形稱為圖.通常用g來表示圖.用v表示圖中所有頂點(diǎn)的集合，用,e表示所有邊的集合，并且記為g=(v,e).圖g中頂點(diǎn)的個(gè)數(shù)|v|稱為g的階. 圖的基本性質(zhì)： 設(shè)g是n階圖，則g中n個(gè)頂點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍. 證明： 所有頂點(diǎn)的度數(shù)之和表示以每一頂點(diǎn)為端點(diǎn)的邊的總數(shù).由于一條邊有兩個(gè)端點(diǎn)，因此每條邊在頂點(diǎn)的度數(shù)

6、之和中都被記入兩次，所以頂點(diǎn)的度之和應(yīng)為邊數(shù)的兩倍. 推論： 對于任意的圖g，奇點(diǎn)的個(gè)數(shù)是偶數(shù). 在圖g中，有一個(gè)不同的邊組成的序列： e1, e2, , em，如果其中邊, ei=(vi-1，vi),i=1,2,3m.則稱這個(gè)序列是從v0到vm的鏈. 如果一條鏈的始點(diǎn)v0和終點(diǎn)vm重合，則稱這條鏈為圈.,如果對于圖g中的任意兩個(gè)頂點(diǎn)u和v，都有一條從u到v的鏈，則稱這樣的圖g是連通的，否則稱g是不連通的.,經(jīng)過圖g的每條邊的鏈，稱為g的歐拉鏈.經(jīng)過圖g的每條邊的圈稱為g的歐拉圈.一個(gè)圖若包含歐拉圈，則稱這個(gè)圖為歐拉圖. 直觀的講，歐拉圖就是從某一頂點(diǎn)出發(fā)而每邊恰通過一次又能回到出發(fā)點(diǎn)的圖.,

7、9.1.3 一筆畫定理及其證明,在七橋問題的討論中，我們得到了一個(gè)結(jié)論:如果一個(gè)圖形可以“一筆畫”，當(dāng)且僅當(dāng)其奇點(diǎn)個(gè)數(shù)必為0或2.那么我們自然會問，這個(gè)命題的逆命題成立嗎？也就是說，當(dāng)一個(gè)圖形的奇點(diǎn)個(gè)數(shù)為0或2時(shí)，它可以“一筆畫”嗎？如果能畫，是否有一種一般可行的畫法？答案是肯定的.將原命題與其逆命題綜合起來，就是我們所說的一筆畫定理. 一筆畫定理：圖g是歐拉鏈（即可以一筆畫）的充要條件是：g是連通的，并且奇點(diǎn)的個(gè)數(shù)為0或2.當(dāng)且僅奇點(diǎn)個(gè)數(shù)等于0時(shí)，連通圖g是一個(gè)圈. 證明 必要性：如果圖g是一條從v1到vn+1的鏈，那么每一個(gè)不同于v1及vn+1的頂點(diǎn)vi（i=2,3你）都是偶頂點(diǎn)。故g至多

8、有兩個(gè)奇點(diǎn)，即v1與vn+1。若g是圈，則v1與vn+1也是偶定點(diǎn).,充分性：如果g是連同，且奇頂點(diǎn)的個(gè)數(shù)為0，那么g一定是一個(gè)圈.事實(shí)上，從g中任一頂點(diǎn)v0出發(fā)，經(jīng)相鄰的邊e1進(jìn)入,v1，因?yàn)閐（v1）是偶數(shù)，由v1再經(jīng)相鄰的邊e2可進(jìn)入v2，如此繼續(xù)下去，每條邊僅取一次，經(jīng)過若干步后必可回到v0，于是就得到一個(gè)圈u1：v0v1v0. 如果u恰好是圖g，則命題得證.否則在圖g中去條u1后得子圖g1，g1中每個(gè)頂點(diǎn)也都是偶頂點(diǎn).因圖g是連通的，所以在g1中必定存在一個(gè)和u1公共的頂點(diǎn)u，使得g1中存在一個(gè)從u出發(fā)到u 的圈u2.于是u1和u2合起仍是一個(gè)圈. 重復(fù)上述過程，因?yàn)間中總共只有有限

9、條邊，總有一個(gè)時(shí)候，得到的這些圈恰好是圖g.所以g是歐拉圖. 如果g連通，其奇頂點(diǎn)的個(gè)數(shù)為2，不妨設(shè)u和v是兩個(gè)奇頂點(diǎn).在u和v之間連一條邊e得圖g，于是g中奇頂點(diǎn)的個(gè)數(shù)為0，故g是一個(gè)圈，從而去掉e后，g便是一條歐拉鏈.證畢.,注： 在充分性的證明過程中，我們提供了”一筆畫“的一種方法，即一筆畫圖形是由具有公共頂點(diǎn)的一個(gè)一個(gè)圈組合而成,的，而且一個(gè)圖能夠”一筆畫“的方法往往有很多種. 9.1.4 一筆畫定理的簡單應(yīng)用 回過頭來看哥尼斯堡七橋問題。有模擬圖知：d（a）=d（b）=d（d）=3，d（c）=5. 4個(gè)頂點(diǎn)都是奇點(diǎn)，所以模擬圖不可能被一筆畫成.也就是說，哥尼斯堡七橋問題中要找的那條道

10、路是不存在的. 9.1.5 評注 在這個(gè)模型中，不需要考慮點(diǎn)線的長短大小，也不需要涉及量的計(jì)算，而只要研究點(diǎn)與點(diǎn)的關(guān)系就可以了.這種特殊的研究對象、研究方法和研究模型被公認(rèn)為是圖論學(xué)科的起源，現(xiàn)在以體現(xiàn)出它廣泛的應(yīng)用價(jià)值.,9.2 中國郵遞員問題,郵路問題：一個(gè)郵遞員每次上班，要走遍他負(fù)責(zé)的每條路，然后回到郵局.問他應(yīng)該怎么走才能使所走的路程最短？ 首先考慮這樣一個(gè)問題：如圖，每條線上的數(shù)字表示距離，小圓圈中的數(shù)字表示交叉路口的編號.我們從一點(diǎn)出發(fā)，有沒有可能沿每條路都走過一遍（不許重復(fù)也不許遺漏），然后回到出發(fā)點(diǎn)呢？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員

11、問題。,1,2,3,4,5,6,7,2,1,2,3,3,1,3,4,易見，當(dāng)圖中只要有一個(gè)奇點(diǎn)時(shí)，就不可能那樣走一遍了，因?yàn)閷σ粋€(gè)路口來說，有走進(jìn)去的一條路，必有走出來的一,條路.反之也不難證明，當(dāng)?shù)缆穲D上沒有沒有奇點(diǎn)時(shí)，便可以那樣走一遍了.如果起點(diǎn)和終點(diǎn)可以不同，則允許有兩個(gè)奇點(diǎn).這就是上節(jié)討論的“一筆畫”問題.回到郵路問題，如果道路圖上沒有奇點(diǎn)，問題就已經(jīng)解決了.如果有奇點(diǎn)，我們總可以通過在某一些路上再重復(fù)走一遍的辦法來消滅奇點(diǎn)，這相當(dāng)于在圖上再添一些路. 在圖中， 是偶點(diǎn)， 是奇點(diǎn)，因此，在圖上要再添一些路來消滅奇點(diǎn).如果在 和 之間， 和 之間各添上一條路（即在2，3和5，6上走兩次）

12、，奇點(diǎn)就沒有了，于是就可以一筆畫了.但我們還要求所走的路程最短，所以問題就歸結(jié)為：如何選擇要重復(fù)的路程，使之既能消滅奇點(diǎn),又能使重復(fù)的路程最短？,1,4,7,2,3,5,6,2,3,5,6,這個(gè)問題已經(jīng)被我國數(shù)學(xué)家管梅谷解決了，所以郵路問題又稱為中國郵遞員問題.他證明了只要在每個(gè)圈上所走的重復(fù)路,程不超過整個(gè)圈長的一半，就可以得到路程最短的走法.例如在上圖中，如果重復(fù) 和 ， 和 兩條路，雖能消滅奇點(diǎn)，但在圈 上重復(fù)路程2+3=5已經(jīng)超過整個(gè)圈長的一半(4.5)，所以它不是路程最短的走法.我們可以改為重復(fù) - ， - ， - ，這樣既消滅了奇點(diǎn)，又使得每個(gè)圈上的重復(fù)路程都不超過整個(gè)圈長的一半.

13、于是就得到這樣一個(gè)路程最短的走法： . 綜上所述，得出解決郵路問題的基本步驟如下：首先把道路圖上所有的奇點(diǎn)都找出來，然后選擇一些需要重復(fù)的路，消滅奇點(diǎn)，再在每個(gè)圈上檢查重復(fù)路程是否超過整個(gè)圈長之半，如有超過的情況，則在這個(gè)圈上，把原來不重復(fù)的路定為重復(fù)的路，而把原來重復(fù)的路定為不重復(fù)的路，這樣逐步調(diào)整，當(dāng)所有圈上的重復(fù)路程都不超過整個(gè)圈長之半時(shí)，就達(dá)到路程最短的要求了，最后將整個(gè)圖形一筆畫出.,2,3,5,6,2,3,4,5,6,2,2,6,3,4,4,5,1,3,4,6,5,7,5,4,3,2,6,2,1,一般說來，一個(gè)圖形所具有的圈數(shù)是很多的，是否每個(gè)圈都必須要檢查？答案是否定的，如上圖中

14、共有6個(gè)圈，實(shí)際上,只要檢查3個(gè)就夠了.一般的，若一個(gè)圖有s條路，n個(gè)頂點(diǎn)，則需要檢查的圈數(shù)為s-n+1. 這里提出的問題，不只是郵遞員會碰到，在其他一些場合也會碰到，如在馬路上掃地、灑水的車子所走的路線.,9.3 周游世界問題,人們在旅游時(shí)常常希望設(shè)計(jì)這樣一條路線，能夠不重復(fù)地經(jīng)過所有想要游覽的景點(diǎn)，而且路程最短.1859年，愛爾蘭數(shù)學(xué)家哈密爾頓設(shè)計(jì)了一種叫做“周游世界”的游戲.游戲的玩具是一個(gè)正十二面體.如下圖:,在它的20個(gè)頂點(diǎn)上分別表有世界上20個(gè)著名的城市，每兩個(gè),頂點(diǎn)之間的棱表示這兩個(gè)城市之間的可通行道路.游戲的規(guī)則是：找出一條道路，使他從某個(gè)城市出發(fā)，經(jīng)過所有其他城市一次后返回原

15、出發(fā)城市. 為方便起見，我們把這個(gè)十二面體投影到平面上保持原點(diǎn)、線之間的連接關(guān)系.能否在下圖（2）中找出一條道路，使它從某個(gè)頂點(diǎn)出發(fā)，經(jīng)過所有其他定點(diǎn)各一次后再回到出發(fā)點(diǎn)呢？ 如果這條首尾相連的道路存在，我們把它叫做原圖的一個(gè)哈密爾頓圈，含有哈密爾頓圈的圖稱為哈密爾頓圖.,我們注意到，哥尼斯堡七橋問題的幾何模型與哈密爾頓周游世界問題的幾何模型有某些相似之處，即都是在圖中尋找一,條首尾相連的道路，都要求所走的路程最短.不同的是，前者所找的道路要經(jīng)過所有的邊恰好一次（每條邊至少一遍），而后者則要求經(jīng)過所有的頂點(diǎn)恰好一次（有的路可以不走）. 解決哈密爾頓周游世界問題，可借助于“一筆畫”的性質(zhì)：如果圖

16、（2）中存在哈密爾頓圈，那么由于這個(gè)“圈”是一個(gè)“一筆畫”圖形，其所經(jīng)過的點(diǎn)必都是“圈”上度數(shù)為2的偶點(diǎn)，在圖（2）中，這個(gè)“圈”要經(jīng)過20個(gè)頂點(diǎn)，而所有頂點(diǎn)的度數(shù)之和為邊數(shù)的兩倍，由此可知“圈”上的邊數(shù)為20.已知正十二面體共有30條邊，于是問題轉(zhuǎn)化為：能否抹去10條邊，使圖中（2）中20個(gè)頂點(diǎn)的度數(shù)都變?yōu)?.這是可以做到的.,第10章 數(shù)學(xué)建模的常見方法,10.1 數(shù)據(jù)建模法 在用數(shù)學(xué)模型解決實(shí)際問題時(shí)，如果能夠利用物理、化鄧自然科學(xué)的規(guī)律來建立數(shù)學(xué)模型，就把這種建模的方法稱為機(jī)理分析法.但是在不少實(shí)際問題中，人們所掌握的僅僅是一些通過檢測所得到的數(shù)據(jù)資料，根據(jù)這些數(shù)據(jù)建立盡量符合問題實(shí)際

17、的數(shù)學(xué)模型，稱為數(shù)據(jù)建模法. 這里所說的數(shù)據(jù)資料是指人們從實(shí)際問題中收集得到的事實(shí)觀察值和測量值.它是數(shù)學(xué)模型與實(shí)際問題相聯(lián)系的重要途徑和手段.由于來自實(shí)際的數(shù)據(jù)資料有可能是不精確的，或者是不完善的，因此建模過程中處理好數(shù)據(jù)資料和模型的關(guān)系非常重要的. 在使用數(shù)據(jù)建模法時(shí)，有時(shí)所采集的數(shù)據(jù)資料對于建模與分析已經(jīng)足夠了，無需另外采集更多的數(shù)據(jù)；有時(shí)則不然，得從采集數(shù)據(jù)做起.收集有效數(shù)據(jù)并不是一件容易的,事，一般得注意以下兩點(diǎn)（1）收集數(shù)據(jù)應(yīng)有明確的目標(biāo).,（2）對于收集得來的數(shù)據(jù)應(yīng)作適當(dāng)?shù)念A(yù)處理.在建模過程中，數(shù)據(jù)資料的作用很大，主要體現(xiàn)在以下三個(gè)方面： （a）在建模過程中（特別是在建模的初期）

18、，當(dāng)我們開始構(gòu)架問題的模型時(shí)，數(shù)據(jù)資料能夠?qū)ξ覀兯鶚?gòu)架模型給予了提示.有些模型（如經(jīng)驗(yàn)?zāi)Ｐ停﹦t是完全建立在數(shù)據(jù)資料的基礎(chǔ)之上.（b）數(shù)據(jù)資料可以幫助我們對模型的參數(shù)給出估計(jì).使用數(shù)據(jù)資料給出模型參數(shù)值的估計(jì)過程，我們稱之為模型的參數(shù)估計(jì). （c）數(shù)據(jù)資料還可以用于檢驗(yàn)?zāi)Ｐ偷男Ч?，也就是檢驗(yàn)由模型計(jì)算出來的理論數(shù)據(jù)是否合理地反映了實(shí)際的觀測結(jié)果.如果有若干個(gè)模型描述同一個(gè)實(shí)際問題時(shí)，模型效果的檢驗(yàn)可以幫助我們選擇最優(yōu)的模型. 本節(jié)主要討論數(shù)據(jù)建模的兩種情形，即由確定性數(shù)據(jù)建模和由隨機(jī)性數(shù)據(jù)建模. 10.1.1 從不同角度看待數(shù)據(jù)資料 解決問題最重要的往往并不是怎樣將數(shù)據(jù)代入公式，而是要確,定哪些

19、數(shù)據(jù)、哪些因素對事件有影響.請看下面的例子.,例1. 香港地區(qū)的中學(xué)數(shù)學(xué)教材中有這樣一個(gè)題目：某企業(yè)有股東5人，工人100人，19901992年的3年間，該企業(yè)的收益情況如表所示，要求根據(jù)表中數(shù)據(jù)繪制一幅坐標(biāo)圖.,面對這樣一組數(shù)據(jù)，不同的思維哦方法可以構(gòu)建出不同的數(shù)學(xué)模型，描繪出不同的圖形. 可以是兩條平行線，傳遞出的信息是勞資雙方共同發(fā)展，有福同享、有難同當(dāng)。這樣的圖形是老板最愿意看到的，我們姑且稱它為“老板圖”。,也可以那全體股東利潤增長的比例和全體工人工資增長的比例作比較，以1990年為起點(diǎn)（100），3年后，股東利潤增長了100%，而工人工資只增長了50%.這幅圖傳遞出來的信息是工人工

20、資的增長比例是股東利潤增長比例的一半，應(yīng)該適當(dāng)增加工人的工資，我們把它稱為“工會圖”.我們還可以那股東跟人收入的增長和工人個(gè)人收入的增長作比較，傳遞出來的信息則是股東和工人的收入差距十分懸殊，而且差距越來越大，這樣的圖可稱為“工人圖”. 華東師大的張奠宙教授拿這一題目請一位教師到中學(xué)做實(shí)驗(yàn)，讓同學(xué)們根據(jù)數(shù)據(jù)匯出圖來。結(jié)果100%的學(xué)生繪制出第一個(gè)圖形.在學(xué)生們看來，第一個(gè)圖是最規(guī)范的思路，也是最標(biāo)準(zhǔn)的答案，他們根本沒想過這一題目會具有多種答案，也沒有想過一組數(shù)據(jù)中透露出來的生活中的實(shí)際信息，而只是想到把這一題目解出來就行了. 由此可見，面對不同的數(shù)據(jù)或條件、不同的需要、不同的構(gòu)思，完全可能建立

21、起不同的數(shù)學(xué)模型來，關(guān)鍵在于我們看待問題要多角度，思維力求發(fā)散.,10.1.2 依據(jù)確定性數(shù)據(jù)的建模方法 在某種變化過程中，所涉及的變量之間存在某種確定性的函數(shù)關(guān)系，檢測所得的數(shù)據(jù)資料僅僅是這種確定性的函數(shù)關(guān)系在量上的反映，我們把這種情況稱為確定性現(xiàn)象. 既然此時(shí)變量之間存在確定性的函數(shù)關(guān)系，那么就需要我們通過對數(shù)據(jù)資料進(jìn)行分析處理，來揭示其內(nèi)在的函數(shù)關(guān)系，建立數(shù)學(xué)模型.一個(gè)簡單的例子就是，圓的周長c與直徑d之間的關(guān)系.不同的圓有不同的周長，人們通過大量的檢測數(shù)據(jù)，揭示了這一本質(zhì)關(guān)系，建立了函數(shù)模型 c= d 其中圓周率是一個(gè)常數(shù)3.141592653 例10-2 跳板承受力的問題 10.1.

22、3依據(jù)隨機(jī)性數(shù)據(jù)的建模方法,10.3 統(tǒng)籌法,10.3.1 定義 一項(xiàng)工程由若干道工序組成，每道工序都需要一定的工期，各道工序之間存在一定的前后銜接關(guān)系，那么工程進(jìn)度如何安排呢？ 解決這類問題的方法一般是統(tǒng)籌法，國外又叫做計(jì)劃外評審方法. 又稱網(wǎng)絡(luò)計(jì)劃法。它是以網(wǎng)絡(luò)圖反映、表達(dá)計(jì)劃安排，據(jù)以選擇最優(yōu)工作方案，組織協(xié)調(diào)和控制生產(chǎn)（項(xiàng)目）的進(jìn)度（時(shí)間）和費(fèi)用（成本），使其達(dá)到預(yù)定目標(biāo)，獲得更佳經(jīng)濟(jì)效益的一種優(yōu)化決策方法。 10.3.2 背景 1957年，美國化學(xué)公司du pont的m.r.walker與rand通用電子計(jì)算機(jī)公司的j.e.kelly為了協(xié)調(diào)公司內(nèi)部不同業(yè)務(wù)部門的工作，共同研究出關(guān)鍵

23、路線方法（簡記作cpm）.首,次把這一方法用于一家化工廠的籌建，結(jié)果籌建工程提前兩個(gè)月完成.隨后又把這一方法用于工廠的維修，結(jié)果使停工時(shí)間縮短了47個(gè)小時(shí)，當(dāng)年就取得節(jié)約資金達(dá)百萬元的要觀效益。 1958年，美國海軍武器規(guī)劃局特別規(guī)劃室研制含約3000項(xiàng)工作任務(wù)的北極星導(dǎo)彈潛艇計(jì)劃，參與的廠商達(dá)11000多家.為了有條不紊地實(shí)施如此復(fù)雜的工作，特別規(guī)劃室領(lǐng)導(dǎo)人w.fazar積極支持與推廣由專門小組創(chuàng)建的計(jì)劃評審技術(shù)（簡記作pert）.結(jié)果研制計(jì)劃提前兩個(gè)完成，取得了極大的成功。 cpm在民用企業(yè)與pert在軍事工業(yè)中的顯著成效，自然引起了普遍的重視.在很短的時(shí)間內(nèi)，cpm與pert就被應(yīng)用于工

24、業(yè)、農(nóng)業(yè)、國防與科研等等復(fù)雜的計(jì)劃管理工作中，隨后又推廣到世界各國.在應(yīng)用推廣cpm與pert的過程中，又派生出多種各具特點(diǎn)，各有側(cè)重的類似方法.但是萬變不離其宗，各種有所不同的方法，其基本原理都源于cpm與pert。 cpm與pert兩種方法實(shí)質(zhì)上大同小異，因此，人們把,cpm與pert及其他類似方法統(tǒng)稱為網(wǎng)絡(luò)計(jì)劃技術(shù)，簡稱為網(wǎng)絡(luò)技術(shù)或網(wǎng)絡(luò)方法，簡記為統(tǒng)籌法。網(wǎng)絡(luò)計(jì)劃技術(shù)最適用于大規(guī)模工程項(xiàng)目，工程愈大，非但人們的經(jīng)驗(yàn)難以勝任，就是用以往的某些管理方法（例如反映進(jìn)度與產(chǎn)量的線條圖等方法）來進(jìn)行計(jì)劃控制也愈加困難.相反地在項(xiàng)目繁多復(fù)雜的情況下，網(wǎng)絡(luò)計(jì)劃是可以大顯身手。 1962年，我國科學(xué)家錢

25、學(xué)森首先將網(wǎng)絡(luò)計(jì)劃技術(shù)引進(jìn)國內(nèi)。1963年，在研究國防科研系統(tǒng)si屯子計(jì)算機(jī)的過程中，采用了網(wǎng)絡(luò)計(jì)劃技術(shù)，使研制任務(wù)提前完成.計(jì)算機(jī)的性能穩(wěn)定可靠，隨后，經(jīng)過我國數(shù)學(xué)家華羅庚對網(wǎng)絡(luò)計(jì)劃技術(shù)的大力推廣，終于使這一科學(xué)的管理技術(shù)在中國生根發(fā)芽，開花結(jié)果，鑒于這類方法共同具有“統(tǒng)籌兼顧、合理安排”的特點(diǎn)，我們又把它們稱為統(tǒng)籌法，網(wǎng)絡(luò)圖也稱統(tǒng)籌圖，本節(jié)主要講述統(tǒng)籌法的基本思想。 現(xiàn)在通過對下例的分析，來了解統(tǒng)籌法的基本思想。,作出該部件的生產(chǎn)計(jì)劃流程圖并加以分析，再提出使完工期縮短的 改進(jìn)措施。,分析 本例可稱為“生產(chǎn)過程的優(yōu)化問題”，衡量的數(shù)量指標(biāo)是“完成工程的時(shí)間”越短越好.鑒于工廠生產(chǎn)的實(shí)際情況

26、，可知明細(xì)表中所列各項(xiàng)目的先后順序關(guān)系不允許更動，也中可能對任一項(xiàng)目進(jìn)行分解.例如，依照工藝過程，必須先制造木模，才能去生產(chǎn)鑄件，這樣就可得到下圖所示的生產(chǎn)計(jì)劃流程的一個(gè)方案。,從上圖中可見，a、d、f三個(gè)項(xiàng)目同時(shí)開工，隨后分成三條支路.先考察上、中、下三條支路上各項(xiàng)目總共所費(fèi)的時(shí)間，具體地說，有 上支路 10151035 中支部 251540 下支部 204060 比較之，可見f與g兩個(gè)項(xiàng)目合成的下支部所花時(shí)間最長。該部件生產(chǎn)計(jì)劃的完工期實(shí)質(zhì)上受f與g兩個(gè)項(xiàng)目工時(shí)的制約。 設(shè)想一下，即使a、b、c、d、e都如期完工，但是由于f、g還在進(jìn)行中，先完工的人員與設(shè)備如不及時(shí)利用只能閑置起來，造成所

27、謂“窩工”現(xiàn)象，這就是生產(chǎn)力浪費(fèi)，要是有可能重新調(diào)配力量，適當(dāng)?shù)刈宎、b、c、d或d、e慢點(diǎn)完工，同時(shí)力求f、g快點(diǎn)完工，那么就可能縮短工程的完工期.于是可以采取如下措施：把上支部或中,支部上的資源（人員、設(shè)備等）適當(dāng)抽調(diào)一部發(fā)到下支路上去，以加快完工期.當(dāng)然，這里已設(shè)被抽調(diào)的資源適用于下支部上的項(xiàng)目。例如，設(shè)計(jì)鍛模（a）的人也要會設(shè)計(jì)工裝（f）。從而可以去支援f。此外，從某項(xiàng)目上被抽調(diào)的資源數(shù)量必須適當(dāng)，抽調(diào)過多，原項(xiàng)目的完工時(shí)間將大為延長，反過來又會影響完工期。 因此，時(shí)間最長的那條支路對于完工期起著關(guān)鍵的作用，所以被稱為關(guān)鍵路線。 可見統(tǒng)籌法基本思想，簡單地說就是：向關(guān)鍵路線要時(shí)間，向非

28、關(guān)鍵路線要資源，以達(dá)到預(yù)期目標(biāo)的最優(yōu)。 統(tǒng)籌法主要由互相關(guān)聯(lián)的三部分內(nèi)容組成： 1、統(tǒng)籌圖概念及繪圖規(guī)劃； 2、統(tǒng)籌圖各參數(shù)的計(jì)算法； 3、統(tǒng)籌圖的調(diào)整與優(yōu)化。由柳洪平創(chuàng)建。,統(tǒng)籌法的基本步驟如下： 第一： 確定工序，估計(jì)工時(shí)，弄情歌工序之間的結(jié)合及順序關(guān)系（工序本身的基本關(guān)系）； 第二：繪制工序流程圖； 第三： 計(jì)算各條工序線路的工期數(shù)， 第四： 通過比較，選出主要矛盾線及若干條次要矛盾線.盯住主要矛盾線，按流線圖安排施工。并時(shí)刻收集各工序進(jìn)展情況，通過信息反饋調(diào)整流線圖.有條不紊的指揮整個(gè)工程. 例 想泡壺茶喝。當(dāng)時(shí)的情況是：開水沒有；水壺要洗，茶壺茶杯要洗；火生了，茶葉也有了。各項(xiàng)工作要

29、用的時(shí)間(單位：分鐘)如下：a洗水壺1;b燒開水15；c洗茶壺1；d洗茶杯1，e拿茶葉2；f泡開茶1/3.問各項(xiàng)工作怎么安排才能盡快喝到茶？最快多長時(shí)間？,辦法甲： 洗好水壺，灌上涼水，放在火上；在等待水開的時(shí)間里，洗茶壺、洗茶杯、拿茶葉；等水開了，泡茶喝。 辦法乙： 先做好一些準(zhǔn)備工作，洗水壺，洗茶壺茶杯，拿茶葉；一切就緒，灌水燒水；坐待水開了泡茶喝。 辦法丙： 洗凈水壺，灌上涼水，放在火上，坐待水開；水開了之后，急急忙忙找茶葉，洗茶壺茶杯，泡茶喝。 哪一種辦法省時(shí)間？我們能一眼看出第一種辦法好，后兩種辦法都窩了工。 水壺不洗，不能燒開水，因而洗水壺是燒開水的前提。沒開水、沒茶葉、不洗茶壺茶

30、杯，就不能泡茶，因而這些又是泡茶的前提。,辦法甲總共要161/3分鐘（而辦法乙、丙需要20分鐘）。如果要縮短工時(shí)、提高工作效率，應(yīng)當(dāng)主要抓燒開水這個(gè)環(huán)節(jié)，而不是抓拿茶葉等環(huán)節(jié)。同時(shí)，洗茶壺茶杯、拿茶葉總共不過4分鐘，大可利用等水開的時(shí)間來做。 練習(xí) 造某幢房子的工序、工期和工序銜接關(guān)系如表所示，問：怎樣才能使工程盡快完工？,開始a,b,3,5,c,12,d,5,g,9,i,7,j,3,e,3,f,7,h,15,k,4,結(jié)束,1.開始,a,b,c,f,g,i,j,結(jié)束，需44天.,2.開始,a,b,c,e,d,g,i,j,結(jié)束，需49天.,3.開始,a,b,c,e,f,結(jié)束，需30天.,4.開始

31、,a,b,c,h,k,結(jié)束，需39天.,我們知道，每個(gè)工序鏈的完成都是工程完成的必要條件.所以，我們應(yīng)該在其中找一條工期最長的鏈作為關(guān)鍵工序鏈，其鏈上的每道工序都是關(guān)鍵工序.在這項(xiàng)建房工程中，工序鏈2可以作為關(guān)鍵工序鏈，不在鏈上的工序都是非關(guān)鍵工序. 下面來確定各工序的開工時(shí)間.由于關(guān)鍵工序鏈已經(jīng)確定，所以各關(guān)鍵工序的開工、完工時(shí)間是確定的，關(guān)鍵工序鏈上每道工序的開工日期都可以定在其緊前工序的完成之時(shí).結(jié)果見右表.,確定非關(guān)鍵工序開工時(shí)間的原則是不影響關(guān)鍵工序的施工.例如，非關(guān)鍵工序d是關(guān)鍵工序g的緊前工序，而g的開工日期已定為30，因此d最遲必須在第30天完成.考慮到d的施工期為5天，所以d

32、的最遲開工日期應(yīng)為第25天（即第26天開始）.至于d的最早開工日期則是它的緊前工序c的完成之時(shí)-日期為第20天，相應(yīng)的最早完工日期為第25天.總之，對非關(guān)鍵工序，它們的開工日期由一定的松動余地，我們可按其緊前的關(guān)鍵工序的完工日期推算出它們的最早開工日期和最早完工日期；再按其緊后的關(guān)鍵工序的開工日期推算出它們的最遲完工日期和最遲開工日期.于是，一份完整的各工序時(shí)間安排表就制作完畢（見表）,總的施工進(jìn)度安排妥當(dāng)后，還要把各項(xiàng)任務(wù)和完成任務(wù)的時(shí)間落實(shí)到各施工組.設(shè)工序a由技術(shù)組負(fù)責(zé)；工序b和c由建筑組負(fù)責(zé)；工序d由管道組負(fù)責(zé)；工序e、f由電工組負(fù)責(zé)；工序g、h、i、j、k由泥工組和木工組共同負(fù)責(zé).匯

33、總上述情況，可將施工進(jìn)度按組作出條狀的進(jìn)度管理圖.見下表. 其中，泥木工組的任務(wù)比較多，又有一些工序需同時(shí)施工，所以把泥木工組分為兩組分頭施工.,10.4 聚類分析法,分類是人類認(rèn)識客觀世界的基本方法之一.人們把所研究的對象分成若干類，然后分門別類地進(jìn)行仔細(xì)研究，從而加深對事物的認(rèn)識.例如，通過對感冒病人病史的分類，可以加深對感冒病因的認(rèn)識；通過對公司經(jīng)營業(yè)績分類，可以找到改善經(jīng)營狀況的途徑.歷史上很早以前就有分類這門學(xué)問，但是那時(shí)主要是依靠專業(yè)知識進(jìn)行分類，很少利用數(shù)學(xué)工具.隨著生產(chǎn)和科學(xué)技術(shù)的發(fā)展，分類越來越細(xì)，分類準(zhǔn)確性的要求也越來越高.于是，分類學(xué)中逐漸形成了“統(tǒng)計(jì)聚類分析”或“統(tǒng)計(jì)聚

34、類建?！边@門學(xué)問. 10.4.1 如何衡量兩事物的差別 衡量兩個(gè)事物接近程度的方法很多，我們用量化手段來處理. 例1 體型差別.,從生活中我們知道，影響人類體型的因素中最重要的莫過于身高和體重了.我們把一個(gè)人的身高用 表示，體重用 表示；另一個(gè)人的身高用 表示，體重用 表示.兩個(gè)人體形的差別大體上可以用他們的身高和體重的差別來表示.為此，我們可以把 和 看做坐標(biāo)平面上的兩個(gè)點(diǎn).用這兩個(gè)點(diǎn)的“距離”來表示這連個(gè)人在體型上的差別.如果該距離比較小，說明這兩個(gè)人的體型比較接近；反之，他們體型的差別則較大.于是就得到了衡量兩個(gè)人體型差別的兩個(gè)簡單指標(biāo)：（1）矩形距離 ； （2）歐氏距離 . 當(dāng)然，在衡

35、量體形的差別時(shí)，我們還可以考慮更多的因素，如坐高、臂長等等. 例2 語言差別. 每種語言都非常復(fù)雜，各種語言既有差別，又有很多相近之處，如何對各種語言做一個(gè)恰當(dāng)?shù)姆诸惸兀?首先，必須尋找一種既簡單又能反映他們之間聯(lián)系和差別的方法.一種簡單的方法就是對各種語言中表達(dá)數(shù)字的詞進(jìn)行比較，這些詞之間的差別在一定程度上代表了不同語言之間的差別. 其次，不同語言的兩個(gè)數(shù)詞之間的差別如何用數(shù)來刻畫呢？我們設(shè)法用一種簡單的方法來規(guī)定兩種語言中數(shù)詞間的距離：若數(shù)詞的第一個(gè)字母相同，規(guī)定其距離為零；若數(shù)詞的第一個(gè)字母不同，則規(guī)定為1. 然后，用十個(gè)數(shù)詞間的距離之和a來規(guī)定這兩種語言的距離.顯然，a越小，這兩種語言

36、就越接近；反之，則相差越大.例如，歐洲各國之間有著悠久的歷史淵源關(guān)系，意大利語與西班牙語的距離為1，因此十分相近；而意大利語與匈牙利語的距離為10，因此相差很大. 最后，我們還可以對一些語言進(jìn)行適當(dāng)?shù)姆诸?例如歐洲10種語言與英語之間的距離見下表.,根據(jù)這些距離指標(biāo)，可以粗略的講著10種歐洲語言分為三類：挪威、丹麥；荷蘭、德國、法國、西班牙、意大利、波蘭；匈牙利、芬蘭. 10.4.2 聚類分析法 將每個(gè)事物都看做數(shù)學(xué)空間中的一點(diǎn)，在這個(gè)數(shù)學(xué)空間中規(guī)定兩點(diǎn)間的距離，以距離來表示事物的差別，分類時(shí)，常把距離近的點(diǎn)歸于一類，這種方法叫做聚類分析法. 聚類分析法如何操作呢？ 我們用d(i,k)表示第i

37、個(gè)事物與第k個(gè)事物間的距離.丙用適當(dāng)?shù)姆椒ㄒ?guī)定類與類之間的距離.了；例如：以 、 表示類，,以d(p,q)標(biāo)記類 與類 之間的距離， d(p,q)可以規(guī)定為 中任一事物和 中任一事物距離的最小值，即類 與類 之間的“最短距離”. 假設(shè)現(xiàn)在要對100個(gè)事物進(jìn)行分類.可先將100個(gè)事物各自成一類，這樣開始時(shí)共有100類.我們規(guī)定事物之間的距離，以表示事物之間的差別.同時(shí)規(guī)定類與類之間的距離，以表示類之間的差別.開始時(shí)，由于100個(gè)事物自成一類，故類與類之間的距離就是事物與事物之間的距離.將距離最小(或不超過某一數(shù)值)的類合并成一個(gè)新類，計(jì)算新類與其它類之間的距離，再將距離近的類合并.這樣，每次可以

38、減少類的數(shù)目，直至類的數(shù)目滿足聚類的要求為止.這是一種逐步合并的聚類方法. 10.4.3 有序事物的聚類分析 許多實(shí)際問題中的事物是按一定的次序排列的，這樣的事物稱為有序事物.例如，兒童的增重?cái)?shù)按年齡排序，歷史按時(shí)間的先后排序，地質(zhì)勘探取樣按地層的深淺排序.,對有序事物進(jìn)行分類時(shí)，不能打亂原先事物的次序.那么有序 事物如何聚類呢？ 10.4.3.1 問題 兒童體重每年增加的數(shù)量與兒童的生長發(fā)育過程有關(guān).下表給出了1歲至11歲兒童每年的平均增重?cái)?shù).,從上表中可以粗略地看到：1歲時(shí)兒童增重的高峰，6歲是兒童增重的低谷.我們主要討論：應(yīng)該把1歲到11歲的兒童劃分成幾個(gè)發(fā)育好階段？如何劃分階段為好？,

39、10.4.3.2 分析 一種好的分類方法，應(yīng)能使處于同一類中的事物之間的差別盡可能的小，而使類與類之間的差別盡可能的大.例如，把一個(gè)班級的學(xué)生分成學(xué)習(xí)成績好、中、差三類，同是成績好的一類學(xué)生之間的差別應(yīng)該不大.而若一個(gè)學(xué)生屬于成績好的類，另一個(gè)學(xué)生屬于成績中等的類，則這兩個(gè)學(xué)生之間應(yīng)有明顯的差別.如何表示類內(nèi)部事物與事物之間的差別呢？我們借用統(tǒng)計(jì)中全距(即兩數(shù)的距離)的計(jì)算方法. 10.4.3.3 模型建立及求解 以 ， ， ，記上述對應(yīng)的兒童增重的11個(gè)數(shù)據(jù)， 表示i歲兒童的增重?cái)?shù).設(shè)想要把它們分成保持次序的3個(gè)組，這時(shí)可以有多種選擇.例如，1，2，3，4，5，6，7，8，9，10，11就是一種可選擇的分類方法.這里1，2，3表示把1歲3歲分為一組， 4，5，6，7，8表示把4歲