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

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

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

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

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

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

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

滿足約束條件

一、問題的提出共同特征問題的所求均用一組未知變量表出，這些變量稱為決策變量或稱為設(shè)計變量，且問題的每—個具體的方案，都用一組取值為非負(fù)的決策變量表示每個問題都有一個決策變量或設(shè)計變量的線性目標(biāo)函數(shù)，并有最大化或最小化兩種類型。每個問題都存在若干約束條件，用一組線性等式或不等式來表達(dá)。，，，……，二、線性規(guī)劃的數(shù)學(xué)模型，，，……，目標(biāo)函數(shù)約束條件維數(shù)、價格系數(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ù)項為負(fù)值目標(biāo)函數(shù)優(yōu)化方向的變換需轉(zhuǎn)換類型

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

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

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

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

，稱為松弛變量；同時令cn+i

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

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

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

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

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

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

C＝FC十VC

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

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

且(即或)。生成子圖——且?；靖拍钊⒆訄D，補圖。導(dǎo)出子圖——非空，以為頂點集，以兩端均在中的邊的全體為邊集的的子圖，稱的導(dǎo)出子圖。——非空，以為邊集，以中邊關(guān)聯(lián)的頂點的全體為頂點集的的子圖，稱的導(dǎo)出子圖?；靖拍罾?、上圖中，(1)－(6)都是(1)的子圖，其中(2)－(6)為真子圖，(1)－(5)為生成子圖。基本概念2、補圖定義。設(shè)為無向完全圖，，為無向簡單圖，其中，，則稱，相對于互為補圖，記，?；靖拍罨靖拍钏摹D的同構(gòu)。定義：設(shè)兩個無向圖，，若存在雙射函數(shù)，使得對于任意的，當(dāng)且僅當(dāng)并且與重數(shù)相同，則稱與同構(gòu)，記作?；靖拍罾?、基本概念內(nèi)容：圖的通路，回路，連通性。重點：1、通路，回路，簡單通路，回路，初級通路，回路的定義，2、圖的連通性的概念，3、短程線，距離的概念?；靖拍睿ǘ┮?、通路，回路。1、通路(回路)中頂點和邊的交替序列——，其中(無向圖)，或(有向圖)，——始點，——終點，稱為到的通路。當(dāng)時，為回路?；靖拍钜?、通路，回路。2、簡單通路，簡單回路。簡單通路(跡)簡單回路(閉跡)復(fù)雜通路(回路)基本概念一、通路，回路。3、初級通路，初級回路。初級通路(路徑)初級回路(圈)初級通路(回路)簡單通路(回路)，但反之不真。4、通路，回路的長度——中邊的數(shù)目?；靖拍罾?、(1)圖(1)中，從的通路有：到…………長度3長度6長度6基本概念例1、(1)圖(1)中，從的通路有：到…………初級通路簡單通路復(fù)雜通路基本概念例1、(2)…………長度3長度4長度7圖(2)中過)有：的回路(從到基本概念例1、(2)…………初級回路(圈)初級回路(圈)復(fù)雜回路圖(2)中過)有：的回路(從到基本概念5、圖中最短的回路。如圖：基本概念6、性質(zhì)。定理：階圖中，若從頂點到存在通路，則從到存在長度小于等于在一個的通路。推論：階圖中，若從頂點到存在通路，則從到存在長度小于等于在一個的初級通路?；靖拍?、性質(zhì)。定理：階圖中，若到自身存在回路，則從到自身存在長度小于等于的回路。在一個推論：階圖中，若到自身存在一個簡單回路，則從到自身存在長度小于等于的初級回路。在一個基本概念6、性質(zhì)。由以上定理可知，在階圖中，任何一條初級通路的長度任何一條初級回路的長度基本概念二、圖的連通性。1、連通，可達(dá)。無向圖中，從到存在通路，稱到是連通的(雙向)。有向圖中，從到存在通路，稱可達(dá)(注意方向)?；靖拍?、短程線，距離。短程線——連通或可達(dá)的兩點間長度最短的通路。距離——短程線的長度，記無向圖有向圖基本概念2、短程線，距離。若之間無通路(或不可達(dá))，規(guī)定距離滿足：(1)，時，等號成立。(2)若是無向圖，還具有對稱性，。基本概念3、無向圖的連通。為連通圖——是平凡圖，或都是連通的。中任兩點為非連通圖——中至少有兩點不連通?；靖拍?、無向圖的連通。設(shè)是一個無向圖，是中頂點之間的連通關(guān)系，則是等價關(guān)系。設(shè)將劃分成個等價類：，由它們導(dǎo)出的子圖稱為的連通分支，其個數(shù)記為基本概念4、有向圖的連通?！腥我粚旤c都互相可達(dá)(雙向)——中任一對頂點至少一向可達(dá)——略去中有向邊的方向后得到的無向圖連通連通強連通單向連通弱連通強連通單向連通弱連通基本概念例2、強連通單向連通基本概念例2、單向連通弱連通非連通圖基本概念內(nèi)容：關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣。重點：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)為孤立點。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)的個數(shù)。圖的矩陣表示3、求中長度為的通路數(shù)和回路數(shù)。(1)令矩陣乘法其中表示從到長度為2的通路數(shù)或回路數(shù)。圖的矩陣表示3、求中長度為的通路數(shù)和回路數(shù)?？紤]，簡記為。其中表示從到長度為或回路數(shù)。的通路數(shù)中長度為為的通路總數(shù)，其中為中長度為的回路總數(shù)。圖的矩陣表示3、求中長度為的通路數(shù)和回路數(shù)。(2)設(shè)則中元素為中到長度小于等于的通路總數(shù)，為中長度小于等于的通路總數(shù)，其中為中長度小于等于的回路總數(shù)。圖的矩陣表示例4、在例3的有向圖中求，，。解：，，圖的矩陣表示四、有向圖的可達(dá)性矩陣。(了解)設(shè)為有向圖，，令，圖的矩陣表示四、有向圖的可達(dá)性矩陣。(了解)可達(dá)性矩陣其中元素可由求得：圖的矩陣表示樹(tree)樹：一個無圈的連通圖稱為樹例：已知有5個城市，要在他們之間架設(shè)電話線，要求任何兩個城市都可以互相通話（允許通過其他城市），并且電話線的根數(shù)最少。v1v2v5v4v3e1e2e3e4e5樹的性質(zhì)定理1：設(shè)圖G=(V,E)是一個樹，p(G)>=2，則G至少有兩個懸掛點。定理2：圖G=(V,E)是一個樹的充分必要條件是G不含圈，且恰有p-1條邊。定理3：圖G=(V,E)是一個樹的充分必要條件是G是連通圖，并且

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

，又給定中的兩個頂點vs，vt

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