。精選資料，歡迎下載2.2求M/M/m（n）中，等待時間w的概率密度函數(shù)。解： M/M/m（n）的概率分布為：假定n>m，n≥0，現(xiàn)在來計算概率P{w>x}，既等待時間大于x的概率。其中，Pj{w>x}的概率為：可得：特別的，新到顧客需等待的概率為： 2.4求M/D/1排隊(duì)問題中等待時間W的一、二、三階矩m1、m2、m3，D表示服務(wù)時間為定值b，到達(dá)率為。解： 其中 從而又 2.5求M/B/1，B/M/1和B/B/1排隊(duì)問題的平均等待時間，其中B是二階指數(shù)分布：解：M/B/1B/M/1B/B/1 設(shè)到達(dá)的概率密度函數(shù)為 設(shè)離去的概率密度函數(shù)為 假設(shè) 2.6在D/D/1排隊(duì)問題中，顧客到達(dá)的時間間隔為a，服務(wù)時間為b，均為恒定值，且a>b， 求：穩(wěn)定狀態(tài)時系統(tǒng)的隊(duì)列長度為k的概率pk，顧客到達(dá)時隊(duì)列的長度為k的概率vk，顧客離去時隊(duì)列的長度dk，以及平均等待時間，并用G/G/1上界公式求出此時的平均等待時間，評論計算結(jié)果，并討論a≤b的情況。解： 由于是D/D/1問題，故子系統(tǒng)運(yùn)行情況完全確定，第一個顧客到達(dá)后，系統(tǒng)無顧客，經(jīng)過b后，服務(wù)完畢，顧客離去，再經(jīng)過a-b后，下一個顧客到達(dá)。 此時有：顧客不等待時G/G/1上界公式當(dāng)a<b時系統(tǒng)將不穩(wěn)定,以恒定的速率增加顧客，即每隔時間后，系統(tǒng)隊(duì)列長度增長1。2.7求M/E2/1即時拒絕系統(tǒng)的呼損，其中E2是二階愛爾蘭分布，解： 設(shè)相鄰呼叫到達(dá)間隔為t，如果服務(wù)時間，將造成呼損，時無呼損。 2.8在優(yōu)先級別隊(duì)列中，A隊(duì)為優(yōu)先級，不拒絕，B隊(duì)為非優(yōu)先級，只準(zhǔn)一人排隊(duì)等待（不計在服務(wù)中的），且當(dāng)A隊(duì)無人時才能被服務(wù)，求各狀態(tài)概率，A隊(duì)的平均等待時間和B隊(duì)的拒絕概率。解： 說明：0狀態(tài)代表系統(tǒng)中無顧客狀態(tài)；i，j狀態(tài)代表系統(tǒng)中正在服務(wù)且A隊(duì)中有i個顧客，B隊(duì)列中有j個顧客排隊(duì)的狀態(tài)。狀態(tài)轉(zhuǎn)移圖如右，A隊(duì)到達(dá)率為，B隊(duì)到達(dá)率為，服務(wù)率，系統(tǒng)穩(wěn)定時，應(yīng)有可得到特征方程如下:由于4是差分方程，不妨設(shè)其通解為：代入有： 由于5是非齊次差分方程： 其特征根為：假設(shè)其通解為：代入前式得：解之，得：代入3式得：即：由正則條件：2.9排隊(duì)系統(tǒng)中有三個隊(duì)列,其到達(dá)率分別為公用同一出線路，其中a類最優(yōu)先，即線路有空閑就發(fā)送；b類次之，即a無排隊(duì)時可以發(fā)送，c類最低，即a，b類均無排隊(duì)時可以發(fā)送，不計正在傳送的業(yè)務(wù)，各個隊(duì)列的截至隊(duì)長為na＝2，nb=1，nc＝0，試列出穩(wěn)定狀態(tài)下的狀態(tài)方程，并計算時，各狀態(tài)的概率和三類呼叫的呼損。解： r，s，k分別表示a，b，c三隊(duì)中等待的呼叫數(shù)，狀態(tài)以（r，s，k）表示。穩(wěn)態(tài)方程：歸一條件若令C類呼損為：B類呼損為：A類呼損為：2.10有一個三端網(wǎng)絡(luò)，端點(diǎn)為，邊為及，v1到v3的業(yè)務(wù)由v2轉(zhuǎn)接，設(shè)所有的端之間的業(yè)務(wù)到達(dá)率為，線路的服務(wù)率為的M|M|1(1)問題，當(dāng)采用即時拒絕的方式時，求：各個端的業(yè)務(wù)呼損。網(wǎng)絡(luò)的總通過量。線路的利用率。解： 令：00表示e1,e2均空閑。 10表示e1忙,e2閑（即e1由v1,v2間業(yè)務(wù)占用）。01表示e1閑,e2忙（即e2由v2,v3間業(yè)務(wù)占用）。11表示e1,e2均忙，且分別由v1v2,v2v3間業(yè)務(wù)占用。★表示e1,e2均忙，且由v1，v3間業(yè)務(wù)占用。狀態(tài)轉(zhuǎn)移圖如右：當(dāng)時有下列關(guān)系: 又解之得: 呼損而通過量線路利用率2.11上題中的網(wǎng)若用于傳送數(shù)據(jù)包,到達(dá)率仍為每秒平均包長為b比特,邊的容量為c比特/秒,采用不拒絕的方式,并設(shè)各端的存儲容量足夠大,求:(1)穩(wěn)定條件。(2)網(wǎng)絡(luò)的平均時延。(3)總的通過量。(4)線路的平均利用率。解：這是一個無損但有時延的系統(tǒng)。 兩條線路上到達(dá)率為：2，而服務(wù)率為：c/b的M/M/1系統(tǒng)。(1)穩(wěn)定條件為：2b/c<1。(2)網(wǎng)絡(luò)的平均時延：對v1v2和v2v3間的業(yè)務(wù)：對v1v3間的業(yè)務(wù)：(3)系統(tǒng)穩(wěn)定時，總的通過量為：3b/c。(4)線路的平均利用率==2b/c。一般來說，通過率與利用率均有增加，這是以穩(wěn)定性和時延為代價換來的。2.12在分組交換系統(tǒng)中，設(shè)信息包以泊松率到達(dá)，平均到達(dá)率為，但信息包的長度為固定b比特，信道容量為c比特/秒。由于端內(nèi)存儲量的限制，設(shè)除了在傳送的包外，只允許有兩個信息包等待傳送，試：(1)列出關(guān)于dr(顧客離去時的隊(duì)長)的系統(tǒng)方程(2)解出個dr.(3)求平均時延。(4)求信息包被拒絕的概率。解： 其中p0是第4個顧客被拒絕離去之后，第3個顧客的殘余壽命中無顧客到達(dá)的概率。 這里到達(dá)是隨機(jī)的，可知： 設(shè) 則 平均時延： 拒絕概率：2.13有四個端三條邊組成的數(shù)據(jù)網(wǎng)，如圖所示。端間的信息包分別為和每秒，信息包長度為負(fù)指數(shù)分布，平均包長為k比特，各信道容量分別為c1，c2和c3，和一起排隊(duì)，和一起排隊(duì)，和一起排隊(duì)，均不拒絕，求(1)各種業(yè)務(wù)的平均時延。(2)網(wǎng)絡(luò)的平均時延。(3)各信道的平均利用率。解: 由于均不拒絕且到達(dá)和離去均隨機(jī)，故3個信道均等效于3個M/M/1系統(tǒng)，其中：C1：到達(dá)為。服務(wù)為：c1/bC2：到達(dá)為。服務(wù)為：c2/bC3：到達(dá)為。服務(wù)為：c3/bC1的平均遲延為C1的平均遲延為C1的平均遲延為網(wǎng)絡(luò)的平均時延為：各信道利用率為：2.14總線上有4個用戶v1,v2,v3和v4，它們之間以Alopha方式互相通信，信包到達(dá)率均為每秒，信息包的長度為b比特；總線上的傳輸速率為c比特/秒，試求通過率r，并大致畫出r與b的曲線關(guān)系。解：r與b的曲線關(guān)系如右圖，從直觀上來看，這也是顯然的。總線上一個包的服務(wù)時間秒，總的呼叫量為：，通過量為：通過率： 3.2設(shè)在一個純ALOHA系統(tǒng)中，分組長度ms，總業(yè)務(wù)到達(dá)率pkt/s，試求一個消息成功傳輸?shù)母怕省Ｈ魹镾-ALOHA系統(tǒng)，試求這時消息成功傳輸?shù)母怕剩⑶笠粋€消息分組傳輸時和另一個分組碰撞的概率。解：由題意，ms，pkt/s，則系統(tǒng)的總業(yè)務(wù)量為純ALOHA系統(tǒng)吞吐量滿足，一個消息成功傳輸?shù)母怕蕿镾-ALOHA系統(tǒng)的吞吐量滿足，這時消息成功傳輸?shù)母怕蕿橐粋€消息分組傳輸時和另一個分組碰撞的概率為：。3.3設(shè)在一個S-ALOHA系統(tǒng)中每秒共發(fā)送120次，其中包括原始發(fā)送和重發(fā)。每次發(fā)送需占用一個12.5ms的時隙。試問：系統(tǒng)的歸一化總業(yè)務(wù)量等于多少？第一次發(fā)送就成功的概率等于多少？在一次成功發(fā)送前，剛好有兩次碰撞的概率等于多少？解：由題意，=120次/秒，=12.5ms。（1）。（2）。（3）。3.4設(shè)一條長度為10km的同軸電纜上，接有1000個站，信號在電纜上傳輸速度為200m/us，信號發(fā)送速率為10Mb/s，分組長度為5000b。試問：若用純ALOHA系統(tǒng)，每個站最大可能發(fā)送分組速率等于多少？若用CSMA/CD系統(tǒng)，每個站最大可能發(fā)送分組速率等于多少？解：（1）純ALOHA中，發(fā)送分組不用等待。理想情況下，各站一個接一個發(fā)送分組，互不干擾，發(fā)送分組的最大速率為pkt/s（2）對于CSMA/CD系統(tǒng)，信號傳輸速率為200m/s，對于10km電纜，單程傳播時間為CSMA/CD系統(tǒng)發(fā)送一個分組必須等待的時間為：2t=100us=0.1ms。故每個站的最大可能發(fā)送分組速率為：。4.4有一個n端的全連接圖。試證：（1）無重復(fù)端的環(huán)數(shù)為（2）經(jīng)過某一固定邊e的環(huán)數(shù)為（3）兩個固定端之間的徑數(shù)位(1)環(huán)上有k個端（3≤k≤n），此k個端的選擇方式有種；對于某固定的k端來說，考慮可以生成的環(huán)，任指定一個端，下個端的選取方法公有k-1種，再下端的選法有k-2種，等等，注意，這樣生成的環(huán)可按兩種試圖順序取得，故有種，總的環(huán)數(shù)為(2)某一固定邊e確定了兩個端，經(jīng)過e的環(huán)數(shù)按其過余下端進(jìn)行分類，若環(huán)再過k個端（1≤k≤n-2），有選法種；對于某固定端來說，自然可以生成k!個環(huán)，從而總的環(huán)數(shù)為個。(3)兩個固定端之間的徑按其經(jīng)過端數(shù)分類，其中有一條不經(jīng)過其他端的徑，若經(jīng)過k個端，（1≤k≤n-2），則對于第一個端有（n-2）種選擇，第二個端有（n-3）種選擇，第k個端有（n-k-1）種選擇，共有總的徑數(shù)為4.5試求圖4-44中圖的主樹數(shù)目，并列舉所有的主樹。圖4-44 解：為圖的端編號為v1,v2,v3,v4。 取v3為參考點(diǎn)，有：所得主樹見下:4.6試證明端數(shù)n大于4的連接圖都是非平面圖，并求n=2，3，4的全連接圖為對偶圖。證明：設(shè)有n個端的全聯(lián)接圖為Kn因?yàn)镵5是非平面圖，而當(dāng)n>5時K5是Kn的子圖，從而Kn（n>5）均不是平面圖。一下是對偶圖（注意K4為自對偶圖）。4.7已知一個圖的鄰接矩陣如左，畫出此圖，并求各端之間的最小有向徑長。 對所繪制圖形的端點(diǎn)進(jìn)行編號，得鄰接矩陣。 解：首先作出圖形： 經(jīng)計算：因而有 其余有向徑長均為∞，或不存在。4.8圖有六個端，其無向距離矩陣如下：用P算法，求出最短樹。用K算法，求出最短樹。限制條件為兩端間通信的轉(zhuǎn)接次數(shù)不超過2的最短樹。 解：(1)P算法求解：(2)K算法求解：按最小邊長順序取得：此結(jié)果意味著最短樹不唯一。(3)原圖有一個邊長全為1的基本子圖G1，要求轉(zhuǎn)接次數(shù)小于等于2，若選取G1的任何4個連續(xù)頂點(diǎn)，,作為基礎(chǔ)，然后再按要求增加邊，例如以為基礎(chǔ)，增加，得到一個樹長為7轉(zhuǎn)接次數(shù)小于等于2的樹T1，事實(shí)上，以任何4個連續(xù)頂點(diǎn)均可得到樹長為7的轉(zhuǎn)接次數(shù)小于等于2的樹4.9圖有六個端，端點(diǎn)之間的有向距離矩陣如下：(1)用D算法求V1到所有其他端的最短徑長及其路徑。(2)用F算法求最短徑矩陣和路由矩陣，并找到V2至V4和V1至V5的最短徑長及路由。(3)求圖的中心和中點(diǎn)。解：(1)D算法V1V2V3V4V5V6指定最短徑長0∞∞∞∞∞V1W1＝0913∞∞V3W13＝0932∞V5W15＝0837V4W14＝087V3W16＝08V2W12＝0(2)F算法最短路徑矩陣及最短路由陣為W5，R5 有向距離為4 有向距離為2(3) 中心為V3或V5 中心為V2補(bǔ)充習(xí)題：試計算完全圖Kn的主樹的數(shù)目。解：設(shè)A為Kn的關(guān)聯(lián)陣，那么主樹的數(shù)目為：證畢。5.1求下圖中Vs到Vt的最大流量fst,圖中編上的數(shù)字是該邊的容量。解： 本題可以利用M算法，也可以使用最大流－最小割簡單計算可知： 可知：最大流為12，可以安排為fs1=3,，fs2=5，f12=1，f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。5.2試移動上圖中的一條邊，保持其容量不變，是否能增大fst？如果可以，求此時的最大值，但若所有轉(zhuǎn)接端v1v2v3和v4的轉(zhuǎn)接容量限制在4，則情況將如何？解： 依然按照最大流－最小割定理，若能依一邊從X找到內(nèi)部至割中，自然可以增大流量，可以將e34移去，改為：e41或者e42均可，使總流量增至12＋2＝14。當(dāng)vi(i=1,...4)的轉(zhuǎn)接容量限制到4時，等效圖為右圖，對于3.11中的流量分配，在本題限制下，若將fs2由5改為4即得到一個流量為11的可行流。但若，則，換句話說就是11已是最大流。5.3圖5-12中的Vs和Vt間要求有總流量fst＝6，求最佳流量分配，圖中邊旁的兩個數(shù)字前者為容量，后者為費(fèi)用。解： 本題可以任選一個容量為6的可行流，然后采用負(fù)價環(huán)法，但也可用貪心算法，從Vs出發(fā)的兩條線路費(fèi)用一樣，但進(jìn)入Vt的兩條路徑費(fèi)用為7和2，故盡可能選用費(fèi)用為2的線路，得下圖1。圖1再考慮V0，進(jìn)入V0的兩條路徑中優(yōu)先滿足費(fèi)用為3的路徑，得：圖2，很容易得到最后一個流量為fst=6的圖3，邊上的數(shù)字為流量安排。總的費(fèi)用為易用負(fù)價環(huán)驗(yàn)證圖4的流量分配為最佳流量分配。

