應(yīng)用數(shù)學基礎(chǔ)（第2版）課件 陽永生 第4、5章 用圖表示關(guān)系、最優(yōu)化問題

用

圖表示

關(guān)

系

《應(yīng)用數(shù)學基礎(chǔ)》第四章引

言

在實際生活中，人們經(jīng)常會碰到各種各樣的圖問題。幾乎可以想到的每個學科中的問題都可以運用圖模型來解決。例如，如何用圖表示生態(tài)環(huán)境里不同物種的競爭，如何用圖表示組織中誰對誰產(chǎn)生了影響，如何用圖表示一個交通網(wǎng)絡(luò)等等。圖是由頂點和連接頂點的邊構(gòu)成的離散結(jié)構(gòu)。在本章中，我們將比較系統(tǒng)地介紹如何建立圖模型以及利用圖模型來解決實際問題。

第一節(jié)

圖的基本概念01第一節(jié)圖的基本概念

引例1

假設(shè)有一群人和一組工作，這群人中的某些人能夠做這組工作中的某些工作。例如，有3個人A、B和C，3件工作D、E和F，假設(shè)A只能做工作D,B能做工作E和F,C能做工作D和E。則這種情形可用下圖表示，其中，在人和這個人能夠做的工作之間畫有線。ACFDBE圖4-1工作關(guān)系圖

引例2考慮一張航線地圖，圖中用點表示城市，當兩個城市間有直達航班時，就用一條線將相應(yīng)的點連接起來。這種航線地圖的一部分如下圖所示：長春北京成都武漢上海

圖4-2航行線路圖第一節(jié)圖的基本概念

這兩個圖也可以表示其它的含義。例如，引例1的圖中，點A、B、C、D、E和F可以分別表示6家企業(yè)，如果某兩家企業(yè)有業(yè)務(wù)往來，則其對應(yīng)的點之間用線連接起來，這時的圖又反映了這6家企業(yè)間的業(yè)務(wù)關(guān)系。

事實上，生活中的許多問題如果用圖來描述可能更加簡潔清晰，這種圖是由一些點以及這個點中的某些點對的連線構(gòu)成。

如果圖中的邊有方向，則稱為有向圖，否則稱為無向圖。第一節(jié)圖的基本概念

在圖的圖形表示中，每個頂點用一個小圓點表示，每條邊用頂點之間的連線段表示。例如，引例1中的圖，它的頂點是A、B、C、D、E、F，連接它們的5條線段就是邊。一般情況下，我們用大寫字母A、B、C等來標記這些頂點，如果只有一條邊連接兩個頂點，我們就用這兩個頂點的字母連接起來表示這條邊。

在圖論中，我們只關(guān)注一個圖有多少個頂點、哪些點之間有邊連接，至于連線的長短曲直和頂點的位置卻無關(guān)緊要。例如，我們可以把圖4-1畫成下圖所示的形狀第一節(jié)圖的基本概念第一節(jié)圖的基本概念

建立圖論模型的方法：（1）用頂點代表每一個對象；（2）對于每一對有關(guān)系的對象，將相應(yīng)的頂點用邊連接起來。例1

(比賽圖模型)甲、乙、丙、丁、戊5支球隊進行比賽，各隊之間的比賽勝負情況如表4-1所示，試用圖表示他們的關(guān)系。第一節(jié)圖的基本概念解：

一個頂點表示一支球隊，球隊之間的勝負關(guān)系用有向邊表示，如，甲擊敗了隊，則頂點對(甲,乙)之間有一條從甲到乙的有向邊。圖4-4表示了5支球隊比賽情況的有向圖模型。從圖中可以很容易看出，在這項賽事里，目前丁隊無勝績。圖4-4比賽結(jié)果圖模型第一節(jié)圖的基本概念例2(生態(tài)學棲息地重疊圖模型)用頂點表示每一個物種，若兩個物種競爭(即它們共享某些實物來源)，則用無向邊連接它們對應(yīng)的頂點，如圖4-5表示一個森林生態(tài)系統(tǒng)。從圖4-5可以看出松鼠與浣熊競爭，但烏鴉不與臭鼬競爭。圖4-5棲息地重疊圖第一節(jié)圖的基本概念概念2一個圖稱為連通圖，如果可以從圖中任意一個頂點開始沿著邊連續(xù)地畫到另外一個任意的頂點。連通圖里被稱為橋的邊是指如果移去這條邊的話，圖就不再連通了。圖4-6連通圖例如，圖4-6就是一個連通圖，圖中的邊CG是一條橋。第一節(jié)圖的基本概念概念3圖中的路是指一個連續(xù)的、沒有重復邊的點邊序列。路中邊的條數(shù)稱為路的長度。起點和終點是同一個頂點的路稱為回路。

例如，在圖4-7中，路徑ABGED就是從A到D的一條長度為4的路，路徑ABHEFA就是從A出發(fā)又回到A的一條長度為5的回路。圖4-7第一節(jié)圖的基本概念例3

(疾病傳播模型)新墨西哥州西南方的一個小鎮(zhèn)面臨著一場危機。有8個被hanta病毒感染的人已經(jīng)報給鎮(zhèn)醫(yī)療中心，政府官員把這些人隔離，并希望沒有其他人也感染了這種病毒。健康部門來調(diào)查病毒是如何在這組人之間傳播的。他們認為病毒最初是由一個人帶入小鎮(zhèn)，然后向其他人傳播。請用表4-2的信息判斷是否小鎮(zhèn)上所有被感染的人已經(jīng)都已經(jīng)被隔離了。表4-2小鎮(zhèn)上病毒傳染表第一節(jié)圖的基本概念解用頂點表示病人，因為Amanda將病毒傳給了Dustin，所以從Amanda向Dustin畫一條有向邊。類似地，如果X將病毒傳給了Y，就從X向Y畫一條有向邊。這樣我們很容易利用有向圖為疾病傳播情況建立模型，如圖4-8所示。圖4-8疾病傳播圖模型第一節(jié)圖的基本概念

