網(wǎng)絡(luò)最優(yōu)化問題

7.1最小費(fèi)用流問題7.2案例研究：BMZ公司的最大流問題7.3最大流問題7.4最短路問題：里特城的消防隊(duì)問題7.4最短路問題：一般特征7.4最短路問題：最小化莎拉的總成本問題7.4最短路問題：最小化奎克公司總時(shí)間問題7.5最小支撐樹問題：摩登公司問題)主要內(nèi)容現(xiàn)在是1頁\一共有108頁\編輯于星期三無限配送公司的問題無限配送公司有兩個(gè)工廠生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運(yùn)到兩個(gè)倉庫里工廠1生產(chǎn)80個(gè)單位工廠2生產(chǎn)70個(gè)單位最小費(fèi)用流問題倉庫1需要60個(gè)單位倉庫2需要90個(gè)單位現(xiàn)在是2頁\一共有108頁\編輯于星期三無限配送公司的問題在工廠1和倉庫1之間以及工廠2和倉庫2之間各有一條鐵路運(yùn)輸軌道卡車司機(jī)至多可以從工廠運(yùn)輸50個(gè)單位到配送中心，然后可以從配送中心運(yùn)輸50個(gè)單位到倉庫現(xiàn)在是3頁\一共有108頁\編輯于星期三配送網(wǎng)絡(luò)現(xiàn)在是4頁\一共有108頁\編輯于星期三配送網(wǎng)絡(luò)的數(shù)據(jù)現(xiàn)在是5頁\一共有108頁\編輯于星期三最小費(fèi)用流問題的網(wǎng)絡(luò)模型現(xiàn)在是6頁\一共有108頁\編輯于星期三每條路線應(yīng)該運(yùn)送多少單位的產(chǎn)品？無限配送公司的問題現(xiàn)在是7頁\一共有108頁\編輯于星期三最優(yōu)解現(xiàn)在是8頁\一共有108頁\編輯于星期三最小費(fèi)用流問題的術(shù)語所有最小費(fèi)用流問題都是用帶有通過其中的流的網(wǎng)絡(luò)表示的網(wǎng)絡(luò)中的圓圈被稱為節(jié)點(diǎn)如果節(jié)點(diǎn)產(chǎn)生的凈流量[流出減去流入]是一個(gè)確定的正數(shù)的話，這個(gè)節(jié)點(diǎn)就是供應(yīng)點(diǎn)如果節(jié)點(diǎn)產(chǎn)生的凈流量是一個(gè)確定的負(fù)數(shù)的話，那么這個(gè)節(jié)點(diǎn)就稱為需求點(diǎn)現(xiàn)在是9頁\一共有108頁\編輯于星期三最小費(fèi)用流問題的術(shù)語如果節(jié)點(diǎn)產(chǎn)生的凈流量恒為零，那么這個(gè)節(jié)點(diǎn)就稱為轉(zhuǎn)運(yùn)點(diǎn)，我們把流出節(jié)點(diǎn)的量等于流入節(jié)點(diǎn)的量稱為流量守恒網(wǎng)絡(luò)中的箭頭稱為弧允許通過某一條弧的最大流量稱為該弧的容量現(xiàn)在是10頁\一共有108頁\編輯于星期三最小費(fèi)用流問題的假設(shè)至少有一個(gè)節(jié)點(diǎn)是供應(yīng)點(diǎn)至少有一個(gè)節(jié)點(diǎn)是需求點(diǎn)所有剩下的節(jié)點(diǎn)都是轉(zhuǎn)運(yùn)點(diǎn)通過弧的流只允許沿著箭頭的方向流動(dòng)，通過弧的最大流量取決于該弧的容量[如果流是雙向的話，則需要用一對(duì)箭頭指向相反的弧來表示]現(xiàn)在是11頁\一共有108頁\編輯于星期三最小費(fèi)用流問題的假設(shè)網(wǎng)絡(luò)中有足夠的弧提供足夠的容量，使得所有在供應(yīng)點(diǎn)中產(chǎn)生的流都能夠達(dá)到需求點(diǎn)在流的單位成本已知的前提下，通過每一條弧的流的成本和流量成正比最小費(fèi)用流問題的目標(biāo)是在滿足給定需求的條件下，使得通過網(wǎng)絡(luò)供應(yīng)的總成本最小[或通過這樣做使得總利潤最大化]現(xiàn)在是12頁\一共有108頁\編輯于星期三最小費(fèi)用流問題的特征具有可行解的特征：在以上假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點(diǎn)所提供的流量總和等于需求點(diǎn)所需要的流量總和時(shí)，最小費(fèi)用流問題有可行解具有整數(shù)解的特征：只要其所有的供應(yīng)、需求和弧的容量都是整數(shù)值，那么任何最小費(fèi)用流問題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解現(xiàn)在是13頁\一共有108頁\編輯于星期三電子表格描述現(xiàn)在是14頁\一共有108頁\編輯于星期三SUMIF函數(shù)SUMIF公式可以簡化節(jié)點(diǎn)流約束

