青年学生基础研究项目负责人在线性规划基础理论研究中取得进展

文章导读

你是否知道，一个困扰运筹学界7多年的算法瓶颈，竟被一位中国博士生撕开突破口？线性规划中的“高退化”问题长期导致求解效率骤降，严重影响航空调度资源分配等关键领域。同济大学郭斯琪提出“升维深度对偶最优不等式”与“增强检验数”理论，首创“Pruning-and-pricing”主元法，不仅从根源上识别退化变量，更将嵌套问题求解速度提升近5倍。成果登顶运筹学顶刊《Operations Research》，已应用于18家航空公司，覆盖全国1/3民航运力，大幅降低运营成本。这不仅是理论突破，更是中国青年学者推动工业优化升级的硬核实践。

— 内容由好学术AI分析文章内容生成，仅供参考。

　　线性规划作为数学规划与运筹学的核心分支，在供应链管理、路径优化、金融决策等领域被广泛应用。自1947年单纯形法提出以来，该方法被长期视为求解线性规划问题的经典算法。然而，实际应用中的高退化性问题常导致单纯形法及其衍生算法（如列生成法、行列生成法）收敛效率显著降低，这一瓶颈问题至今仍是该领域亟待攻克的理论难题。

　　围绕上述科学问题，同济大学博士生郭斯琪在国家自然科学基金青年学生基础研究项目（博士研究生）724B2025资助下，针对高退化线性规划问题，开展了关于单纯形法退化生成机理及缓解措施的理论和实验研究，取得以下研究成果：

　　1. 提出了一类“升维深度对偶最优不等式”，通过缩减对偶可行域，有效稳定对偶变量取值，拓展了文献中已有对偶不等式法的理论内涵及应用范围。

　　2. 针对包含对偶最优不等式的线性规划问题，创新性地提出了“增强检验数”概念，并证明了其严格优于已沿用近80年的单纯形法传统检验数。

　　3. 构建了“Pruning-and-pricing”主元方法，结合了增强检验数和传统检验数的优点，首次实现在变量进入可行基之前识别其是否为退化变量。

　　4. 针对高退化嵌套集覆盖问题，结合增强检验数和Pruning-and-pricing主元方法，设计了高效的嵌套行列生成算法。算法求解速度相较于传统方法提升了近5倍，为大规模资源调度问题的高效求解提供了新思路。

　　研究成果以“嵌套集覆盖/包装问题：退化缓解和对偶稳定（Nested set covering/packing problem: Degeneracy alleviation and dual stabilization）”为题，于2025年7月在线发表在《运筹学》（Operations Research）期刊上。论文链接：https://doi.org/10.1287/opre.2024.0720。

　　该研究不仅深化了对线性规划退化现象的理论认知，更通过算法创新为相关领域的工程应用提供了重要技术支撑，已成功应用于东方航空、四川航空、厦门航空等18家航空公司的飞机、机组排班问题，服务了我国1400余架民用客机和货机（占我国飞机总数的1/3）、近万名飞行员、近2万名空中服务人员，在大幅提升飞机排班和机组排班决策效率的同时，显著降低了航司运营成本。