圖4-8中的有向邊表示病毒是如何在這組人中傳播的。例如，圖中的路ADCF表示病毒有可能是由Amanda傳給Dustin，再傳給Caterina，再到Frank的。因此，從圖中我們可以看出病毒不可能從Amanda開始在這組人之內(nèi)傳播，因為圖中不存在一條從Amanda到Brian的路。實際上，通過檢查每一個人，我們發(fā)現(xiàn)病毒不可能由他們之中的某一個人開始傳播，并傳給其他的所有人。因此，小鎮(zhèn)上必然有至少一人，他已經(jīng)被病毒感染，但是沒有被發(fā)現(xiàn)。第一節(jié)圖的基本概念

有時，我們解決問題的時候只需要圖的某一部分。例如，如果只關(guān)心疾病傳播模型中涉及Amanda、Brian、Dustin這三個人之間的那一部分，那么，這個組中其他的人以及不連接到這3人里任何2個人的所有邊都可以忽略。也就是說，在大網(wǎng)絡(luò)的圖模型里，可以刪除這3人以外的所有頂點和與所刪除頂點關(guān)聯(lián)的邊。刪除后剩下的圖稱為原圖的子圖。概念3設(shè)是兩個圖，若，且，則稱是的子圖，的母圖。是特別地，如果的子圖，并且是，則稱的生成子圖。是第一節(jié)圖的基本概念

例如，下圖中（2）、（3）均為（1）的子圖，更進一步地，因為（3）中的頂點數(shù)和（1）的頂點數(shù)相等，所以（3）還是（1）的生成子圖。類似地，（5）、（6）是（4）的子圖，（6）是（4）的生成子圖。生成子圖一定是子圖，但是子圖不一定是生成子圖，并且每個圖都是本身的子圖

第二節(jié)

歐拉圖及其應(yīng)用02第二節(jié)歐拉圖及其應(yīng)用引例1

(設(shè)計區(qū)間公交車路線)某運輸管理部門在設(shè)計一個新的區(qū)間公交系統(tǒng)，來運送城市商業(yè)區(qū)的顧客,具體地圖如圖4-10所示，為了提高公交車的運行效率，他們希望能夠設(shè)計一條恰好通過商業(yè)區(qū)每條道路一次的運行路線，并且最終回到初始位置。圖4-10商業(yè)區(qū)地圖第二節(jié)歐拉圖及其應(yīng)用解：將每一個道路交叉口用一個頂點表示，連接兩個交叉口的道路用一條邊表示，這樣我們就可以將地圖模擬成圖4-11所示。圖4-11商業(yè)區(qū)模擬圖

從而將問題轉(zhuǎn)化為在圖4-11中找到一條從頂點A出發(fā)，走遍圖中每條邊一次且僅一次的回路。第二節(jié)歐拉圖及其應(yīng)用概念4經(jīng)過圖中所有邊一次且僅一次的路稱為歐拉路。起點和終點是同一頂點的歐拉路稱為歐拉回路。包含歐拉回路的圖稱為歐拉圖，包含歐拉路但不包含歐拉回路的圖稱為半歐拉圖。

例如，在圖4-12中，路徑ABCDEFBEA包含了圖中的所有邊，并且路徑中沒有重復的邊，所以路徑ABCDEFBEA是一條長度為8的歐拉路，它也是一條歐拉回路，因為它的起點和終點都在同一個頂點。圖4-12第二節(jié)歐拉圖及其應(yīng)用概念5一個頂點所關(guān)聯(lián)的邊(即以該頂點為端點的邊)的條數(shù)，稱為該頂點的度數(shù)。度數(shù)為奇數(shù)的頂點稱為奇頂點，度數(shù)為偶數(shù)的頂點為偶頂點。

例如，在圖4-13中，頂點A、B、D、E、F的度數(shù)均為2，因為與這些頂點關(guān)聯(lián)的邊都是兩條。類似地，因為與頂點C、G相連的邊為3條，所以頂點C、G的度數(shù)為3。頂點A、B、D、E、F是偶頂點，頂點C、G是奇頂點。圖4-13第二節(jié)歐拉圖及其應(yīng)用

歐拉圖判定定理一個圖G是歐拉圖的充分必要條件是圖G是連通圖且無奇頂點。

半歐拉圖判斷定理一個圖G是半歐拉圖的充分必要條件是圖G是連通圖且剛好有兩個奇頂點。半歐拉圖對應(yīng)的歐拉路必定以兩個奇頂點為端點。例4請判斷下面的兩個圖是否為歐拉圖或半歐拉圖？解（a）是一個連通圖，但是圖中含有四個奇頂點，根據(jù)判定定理，（a）既不

是歐拉圖也不是半歐拉圖。（b）是連通圖并且圖中每個頂點都是偶頂點，所以（b）是一個歐拉圖。第二節(jié)歐拉圖及其應(yīng)用例5(螞蟻比賽問題)甲、乙兩只螞蟻分別位于頂點A、B處。假設(shè)圖中邊的長度是相等的，甲、乙進行比賽，從它們所在頂點出發(fā)，走遍圖中的所有邊，最后到達頂點C。如果它們的速度相同，請問誰先到達目的地？圖4-16螞蟻比賽圖解

