用单纯形法求解下列线性规划问题 线性规划单纯形法教学策略探求

摘    要：运筹学中的线性规划使用日广。文章从高职院校线性规划教材与教育现状动身，提出了改善线性规划单纯形法教育的新策略。

要害词：高职院校;线性规划;单纯形法

中图分类号：G642.0          文献标识码：A          文章编号：1002-4107（2015）12-0030-02

运筹学是使用数学的一个分支，是研讨怎么将出产日子、军事办理等事情中呈现的一些问题加以提炼，然后使用数学办法进行处理的学科。主要是使用高级数学、线性代数等数学常识来处理问题，使本钱最小化和赢利最大化。是高级院校中经济和办理系学生的必修课。线性规划是运筹学的一个重要分支。1947年丹捷格（G.B.Dantzig）提出了解线性规划问题的一种有用办法——单纯形法，线性规划在理论上日益老练，在实践使用中愈加广泛与深化。特别是在核算机能处理不计其数个束缚条件和决议计划变量的线性规划问题之后，线性规划的适用范畴愈加广泛。从处理一些技术问题的最优化规划，到工业、农业、商业、交通运输业、军事、经济计划和办理决议计划等范畴都可以发挥重要作用。

线性规划使用日益广泛。高职高专职业院校的许多专业都将这一运筹学根本内容归入教育计划。可是线性规划是一种数学办法，触及高维空间。这些专业的本科生、大专生，即使学过线性代数，往往仍比较陌生，不能灵活运用线性代数常识体会线性规划内容。他们觉得线性规划理论笼统难明。部分学生乃至失掉学习决心。另一方面，许多教材把线性规划组织在线性代数后边，有作为线性代数使用举例的意图，若前后教育规划照应欠好，这一组织也将失败。

笔者等应邀为高职高专院校编写线性规划新教材[1]，在教材中怎么表现从此类学生数学根底的现状动身？怎么形象化地解说线性规划原理？怎么与他们学过的线性代数照应？怎么跟着年代脚步，更新教材[2]？——这些问题就说到笔者的面前。

针对高职高专院校学生的状况，笔者提出“夯实理论根底，抓好建模、上机两个实践身手”。在“夯实理论根底”方面，主要是依据经济、办理事务需求，针对学生实践的数学根底，加强与他们学过的线性代数相关常识的联络，在形象化的解说上下大力气。改动一些概念的提法，使学生感到通俗易懂，在寻求概念正确的前提下力求内容解说形象生动，选用核算机画图并结合动画演示等手法给学生以理性认识。使线性规划的理论部分变得简单承受。在线性规划标题的核算方面，削减笔算，添加机算，下降学生核算的难度，进步核算功率，增强学生学习的自决心。此外，针对线性规划教育和教材中需求留意的一些不确切的表述，笔者提出了一些见地，期望协助学生对常识的透彻了解，也可与同行沟通。在课后习题的设置方面，笔者也作了讨论，请参阅文章《编写线性规划习题的新构思》[3]，在教育中为了更好地培育学生的着手才干，笔者写了《线性规划教育中怎么培育学生的着手才干》一文，在此均不再赘述[4]。

一、用“自在变量改称非基变量”的提法，破除“基”的神秘感

现在线性规划教材的用语是跟着运筹学的几本大部头作品走的。而威望作品的用语，一方面受早年开创性论文词汇的影响，有些术语今已改译;另一方面威望作品比较艰深，假定读者关于线性代数中的相关根底理论常识均已熟练把握。可是实践上职业院校的运筹学教材大多只讲到线性方程组的求解，往往未将上述根底理论悉数列入纲要，单个概念即使说到，顶多也是草草带过。这就形成在职业院校的运筹学的许多教材中，线性规划的许多术语学生感到陌生、笼统，或与曾经学过的线性代数对不上号。

许多线性规划教材一开始就重整旗鼓，用学生不了解的术语下“基”的界说，举例又很简略。学生用不上刚学的线性代数，致使对“基”的概念懵懂，云遮雾罩，往往全凭死记，也就更谈不上了解“换基”等等内容。

笔者为防止使职业院校的学生感到突兀，从他们了解的线性方程组求解常识下手，指出束缚方程的增广矩阵化成行最简形矩阵后所得同解方程和相应的通解，实质上就是“用自在变量表达非自在变量”。按线性规划的术语，称作“用非基变量表达基变量”。不过是把“自在变量”改称“非基变量”;把“非自在变量”改称“基变量”算了。再由“基变量”引进“基”的概念，由此破除“基”的神秘感。再使用他们会的通过“行初等变换”，在增广矩阵系数矩阵中化出单位阵的常识，讲“基”的性质等内容。这样，学生就会很简单了解。

学生简单知道：写线性方程组的通解时，最易手到拈来的是“悉数自在变量皆取零值的特解”，这个“特解”在线性规划里叫作“悉数非基变量皆取零值”。并指出这个特解在线性规划里更重要，特意命名“根本解”。若“根本解” 还契合非负条件，就成为“根本可行解” （Basic feasible solution），它与图解法中至关重要的可行解域的极点有对应联络。这样引进新概念，学生感到轻松天然。连差生也能顺利地由上章常识过渡到本章的新概念。

