網路最最佳化問題是一類特殊的組合最最佳化問題。套用圖論理論,通過網路的拓撲結構及其性質,對網路進行研究,並且以計算機算法尋求網路中的最短路、最大流等。
基本介紹
- 中文名:網路最最佳化問題
- 外文名:Network optimization problem
- 拼音:Wǎng luò zuì yōu huà wèn tí
- 學科:數理科學
- 學科:運籌學
- 歸屬:網路規劃
基本內容
分類
- 最小費用流問題:模型在網路最最佳化中扮演著重要的角色,因為它的適用性很廣,並且求解方法容易。通常最小費用流問題用於最最佳化貨物從供應點到需求點的網路。目標是在通過網路配送貨物時,以最小的成本滿足需求,一種典型的套用就是使得配送網路的運營最優;
- 最大流問題:有供應點、需求點、轉運點、弧的容量限制,但沒有供應量和需求量的限制,目標是通過網路到目的地的總流量最大;
- 最短路問題:有供應點(供應量為1) 、需求點(需求量為1) 、轉運點、沒有弧的容量限制,目標是通過網路到目的地的總距離最短;
- 最小支撐樹問題:為了使得每兩個節點之間形成路,需要提供足夠的邊。目標就是以某種方法完成網路設計,使得邊的總成本最小。這種問題稱為最小支撐樹問題;
- 貨郎擔問題:一個推銷員從n個城市中的某個城市出發,到其他n-1個城市推銷貨物,每個城市都必須訪問並且只訪問一次,最後回到出發地,如何安排他的行走路線使總距離最短,這就是貨郎擔問題或旅行售貨員問題;
- 中國郵路問題:一個郵遞員從郵局出發,將郵件投遞到他管轄的所有街道,最後回到郵局,如何安排他的行駛路線,使總路長最短。這個問題由我國數學家管梅谷教授於1962年首先提出來的,因此稱為“中國郵路問題”。