How do we know that the Simplex method maximises the objective function

Question

I understand how to use the Simplex method.

However, I don't understand the reasoning behind it.

How do we know there is no other value for the objective function that satisfies the constraints?

Answer 1

You textbook should have a complete proof of correctness. (If you just learned Symplex on your own and have no reference, there are good expositions in many texts, including Papadimitriou and Steiglitz, Combinatorial Optimization.)

With the disclaimer out of the way, the basic idea behind Linear Programming can be understood in the case of two variables, in which we can draw "things" on a piece of paper. Suppose the constraints are inequalities like $x+2y \leq 4$. To fix ideas, let's talk about maximization problems.

Linear constraints are half planes in 2D and half planes are convex sets. When you intersect two convex sets you get another convex set. Bottom line: the feasible region of a linear program is a convex set.

Suppose the feasible region is non-empty and bounded. (Refer to your book for what happens when this is not true.) In the 2D case, it will be a convex polygon. Our problem is to find the point(s) of this polygon where the objective function attains its maximum value.

The objective function is also linear. For each value of the linear program it is indeed a straight line. For example, the objective function may be $2x + 3y$. The combinations of $x$ and $y$ for which the objective is $4$ are the points on the line $2x+3y=4$. As the objective changes, we get a family of lines, all with the same slope.

Take a generic line of this family, i.e., $2x + 3y = c$ and sweep the plane with it. As $c$ changes from large negative to large positive, the sweeping line will at some point touch the polygon. As $c$ continues to increase, the line will eventually leave the polygon behind. Just before it leaves the polygon, the sweeping line's $c$ gives the maximum values that the objective function achieves over a feasible point.

Normally, the sweeping line will at this point just touch the polygon in one of its vertices, but it is possible for it to be parallel to one of the sides of the polygon. In any case, the optimum value is achieved on the boundary of the polygon and not inside it.

This last observation is the key to the Symplex algorithm, because at every step it moves from a vertex of the polygon to another vertex along an edge in such a way that the objective function increases. That is, it moves the sweeping line in the direction of increasing value. Symplex stops when this is no longer possible; that is, when there is no vertex that would increase the objective function. This situation corresponds to the sweeping line being about to leave the polygon for good and provides the optimum solution.