chap 5 系統(tǒng)建模與仿真

第五章建模與仿真第一節(jié)系統(tǒng)模型概述第二節(jié)系統(tǒng)建模方法第三節(jié)線性規(guī)劃模型第四節(jié)系統(tǒng)動(dòng)力學(xué)模型第五節(jié)圖與網(wǎng)絡(luò)模型第一節(jié)系統(tǒng)模型概述（一）系統(tǒng)模型的定義與特征（二）使用系統(tǒng)模型的必要性（三）系統(tǒng)模型的分類（四）使用系統(tǒng)模型的好處（一）系統(tǒng)模型的定義與特征1.定義

系統(tǒng)模型是一個(gè)系統(tǒng)某一方面本質(zhì)屬性的描述，它以某種確定的形式(例如文字、符號(hào)、圖表、實(shí)物、數(shù)學(xué)公式等)提供關(guān)于該系統(tǒng)的知識(shí)。系統(tǒng)模型一般不是系統(tǒng)對(duì)象本身，而是現(xiàn)實(shí)系統(tǒng)的描述、模仿或抽象。系統(tǒng)是復(fù)雜的，系統(tǒng)的屬性也是多方面的。對(duì)于大多數(shù)研究目的而言，沒有必要考慮系統(tǒng)的全部屬性系統(tǒng)模型只是系統(tǒng)某一方面本質(zhì)屬性的描述，本質(zhì)屬性的選取完全取決系統(tǒng)工程研究的目的。對(duì)同一個(gè)系統(tǒng)根據(jù)不同的研究目的，可以建立不同的系統(tǒng)模型。例子同一種模型可以代表多個(gè)系統(tǒng)y＝kx(k為常量)幾何上：代表一條通過原點(diǎn)的直線；代數(shù)上；表示比例關(guān)系；設(shè)k＝π，x代表直徑，則y表示圓周長(zhǎng)；設(shè)k表示彈簧剛度，x表示伸長(zhǎng)量，則y表示彈簧力大??；當(dāng)k＝a表示加速度，x＝m表示質(zhì)量，則y表示物體所受外力大小等等。2.特征系統(tǒng)模型反映著實(shí)際系統(tǒng)的主要特征，但它又高于實(shí)際系統(tǒng)而具有同類問題的共性。一個(gè)適用的系統(tǒng)模型應(yīng)該具有如下三個(gè)特征；(1)它是現(xiàn)實(shí)系統(tǒng)的抽象或模仿；(2)它是由反映系統(tǒng)本質(zhì)或特征的主要因素構(gòu)成的；(3)它集中體現(xiàn)了這些主要因素之間的關(guān)系。（二）使用系統(tǒng)模型的必要性人類認(rèn)識(shí)和改造客觀世界的研究方法，一般來說主要有三種：實(shí)驗(yàn)法、抽象法、模型法。實(shí)驗(yàn)法是通過對(duì)客觀事物本身直接進(jìn)行科學(xué)實(shí)驗(yàn)來進(jìn)行研究的，因此局限性比較大。抽象法是把現(xiàn)實(shí)系統(tǒng)抽象為一般的理論概念，然后進(jìn)行推理和判斷，因此這種方法缺乏實(shí)體感，過于概念化。模型法是在對(duì)現(xiàn)實(shí)系統(tǒng)進(jìn)行抽象的基礎(chǔ)上，把它們?cè)佻F(xiàn)為某種實(shí)物的、圖畫的或數(shù)學(xué)的模型，然后通過模型來對(duì)系統(tǒng)進(jìn)行分析、對(duì)比和研究，最終導(dǎo)出結(jié)論。模型法既避免了實(shí)驗(yàn)法的局限性，又避免了抽象法的過于概念化，所以它成為現(xiàn)代工程中一種最常用的研究方法。(1)系統(tǒng)開發(fā)的需要。在開發(fā)一個(gè)新系統(tǒng)時(shí)，由于此時(shí)系統(tǒng)尚未建立，無法直接進(jìn)行實(shí)驗(yàn)，只能通過建造系統(tǒng)模型來對(duì)系統(tǒng)的性能進(jìn)行預(yù)測(cè)，以實(shí)現(xiàn)對(duì)系統(tǒng)的分析、優(yōu)化和評(píng)價(jià)。(2)經(jīng)濟(jì)上的考慮。對(duì)大型復(fù)雜系統(tǒng)直接進(jìn)行實(shí)驗(yàn)，其成本是十分昂貴的，但是使用系統(tǒng)模型就便宜多了。(3)安全上的考慮。對(duì)有些系統(tǒng)(如載人航天飛行器、核電站等)通過直接實(shí)驗(yàn)進(jìn)行分析，往往是很危險(xiǎn)的，有時(shí)甚至是根本不允許的。必要性(4)時(shí)間上的考慮。社會(huì)、經(jīng)濟(jì)、生態(tài)等系統(tǒng)，由于慣性大、反應(yīng)周期很長(zhǎng)，對(duì)其直接進(jìn)行實(shí)驗(yàn)要等若干年以后才能看到結(jié)果，這是系統(tǒng)分析和評(píng)價(jià)所不允許的。而使用系統(tǒng)模型進(jìn)行分析，很快就可得到分析結(jié)果。(5)系統(tǒng)模型容易操作，分析結(jié)果易于理解。有時(shí)對(duì)現(xiàn)實(shí)系統(tǒng)進(jìn)行直接實(shí)驗(yàn)雖然是允許的，而且也不過分費(fèi)時(shí)、費(fèi)錢，但此時(shí)采用系統(tǒng)模型仍然具有優(yōu)越性。必要性（三）系統(tǒng)模型的分類分類原則模型種類1按建模材料不同抽象、實(shí)物2按與實(shí)體的關(guān)系形象、類似、數(shù)學(xué)3按模型表征信息的程度觀念性、數(shù)學(xué)、物理4按模型的構(gòu)造方法理論、經(jīng)驗(yàn)、混合5按模型的功能結(jié)構(gòu)、性能、評(píng)價(jià)、最優(yōu)化、網(wǎng)絡(luò)6按與時(shí)間的依賴程度靜態(tài)、動(dòng)態(tài)7按是否描述系統(tǒng)內(nèi)部特性黑箱、白箱8按模型的應(yīng)用場(chǎng)合通用、專用9數(shù)學(xué)模型的分類（1）按變量形式分確定性、隨機(jī)性、連續(xù)型、離散型（2）按變量之間的關(guān)系分代數(shù)方程、微分方程、概率統(tǒng)計(jì)、邏輯一般分為三類：物理模型、文字模型和數(shù)學(xué)模型（四）使用系統(tǒng)模型的好處(1)是定量分析的基礎(chǔ)。在自然科學(xué)和工程技術(shù)領(lǐng)域里，數(shù)量不準(zhǔn)將導(dǎo)致質(zhì)量低劣；在社會(huì)科學(xué)領(lǐng)域里，沒有定量分析會(huì)使人心中無數(shù)，造成決策失誤，引起不必要的混亂；采用數(shù)學(xué)模型進(jìn)行定量分析已成為當(dāng)代自然科學(xué)和社會(huì)科學(xué)進(jìn)一步發(fā)展的共同要求。(2)是系統(tǒng)預(yù)測(cè)和決策的工具可以利用系統(tǒng)已有的數(shù)據(jù)建立預(yù)測(cè)模型，用來預(yù)測(cè)系統(tǒng)的未來狀態(tài)，為正確決策提供依據(jù)。(3)可變性好，適應(yīng)性強(qiáng)，分析問題速度快，省時(shí)省錢，而且便于使用計(jì)算機(jī)，因此，它是所有模型中使用最廣泛的一種。我們通常所說的系統(tǒng)建模，大多數(shù)情況下都是指建立系統(tǒng)的數(shù)學(xué)模型。好處第二節(jié)系統(tǒng)建模方法系統(tǒng)建模是系統(tǒng)工程人員的重要工作之一系統(tǒng)建模既是一種技術(shù)，又是一種“藝術(shù)”（一）對(duì)系統(tǒng)模型的要求

