丹齊格一沃爾夫分解算法(Dantzig-Wolfedecomposition algorithm)是求解可分解的大規模線性規劃問題的算法。對於可分解的線性規劃問題(稱為母規劃)，可以分解成幾個規模較小的子規劃。分解算法的過程是從母規劃的一個基可行解開始，作對應的乘數，並將母規劃分解成幾個子規劃。
基本介紹
- 中文名：丹齊格一沃爾夫分解算法
- 外文名：Dantzig-Wolfedecomposition algorithm
- 領域：數學
- 作用：求解可分解的大規模線性規劃問題
- 提出：福特和富爾克森
- 完善：丹齊格和沃爾夫
概念,線性規劃,套用——大系統問題,丹齊格,
概念
丹齊格一沃爾夫分解算法(Dantzig-Wolfedecomposition algorithm)是求解可分解的大規模線性規劃問題的算法。對於可分解的線性規劃問題(稱為母規劃)，可以分解成幾個規模較小的子規劃。分解算法的過程是從母規劃的一個基可行解開始，作對應的乘數，並將母規劃分解成幾個子規劃。通過 解幾個子規劃來判斷這一基可行解是否為最優的。若不是最優的，就利用單純形法對母規划進行換基疊代，得到一個新的基可行解，再作相應的乘數……經有限次計算就可以得到母規劃的最優解。這種把一個大規模的線性規劃問題分解成幾個有關係的規模較小的規劃問題來計算的方法， 最早是福特(Lester Randolph Ford，1927— )和富爾克森 (Delbert Ray Fulkerson，1924—1976)在解多種商品網路流時提出。丹齊格(George Bernard Dantzig，1914—2005)和沃爾夫(Philip Wolfe)在他們工作基礎上提出求線性規劃問題的分解算法。分解原理已成為解決大系統最最佳化問題的有力工具。
線性規劃
用線性方程或線性不等式規劃，由若干約束條件組合併具有一定目標的系統，以求得最優解的數學方法。線性規劃是最最佳化方法之一。用數學語言表達，就是在n個變數(x1，x2，……，xn)必須滿足一些線性等式和(或)不等式的條件下，尋求x1，……，xn的一個線性關係的最優解。如在一定的人力、物力、財力、時間等條件下，尋求完成最大的任務量或最小的支出。這個方法是在1947年，美國學者丹西格提出“單純形法”以後，作為運籌學的一個分支科目發展起來。線性規劃的數學模型主要由兩個部分組成：(一)約束條件。即對系統所考慮的控制因素加以限制的條件，或者說該系統達到目標時對各因素的限制條件。(二)目標函式。指系統的最優要求。目標為極大化，則目標函式值取極大值，如利潤、產值、產量等;目標若極小化，目標函式值取極小值，如成本、工時、距離等。具體問題線性規劃的數學模型是各式各樣的，為了方便，人們建立了標準化的約束條件和目標函式的數學模型。線性規劃的求解方法主要有圖解法和單純形法。圖解法即用幾何圖形的分析方法求解，簡便直觀，但只適用於兩個變數的線性規劃問題。單純形法的計算基礎是線性代數。單純形法是逐步求解的，先求可行解(也可能沒有可行解)，再逐步改善可行解，使目標函式達到極值(最大或最小值)就是最優解。單純形法藉助計算機可以求解成百上千個變數的線性規劃。套用線性規劃的系統必須具備下列條件：(一)目標函式可以用極值形式表達。(二)達到目標有不同方法可供選擇。(三)目標是有限制條件的。(四)約束條件和目標函式能用線性方程表示。(五)模型中的生產活動有比例性和加法性。模型中的變數是非負值。線性規劃套用廣泛，從技術問題到工農商、運輸、軍事等計畫管理的決策，從小範圍的工作安排到巨觀的國民經濟計畫。在大型的社會輿論調查和讀者調查的方案設計以及最佳化中也是適用的。
套用——大系統問題
亦稱“大系統”。是現代控制理論的一個重要分支。是指 專門研究那些規模大、層次多、結構雜、因素繁及目標、功能多樣，且伴有 隨機性質系統的綜合自動化、最最佳化問題的理論、技術和方法。如經濟計畫 管理系統、大型聯合企業生產的計算機系統和管理系統、環境保護系統等。 是控制論、系統工程、運籌學的繼續和發展，產生於20世紀70年代，其主要 內容有：對大系統作出各種系統的分析、評價，尋找最最佳化方案。在對大系 統的分析、綜合中，採用“分解——協調”的方法，先將複雜的大系統分解 為若干簡單的小系統，實現小系統最最佳化，然後再根據大系統的總目標，實 現各小系統協調，以便尋得大系統最最佳化。
丹齊格
美國數學家。生於俄勒岡。其父親T.丹齊格也是一位數學家，曾以發表著作《數，科學的語言》(有中譯本)而著稱。1936年丹齊格畢業於馬里蘭大學，之後進入密執安大學攻讀研究生課程。1937年成為美國勞工統計局的統計職員，在那裡接觸到第二次世界大戰時期關於美國經濟投入產出模型的研究。不久進入伯克利加利福尼亞大學，跟隨著名統計學家內曼攻讀博士學位。後來由於美國空軍組建統計控制中心的需要而中止研究生學業，作為文職人員加入空軍。1946年回到伯克利，獲得博士學位。之後成為美國空軍審計長的一名數學顧問。1952年又轉到蘭德公司進行研究。20世紀60年代以後到史丹福大學任教授。丹齊格的主要貢獻線上性規劃方面。1947年，他首次提出線性規劃的名稱，他創立的線性規劃和單純形法在經濟學、環境科學和統計學中有重要套用，從而在美國得到迅速發展，在世界上也處於領先地位，因此他被冠以“線性規劃之父”的頭銜。他還研究整數規劃和非線性規劃，提出對稱的對偶性概念，並研究了對偶規劃問題。其代表作為《線性規劃與推廣》(1963)。為了紀念他的貢獻，美國工業與套用數學學會和數學規劃學會聯合設立一種以丹齊格命名的國際獎，獎勵線上性規劃方面的開創性工作，1982年首次頒獎。
