改进单纯形法简易算法探究

《改进单纯形法简易算法探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、改进单纯形法简易算法探究【摘要】改进单纯形法的每一步都需要求解基矩阵的逆矩阵，而且与单纯形法不同的是，求解逆矩阵使得其不能使用表上作业法，求解过程繁琐、冗长，不易理解，且不可在计算机上直接求解。本文提出改进单纯形法的表上作业法，且对于初始可行基的求解方法进行改进，使得其可以在计算机上进行，过程直观，计算简便，较两阶段法以及大M法计算量少，数据所占据的内存量要少的多。【关键词】单纯形法；改进单纯形表；迭代线性规划问题是运筹学的一个重要的分支，自1947年丹捷格(G.B.Dantzig)提出了一般线性规划问题的求解方法一单纯形法后，线性规划在理论上

2、趋于成熟，在实用中日益广泛和深入。尤其是在电子计算机能处理成千万个约束条件和决策变量的线性规划问题之后，线性规划问题的适用领域更加广泛。从解决技术问题的最优化设计到工业、农业、商业、交通业、军事、经济计划和管理决策等领域都可以发挥作用，广泛应用于合理下料问题、生产组织与计划问题、运输问题、生产工艺优化等问题，单纯形法已经是现代科学管理的重要手段之一。相信随着科学技术的发展和日益完善，单纯形法在今后有更科学实用的发展。单纯形法作为线性规划主要的算法已经得到广泛的应有。使用单纯形法求解线性规划时，要求有一个初始基可行解，如果没有明显的初始基可行解时

3、，现在常用的方法是引进人工变量构造初始人造基，再利用两阶段法或者大M法进行迭代求解。但是，人工变量的引入使得方程组的变量增加,进而使得计算工作量以及计算机的存储量大为增加，为此出现了很多基于高斯消元法求初始基的方法[1-2],从而使得无需引入人工变量就可求解线性规划问题成为可能。单纯形法的表格繁杂，每一步迭代都需要重新创建新的单纯行表，占据很大的内存，而且效率低下。今在改进单纯形法的基础上，对单纯形表进行改进，创建改进单纯形法的表上作业法，过程直观，计算简便，只需记住一些迭代公式就可掌握其计算方法。引进参考文献中求解初始可行基的方法，更进一步的

4、提高了改进单纯形法的计算效率，也缩减了数据所占据的内存量。1.方法的引入标准形式的线性规划问题：这是线性规划问题的矩阵标准形式。对于（1）式我们通过加入松弛变量变成等式。对于含有初始基的线性规划问题我们知道基变量的检验数一定为0,我们可以不用计算，而且它们的系数矩阵一定是单位矩阵，为此我们是否可以省略单位矩阵，从而简化单纯形表？下面就对本方法进行介绍。1.方法的介绍2.1主要思想单纯形表中基变量的系数矩阵一定为单位矩阵，没有必要必须罗列出来，省略掉基变量的系数矩阵可以简化单纯形表，使得迭代的过程不会过于繁琐，简化后的单纯形表。使用参考文献中的求

5、解初始可行基的方法，不必引进人工变量即可求得初始可行基，进一步简化计算。2.2计算步骤(1)计算初始可行基，，-z(2)建立改进单纯形表表1与单纯形表相似，只是对其进行了改进，下面是对表格的说明：1)S行为第一行，此行为单纯形表中检验数一行，为了计算方便我们将检验数行提到了上面。2)S列为基变量列，我们定义为第一列。3)第二列为价值系数列。4)从第三列开始的各列为各个非基变量的系数列。(3)寻找迭代主元，进行迭代计算与单纯形法寻找最好主元一样，初始改进单纯形表中已有，根据求解最大值线性规划问题的最大原则，确定迭代主元所在的列。价值系数列依次除以

6、迭代主元所在的列中的大于0的各元素为，即：，确定出迭代主元。在新的改进单纯形表中：①原主元所在的位置取原主元的倒数，即②原主元所在的行的其他元素取原表中该行对应元素与原主元的商，即：③原主元所在的列的其他元素（主元素除外）取原主元素除原系数的商的相反数，④其他的各行各列的元素，新元素=原元素-（对角之积十主元），即：经过若干次的迭代，对于求最大值的线性规划问题，直到全部小于等于0,即第一行除-Z外其他元素全部小于等于0,结束计算，得到最优解。求解最小化的线性规划问题，我们只需在目标函数两端同乘以-1,按上述方法进行迭代即可。下面举例计算。1.举

7、例计算此处我们应用参考文献[1][2]综合在一起的一种方法求解初始可行基，得到初始的单纯形表。应用初始的单纯形表求解。，，为初始可行基，检验数一定为0,我们就不再计算。第二步：将上面的数据填入初始改进单纯形表，得到表第三步：确定迭代主元，进行迭代计算在表2中，S行为行，，根据单纯形法求解最大值问题原则，我们确定列为主元列。观察表2知，只有行中0,所以我们可以不用计算值即可确定其为迭代主元。下面以为迭代主元进行迭代计算。1）行中主元取其倒数，即；2）行中的所有元素（除主元外）都除以2；3）所在列中的所有元素（除主元外）除以主元后取其相反数，并填于

8、新的迭代单纯形表中;4）其余元素的计算，在此只举一个为例,其他的计算可仿照此方法依次算出。如行中的第一个元素，填入表3中作为新的b2o计算出其余元素，