浅析修正单纯形法的计算

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

2、体的线性规划问题，分别用单纯形法和修正单纯形 法计算，然后做出对比分析。求解线性规划问题min z = -7 x -12xs.9 x + 4 x4 x + 5 x3 x +10 x + x = 300X0（ j = 1，2，5）1.1单纯形法运用单纯形表进行运算，即可得到该线性规划问题的最优解 和最优值，具体运算过程见表1,表2,表3所示。表1初始表解-7-120000-199ijcP.PP,PbP0 x19243140503603749003x450102002104004x31000130031430 f。）0000000-c f (a )-7-120000-19-17表2解-7-1200

3、00-199iJcPPPP一b-P-0 x17.82031405-0.4240248.430.7703x2.5001-0.5505320 -124x0.31000.13031.4100f (a, X-3.6-1200-1.2-360-376.8-c f J(a )-3.40001.2360357.8-77解-7-120000-199iJcPPPP,Pb0 x1020314-3.125 -0.248481.64-73x1000.4-0.22021.2-121x0100.120.162424.72-f (a, Y-7-120-13.6-0.52-428-448.88-c f J(a )0001.3

4、60.52428429.88-7720，经过两次运算，得到该线性规划问题的最优解为X1% = 24，X3 = 84，X4 = X5 = 0，最优值 z = -428。1.2修正单纯形法(1)由问题的教学模型，写出初始信息：P1P2P3P4P5-94100 -A =45010,c = -7 -12 0 0 0310001b = 360200300 t初始基方阵1 0 0_E = pp p =0 1 003450 0 11 0 0同时得E-1 = 0 1 0 00 0 1所以X =E0X3X4X5100360360E-1b =010200=2000_001 _300300c E-1 = 0 0E0

5、1 0 00 0 1 0 = 0 0 00 0 1(2)计算各非基本变量的相对价值系数，得r = c - c E-1 p = -7 - 09004=-745 =-1210L 广 Cf - 0 (3)根据min尸=一7,r =一12= r，对应非变量x，确定x为调入基本1222210 0_ 4-4_E-1 p =01 05=50200 11010变量的变量。同时计算(4)根据0规则，求.I 360 200 300 I 300 七-mn | 4- 11 = 10-=30 得到 s = 3，它所对应的基本变量X5被确定为调出变量。于是得到新的基方阵E1 =P p p，相应的 C =0 0 12(5)

6、计算新的基方阵的逆矩阵E1。因为从前面(3)(4 )步得到主元素为10,s=3,所以可以得到1 0r一1 .E-1E 0 -1 = 0 1L 010 0-0.4-0.5，所以0.110-0.4 -10-0.4 一360-240一E-1 =10010-0.50.1，x = E-1 x =气1 E00010-0015200=5030c E-1 = 0E111 0 -0.41r0 -12 0 1 -0.5 = 00 -1.20 0 0.1用E1代替E-1重复以上步骤(2)-(5)。得到最优解。最优解为x = 20，x = 24， x = 84，x = x = 0。目标函数的极小值为84z = c x

7、E =【0 -7 -12 20 = -428e22224由单纯形法和修正单纯形法的计算过程可得出如下几点结论：修正单纯形法和单纯形法一样，在进行E=【p P . P乌到E =P % . P 匕的基方阵变换时，仍要确定进行基本变量的变量七和离开基本变量七的判别和计算。因此, 规则和最速变化规则仍是修正单纯形法应遵循的基本原则；单纯形法要计算单纯形表中的所有元素，而修正单纯形法只要 计算基矩阵的逆矩阵E-1和E-ib、E-1A、C - C e-1 A这三组数据。E E基方阵E求逆只需对其中的一列数据进行计算，这可减少计算E的逆矩 阵的工作量。2结语由上述实例计算和对计算过程分析可知，修正单纯形法的计 算量比单纯形法的要小,且每次迭代时只存储一个初等矩阵，存储 量小。因此，修正单纯形法是在计算机上求解线性规划问题的实用 而有效的方法。参考文献：徐成贤.修正单纯形法的有效而稳定的执行方法J.西安交 通大学学报，1992,(04).郭强.修正单纯形法的计算量的注记J.运筹与管理， 1999,(02).申