多商品流網絡問題文獻翻譯(word文檔良心出品)

1、多商品流問題（MCF）關鍵詞和關鍵短語：多目標優(yōu)化，多準則決策，有效解，帕累托最優(yōu) 解，非劣解，非解方案，弱效解，弱帕累托最優(yōu)解，弱非劣解，弱非解，弱效解。線性多商品流問題是一種以一系列商品和潛在網絡為特征的線性規(guī)劃問題。這兒指的商品是必須從一個或多個原始節(jié)點上，傳輸到網絡中的 另一個或多個目的節(jié)點上的商品。實際上，這些商品可能是 電信網絡中 撥出的電話，分銷網絡中的包裹，或航空公司飛行網絡中的飛機。每種商品都有獨特的特征，并且商品是不可互換的。也就是 說，你不能同時滿足兩種商品的需求。MCF問題的目標是通過網絡以最低的成本流通商品，且要不超過每條弧的容量。提出了做線性多商品流模型和其解決方案

2、的綜 合性研究調查。整數多商品流問題（IMCF）是線性多商品流問題中有約束條件的一個多商品流問題，約束條件是從原點到目的的路徑只有一條。MCF和IMCF問題在許多情況下都普遍存在，例如在運輸 通信 和生產中。多商品流問題應用實例交通網絡中車輛的路徑（動態(tài)交通分配）這涉及通過流量網絡確定車輛從起點到其各自目的地的最小延 遲路線?；蛘撸瑳]有具體的容量，但 弧上的容量是一個關于流量的函數。在前一種情況下，目標函數是線性 的，而后者則是非線性的。分配系統(tǒng)規(guī)劃 在這個問題上，在具有已知生產能力的幾家工廠生產不同的產品（或 商品）。每個商品在每個客戶區(qū)都有一定的需求。通過具有有限存儲容量 的區(qū)域配送中心的

3、運輸來滿足需求。某某【28模擬了通過 配送中心將商 品從制造工廠送到到客戶區(qū)域的路徑問題，即為MCF問題。進出口模型可能影響出口的因素之一是港口處理能力。某某【8利用MCF模型 來分析美國港口能力對小麥，玉米和大豆出口的影響。貨運業(yè)務的優(yōu)化某某【20開發(fā)基于MCF的路徑和調度優(yōu)化模型，用來解決鐵路 行業(yè)的規(guī)劃問題。某某【48】使用多商品流問題中的公式來研究鐵路的擁 塞問題。零擔貨運中的貨物運輸問題零擔貨運的運營商必須整合許多貨物，以 便更經濟地使用車輛。這就要求建立大量碼頭來進行分貨。貨運公司通過 對需求的預測來規(guī)劃每輛車輛往返碼頭的運輸路線。一旦路線固定，問 題是以最少的總時間或成本交付所有

4、的貨物。這個問題在【17】和24中被定義為MCF問題?？爝f發(fā)貨問題 某某【40】模擬聯(lián)邦快遞，美國郵政，聯(lián)合包裹服務等快遞公司所面臨的貨運交付問題，作為空間和時間網絡上的MCF問題。電信或計算機網絡中的信息傳輸問題網絡由傳輸線路組成。每個消息發(fā)出的請求就相當于商品。問題是 以最低的成本將信息從起始點傳到各個目的地。某某【42】為該問題提供 多商品流問題中的公式。長期水力發(fā)電的優(yōu)化在這種情況下，任務是在一段時間內確定一個水庫的水力發(fā)電量，將 一段時間分為若干間隔使得發(fā)電的預期成本減至最小。某某【47】認為這個問題可以建模為一個給定的流入概率密度函數的 MCF問題。森林管理 對于每一個規(guī)劃期，森林

5、管理人員必須就收割的土地面積，和從這些地區(qū)收獲的木材數量，以及要開發(fā)的娛樂用地面積和建造與維護 的道路網進行決策，以便木材的運輸和娛樂活動。這個問題已經在【33】中定義為一個MCF問題。街道規(guī)劃某某在【26介紹了這個問題，并將其作為一個MCF問題。目的是確定一套雙向街道，使這些網絡中的街道單向的總擁塞損失最小化?？臻g價格平衡（SPE問題這個問題需要消費者在一般網絡內的流動模型。SPE問題決定了每個市場的最佳生產量和消費水平，最優(yōu)流量滿足均衡性。某某在【59】 將SPE問題視為MCF問題并將其解決。為了更全面了解MCF的應用，請看到【57】、【2】、【37】。整數多商品流問題應用實例航空機隊指派

