浅析修正单纯形法的计算.doc

1、浅析修正单纯形法的计算摘要：本文通过实例,对单纯形法和修正单纯形法进行了具体的对比分析,得出了在求解线性规划问题时运用修正单纯形法明显优于单纯形法的结论。关键词：单纯形法 修正单纯形法 对比 基矩阵引 言单纯形法是求解优化设计线性规划问题行之有效的方法,在线性规划问题的求解上得到了广泛的应用。单纯形法是利用单纯形表通过转轴运算最终获得最优解和目标函数的极值,但一般要列数个单纯形表和进行数次转轴运算,且要计算单纯形表中的所有元素,其计算量较大和较繁琐。因此,人们在对单纯形法进行了较深入的研究基础上,推出了修正单纯形法或称改进单纯形法。1 单纯形法与修正单纯形法算法对比分析下面就一具体的线性规划问

2、题,分别用单纯形法和修正单纯形法计算,然后做出对比分析。求解线性规划问题 1.1单纯形法运用单纯形表进行运算,即可得到该线性规划问题的最优解和最优值,具体运算过程见表1,表2,表3所示。表1 初始表解-7-120000-19094100360374900450102002104003001300314300000000-7-120000-19- 表2解-7-120000-1907.8010-0.4240248.430.770001-0.5505320-120.31000.13031.4100-3.6-1200-1.2-360-376.8-3.40001.2360357.8- 表3 解-7-12

3、0000-190001-3.12-0.248481.64-71000.4-0.22021.2-120100.120.162424.72-7-120-13.6-0.52-428-448.88-0001.360.52428429.88-经过两次运算，得到该线性规划问题的最优解为，最优值。1.2修正单纯形法(1)由问题的教学模型,写出初始信息：,，初始基方阵同时得所以(2)计算各非基本变量的相对价值系数,得(3)根据，对应非变量，确定为调入基本变量的变量。同时计算(4)根据规则,求得到，它所对应的基本变量被确定为调出变量。于是得到新的基方阵，相应的（5）计算新的基方阵的逆矩阵。因为从前面(3)(4)

4、步得到主元素为10,s=3,所以可以得到，所以，用代替重复以上步骤(2)-(5)。得到最优解。最优解为，。目标函数的极小值为由单纯形法和修正单纯形法的计算过程可得出如下几点结论：(1) 修正单纯形法和单纯形法一样,在进行到的基方阵变换时,仍要确定进行基本变量的变量和离开基本变量的判别和计算。因此,规则和最速变化规则仍是修正单纯形法应遵循的基本原则；(2) 单纯形法要计算单纯形表中的所有元素,而修正单纯形法只要计算基矩阵的逆矩阵和、这三组数据。(3) 基方阵E求逆只需对其中的一列数据进行计算，这可减少计算E的逆矩阵的工作量。2 结语由上述实例计算和对计算过程分析可知,修正单纯形法的计算量比单纯形法的要小,且每次迭代时只存储一个初等矩阵,存储量小。因此,修正单纯形法是在计算机上求解线性规划问题的实用而有效的方法。参考文献：1徐成贤. 修正单纯形法的有效而稳定的执行方法J. 西安交通大学学报, 1992,(04) .2 郭强. 修正单纯形法的计算量的注记J. 运筹与管理, 1999,(02) .3 申卯兴,许进. 求解线性规划的单纯形法的直接方法J. 计算机工程与应用, 2007,(30) .4 祝青芳. 细说单纯形法J. 考试周刊, 2007,(38) .5 范国兵. 线性规划问题的一种改进的单纯形法J. 海南大学学报(自然科学版), 2007,(03) .