圖4-16中僅有兩個奇頂點A、C，根據(jù)半歐拉圖判定定理，存在從A到C的歐拉路，螞蟻甲走到C只需要走一條歐拉路，邊數(shù)為9條。而螞蟻乙要想走完所有的邊到達C，至少要先走一條邊到達A，再走一條歐拉路，故螞蟻乙至少要走10條邊才能到達C點，因此，在速度相同的情況下，螞蟻甲先到達目的地。第二節(jié)歐拉圖及其應(yīng)用

Fleury算法在一個歐拉圖中，我們可以按照下面的步驟尋找歐拉回路：從圖中任意一個頂點開始，運用下面的規(guī)則連續(xù)地通過各邊：（1）經(jīng)過一條邊后，把它擦掉。如果一個頂點的所有邊都被擦掉，那么也將這個頂點擦掉。（2）當且僅當沒有其他的選擇時經(jīng)過一座橋。例6利用Fleury算法在圖4-11中尋找到一條歐拉回路。解

第一步：從頂點A開始，走過邊AH，并把它擦掉。如圖4-17所示。第二節(jié)歐拉圖及其應(yīng)用第二步：經(jīng)過邊HG和GF，到達F點。擦掉邊HG和GF，而且所有連接頂點G的邊都被擦掉了，所以把頂點G也擦掉。目前的路是AHGF。如圖4-18所示。第三步：經(jīng)過邊FE、ED、DC，并擦去它們和頂點E，此時到達頂點C的路是AHGFEDC，如圖4-19所示。第四步：現(xiàn)在邊CB是一座橋，但是除了它沒有別的選擇，沿著邊CB連續(xù)通過BD、DI、IF、FH、HI、IB、BA回到頂點A，最終的回路是AHGFEDCBDIFHIBA。如果運輸管理部門沿著這條回路來設(shè)計公交車的運行路線，就可以每條路只走一次來提高運行效率。第二節(jié)歐拉圖及其應(yīng)用例7一個郵遞員投遞信件要走的街道如圖4-20所示，圖中的數(shù)字表示各條街道的千米數(shù)，他從郵局A出發(fā)，要走遍各街道，最后回到郵局。怎樣走才能使所走的行程最短？全程多少千米？圖4-20街道示意圖解

圖中頂點B、D、E、F、G、H、I、J、K、L均是奇頂點，根據(jù)歐拉圖判定定理，圖4-20不是歐拉圖。因此，郵遞員要想把每條街道只走一遍然后回到郵局是不可能實現(xiàn)的，他必須重復走一些街道。如果郵遞員想要行程最短，他重復走的街道數(shù)越少越好、越短越好。第二節(jié)歐拉圖及其應(yīng)用

因為歐拉回路是一條通過圖中每條邊一次且僅一次的路，不存在行程的長短，所以問題轉(zhuǎn)化為如何在圖4-20中添加邊，使添加的邊的長度之和最短，且消除圖4-20中所有的奇頂點。圖4-20有10個奇頂點，至少添加5條邊，故一個使長度之和最短的添加邊的方案如圖4-21所示。圖4-21接下來，我們可利用Fleury算法在圖4.21中找到一條歐拉回路，比如ABCDJMLKNGHKLIHIJDEBEFGFA，這是一條郵遞員行程最短的回路，最短行程為34千米。

第三節(jié)

樹及其應(yīng)用03第三節(jié)樹及其應(yīng)用例12(道路掃雪問題)圖4-22表示的是某地區(qū)的6個鄉(xiāng)鎮(zhèn)之間的公路交通網(wǎng)絡(luò)。在冬天為了保持道路通暢，公路部門需要經(jīng)常掃雪。為了提高效率，公路部門希望只掃盡可能少的道路上的雪，但是又能確保任何兩個鄉(xiāng)鎮(zhèn)之間都存在一條干凈的道路，請問公路部門該如何設(shè)計掃雪路線？第三節(jié)樹及其應(yīng)用解

要設(shè)計一條掃雪路線，只需要在圖4-22的基礎(chǔ)之上刪掉一些邊，來構(gòu)建一個包含所有頂點并且邊數(shù)最少的連通子圖。不難發(fā)現(xiàn)，公路部門至少需要掃除其中5條道路上的雪，才能保證任何兩個鄉(xiāng)鎮(zhèn)之間有一條干凈的道路，其中的一個清掃方案如下圖所示。

需要注意的是，上圖只是給出了一個道路條數(shù)最少的方案，如果需要求清

掃總里程最短的方案，則需要進一步知道每一條道路的里程信息。第三節(jié)樹及其應(yīng)用概念6連通而不含回路的無向圖稱為無向樹，簡稱樹。如果一個有向圖在不考慮邊的方向時是一棵樹，則稱這個有向圖為有向樹。例8在圖4-23中哪些圖是樹？解

圖（a）是一顆無向樹，因為是無向連通圖且沒有回路。圖（b）是一棵有向樹，因為在不考慮邊的方向時是一棵樹，故是一棵有向樹。圖（c）不是樹，因為存在回路，比如回路ebade。圖（d）不是樹，因為不是連通圖。第三節(jié)樹及其應(yīng)用概念7若圖G的生成子圖是一棵樹，則稱這棵樹為圖G的生成樹。

