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

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

奎克公司奎克公司獲悉它的一個競爭對手計劃將把一種很有銷售潛力的新產(chǎn)品投放市場奎克公司也一直在研制一種類似的產(chǎn)品，并計劃在20個月后投放市場第七十八頁，共一百零九頁，2022年，8月28日總時間最小化的例子:

奎克公司奎克公司的管理者希望迅速推出產(chǎn)品去參與競爭現(xiàn)在還有四個階段沒有完成，每個階段都可以正常水平、優(yōu)先水平和應(yīng)急水平加速完成。正常水平由于后三個階段的實施速度太慢而被排除了有3000萬美元用于這四個階段的實施過程第七十九頁，共一百零九頁，2022年，8月28日各階段所需的時間和成本第八十頁，共一百零九頁，2022年，8月28日總時間最小化的例子:

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