現(xiàn)實(shí)性、簡(jiǎn)明性、標(biāo)準(zhǔn)化1．現(xiàn)實(shí)性即在一定程度上能夠較好地反映系統(tǒng)的客觀實(shí)際，應(yīng)把系統(tǒng)本質(zhì)的特征和關(guān)系反映進(jìn)去，而把非本質(zhì)的東西去掉，但又不影響反映本質(zhì)的真實(shí)程度。也就是說，系統(tǒng)模型應(yīng)有足夠的精度。精度要求不僅與研究對(duì)象有關(guān)，而且與所處的時(shí)間、狀態(tài)和條件有關(guān)。因此，為滿足現(xiàn)實(shí)性要求，對(duì)同一對(duì)象在不同情況下可以提出不同的精度要求。2．簡(jiǎn)明性在滿足現(xiàn)實(shí)性要求的基礎(chǔ)上，應(yīng)盡量使系統(tǒng)模型簡(jiǎn)單明了，以節(jié)約建模的費(fèi)用和時(shí)間這也就是說，如果一個(gè)簡(jiǎn)單的模型已能使實(shí)際問題得到滿意的解答，就沒有必要去建一個(gè)復(fù)雜的模型，因?yàn)榻ㄔ煲粋€(gè)復(fù)雜的模型并求解是要付出很高代價(jià)的。

3．標(biāo)準(zhǔn)化在建立某些系統(tǒng)的模型時(shí)，如果已有某種標(biāo)準(zhǔn)化模型可供借鑒，則應(yīng)盡量采用標(biāo)準(zhǔn)化模型；或?qū)?biāo)準(zhǔn)化模型加以某些修改，使之適合對(duì)象系統(tǒng)。

以上三條要求往往是相互抵觸的，容易顧此失彼例如，現(xiàn)實(shí)性和簡(jiǎn)明性就常常存在矛盾，如果模型復(fù)雜一些，雖然滿足現(xiàn)實(shí)性要求．但建模和求解卻相當(dāng)閑難，費(fèi)時(shí)、費(fèi)錢，同時(shí)也可能影響標(biāo)準(zhǔn)化的要求為此，必須根據(jù)對(duì)象系統(tǒng)的主體情況妥善處理。一般的處理原則是：力求達(dá)到現(xiàn)實(shí)性，在現(xiàn)實(shí)性的基礎(chǔ)上達(dá)到簡(jiǎn)明性，然后盡可能滿足標(biāo)準(zhǔn)化。（二）系統(tǒng)建模應(yīng)遵循的原則根據(jù)對(duì)系統(tǒng)模型提出的三條要求，可以導(dǎo)出系統(tǒng)建模時(shí)應(yīng)該遵循的四項(xiàng)原則是：切題清晰精度要求適當(dāng)盡量使用標(biāo)準(zhǔn)模型1．切題模型只應(yīng)包括與研究目的有關(guān)的方面，而不是對(duì)象系統(tǒng)的所有方面。例如，對(duì)一個(gè)空運(yùn)指揮調(diào)度系統(tǒng)的研究，建模只需考慮飛機(jī)的飛行航向而無需考慮其飛行姿態(tài)。2．清晰一個(gè)大型復(fù)雜系統(tǒng)是由許多聯(lián)系密切的子系統(tǒng)組成的，因此對(duì)應(yīng)的系統(tǒng)模型也是由許多子模型(或模塊)組成的。在子模型與子模型之間，除了保留研究目的所必要的信息聯(lián)系外，其它的輻合關(guān)系要盡可能減少，以保證模型結(jié)構(gòu)盡可能清晰3．精度要求適當(dāng)建立系統(tǒng)模型，應(yīng)該視研究目的和使用環(huán)境不同，選擇適當(dāng)?shù)木鹊燃?jí)，以保證模型切題、實(shí)用，而又不致花費(fèi)太多。例如，一個(gè)受外力F作用下的物體M，其動(dòng)力學(xué)系統(tǒng)的數(shù)學(xué)模型，在不同使用環(huán)境下有不同精度等級(jí)，應(yīng)該適當(dāng)選擇。（1）當(dāng)物體的運(yùn)動(dòng)速度。足夠小時(shí)，可以忽略空氣阻力的影響，其符合精度要求的數(shù)學(xué)模型為（2）當(dāng)速度v提高到必須考慮空氣阻力的影響時(shí)，則其符合精度要求的數(shù)學(xué)模型為：（3）當(dāng)物體的運(yùn)動(dòng)速度接近于光速3×108m/s時(shí)，按相對(duì)論原理，此時(shí)M將不是常數(shù)，因此其符合精度要求的數(shù)學(xué)模型為:4．盡量使用標(biāo)準(zhǔn)模型在建立一個(gè)實(shí)際系統(tǒng)的模型時(shí)，應(yīng)該首先大量調(diào)閱模型庫(kù)中的標(biāo)準(zhǔn)模型，如果其中某些可供借鑒，不妨先試用一下如能滿足要求，就應(yīng)該使用標(biāo)準(zhǔn)模型，或者盡可能向標(biāo)準(zhǔn)模型靠攏。（三）系統(tǒng)建模的主要方法主要有5種方法：（1）推理法（用于白箱）；（2）實(shí)驗(yàn)法（黑箱或灰箱）；（3）統(tǒng)計(jì)分析法（黑箱，但無法直接實(shí)驗(yàn)）（4）混合法；（5）類似法（建造原系統(tǒng)的類似模型）模擬法：對(duì)那些內(nèi)部結(jié)構(gòu)和特性不很清楚的系統(tǒng)，建立計(jì)算機(jī)仿真模型，模擬實(shí)際系統(tǒng)行為，通過模擬的輸入、輸出結(jié)果，評(píng)價(jià)和確認(rèn)系統(tǒng)模型仿真：是利用模型對(duì)實(shí)際系統(tǒng)進(jìn)行實(shí)驗(yàn)研究系統(tǒng)仿真系統(tǒng)仿真：是通過建立和運(yùn)行計(jì)算機(jī)仿真模型，模仿實(shí)際系統(tǒng)的運(yùn)行狀態(tài)及隨時(shí)間變化規(guī)律，以實(shí)現(xiàn)在計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)的全過程通過對(duì)仿真運(yùn)行過程的觀察和統(tǒng)計(jì)，得到被仿真系統(tǒng)的仿真輸出參數(shù)和基本特性，以此來估計(jì)和推斷實(shí)際系統(tǒng)的真實(shí)參數(shù)和性能系統(tǒng)仿真系統(tǒng)仿真特點(diǎn)

