摘要：在当今大数据背景下,从实际应用中抽象出来的线性规划问题的规模越来越大,复杂性越来越高,因此数据预处理技术在线性规划问题求解中的重要性日渐突显。对偶性不仅有助于原始问题的算法(如对偶单纯形法)求解,而且是进行算法求解前的预处理步的重要组成部分。针对后者,本文基于有上下界的线性规划模型,详细分析总结了将对偶性应用于预处理中的两种方法:优先列和比例列的处理,并利用无效约束的概念证明了弱优先列的性质,最后应用C语言将预处理方法进行编程实现,以国际通用题库中变量个数大于1500的标准线性规划问题为实例进行测试。实例测试结果表明:(1)对于一般线性规划问题而言,对偶性在预处理中的应用能够有效减小问题规模,一方面体现在直接减少问题的变量数和非零元数,另一方面通过影响其他预处理方法间接减少问题的约束个数;(2)从减小问题规模的角度,对大部分问题而言比例列的预处理效果优于优先列。

关键词：线性规划 预处理 对偶性 优先列 比例列 

单位：中国科学院科技战略咨询研究院; 中国科学院大学