運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析

1、會(huì)計(jì)學(xué)1運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析22022-4-273歐拉回路歐拉回路：經(jīng)過每邊且僅一次：經(jīng)過每邊且僅一次 厄尼斯堡七橋問題、郵路問題厄尼斯堡七橋問題、郵路問題哈密爾頓回路哈密爾頓回路：經(jīng)過每點(diǎn)且僅一次：經(jīng)過每點(diǎn)且僅一次 貨郎擔(dān)問題、快遞送貨問題貨郎擔(dān)問題、快遞送貨問題4圖圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。 例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示，圖來表示，圖8.18.1就是一個(gè)表示這種關(guān)系的圖。就是一個(gè)表示這種關(guān)系的圖。(v1)趙趙(v2)錢錢(v3)孫孫(

2、v4)李李(v5)周周(v6)吳吳(v7)陳陳e2e1e3e4e5圖圖8.15 描述描述對(duì)象之間關(guān)系對(duì)象之間關(guān)系， 研究研究特定關(guān)系之間的內(nèi)在規(guī)律特定關(guān)系之間的內(nèi)在規(guī)律， 圖圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系反映對(duì)象之間的關(guān)系并不是重要并不是重要的。的。(v1)趙趙(v2)錢錢孫孫(v3) 李李(v4)周周(v5)吳吳(v6)陳陳(v7)e2e1e3e4e5圖圖8.26a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙趙(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳

3、吳(v7)陳陳圖圖8.3 如果我們把上面例子中的如果我們把上面例子中的“相互認(rèn)識(shí)相互認(rèn)識(shí)”關(guān)系改為關(guān)系改為“認(rèn)識(shí)認(rèn)識(shí)” 的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧弧。2022-4-27782022-4-279完全圖完全圖：每一對(duì)頂點(diǎn)間都有邊（?。┫噙B的簡(jiǎn)單圖：每一對(duì)頂點(diǎn)間都有邊（弧）相連的簡(jiǎn)單圖2022-4-2710出次出次：d+(vi)入入次次：d-(vi)d (vi) = d+(vi) + d-(vi)()(iivdvd定理定理1 1 頂點(diǎn)次數(shù)總和

4、等于邊數(shù)的兩倍。頂點(diǎn)次數(shù)總和等于邊數(shù)的兩倍。定理定理2 2 次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。mvdnii2)(111),(),(EVGEVGEEVV,GG EEVV,GG EEVV,12ikivv0ikivv0132022-4-27142022-4-2715歐拉回路歐拉回路：經(jīng)過每邊且僅一次：經(jīng)過每邊且僅一次 厄尼斯堡七橋問題、郵路問題厄尼斯堡七橋問題、郵路問題 充要條件：充要條件：無向無向圖中無奇點(diǎn)，有向圖每個(gè)頂點(diǎn)出次等于入次圖中無奇點(diǎn)，有向圖每個(gè)頂點(diǎn)出次等于入次16 圖圖8-4中，中，(a)就是一個(gè)樹，而就是一個(gè)樹，而(b)因?yàn)閳D中有圈所以就不是因?yàn)閳D中有圈所以就不是樹

5、，樹， (c)因?yàn)椴贿B通所以也不是樹。因?yàn)椴贿B通所以也不是樹。圖圖8-4v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)1718(a)(b)(c)生成（支撐）樹生成（支撐）樹若若 , ,則則GG是是G G的的支撐（生成支撐（生成）樹）樹。19最小生成樹最小生成樹問題問題就是指在一個(gè)賦權(quán)的連通的無向圖就是指在一個(gè)賦權(quán)的連通的無向圖G G中找出一中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。2021SSS222022-4-27232022-4-27242022

6、-4-2725 霍夫曼樹：霍夫曼樹：最優(yōu)二叉樹最優(yōu)二叉樹siiilpTm1min)(2627一、狄氏標(biāo)號(hào)法（一、狄氏標(biāo)號(hào)法（Dijkstra算法）算法）2022-4-27282022-4-27292022-4-2730 役役齡齡項(xiàng)目項(xiàng)目012345效益效益vk(t)54.543.7532.5維修費(fèi)維修費(fèi)uk(t)0.511.522.53更新費(fèi)更新費(fèi)ck(t)-1.52.22.533.52022-4-2731321( )max(), (11,2, )ijj nd idn 1( )min( )i nd rd i 例例8-11 8-11 某連鎖企業(yè)有某連鎖企業(yè)有6 6個(gè)銷售點(diǎn)，問倉庫應(yīng)建在哪個(gè)地點(diǎn)個(gè)

7、銷售點(diǎn)，問倉庫應(yīng)建在哪個(gè)地點(diǎn)，可使各銷售點(diǎn)離倉庫較近？，可使各銷售點(diǎn)離倉庫較近？2022-4-273334( )111, (2,3, )kkijkkDdDDkpDW)1()1()1(,minkkjkikkijkijdddd二、二、Floyd算法算法2022-4-2735例例8-12 8-12 求任意兩點(diǎn)間的最短路求任意兩點(diǎn)間的最短路2022-4-27362022-4-27372022-4-273839第四節(jié)最大流問題第四節(jié)最大流問題AjixXij),(),(, 0),(,0tsixxAjicxjijjjiijij)(,)(,tifsifxxjjijij40StSsSSSSVAVN,),(IU)

8、,(),(),(SSjiijcSSc)*,(*SScc 2022-4-2741),()(SSCXf?),()(*SSCXf2022-4-2742）（X),(,0),(,0jixcjicxijijijij?)(*Xff),(,0)(,)(,),(, 0)(,. .maxAjicxVitiftsisifxxtsfijijjjjiij2022-4-274445),(,),(,),(,),(,),(,min)() (jixjixjixxjixjixcXfXfijijijijijijij?4.調(diào)整量調(diào)整量),(minijijjxcibbijijrx ijijrx 0jix),(minjijxibb ),

9、(,),(,jixjixxijijij當(dāng)當(dāng)47例例8-138-13（1 1）計(jì)算機(jī)編程）計(jì)算機(jī)編程48（2 2）手算）手算2415223332tsf*=112022-4-27492022-4-2750162511622633524415213314321352323341455tststststs511.1. 先先求出此網(wǎng)絡(luò)圖中的最大求出此網(wǎng)絡(luò)圖中的最大流量流量f f。2.2. 在在最大最大流量流量f f的的所有解中，找出一個(gè)最小費(fèi)用的所有解中，找出一個(gè)最小費(fèi)用的解解（一）線性（一）線性( (整數(shù)整數(shù)) )規(guī)劃法規(guī)劃法2022-4-2752第一步第一步ijijtststtsssscxxxxxx

10、xxxxxxxxxtsxxf0. .max3231323212131211312121第第二二步步ijijtststtssjiijijcxxxxxxxxxxxfxxxxtsxdz0. .min32313232121312113121,53（二）網(wǎng)絡(luò)分析法（二）網(wǎng)絡(luò)分析法542022-4-2755565758圖圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。 例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示，圖來表示，圖8.18.1就是一個(gè)表示這種關(guān)系的圖。就是一個(gè)表示這種關(guān)系的圖。(v1)趙趙(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳e2e1e3e4e5圖圖8.159一、狄氏標(biāo)號(hào)法（一、狄氏標(biāo)號(hào)法（Dijkstra算法）算法）2022-4-27602022-4-2761),(,0)(,)(,),(, 0