有效的實(shí)驗(yàn)手段，為復(fù)雜系統(tǒng)創(chuàng)造了柔性計(jì)算機(jī)實(shí)驗(yàn)環(huán)境，節(jié)省認(rèn)識(shí)系統(tǒng)運(yùn)行規(guī)律的時(shí)間系統(tǒng)仿真是一種計(jì)算機(jī)仿真實(shí)驗(yàn)，需要較好的仿真軟件支持系統(tǒng)建模仿真過程系統(tǒng)仿真的輸出結(jié)果在仿真過程由軟件自動(dòng)給出需要多次仿真實(shí)驗(yàn)，才能統(tǒng)計(jì)推斷、估計(jì)實(shí)際系統(tǒng)的真實(shí)參數(shù)和性能系統(tǒng)仿真系統(tǒng)仿真優(yōu)點(diǎn)

直接面向?qū)嶋H過程和系統(tǒng)問題，將不確定性作為系統(tǒng)隨機(jī)變量來處理，建立系統(tǒng)內(nèi)部關(guān)系模型，有利于簡(jiǎn)化復(fù)雜并有多種隨機(jī)因素的系統(tǒng)模型求解采用面向?qū)ο蟮慕７治龇椒?，使用人機(jī)友好的計(jì)算機(jī)軟件，有利于分析人員集中精力研究問題的內(nèi)部因素及相互關(guān)系，避免復(fù)雜編程為分析和決策人員提供了有效實(shí)驗(yàn)環(huán)境，有利于他們直接參與調(diào)整模型參數(shù)或結(jié)構(gòu)，選擇滿意方案系統(tǒng)仿真系統(tǒng)仿真的步驟問題描述與定義建立模型：要求面向問題和過程，選擇適當(dāng)?shù)姆抡婺Ｐ团c語言數(shù)據(jù)采集仿真模型確認(rèn)：專家評(píng)價(jià)、統(tǒng)計(jì)檢驗(yàn)、靈敏性分析編程實(shí)現(xiàn)與驗(yàn)證：仿真程序與模型的一致性仿真實(shí)驗(yàn)設(shè)計(jì)：定實(shí)驗(yàn)方案結(jié)果分析系統(tǒng)仿真（四）系統(tǒng)建模者應(yīng)具備的素質(zhì)應(yīng)該具備以下幾方面的能力：（1）對(duì)客觀事物或過程能夠透過現(xiàn)象抓住本質(zhì)，使得對(duì)問題有一個(gè)深刻的理解、清晰的圖景、清楚的層次和明確的輪廓。（2）在數(shù)學(xué)方面應(yīng)有基本訓(xùn)練，要有一定的數(shù)學(xué)修養(yǎng)．并且掌握一套數(shù)學(xué)的思路和方法。（3）具有把實(shí)際問題與數(shù)學(xué)聯(lián)系起來的能力，善于把各種現(xiàn)象中的表面差異撇去，而把本質(zhì)的共性提煉出來。有些數(shù)學(xué)工作者或者實(shí)際工作者，在實(shí)際問題面前感到束手無策，主要就是由于缺乏這種能力，而這種能力在書本上是很難學(xué)到的。應(yīng)該從實(shí)踐中學(xué)，邊干邊學(xué)，逐步積累和培養(yǎng)這種能力。系統(tǒng)建模者應(yīng)該注意避免的四種傾向是：懶、饞、貪、變。懶：沒有詳細(xì)地調(diào)查實(shí)際情況，僅僅根據(jù)一知半解，就隨便假設(shè)，憑想象提出一些公式、數(shù)學(xué)方程和邏輯判斷。結(jié)果：系統(tǒng)模型不能反映系統(tǒng)的實(shí)際情況，所得到的解無用。饞：建模時(shí)要求的數(shù)據(jù)太多，以至提供了全部現(xiàn)有數(shù)據(jù)和經(jīng)過多方努力能夠得到的數(shù)據(jù)也還是“喂不飽”。顯然，這種要求是很難滿足的。貪：企圖把研究問題的一切細(xì)節(jié)、一切因素都要包羅進(jìn)去，以致模型過于復(fù)雜而無法求解。這是由于抓不住問題的本質(zhì)和關(guān)鍵，抓不住主要矛盾所造成的。變：企圖把研究的問題“變”成為適合某種模型。這種改變問題的特征去適合某種模型的作法是一種本末例置的作法，由此而建立起來的模型一點(diǎn)用處也沒有。必須記住的是，最好的模型是一個(gè)實(shí)用的切題的模型，而不是一個(gè)外表漂亮的失真的模型。第三節(jié)數(shù)學(xué)規(guī)劃模型線性規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃整數(shù)規(guī)劃……LP問題及其數(shù)學(xué)模型一、問題的提出二、線性規(guī)劃的數(shù)學(xué)模型三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式四、圖解法第三節(jié)數(shù)學(xué)規(guī)劃模型一、問題的提出例2—1生產(chǎn)計(jì)劃問題某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)甲乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、以及每件產(chǎn)品的獲利如表所示。問該工程如何安排計(jì)劃能使獲利最大?甲乙總資源數(shù)設(shè)備（臺(tái)時(shí)）128原材料A（kg）104原材料B（kg）013獲利（元/件）23一、問題的提出目標(biāo)函數(shù)

