Chapter 5

Linear Programming: A Geometric

1

Approach

5.1 Chapter Overview

In this chapter, you will learn to:

1. Solve linear programming problems that maximize the objective function.

2. Solve linear programming problems that minimize the objective function.

5.2 Maximization Applications

Application problems in business, economics, and social and life sciences often ask us to make decisions on
the basis of certain conditions. These conditions or constraints often take the form of inequalities. In this
section, we will look at such problems.
A typical linear programming problem consists of nding an extreme value of a linear function subject
to certain constraints. We are either trying to maximize or minimize our function. That is why these linear
programming problems are classied as maximization or minimization problems, or just optimization
problems. The function we are trying to optimize is called an objective function, and the conditions
that must be satised are called constraints. In this chapter, we will do problems that involve only two
variables, and therefore, can be solved by graphing. We begin by solving a maximization problem.
Example 5.1
Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of
12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of
preparation time, and for every hour she works at Job II, she needs one hour of preparation time,
and she cannot spend more than 16 hours for preparation. If she makes $40 an hour at Job I, and
$30 an hour at Job II, how many hours should she work per week at each job to maximize her
income?
Solution
We start by choosing our variables.
Let x = The number of hours per week Niki will work at Job I.
and y = The number of hours per week Niki will work at Job II.
1 This content is available online at <http://cnx.org/content/m18903/1.2/>.

Available for free at Connexions <http://cnx.org/content/col10613/1.5>

97
98 CHAPTER 5. LINEAR PROGRAMMING: A GEOMETRIC APPROACH

Now we write the objective function. Since Niki gets paid $40 an hour at Job I, and $30 an
hour at Job II, her total income I is given by the following equation.

I = 40x + 30y (5.1)

Our next task is to nd the constraints. The second sentence in the problem states, "She never
wants to work more than a total of 12 hours a week." This translates into the following constraint:

x + y ≤ 12 (5.2)
The third sentence states, "For every hour she works at Job I, she needs 2 hours of preparation
time, and for every hour she works at Job II, she needs one hour of preparation time, and she
cannot spend more than 16 hours for preparation." The translation follows.

2x + y ≤ 16 (5.3)
The fact that x and y can never be negative is represented by the following two constraints:
x ≥ 0, and y ≥ 0.
Well, good news! We have formulated the problem. We restate it as
Maximize I = 40x + 30y
Subject to: x + y ≤ 12
2x + y ≤ 16 (5.4)

x ≥ 0; y ≥ 0 (5.5)
In order to solve the problem, we graph the constraints as follows.

Figure 5.1

Available for free at Connexions <http://cnx.org/content/col10613/1.5>

 99

Observe that we have shaded the region where all conditions are satised. This region is called
the feasibility region or the feasibility polygon.
The Fundamental Theorem of Linear Programming states that the maximum (or mini-
mum) value of the objective function always takes place at the vertices of the feasibility region.
Therefore, we will identify all the vertices of the feasibility region. We call these points critical
points. They are listed as (0, 0), (0, 12), (4, 8), (8, 0). To maximize Niki's income, we will substitute
these points in the objective function to see which point gives us the highest income per week. We
list the results below.

Critical Points Income

(0,0) 40 (0) + 30 (0) = $0
(0.12) 40 (0) + 30 (12) = $360
(4,8) 40 (4) + 30 (8) = $400
(8,0) 40 (8) + 30 (0) = $320

Table 5.1

Clearly, the point (4, 8) gives the most prot: $400.

Therefore, we conclude that Niki should work 4 hours at Job I, and 8 hours at Job II.

Example 5.2
A factory manufactures two types of gadgets, regular and premium. Each gadget requires the
use of two operations, assembly and nishing, and there are at most 12 hours available for each
operation. A regular gadget requires 1 hour of assembly and 2 hours of nishing, while a premium
gadget needs 2 hours of assembly and 1 hour of nishing. Due to other restrictions, the company
can make at most 7 gadgets a day. If a prot of $20 is realized for each regular gadget and $30 for
a premium gadget, how many of each should be manufactured to maximize prot?
Solution
We choose our variables.
Let x = The number of regular gadgets manufactured each day.
and y = The number of premium gadgets manufactured each day.
The objective function is

P = 20x + 30y (5.6)

We now write the constraints. The fourth sentence states that the company can make at most 7
gadgets a day. This translates as

x+y ≤7 (5.7)
Since the regular gadget requires one hour of assembly and the premium gadget requires two hours
of assembly, and there are at most 12 hours available for this operation, we get

x + 2y ≤ 12 (5.8)
Similarly, the regular gadget requires two hours of nishing and the premium gadget one hour.
Again, there are at most 12 hours available for nishing. This gives us the following constraint.

