線性規劃最優解不在內部：單純形法只沿邊界頂點爬

核心論點 · 點時間戳可跳到原聲

原話 · 已逐字校驗

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最小比率檢驗

用約束總量除以當前列正係數，取最小比值定步長。

收聽指南