破圈法：（1）在圖中找到一條回路，并把該回路中的某一條邊刪掉，使它不再構(gòu)成回路。（2）重復步驟（1），直到恰好把圖中所有回路都消除掉。如何尋找生成樹？第三節(jié)樹及其應(yīng)用例9找出下圖4-24的一棵生成樹。圖4-24解

因為樹中不能含有回路的，所以要找到圖的一棵生成樹，就必須把圖中的所有回路消除掉，可以通過刪除一條回路中的邊來消除這條回路并且保持圖是連通的。在圖4-24中，首先，邊ae是回路aefb的一條邊，可以刪除這條邊來消除回路aefb，如圖4-25（a）所示。其次，刪除邊ef，消除回路efge，如圖4-25（b）。最后，刪除邊cg，消除回路cgfc,如圖4-25（c）。至此，圖中不再包含回路，這樣就得到了圖4-24的一棵生成樹。第三節(jié)樹及其應(yīng)用圖4-25

在消除回路的過程中，只要確保圖是連通的，可以刪除掉回路中的任意一條邊，故一個圖的生成樹不唯一。例如，圖4-26所示的每一棵樹都是圖4-24的生成樹。圖4-26第三節(jié)樹及其應(yīng)用

每邊均賦予權(quán)的圖稱為帶權(quán)圖。概念8帶權(quán)圖的總權(quán)值最小的生成樹稱為最小生成樹。

克魯斯特爾算法

（1）去掉圖中的所有邊，將圖置于只有n個頂點的初始狀態(tài)，并將圖中的邊按其權(quán)值由小到大進行排序。

（2）選取權(quán)值最小的邊，若將該邊加入到圖中，不與已選取的邊構(gòu)成回路，則將此邊加入到圖中，否則舍去此邊而選取下一條權(quán)值最小的邊，依次類推，直到構(gòu)成一棵樹。第三節(jié)樹及其應(yīng)用例10一個公司計劃通過租用電話線來建立一個通信網(wǎng)絡(luò)，以便連接A、B、C、D、E五個計算機中心。但是每兩個計算機中心之間的電話線租用費用不相同，如圖4-29所示。那么該公司應(yīng)當建立哪些連接，以便保證每個計算機中心都在這個通信網(wǎng)絡(luò)中，并且使得構(gòu)建網(wǎng)絡(luò)的總成本最小？圖4-27電話線租賃費用圖第三節(jié)樹及其應(yīng)用解

要使得構(gòu)建網(wǎng)絡(luò)的總成本最小，實際上就是要找到一棵最小生成樹。利用克魯斯特爾算法尋找最小生成樹。第一步：去掉圖中的所有邊，如圖4-28(a)。第二步：選擇權(quán)值最小的邊CE添加到圖中，如圖4-28(b)。第三步：然后在剩下的邊中，依次選取權(quán)值為800的邊DE和權(quán)值為900的邊AB添加進圖中，如圖4-28(c)。第四步：接下來，再選取權(quán)值最小的邊CD，但是如果選擇CD的話，在圖中就會形成回路，故舍棄邊CD。在剩下的邊中選擇權(quán)值最小的邊AC。圖4-28克魯斯特爾算法構(gòu)造生成樹

此時，所有頂點都已經(jīng)連接在圖中了，圖4-29(d)就是我們要找的最小生成樹。對應(yīng)地，連接5個計算機中心的網(wǎng)絡(luò)總成本為700+800+900+1200=3600(元)。第三節(jié)樹及其應(yīng)用概念9根樹是指定一個頂點作為樹根并且每條邊的方向都離開根的樹。通常一顆根樹可以看成一顆家族樹。

(1)若結(jié)點a到結(jié)點b有一條邊,則稱b是a的兒子,a是b的父親;

(2)若b和c為同一個結(jié)點的兒子,則稱b和c是兄弟;

根樹中，沒有子女的頂點稱為樹葉，有子女的頂點稱為內(nèi)點，內(nèi)點和樹根統(tǒng)稱為分支點。第三節(jié)樹及其應(yīng)用例11(計算機文件系統(tǒng)圖)計算機存儲器中的文件可以組織成目錄，目錄可以包含文件和子目錄，根目錄包含整個文件系統(tǒng)。因此，文件系統(tǒng)可以表示成根樹，其中樹根表示根目錄，內(nèi)點表示文件或空目錄。在圖4-29（1）中表示了一個這樣的文件系統(tǒng)，在該系統(tǒng)中，文件khr屬于目錄rje。圖4-30一個計算機文件系統(tǒng)圖第三節(jié)樹及其應(yīng)用

根樹可以用來為決策問題建立模型，其中一系列決策將生成一個解。在這種根樹中，每個內(nèi)點都對應(yīng)著一次決策，這些頂點的子樹都對應(yīng)著該決策的每種可能后果，這樣的根樹稱為決策樹。例12假定有重量相同的7枚硬幣和重量較輕的一枚偽幣。為了用一架天平確定

這8枚硬幣中哪個是偽幣，需要稱重多少次。

解在天平上每次稱重結(jié)果只有三種可能性。分別是：兩個托盤有相同的重量、第一個托盤較重或第二個托盤較重。所以，稱重序列的決策樹是一顆3元樹。在決策樹里至少有8片樹葉，這是因為有8種可能的后果（因為每枚硬幣都可能是較輕的偽幣），而每種可能的后果必須至少用一片樹葉來表示。接下來，我們建立如圖4-30所示的決策樹。圖4-30找出偽幣位置的決策樹第三節(jié)樹及其應(yīng)用例13有三個數(shù)a、b、c，如何建立決策樹來給這三個數(shù)按從大到小排序。解兩個數(shù)a、b比較大小只有兩種可能的情況：a大或者b大；這也就是說每次決策都會出現(xiàn)兩種可能的情況，依此，我們可以建立如圖4-31所示的決策樹。圖4-31排序三個不同元素的決策樹

