探讨单纯形法的改进

李丰兵

摘  要：该文对线性规划单纯形法进行改进探讨，提出一种构造初始可行基矩阵的新方法。该方法通过对单纯形表进行某种初等行变换，逐步构造出初始可行基矩阵，从而避免了增加人工变量及构造辅助问题，因此，比人工变量法计算更简单。实例计算表明，该方法切实可行。

关键词：线性规划  单纯形法  人工变量法  初始可行基

中图分类号：O221.1   文献标识码：A           文章编号：1672-3791（2019）05（a）-0194-02

Abstract： In this paper， the simplex method of linear programming is improved and a new method of constructing initial feasible basis matrix is proposed. According to some rules， this method use elementary row transformation of simplex table step by step to construct the initial feasible basis matrix， and thus avoid the problem of adding artificial variables and constructing auxiliary problem. Therefore， this method is simpler than the artificial variable method. The calculation example shows that this method is feasible.

Key Words： Linear programming; Simplex method; Artificial variable method; Initial feasible basis

单纯形法是求解线性规划问题的基本方法，是运筹学及最优化方法领域的一个重要研究内容，目前，国内外已存在诸多与单纯形法密切相关的研究工作[1-3]。单纯形法包括原始单纯形法、两阶段法、大M法及对偶单纯形法等。其中，原始单纯形法又是最基本、最简单的一种算法，它以线性规划标准型系数矩阵中的单位阵作为初始可行基，条件过于苛刻。人工变量法（即两阶段法和大M法）通过引入人工变量及构造辅助问题，并由此构造出单位阵作为初始可行基矩阵，很好地解决了原始单纯形法的上述缺陷，但是人工变量法因为引入了人工变量，故增大了决策空间的维数及求解问题的规模，使得计算变得更加复杂。此外，大M法中的参数M的取值没有确定的方式，在计算机上实现比较困难。

1  单纯形法的改进

针对单纯形法的上述缺陷，该文对其进行改进，提出一种新的初始可行基的构造方法，其思想是按照某种规则对单纯形表实施转轴运算（某种初等行变换），“分步”选择出初始基变量。该法克服了原始单纯形法依赖于标准型中单位阵的缺陷，同时又不用引入人工变量和构造辅助问题，其详细步骤如下。

其中y1、y2为人工变量。显然，引入人工变量后，决策空间的维数增大了，由原来的5维变成了7维，这将导致计算过程变得更加复杂，实际计算过程比该文提出的改进方法要复杂多了。该文提出的方法不仅仅适用于上述问题（2），经验证对其他原始单纯形法无法求解的标准型（1），该文方法照样可行，由于篇幅限制，不再介绍其他实例的计算过程。

2  结语

该文对单纯形法进行了改进探讨，在原始单纯形法的基础上提出了一种仅通过对单纯形表“逐步”实施转轴运算就能构造出初始可行基的方法。该方法改善了原始单纯形法依赖单位阵作为初始可行基的不足，同时又没有引入人工变量和构造辅助问题，因此比人工变量法计算更简单。从诸多实例计算结果可知，该方法确实可行。尽管如此，该方法仍需进一步研究，特别是理论上仍需完善。

参考文献

[1] 赵旭芳，梁昔明，龙文.基于最优个体指导单纯形法改进的人工蜂群算法及应用[J].计算机应用与软件，2019（2）：44-51，92.

[2] 王梦娜，王秋萍，王晓峰.基于Iterative映射和单纯形法的改进灰狼优化算法[J].计算机应用，2018，38（S2）：16-20，54.

[3] 吴卓然.基于改进单纯形法的冗余证券的判别[J].金融经济，2016（16）：143-145.

[4] 熊伟.运筹学[M].北京：机械工业出版社，2008.

[5] 胡運权.运筹学基础及应用[M].北京：高等教育出版社，2008.