求线性规划初始基本可行解的最小价格系数最小比值法

摘要

本文对世界运筹学历史、中国运筹学历史、线性规划历史做了细致的综述，介绍了近些年来在求线性规划初始基本可行解方面取得的主要成果，对这些方法作了比较、归纳。 本文的创新点，给出了求线性规划初始基本可行解的最小价格系数最小比值法。该法的主要特点有不需要引入人工变量，不需要求解另一个线性规划，可能最多迭代m(约束方程的个数)步即可获得一个初始基本可行解，或者在计算过程中可以判断出线性规划无可行解；对于求极小值的线性规划问题，主元总在未进基变量所对应的最小价格系数的系数列中选，使得按该法得到的初始基本可行解与用其它方法得到的初始基本可行解相比往往更接近最优解；不改变约束条件，对不同的目标函数一般会得到不同的初始基本可行解；已进基变量不会出基，避免重复运算，节省计算量和存储量，对大规模线性规划这一特点会更突出。