Chapter07-網絡最優(yōu)化問題

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

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

奎克公司奎克公司得悉它的一個競爭對手方案將把一種很有銷售潛力的新產品投放市場奎克公司也一直在研制一種類似的產品，并方案在20個月后投放市場總時間最小化的例子:

奎克公司奎克公司的管理者希望迅速推出產品去參與競爭現在還有四個階段沒有完成，每個階段都可以正常水平、優(yōu)先水平和應急水平加速完成。正常水平由于后三個階段的實施速度太慢而被排除了有3000萬美元用于這四個階段的實施過程各階段所需的時間和本錢總時間最小化的例子:

奎克公司每個階段應該以什么樣的速度進行？如何考慮？如何轉換成最短路問題？最短路問題的描述虛擬節(jié)點節(jié)點:(階段,剩余資金)；弧:活動；權:時間電子表格描述最優(yōu)解最小支撐樹:摩登公司的問題摩登公司決定鋪設最先進的光纖網絡系統(tǒng)以便在其主要中心之間提供高速通信，包括數據、聲音和視頻等為了充分利用光纖技術在中心之間高速通信的優(yōu)勢，不需要在每兩個中心之間都用一條光纜把它們直接連接起來，那些需要光纜直接連接的中心有一系列的光纜連接它們最小支撐樹問題摩登公司主要中心、纖維光纜的可能布局及本錢應該鋪設哪些光纖以便在每兩個中心之間提供高速通信？最小支撐樹:摩登公司的問題最小支撐樹的假設給你網絡中的節(jié)點，但沒有給你邊?；蛘撸o你可供選擇的邊和如果把它插入到網絡中后的每條邊的正的本錢[或者相似的度量]在設計網絡時你希望通過插入足夠的邊，以滿足每兩個節(jié)點之間都存在一條路的需要目標是尋找一種方法，使得在滿足要求的同時總本錢最小最小支撐樹的算法選擇第一條邊：選擇本錢最低的備選邊選擇下一條邊：在一個已經有一條邊連接的節(jié)點和另一個還沒有邊連接的節(jié)點之間選擇本錢最低的備選邊重復第二個步驟，直到所有的節(jié)點都有一條邊[可能會有多于一條邊]與其相連。此時就得到了最優(yōu)解[最小支撐樹])當有幾條邊同時是本錢最低的邊時，任意選擇一條邊不會影響最后的最優(yōu)值摩登公司的算法應用:第一步摩登公司的算法應用:第二步摩登公司的算法應用:第三步摩登公司的算法應用:第四步摩登公司的算法應用:第五步摩登公司的算法應用:最后一步最優(yōu)解最小支撐樹問題避圈法：開始選一條最小權的邊，以后每一步中，總從未被選取的邊中選一條權最小的邊，并使之與已被選取的邊不構成圈(如果有兩條或兩條以上的邊都是權最小的邊，那么從中任選一條)最小支撐樹問題算例最小支撐樹問題破圈法：任取一個圈，從圈中去掉權最大的邊(如果有兩條或兩條以上的邊都是權最大的邊，那么任意去掉其中一條)。在余下的圖中，重復這個步驟，一直到圖中不含圈為止。去邊的同時必須保證圖的連通性最小支撐樹問題算例最小支撐樹的應用電信網絡[計算機網絡、專用線網絡、有線電視網絡等等]的設計低負荷運輸網絡的設計，使得網絡中提供鏈接的局部[如鐵路、公路等]的總本錢最小最小支撐樹的應用高壓輸電線路網絡的設計連接多個場所的管道網絡設計電器設備線路網絡[如數字計算機系統(tǒng)]的設計，使得線路總長度最短規(guī)劃問題總結線性規(guī)劃資源分配問題本錢收益平衡問題網絡配送問題：運輸問題，指派問題，最小費用流問題，最大流問題，最短路問題混合問題最小支撐樹問題規(guī)劃問題總