We now begin discussion on how to solve a linear program. In this section, we describe how to solve a linear program with two decision variables, using the so-called graphical method. While doing this, we will develop a number of important geometrical insights that will form the basis for the general solution procedure known as the Simplex method.

Click on the title below to view the solution of an example.

The Graphical Method: An Example

The discussion in this example refers to several figures. To view these figures, click on the following titles: Figure LP-1, Figure LP-2, Figure LP-3.

The graphical solution of the above example reveals that a most important task in devising a solution procedure for linear programs is that of identification of corner-point solutions. We now turn our attention to this task. Our goal is to develop Procedure Corner Points into a formal, algebraic characterization of the corner-point solutions.

Click on the title below to view this characterization.

Corner-Point Solutions: A Characterization

This discussion refers to: Figure LP-4.

Assignment No. 2

Chapter 3: 3.1-5.

Chapter 5: 5.1-1, parts (a), (b), and (c) only.

Note that there is a slight difference in terminology between the text and our discussion here. In the text, the term "corner-point" solution refers to the solution of any given pair of defining equations. If the corner-point solution satisfies all constraints, then it is called a "corner-point feasible" (CPF) solution; otherwise, it is called a corner-point infeasible solution. Thus, the term "a CPF solution" in the text corresponds to the term "a corner-point solution" in our discussion.

For graphing, you might find the following Excel template helpful: A Sample Graph.