爲什麼simplex算法可以解決線性規劃問題

Question

我們知道simplex是一個非常有名的算法，用於解決線性規劃問題，我知道如何使用它，但是讓我困惑的是爲什麼simplex總是假定其中一個頂點多面體是最佳解決方案？

Answer 1

我認爲你可以參考幾何，尤其是解析幾何。單純形算法實際上意味着最佳結果始終停留在頂點而不是線或面中，這非常直觀。

Answer 2

簡而言之，在增加利潤的方向上走多面體內部，最終會出現在頂點。非常類似這樣的觀察：如果你在其中一個角落放置一個盒子，並從上面放一個大理石滾子，它會在這個角落裏結束。

當您停止垂直於利潤增長線的一側時，有一種情況需要考慮，那麼此端的所有點都是最佳解決方案。因此你可以選擇這邊的任何頂點。

Answer 3

給出的線性目標函數˚F和多面體P，你可以推理如下。

1. 任何點p在內部P嚴格的局部最大值不能。取一行L到p，並限制f到L。參數化L作爲p + t（q-p）對於某點q和t實數。然後˚F的限制是在噸線性的，並且有一個間隔（A，B）含有0表示噸是有效的。根據的噸係數，去在一個方向或另一個增加f。如果t的係數爲0，則儘可能在一個方向上走。
2. P的內部任何點都具有相同的屬性，您將行限制在該面上。
3. 走下來的邊界simplices，按維度。你最終在一個頂點;局部最大值在頂點。
4. 這並不意味着你選擇了正確的路線;單純形算法的複雜性是如何去正確的方向。