單純形算法 - 爲什麼這麼複雜？

Question

最近我被介紹給單純形算法來優化線性問題。我想我理解它是如何工作的，但我不知道，爲什麼它很複雜。

1. 爲什麼我們必須使用pivot- row/column /元素。如果我正確地看到這一點，它只是一個高斯消除，它消除了特定順序的元素。訂單爲什麼重要？這是由於數字噪音？如果一切都精確計算，那麼順序應該不重要，對嗎？

2. 在我迄今爲止遇到的所有例子中（不要太多太公平），所有鬆弛變量最後都設置爲零。爲什麼我們首先介紹它們，而不是直接將所有的不等式改寫成方程式？

Answer 1

1. 轉軸不是高斯消去。這個畫面可能會有像以前一樣多的零點。選擇樞軸的順序是爲了維持單形約束（總是從可行空間的一個頂點移動到另一個頂點），並且有效地完成（通過在每次移動時沿着目標取得最大進展）。
2. 對於綁定解決方案的約束，Slack變量爲零。這聽起來像你看到的問題沒有任何非約束性的約束。