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

用

圖表示

關(guān)

系

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

言

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

第一節(jié)

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

引例1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第二節(jié)

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

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

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

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

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

歐拉圖判定定理一個(gè)圖G是歐拉圖的充分必要條件是圖G是連通圖且無奇頂點(diǎn)。

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

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

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

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

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

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

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

第三節(jié)

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

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

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

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

圖（a）是一顆無向樹，因?yàn)槭菬o向連通圖且沒有回路。圖（b）是一棵有向樹，因?yàn)樵诓豢紤]邊的方向時(shí)是一棵樹，故是一棵有向樹。圖（c）不是樹，因?yàn)榇嬖诨芈?，比如回路ebade。圖（d）不是樹，因?yàn)椴皇沁B通圖。第三節(jié)樹及其應(yīng)用概念7若圖G的生成子圖是一棵樹，則稱這棵樹為圖G的生成樹。

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

因?yàn)闃渲胁荒芎谢芈返?，所以要找到圖的一棵生成樹，就必須把圖中的所有回路消除掉，可以通過刪除一條回路中的邊來消除這條回路并且保持圖是連通的。在圖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

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

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

克魯斯特爾算法

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

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

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

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

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

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

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

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

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

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

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

第四節(jié)

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

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

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

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

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

招募移民

訓(xùn)練移民；（2）開始

建筑外殼

訓(xùn)練移民；（3）開始

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

訓(xùn)練移民。

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

在PERT圖中，如何為一項(xiàng)任務(wù)T安排一個(gè)開始時(shí)間呢？

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

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

訓(xùn)練構(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圖制定工作計(jì)劃

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

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

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

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

討論商人對廣告的支持

請演員

拍音樂會(huì)廣告

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

優(yōu)

化

問

題

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

言

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

第一節(jié)

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

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

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

一、幾個(gè)引例

引例2

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

目標(biāo)函數(shù)

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

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

備A128（臺(tái)時(shí)）原材料B3012（100千克）原材料C0515（100千克）

引例3某企業(yè)在計(jì)劃期內(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ù)學(xué)模型

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

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

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

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

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

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

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

第二節(jié)

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

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

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

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

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

第二步，求可能的最值點(diǎn)，令，但當(dāng)時(shí)，無意義，

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

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

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

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

第三節(jié)

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

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

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

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

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

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

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

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

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

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

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

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

容易看出，等值線離原點(diǎn)越遠(yuǎn)，目標(biāo)函數(shù)值越大。

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

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

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

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

容易看出區(qū)域1與區(qū)域2沒有公共部分，即該問題的可行域?yàn)榭占源藛栴}沒有可行解，當(dāng)然也就沒有最優(yōu)解。圖5-4無可行解情形第三節(jié)多變量優(yōu)化問題3.線性規(guī)劃問題解的性質(zhì)

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

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

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

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

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

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

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

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

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

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