线性规划最优解不在内部：单纯形法只沿边界顶点爬

核心论点 · 点时间戳可跳到原声

原话 · 已逐字校验

The simplex algorithm starts at the origin and then moves to neighboring vertices that increase revenue until moving to the next vertex does not increase the revenue. Bam.

单纯形法从原点出发，移动到能使收入增加的相邻顶点，直到移动到下一个顶点不再增加收入为止。Bam。

Josh Starmer1:06

Now the two inequalities give us a sort of inequality sandwich that is the equivalent of the original equality.

这两个不等式构成一种「不等式三明治」，它等价于原来的等式。

Josh Starmer4:06

The idea is that when the total amount of something like flour used by the cookie and doughnut mixes on the left is less than the amount available on the right, the slack variables make up the difference.

思路是：当左侧饼干和甜甜圈混合料使用的面粉总量小于右侧可用量时，松弛变量把差额补上。

Josh Starmer5:08

In this example, the largest negative number in the first row, -3, is in the first column, the column for cookie mix. So, we could decide to go along the cookie mix axis.

在这个例子中，第一行最负的数是 -3，位于第一列 cookie mix，于是我们决定先沿 cookie mix 轴移动。

Josh Starmer8:10

Again, in general, the simplex algorithm selects the lowest value because larger values are always outside of the feasible region.

还是一样，单纯形法通常选最小的比值，因为更大的比值一定落在可行域外面。

Josh Starmer15:16

In other words, the point 10, 10, which represents a revenue of 50, is the best we can do given the constraints on the amount of flour, sugar, and chocolate that we can use.

也就是说，点 10,10 对应收入 50，是在面粉、糖、巧克力用量约束下我们能达到的最好结果。

Josh Starmer18:19

数字与实体

术语

simplex algorithm单纯形法

从原点出发、沿相邻边界顶点逐步寻找线性规划最优解的算法。

feasible region可行域

由全部约束围成的所有可行解所在区域。

objective function目标函数

要最大化或最小化的线性方程，例中是收入方程。

slack variable松弛变量

为把不等式补成等式而加入的非负变量。

Gaussian elimination高斯消元

用行变换化矩阵为阶梯形，从而读出交点坐标。

ratio test最小比率检验

用约束总量除以当前列正系数，取最小比值定步长。

收听指南