运筹学课程中单纯形法教学的几点思考*

孙 祥 凯

(重庆工商大学 数学与统计学院，重庆 400067)

运筹学课程中单纯形法教学的几点思考*

孙 祥 凯

(重庆工商大学 数学与统计学院，重庆 400067)

线性规划问题的单纯形法一直是运筹学课程教学的重点和难点，通过对线性规划问题单纯形法计算原理的分析和研究，指出了线性规划问题的单纯形法思想与运输问题的表上作业法以及目标规划问题的单纯形法之间的区别与联系，给出了一种求解目标规划问题的更简便方法；教学实践证明这些方法更能够加深学生对单纯形法的算法逻辑的认识和理解。

线性规划；单纯形法；运输问题；目标规划；教学改革

运筹学是20世纪新兴的一门应用学科，它能够帮助决策者解决那些可以用定量方法和相关理论方法来处理的问题。它在诸如经济规划、计划管理、金融决策、能源开发、工程设计、农业种植、卫生保健以及军事科学等领域有着重要的应用。不仅如此，运筹学问题也常常涉及经济学、对策论、系统工程和控制论等学科的研究领域[1-6]。作为运筹学的一个重要分支，线性规划的应用极其广泛，其作用已为越来越多的人所重视。特别是美国数学家G.B. Dantzig在1947年提出了求解一般线性规划问题的求解方法，即单纯形法之后，线性规划在理论上更进一步趋于成熟。至今，单纯形法仍然是行之有效且被广泛应用的求解线性规划问题的方法。除此之外，单纯形法在运筹学中的运输问题以及目标规划问题中也有着十分重要的作用。因此深入理解单纯形法的基本思想以及求解步骤，对运筹学后续学习有着十分重要的作用。

本文主要从单纯形法的基本思想出发，进一步阐述单纯形法的求解步骤，同时分别比较求解运输问题的表上作业法以及求解目标规划问题的单纯形法与线性规划问题的单纯形法之间的区别与联系。不仅加深了学生对单纯形法的理解和认识，而且增强了学生对运筹学学习的兴趣。

1 单纯形法的基本思想及其直观理解

线性规划问题的所有可行解构成的集合(即可行域)是凸集，它们有有限个顶点，并且其最优值如果存在必在该凸集的某顶点处达到。这里顶点所对应的可行解，称为基本可行解。单纯形法是解线性规划的一种传统而且有效的方法，其基本思想[1，2]：先找出一个基本可行解，对它进行判断，看是否是最优解；若不是，则按照一定法则转换到另一个使目标函数能增加的基本可行解，重复这一迭代过程，直到求得问题最优解。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。

在学习单纯形法求解线性规划时，我们首先需要十分清楚单纯形表中的相关概念及其直观的图形解释。例如，线性规划问题的基可行解实际上就是其可行域的顶点，所谓的单纯形实际上指的是一维空间中的线段、二维空间中的三角形，三维空间中的四面体以及n维空间中的含有n+1顶点的多面体。其次，也要善于将单纯形法每一步所得结果与线性规划问题的图解法做一个比较，进一步的理解其几何意义。这样，学生不仅可以很容易的理解单纯形法的含义，而且对单纯形法的后续学习也有一个良好的铺垫。

2 单纯形法的求解步骤及注意事项

由上一节所介绍的单纯形法基本思想可知，首先在线性规划问题的系数矩阵中构造一个单位矩阵作为初始可行基，然后逐步进行迭代，进而判断解的类型以及解的存在与否，最终找到最优解。为了学生在学习中能够对单纯形法有一个更加简洁明了、深刻的理解，下面进一步阐述单纯形法的求解步骤。给定一个线性规划问题(此处假定是对目标函数求最大的线性规划问题)，用单纯形法对其求解，具体步骤如下：

(1) 确定初始基可行解。首先找出初始基矩阵，通常选取系数矩阵中的单位方阵为初始基矩阵。然后选取初始基矩阵对应的变量为初始基变量，剩余的变量为非基变量。最后只需令非基变量为零，则就可以得到一组初始基可行解。

(2) 最优检验。首先求解非基变量的检验数(基变量的检验数无需求解，都为零)。若非基变量的检验数全为负数，则达到最优解，停止计算。若存在某个检验数为正数，并且其对应的列向量为负，则此问题无界，停止计算。否则进行下一步。

(3) 迭代。确定换入变量以及换出变量，重新建立新的基矩阵，基变量以及非基变量，从而得到新的基可行解。按照上述步骤重新计算，直到找到最优解为止。

单纯形法的求解步骤思想十分简单，然而由于在求解过程中，需要列大量的单纯形表，计算量很大。若一个地方出错，整个计算就前功尽弃。所以在实际操作中，我们需要加强学生对单纯形法表的计算。这样不仅可以加深学生对单纯形法的理解，而且可以使得学生对单纯形表中的相关概念有更准确的把握。

3 运输问题的表上作业法

运输问题作为一类特殊的线性规划问题，其在现实世界中有着广泛的应用。目前求解运输问题的一种常用方法是表上作业法。表上作业法是单纯形法在求解运输问题的一种简化方法，其实质是单纯形法。但是两者之间在具体的计算和术语上有一定的差别。为了让读者对表上作业法有更清晰的认识和理解。将表上作业法的几点注意事项归纳如下：