二、合理运用多种教育手法，增强学生的理性认识

由于线性规划单纯形法比较笼统，许多要害点学生不简单了解，对一些常识的了解比较含糊，为了使学生对解法有明晰理性的了解，笔者想到使用二维图形、对照极点表及图象和动画演示等手法，到达较好的教育效果。

（一）用二维图形显现“根本可行解”与可行解域极点的对应联络

因学时束缚，职业院校的运筹学教材不作证明，仅介绍“根本可行解”与可行解域极点的对应联络定论。许多教材一笔带过，学生形象不深。笔者加写一个二维例图让学生验看，增加理性认识。还把该例的对应联络，包含决议计划变量与张弛变量的值等，具体列出表格，供后边讲“换基”时查验。尽管费些翰墨，因事关单纯形法只到各个极点查找最优解的根本思路，仍是值得的。

（二）在二维图上验看可行解域极点上的确“悉数非基变量等于零”

在以往教育中，常有学生对悉数非基变量在每个可行解域的极点都取零值感到疑问。笔者除了指出代数上的“根本可行解”与几许上的可行解域极点有对应联络外，还从几许视点在二维图上阐明该例中各个非基变量等于零的几许意义：在坐标轴线上的极点，它的另一个坐标的值为零，其意义为非负条件;在其他边线上的极点，束缚方程的张弛变量为零，标明至此已踩该束缚条件的边线。例如二维图解法中，在表明不等式束缚x1+x2≤6的边线上，由它标准化所得的等式束缚x1+x2+x3=6中的张弛变量x3为零。以此协助学生承受高维空间也有相似规则的定论。

   （三）对照极点表及图象导出“换基”的理性认识

在从代数学视点讲“换基”的过程中，笔者还让学生调查上述可行解域极点与“根本可行解”对照表中极点间各变量值的改变，结合“非基变量必取零值”，自己总结得出“换基”的规则。学生感到生动了解。

   （四）用动画归纳单纯形法的思路

在讲完单纯形法的思路后，笔者放映一个二变量线性规划题求最优解的动画，以动态形象的动画演示，使学生直观地了解单纯形法的解题思路，以加深学生对此解法的形象，稳固学习效果。

   三、削减笔算法的辅佐内容，展开机算

实践工作中遇到的线性规划问题，必定变量许多（往往十个以上）且有用数字长，核算量太大。许多学生面临实践问题，凭笔算解不出来，只能无可奈何。身处核算机年代，而沿袭几十年前的老教法，只教笔算内容，或虽点到某处刊有源程序，却不上机，这是国内经济办理类专业线性规划教育中适当遍及的现状。为使学生真实具有处理实践问题的才干，笔者痛感有必要把握一种软件。有所失才干有所得，为挤出时刻上机，有必要舍弃一些原有内容。一般教材在讲完单纯形法的表上求解后，还要讲一种求初始根本可行解的办法，一般是“辅佐规划法”。笔者考虑这部分与单纯形法骨干内容的联络相对而言小些，只好割爱。何况实践工作中，用核算机解题，不需求供给初始可行解。即使偶遇简易笔算场合，由于新讲稿中加强了与上章的联络，真实看懂新教材的学生，从引进基变量概念的例题中，也会悟出对增广矩阵作行初等变换，查找出一个根本可行解，绘出首张单纯形表，供表上叠代求解用。所以删去这部分内容影响不算太大。这样节省出使用核算机解题的时刻，使学生使用上机解题，进步学习功率。

   四、留意言语的准确性

线性规划是运筹学中最活泼的分支，经济类、办理类专业学生及从业人士遍及学习。现在商场出售的线性规划书本许多，但在教育和教材中都有一些需求留意的问题。

讲课中不能由于着重形象风趣而忽视科学性。在职业院校的运筹学课堂上，虽无理工科那么多证明，相同要在要害当地，咬文嚼字，锻炼用语。在线性规划的教材中就有若干常见的语病。例如单个书说“基的个数为组合数Cmn”（其间m为标准化后的束缚方程数，n为变量数，且R（A）=m ）。这句话就漏掉“至多”二字，由于有的m阶方阵的行列式可能为零，因此不能作基。

总归，线性规划单纯形法是一种较为笼统的数学办法，通过改善教育办法，选用上述讲法，学生对该部分的学习遍及承受较好。

参考文献：

[1]阎章杭等.高级数学与经济数学[M].北京：化学工业出

版社，2007：250-262.

[2]阎章杭等.高级数学与经济数学[M].北京：化学工业出

版社，2003：276-281.

[3]阎向曜，张小慧.编写线性规划习题的新构思[J].河南

财务税务高级专科学校学报，2008，（6）.

[4]张小慧.线性规划教育中怎么培育学生的着手才干[J].

社科纵横，2009，（3）.