线性规划算法的改进及在企业管理中的应用【文献综述】

《线性规划算法的改进及在企业管理中的应用【文献综述】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业论文文献综述数学与应用数学线性规划算法的改进及在企业管理中的应用线性规划是运筹学最基木、运用最广泛的分支，是其他运筹学问题研究的基础。在20世纪50年代到60年代期间，运筹学领域出现许多新的分支：非线性规划、商业应用、大尺度方法、随机规划、整数规划、互补转轴理论、多项式时间算法等。20世纪70年代末，上述分支领域都得到了极大发展，但是却都不完善。而且数学规划领域中存在许多Np-hard问题，如TSP问题，整数规划问题等。这些问题的基本模型都口J以写成线性规划形式，因此通过对线性规划算法的进一步研究，可以进一步启发及推动数学规划领域内其他分支

2、的发展。线性规划理论和算法的研究及发展共经丿力了三个高潮，每个高潮都引起了社会的极大关注。线性规划研究的第一高潮是著名的单纯形法的研究。这一方法是Dantzing在1947年提出的，它以成熟的算法理论和完善的算法及软件统治线性规划达三十多年。随着60年代发展起来的计算性复杂理论的研究，单纯形法在七I•年代末受到了挑战。1979年前苏联数学家Khachiyan提出了第一个理论上由于单纯形法的所谓多项式时间算法一椭球法，曾成为轰动一时的新闻，并掀起了研究线性规划的第二个高潮。但遗憾的是广泛的数值试验表明，椭球算法的计算比单纯形方法差。1984年Ka

3、rmarkar提出了求解线性规划的另一个多项式时间算法。这个算法从理论上和数值上都由于椭球法，因而引起学术界的极大关注，并由此掀起了研究线性规划的第三个高潮。从那以后，许多学者致力于改进和完善这一算法，得到了许多改进算法。这些算法运用不同的思想方法均获得通过可行域内部的迭代点列，因此统称为解线性规划问题的内点算法。H前内点算法正以不可抗拒的趋势将超越和替代单纯形法。单纯形法是求解线性规划问题很冇效的方法，基本思想是从方程组AX=0的某个基可行解开始，在不违背条件Xno的前提下，不断生成新的基可行解，且基可行解的每次更新，均能确保目标函数值有所改

4、进，一直获得最优解为止，是一个多次迭代的过程。此方法从理论上已趋丁完善，但在求最优解的过程屮述冇很多值得研究和改进的，在现有的方法中，单纯形表很烦琐，在计算中，光制表就要浪费很多的时间。另外，根据不同的类型有大M法、两阶段法，而这两种方法求解过程更麻烦，迭代次数都较大，还要有很多语言叙述，即使-•个很简单的题，要得到最优解，也需要做大量的工作。针对上述问题，可以利用单纯形法的思想，将现有的单纯形法进行改进，给出单纯形表的矩阵形式，用矩阵的行的初等变换来实现求解过程，使方法更容易理解和掌握，求解过程更简捷，并通过例了來展示此种方法的优越性。展丙军

5、在《单纯形法的改进及应用》中提到，在利用线性规划的单纯形法求解时，首先，要在线性规划问题屮引入人工变量，把问题变为约束方程组的系数炬阵屮含有单位矩阵，用以作为人造基，然后按单纯形方法进行换基迭代，求得最优解或判定无最优解，这种方法称为两阶段法。第一阶段是判断原线性规划问题是否存在基本可行解。第二阶段是由第一阶段最后求得原问题的一个可行基开始，运用单纯形方法，求得原问题的最优解或判定原问题无最优解。有些线性规划问题，引进松驰变量化成标准形后，约束条件方程组的系数矩阵并不舍m阶单位矩阵，这样就给单纯形解法的换基迭代带来了困难。线性规划在利用两阶段法

6、解这类问题时，尤其是一些具体的实际问题，对于加人的人工变量Yi应该根据问题尽可能的少，使人工变量的个数小于（或等于）哄口岩在《线性规划中两阶段法的简便算法》就线性规划问题的原问题在加人人工变量y中，如何根据所给问题尽可能的少引人人工变量，通过例子来说明线性规划问题两阶段法的简便计算法。需要注意的是尽可能少引人人工变量y的同时，保证使约束条件方程组的系数矩阵中有一个可行基，这就要根据实际问题，灵活运用两阶段法。刘心在《线性规划增减约束条件的灵墩度分析》中，在灵墩度分析的基础上，面对增减约束条件，特别对减少约束的情形，给出新最优方案的获得方法，并指

7、出其特殊的经济意义。一个企业要在市场竞争中立于不败之地，就必须改善经营管理，提高经济效益，具体包括怎样合理安排生产任务、合理配置资源，怎样制定最优的生产计划，并对瞬息万变的市场信息及时作出反应。随着计算机技术的普及，线性规划的数学方法在企业管理中应用的范围越來越广泛。线性规划产生于三十年代未和四十年代初，并随着现代科技和管理实践的发展而不断发展。是运筹学屮起源较早、理论上较成熟的一个分支。线性规划的“线性”特点，简化了数学模型的构造和解题方法，容易被一般未具冇高等数学知识的各级企业管理人员所掌握应用。特别是计算机的广泛应用，线性规划的在企业管理

8、中的应用范围更加广泛和深入。渐渐成为管理人员必须掌握的一门现代化管理方法和优化技术。线性规划在企业中的应用范围：企业的效益依赖于资源配置的优化，即依赖