基于Matlab工具箱YALMIP的Dantzig-Wolfe分解算法實(shí)現(xiàn)研究

度巍　張星宇

關(guān)鍵詞：Dantzig-Wolfe分解算法；YALMIP；Matlab；對(duì)偶乘子；極方向

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）03-0039-04

0 引言

在現(xiàn)實(shí)的工程優(yōu)化建模中，往往會(huì)遇到各種決策變量多，約束復(fù)雜的線性規(guī)劃模型，尤其是具有塊狀結(jié)構(gòu)的優(yōu)化問題。針對(duì)此情形，1960年線性規(guī)劃之父Dantzig.G.B 與學(xué)者P.Wolfe[1] 共同提出了Dantzig-Wolfe分解算法（簡(jiǎn)稱DW算法）。至今該算法被公認(rèn)為求解大規(guī)模復(fù)雜線性規(guī)劃的高效算法，其算法蘊(yùn)含的列生成思想也在其他優(yōu)化算法中得到應(yīng)用。然而該算法計(jì)算過程較復(fù)雜，其中的主次規(guī)劃求解迭代細(xì)節(jié)不易編程實(shí)現(xiàn)。本文在文獻(xiàn)[2]的基礎(chǔ)上，發(fā)展了一套考慮無界情形的DW 算法步驟，并基于Matlab 軟件，借助YALMIP工具箱，實(shí)現(xiàn)了相應(yīng)的代碼，通過一個(gè)算例驗(yàn)證了程序的可行性，相關(guān)工作為DW算法的課堂教學(xué)與科研提供了素材。

4 總結(jié)

DW分解算法作為解決大規(guī)模復(fù)雜優(yōu)化問題的重要算法，在當(dāng)前中文教材中更側(cè)重原理的講解和簡(jiǎn)單習(xí)題的演算，忽略了算法的代碼實(shí)現(xiàn)，難以適應(yīng)當(dāng)前教學(xué)與相關(guān)科研的需要。由于Matlab的YALMIP工具箱提供了描述優(yōu)化模型的簡(jiǎn)潔語法，同時(shí)可以快捷獲取對(duì)偶乘子值，本文構(gòu)建了考慮無界情形下DW算法的實(shí)現(xiàn)代碼，可作為高級(jí)運(yùn)籌學(xué)、優(yōu)化理論與算法等相關(guān)課程里教授DW算法的補(bǔ)充材料。

【通聯(lián)編輯：謝媛媛】