度巍 張星宇
關鍵詞:Dantzig-Wolfe分解算法;YALMIP;Matlab;對偶乘子;極方向
中圖分類號:TP311 文獻標識碼:A
文章編號:1009-3044(2024)03-0039-04
0 引言
在現實的工程優化建模中,往往會遇到各種決策變量多,約束復雜的線性規劃模型,尤其是具有塊狀結構的優化問題。針對此情形,1960年線性規劃之父Dantzig.G.B 與學者P.Wolfe[1] 共同提出了Dantzig-Wolfe分解算法(簡稱DW算法)。至今該算法被公認為求解大規模復雜線性規劃的高效算法,其算法蘊含的列生成思想也在其他優化算法中得到應用。然而該算法計算過程較復雜,其中的主次規劃求解迭代細節不易編程實現。本文在文獻[2]的基礎上,發展了一套考慮無界情形的DW 算法步驟,并基于Matlab 軟件,借助YALMIP工具箱,實現了相應的代碼,通過一個算例驗證了程序的可行性,相關工作為DW算法的課堂教學與科研提供了素材。
4 總結
DW分解算法作為解決大規模復雜優化問題的重要算法,在當前中文教材中更側重原理的講解和簡單習題的演算,忽略了算法的代碼實現,難以適應當前教學與相關科研的需要。由于Matlab的YALMIP工具箱提供了描述優化模型的簡潔語法,同時可以快捷獲取對偶乘子值,本文構建了考慮無界情形下DW算法的實現代碼,可作為高級運籌學、優化理論與算法等相關課程里教授DW算法的補充材料。
【通聯編輯:謝媛媛】