滿足約束條件

一、問題的提出共同特征問題的所求均用一組未知變量表出，這些變量稱為決策變量或稱為設(shè)計(jì)變量，且問題的每—個(gè)具體的方案，都用一組取值為非負(fù)的決策變量表示每個(gè)問題都有一個(gè)決策變量或設(shè)計(jì)變量的線性目標(biāo)函數(shù)，并有最大化或最小化兩種類型。每個(gè)問題都存在若干約束條件，用一組線性等式或不等式來表達(dá)。，，，……，二、線性規(guī)劃的數(shù)學(xué)模型，，，……，目標(biāo)函數(shù)約束條件維數(shù)、價(jià)格系數(shù)、階數(shù)、結(jié)構(gòu)系數(shù)、常數(shù)1、和式二、線性規(guī)劃的數(shù)學(xué)模型2、向量式二、線性規(guī)劃的數(shù)學(xué)模型3、矩陣式二、線性規(guī)劃的數(shù)學(xué)模型二、線性規(guī)劃的數(shù)學(xué)模型，，，……，目標(biāo)函數(shù)約束條件三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，目標(biāo)函數(shù)約束條件三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，目標(biāo)函數(shù)約束條件三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，約束條件的標(biāo)準(zhǔn)化——松弛變量法自由變量的處理方法常數(shù)項(xiàng)為負(fù)值目標(biāo)函數(shù)優(yōu)化方向的變換需轉(zhuǎn)換類型

變換的方法：目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號(hào)。令f

(x)=-f(x)=-CX,有minf(x)=-max[-

f(x)]=-maxf(x)第i個(gè)約束的bi

為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向第i個(gè)約束為型，在不等式左邊增加一個(gè)非負(fù)的變量xn+i

，稱為松弛變量；同時(shí)令cn+i

=0第i個(gè)約束為型，在不等式左邊減去一個(gè)非負(fù)的變量xn+i

，稱為剩余變量；同時(shí)令cn+i

=0若xj0，令

xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

0若xj

不限，令

xj=xj

-

xj

，xj

0，xj

