Chapter 2 The Simplex Algorithm
So, we saw that in lower dimensions, one can use geometric reasoning to find and interpret the optimal solution to a linear optimization problem. However, this intuition easily breaks down in higher dimensions. Moreover, brute force examination of potential corner points proves to be a massive and overwhelming approach to finding optimal solutions. Is there any way we can leverage this intuition built in lower dimensions to develop a systematic way to identify the optimal corner point?
In this chapter, we develop an algorithm, the Simplex Algorithm, which allows us to solve linear optimization problems in Section 2.1 we determine the rules for a simplex pivot and interpret this operation computationally, algebraiacally and geometrically. In Section 2.2 we discover the conditions for an appropriate pivot which preserves feasibility, as well as how to handle basic solutions which are infeasible, and minimization problems. In Section 2.3 we discuss Cycling, and how to avoid it with Bland’s Anticycling Rules. Finally in Section 2.4 we show how the programming language Sage may be used to remove some of the computational tedium of solving these problems.