從圖4-31中，我們可以看到a、b、c三個數(shù)排序的六種可能的排序結(jié)果。在決策過程中，最好的情況是只需要做兩次決策就能給這3個數(shù)排序，最壞的情況是需要做3次決策才能給這3個數(shù)排序。

第四節(jié)

用PERT圖制定工作計劃04第四節(jié)用PERT圖制定工作計劃PERT（ProgramEvaluationandReviewTechnique）圖也稱“計劃評審技術(shù)”，它通過建立有向圖模型來描述一個項目的任務(wù)網(wǎng)絡(luò)。不僅可以表達子任務(wù)的計劃安排，還可以在任務(wù)計劃執(zhí)行過程中估計任務(wù)完成的情況，分析某些任務(wù)完成情況對全局的影響，找出影響全局的區(qū)域和關(guān)鍵任務(wù),以便及時采取措施，確保整個項目的完成。例14(太空移民計劃)美國國會授權(quán)科學委員會制定一個計劃來建立太空居住基地表4-3中列出了要完成工程的十項主要任務(wù)和每一項任務(wù)要完成的時間；表4-4中列出了任務(wù)的先后順序，請構(gòu)建太空移民計劃的PERT圖。第四節(jié)用PERT圖制定工作計劃解

我們將按如下步驟建立PERT圖：

（1）用頂點代表每一個任務(wù)，頂點中包含那個任務(wù)要完成所需要的時間；

（2）從頂點X向頂點Y畫有向邊，表示頂點X所代表的任務(wù)必須在頂點Y所代表的任務(wù)之前完成。根據(jù)表4-3、表4-4中的數(shù)據(jù)，我們可以建立如圖4-32所示的太空移民計劃的PERT圖。結(jié)合圖4-32，可以很容易看出各個任務(wù)所需要的時間和完成任務(wù)的先后順序，例如，訓練構(gòu)建工人任務(wù)必須在裝配外殼任務(wù)之前完成，安裝生命維持系統(tǒng)任務(wù)必須在建立生命維持系統(tǒng)之后等等。圖4-32太空移民計劃的PERT圖第四節(jié)用PERT圖制定工作計劃

僅僅畫出一個項目的PERT圖還不夠，我們還要能夠利用PERT圖來制定工作計劃以及對項目的各個子任務(wù)進行分析等。例15繼續(xù)例14，作為委員會成員，他們希望知道在空間基地中訓練移民的最早時間。解根據(jù)圖4-32，我們很容易看到從開始到訓練移民的路徑一共有3條，分別是：（1）開始

招募移民

訓練移民；（2）開始

建筑外殼

訓練移民；（3）開始

建筑生命維持系統(tǒng)

訓練移民。

通過圖4-32中頂點的數(shù)據(jù)，我們知道在訓練移民之前的3條路徑需花費的時間分別是：12個月、8個月和14個月，路徑（3）需花費的時間最長。根據(jù)任務(wù)的先后順序，建立生命維持系統(tǒng)必須要在訓練移民之前完成，所以，必須在工程的第15個月才能開始訓練移民。第四節(jié)用PERT圖制定工作計劃概念14假設(shè)T是PERT圖中的一個任務(wù)，考慮從開始到T的所有有向路徑，計算出每一條路徑所需要的時間，則需要最長時間完成的路徑稱為臨界路。

在PERT圖中，如何為一項任務(wù)T安排一個開始時間呢？

（1）列出從開始到任務(wù)T的所有路徑，并找出任務(wù)T的臨界路。（2）用臨界路的時間減去任務(wù)T所需要的時間，就得到安排任務(wù)T之前所容許

的時間。步驟：第四節(jié)用PERT圖制定工作計劃例16繼續(xù)例14，試安排太空移民計劃各項任務(wù)開始時刻表。解根據(jù)圖4-32中，找出從開始到測試系統(tǒng)的所有路徑如下：（1）開始

訓練構(gòu)建工人

裝配外殼

安裝太陽能系統(tǒng)

測試系統(tǒng)（2）開始

建筑外殼

裝配外殼

安裝太陽能系統(tǒng)

測試系統(tǒng)（3）開始

建筑外殼

裝配外殼

安裝生命維持系統(tǒng)

測試系統(tǒng)（4）開始

建造生命維持系統(tǒng)

安裝生命維持系統(tǒng)

測試系統(tǒng)圖4-33測試系統(tǒng)安排臨界路第四節(jié)用PERT圖制定工作計劃

這條臨界路需要22個月才能到達測試系統(tǒng)，因此，測試系統(tǒng)必須安排在第23個月開始。依次類推，我們可以得到太空移民計劃中各項任務(wù)開始的時刻表4-5。

表4-5太空居住基地任務(wù)時刻表第四節(jié)用PERT圖制定工作計劃例17(運用PERT組織一場音樂會)假設(shè)你負責組織一場音樂會來籌集善款援助在最近一次地震中的災(zāi)民。你的工作就是制定一項計劃在最短的時間內(nèi)完成這個項目。這個項目的各個任務(wù)完成所需時間及其任務(wù)間的關(guān)系見表4-6。表4-6音樂會項目任務(wù)表第四節(jié)用PERT圖制定工作計劃解

首先根據(jù)表4-6構(gòu)建音樂會項目的PERT圖，如圖4-34所示。圖4-34音樂會項目的PERT圖

