網路最最佳化問題

網路最最佳化問題是一類特殊的組合最最佳化問題。套用圖論理論，通過網路的拓撲結構及其性質，對網路進行研究，並且以計算機算法尋求網路中的最短路、最大流等。

基本介紹

• 中文名：網路最最佳化問題
• 外文名：Network optimization problem
• 拼音：Wǎng luò zuì yōu huà wèn tí
• 學科：數理科學
• 歸屬：網路規劃

基本內容

網路在各種實際背景問題中以各種各樣的形式存在。交通、電子和通訊網路遍及我們日常生活的各個方面，網路規劃也廣泛用於解決不同領域中的各種問題，如生產、分配、項目計畫、廠址選擇、資源管理和財務策劃等等。網路規劃為描述系統各組成部分之間的關係提供了非常有效的直觀和概念上的幫助，廣泛套用於科學、社會和經濟活動的各個領域中。

分類

網路最最佳化問題類型主要包括： 最小費用流問題、最大流問題、最短路問題、最小支撐樹問題、貨郎擔問題和中國郵路問題等。

1. 最小費用流問題：模型在網路最最佳化中扮演著重要的角色，因為它的適用性很廣，並且求解方法容易。通常最小費用流問題用於最最佳化貨物從供應點到需求點的網路。目標是在通過網路配送貨物時，以最小的成本滿足需求，一種典型的套用就是使得配送網路的運營最優；
2. 最大流問題：有供應點、需求點、轉運點、弧的容量限制，但沒有供應量和需求量的限制，目標是通過網路到目的地的總流量最大；
3. 最短路問題：有供應點(供應量為1) 、需求點(需求量為1) 、轉運點、沒有弧的容量限制，目標是通過網路到目的地的總距離最短；
4. 最小支撐樹問題：為了使得每兩個節點之間形成路，需要提供足夠的邊。目標就是以某種方法完成網路設計，使得邊的總成本最小。這種問題稱為最小支撐樹問題；
5. 貨郎擔問題：一個推銷員從n個城市中的某個城市出發，到其他n－1個城市推銷貨物，每個城市都必須訪問並且只訪問一次，最後回到出發地，如何安排他的行走路線使總距離最短，這就是貨郎擔問題或旅行售貨員問題；
6. 中國郵路問題：一個郵遞員從郵局出發，將郵件投遞到他管轄的所有街道，最後回到郵局，如何安排他的行駛路線，使總路長最短。這個問題由我國數學家管梅谷教授於1962年首先提出來的，因此稱為“中國郵路問題”。

套用

網路規劃可以用於解決最佳化物流配置問題。首先將實際問題按照網路最最佳化問題的一般假設和原理建立數學模型，用電腦程式進行求解。然後測試模型，在必要時進行修正，並套用模型分析問題、提出建議、進行輔助管理決策。物流系統是由物流各要素所組成的，要素之間存在有機聯繫的總體。這個總體十分複雜，其內部存在著相互作用和相互依賴的各個組成部分。這個總體的特定功能，是使物流活動最佳化及合理化。網路分析是運籌學中的一個重要分支，是藉助於圖的知識來研究管理、組織與計畫中的最佳化問題的另一種方法。

比如在研究工程問題中，如何找出在現有資源的情況下，使工程所用時間最短或費用最小的方案。又如在企業管理中，如何制定管理計畫或設備購置計畫使得收益最大或費用最小等。在研究物流配置的問題中也可以利用網路的方法來對物流網路進行最佳化達到合理配置的目的。線性規劃的一類重要套用是網路最最佳化問題。網路最最佳化問題有許多類，主要有最短路問題、最大流問題、最小費用流問題。