The Simplex Method

Based on the example described in Section 1.1, the idea for solving general linear proauf grams with the Simplex Method can be motivated as follows: Imagine we move from corner point to corner point of the feasible region P (a corner point is a point in P which is a unique intersection point of two of its facets) uszungs ing a procedure which guarantees that the objective value is improved in every step. As soon as we have reached a corner point in which no further improvement of the objective value is possible, the algorithm stops and the corner point corresponds to an optimal solution of the LP. In Examdes ple 1.1.1 of Section 1.1 such a sequence of corner points is, for instance:

This is exactly the idea on which the Simplex Method is based which was developed by G. Dantzig in 1947. It yields an optimal solution (whenever it exists) for any LP (that means the objective function can be maximized or minimized, the number of constraints and variables is .nite but arbibig, trary, sign constraints can be present but they don’t have to be). An important step in the development of the preceding idea for arbitrary linear programs is the application of methods from linear algebra, in particular the solution of systems of linear equalities.