线性规划概念是在1947年的军事行动计划有关实践中产生的，而相关问题1823年Forier和口1911年PQusi就已经提出过，发展至今已有将近100年的历史了。现在已成为生产制造、市场营销、银行贷款、股票行情、出租车费、统筹运输、电话资费、电脑上网等等热点现实问题决策的依据。线性规划就是在满足线性约束下，求线性函数的极值。毋庸置疑，数学规划领域的重大突破总是始于线形规划。提到线性规划算法，人们最先想到的是单纯形法和内点法。单纯形法是实际应用中使用最普遍的一种线性规划算法，而研究者们已证明在最坏的情况下单纯形法的计算复杂度是指数级的，内点算法的计算复杂度是多项式时间的。把两种算法相提并论，要么是这两种算法都已经非常完备，要么都有需改进之处。显然不属于前者，即两者都有需要改进之处。几十年来，研究者通过不断努力，在两种算法的计算上都取得相当的进展。1数学模型线性规划问题通常表示成如下两种形式:标准型、规范型。设jj(2，n)是待确定的非负的决策变量；认2，n)是与决策变量相对应的价格系数