2x + y ≤ 12 (5.9)

Available for free at Connexions <http://cnx.org/content/col10613/1.5>

100 CHAPTER 5. LINEAR PROGRAMMING: A GEOMETRIC APPROACH

The fact that x and y can never be negative is represented by the following two constraints:
x ≥ 0, and y ≥ 0.
We have formulated the problem as follows:
Maximize P = 20x + 30y
Subject to: x + y ≤ 7
x + 2y ≤ 12 (5.10)

2x + y ≤ 12 (5.11)

x ≥ 0; y ≥ 0 (5.12)
In order to solve the problem, we graph the constraints as follows:

Figure 5.2

Again, we have shaded the feasibility region, where all constraints are satised.
Since the extreme value of the objective function always takes place at the vertices of the
feasibility region, we identify all the critical points. They are listed as (0, 0), (0, 6), (2, 5), (5,
2), and (6, 0). To maximize prot, we will substitute these points in the objective function to see
which point gives us the maximum prot each day. The results are listed below.

Available for free at Connexions <http://cnx.org/content/col10613/1.5>

 101

Critical point Income

(0,0) 20 (0) + 30 (0) = $0
(0,6) 20 (0) + 30 (6) = $180
(2,5) 20 (2) + 30 (5) = $190
(5,2) 20 (5) + 30 (2) = $160
(6,0) 20 (6) + 30 (0) = $120

Table 5.2

The point (2, 5) gives the most prot, and that prot is $190. Therefore, we conclude that we
should manufacture 2 regular gadgets and 5 premium gadgets daily for a prot of $190.

Although we are mostly focusing on the standard maximization problems where all constraints are of the
form ax + by ≤ 0, we will now consider an example where that is not the case.
Example 5.3
Solve the following maximization problem graphically.
Maximize P = 10x + 15y
Subject to: x + y ≥ 1
x + 2y ≤ 6 (5.13)

2x + y ≤ 6 (5.14)

x ≥ 0; y ≥ 0 (5.15)
Solution
The graph is shown below.

Available for free at Connexions <http://cnx.org/content/col10613/1.5>

102 CHAPTER 5. LINEAR PROGRAMMING: A GEOMETRIC APPROACH

Figure 5.3

The ve critical points are listed in the above gure. Clearly, the point (2, 2) maximizes the
objective function to a maximum value of 50. The reader should observe that the rst constraint
x + y ≥ 1 requires that feasibility region must be bounded below by the line x + y = 1.

Finally, we address an important question. Is it possible to determine the point that gives the maximum
value without calculating the value at each critical point?
The answer is yes.
For example, in the above problem, we substituted the points (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0),
in the objective function P = 20x + 30y , and we got the values $0, $180, $190, $160, $120, respectively.
Sometimes that is not the most ecient way of nding the optimum solution.
To determine the largest P , we graph P = 20x + 30y for any value P of our choice. Let us say, we choose
P = 60. We graph 20x + 30y = 60. Now we move the line parallel to itself, that is, keeping the same slope at
all times. Since we are moving the line parallel to itself, the slope is kept the same, and the only thing that
is changing is the P . As we move away from the origin, the value of P increases. The largest value of P is
realized when the line touches the last corner point. The gure below shows the movements of the line, and
the optimum solution is achieved at the point (2, 5). In maximization problems, as the line is being moved
away from the origin, this optimum point is the farthest critical point.

Available for free at Connexions <http://cnx.org/content/col10613/1.5>

 103

Figure 5.4

We summarize:
5.4: The Maximization Linear Programming Problems
1. Write the objective function.
2. Write the constraints.
a) For the standard maximization linear programming problems, constraints are of the
form: ax + by ≤ c
b) Since the variables are non-negative, we include the constraints: x ≥ 0; y ≥ 0.
3. Graph the constraints.
4. Shade the feasibility region.
5. Find the corner points.
6. Determine the corner point that gives the maximum value.
a) This is done by nding the value of the objective function at each corner point.
b) This can also be done by moving the line associated with the objective function.

5.3 Minimization Applications

Minimization linear programming problems are solved in much the same way as the maximization problems.
For the standard minimization linear programming problem, the constraints are of the form ax + by ≥ c, as
opposed to the form ax + by ≤ c for the standard maximization problem. As a result, the feasible solution
extends indenitely to the upper right of the rst quadrant, and is unbounded. But that is not a concern,
since in order to minimize the objective function, the line associated with the objective function is moved
towards the origin, and the critical point that minimizes the function is closest to the origin.
However, one should be aware that in the case of an unbounded feasibility region, the possibility of no
optimal solution exists.

Available for free at Connexions <http://cnx.org/content/col10613/1.5>