大學(xué)本科-運籌學(xué)-教程-運籌學(xué)-第八章-圖與網(wǎng)絡(luò)分析課件

一、考慮下面給出的不完全初始單純形表：C63025000θcBxBbX1X2X3X4X5X6

40310100

50021010

2021-1001

σ

1、把上面的表格填寫完整；2、按照上面的完整表格，寫出此線性規(guī)劃模型；3、寫出初始基可行解和其對應(yīng)的目標(biāo)函數(shù)值；4、為下一次迭代確定進基變量和出基變量，說明理由，并在表格上標(biāo)出主元素。5、若解得此模型對偶問題最優(yōu)解之一y1﹡=m，試說明其經(jīng)濟意義。一、考慮下面給出的不完全初始單純形表：C63025000θc1二、求解下列運輸問題，說明初始調(diào)運表中某變量檢驗數(shù)為負(fù)的經(jīng)濟意義。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A283741642088A3571062銷量5526

二、求解下列運輸問題，說明初始調(diào)運表中某變量檢驗數(shù)為負(fù)的經(jīng)濟2三、五人翻譯五種外文的速度（百個印刷符號/小時）如下表所示：語種人英俄日德法甲乙98456981056丙97358丁48695戊653108若規(guī)定每人專門負(fù)責(zé)一個語種的翻譯工作，應(yīng)如何指派，使總的翻譯效率最高？三、五人翻譯五種外文的速度（百個印刷符號/小時）如下表所示：3作業(yè)：將資金分配看作三階段的動態(tài)過程1(項目A)2(項目B)3(項目C)可分配資金S1百萬元可分配資金S2可分配資金S3分配U1百萬元分配u2S4=0分配u3作業(yè)：將資金分配看作三階段的動態(tài)過程1(項目A)2(項目B4資源分配問題模型1、設(shè)階段為分配過程（步驟），K=1，2，32、狀態(tài)變量SK為第K步可供分配的資金數(shù)(百萬元)3、決策變量UK為分配給第K各項目的資金數(shù)4、狀態(tài)轉(zhuǎn)移方程：SK+1=SK－UK5、gK(UK)為UK資金分配給該項目所產(chǎn)生的收益6、fk(Sk)=max{gK+fk+1(SK+1)}

f4(S4)=0基本方程邊界條件資源分配問題模型1、設(shè)階段為分配過程（步驟），K=1，2，351、f4(S4)=0,fk(Sk)=max{gK(UK)+fk+1(SK+1)}2、K=3時，S3=0,1,2,3,4=max{g3(U3)+f4(S4)}=max[g3(U3)]∴U3=0,1,2,3,4f3(S3)1(項目A)2(項目B)3(項目C)可分配資金S1百萬元可分配資金S2可分配資金S3分配U1百萬元分配u2S4=0分配u31、f4(S4)=0,fk(Sk)62、K=3時，

S3=0,1,2,3,4U3=0,1,2,3,4

f3(S3)

=max{g3(U3)

+f4(S4)}

=max[g3(U3)]

47070437070326868216262103838043210U3﹡f3(S3)g3(U3)U3

S301234A3841486066B4042506065C38626870702、K=3時，

S3=0,1,2,3,473、K=2時，S2=0,1,2,3,4

B：分U2，盈利g2(U2)

C：分S2-U2，盈利f3(S3)

f2(S2)=max{g2(U2)+f3(S3)}312265+3860+6250+6842+7040+70211260+3850+6242+6840+70010850+3842+6240+68010242+3840+6207840+384321043210U2﹡f2(S2)g2(U2)+f3(S3)U2

S2S3f3(S3)U3﹡0380162126823703470401234A3841486066B4042506065C38626870703、K=2時，B：分U2，盈利g2(U2)C：分S2-U83、K=1時，

S1=4

甲：分U1，盈利g1(U1)

乙+丙：分4

–U1，盈利f2(S2)

f1(S1)=max{g1(U1)+f2(S2)}316266+7860+10248+10841+11238+122443210U1﹡f1(S1)g1(U1)+f2(S2)U1

S1S3f3(S3)U3﹡07801102021080311224122301234A3841486066B4042506065C38626870703、K=1時，

S1=4

甲：分U9資金分配問題最優(yōu)方案A：追加投資3百萬元B：0C：追加投資1百萬元

最大盈利162百萬元資金分配問題最優(yōu)方案A：追加投資3百萬元10s.t.X11+X12+

X13+

X14+

X15≤1

，

X21+X22+

X23+

X24+

X25≤1X31+X32+

X33+

X34+

X35≤1

，

設(shè)xij=1第i電廠在第j年投資0第i電廠在第j年不投資X41+X42+

X43+

X44+

X45≤170X11+50X21+

60X31+

40X41≥30

，

70(X11+X12)

+50(X21+X22)

+

60(X31+X32)

+

40(X41+X42)

≥50

，

70(X11+X12+

X13)

+50(X21+X22+

X23)

+

60(X31+X32+

X33)

+

40(X41+X42+

X43)

≥70

，

70(X11+X12+

X13+

X14)

+50(X21+X22+

X23+

X24)

+

60(X31+X32+

X33+

X34)

+

40(X41+X42+

X43+

X44)

≥90

，

70(X11+X12+

X13+

X14+

X15)

+50(X21+X22+

X23+

X24+

X25)

+

60(X31+X32+

X33+

X34+

X35)

+

40(X41+X42+

X43+

X44+

X45)

≥110

s.t.X11+X12+X13+X14+11作業(yè):9468585910697358486951053681642525104137526241505742作業(yè):94685859106973584869510536812minZ′=∑∑(-cij)xijminZ〞=∑∑(M-cij)xij其中M是一大的常數(shù)目標(biāo)函數(shù)極大化maxZ=∑∑cijxij0310234003115406020303530minZ′=∑∑(-cij)xijminZ〞=∑∑(M13第八章圖與網(wǎng)絡(luò)分析第八章圖與網(wǎng)絡(luò)分析14圖論的起源哥尼斯堡七橋問題ABDCABCD圖論的起源哥尼斯堡七橋問題ABDCABCD15一筆劃問題V1V2V3V5V4一筆劃問題V1V2V3V5V416中國郵遞員問題（管梅谷）右圖為一街道圖。點表示街口，線表示街道。v點處有一郵局。某郵遞員從郵局v出發(fā)送郵件，需每條街至少經(jīng)過一次，最后回到郵局。問他應(yīng)怎樣選擇路線，才能使走的路程最短？v中國郵遞員問題（管梅谷）右圖為一街道圖。點表示街口，線表示街17圖的基本概念圖:反映現(xiàn)象之間關(guān)系的工具,由點和點間連線組成。如四國單循環(huán)制足球邀請賽，以圖表示賽制V1V2V3V4圖的基本概念圖:反映現(xiàn)象之間關(guān)系的工具,由點和點間連線組18例:（V1）張林（V2）孫（V3）（V4）李吳（V6）王（V5）鄭（V7）例:（V1）張林（V2）孫（V3）（V4）李吳（V6）王（V19（V1）張孫（V2）林（V3）（V4）李吳（V6）王（V5）鄭（V7）（V1）張孫（V2）林（V3）（V4）李吳（V6）王（V5）20若以圖表示比賽結(jié)果V1V2V3V4若以圖表示比賽結(jié)果V1V2V3V421（V1）張王（V2）孫（V3）（V4）李吳（V6）林（V5）鄭（V7）（V1）張王（V2）孫（V3）（V4）李吳（V6）林（V5）22無向圖兩點間不帶箭頭的聯(lián)線稱邊邊的集合記為E點的集合記為V一個由點及邊構(gòu)成的圖，稱為無向圖，記為G=(V,E

)V1V2V3V4無向圖兩點間不帶箭頭的聯(lián)線稱邊V1V2V3V423有向圖兩點間帶箭頭的聯(lián)線稱弧弧的集合記為A一個由點及弧構(gòu)成的圖，稱為有向圖，記為D=(V,A

)V1V2V3V4有向圖兩點間帶箭頭的聯(lián)線稱弧V1V2V3V424點的次以點v為端點的邊的個數(shù)稱為點v的次次為1的點——懸掛點

次為0的點——孤立點天津南京常州上海杭州鄭州連云港濟南徐州臺北點的次以點v為端點的邊的個數(shù)稱為點v的次次為1的點次為0的點25鏈和圈鏈中，若vi1=vik，則稱此鏈為一個圈。一個點邊交錯的序列(vi1,ei1,vi2,ei1,…vik-1,eik-1,vik)稱為一條聯(lián)結(jié)vi1和vik鏈。V1V2V3V5V4e1e3e2e4e5e6e7鏈和圈鏈中，若vi1=vik，則稱此鏈為一個圈。一個點邊交26連通圖圖G=(V,E

)中，若任何兩點之間，至少有一條鏈，則稱G為連通圖，否則為不連通圖。連通圖圖G=(V,E)中，若任何兩點之間，至少有一條鏈，27路和回路在有向圖中，若點弧交錯形成的鏈中弧方向均相同，則為一條路。有向圖中若點弧交錯形成的圈中弧方向均相同，則為一條回路。v7v6v5v4v3v26341014366122410v8v1路和回路在有向圖中，若點弧交錯形成的鏈中弧方向均相同，則為一28支撐子圖給定圖G=(V,E

)，若有圖G′=(V′,E′

)，使V′=V,E′∈E，則G′稱G是的一個支撐子圖。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e3e2e5e6支撐子圖給定圖G=(V,E)，若有圖G′=(V′,E′29樹一個無圈的連通圖為樹。樹的性質(zhì)如下：必有次為1的點，稱為樹葉。樹是無回路的連通圖，所以任意兩點之間有且僅有一條通路，任意去掉一個樹枝，樹被分成不連通圖。天津南京常州上海鄭州連云港濟南徐州樹一個無圈的連通圖為樹。樹的性質(zhì)如下：必有次為1的點，稱為30樹樹的任意兩個頂點間加一條邊，構(gòu)成一個回路，不再成為樹。一個連通圖有很多樹，這些樹都是原連通圖的部分圖，即包括了原連通圖的所有頂點。天津南京常州上海鄭州連云港濟南徐州樹樹的任意兩個頂點間加一條邊，構(gòu)成一個回路，不再成為樹。天津31支撐樹若圖T=(V,E′

)是圖G=(V,E

)的支撐子圖，且G′是一個樹，則稱T是G的一個支撐樹。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e2e4e5支撐樹若圖T=(V,E′)是圖G=(V,E)的支撐子32最小支撐樹在圖G=(V,E

)中，對每條邊[vi,vj]相應(yīng)給一個數(shù)wij，則G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。權(quán)可表示距離、時間、費用等。w12w25w23w34w45w15V1V2V3V5V4w25最小支撐樹在圖G=(V,E)中，對每條邊[vi,vj33最小支撐樹若T

=(V,E′

)是圖G=(V,E

)的一個支撐樹，則E′中所有邊的權(quán)之和為支撐樹T的權(quán)。若支撐樹T﹡的權(quán)w（T﹡）是G的所有支撐樹的權(quán)中最小者，則稱T﹡是G的最小支撐樹（最小樹）。w12w25w23w34w45w15V1V2V3V5V4w25最小支撐樹若T=(V,E′)是圖G=(V,E)的一34w12w23w45w15V1V2V3V5V4w12w23w34w45V1V2V3V5V4w12w23w34V1V2V3V5V4w25w12w25w23w34w45w15V1V2V3V5V4w12w23w45w15V1V2V3V5V4w12w23w335254453v1v2v3v4243v1v2v3v4最小支撐樹的避圈法w（T﹡）=9254453v1v2v3v4243v1v2v3v4最小支撐樹36最小支撐樹的破圈法254453v1v2v3v4254453v1v2v3v4w（T﹡）=9最小支撐樹的破圈法254453v1v2v3v4254453v37例：某大學(xué)準(zhǔn)備對所屬的7個學(xué)院辦公室計算機聯(lián)網(wǎng)，可能連通的途徑如圖，請設(shè)計一個鋪線方法既能連通7個學(xué)院辦公室，又使總的線路長度最短。v1v2v3v4v5v6125333748v7104例：某大學(xué)準(zhǔn)備對所屬的7個學(xué)院辦公室計算機聯(lián)網(wǎng)，可能連通的途38v1v2v3v4v5v6125333748v7123337v1v2v3v4v5v6v7104w（T﹡）=19v1v2v3v4v5v6125333748v7123337v39最短路問題v1v8v7v6v5v4v3v26341014366122410﹢∞﹢∞﹢∞﹢∞﹢∞﹢∞﹢∞＼v16v13v11v411v59v35v26v510v512＼＼＼＼＼＼＼＼0最短路問題v1v8v7v6v5v4v3v263410143640Dijkstra標(biāo)號法?使用兩種標(biāo)號給圖中每一點vi標(biāo)號：T標(biāo)號（Temporarylabel），P標(biāo)號（Permanentlabel）。?給vi點一個P標(biāo)號時，表示從始點vs到vi點的最短路權(quán)，此標(biāo)號不再改變；給vi點一個T標(biāo)號時，表示從vs到vi點的最短路權(quán)的上界，是一種臨時標(biāo)號，沒有得到P標(biāo)號的點都是T標(biāo)號。?計算的每一步就是把某一點的T標(biāo)號改為P標(biāo)號，當(dāng)所有點都得到P標(biāo)號時，計算結(jié)束。Dijkstra標(biāo)號法?使用兩種標(biāo)號給圖中每一點vi標(biāo)號：41Dijkstra標(biāo)號法步驟1、給始點vs以P標(biāo)號，P(vs)=0，其余各點給T標(biāo)號，T（vi）=﹢∞2、若vi點為剛得到P標(biāo)號的點，考慮與vi相鄰的另一頂點vj，且vj為T標(biāo)號。對vj的T標(biāo)號進行如下更改：T（vj）=min[T（vj）,P(vi)+Lij]3、比較所有具有T標(biāo)號的點，把最小者改為P標(biāo)號若全部點均為P標(biāo)號則停止，否則轉(zhuǎn)回第2步。Dijkstra標(biāo)號法步驟1、給始點vs以P標(biāo)號，P(42無向圖的Dijkstra標(biāo)號法v1v9v8v7v6v5v4v3v26334210143662122﹢∞＼65＼﹢∞3＼﹢∞＼﹢∞7＼﹢∞1110＼＼﹢∞8＼1﹢∞9＼﹢∞12＼＼6＼110無向圖的Dijkstra標(biāo)號法v1v9v8v7v6v5v443用最短路解設(shè)備更新問題v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53年數(shù)0-11-22-33-44-5費用5681118年份12345價格1111121213用最短路解設(shè)備更新問題v1v2v3v4v5v6161822444v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53v1v2v3v4v5v616182241302230165945網(wǎng)絡(luò)最大流問題vsv4v2vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）v3v1（4，2）例：流量容量網(wǎng)絡(luò)最大流問題vsv4v2vt（4，3）（3，2）（5，2）46基本概念1、網(wǎng)絡(luò)在有向連通圖D=(V,A

)中，D的每條弧上有非負(fù)數(shù)的權(quán)Cij（弧的容量），且存在一個發(fā)點Vs和一個收點Vt，則稱此D為網(wǎng)絡(luò)。記為：D=(V,A,C

)vsv3v4v2v1vt241153253基本概念1、網(wǎng)絡(luò)vsv3v4v2v1vt241153253472、流在網(wǎng)絡(luò)D=(V,A,C

)中，對任一?。╲i,vj）有流量fij，稱集合f={fij}為網(wǎng)絡(luò)上的一個流。vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3）（2，1）Cij（1，1）2、流在網(wǎng)絡(luò)D=(V,A,C)中，對任一弧（vi,482、流如：vsv3v4v2v1vt3311023112、流如：vsv3v4v2v1vt3493、可行流vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3）（2，1）（1，1）（3，4）（5，2）3、可行流vsv3v4v2v1vt（4，3）（3，3）（5，503、可行流滿足下列條件的流稱為可行流。（1）容量限制條件：0≤fij≤Cij（2）平衡條件：對于中間點：流入的流量=流出的流量對于發(fā)點Vs和收點Vt：Vs的流出量=Vt的流入量對于一個網(wǎng)絡(luò)，可行流總存在，如所有fij=0，就是一可行流，v(f)=0。3、可行流滿足下列條件的流稱為可行流。對于一個網(wǎng)絡(luò)，可行流總51vsv3v4v2v1vt（4，0）（3，0）（5，0）（1，1）（3，0）（2，0）（5，0）（2，0）（1，1）vsv3v4v2v1vt（4，0）（3，0）（5，0）（1，524、最大流網(wǎng)絡(luò)中，從Vs到Vt流量最大的可行流為該網(wǎng)絡(luò)的最大流。vsv4vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）v3v1（4，2）v2v4vt（4，3）（3，3）（5，2）（1，0）（5，3）v3v1（4，2）v2vs（2，2）4、最大流網(wǎng)絡(luò)中，從Vs到Vt流量最大的可行流為該網(wǎng)絡(luò)的最大53網(wǎng)絡(luò)最大流問題應(yīng)用范圍交通運輸網(wǎng)絡(luò)中，存在人流、車流、貨物流，供水供氣網(wǎng)絡(luò)中存在水流、氣流，通訊系統(tǒng)中有信息流…。最大流問題就是在一定條件下，使網(wǎng)絡(luò)系統(tǒng)中的某種流的流量達到最大。網(wǎng)絡(luò)最大流問題應(yīng)用范圍54有增廣鏈：vsv4v2v2vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）vsv3v1vt（4，2）（3，2）（1，1）（2，1）v3（3，3）（2，2）（1，0）有增廣鏈：vsv4v2v2vt（4，3）（3，2）（5，2）555、