鲁达 作者：臧永森
清华大学工业工程系在读博士生，研究方向:运筹优化算法设计与应用、数据统计分析、大数据技术与应用，戚铭尧老师团队
编者按：此文属于电子书线性规划专题第三章单纯形法的内容。单纯形法是求解线性规划问题的有效算法。在具体介绍单纯形法之前，我们需要先认识求解线性规划问题中的两组重要概念：（1）可行域与最优解；（2）基变量与基可行解。
单纯形法由美国数学家George Bernard Dantzig在1947年担任美国空军司令部数学顾问时提出，旨在解决空军军事规划问题，之后成为解决线性规划问题比较通用的有效算法。 在具体介绍单纯形法之前，我们需要先来认识求解线性规划问题中的两组重要概念：（1）可行域与最优解；（2）基变量与基可行解。
可行域与最优解
谈线性规划问题目的就是要进行求解获取最优解，要理解最优解就不得不提可行域，可行域和最优解是线性规划问题中最为重要的两个概念。
线性规划问题的可行域指的是满足线性规划问题所有约束条件（包含符号约束等各种约束）的所有点的集合，每个点叫做可行解。最优解是指可行域中使得目标函数取得最小值（对于最小化问题）或最大值（对于最大化问题）的某一个或某些点，相应的函数值就是最优值。
用一个比较生动的例子来解释上述两个概念：假设某个周末小明来到采摘园享受轻松时光，采摘园有三块相邻的采摘区，分别属于三家农户：老张、老李、老王，老张种植草莓，老李种植的西瓜，老王则种植了葡萄，虽然三块采摘区相邻，但三家农户分别做自己的生意互不相往来。小明决定到老李家采摘西瓜，老李做生意的规定是：每位顾客只能进入园区一次，只能吃或者带走一个西瓜，进入园区的门票是20元人民币。
当小明进入老李的西瓜园区后，就可以来分析我们的可行域和最优解了。虽然老李家的西瓜园区与隔壁的草莓园区、葡萄园区相邻，但是小明是不可以进入草莓园区和葡萄园区进行采摘的，因为他买的是老李家的门票，而草莓园区和葡萄园区不属于老李，如果进入草莓园区或者葡萄园区，老张或者老王就要找小明或者老李讨说法了。也就是说，小明只能在西瓜园区进行采摘，那么西瓜园区就是小明的采摘范围，这个采摘范围就可以看成是小明活动的可行域。
那最优解对于小明来说是啥呢？小明花了20元钱进入采摘园，老李规定他只能享用一个西瓜，那么正常情况下小明会选择一个最大又最熟的西瓜来吃或者带走，这样才会使得进入园区的利益最大化，也就是我们俗话说的“对得起那20块钱”。而西瓜园区内成百上千个西瓜都是小明可以选择的，这些可以选择的西瓜可以看成是小明的可行解，而最大的最熟的那个就是最优解。当然，如何从所有西瓜中找到最大最熟的那一个，就是如何求解线性规划问题的研究范围了。
把上述场景简化并抽象到坐标系中，就是一个简单的线性规划问题模型，令x、y分别代表采摘园区的长度和宽度，水果在园区的位置对应相应的坐标点，假设西瓜大小与成熟度和坐标点存在某种线性关系，那么模型可以粗略表示如下图1所示：
图1 可行域与最优解通俗粗略解释图示
把上述例子继续抽象简化，将其设计为精确的线性规划问题，可以抽象为如下模型：
画出上述模型的图示，如图2所示，其中蓝色填充区域为该模型的可行域，红色直线表示模型的目标函数，绿色剪头表示红线向上移动能够使得目标函数值增大，移动的过程中不能超出可行域（蓝色区域），因此能够使目标函数取得最大值的点，就是黑色标注点（12,6），这一点就是该模型的最优解，相应的最优值为z =x+y=12+6=18。
图2 可行域与最优解精确模型解释图示
基变量与基可行解
除了上述两个概念，在线性规划问题的单纯形法求解过程中，还绕不开基变量和基可行解两个重要概念，下面通过线性方程组的知识引入这两个概念。
考虑n个变量、m个线性方程所构建的方程组
，假设n≥m且A有m×m的满秩子矩阵（该子矩阵称为基），令n-m个变量等于0，然后根据克莱姆法则可知能够求出满足
的其余m个变量的唯一值。此时这n-m个变量就是非基变量，其余m个变量就是基变量。而由上述基变量和非基变量组成的变量叫做基解。
考虑由
组成的线性规划模型：
如果上述讨论的线性方程组
的基解满足线性规划模型中的符号约束（3），那么它就是基可行解。
在上述分析中，我们是任意令n-m个变量为0，这也就意味着，n-m个变量的选择是具有不确定性的，基于此求得的基变量就不同，也就是说在解的集合中会出现不同的非基变量与基变量组合而成的基解。
下面我们通过一个简单的例子[1]来理解上述概念，考虑下述线性规划问题：
该线性规划问题涉及的线性方程组
中的A为3×5的矩阵
，容易看出矩阵
是线性规划问题的一个满秩矩阵，因此该矩阵的秩为3，令5-3=2个变量等于0，任意取
（这里的任意是指在保证满足方程组本身方程等式的条件下取值，比如我们不能取
，因为这样就违背了方程
），此时求解
可以求得
，对应的列向量组成的矩阵
是线性规划问题的一个基，其中的三个列向量均称为基向量，与其对应的
就是基变量，而
就是非基变量。它们组成的变量
叫做基解，此时
不满足线性规划的约束
，因此该基解不是基可行解。
为了帮助读者更好地理解基可行解的概念，我们再考虑任意令
，此时求
解可以求得
，那么
就组成了基变量，而
就是非基变量，它们的组合
就是基解，同时基解满足
，因此该基解也就是基可行解。其实还可以验证，没有其它基可行解对应的目标函数值大于该基可行解对应的函数值，即该基可行解为该线性规划的最优解，将其带入线性规划的目标函数可得最优值为
。
为了更加清晰地表示基解和基可行解以及可行解之间的关系，将上述线性规划的全部基解以及部分可行解列于表1：
表1 上述例题的基解与基可行解以及可行解之间的关系表
从上表可以很清晰地看出，可行解可能是基解，也可能是非基解，可行解中的基解便是基可行解；基解中包含可行解和非可行解，基解中的可行解就是基可行解。因此，基可行解必须同时是可行解和基解。
此文是电子书线性规划专题的约稿文。该篇给接下来介绍单纯形法做了个简单铺垫，我们后面会陆续推出与单纯形法相关的内容，希望大家继续关注【优化】板块，电子书线性规划专题的科普文。
参考文献
[1]胡运权，郭耀煌，《运筹学教程（第三版）》，清华大学出版社，P19—20.