通過尋找從開始到各個子任務(wù)的臨界路，我們可以得到音樂會項目的任務(wù)時刻表4-7。同時，我們從PERT圖4-34中還可以發(fā)現(xiàn)，從開始到結(jié)束的臨界路為“開始

討論商人對廣告的支持

請演員

拍音樂會廣告

結(jié)束”，此臨界路的時間總和為9周，這意味著整個音樂會項目最少需要9個月才能全部完成。表4-7音樂會項目任務(wù)開始時刻表謝謝！最

優(yōu)

化

問

題

《應(yīng)用數(shù)學基礎(chǔ)》第五章引

言

在日常生活、經(jīng)濟管理和科學研究等領(lǐng)域，人們經(jīng)常會遇到一類決策問題：在一系列客觀或主觀限制條件下，尋求使所關(guān)注的指標達到最優(yōu)(最大或最小)的決策。例如，資源分配要在有限資源約束下，制定最優(yōu)分配方案，使資源產(chǎn)生的總效益最大；生產(chǎn)計劃要按照產(chǎn)品生產(chǎn)流程和市場需求，制定原料、零件和部件的最佳訂購時間點，盡量降低生產(chǎn)成本使利潤最高；運輸方案要在滿足物資需求和裝載條件下，安排從各供應(yīng)點到需求點的最優(yōu)路線和運量，使運輸總費用最低等。上述幾類決策問題通常稱為最優(yōu)化問題(簡稱為優(yōu)化問題)，本章將簡單介紹優(yōu)化問題的數(shù)學模型，單變量和多變量優(yōu)化問題的建模與求解等知識，為我們以后的工作和生活提供基本的優(yōu)化思想。

第一節(jié)

優(yōu)化問題數(shù)學模型01第一節(jié)優(yōu)化問題數(shù)學模型

引例1設(shè)某產(chǎn)品的總成本(單位：元)函數(shù)為

產(chǎn)量，單位：千克)，求當產(chǎn)量為多少時，該產(chǎn)品的平均成本最小，最小平均成本是多少？解該問題的目標是平均成本最小，設(shè)平均成本為，則于是，建立該問題的數(shù)學模型如下：

一、幾個引例

引例2

給定一條1米長的鐵絲，要求將其彎成一個矩形，使得該矩形的面積最大。

目標函數(shù)

約束條件借助EXCEL的“規(guī)劃求解”工具，易求得米時，矩形面積最大,最大面積為第一節(jié)優(yōu)化問題數(shù)學模型

產(chǎn)品Ⅰ產(chǎn)品Ⅱ日允許消耗量設(shè)

備A128（臺時）原材料B3012（100千克）原材料C0515（100千克）

引例3某企業(yè)在計劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知每生產(chǎn)100千克產(chǎn)

品所需設(shè)備A及原材料B、C的消耗如表5-1所示。表5-1生產(chǎn)設(shè)備和原材料消耗表

已知每生產(chǎn)100千克的產(chǎn)品Ⅰ可獲利2萬元，生產(chǎn)100千克的產(chǎn)品Ⅱ可獲利5萬元，問怎樣安排生產(chǎn)，才能使每天獲得的利潤最大？第一節(jié)優(yōu)化問題數(shù)學模型

同理，因受原材料B、C的限制，可以得到以下兩個不等式第一節(jié)優(yōu)化問題數(shù)學模型

綜上所述，建立生產(chǎn)計劃問題的數(shù)學模型為：目標函數(shù)

約束條件通過圖解法或者借助EXCEL的“規(guī)劃求解”工具，可得最優(yōu)解為最優(yōu)值為19。第一節(jié)優(yōu)化問題數(shù)學模型引例4某機械廠需要長80厘米的鋼管800根，長60厘米的鋼管200根，這兩種長度不同的鋼管由長200厘米的鋼管截得。工廠該如何下料，使得用料最??？解對于該問題，首先必須找到可行的下料方式。由1根長200厘米的鋼管去截得80厘米與60厘米兩種型號的鋼管，共有三種截取方法。第一種下料方式：一根長200厘米的鋼管截得長80厘米的鋼管2根；第二種下料方式：一根長200厘米的鋼管截得長80厘米的鋼管1根，長60厘米的鋼管2根；第三種下料方式：一根長200厘米的鋼管截得長60厘米的鋼管3根。

第一節(jié)優(yōu)化問題數(shù)學模型對于所需長80厘米的鋼管：對于所需長60厘米的鋼管：

綜上所述，得鋼管下料問題的數(shù)學規(guī)劃模型為：目標函數(shù)

約束條件借助EXCEL的“規(guī)劃求解”工具，可得最優(yōu)解為第一節(jié)優(yōu)化問題數(shù)學模型二、優(yōu)化問題的數(shù)學模型優(yōu)化問題的數(shù)學模型一般包含三個要素：決策變量、目標函數(shù)和約束條件。1.決策變量在優(yōu)化過程中經(jīng)過逐步調(diào)整、最后達到最優(yōu)值的參數(shù)，稱為決策變量(簡稱變量)2.目標函數(shù)反映變量間相互關(guān)系的數(shù)學表達式稱為目標函數(shù)，其值的大小可以用來評價優(yōu)化方案的好壞。一般可表示為特別地，如果優(yōu)化問題只有一個目標函數(shù)，稱為單目標函數(shù)，如果優(yōu)化問題同時追求多個目標，則該問題的目標函數(shù)稱為多目標函數(shù)。第一節(jié)優(yōu)化問題數(shù)學模型3.約束條件變量間應(yīng)該遵循的限制條件的數(shù)學表達式稱為約束條件或約束函數(shù)。約束條件一般可表示為：不等式約束等式約束其中，不帶約束條件的優(yōu)化問題稱為無約束最優(yōu)化問題。第一節(jié)優(yōu)化問題數(shù)學模型4.優(yōu)化問題數(shù)學模型的表示形式(5.1)式中滿足所有約束條件的解稱為可行解，可行解的集合稱為可。行域。求解優(yōu)化問題(5.1)，就是從可行域中找到一個解，使目標函數(shù)取得最大值(或最小值)，這樣的解稱為最優(yōu)解，相應(yīng)的目標函數(shù)值稱為最優(yōu)值。第一節(jié)優(yōu)化問題數(shù)學模型5.優(yōu)化問題的基本類型優(yōu)化模型可以從不同的角度進行分類。根據(jù)決策變量的數(shù)量：