0，代入非標(biāo)準(zhǔn)型三、線性規(guī)劃的標(biāo)準(zhǔn)形式三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，一個(gè)例子三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，（1）轉(zhuǎn)換自由變量三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，（2）轉(zhuǎn)換不等式三、線性規(guī)劃的標(biāo)準(zhǔn)形式，，，……，（3）轉(zhuǎn)換右端項(xiàng)及目標(biāo)函數(shù)四、線性規(guī)劃的圖解法f(x)=36第四節(jié)系統(tǒng)動(dòng)力學(xué)模型（一）系統(tǒng)動(dòng)力學(xué)簡(jiǎn)述（二）動(dòng)力學(xué)模型（一）系統(tǒng)動(dòng)力學(xué)簡(jiǎn)述系統(tǒng)動(dòng)力學(xué)主要是研究生產(chǎn)管理及庫(kù)存管理問題的反饋動(dòng)態(tài)行為的方法。起初叫工業(yè)動(dòng)力學(xué)，后來當(dāng)應(yīng)用于城市問題時(shí)，又出現(xiàn)了城市動(dòng)力學(xué)。當(dāng)應(yīng)用系統(tǒng)動(dòng)力學(xué)建立了全國(guó)性、全球性模型之后，不但可以評(píng)估企業(yè)或政府及整個(gè)人類的經(jīng)濟(jì)方針和政策，摸出采用某項(xiàng)政策后在多長(zhǎng)時(shí)間內(nèi)其影響有多大，時(shí)間有多長(zhǎng)。而且還可以用電子計(jì)算機(jī)按不同假設(shè)選擇出各種變量，通過反饋?zhàn)詣?dòng)打出系統(tǒng)的行為數(shù)據(jù)，并給出曲線圖，以協(xié)助決策者作出更好更適當(dāng)?shù)倪x擇。1.含義與內(nèi)容系統(tǒng)動(dòng)力學(xué)是研究反饋動(dòng)態(tài)行為的方法論。具體說，系統(tǒng)動(dòng)力學(xué)的內(nèi)容是：①它把有生命和無生命系統(tǒng)稱作為信息反饋系統(tǒng)來處理，并且認(rèn)為在每個(gè)系統(tǒng)中部存在著信息反饋機(jī)構(gòu)；②它把被研究系統(tǒng)劃分為若干子系統(tǒng)，并建立各子系統(tǒng)的因果關(guān)系③在確定了因果關(guān)系的基礎(chǔ)上，建立被研究系統(tǒng)的仿真模型——流圖和結(jié)構(gòu)方程式；④實(shí)行計(jì)算機(jī)仿真(在模型上做實(shí)驗(yàn))；⑤驗(yàn)證模型的有效性；⑥為戰(zhàn)略和策略的制訂提供依據(jù)。1.含義與內(nèi)容由系統(tǒng)動(dòng)力學(xué)的內(nèi)容可看出，它能對(duì)社會(huì)經(jīng)濟(jì)管理系統(tǒng)的規(guī)劃和決策進(jìn)行實(shí)驗(yàn)研究。領(lǐng)導(dǎo)者在作出重大決策之前，可先在“實(shí)驗(yàn)室”里做一些“實(shí)驗(yàn)”以便對(duì)將要實(shí)行的策略進(jìn)行比較，決定取舍，或?qū)ο到y(tǒng)的行為做出科學(xué)的預(yù)測(cè)。意義系統(tǒng)動(dòng)力學(xué)，研究一個(gè)系統(tǒng)在活動(dòng)中的信息反饋特性，可顯示出系統(tǒng)組織的結(jié)構(gòu)，放大和延滯的相互作用，以及對(duì)管理系統(tǒng)本身或企業(yè)本身所受到的影響。系統(tǒng)動(dòng)力學(xué)建立了四個(gè)基礎(chǔ)性的支柱：①信息反饋系統(tǒng)的理論；②決策制訂過程的知識(shí)；③對(duì)復(fù)雜系統(tǒng)的實(shí)驗(yàn)?zāi)Ｐ头椒?；④用?shù)字計(jì)算機(jī)作為實(shí)際模型的手段。2.系統(tǒng)動(dòng)力學(xué)的建模特點(diǎn)系統(tǒng)動(dòng)力學(xué)的建模別具一格，具有不同于其它預(yù)測(cè)方法的特點(diǎn)?，F(xiàn)代的管理系統(tǒng)是龐大、復(fù)雜而由許多子系統(tǒng)構(gòu)成。這些子構(gòu)造相互作用形成了系統(tǒng)內(nèi)部錯(cuò)綜復(fù)雜的因果關(guān)系。這些因果關(guān)系形成作用環(huán)或反饋環(huán)。在一個(gè)管理系統(tǒng)中，我們可以找到多個(gè)這樣的環(huán)，人們的決策活動(dòng)就在這些環(huán)間進(jìn)行。對(duì)于這樣多重環(huán)的復(fù)雜系統(tǒng)來說，單憑人們的經(jīng)驗(yàn)不能有效地跟蹤。只有使用統(tǒng)計(jì)的方法。通過對(duì)系統(tǒng)輸入、輸出數(shù)據(jù)的處理，來獲得系統(tǒng)的行為，稱為“數(shù)據(jù)產(chǎn)生的行為”。但是管理系統(tǒng)從本質(zhì)上講，是缺乏數(shù)據(jù)的，關(guān)于描述系統(tǒng)行為的數(shù)據(jù)，雖然經(jīng)過收集，很難做到完整。僅僅依據(jù)這種不完整的數(shù)據(jù)構(gòu)筑起來的統(tǒng)計(jì)模型，其有效性是很有限的。實(shí)際上，人們認(rèn)識(shí)事物的主要依據(jù)不是數(shù)據(jù)，而是事物的內(nèi)部構(gòu)造。系統(tǒng)可以劃分為若干子構(gòu)造，這些子構(gòu)造的相互作用產(chǎn)生系統(tǒng)的行為。人們對(duì)于系統(tǒng)構(gòu)造的認(rèn)識(shí)，不是通過數(shù)據(jù)，而是通過邏輯思維、想象力和創(chuàng)造性來獲得的。例：一個(gè)企業(yè)可以劃分為生產(chǎn)量、庫(kù)存量、訂貨量、受訂欠付量等等。確定這些子構(gòu)造和它們的因果關(guān)系并不需要數(shù)據(jù)，而數(shù)據(jù)只是用在構(gòu)造概念基礎(chǔ)上，建立各子構(gòu)造的定量關(guān)系。數(shù)據(jù)和構(gòu)造的有機(jī)結(jié)合，形成完整的系統(tǒng)構(gòu)造模型。系統(tǒng)動(dòng)力學(xué)在工程、經(jīng)濟(jì)甚至醫(yī)學(xué)、心理學(xué)、社會(huì)學(xué)方面都獲得相當(dāng)成功。近年來，在科技管理系統(tǒng)，特別作為復(fù)雜系統(tǒng)的長(zhǎng)期預(yù)測(cè)，確實(shí)是一種強(qiáng)有力的建模工具。（二）動(dòng)力學(xué)模型1.幾個(gè)概念（1）水平——貯放于水槽的水量或流水所積蓄的量。比如，經(jīng)濟(jì)上是庫(kù)存量、銀行存款額、工廠設(shè)備、資金、材料等；在世界性模型中，則以人口、資本、自然資源、可耕地等為水平變量。2．流速——平均單位時(shí)間流入水槽和流出水槽的水流量。比如，物料流中商品進(jìn)貨量和實(shí)際存貨量，資金中的金錢支付交換量。每一個(gè)月的存款額，一年中設(shè)備投資等均屬此類。世界模型中則有出生率和死亡率，自然資源的消耗，污染的產(chǎn)生和處理等均為流速的變量。水平流速的關(guān)系如下圖系統(tǒng)動(dòng)力學(xué)的水平與流速的關(guān)系一個(gè)可變水平和可變流速的基本結(jié)構(gòu)可用來表示一個(gè)工業(yè)管理系統(tǒng)。水平?jīng)Q定了流速，而決策控制流速，流速反過來改變水平。這些水平和流速由信息、材料、訂貨、貨幣、人員和主要設(shè)備這六個(gè)相互交連的網(wǎng)絡(luò)組成，用以反映工業(yè)系統(tǒng)的活動(dòng)。如果把網(wǎng)絡(luò)中(如物料網(wǎng)絡(luò))中較重要的階段包括原料倉(cāng)庫(kù)、半成品庫(kù)、成品庫(kù)、運(yùn)轉(zhuǎn)倉(cāng)庫(kù)、批發(fā)商倉(cāng)庫(kù)和零售商倉(cāng)庫(kù)；放在網(wǎng)絡(luò)中某一階段的數(shù)量稱為水平；我們又知道網(wǎng)絡(luò)中發(fā)生各種水平的改變時(shí)，便能由網(wǎng)絡(luò)的水平來說明某一時(shí)刻的網(wǎng)絡(luò)狀態(tài)。網(wǎng)絡(luò)中的流送信息，便能預(yù)期網(wǎng)絡(luò)中的下個(gè)水平?jīng)Q策被看作是決定未來系統(tǒng)狀態(tài)的管理活動(dòng)，以及決定系統(tǒng)水平改變的管理活動(dòng)。在某一時(shí)間間隔的水平波動(dòng)，因流入和流出量之差導(dǎo)致出積蓄。流速的符號(hào)象征著流量調(diào)節(jié)閥在經(jīng)濟(jì)學(xué)上，水平相當(dāng)于固定資本，而流速相當(dāng)于浮動(dòng)。2.系統(tǒng)動(dòng)力學(xué)的方程結(jié)構(gòu)

系統(tǒng)動(dòng)力學(xué)模型：按照數(shù)學(xué)的語言，就是所謂離散的差分方程。其表達(dá)式為：現(xiàn)在瞬時(shí)水平＝前一瞬時(shí)水平

+經(jīng)歷時(shí)間×流速差。3.應(yīng)用舉例例1市場(chǎng)銷售模型設(shè)一批貨物的成本為C(包括生產(chǎn)、運(yùn)輸、倉(cāng)儲(chǔ)管理等)，出售后的總收入為R則利潤(rùn)P＝R—C。貨物的價(jià)格是銷售量x的函數(shù)，即P＝P(X)，這個(gè)函數(shù)稱為需求函數(shù)對(duì)整個(gè)市場(chǎng)來說，價(jià)格高需求量就減少；價(jià)格低時(shí)需求量就高，所以需求函數(shù)P(X)是X的遞減函數(shù)。如果它是線性函數(shù)時(shí)，則其斜率為負(fù)。即

