Can someone explain to me the reason why the simplex algorithm proceeds by only considering so-called basic solutions as candidates for the optimal solution to an LP?
Asked
Active
Viewed 624 times
-1
-
3Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. – José Carlos Santos Jan 22 '18 at 13:16
1 Answers
1
This is due to the Fundamental Theorem of Linear Programming, which states that a LPP has an optimal solution if and only if it has an optimal basic solution.
Therefore, in a (dual) simplex algorithm, it suffices to explore only the basic solutions (which are finitely many) instead of the whole feasible region (which is uncountably many).
GNUSupporter 8964民主女神 地下教會
- 17,627