可以分為單變量優(yōu)化問題和多變量優(yōu)化問題根據(jù)決策變量在目標函數(shù)與約束條件中最高次項的次數(shù)是否大于1：可以分為線性規(guī)劃問題和非線性規(guī)劃問題根據(jù)決策變量是否要求取整數(shù)：可以分為整數(shù)規(guī)劃問題和連續(xù)優(yōu)化問題根據(jù)有無約束條件：可以分為無約束的優(yōu)化問題和有約束的優(yōu)化問題第一節(jié)優(yōu)化問題數(shù)學模型

第二節(jié)

單變量優(yōu)化問題02第二節(jié)單變量優(yōu)化問題一、單變量優(yōu)化問題

閉區(qū)間上的連續(xù)函數(shù)一定存在最大值和最小值，統(tǒng)稱為最值。顯然，最值只能在極值點或區(qū)間端點取得，而極值點的所有可能點只能是函數(shù)的駐點(使函數(shù)的導數(shù)為零的點)和函數(shù)導數(shù)不存在的點。因此，求函數(shù)的最值時只需考慮這三類點的函數(shù)值。

按從小到大記為3.求最大值和最小值，即計算在點的函數(shù)值，并比較大小。第二節(jié)單變量優(yōu)化問題例1

求函數(shù)，在[a,b]上的最大值和最小值。

第二步，求可能的最值點，令，解得即所有可能的最值點為第三步，求最大值和最小值，計算各可能點的函數(shù)值，比較大小，得函數(shù)的最大值為，最小值為第二節(jié)單變量優(yōu)化問題例2求函數(shù)在[0,9]上的最大值和最小值。

第二步，求可能的最值點，令，但當時，無意義，

第三步，求最大值和最小值，計算各可能點的函數(shù)值比較大小，得函數(shù)的最大值為，最小值為第二節(jié)單變量優(yōu)化問題例3某租戶有100間房子出租，若每間租金定為200元能夠全部租出去，但每間每增加10元租金就有一間租不出去，且每租出去一間，就需要增加20元管理費。問租金定為多少才能獲得最大利潤？

,由題意得，租出的房間數(shù)為

第二節(jié)單變量優(yōu)化問題

第二節(jié)單變量優(yōu)化問題求導得令得唯一可能的最值點即當每間房子的出租價格定為610元時，可獲得最大利潤。由于該實際問題確實存在最大值，因此利潤函數(shù)在有最大值。第二節(jié)單變量優(yōu)化問題二、限制條件下雙變量優(yōu)化問題接下來我們討論在限制條件下二元函數(shù)的優(yōu)化問題。例4求函數(shù)在限制條件下的最小值。解由，可得故求導數(shù)，得令，得（1）當時，，在區(qū)間內(nèi)單調(diào)遞減；（2）當時，，在區(qū)間內(nèi)單調(diào)遞增。因此是最小值點此時故在限制條件的最小值為第二節(jié)單變量優(yōu)化問題

第三節(jié)

多變量優(yōu)化問題03第三節(jié)多變量優(yōu)化問題一、線性規(guī)劃1.線性規(guī)劃問題的一般形式(1)有一組決策變量(2)存在一組約束條件，且表示約束條件的數(shù)學式子都是線性等式或不等式。(3)有一個目標函數(shù)，且目標函數(shù)是線性函數(shù)。

線性規(guī)劃模型的一般形式：第三節(jié)多變量優(yōu)化問題2.圖解法例5求解引例3對應(yīng)的線性規(guī)劃模型。

因為，所以滿足約束條件的點落在第一象限及坐標軸的正半軸上。在坐標系中畫出直線，這條直線將坐標平面分成兩個半平面，滿足約束條件的所有點落在直線上及原點所在一側(cè)的半平面內(nèi)。割線的原點所在一側(cè)的半平面內(nèi)；同理，滿足約束條件的所有點位于直線上及以該直線為分滿足約束條件的所有點位于直線原點所在一側(cè)的半平面內(nèi)；上及以該直線為分割線的第三節(jié)多變量優(yōu)化問題上述三個平面點集在第一象限的交集即為可行域，如下圖5-1所示可行域內(nèi)任意一點的坐標都是該線性規(guī)劃問題的可行解。圖5-1唯一最優(yōu)解情形第三節(jié)多變量優(yōu)化問題(2)繪制目標函數(shù)等值線.

，畫出相應(yīng)的等值線。

的值越大(3)確定最優(yōu)解最優(yōu)解必須是滿足約束條件，并使目標函數(shù)達到最優(yōu)值的解，故的值只能在可行域中去尋找。當?shù)戎稻€移動到與可行域相切時，切點就是代表最優(yōu)解的點。

