线性规划的教学模式探讨

苗连英　逄世友

摘要：线性规划是运筹学的核心内容，求解线性规划的单纯形法在理论上已趋于成熟，应用也越来越广泛。为了使学生更容易、更深刻地理解这种算法及其理论基础，本文给出了一种循序渐进的教学模式。这种模式也适用于运筹学其他内容的教学。

关键词：单纯形法；循序渐进；教学模式

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2014）45-0036-04

运筹学是二战期间发展起来的一门应用学科，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的一些问题，为决策者选择最优策略提供定量依据，其内容包括：规划论（线性规划、非线性规划、整数规划、动态规划、多目标规划等）、图论与网络分析、对策论、排队论、存储论、决策论、排序与统筹方法等[1]。运筹学的实际应用涉及生产计划、运输问题、人事管理、库存管理、市场营销、财务和会计等方面。另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价、工程优化设计、环境保护等问题中。据统计，50%数学建模问题与运筹学内容相关，可以用运筹学的方法解决。另外，为各大高校数次争得荣誉的建模队伍，长期以来一直接受运筹学相关知识的培训。

运筹学中最主要的分支是线性规划。线性规划模型是前苏联著名经济学家康托罗维奇于1939年提出的，这一重大发现使他获得了诺贝尔经济学奖。1947年G.B.Dantzig提出求解线性规划的单纯形法。针对退化问题，1952年A.Charner和W.W.Cooper[2]给出了摄动法，1954年G.B.Dantzig，A.Orden和P.Wolfe[3]提出了字典序方法，1976年G.G.Bland[4]提出了Bland法则，这些方法都能避免循环发生。线性规划理论上已趋于成熟，应用也越来越广泛。事实上，运筹学中许多问题都可以或需要用线性规划模型来描述或近似地描述，如运输问题——求解运输问题的表上作业法本质上就是单纯形法，并且这种方法充分展示了单纯形法的魅力。求最短路、最小费用最大流的问题都可以用线性规划模型来解决。求解指派问题的匈牙利法本质上也是单纯形法[5]。矩阵对策问题最后转化成求解线性规划。学习运筹学的先修课程主要有线性代数、微积分、概率论与数理统计。事实上，运筹学不仅应用了这些学科，也从理论上进一步发展了这些学科。

单纯形法是建立在一系列理论基础之上的。首先，如果线性规划的可行域非空，则它是一个凸集，这个结论很容易证明。线性规划的可行域的顶点与基可行解之间是一一对应的，所以其顶点个数有限，这个结论与单纯形法的关系不大，其证明可以省略。其次，线性规划若有可行解，则一定有基可行解，这个结论是很重要的，为了更好地理解它的证明，我们先看下面的例子。

进一步讲，若线性规划有最优解，其最优解一定可以在其可行域的顶点上找到，也就是在其基可行解中找到，这样就把一个从无限个可行解中找最优转化成在有限个可行解中找最优。这是单纯形法的理论基础。为了更好地理解这一重要结论的证明，我们看下一个例子。

X2的正分量的个数是2。由于P2，P4线性无关，所以X2是基可行解。这样我们就找到了一个最优解也是基可行解。一般地，若X2的正分量对应的系数列与线性相关，继续上述过程，直到找到基可行解为止。

从基可行解中找最优解所用的方法是单纯形迭代法。那么，如何判断一个线性规划是否有最优解？如何判断一个基可行解是否是最优解？在一个基可行解不是最优的情况下如何迭代到下一个与其相邻的更好的基可行解？为回答这些问题，我们举例说明。

先讲特例再引入最优性判别定理、基可行解的改进定理以及单纯形法的迭代步骤，学生就容易理解。即使针对有些专业的学生讲解这些定理的证明，也容易接受。

总之，现代社会信息量大，大学生需要学习的课程很多，用于预习或复习的时间就很少，这样上课时间就尤为珍贵，教师应该如何讲，才能使学生当堂听明白所授内容，这是一个必须思考的问题。其实，运筹学这门学科更侧重的是应用，数学理论并不难，之所以有人觉得难学，是因为没有把握一种好的学习方法。本文针对单纯形法给出了一种循序渐进的教学模式，实践证明这种模式能使学生更容易的理解课堂内容，有利于激发学生的自信心和学习兴趣，使学生在轻松掌握数学理论的基础上，能更好地探讨运筹学的经典案例的建模和求解，加强学生运用所学知识解决实际问题的能力和创新能力。

参考文献：

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

[2]Charnes，A.And Cooper W.W.，The stepping stone method of explaining linear programming calculations in thansportation problems，Management Science，1954，（1）：49-69.

[3]Dantzig，G.B.，Orden.A.and Wolfe.P.，Note on linear programming，Pacific J.Math.1955，（5）：183-195.

[4]Bland，G.G.，New finite pivoting rules of Simplex method，Math.Of Operations Research，1977，（2）：103-107.

[5]Hamdy，A.Taha，Operations Research-An Introduction[M].北京：人民邮电出版社，2007.

基金项目：2014年度江苏省研究生教育教学改革研究与实践课题，《运筹学》立体化教学平台建设；2014年中国矿业大学精品资源共享课：《运筹学》

作者简介：苗连英（1966-），女，中国矿业大学理学院教授，主要从事运筹学教学和科研工作。