如何用vb.net编程求解单纯型法

作者：臧永森

清华大学工业工程系在读博士生，研究方向:运筹优化算法设计与应用、数据统计分析、大数据技术与应用，戚铭尧老师团队

编者按：此文属于电子书线性规划专题第三章单纯形法的内容。单纯形法是求解线性规划问题的有效算法。在具体介绍单纯形法之前，我们需要先认识求解线性规划问题中的两组重要概念：（1）可行域与最优解；（2）基变量与基可行解。

单纯形法由美国数学家George Bernard Dantzig在1947年担任美国空军司令部数学顾问时提出，旨在解决空军军事规划问题，之后成为解决线性规划问题比较通用的有效算法。在具体介绍单纯形法之前，我们需要先来认识求解线性规划问题中的两组重要概念：（1）可行域与最优解；（2）基变量与基可行解。

可行域与最优解

谈线性规划问题目的就是要进行求解获取最优解，要理解最优解就不得不提可行域，可行域和最优解是线性规划问题中最为重要的两个概念。

线性规划问题的可行域指的是满足线性规划问题所有约束条件（包含符号约束等各种约束）的所有点的集合，每个点叫做可行解。最优解是指可行域中使得目标函数取得最小值（对于最小化问题）或最大值（对于最大化问题）的某一个或某些点，相应的函数值就是最优值。

用一个比较生动的例子来解释上述两个概念：假设某个周末小明来到采摘园享受轻松时光，采摘园有三块相邻的采摘区，分别属于三家农户：老张、老李、老王，老张种植草莓，老李种植的西瓜，老王则种植了葡萄，虽然三块采摘区相邻，但三家农户分别做自己的生意互不相往来。小明决定到老李家采摘西瓜，老李做生意的规定是：每位顾客只能进入园区一次，只能吃或者带走一个西瓜，进入园区的门票是20元人民币。

当小明进入老李的西瓜园区后，就可以来分析我们的可行域和最优解了。虽然老李家的西瓜园区与隔壁的草莓园区、葡萄园区相邻，但是小明是不可以进入草莓园区和葡萄园区进行采摘的，因为他买的是老李家的门票，而草莓园区和葡萄园区不属于老李，如果进入草莓园区或者葡萄园区，老张或者老王就要找小明或者老李讨说法了。也就是说，小明只能在西瓜园区进行采摘，那么西瓜园区就是小明的采摘范围，这个采摘范围就可以看成是小明活动的可行域。

那最优解对于小明来说是啥呢？小明花了20元钱进入采摘园，老李规定他只能享用一个西瓜，那么正常情况下小明会选择一个最大又最熟的西瓜来吃或者带走，这样才会使得进入园区的利益最大化，也就是我们俗话说的“对得起那20块钱”。而西瓜园区内成百上千个西瓜都是小明可以选择的，这些可以选择的西瓜可以看成是小明的可行解，而最大的最熟的那个就是最优解。当然，如何从所有西瓜中找到最大最熟的那一个，就是如何求解线性规划问题的研究范围了。

把上述场景简化并抽象到坐标系中，就是一个简单的线性规划问题模型，令x、y分别代表采摘园区的长度和宽度，水果在园区的位置对应相应的坐标点，假设西瓜大小与成熟度和坐标点存在某种线性关系，那么模型可以粗略表示如下图1所示：

图1 可行域与最优解通俗粗略解释图示

把上述例子继续抽象简化，将其设计为精确的线性规划问题，可以抽象为如下模型：

画出上述模型的图示，如图2所示，其中蓝色填充区域为该模型的可行域，红色直线表示模型的目标函数，绿色剪头表示红线向上移动能够使得目标函数值增大，移动的过程中不能超出可行域（蓝色区域），因此能够使目标函数取得最大值的点，就是黑色标注点（12,6），这一点就是该模型的最优解，相应的最优值为z =x+y=12+6=18。