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

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

40310100

50021010

2021-1001

σ

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

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

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時(shí)，

S3=0,1,2,3,473、K=2時(shí)，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時(shí)，B：分U2，盈利g2(U2)C：分S2-U83、K=1時(shí)，

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時(shí)，

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中國郵遞員問題（管梅谷）右圖為一街道圖。點(diǎn)表示街口，線表示街道。v點(diǎn)處有一郵局。某郵遞員從郵局v出發(fā)送郵件，需每條街至少經(jīng)過一次，最后回到郵局。問他應(yīng)怎樣選擇路線，才能使走的路程最短？v中國郵遞員問題（管梅谷）右圖為一街道圖。點(diǎn)表示街口，線表示街17圖的基本概念圖:反映現(xiàn)象之間關(guān)系的工具,由點(diǎn)和點(diǎn)間連線組成。如四國單循環(huán)制足球邀請賽，以圖表示賽制V1V2V3V4圖的基本概念圖:反映現(xiàn)象之間關(guān)系的工具,由點(diǎn)和點(diǎ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無向圖兩點(diǎn)間不帶箭頭的聯(lián)線稱邊邊的集合記為E點(diǎn)的集合記為V一個(gè)由點(diǎn)及邊構(gòu)成的圖，稱為無向圖，記為G=(V,E

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

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

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

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

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

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

)是圖G=(V,E

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

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

=(V,E′

)是圖G=(V,E

)的一個(gè)支撐樹，則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個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，可能連通的途徑如圖，請?jiān)O(shè)計(jì)一個(gè)鋪線方法既能連通7個(gè)學(xué)院辦公室，又使總的線路長度最短。v1v2v3v4v5v6125333748v7104例：某大學(xué)準(zhǔn)備對所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，可能連通的途38v1v2v3v4v5v6125333748v7123337v1v2v3v4v5v6v7104w（T﹡）=19v1v2v3v4v5v6125333748v7123337v39最短路問題v1v8v7v6v5v4v3v26341014366122410﹢∞﹢∞﹢∞﹢∞﹢∞﹢∞﹢∞＼v16v13v11v411v59v35v26v510v512＼＼＼＼＼＼＼＼0最短路問題v1v8v7v6v5v4v3v263410143640Dijkstra標(biāo)號法?使用兩種標(biāo)號給圖中每一點(diǎn)vi標(biāo)號：T標(biāo)號（Temporarylabel），P標(biāo)號（Permanentlabel）。?給vi點(diǎn)一個(gè)P標(biāo)號時(shí)，表示從始點(diǎn)vs到vi點(diǎn)的最短路權(quán)，此標(biāo)號不再改變；給vi點(diǎn)一個(gè)T標(biāo)號時(shí)，表示從vs到vi點(diǎn)的最短路權(quán)的上界，是一種臨時(shí)標(biāo)號，沒有得到P標(biāo)號的點(diǎn)都是T標(biāo)號。?計(jì)算的每一步就是把某一點(diǎn)的T標(biāo)號改為P標(biāo)號，當(dāng)所有點(diǎn)都得到P標(biāo)號時(shí)，計(jì)算結(jié)束。Dijkstra標(biāo)號法?使用兩種標(biāo)號給圖中每一點(diǎn)vi標(biāo)號：41Dijkstra標(biāo)號法步驟1、給始點(diǎn)vs以P標(biāo)號，P(vs)=0，其余各點(diǎn)給T標(biāo)號，T（vi）=﹢∞2、若vi點(diǎn)為剛得到P標(biāo)號的點(diǎn)，考慮與vi相鄰的另一頂點(diǎn)vj，且vj為T標(biāo)號。對vj的T標(biāo)號進(jìn)行如下更改：T（vj）=min[T（vj）,P(vi)+Lij]3、比較所有具有T標(biāo)號的點(diǎn)，把最小者改為P標(biāo)號若全部點(diǎn)均為P標(biāo)號則停止，否則轉(zhuǎn)回第2步。Dijkstra標(biāo)號法步驟1、給始點(diǎn)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費(fèi)用5681118年份12345價(jià)格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（弧的容量），且存在一個(gè)發(fā)點(diǎn)Vs和一個(gè)收點(diǎn)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ò)上的一個(gè)流。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)中，對任一?。╲i,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）平衡條件：對于中間點(diǎn)：流入的流量=流出的流量對于發(fā)點(diǎn)Vs和收點(diǎn)Vt：Vs的流出量=Vt的流入量對于一個(gè)網(wǎng)絡(luò)，可行流總存在，如所有fij=0，就是一可行流，v(f)=0。3、可行流滿足下列條件的流稱為可行流。對于一個(gè)網(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)用范圍交通運(yùn)輸網(wǎng)絡(luò)中，存在人流、車流、貨物流，供水供氣網(wǎng)絡(luò)中存在水流、氣流，通訊系統(tǒng)中有信息流…。最大流問題就是在一定條件下，使網(wǎng)絡(luò)系統(tǒng)中的某種流的流量達(dá)到最大。網(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、