对偶性在线性规划预处理中的应用分析

摘要：

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

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

所属期刊栏目：24

分类号：O221.1(运筹学)

在线出版日期：2017-05-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：117-126