《线性规划算法的改进及在企业管理中的应用【文献综述】》由会员分享，可在线阅读，更多相关《线性规划算法的改进及在企业管理中的应用【文献综述】（4页珍藏版）》请在金锄头文库上搜索。
1、毕业论文文献综述数学与应用数学线性规划算法的改进及在企业管理中的应用 线性规划是运筹学最基本、运用最广泛的分支，是其他运筹学问题研究的基础。在20世纪50年代到60年代期间，运筹学领域出现许多新的分支：非线性规划、商业应用、大尺度方法、随机规划、整数规划、互补转轴理论、多项式时间算法等。20世纪70年代末,上述分支领域都得到了极大发展，但是却都不完善。而且数学规划领域中存在许多Np-hard问题,如TSP问题，整数规划问题等。这些问题的基本模型都可以写成线性规划形式，因此通过对线性规划算法的进一步研究，可以进一步启发及推动数学规划领域内其他分支的发展。线性规划理论和算法的研究及发展共经历了三个
2、高潮，每个高潮都引起了社会的极大关注。线性规划研究的第一高潮是著名的单纯形法的研究。这一方法是Dantzing在1947年提出的，它以成熟的算法理论和完善的算法及软件统治线性规划达三十多年。随着60年代发展起来的计算性复杂理论的研究，单纯形法在七十年代末受到了挑战。1979年前苏联数学家Khachiyan提出了第一个理论上由于单纯形法的所谓多项式时间算法-椭球法，曾成为轰动一时的新闻，并掀起了研究线性规划的第二个高潮。但遗憾的是广泛的数值试验表明，椭球算法的计算比单纯形方法差。1984年Karmarkar提出了求解线性规划的另一个多项式时间算法。这个算法从理论上和数值上都由于椭球法，因而引起学
3、术界的极大关注，并由此掀起了研究线性规划的第三个高潮。从那以后，许多学者致力于改进和完善这一算法，得到了许多改进算法。这些算法运用不同的思想方法均获得通过可行域内部的迭代点列，因此统称为解线性规划问题的内点算法。目前内点算法正以不可抗拒的趋势将超越和替代单纯形法。单纯形法是求解线性规划问题很有效的方法，基本思想是从方程组AX=0的某个基可行解开始，在不违背条件X 0的前提下，不断生成新的基可行解，且基可行解的每次更新，均能确保目标函数值有所改进，一直获得最优解为止，是一个多次迭代的过程。此方法从理论上已趋于完善，但在求最优解的过程中还有很多值得研究和改进的，在现有的方法中，单纯形表很烦琐，在计
4、算中，光制表 就要浪费很多的时间。另外，根据不同的类型有大M法、两阶段法，而这两种方 法求解过程更麻烦，迭代次数都较大，还要有很多语言叙述，即使一个很简单的题，要得到最优解，也需要做大量的工作。针对上述问题，可以利用单纯形法的思想，将现有的单纯形法进行改进，给出单纯形表的矩阵形式，用矩阵的行的初等变换来实现求解过程，使方法更容易理解和掌握，求解过程更简捷，并通过例子来展示此种方法的优越性。展丙军在单纯形法的改进及应用中提到，在利用线性规划的单纯形法求解时，首先，要在线性规划问题中引入人工变量，把问题变为约束方程组的系数矩阵中含有单位矩阵，用以作为人造基，然后按单纯形方法进行换基迭代，求得最优解
5、或判定无最优解，这种方法称为两阶段法。第一阶段是判断原线性规划问题是否存在基本可行解。第二阶段是由第一阶段最后求得原问题的一个可行基开始，运用单纯形方法，求得原问题的最优解或判定原问题无最优解。有些线性规划问题，引进松驰变量化成标准形后，约束条件方程组的系数矩阵并不舍 m阶单位矩阵，这样就给单纯形解法的换基迭代带来了困难。线性规划在利用两阶段法解这类问题时，尤其是一些具体的实际问题，对于加人的人工变量Yi应该根据问题尽可能的少，使人工变量的个数小于（或等于)m。白岩在线性规划中两阶段法的简便算法就线性规划问题的原问题在加人人工变量 y中，如何根据所给问题尽可能的少引人人工变量，通过例子来说明线
6、性规划问题两阶段法的简便计算法。需要注意的是尽可能少引人人工变量y的同时，保证使约束条件方程组的系数矩阵中有一个可行基，这就要根据实际问题，灵活运用两阶段法。刘心在线性规划增减约束条件的灵敏度分析中，在灵敏度分析的基础上， 面对增减约束条件，特别对减少约束的情形，给出新最优方案的获得方法，并指出其特殊的经济意义。 一个企业要在市场竞争中立于不败之地，就必须改善经营管理，提高经济效益，具体包括怎样合理安排生产任务、合理配置资源，怎样制定最优的生产计划，并对瞬息万变的市场信息及时作出反应。随着计算机技术的普及，线性规划的数学方法在企业管理中应用的范围越来越广泛。线性规划产生于三十年代未和四十年代初
7、，并随着现代科技和管理实践的发展而不断发展。是运筹学中起源较早、理论上较成熟的一个分支。线性规划的“线性”特点，简化了数学模型的构造和解题方法，容易被一般未具有高等数学知识的各级企业管理人员所掌握应用。特别是计算机的广泛应用，线性规划的在企业管理中的应用范围更加广泛和深入。渐渐成为管理人员必须掌握的一门现代化管理方法和优化技术。线性规划在企业中的应用范围：企业的效益依赖于资源配置的优化，即依赖于线性规划模型的优化，优化的范围越大，效果也就越好。首先，线性规划可用于生产计划确定后的优化，内容包括：其一，在一定的资金和风险条件下，确定最佳库存量，使生产保持连续性 和资金占用最小。其二，在生产计划、
8、生产设备、生产能力的条件限制下，在各种产品、原材料、零部件的价格、生产人员的约束条件下，求得产品的最大利益。其三，在运输分配计划中，计算路径、数量、人员的最佳效率和最小费用。其四， 在原材料具有混合比例的限制下，求得价格、成本最低、利益最大。其五，各类投资问题：一定的资金总额，利率与回收期不同的项目之间，如何投放使用，才能使经济效益最好。其二：线性规划支持企业未来的决策。管理者必须分析未来的经济走势、分析未来的消费趋势并预测同行的产销动向。然后确定自己的产品价格、广告与促销策略，最后再将这些数据进行线性规划。这是求解一个随机线性规划问题。此类问题有待于进一步探讨。参考文献：1 吕游. 运筹学的
9、应用与发展J. 大庆师范学院,2007.2 陈宝林. 最优化理论与算法M. 北京:清华大学出版社,2005.3 曾梅清、田大钢. 线性规划问题的算法综述J. 科学技术与工程.2001,1.4. 周凯山、罗毅平. 两类特殊线性规划算法的改进J. 系统工程,1998,5.5. 展丙军. 单纯形法的改进及其应用J. 大庆师范学院学报.2007,4.6. 金涛,刘三阳,孙小军. 一种线性规划问题单纯形法的改进算法J. 2007,12.7. 白岩. 线性规划中两阶段法的简便计算法J. 长春师范学院学报,2005.8. 孙可钦. 线性规划两阶段法的改进算法J. 运筹与管理,2000,3.9. 夏少刚,刘心
10、. 线性规划增减约束条件的灵敏度分析J. 运筹与管理2007,4.10. 王昌贵. 线性规划在企业管理中的应用J. 大众科技,2004,12.11. 雷红. 浅谈线性规划在企业管理中的应用J. 科技情报开发与经济,2000,6.12. Konstantinos Dosios, Konstantinos Paparrizos . Resolution of the problem of degeneracy in a primal and dual simplex algorithmJ. Operations Research Letters 1997.13. Jian-Feng Hu . A note on“an improved initial basis for the simplex algorithm”J. Computers & Operations Research 34 (2007) 3397 3401.14. Tamas Koltai ,Viola Tatay . A practical approach to sensitivity analysis in linear programming under degeneracy for management decision makingJ. Int. J. Production Economics.