SUMIF(RangeA,x,RangeB)區(qū)域A中的每一個(gè)量滿足條件x時(shí)，SUMIF函數(shù)就會(huì)計(jì)算區(qū)域B中相應(yīng)內(nèi)容之和節(jié)點(diǎn)x的凈流出[流出-流入]就等于SUMIF(“Fromlabels”,x,“Flow”)–SUMIF(“Tolabels”,x,“Flow”)現(xiàn)在是15頁\一共有108頁\編輯于星期三對(duì)每一個(gè)節(jié)點(diǎn)有一個(gè)約束，必須遵循“流量守恒規(guī)則”轉(zhuǎn)運(yùn)問題：凈流量=流出量-流入量最小成本網(wǎng)絡(luò)流中將流量守恒規(guī)則應(yīng)用于每個(gè)節(jié)點(diǎn)總供給>總需求流出量-流入量<=供給或需求總供給<總需求流出量-流入量>=供給或需求總供給=總需求流出量-流入量=供給或需求現(xiàn)在是16頁\一共有108頁\編輯于星期三對(duì)每一個(gè)節(jié)點(diǎn)有一個(gè)約束，必須遵循“流量守恒規(guī)則”凈流量=流入量-流出量最小成本網(wǎng)絡(luò)流中將流量守恒規(guī)則應(yīng)用于每個(gè)節(jié)點(diǎn)總供給>總需求流入量-流出量>=供給或需求總供給<總需求流入量-流出量<=供給或需求總供給=總需求流入量-流出量=供給或需求現(xiàn)在是17頁\一共有108頁\編輯于星期三轉(zhuǎn)運(yùn)問題Newark港和Jacksonville港接受到進(jìn)口到美國的汽車分別為200輛和300輛。B城，G城，Y城，R城和M城的經(jīng)銷商分別需要100輛，60輛，170輛、80輛和70輛汽車。根據(jù)各個(gè)城市間的運(yùn)輸費(fèi)用確定成本最小的運(yùn)送汽車的方式?，F(xiàn)在是18頁\一共有108頁\編輯于星期三凈流量=流出量-流入量現(xiàn)在是19頁\一共有108頁\編輯于星期三凈流量等于流入量-流出量現(xiàn)在是20頁\一共有108頁\編輯于星期三請(qǐng)?jiān)陔娮颖砀窭锓謩e按照供給為正和供給為負(fù)的情況，建立兩種情況下的模型，并求解比較現(xiàn)在是21頁\一共有108頁\編輯于星期三供給為正、需求為負(fù)時(shí)的電子表格模型現(xiàn)在是22頁\一共有108頁\編輯于星期三供給為負(fù)、需求為正的電子表格模型現(xiàn)在是23頁\一共有108頁\編輯于星期三分析最優(yōu)解現(xiàn)在是24頁\一共有108頁\編輯于星期三廣義網(wǎng)絡(luò)流問題目前所考慮的網(wǎng)絡(luò)流問題，從一條弧線出來的流量與進(jìn)入的流量一定是相等的。事實(shí)上是這種情況嗎？現(xiàn)在是25頁\一共有108頁\編輯于星期三CoalBankHollow再生公司該公司使用兩種不同的再生過程來將報(bào)紙、混合紙、白色辦公紙和紙板轉(zhuǎn)化為紙漿。從再生原料提出再生紙漿的數(shù)量和紙漿的提取成本由于使用不同的再生過程而不同。通過兩種不同的再生過程產(chǎn)生的紙漿通過其他處理轉(zhuǎn)化為新聞?dòng)眉?、包裝用紙或高質(zhì)量打印紙。兩種處理過程的具體數(shù)據(jù)如下現(xiàn)在是26頁\一共有108頁\編輯于星期三紙漿生產(chǎn)問題提取紙漿數(shù)據(jù)再生過程1再生過程2原料每噸成本產(chǎn)出結(jié)果每噸成本產(chǎn)出結(jié)果報(bào)紙1390%1285%混合紙1180%1385%白色辦公紙995%1090%紙板1375%1485%現(xiàn)在是27頁\一共有108頁\編輯于星期三最終紙漿產(chǎn)出結(jié)果新聞?dòng)眉埌b用紙打印紙紙漿來源每噸成本產(chǎn)出每噸成本產(chǎn)出每噸成本產(chǎn)出過程1595%690%890%過程2690%895%795%如果有70噸報(bào)紙，50噸混合紙，30噸白色辦公紙和40噸紙板。如何轉(zhuǎn)化成60噸新聞?dòng)眉埣垵{，40噸包裝用紙紙漿，50噸打印紙紙漿，成本最低。使用供給為負(fù)，需求為正的方法現(xiàn)在是28頁\一共有108頁\編輯于星期三轉(zhuǎn)化為最小費(fèi)用流問題的網(wǎng)絡(luò)圖現(xiàn)在是29頁\一共有108頁\編輯于星期三電子表格模型現(xiàn)在是30頁\一共有108頁\編輯于星期三最優(yōu)解分析現(xiàn)在是31頁\一共有108頁\編輯于星期三流量守恒規(guī)則的應(yīng)用當(dāng)不確定總供給和總需求的關(guān)系時(shí)，假設(shè)供給大于需求如果沒有可行解，再更改為需求大于供給現(xiàn)在是32頁\一共有108頁\編輯于星期三最小費(fèi)用流問題的應(yīng)用通過配送網(wǎng)絡(luò)的費(fèi)用最小現(xiàn)金流管理工廠協(xié)調(diào)產(chǎn)品組合現(xiàn)在是33頁\一共有108頁\編輯于星期三BMZ公司的最大流問題BMZ公司是歐洲一家生產(chǎn)豪華汽車的制造商，其產(chǎn)品出口到美國尤為重要BMZ公司的汽車尤其在加利福尼亞大受歡迎，因此保持洛杉磯中心零部件的充足供給，以便及時(shí)維修這些汽車就顯得特別重要了最大流問題現(xiàn)在是34頁\一共有108頁\編輯于星期三BMZ公司的最大流問題BMZ公司需要迅速執(zhí)行一項(xiàng)計(jì)劃，下個(gè)月要從位于斯圖加特和德國的主要工廠運(yùn)送盡可能多的配件到洛杉磯的配送中心配件運(yùn)送數(shù)量的限制因素就是公司配送網(wǎng)絡(luò)的容量現(xiàn)在是35頁\一共有108頁\編輯于星期三BMZ公司配送網(wǎng)絡(luò)現(xiàn)在是36頁\一共有108頁\編輯于星期三BMZ問題的網(wǎng)絡(luò)模型現(xiàn)在是37頁\一共有108頁\編輯于星期三通過每一條運(yùn)送路線應(yīng)該運(yùn)送多少配件，才能使從斯圖加特到洛杉磯的總流量最大？BMZ公司的最大流問題現(xiàn)在是38頁\一共有108頁\編輯于星期三BMZ公司的電子表格模型現(xiàn)在是39頁\一共有108頁\編輯于星期三最大流問題的假設(shè)網(wǎng)絡(luò)中所有流起源于一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)叫作源[起點(diǎn)]，所有的流終止于另一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)叫作收點(diǎn)[終點(diǎn)]。BMZ問題中的源和收點(diǎn)分別代表工廠和配送中心其余所有的節(jié)點(diǎn)叫作轉(zhuǎn)運(yùn)點(diǎn)通過每一個(gè)弧的流只允許沿著弧的箭頭所指方向流動(dòng)。由源發(fā)出的所有的弧背向源，而所有終結(jié)于收點(diǎn)的弧都指向收點(diǎn)現(xiàn)在是40頁\一共有108頁\編輯于星期三最大流問題的假設(shè)最大流問題的目標(biāo)是使得從源到收點(diǎn)的總流量最大。這個(gè)流量的大小可以用兩種等價(jià)的方法來衡量，分別叫作從源點(diǎn)出發(fā)的流量和進(jìn)入收點(diǎn)的流量現(xiàn)在是41頁\一共有108頁\編輯于星期三最大流問題和最小費(fèi)用流問題區(qū)別最小費(fèi)用流問題：供應(yīng)點(diǎn)、需求點(diǎn)最大流問題：源、收點(diǎn)最小費(fèi)用流問題的供應(yīng)量和需求量都是固定的，而最大流問題的源和收點(diǎn)卻不是最小費(fèi)用流問題的供應(yīng)點(diǎn)和需求點(diǎn)可能有多個(gè)，但最大流問題的源和收點(diǎn)只有一個(gè)現(xiàn)在是42頁\一共有108頁\編輯于星期三BMZ公司具有多個(gè)供應(yīng)點(diǎn)和需求點(diǎn)的案例BMZ公司在柏林還有一家更小的工廠一旦洛杉磯配送中心出現(xiàn)缺貨，位于西雅圖的配送中心就可以給有關(guān)的客戶供應(yīng)配件現(xiàn)在是43頁\一共有108頁\編輯于星期三擴(kuò)展的BMZ問題的網(wǎng)絡(luò)模型現(xiàn)在是44頁\一共有108頁\編輯于星期三擴(kuò)展的BMZ問題通過每一條運(yùn)送路線應(yīng)該運(yùn)送多少配件，才能使從斯圖加特和柏林到洛杉磯和西雅圖的總流量最大？現(xiàn)在是45頁\一共有108頁\編輯于星期三電子表格描述現(xiàn)在是46頁\一共有108頁\編輯于星期三最大流問題的應(yīng)用通過配送網(wǎng)絡(luò)的流量最大，如BMZ問題通過從供應(yīng)商到處理設(shè)施的公司供應(yīng)網(wǎng)絡(luò)的流量最大通過管道運(yùn)輸系統(tǒng)運(yùn)送的油量最大最大化通過輸水系統(tǒng)的水量通過交通網(wǎng)絡(luò)的車流量最大現(xiàn)在是47頁\一共有108頁\編輯于星期三網(wǎng)絡(luò)流與整數(shù)解使用單純形法求解具有約束的右側(cè)值是整數(shù)的任何最小成本的網(wǎng)絡(luò)流模型，最優(yōu)解自動(dòng)取整。但是如果加入了副約束，這樣不服從流量守恒規(guī)則，就不能保證問題的線性規(guī)劃模型的解是整數(shù)?，F(xiàn)在是48頁\一共有108頁\編輯于星期三特殊建模的考慮265431100100-7500-50如果要求進(jìn)入節(jié)點(diǎn)3的流量至少為50，進(jìn)入節(jié)點(diǎn)4的流量至少為60，如何建模？現(xiàn)在是49頁\一共有108頁\編輯于星期三特殊建模的考慮輔助約束-X13-X23<=-50-X14-X24<=-60必須加入虛節(jié)點(diǎn)或虛弧線現(xiàn)在是50頁\一共有108頁\編輯于星期三特殊建模的考慮26540301100100-7500-50如果要求進(jìn)入節(jié)點(diǎn)3的流量至少為50，進(jìn)入節(jié)點(diǎn)4的流量至少為60，如何建模？34$0L.B.=-50$0L.B.=-60現(xiàn)在是51頁\一共有108頁\編輯于星期三特殊建模的考慮12$8$6U.B.=35現(xiàn)在是52頁\一共有108頁\編輯于星期三特殊建模的考慮12$8$6U.B.=3510$0現(xiàn)在是53頁\一共有108頁\編輯于星期三特殊建模的考慮24$6$3U.B.=351$43U.B.=35U.B.=30$5,U.B.=40100100-80-75現(xiàn)在是54頁\一共有108頁\編輯于星期三特殊建模的考慮24$6$3U.B.=351$43U.B.=35U.B.=30$5,U.B.=40-100-100+80+750U.B.=100U.B.=100200$999$999現(xiàn)在是55頁\一共有108頁\編輯于星期三輔助約束與整數(shù)解加入輔助約束，則不會(huì)自己取整需要加入整數(shù)約束現(xiàn)在是56頁\一共有108頁\編輯于星期三里特城的消防隊(duì)問題里特城是一個(gè)農(nóng)村的小鎮(zhèn)它的消防隊(duì)要為包括許多農(nóng)場社區(qū)在內(nèi)的大片地區(qū)提供服務(wù)在這個(gè)地區(qū)有很多路，從消防站到任何一個(gè)社區(qū)都有很多條路線可供選擇最短路問題現(xiàn)在是57頁\一共有108頁\編輯于星期三里特城的道路系統(tǒng)現(xiàn)在是58頁\一共有108頁\編輯于星期三最短路問題的網(wǎng)絡(luò)規(guī)劃現(xiàn)在是59頁\一共有108頁\編輯于星期三從消防站到某個(gè)特定的農(nóng)場社區(qū)的最短路線是那條？里特城的消防隊(duì)問題現(xiàn)在是60頁\一共有108頁\編輯于星期三最短路問題的標(biāo)號(hào)法1959年，Dijkstra提出算法步驟：步驟1：起點(diǎn)是已標(biāo)號(hào)點(diǎn)，標(biāo)號(hào)為0步驟2：從所有已標(biāo)號(hào)點(diǎn)向未標(biāo)號(hào)點(diǎn)擴(kuò)散，得到未標(biāo)號(hào)點(diǎn)的臨時(shí)標(biāo)號(hào)現(xiàn)在是61頁\一共有108頁\編輯于星期三最短路問題的標(biāo)號(hào)法上述公式也用于更新臨時(shí)標(biāo)號(hào)點(diǎn)的臨時(shí)標(biāo)號(hào)現(xiàn)在是62頁\一共有108頁\編輯于星期三最短路問題的標(biāo)號(hào)法步驟3：某臨時(shí)標(biāo)號(hào)點(diǎn)的所有可能標(biāo)號(hào)的最小值即是其最終標(biāo)號(hào)，此時(shí)將該臨時(shí)標(biāo)號(hào)點(diǎn)標(biāo)記為已標(biāo)號(hào)點(diǎn)，并記錄其前一節(jié)點(diǎn)現(xiàn)在是63頁\一共有108頁\編輯于星期三最短路問題的標(biāo)號(hào)法步驟4：重復(fù)步驟2和3直至找到最短路線，此時(shí)得到的最終標(biāo)號(hào)即為其最短路線的長度現(xiàn)在是64頁\一共有108頁\編輯于星期三最短路問題的標(biāo)號(hào)法優(yōu)點(diǎn)：Dijkstra的標(biāo)號(hào)法是求解最短路問題的最優(yōu)化算法，也是目前最好的算法，而且可以求得起點(diǎn)到各點(diǎn)的最短路現(xiàn)在是65頁\一共有108頁\編輯于星期三最短路問題的網(wǎng)絡(luò)規(guī)劃現(xiàn)在是66頁\一共有108頁\編輯于星期三電子表格描述現(xiàn)在是67頁\一共有108頁\編輯于星期三最短路問題的假設(shè)在網(wǎng)絡(luò)中選擇一條路，這條路始于某一節(jié)點(diǎn)，這節(jié)點(diǎn)叫作源，終于另一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)叫作目標(biāo)地連接兩個(gè)節(jié)點(diǎn)的連線通常叫作邊[允許任一個(gè)方向的行進(jìn)]，雖然也允許存在弧[只允許沿著一個(gè)方向行進(jìn)]現(xiàn)在是68頁\一共有108頁\編輯于星期三最短路問題的假設(shè)和每條邊相關(guān)的一個(gè)非負(fù)數(shù)，叫作該邊的長度[注意：在網(wǎng)絡(luò)中，除了在邊的旁邊表明了其長度的準(zhǔn)確數(shù)字以外，所畫的每一條邊的長度并不表明其真實(shí)的長度]目標(biāo)是尋找從源點(diǎn)到目標(biāo)地的最短路線[總長度最小的路]現(xiàn)在是69頁\一共有108頁\編輯于星期三最短路問題的應(yīng)用行進(jìn)的總距離最小一系列活動(dòng)的總成本最小一系列活動(dòng)的總時(shí)間最小現(xiàn)在是70頁\一共有108頁\編輯于星期三總成本最小的例子:莎拉的汽車基金莎拉剛剛高中畢業(yè)在畢業(yè)典禮上，她的父母給了她21000美元的汽車基金幫助她購買并保養(yǎng)一輛使用了三年的二手車，以供她上大學(xué)使用現(xiàn)在是71頁\一共有108頁\編輯于星期三總成本最小的例子:莎拉的汽車基金由于開車費(fèi)用和維修費(fèi)用隨著汽車的老化而飛速上漲，所以，如果能夠最小化總的凈成本，莎拉可能在接下來的三個(gè)夏天里，一次或多次折價(jià)將她的汽車置換為其他使用了三年的二手車。四年后，莎拉的父母會(huì)把她的舊車置換成一輛新車，作為莎拉的畢業(yè)禮物?，F(xiàn)在是72頁\一共有108頁\編輯于星期三莎拉的成本數(shù)據(jù)現(xiàn)在是73頁\一共有108頁\編輯于星期三總成本最小的例子:莎拉的汽車基金在接下來的三個(gè)夏天里，莎拉應(yīng)該何時(shí)折價(jià)賣掉她的汽車？如何考慮？如何轉(zhuǎn)換成最短路問題？現(xiàn)在是74頁\一共有108頁\編輯于星期三最短路的描述權(quán)=購買成本+總使用和維護(hù)成本-銷售收入現(xiàn)在是75頁\一共有108頁\編輯于星期三電子表格描述現(xiàn)在是76頁\一共有108頁\編輯于星期三總時(shí)間最小化的例子:

