Unit 10
Linear Programming: Geometric Method

One of the major applications of linear algebra is the method for maximizing or minimizing some quantity, such as profit or cost, known as linear programming. In a linear programming problem, a linear function, called the objective function, is to be extremized (i.e., maximized or minimized), subject to a set of linear constraint equations. Linear programming provides various methods of solving such problems. In this unit, we present the basic ideas of linear programming in terms of the geometric method of solving linear programming problems.

Solutions are provided for the exercises assigned in this unit. However, you should attempt to solve every exercise on your own, before looking at the answer.

Objectives

When you have completed this unit, you should be able to

1. find the feasible set for simple linear programming problems in two and three variables, and solve these problems using the geometric method.
2. prove the basic theorem of linear programming in the case of two variables, and state the conditions under which there is a degenerate solution.