和的交點，坐標為，所以，最優(yōu)解為最優(yōu)值為19第三節(jié)多變量優(yōu)化問題圖解法的基本步驟如下：

（1）根據(jù)約束條件畫出可行域；（2）根據(jù)目標函數(shù)的表達式畫出目標函數(shù)等值線，并標明目標函數(shù)值增加的方向；（3）在可行域中，尋求符合要求的等值線與可行域邊界相切的點或

點集，并求出最優(yōu)解和最優(yōu)值。第三節(jié)多變量優(yōu)化問題例6

求解線性規(guī)劃問題第三節(jié)多變量優(yōu)化問題

,當?shù)戎稻€向右上方移動時，圖5-2無窮多最優(yōu)解情形

這時在B點、C點及BC線段上的任意點都使目標函數(shù)值達到最大，即該線性規(guī)劃問題有無窮多最優(yōu)解，若取最優(yōu)點B，則最優(yōu)解為最優(yōu)值為16。第三節(jié)多變量優(yōu)化問題例7求解線性規(guī)劃問題第三節(jié)多變量優(yōu)化問題

圖5-3無最優(yōu)解情形

容易看出，等值線離原點越遠，目標函數(shù)值越大。

由于問題可行域無界，等值線可以無限制地向右上方移動，即目標函數(shù)值可以增大至無窮大。該情況下稱問題具有無界解或無最優(yōu)解。第三節(jié)多變量優(yōu)化問題例8

求解線性規(guī)劃問題第三節(jié)多變量優(yōu)化問題

它在第一象限的部分表示為區(qū)域1；

它在第一象限的部分表示為區(qū)域2；

容易看出區(qū)域1與區(qū)域2沒有公共部分，即該問題的可行域為空集，所以此問題沒有可行解，當然也就沒有最優(yōu)解。圖5-4無可行解情形第三節(jié)多變量優(yōu)化問題3.線性規(guī)劃問題解的性質(zhì)

圖解法雖然只能用來求解只含兩個變量的線性規(guī)劃問題，但通過它的解題思路和幾何直觀所得到的一些性質(zhì)，對線性規(guī)劃問題解的理解有很大的幫助。

含兩個變量的線性規(guī)劃問題的解有下面四種情況：

（1）有可行解且有唯一最優(yōu)解，如例5；

（2）有可行解且有無窮多最優(yōu)解，如例6；

（3）有可行解但無最優(yōu)解，如例7；

（4）無可行解，如例8。上述結(jié)論可以推廣到變量多于兩個的一般情形，得線性規(guī)劃問題解的性質(zhì)如下：性質(zhì)1求解線性規(guī)劃問題時，解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解。性質(zhì)2若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮多最優(yōu)解）一定可以在基可行解(頂點)中找到。第三節(jié)多變量優(yōu)化問題4.使用EXCEL求解線性規(guī)劃問題

當變量多于兩個時，線性規(guī)劃問題不能用圖解法，此時，我們一般借助軟件求解。本章將介紹使用EXCEL2007(或以上版本)的“規(guī)劃求解”工具求解簡單規(guī)劃問題。EXCEL的“規(guī)劃求解”工具可以解決最多有200個變量，100個外在約束和400個簡單約束(決策變量整數(shù)約束的上下邊界)的線性規(guī)劃與非線性規(guī)劃問題。例9求解線性規(guī)劃問題：第三節(jié)多變量優(yōu)化問題解

第一步：輸入數(shù)據(jù)。為了使輸入的線性規(guī)劃問題數(shù)據(jù)清晰明了，一般把工作表分成若干區(qū)域(具體根據(jù)實際情況確定)，并用關(guān)鍵詞加以標注。如本例中，區(qū)域B1:D1表示目標函數(shù)系數(shù)，區(qū)域B2:D2表示決策變量值，區(qū)域B4:D6表示約束條件左端系數(shù)，區(qū)域E4:E6表示約束條件左端值，區(qū)域F4:F6表示約束條件右端值，區(qū)域F1表示目標函數(shù)值。具體如圖5-5所示。圖5-5數(shù)據(jù)輸入第三節(jié)多變量優(yōu)化問題第二步：描述約束條件左端和目標函數(shù)表達式。

在E4單元格中輸入“=$B$2*B4+$C$2*C4+$D$2*D4”，并拖曳至E6單元格。

在F1單元格中輸入“=B1*B2+C1*C2+D1*D2”，由于EXCEL默認的決策變量初始值等于0，故描述的目標函數(shù)和約束條件左端值均等于0。如圖5-6所示。圖5-6描述約束條件左端和目標函數(shù)表達式第三節(jié)多變量優(yōu)化問題第三步：設(shè)置求解參數(shù)。單擊【數(shù)據(jù)】中的【規(guī)劃求解】命令，在彈出的規(guī)劃求解對話框中輸入各項參數(shù)．設(shè)置目標單元格和可變單元格在“規(guī)劃求解參數(shù)”對話框中選中“最大值”前的單選按鈕，設(shè)置目標單元格為“$F$1”，可變單元格為“$B$2:$D$2”．添加約束條件單擊“規(guī)劃求解參數(shù)”對話框中的【添加】按鈕，打開【添加約束】對話框，單擊單元格引用位置文本框，然后選定工作表中的E4：E6單元格，則在文本框中顯示“$E$4:$E$6”，選擇“<=”約束條件；單擊約束值文本框，然后選定工作表中的F4:F6單元格．選擇求解方法因為是線性規(guī)劃問題，所以選擇求解方法為“單純線性規(guī)劃