基于效率最优的单纯形法的改进

谢 振

（运城学院，山西 运城 044000）

基于效率最优的单纯形法的改进

谢 振

（运城学院，山西 运城 044000）

提高单纯形法的运算效率是运筹学一直在研究的一个重要问题.文章通过对传统单纯形法的计算机程序化算法的改进，降低了时间和空间复杂度，使两者的效率均达到了o（1）.经过大量实例证明，改进后的算法还减少了进行单纯形法变换时所用到的迭代次数.

单纯形法；时间复杂度；空间复杂度；迭代次数

单纯形法是为用程序的思想解决线性规划问题而提出的，但是在大量解决线性规划问题的实践中，笔者发现计算机在选取换入基变量时所用到的内存的空间复杂度和计算所耗的时间复杂度均为o（n）［1］.比如一个具有n个决策变量的线性规划问题，在每次选取换入基变量时都要将n个检验数全部调入内存，然后将所有的检验数进行比较，运算极为复杂［2］.本文试图研究如何降低计算时所产生的时间和空间复杂度问题，经过大量的实践证明本文提出的方法使效率大大提高.

1 问题改进

设标准形式的线性规划问题如下：

具体改进过程如下：

Step1：将数学模型化成标准型后，将目标函数中的自变量x i按其对目标函数的贡献率（即系数ci）大小由大到小重新排列自变量和其系数组合ci x i位置［3］.

Step2：根据移动后的自变量位置，重新组合约束方程组中每个约束方程内自变量，使其改变后的位置与目标函数中的相对应，按改变后的数学模型列出初始单纯形表.

Step3：在确定换入基的变量时，只要有检验数“Cj－Zj＞0”，则说明该问题还没有找到最优解，此时选取第一个“Cj－Zj＞0”的检验数所对应的自变量作为换入基的变量［4］.

Step5：利用单纯形表进行演算新的基可行解，看其是否达到所有检验数都为非正，如果是则说明该基可行解为最优解，否则调用Step3、Step4，继续寻找最优解［5］.

2 实例分析

例1

设有一线性规划问题数学模型如下：

根据改进后的算法需将数学模型变为以下形式

通过增加松弛变量将其变成线性规划问题的标准形式为

该问题的初始单纯形表如表1所示.

表1 初始单纯生表

但由于不同主体在回应乡村问题时采取不同的策略，差异化的乡建模式有各自的优点和运用局限（表2）。乡建没有统一的模板，应基于不同村庄的自然、社会、经济、文化背景，从而探索出适应自身发展的道路[19，20]。任何一种乡村实践，都不可能面面俱到，需要分清主次、懂得取舍，在传承过去、践行现在、发展未来之间取得平衡

表2 第1次切入基变量运算表

根据步骤Step3、Step4同样可得出表2的换入基变量为X2，换出基变量为X5，然后将表2进行相应的行变换得出最终表3.

表3 第2次切入基变量运算表

最后一行检验数均为非正，所以该题存在唯一最优解：X1＝0，X2＝8／5，X3＝1／5，X4＝X5＝X6＝0；最优值是19／5.

例2

现以文献［6］中所举一例来说明.

某水库灌区，主要种植小麦、棉花和玉米三种作物，根据气象和水文预报，明年水库来水量为22 500万 m3，预估小麦、棉花、玉米的毛灌溉定额分别为1 800 m2／hm2，2 400 m2／hm2，1 200 m2／hm2；三种作物预测产值分别为1 800元／hm2，3 000元／hm2，1 200元／hm2.灌区总面积为10万hm2，根据地区种植计划要求，棉花种植面积不得大于4万hm2.问明年这三种作物种植面积应如何安排，灌区总产值为最大［3］.

设x1，x2，x3分别为小麦、棉花、玉米的种植面积，则该线性规划问题的数学模型如下：

通过增加松弛变量将其变成线性规划问题的标准形式为

解题步骤如表4所示：

由表4可知，X1＝6，X2＝4，X3＝7／4，X5＝17／4，X4＝X6＝X7＝0时，可得灌溉区总产值最大为24 000万元.

表4 效率对比表

通过以上两个例题，本文通过计算它们的时空复杂度与一般单纯形计算时的时空复杂度做以下比较：

项目题 例题1 例题2一般单纯形法计算时比较次数18 28改进后单纯形法计算时比较次数9 13

由表4可知，改进后的单纯形法的计算次数较之一般单纯形法减少了很多.

3 结论

通过该改进方法，可以得出5个结论：

1）较之用传统单纯形法确定换入基变量所耗的复杂度要小得多，效率也会大大提高；

2）并不需要把所有检验数都调入内存中，只需单个调入内存，并找到第一个正检验数所对应的变量作为入基变量即可；

3）将选取换入基变量所耗费的时间和空间复杂度均为o（n）的不确定性变为了o（1）的确定性；

4）改进后的算法大大减少了计算机的计算量和降低了内存的使用频率，并且随着决策变量的增多，这种算法的优势会越来越明显；

5）经过大量的实例运用，改进后的单纯形法还能减少用单纯形表解决问题的计算迭代次数.

总之，改进后的单纯形法大大提高了用计算机程序解题时的计算效率，并且随着目标函数中决策变量数量的增加其效果会更加明显.

［1］杨 旭.线性规划单纯形法一种新的解题途径［J］.河海学报，1991，7：134-137

［2］甘应爱，田 丰，李维铮，等.运筹学［M］.北京：清华大学出版社，1995

［3］兰 艳，李学勇.一种改进的单纯形法［J］.长沙大学学报，1998，12：29-32

［4］张传平，冯德田.对改进单纯形法的探讨［J］.石油大学学报（自然科学版），1999，8：119-120

［5］胡运权，郭耀煌.运筹学教程［M］.北京：清华大学出版社，2002

［6］朱求长.运筹学及其应用［M］.湖北：武汉大学出版社，2003

Improvement on the Basis of the Efficient Simplex Method

Xie Zhen
（Yuncheng University，Yuncheng 044000，China）

To improve the operational efficiency of simplex method is an important topic that has always been researched in operations research.As is discussed in the paper，by improving the computer programming calculation of the traditional simplex method，the complexity of time and the complexity of space are both lowered，so the efficiency of either type reaches o（1）.And many examples also show that the improved calculation decreases the number of successive times needed in the rotation of the simplex method.

simplex method；complexity of time；complexity of space；the number of iterations

王映苗】

1672-2027（2012）01-0104-05

TP312

A

2011-12-23

谢 振（1984-），男，山西运城人，硕士，运城学院助教，主要从事产业经济学、市场营销.