P(x)＝一ax十b(a＞o)而總收入：

R＝xP(X)＝一ax2十bX貨物的成本C由不變成本FC和可變成本VC兩部分組成。即

C＝FC十VC

如對(duì)農(nóng)作物的成本、土地、工具的花費(fèi)是不變成本，它是一個(gè)常數(shù)。而播種、肥料、收獲的花費(fèi)是可變成本，它是x的函數(shù)．問題：對(duì)某一貨物銷售量多大才能使利潤(rùn)P達(dá)到最大？則由P(x)＝R—C對(duì)x求導(dǎo)由P’(X)＝O得R＝C

這個(gè)公式是古典經(jīng)濟(jì)學(xué)中使用利潤(rùn)達(dá)到最大的一個(gè)基本關(guān)系式。第五節(jié)圖與網(wǎng)絡(luò)分析圖的基本概念樹最短路中國(guó)郵遞員問題網(wǎng)絡(luò)最大流問題最小費(fèi)用最大流圖最直觀的模型圖論與網(wǎng)絡(luò)分析起源哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個(gè)島，河上有七座橋。BACD哥尼斯堡七橋問題歐拉在1736年發(fā)表圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋問題。從任何一點(diǎn)出發(fā)，能否通過每條邊一次且僅一次回到出發(fā)點(diǎn)。BACD圖論是一個(gè)古老的數(shù)學(xué)分支，它起源于游戲難題的研究。圖論的內(nèi)容十分豐富，應(yīng)用得相當(dāng)廣泛，許多學(xué)科，諸如運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、博弈論、化學(xué)、生物學(xué)、物理學(xué)、社會(huì)科學(xué)、語言學(xué)、計(jì)算機(jī)科學(xué)等，都以圖作為工具來解決實(shí)際問題和理論問題。隨著計(jì)算機(jī)科學(xué)的發(fā)展，圖論在以上各學(xué)科中的作用越來越大，同時(shí)圖論本身也得到了充分的發(fā)展。實(shí)際背景在組織生產(chǎn)中，為完成某項(xiàng)生產(chǎn)任務(wù)，各工序之間怎樣銜接，才能使生產(chǎn)任務(wù)完成得既快又好。一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的路線走，所走的路線最短。各種通信網(wǎng)絡(luò)的合理架設(shè)交通網(wǎng)絡(luò)的合理分布等問題G=（V，E）子圖矩陣表示含元素的個(gè)數(shù)點(diǎn)的次邊點(diǎn)邊關(guān)系連通圖樹特殊的圖簡(jiǎn)單圖多重圖空?qǐng)D部分樹基本概念內(nèi)容：有向圖，無向圖的基本概念。1、有向圖，無向圖的定義，2、圖中頂點(diǎn)，邊，關(guān)聯(lián)與相鄰，頂點(diǎn)度數(shù)等基本概念，3、各頂點(diǎn)度數(shù)與邊數(shù)的關(guān)系及推論，基本概念（一）5、圖的同構(gòu)的定義。4、簡(jiǎn)單圖，完全圖，子圖，補(bǔ)圖的概念，基本概念一、圖的概念。1、定義。無序積無向圖中元素為無向邊，簡(jiǎn)稱邊。，有向圖中元素為有向邊，簡(jiǎn)稱邊。，基本概念一、圖的概念。1、定義。無序積基本概念基本概念圖論(GraphTheory)：研究圖的理論圖：一個(gè)有序的三元組（V(G)，E(G)，ψG），這里V(G)和E(G)是互無公共元素的集合且V(G)非空，ψG稱為關(guān)聯(lián)函數(shù)，它使E(G)中的每一個(gè)元素對(duì)應(yīng)于V(G)中元素的無序偶（偶中的元素可能相同）V(G)稱為圖G的頂點(diǎn)集，其中的元素稱為圖G的頂點(diǎn)E(G）稱為圖圖G的邊集，其中的元素稱為圖G的邊基本概念弧(arc)：帶箭頭的連線有向圖：一個(gè)有序的三元組（V(D)，A(D)，ψD），這里V(D)和A(D)是互無公共元素的集合且V(D)非空，ψD稱為關(guān)聯(lián)函數(shù)，它使A(D)中的每一個(gè)元素對(duì)應(yīng)于V(D)中元素的序偶（偶中的元素可能相同）。有向圖與無向圖的區(qū)別：無對(duì)稱性?；A(chǔ)圖、始點(diǎn)、終點(diǎn)、路、回路2、圖的表示法。有向圖，無向圖的頂點(diǎn)都用小圓圈表示。無向邊——連接頂點(diǎn)的線段。有向邊——以為始點(diǎn)，以為終點(diǎn)的有向線段?；靖拍罾?、(1)無向圖，圖形表示如右：基本概念圖形表示如右：例1、(2)有向圖，基本概念3、相關(guān)概念。(1)有限圖——都是有限集的圖。階圖——的圖。零圖——的圖。特別，若又有，稱平凡圖。(2)關(guān)聯(lián)(邊與點(diǎn)關(guān)系)——設(shè)邊(或)，則稱與(或)關(guān)聯(lián)?；靖拍?、相關(guān)概念。(2)基本概念3、相關(guān)概念。(2)孤立點(diǎn)——無邊關(guān)聯(lián)的點(diǎn)。環(huán)——一條邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)重合，稱此邊為環(huán)(即兩頂點(diǎn)重合的邊)?；靖拍?、相關(guān)概念。(2)懸掛點(diǎn)——只有一條邊與其關(guān)聯(lián)的點(diǎn)，所對(duì)應(yīng)的邊叫懸掛邊。(3)平行邊——關(guān)聯(lián)于同一對(duì)頂點(diǎn)的若干條邊稱為平行邊。平行邊的條數(shù)稱為重?cái)?shù)。多重圖——含有平行邊的圖。簡(jiǎn)單圖——不含平行邊和環(huán)的圖?；靖拍钊缋?的(1)中，與關(guān)聯(lián)的次數(shù)均為1，與關(guān)聯(lián)的次數(shù)為2，邊都是相鄰的，為孤立點(diǎn)，為懸掛點(diǎn)，為懸掛邊，為環(huán)，為平行邊，重?cái)?shù)2，為多重圖?；靖拍?、完全圖設(shè)為階無向簡(jiǎn)單圖，若中每個(gè)頂點(diǎn)都與其余個(gè)頂點(diǎn)相鄰，則稱為階無向完全圖，記作。若有向圖的任一對(duì)頂點(diǎn)，既有有向邊又有有向邊，則稱為有向完全圖?；靖拍罾纾夯靖拍疃?、頂點(diǎn)的度數(shù)，握手定理。1、頂點(diǎn)的度數(shù)(簡(jiǎn)稱度)。無向圖的度數(shù)記，指與，相關(guān)聯(lián)的邊的條數(shù)。有向圖的度數(shù)，基本概念二、頂點(diǎn)的度數(shù)，握手定理。1、頂點(diǎn)的度數(shù)(簡(jiǎn)稱度)。最大度最小度對(duì)有向圖相應(yīng)地還有，，，?；靖拍钊缋?的(2)中，，?；靖拍钤O(shè)為圖的頂點(diǎn)集，稱為的度數(shù)序列。2、握手定理。定理1：設(shè)圖為無向圖或有向圖，為邊數(shù))，，(則基本概念定理2：設(shè)為有向圖，，則，。2、握手定理推論：任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)?；靖拍钊?、子圖，補(bǔ)圖。1、子圖定義：設(shè)是兩個(gè)圖，若，，且，則稱是的子圖，是的母圖，記作。真子圖——