奎克公司奎克公司獲悉它的一個(gè)競爭對(duì)手計(jì)劃將把一種很有銷售潛力的新產(chǎn)品投放市場奎克公司也一直在研制一種類似的產(chǎn)品，并計(jì)劃在20個(gè)月后投放市場現(xiàn)在是77頁\一共有108頁\編輯于星期三總時(shí)間最小化的例子:

奎克公司奎克公司的管理者希望迅速推出產(chǎn)品去參與競爭現(xiàn)在還有四個(gè)階段沒有完成，每個(gè)階段都可以正常水平、優(yōu)先水平和應(yīng)急水平加速完成。正常水平由于后三個(gè)階段的實(shí)施速度太慢而被排除了有3000萬美元用于這四個(gè)階段的實(shí)施過程現(xiàn)在是78頁\一共有108頁\編輯于星期三各階段所需的時(shí)間和成本現(xiàn)在是79頁\一共有108頁\編輯于星期三總時(shí)間最小化的例子:

奎克公司每個(gè)階段應(yīng)該以什么樣的速度進(jìn)行？如何考慮？如何轉(zhuǎn)換成最短路問題？現(xiàn)在是80頁\一共有108頁\編輯于星期三最短路問題的描述虛擬節(jié)點(diǎn)節(jié)點(diǎn):(階段,剩余資金)；弧:活動(dòng)；權(quán):時(shí)間現(xiàn)在是81頁\一共有108頁\編輯于星期三電子表格描述現(xiàn)在是82頁\一共有108頁\編輯于星期三最優(yōu)解現(xiàn)在是83頁\一共有108頁\編輯于星期三最小支撐樹:摩登公司的問題摩登公司決定鋪設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)系統(tǒng)以便在其主要中心之間提供高速通信，包括數(shù)據(jù)、聲音和視頻等為了充分利用光纖技術(shù)在中心之間高速通信的優(yōu)勢(shì)，不需要在每兩個(gè)中心之間都用一條光纜把它們直接連接起來，那些需要光纜直接連接的中心有一系列的光纜連接它們最小支撐樹問題現(xiàn)在是84頁\一共有108頁\編輯于星期三摩登公司主要中心、纖維光纜的可能布局及成本現(xiàn)在是85頁\一共有108頁\編輯于星期三應(yīng)該鋪設(shè)哪些光纖以便在每兩個(gè)中心之間提供高速通信？最小支撐樹:摩登公司的問題現(xiàn)在是86頁\一共有108頁\編輯于星期三最小支撐樹的假設(shè)給你網(wǎng)絡(luò)中的節(jié)點(diǎn)，但沒有給你邊?；蛘?，給你可供選擇的邊和如果把它插入到網(wǎng)絡(luò)中后的每條邊的正的成本[或者相似的度量]在設(shè)計(jì)網(wǎng)絡(luò)時(shí)你希望通過插入足夠的邊，以滿足每兩個(gè)節(jié)點(diǎn)之間都存在一條路的需要目標(biāo)是尋找一種方法，使得在滿足要求的同時(shí)總成本最小現(xiàn)在是87頁\一共有108頁\編輯于星期三最小支撐樹的算法選擇第一條邊：選擇成本最低的備選邊選擇下一條邊：在一個(gè)已經(jīng)有一條邊連接的節(jié)點(diǎn)和另一個(gè)還沒有邊連接的節(jié)點(diǎn)之間選擇成本最低的備選邊重復(fù)第二個(gè)步驟，直到所有的節(jié)點(diǎn)都有一條邊[可能會(huì)有多于一條邊]與其相連。此時(shí)就得到了最優(yōu)解[最小支撐樹])當(dāng)有幾條邊同時(shí)是成本最低的邊時(shí)，任意選擇一條邊不會(huì)影響最后的最優(yōu)值現(xiàn)在是88頁\一共有108頁\編輯于星期三摩登公司的算法應(yīng)用:第一步現(xiàn)在是89頁\一共有108頁\編輯于星期三摩登公司的算法應(yīng)用:第二步現(xiàn)在是90頁\一共有108頁\編輯于星期三摩登公司的算法應(yīng)用:第三步現(xiàn)在是91頁\一共有108頁\編輯于星期三摩登公司的算法應(yīng)用:第四步現(xiàn)在是92頁\一共有108頁\編輯于星期三摩登公司的算法應(yīng)用:第五步現(xiàn)在是93頁\一共有108頁\編輯于星期三摩登公司的算法應(yīng)用:最后一步現(xiàn)在是94頁\一共有108頁\編輯于星期三最優(yōu)解現(xiàn)在是95頁\一共有108頁\編輯于星期三最小支撐樹問題避圈法：開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已被選取的邊不構(gòu)成圈(如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條)現(xiàn)在是96頁\一共有108頁\編輯于星期三最小支撐樹問題算例現(xiàn)在是97頁\一共有108頁\編輯于星期三最小支撐樹問題破圈法：任取一個(gè)圈，從圈中去掉權(quán)最大的邊(如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條)。在余下的圖中，重復(fù)這個(gè)步驟，一直到圖中不含圈為止。去邊的同時(shí)必須保證圖的連通性現(xiàn)在是98頁\一共有108頁\編輯于星期三最小支撐樹問題算例現(xiàn)在是99頁\一共有108頁\編輯于星期三最小支撐樹的應(yīng)用電信網(wǎng)絡(luò)[計(jì)算機(jī)網(wǎng)絡(luò)、電話專用線網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)等等]的設(shè)計(jì)低負(fù)荷運(yùn)輸網(wǎng)絡(luò)的設(shè)計(jì)，使