线性规划的人工变量法具体案例（CPDA小课堂之线性规划单纯形法）

CPDA小课堂之线性规划单纯形法

单纯形法是求解线性规划问题最常用的方法之一。求可行最优解是一个迭代的过程。在这种方法中，基本变量的值不断变换，以获得目标函数的最大值。线性规划单纯形法的算法如下:

第一步:建立一个给定的问题。(即)写出不等式约束和目标函数。

步骤2:通过向每个不等式表达式添加松弛变量，将给定的不等式转换为方程。

步骤3:创建初始的simplex表。把目标函数写在最下面一行。在这里，每个不等式约束都出现在自己的行中。现在，我们可以用增广矩阵的形式来表示这个问题，它被称为初始单形表。

步骤4:确定最下面一行中最大的负项，这有助于确定主列。最下面一行最大的负项定义了目标函数中最大的系数，这将帮助我们尽可能快地增加目标函数的值。

步骤5:计算商。要计算商，我们需要用最右边一列的项除以第一列的项，不包括最下面一行。最小的商表示行。在此步骤中标识的行和在此步骤中标识的元素将被作为主元素。

步骤6:进行旋转，使列中的所有其他条目为零。

步骤7:如果底部一行没有负数，则结束此过程。否则，请从步骤4开始。

步骤8:最后，确定与最终的simplex表相关的解决方案。