且(即或)。生成子圖——且?；靖拍钊?、子圖，補(bǔ)圖。導(dǎo)出子圖——非空，以為頂點(diǎn)集，以兩端均在中的邊的全體為邊集的的子圖，稱的導(dǎo)出子圖?！强?，以為邊集，以中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的的子圖，稱的導(dǎo)出子圖?；靖拍罾?、上圖中，(1)－(6)都是(1)的子圖，其中(2)－(6)為真子圖，(1)－(5)為生成子圖?；靖拍?、補(bǔ)圖定義。設(shè)為無向完全圖，，為無向簡(jiǎn)單圖，其中，，則稱，相對(duì)于互為補(bǔ)圖，記，?；靖拍罨靖拍钏?、圖的同構(gòu)。定義：設(shè)兩個(gè)無向圖，，若存在雙射函數(shù)，使得對(duì)于任意的，當(dāng)且僅當(dāng)并且與重?cái)?shù)相同，則稱與同構(gòu)，記作?；靖拍罾?、基本概念內(nèi)容：圖的通路，回路，連通性。重點(diǎn)：1、通路，回路，簡(jiǎn)單通路，回路，初級(jí)通路，回路的定義，2、圖的連通性的概念，3、短程線，距離的概念?；靖拍睿ǘ┮?、通路，回路。1、通路(回路)中頂點(diǎn)和邊的交替序列——，其中(無向圖)，或(有向圖)，——始點(diǎn)，——終點(diǎn)，稱為到的通路。當(dāng)時(shí)，為回路。基本概念一、通路，回路。2、簡(jiǎn)單通路，簡(jiǎn)單回路。簡(jiǎn)單通路(跡)簡(jiǎn)單回路(閉跡)復(fù)雜通路(回路)基本概念一、通路，回路。3、初級(jí)通路，初級(jí)回路。初級(jí)通路(路徑)初級(jí)回路(圈)初級(jí)通路(回路)簡(jiǎn)單通路(回路)，但反之不真。4、通路，回路的長(zhǎng)度——中邊的數(shù)目?；靖拍罾?、(1)圖(1)中，從的通路有：到…………長(zhǎng)度3長(zhǎng)度6長(zhǎng)度6基本概念例1、(1)圖(1)中，從的通路有：到…………初級(jí)通路簡(jiǎn)單通路復(fù)雜通路基本概念例1、(2)…………長(zhǎng)度3長(zhǎng)度4長(zhǎng)度7圖(2)中過)有：的回路(從到基本概念例1、(2)…………初級(jí)回路(圈)初級(jí)回路(圈)復(fù)雜回路圖(2)中過)有：的回路(從到基本概念5、圖中最短的回路。如圖：基本概念6、性質(zhì)。定理：階圖中，若從頂點(diǎn)到存在通路，則從到存在長(zhǎng)度小于等于在一個(gè)的通路。推論：階圖中，若從頂點(diǎn)到存在通路，則從到存在長(zhǎng)度小于等于在一個(gè)的初級(jí)通路?；靖拍?、性質(zhì)。定理：階圖中，若到自身存在回路，則從到自身存在長(zhǎng)度小于等于的回路。在一個(gè)推論：階圖中，若到自身存在一個(gè)簡(jiǎn)單回路，則從到自身存在長(zhǎng)度小于等于的初級(jí)回路。在一個(gè)基本概念6、性質(zhì)。由以上定理可知，在階圖中，任何一條初級(jí)通路的長(zhǎng)度任何一條初級(jí)回路的長(zhǎng)度基本概念二、圖的連通性。1、連通，可達(dá)。無向圖中，從到存在通路，稱到是連通的(雙向)。有向圖中，從到存在通路，稱可達(dá)(注意方向)?；靖拍?、短程線，距離。短程線——連通或可達(dá)的兩點(diǎn)間長(zhǎng)度最短的通路。距離——短程線的長(zhǎng)度，記無向圖有向圖基本概念2、短程線，距離。若之間無通路(或不可達(dá))，規(guī)定距離滿足：(1)，時(shí)，等號(hào)成立。(2)若是無向圖，還具有對(duì)稱性，?；靖拍?、無向圖的連通。為連通圖——是平凡圖，或都是連通的。中任兩點(diǎn)為非連通圖——中至少有兩點(diǎn)不連通。基本概念3、無向圖的連通。設(shè)是一個(gè)無向圖，是中頂點(diǎn)之間的連通關(guān)系，則是等價(jià)關(guān)系。設(shè)將劃分成個(gè)等價(jià)類：，由它們導(dǎo)出的子圖稱為的連通分支，其個(gè)數(shù)記為基本概念4、有向圖的連通?！腥我粚?duì)頂點(diǎn)都互相可達(dá)(雙向)——中任一對(duì)頂點(diǎn)至少一向可達(dá)——略去中有向邊的方向后得到的無向圖連通連通強(qiáng)連通單向連通弱連通強(qiáng)連通單向連通弱連通基本概念例2、強(qiáng)連通單向連通基本概念例2、單向連通弱連通非連通圖基本概念內(nèi)容：關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣。重點(diǎn)：1、有向圖，無向圖的關(guān)聯(lián)矩陣，2、有向圖的鄰接矩陣。了解：有向圖的可達(dá)矩陣。圖的矩陣表示一、無向圖的關(guān)聯(lián)矩陣。1、設(shè)無向圖，，，的關(guān)聯(lián)矩陣，圖的矩陣表示

