单纯形的代数思维

许 宁

（南京政治学院 基础部，江苏 南京 21003）

单纯形的代数思维

许 宁

（南京政治学院 基础部，江苏 南京 21003）

以单纯形的代数特征为切入点，建立基于矩阵的单纯形手工计算方法，揭示了单纯形及其各种计算技巧之间的内部联系，理清了单纯形由解特殊问题到解一般问题发展路径.

单纯形；单纯形矩阵；两阶段法；大M法

美国运筹学家Frederick S. Hillier 认为：线性规划理论是20世纪中叶最重要的科学进步之一［1］，线性规划的一个有效的求解方法是单纯形. 目前对单纯形处理通常是从几何直观开始，借助于单纯形表来展开，或者直接借助于MATLAB软件的linprog函数来求解等等，这些没有体现单纯形思想的精髓，没能体现在一堆数据中通过什么角度的观察，找到最优解的思维过程，不利于培养运用大数据的能力. 本文力图设计一种模式，充分揭示单纯形的代数思维过程，真正理解单纯形的本质.

1 单纯形是什么

现今大部分书籍是通过两个变量线性规划问题的图解法来说明最优值是在凸集的顶点上取得，因而只要比较凸集顶点的目标函数值的大小即可得最优解与最优值，这不能揭示单纯形是什么. 事实上，单纯形本质上是一个迭代算法，我们可以通过下面的例子［2］来考察单纯形是如何工作的. 设

单纯形是这样开始工作的，首先它从方程（2）的一个解(x1, x2, x3, x4, x5, x6)出发，寻找一个满足重复这一过程，直到不能改变目标函数值为止，这最后的解即为最优解.

为此，需要一个初始解(x1,L,x6). 一……