基于Matlab工具箱YALMIP的Dantzig-Wolfe分解算法實現研究

度巍　張星宇

關鍵詞：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算法的補充材料。

【通聯編輯：謝媛媛】