圖與網(wǎng)絡(luò)分析ppt課件(編輯修改稿)
2025-02-10 12:34 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門(mén)就要決定是購(gòu)買(mǎi)新的（支付購(gòu)置費(fèi)），還是繼續(xù)使用舊的（支付維修費(fèi)），試制定一個(gè)五年內(nèi)設(shè)備更新的計(jì)劃，使得總的支付費(fèi)用最少。 第 i年度 1 2 3 4 5 購(gòu)置費(fèi) 11 11 12 12 13 設(shè)備役齡 01 12 23 34 45 維修費(fèi)用 5 6 8 11 18 解：（ 1）分析：可行的購(gòu)置方案（更新計(jì)劃）很多！ 如： 1） 每年購(gòu)置一臺(tái)新的 ， 則對(duì)應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購(gòu)置新的 ， 一直用到第五年年底 ， 則總費(fèi)用為： 11+5+6+8+11+18 = 59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。 （ 2）方法：將此問(wèn)題用一個(gè)賦權(quán)有向圖來(lái)描述，然后求這個(gè)賦權(quán)有向圖的最短路。 設(shè) Vi 表示第 i年初， (Vi ,Vj )表示第 i 年初購(gòu)買(mǎi)新設(shè)備用到第 j年初（ j1年底），而 Wij 表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從 V1 到 V6的一條路。 例四、 某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時(shí)間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購(gòu)置設(shè)備，每年需支付購(gòu)置費(fèi)用；若繼續(xù)使用舊設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化會(huì)逐年增加。計(jì)劃期（五年）內(nèi)中每年的購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表所示，工廠要制定今后五年設(shè)備更新計(jì)劃，問(wèn)采用何種方案才能使包括購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。 年份 1 2 3 4 5 購(gòu)置費(fèi) 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費(fèi) 5 7 12 18 25 年份 1 2 3 4 5 購(gòu)置費(fèi) 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費(fèi) 5 7 12 18 25 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 30 作業(yè) P282:, 課堂練習(xí)： 例 1:10名研究生參加 6門(mén)課程考試。由于選修內(nèi)容不同，考試門(mén)數(shù)也不一樣。表 1給出了每個(gè)研究生參加考試的課程（打 的）。規(guī)定考試在三天內(nèi)結(jié)束，每天上下午各排一門(mén)。研究生提出希望每人每天最多考一門(mén)，又課程 A必須在第一天上午考，課程 F安排在最后一門(mén)，課程 B只能安排在下午考。試列出一張滿足各方面要求的考試日程表。 課程 研究生 A B C D E F 1 2 3 4 5 6 7 8 9 10 例 2：某公司在六個(gè)城市 c1,… ,c6中有分公司，從 ci到 cj的直接航程票價(jià)記在下述矩陣中的（ i， j）位置上（ ∞ 表示無(wú)直接航路）。請(qǐng)幫助該公司設(shè)計(jì)一張任意兩城市間的票價(jià)最便宜的路線表。 ??????????????????????????055252510550102025251001020402022022252022050102540500最大流問(wèn)題 設(shè)一個(gè)賦權(quán)有向圖 D=（ V, E） ,在 V中指定一個(gè)發(fā)點(diǎn) vs和一個(gè)收點(diǎn) vt ,其它的點(diǎn)叫做中間點(diǎn) 。 對(duì)于 D中的每一個(gè)弧 （ vi , vj） ∈ E ,都有一個(gè)非負(fù)數(shù) cij,叫做弧的容量 。 我們把這樣的圖 D叫做一個(gè)容量網(wǎng)絡(luò) ， 簡(jiǎn)稱網(wǎng)絡(luò) ， 記做 D=（ V， E， C） 。 網(wǎng)絡(luò) D上的流，是指定義在弧集合 E上的一個(gè)函數(shù) 其中 f(vi ,vj) =fij 叫做弧 (vi， vj)上的流量。 ? ? }{),(jiji fvvff ??基本概念 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 稱滿足下列條件的流為 可行流： （ 1）容量條件：對(duì)于每一個(gè)?。?vi ,vj） ∈ E有 0 ? fij ? cij （ 2） 平衡條件： 對(duì)于發(fā)點(diǎn) vs， 有 對(duì)于收點(diǎn) vt ， 有 對(duì)于中間點(diǎn)，有 ? ?? ???Evv Evvsjjsjs sjfvff),( ),()(? ?? ????Evv Evvtjjtjt tjfvff),( ),()(? ?? ???Evv Evvijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做 飽和弧 ， fij＜ cij的弧叫做 非飽和弧 。 fij＞ 0 的弧為 非零流弧 ， fij＝ 0 的弧叫做 零流弧 。 可行流 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 圖中 為零流弧，其余為非飽和弧。 ) , ( 63 vv例 定理 可行流 f 是最大流的充分必要條件是不存在從 vs到 vt 的關(guān)于 f 的一條可增廣鏈。 容量網(wǎng)絡(luò) G ， 若 為網(wǎng)絡(luò)中從 vs到 vt的一條鏈，給 定向?yàn)閺?vs到 vt， 上的弧凡與方向相同的稱為前向弧，凡與 方向相反的稱為后向弧，其集合分別用 和 表示。f 是一個(gè)可行流，如果滿足：則稱 為從 vs到 vt的關(guān)于 f 的一條 增廣鏈增廣鏈 。?? ? ?????????????????????),(0),(0jijijijijijivvcfvvcf?即 中的每一條弧都是非飽和弧??即即 中的每一條弧都是非零流弧??增廣鏈 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) ? ?7766633232211 ),(,),(,),(,),(, vvvvvvvvvvvvv??? ?),(),(),( 766321 vvvvvv??? ? ?),( 23 vv????是一個(gè)增廣鏈 顯然圖中增廣鏈不止一條 例 容量網(wǎng)絡(luò) G = （ V ， E ， C ）， vs為始點(diǎn)， vt為終點(diǎn)。如果把 V 分成兩個(gè)非空集合使 ，則所有始點(diǎn)屬于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1