6.1由n個元件構(gòu)成的一個系統(tǒng)，各元件的平均壽命都是T。當(dāng)一個元件失效據(jù)使得系統(tǒng)失效的情況下，已知系統(tǒng)的平均壽命將下降至T/n，如果采取容錯措施，當(dāng)m個以上元件失效才使系統(tǒng)失效，求證此系統(tǒng)的平均壽命為：可見比未采取措施前提高至少m倍。當(dāng)m=n-1時，這一系統(tǒng)實(shí)際上即是n個元件的并接系統(tǒng)，試證上式即轉(zhuǎn)化成并連系統(tǒng)的壽命公式。證：以i狀態(tài)代表有i個元件失效的狀態(tài)，此時系統(tǒng)的狀態(tài)轉(zhuǎn)移框圖如下：那么狀態(tài)i的平均壽命為：從而系統(tǒng)的平均壽命為：當(dāng)m=n-1時而利用數(shù)學(xué)歸納法易知：6.3有n個不可修復(fù)系統(tǒng)，它們的平均壽命都是T。先取兩個作為并接，即互為熱備份運(yùn)行；當(dāng)有一個損壞時，啟用第三個作為熱備份；再損壞一個是起用第四個，已知下去，直到n個系統(tǒng)均損壞。忽略起用冷備份期間另一系統(tǒng)損壞的可能性；試計算這樣運(yùn)行下的平均壽命；并與全冷備份和全熱備份是的平均壽命相比較。解：狀態(tài)圖如下：i表示有i個系統(tǒng)損壞，失效在圖中標(biāo)出。由上圖有：從而，平均壽命：6.4上題目中n個子系統(tǒng)都是可修復(fù)系統(tǒng)，可靠度都是R。仍用上述方式運(yùn)行，一損壞系統(tǒng)修復(fù)后作為最后一個系統(tǒng)排隊(duì)等候再起用，求穩(wěn)態(tài)可靠度。解： m，n-m表示n個系統(tǒng)中有m個失效，狀態(tài)轉(zhuǎn)移圖及失效率與修復(fù)率如圖：用Pm表示狀態(tài)m,n-m的概率（穩(wěn)態(tài)），狀態(tài)方程如下：解狀態(tài)方程如下：有： 由歸一性：穩(wěn)態(tài)可靠度：其中，R是單一系統(tǒng)的可靠度。6.5一個復(fù)雜系統(tǒng)有n級梯形結(jié)構(gòu)組成如圖所示。其中有n個子系統(tǒng)作為橋，2(n+1)個子系統(tǒng)作為梯邊，它們都是可靠度為R的可以修復(fù)系統(tǒng)。求這個復(fù)雜系統(tǒng)的可靠度遞推公式，假定所有子系統(tǒng)都互相獨(dú)立。解： 依次考慮1，2，3，…n。依照各個橋的情況可以分類，根據(jù)1，2，3，…n的好壞情況可以得到以下結(jié)果：情況概率可靠度ⅠR[1-(1-R)2]Rn-1ⅡR(1-R)[1-(1-R2)2]Rn-2ⅢR(1-R)2[1-(1-R3)2]Rn-3┇NR(1-R)n-1[1-(1-Rn)2]R0N+1(1-R)n1-(1-Rn+1)2 其中：6.6有一個故障率為的系統(tǒng)，為了考慮是否使之成為可修復(fù)系統(tǒng)而配備維修力量，分別計算兩類可靠度，試證明作為不可修復(fù)系統(tǒng)在時間T以內(nèi)的可靠度大于作為可修復(fù)系統(tǒng)的穩(wěn)態(tài)可靠度的條件是：解：故障率為的不可修復(fù)系統(tǒng)在T（）內(nèi)的可靠度為： 的可修復(fù)系統(tǒng)的穩(wěn)定可靠度為現(xiàn)： >或> 6.7有一故障率為，修復(fù)率為的系統(tǒng)，已知此系統(tǒng)的費(fèi)用是 其中A，B，r，s為已知的非負(fù)常量，求可靠度為0.99時的最小費(fèi)用。解： 令：有 6.8用流量法求圖5－9(b)中的二分網(wǎng)的聯(lián)接度和結(jié)合度，只考慮端故障，且各端的可靠度均為R，求1端和5'端間的聯(lián)接概率。解：圖5－9(b)中的二分圖，任意一端度數(shù)均為4，容易知道： 一知考慮端故障，故中有