無向圖(下圖所示)，求。解：圖的矩陣表示2、性質(zhì)。(1)(2)(3)握手定理圖的矩陣表示(4)，當(dāng)且僅當(dāng)為孤立點(diǎn)。2、性質(zhì)。(5)若第列與第列相同，則說明與為平行邊。圖的矩陣表示二、有向圖的關(guān)聯(lián)矩陣。1、設(shè)無環(huán)有向圖，，，的關(guān)聯(lián)矩陣，其中圖的矩陣表示例2、有向圖(下圖所示)，求。解：圖的矩陣表示2、性質(zhì)。(1)(2)(3)圖的矩陣表示三、有向圖的鄰接矩陣。1、設(shè)有向圖，，的鄰接矩陣，，其中指鄰接到的邊的條數(shù)(非負(fù)整數(shù))。圖的矩陣表示例3、有向圖(下圖所示)，求。解：圖的矩陣表示2、性質(zhì)。(1)(2)(3)(4)為中環(huán)的個(gè)數(shù)。圖的矩陣表示3、求中長(zhǎng)度為的通路數(shù)和回路數(shù)。(1)令矩陣乘法其中表示從到長(zhǎng)度為2的通路數(shù)或回路數(shù)。圖的矩陣表示3、求中長(zhǎng)度為的通路數(shù)和回路數(shù)?？紤]，簡(jiǎn)記為。其中表示從到長(zhǎng)度為或回路數(shù)。的通路數(shù)中長(zhǎng)度為為的通路總數(shù)，其中為中長(zhǎng)度為的回路總數(shù)。圖的矩陣表示3、求中長(zhǎng)度為的通路數(shù)和回路數(shù)。(2)設(shè)則中元素為中到長(zhǎng)度小于等于的通路總數(shù)，為中長(zhǎng)度小于等于的通路總數(shù)，其中為中長(zhǎng)度小于等于的回路總數(shù)。圖的矩陣表示例4、在例3的有向圖中求，，。解：，，圖的矩陣表示四、有向圖的可達(dá)性矩陣。(了解)設(shè)為有向圖，，令，圖的矩陣表示四、有向圖的可達(dá)性矩陣。(了解)可達(dá)性矩陣其中元素可由求得：圖的矩陣表示樹(tree)樹：一個(gè)無圈的連通圖稱為樹例：已知有5個(gè)城市，要在他們之間架設(shè)電話線，要求任何兩個(gè)城市都可以互相通話（允許通過其他城市），并且電話線的根數(shù)最少。v1v2v5v4v3e1e2e3e4e5樹的性質(zhì)定理1：設(shè)圖G=(V,E)是一個(gè)樹，p(G)>=2，則G至少有兩個(gè)懸掛點(diǎn)。定理2：圖G=(V,E)是一個(gè)樹的充分必要條件是G不含圈，且恰有p-1條邊。定理3：圖G=(V,E)是一個(gè)樹的充分必要條件是G是連通圖，并且

q(G)=p(G)-1定理4：圖G是一個(gè)樹的充分必要條件是任意兩個(gè)頂點(diǎn)之間恰有一條路。v1v2v5v4v3e1e2e3e4e5v6圖的支撐樹設(shè)圖T=(V,E’)是圖G=(V,E)的支撐子圖，如果圖T=(V,E’)是一個(gè)樹，則稱T是G的一個(gè)支撐樹。v1v2v4v3圖1v1v2v4v3一個(gè)支撐字圖支撐樹的獲得定理5：圖G有支撐樹的充分必要條件是圖G是連通的。尋求支撐樹的方法：（1）破圈法（2）避圈法v1v2v5v4v3v6v1v2v5v4v3v6最小支撐樹問題給定G=(V,E)，對(duì)G中的每一條邊[vi,vj]，相應(yīng)地有一個(gè)數(shù)wij，則稱這樣的圖為賦權(quán)圖，稱為邊[vi,vj]上的權(quán)(weight)。如果T=(V,E’)是G一個(gè)支撐樹，稱E’中所有邊的權(quán)之和為支撐樹T的權(quán)，記為w(T)，即最小支撐樹問題最小支撐樹T*：權(quán)最小的支撐樹，即求最小支撐樹的方法：（1）避圈法（2）破圈法破圈法v1v2v5v4v361752v65443避圈法v1v2v5v4v361752v65443最短路問題例：某人預(yù)從v1出發(fā)，通過這個(gè)交通網(wǎng)絡(luò)到v8去，求使總費(fèi)用最小的旅行路線。v2v5v1v4v36361101362v6v7v8v922243410幾個(gè)定義給定一個(gè)賦權(quán)有向圖D=(V,A)，對(duì)每一個(gè)弧a=(vi,vj)，相應(yīng)有權(quán)w(a)=wij

，又給定中的兩個(gè)頂點(diǎn)vs，vt

。設(shè)P是D中從vs到vt的一條路，定義路P的權(quán)是路P中所有弧的權(quán)之和，記為w(P)。最短路問題最短路問題就是在所有從vs到vt的路中，求一條權(quán)最小的路，即求一條從vs到vt的路P0，使式中對(duì)D中所有從vs到vt的路P取最小，稱P0是從vs到vt的最短路。路P0的權(quán)稱為從vs到vt的距離，記為d(vs,vt)最短路算法Dijkstra方法（所有wij≥0）基本思想：從vs出發(fā)，逐步地向外探尋最短路。執(zhí)行過程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄下一個(gè)數(shù)（稱為這個(gè)點(diǎn)的標(biāo)號(hào)），它或者表示從vs到該點(diǎn)的最短路的權(quán)（稱為P標(biāo)號(hào)）、或者是從vs到該點(diǎn)的最短路的權(quán)的上界（稱為T標(biāo)號(hào)），方法每一步是去修改T標(biāo)號(hào)，并且把某一個(gè)具T標(biāo)號(hào)的點(diǎn)改變?yōu)镻標(biāo)號(hào)的點(diǎn)，從而使D中具P標(biāo)號(hào)的頂點(diǎn)數(shù)多一個(gè)至多經(jīng)過p-1步，就可以求出從到各點(diǎn)的最短路。具體過程v2v5v1v4v36361101362v6v7v8v922243410P具體過程v2v5v1v4v36361101362v6v7v8v922243410PPPPPPPP網(wǎng)絡(luò)最大流問題城市供水管網(wǎng)v2v5v1v4v31055108v64113317基本概念與定理網(wǎng)絡(luò)：給一個(gè)有向圖D=（V，A)，在V中指定了一點(diǎn)，稱為發(fā)