(1) 确定运输问题的初始基可行解，求出运输问题的初始调运方案。运输问题的初始基可行解是在(m×n)产销平衡表上给出m+n-1个数字格。通常的方法有最小元素法和伏格尔法。

(2) 求解运输问题非基变量的检验数，就是求解产销平衡表上空格的检验数。然后进行最优判定。通常求解检验数的方法有闭回路法和位势法。此处要特别的注意，前面所阐述的线性规划问题都假定目标函数实现最大化，而运输问题的目标函数是要求实现最小化，故此时我们要保证所有的检验数不小于零。

(3) 在利用表上作业法求解计算时，一定要区分好何处利用表格中运量的数据、何处利用表格中运价的数据。例如在利用闭回路法求解检验数时，利用的是空格处的运价进行计算。而在利用闭回路调整法确定换入变量以及换出变量时，考虑的是相应基变量(数字格)处的运量。所有这些就需要我们深刻理解表上作业法的本质含义。

4 目标规划问题的单纯形法及其直接求解方法

目标规划是目前处理多个目标决策的一种方法。它是针对线性规划目标单一的局限性而提出的，是线性规划的应用的进一步拓展，也是解决现实实际问题的一种行之有效的方法。由于目标规划的多个目标之间不仅有主次先后之分，而且有时会互相矛盾，相互制约。因此求解目标规划所用的单纯形法主要是利用了分层的思想，即在建立单纯形表时，需要对检验数行按照优先因子的个数分别列成多行，然后首先考虑第一个优先因子系数的正负，以此类推，直到求出最优解(满意解)为止。具体计算步骤可参考清华大学出版社出版的《运筹学》(本科版)教材[1]。

目前针对目标规划的单纯形法的计算过程，大多数教材是直接给出相应例题的单纯形表中检验数的取值，而具体的求解过程却没有。这对初学者就会造成一定的困惑，不知检验数是如何求出的。针对这一问题，借助一个例子给出求解目标规划问题的一种直接单纯形求解方法，并阐述了教材中检验数的求解过程。

例：试用单纯形法求解下述目标规划问题：

分析：由于目标规划问题的数学模型结构和线性规划问题的数学模型结构没有本质区别，所以按照求解线性规划问题的单纯形法进行求解。在求解过程中只需假设P1≫P2≫P3即可。当然如果目标函数中含有K个优先因子，只需假设P1≫P2≫…≫PK即可。只有这样假设，才能保证在计算过程中按照优先因子的先后顺序来考虑。

表1 初始单纯形表

表2 最终单纯形表

表2的检验数全为正数，所以目标规划问题达到满意解。满意解为(2，4，3)。通过上述解法不难发现：由于目标规划问题的数学模型结构和线性规划问题的数学模型结构没有本质区别，所以可以完全按照求解线性规划问题的单纯形法进行求解目标规划问题，并且求解更加方便易懂。通过观察教材上关于目标规划单纯形表中的检验数行，容易发现其检验数行P1，P2，P3对应的数字实际上就是表1以及表2中所得检验数行的P1，P2，P3的系数。

5 结束语

作为运筹学的一个重要分支，线性规划问题已经广泛应用到工业、商业、农业、交通运输业等各个领域。而单纯形法作为求解线性规划问题模型的一种行之有效的方法，其可以广泛应用到求解运输问题以及目标规划问题等模型中。因此深刻理解线性规划问题单纯形法的基本原理以及解题思路对运筹学相关问题模型的求解，特别是运输问题以及目标规划问题的求解有着十分重要的作用。本文通过对线性规划单纯形法的进一步阐述，阐明了单纯形法在运筹学课程中各种问题模型求解术语的区别与联系，加深了学生对运筹学相关问题的的求解方法和原理，消除了学生对各种问题模型中单纯形法求解的困惑。

[1] 《运筹学》教材编写组．运筹学[M]．本科版．北京：清华大学出版社，2005

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

[3] 杨盛昌. 目标规划问题的建模方法探析[J]. 云南民族学院学报：自然科学版，2001，10(2)： 351-355

[4] 褚淑贞. 运筹学课程教学模式确定[J]. 教学教育，2003(3)： 38-39

[5] 张杰，郭丽杰. 运筹学课程的改革与数学建模教育[J]. 高等数学研究，2007(1)： 103-105

[6] 陈修素，丁宣浩，陈义安. 基于创新能力培养的《运筹学》课程改革与数学建模实践[J]. 计算数学，2012，22(2)： 109-113

Keywords：linear programming；simplex method；transportation problem；objective programming；teaching reform

Several Ideas on Simplex Method Teaching in Operational Research Courses

SUNXiang-kai

(School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067, China)

The simplex method of linear programming problem has been the important point and the difficult point in the teaching of operational research courses, through the analysis and study of calculation principle of simplex method of linear programming problem, the difference and association between the table dispatching method of simplex method ideas and transportation issue of linear programming problem and the simplex method of objective programming problem are pointed out, especially a kind of more simple method for solving objective programming problem is given. Teaching practice verifies that these methods can better deepen the understanding of calculation logic of the simplex method by the students.

1672-058X(2013)10-0091-05

2013-03-13；

2013-04-25.

国家自然科学基金(11171362和11201509)；重庆市自然科学基金(cstc2012jjA00033).

孙祥凯(1984-)，男，山东青州人，在站博士后，讲师，从事最优化理论与应用的研究.

G521

A

责任编辑：代小红