一种新的对偶原始算法的有效实现

作者：黄金花; 王聪; 刘继清

来源：华中科技大学学报(自然科学版)科技大学, 2021, 49(06): 13-18.

• 线性规划
• 单纯形法
• 原始混合算法
• 最小二乘问题
• 新对偶原始算法

为了规避求解线性规划问题时存在的一系列不足(如受原始退化影响、迭代次数随规模大幅增长、占用中央处理器时间长等),提出了一种处理一般线性规划问题的新对偶原始算法(NDPA),即采用求解一系列无约束最小二乘问题获得残差,确定搜索方向,而不是通过经典非线性优化算法来处理约束最小二乘问题.通过随机生成的线性规划问题试验,初步证明NDPA在迭代次数和计算时间上相较修正后单纯形法具有较大优越性,且NDPA在运行时间上对于修正后单纯形法的优势随测试问题规模的增大而增强,符合对NDPA的期望.当问题规模等于200时,其计算时间可减少约48.87%.

• 单位
  武汉船舶职业技术学院; 华南理工大学; 电子工程学院