基于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算法的补充材料。

【通联编辑：谢媛媛】