6、 給定航班的到達和起飛時間表，對航班和一組飛機有預期需求，目標是以最低的成本給航班分配飛機。這個問題已經在【31進行了廣泛的研 究。機組排班這個問題是將調度人員的成本降至最低。在解決問題時，必須考慮工時限制和聯(lián)邦航空管理條例等因素。深入的研究見【5】、14 o航線維護路徑問題 要求單個飛機飛單個路徑以滿足維修要求，每一個航班都被分配到一架飛機上。這個問題已經在【19】、【10】、25中進行了研究。帶寬分配問題 要求在電信網絡中最好的分配帶寬，從而最大限度地提高總收入。網絡上的需求或呼叫就是商品，目標是將呼叫從其來源地傳到目的地。在視 頻電話會議的情況下，由于不允許呼叫分配，每個呼叫必須在一個網

7、絡 路徑上進行。這個IMCF問題在【49】中有描述。快遞包裹流量問題例如快遞包裹交付業(yè)務中的貨物，要求每一個具有特定來源和目的地的貨物通過運輸網絡進行運輸。具有共同來源的每組包裹可以被 認為是一種商品，并且通常為了方便操作并確?？蛻魸M意，必須分配到單個網絡路徑上。這個問題在【12】中被作為IMCF問題。數學模型多商品流問題可以通過多種方式進行建模，這取決于如何定義商品。主要有三種情況：第一種是商品可能是從網絡節(jié)點子集中的一個 節(jié)點，指向另一個子節(jié)點第二種是它可能從某單一節(jié)點,指向網絡節(jié)點子集中的一個節(jié)點；最后一種是它可能從一個單一節(jié)點，指向另一個單一節(jié) 點。某某【34】為每種不同情況提供了不同

8、的模型。為了利益空間最大 化，我們只會考慮最后一種情況的模型。其他情況也可以參考這里提出的 模型來進行建模。我們就MCF問題提供兩種不同的公式：一種是節(jié)點弧和傳統(tǒng)公 式，一種是路徑或列生成公式。MCF的定義是由節(jié)點集N和弧組A行成的網 絡G。MCF問題中包含決策變量x,其中Xk是商品總量k中分配給弧ij的 商品量（表示為q9。在IMCF問題中，這些變量被限制 在二進制下。商品k全部分配給弧ij的費用等于弧ij的單位流量費用的qk倍，表示為 Cko對于所有的ij屬于集合A時，弧ij的容量為djjo節(jié)點i提供的商品k,表 示為b*如果i是k的起始節(jié)點，則等于1;如果i是k的目標節(jié)點，則等于1,否則

9、等于0。節(jié)點弧MCF公式為：(1)V V L L minimize ) cAq ijeA由此二爲ViG NKKi(3)注意，在沒有限制條件的一般性情況下，我們對弧流量變量x進行了建模，其值在0到1之間。為此，我們將每種商品的需求量化為1,并 相應的調整目標函數(1)和約束(3)中的系數。還要注意 這個模型的矩 形結構。流量約束條件(2)形成了不重疊的區(qū)域，每 個商品對應一個。只 有弧的容量約束條件(3)將不同商品的流量變 量的值聯(lián)系了起來。相比之下，基于路徑或列生成的MCF公式具有較少的約束條件和更多的變量。再次，潛在的網絡G由節(jié)點集N和弧集A組成，其中qk表示 商品k的數量。P (k)表示在

