浅析修正单纯形法的计算.doc
《浅析修正单纯形法的计算.doc》由会员分享，可在线阅读，更多相关《浅析修正单纯形法的计算.doc（5页珍藏版）》请在冰点文库上搜索。
浅析修正单纯形法的计算
摘要：
本文通过实例,对单纯形法和修正单纯形法进行了具体的对比分析,得出了在求解线性规划问题时运用修正单纯形法明显优于单纯形法的结论。
关键词：
单纯形法修正单纯形法对比基矩阵
引言
单纯形法是求解优化设计线性规划问题行之有效的方法,在线性规划问题的求解上得到了广泛的应用。
单纯形法是利用单纯形表通过转轴运算最终获得最优解和目标函数的极值,但一般要列数个单纯形表和进行数次转轴运算,且要计算单纯形表中的所有元素,其计算量较大和较繁琐。
因此,人们在对单纯形法进行了较深入的研究基础上,推出了修正单纯形法或称改进单纯形法。
1单纯形法与修正单纯形法算法对比分析
下面就一具体的线性规划问题,分别用单纯形法和修正单纯形法计算,然后做出对比分析。
求解线性规划问题
1.1单纯形法
运用单纯形表进行运算,即可得到该线性规划问题的最优解和最优值,具体运算过程见表1,表2,表3所示。
表1初始表
解
-7
-12
0
0
0
0
-19
0
9
4
1
0
0
360
374
90
0
4
5
0
1
0
200
210
40
0
3
0
0
1
300
314
30
0
0
0
0
0
0
0
-
-7
-12
0
0
0
0
-19
-
表2
解
-7
-12
0
0
0
0
-19
0
7.8
0
1
0
-0.4
240
248.4
30.77
0
0
0
1
-0.5
50
53
20
-12
0.3
1
0
0
0.1
30
31.4
100
-3.6
-12
0
0
-1.2
-360
-376.8
-
-3.4
0
0
0
1.2
360
357.8
-
表3
解
-7
-12
0
0
0
0
-19
0
0
0
1
-3.12
-0.24
84
81.64
-
-7
1
0
0
0.4
-0.2
20
21.2
-
-12
0
1
0
0.12
0.16
24
24.72
-
-7
-12
0
-13.6
-0.52
-428
-448.88
-
0
0
0
1.36
0.52
428
429.88
-
经过两次运算，得到该线性规划问题的最优解为，，，，最优值。
1.2修正单纯形法
（1）由问题的教学模型,写出初始信息：
，
初始基方阵
同时得
所以
（2）计算各非基本变量的相对价值系数,得
（3）根据，对应非变量，确定为调入基本变量的变量。
同时计算
（4）根据规则,求
得到，它所对应的基本变量被确定为调出变量。
于是得到新的基方阵
，相应的
（5）计算新的基方阵的逆矩阵。
因为从前面（3）（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）.
升级会员 