改进单纯形法的简易算法研究.docx

《改进单纯形法的简易算法研究.docx》由会员分享，可在线阅读，更多相关《改进单纯形法的简易算法研究.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、改进单纯形法的简易算法研究 【摘要】改进单纯形法的每一步都须要求解基矩阵的逆矩阵，而且与单纯形法不同的是，求解逆矩阵使得其不能运用表上作业法，求解过程繁琐、冗长，不易理解，且不行在计算机上干脆求解。本文提出改进单纯形法的表上作业法，且对于初始可行基的求解方法进行改进，使得其可以在计算机上进行，过程直观，计算简便，较两阶段法以及大M法计算量少，数据所占据的内存量要少的多。 【关键词】单纯形法；改进单纯形表；迭代 线性规划问题是运筹学的一个重要的分支，自1947年丹捷格提出了一般线性规划问题的求解方法单纯形法后，线性规划在理论上趋于成熟，在好用中日益广泛和深化。尤其是在电子计算机能处理成千万个约束

2、条件和决策变量的线性规划问题之后，线性规划问题的适用领域更加广泛。从解决技术问题的最优化设计到工业、农业、商业、交通业、军事、经济安排和管理决策等领域都可以发挥作用，广泛应用于合理下料问题、生产组织与安排问题、运输问题、生产工艺优化等问题，单纯形法已经是现代科学管理的重要手段之一。信任随着科学技术的发展和日益完善，单纯形法在今后有更科学好用的发展。 单纯形法作为线性规划主要的算法已经得到广泛的应有。运用单纯形法求解线性规划时，要求有一个初始基可行解，假如没有明显的初始基可行解时，现在常用的方法是引进人工变量构造初始人造基，再利用两阶段法或者大M法进行迭代求解。但是，人工变量的引入使得方程组的变

3、量增加，进而使得计算工作量以及计算机的存储量大为增加，为此出现了许多基于高斯消元法求初始基的方法1-2，从而使得无需引入人工变量就可求解线性规划问题成为可能。 单纯形法的表格繁杂，每一步迭代都须要重新创建新的单纯行表，占据很大的内存，而且效率低下。今在改进单纯形法的基础上，对单纯形表进行改进，创建改进单纯形法的表上作业法，过程直观，计算简便，只需记住一些迭代公式就可驾驭其计算方法。引进参考文献中求解初始可行基的方法，更进一步的提高了改进单纯形法的计算效率，也缩减了数据所占据的内存量。 1.方法的引入 标准形式的线性规划问题： 这是线性规划问题的矩阵标准形式。对于式我们通过加入松弛变量变成等式。

4、 对于含有初始基的线性规划问题我们知道基变量的检验数肯定为0，我们可以不用计算，而且它们的系数矩阵肯定是单位矩阵，为此我们是否可以省略单位矩阵，从而简化单纯形表？ 下面就对本方法进行介绍。 2.方法的介绍 2.1 主要思想 单纯形表中基变量的系数矩阵肯定为单位矩阵，没有必要必需排列出来，省略掉基变量的系数矩阵可以简化单纯形表，使得迭代的过程不会过于繁琐，简化后的单纯形表。运用参考文献中的求解初始可行基的方法，不必引进人工变量即可求得初始可行基，进一步简化计算。 2.2 计算步骤 计算初始可行基，-Z 建立改进单纯形表 表1与单纯形表相像，只是对其进行了改进，下面是对表格的说明： 1）S行为第一

5、行，此行为单纯形表中检验数一行，为了计算便利我们将检验数行提到了上面。 2）S列为基变量列，我们定义为第一列。 3）其次列为价值系数列。 4）从第三列起先的各列为各个非基变量的系数列。 找寻迭代主元，进行迭代计算 与单纯形法找寻最好主元一样，初始改进单纯形表中已有，依据求解最大值线性规划问题的最大原则，确定迭代主元所在的列。价值系数列依次除以迭代主元所在的列中的大于0的各元素为，即：，确定出迭代主元。 在新的改进单纯形表中： 原主元所在的位置取原主元的倒数，即 原主元所在的行的其他元素取原表中该行对应元素与原主元的商，即： 原主元所在的列的其他元素取原主元素除原系数的商的相反数， 其他的各行各

6、列的元素，新元素=原元素-，即： 经过若干次的迭代，对于求最大值的线性规划问题，直到全部小于等于0，即第一行除-Z外其他元素全部小于等于0，结束计算，得到最优解。 求解最小化的线性规划问题，我们只需在目标函数两端同乘以-1，按上述方法进行迭代即可。 下面举例计算。 3.举例计算 此处我们应用参考文献12综合在一起的一种方法求解初始可行基，得到初始的单纯形表。应用初始的单纯形表求解。，为初始可行基，检验数肯定为0，我们就不再计算。 其次步：将上面的数据填入初始改进单纯形表，得到表2 第三步：确定迭代主元，进行迭代计算 在表2中，S行为行，依据单纯形法求解最大值问题原则，我们确定列为主元列。视察表

7、2知，只有行中0，所以我们可以不用计算值即可确定其为迭代主元。下面以为迭代主元进行迭代计算。 1）行中主元取其倒数，即； 2）行中的全部元素都除以2； 3）所在列中的全部元素除以主元后取其相反数，并填于新的迭代单纯形表中； 4）其余元素的计算，在此只举一个为例，其他的计算可仿照此方法依次算出。如行中的第一个元素，填入表3中作为新的b2。 计算出其余元素，填入新表即得表3，仿照表3的计算步骤得到表4。 S行所对应的已全为负数，计算结束，得到最优解，最优值为。 4.结论 本方法综合运用了参考文献12中的求初始可行基的方法，无需引进人工变量即可获得初始可行基，相对于两阶段法或大M法计算量小而且简单操

8、作，算法简便，改进单纯形表的运用实现了改进单纯形法的表上作业法，降低了改进单纯形法的困难度，过程直观，对于不是很熟识改进单纯形法的人来说也可以计算求解。改进单纯形法的表上作业法本质上是单纯形表的变形，所以本方法可以应用到单纯形表的计算过程中，使得求解线性规划问题更加简洁便利。 参考文献 1吕林霞，茹少锋，申卯兴.线性规划模型的单纯想法初始可行基选择探讨J.西北高校学报，2022，41. 2金涛，刘三阳，孙小军.一种线性规划问题单纯形法的改进算法J.宝鸡文理学院学报，2022，27：278. 3教材编写组.运筹学M.北京：清华高校出版社. 第6页 共6页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页