10、網絡G中，k屬于K的中所有起 始點到目的 點的路徑集合。在列生成模型中，二進制決策變量表示為？霧，？ ？?是商品k分配到路徑p屬于P (k)的一部分。將商品k全部分配 給路徑p的費用 等于路徑P的單位流量費用乘以qk,表示為？舁?表 示在路徑p中，所有 的弧ij上的？?費用總和。如前所述，對于所有屬 于A的弧ij都有容量？?？ 最后，如果弧ij是屬于路徑p屬于P (k)中的且對于所有k都屬于K, 則？?等于1；否則等于0。然后，路徑或列生成IMCF公式如下:E 展5卩(可工 52 q 秋硝 s dij, Vij 6 A.kEKpeP(k)(8)J/J 0, PpEPg Vt e K.線性規(guī)劃化

11、問題解決方案【37】提供了可用的多商品網絡流解決方案的全面研究資料。【2】和【38】也提供了這種方法的相關資料。價格指導分配方法，是基于MCF模型路徑上的方法。為了限制 在尋 找最優(yōu)解時考慮的變量的數目，使用了列生成的方法。價格指導 分配和 列生成方法的更多內容在【22】、【41】、【61】、【18、【45】 中給出。資源指導分配方法是試圖通過分配商品，通過弧的容量來解決MCF問題，并解決每個商品的最小成本問題。在【52】、【61】、27、【41】、【37】、【30】、【39】、【35】、【60中可找到關于該方法的附加 說明。價格和資源指導分配方法的優(yōu)劣比較可以在【3】中找到。某某【4】報告說

12、，專門的分配代碼的完成預期可以比一般的線性編程包 快三 到十倍。此外，某某【7報告說，資源指導分配算法能夠在小問題上快 速收斂，但是對于大的MCF問題，價格指導分配方法要優(yōu)于其他方法。某某【56在有束約束的拉格朗日松弛法中使用次梯度方法，提出 了一種能最低成本解決多目標流問題的高級基礎方法。劃分方法通過對當前主要部分進行劃分,以便利用底層網絡結構來形成解決這類問題的單純形方法。已經在【51】,【53】,【54】,【55】,32,【43】，【36】，【24等中提供了基礎 劃分方法的研究資料。某某【53】提出了解決角度問題的劃分方法。某某【32提出了一種廣 義上的上邊界算法，用于解決多商品網絡流問

13、題, 其中用到了關于MCF問題的特殊結構。他們的原始劃分程序，是由某某【21開發(fā)的一 個專業(yè)化的廣義上邊界程序，該程序在每一次迭代的基礎上一個飽和弧 只包含有一行逆矩陣。類似地，某某【44】提出了一種通用的網絡規(guī)劃 問題的廣義上邊界算法。所有這些過程都利用了區(qū)塊對角化問題的結 構，并在降維數為m的基礎上執(zhí)行了單純形法的所有步驟，其中m表示 集合A的大小。內點算法和并行計算技術也被應用于MCF問題。內點算法為MCF 問題的多項式時間算法。最優(yōu)的時間約束條件是某某【62提出的。某 某【58】提供了一種用大規(guī)模并行計算技術來解決多商品流問題的內點算 法?！?7】和【9】中分別提供了原始和雙上升式程序

14、，都是解決MCF 問題的新啟發(fā)式程序。某某【29使用障礙懲罰法找到多商品問題的近 似最優(yōu)解，而某某【62】則描述了一種算法，解決多商品流問題幾乎是 可行的。如今，價格指導分配法或列生成法，如【2】，11 ,23,【34中提出的方法是解決大型線性MCF問題時最廣泛使用的方法。 列生成的一般思想是，在沒有明確包含約束矩陣（稱為主問題）中所有列 （即變量）的情況下，可以得到線性規(guī)劃問題的最優(yōu)解。事實上，只有所 有列中的小部分將處于最佳解決方案上，所有其他（非基本）列都可以忽 略。在最小化問題中，這意味著所有降低成本的列都可以忽略。那么多 商品流問題的列生成方法就是：0） RMP建立。在受限制的主問題

15、中包含一個列的子集，稱為限制主問題即RMP;1）RMP解決方案。解決RMP線性規(guī)劃問題；2）定價問題解決方案。使用解決RMP獲得的雙重變量來解決定價問 題。定價問題可以識別一個或多個負成本的列（即價格降低的歹U）,或者確定不存在這樣的列。3）最優(yōu)性測試。如果一個或多個列定價，請將這些列（其中的一個子集）添加到RMP中并返回到步驟1）否則停止，主問題 解 決。對于步驟1）中的任何RMP,令-?表示與約束（6）相關聯(lián)的非負雙 重變量，？ ？?表示與約束（7）相關的無限制雙重變量。由于？?可以表示 為爲?？ ？ ? ?商品k的p列的降低成本？ ?,是：訝二1知+切）曙-六（9）對于步驟1）中生成的每

16、個RMP解決方案，可以有效地解決步 驟2）中的定價問題。對于每個ij屬于A情況下，可以通過解決在商品k屬于K時的網絡中弧成本等于？?的最短路徑的問題，來確定每列的定價。令？ ？表示商品k的最終最短路徑？ ?o那么，如果所有的k屬于K時:主要問題解決了。否則，MP沒有解決，那對于每個k屬于K：詩才 O,路徑？ ?（被添加到步驟3中的限制主要問題中。整數規(guī)劃化問題解決方案有能力解決大型多商品流問題，就有方法解決大型整數多商品流問 題。解決大型整數多商品流問題的成功方法是使用基于路徑或列生成的方 法。列生成的線性規(guī)劃問題可以使用熟知的分支和價格的方法求解，詳見【15】、641、23 o分支和價格，是

17、一個廣義化的分支和線性規(guī) 劃松弛的約束，允許列生成應用于每個節(jié)點的分支定界樹。當沒有列價格 進入基礎矩陣并且線性規(guī)劃問題解決方案不能滿足完整性條件時，分支就 產生了。將標準分支定界程序應用到已有的約束主問題中并不能保證最優(yōu)解（或可行解）。在分支修改限制住問題之后，可能存在一種情況，即為主 問題提供了有利價格的列，但在限制主問題中卻沒有。因此，為了找到最 優(yōu)解，我們必須保證在分支后解決定價問題的能力。在【63】中演示 了，航空公司機組排班應用程序解決初始線性規(guī)劃問題后，生成列的重要性。雖然他們無法找到可行的整數規(guī)劃問題解決方案，僅使 用列生成法解決初始線性規(guī)劃松弛問題，但他們能夠使用分支和價格方

18、 法找到質量解決方案用于機組的調度。每當線性規(guī)劃問題的節(jié)點綁定超 過預設的整數規(guī)劃問題目標值時，附加列。執(zhí)行具有分支和約束的列生成法的難點是常規(guī)的整數規(guī)劃問題在變量 上的分支可能無效，因為固定變量可以破壞定價問題的結構。對于多 商品流問題的應用，是需要一個分支規(guī)則的，用來確保包含分支決策的線性規(guī)劃的定價問題可以用最短路徑法有效的解決。舉例說 明一下，考慮到基于變量二分法有分支，其中一個分支將商品K指派給 路徑P，即？?=7,另一個分支不允許商品K使用路徑p,即？ =0。第一個 分支很容易執(zhí)行，因為一旦k分配給路徑p,就不需要生成額 外的路徑。 但是，如果將定價問題作為最短路徑問題解決，則無法執(zhí)

19、 行后一個分支。不 能保證最短路徑問題的解不是路徑p。事實上，k的最短路徑很可能是路徑P。因此，要執(zhí)行分支決策，必須使用下一個最 短路徑過程來實現定價問題的解決方案。一般來說，對于涉及一組分支 決策的子問題，必須使用第k個最短路徑過程來實現定價問題的解決方 案。開發(fā)分支和價格程序的關鍵是確定一個分支規(guī)則，消除當前的分數 解,而不會影響定價問題的易處理性。一般來說，某某等人【23認為,這可以通過將分支規(guī)則基于原始公式中的變量，而不是列生成公式 中的變量來實現。這意味著分支規(guī)則應該基于問題的節(jié)點弧公式中的弧 流變量X。某某【15】為許多不同主問題結構研發(fā)分支規(guī)則。他們還調查 在文獻中出現廣泛應用的專業(yè)算法。某某【49】提出了帶寬包裝問題的分支和價格算法。其目的是以最 大限度地提高收益的發(fā)送一套商品。他們使用基于路徑的公式。他們的 分支方案選擇一個分數路徑，并創(chuàng)建一個等于路徑長度（以其包含的弧的數量為單位）的新的子問題。在