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

改进单纯形法的简易算法研究 【摘要】改进单纯形法的每一步都须要求解基矩阵的逆矩阵，而且与单纯形法不同的是，求解逆矩阵使得其不能运用表上作业法，求解过程繁琐、冗长，不易理解，且不行在计算机上干脆求解。本文提出改进单纯形法的表上作业法，且对于初始可行基的求解方法进行改进，使得其可以在计算机上进行，过程直观，计算简便，较两阶段法以及大M法计算量少，数据所占据的内存量要少的多。 【关键词】单纯形法；改进单纯形表；迭代 线性规划问题是运筹学的一个重要的分支，自1947年丹捷格提出了一般线性规划问题的求解方法单纯形法后，线性规划在理论上趋于成熟，在好用中日益广泛和深化。尤其是在电子计算机能处理成千万个约束条件和决策变量的线性规划问题之后，线性规划问题的适用领域更加广泛。从解决技术问题的最优化设计到工业、农业、商业、交通业、军事、经济安排和管理决策等领域都可以发挥作用，广泛应用于合理下料问题、生产组织与安排问题、运输问题、生产工艺优化等问题，单纯形法已经是现代科学管理的重要手段之一。信任随着科学技术的发展和日益完善，单纯形法在今后有更科学好用的发展。 单纯形法作为线性规划主要的算法已经得到广泛的应有。运用单纯形法求解线性规划时，要求有一个初始基可行解，假如没有明显的初始基可行解时，现在常用的方法是引进人工变量构造初始人造基，再利用两阶段法或者大M法进行迭代求解。但是，人工变量的引入使得方程组的变量增加，进而使得计算工作量以及计算机的存储量大为增加，为此出现了许多基于高斯消元法求初始基的方法1-2，从而使得无需引入人工变量就可求解线性规划问题成为可能。 单纯形法的表格繁杂，每一步迭代都须要重新创建新的单纯行表，占据很大的内存，而且效率低下。今在改进单纯形法的基础上，对单纯形表进行改进，创建改进单纯形法的表上作业法，过程直观，计算简便，只需记住一些迭代公式就可驾驭其计算方法。引进参考文献中求解初始可行基的方法，更进一步的提高了改进单纯形法的计算效率，也缩减了数据所占据的内存量。 1.方法的引入 标准形式的线性规划问题： 这是线性规划问题的矩阵标准形式。对于式我们通过加入松弛变量变成等式。 对于含有初始基的线性规划问题我们知道基变量的检验数肯定为0，我们可以不用计算，而且它们的系数矩阵肯定是单位矩阵，为此我们是否可以省略单位矩阵，从而简化单纯形表？ 下面就对本方法进行介绍。 2.方法的介绍 2.1 主要思想 单纯形表中基变量的系数矩阵肯定为单位矩阵，没有必要必需排列出来，省略掉基变量的系数矩阵可以简化单纯形表，使得迭代的过程不会过于繁琐，简化后的单纯形表。运用参考文献中的求解初始可行基的方法，不必引进人工变量即可求得初始可行基，进一步简化计算。 2.2 计算步骤 计算初始可行基，-Z 建立改进单纯形表 表1与单纯形表相像，只是对其进行了改进，下面是对表格的说明： 1）S行为第一行，此行为单纯形表中检验数一行，为了计算便利我们将检验数行提到了上面。 2）S列为基变量列，我们定义为第一列。 3）其次列为价值系数列。 4）从第三列起先的各列为各个非基变量的系数列。 找寻迭代主元，进行迭代计算 与单纯形法找寻最好主元一样，初始改进单纯形表中已有，依据求解最大值线性规划问题的最大原则，确定迭代主元所在的列。价值系数列依次除以迭代主元所在的列中的大于0的各元素为，即：，确定出迭代主元。 在新的改进单纯形表中： 原主元所在的位置取原主元的倒数，即 原主元所在的行的其他元素取原表中该行对应元素与原主元的商，即： 原主元所在的列的其他元素取原主元素除原系数的商的相反数， 其他的各行各列的元素，新元素=原元素-，即： 经过若干次的迭代，对于求最大值的线性规划问题，直到全部小于等于0，即第一行除-Z外其他元素全部小于等于0，结束计算，得到最优解。 求解最小化的线性规划问题，我们只需在目标函数两端同乘以-1，按上述方法进行迭代即可。 下面举例计算。 3.举例计算 此处我们应用参考文献12综合在一起的一种方法求解初始可行基，得到初始的单纯形表。应用初始的单纯形表求解。，为初始可行基，检验数肯定为0，我们就不再计算。 其次步：将上面的数据填入初始改进单纯形表，得到表2 第三步：确定迭代主元，进行迭代计算 在表2中，S行为行，依据单纯形法求解最大值问题原则，我们确定列为主元列。视察表2知，只有行中0，所以我们可以不用计算值即可确定其为迭代主元。下面以为迭代主元进行迭代计算。 1）行中主元取其倒数，即； 2）行中的全部元素都除以2； 3）所在列中的全部元素除以主元后取其相反数，并填于新的迭代单纯形表中； 4）其余元素的计算，在此只举一个为例，其他的计算可仿照此方法依次算出。如行中的第一个元素，填入表3中作为新的b2。 计算出其余元素，填入新表即得表3，仿照表3的计算步骤得到表4。 S行所对应的已全为负数，计算结束，得到最优解，最优值为。 4.结论 本方法综合运用了参考文献12中的求初始可行基的方法，无需引进人工变量即可获得初始可行基，相对于两阶段法或大M法计算量小而且简单操作，算法简便，改进单纯形表的运用实现了改进单纯形法的表上作业法，降低了改进单纯形法的困难度，过程直观，对于不是很熟识改进单纯形法的人来说也可以计算求解。改进单纯形法的表上作业法本质上是单纯形表的变形，所以本方法可以应用到单纯形表的计算过程中，使得求解线性规划问题更加简洁便利。 参考文献 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 页