Page 74 -

54 CHAPTER 2 AN INTRODUCTION TO LINEAR PROGRAMMING

Figure 2.13 The Five Extreme Points of the Feasible Region for the GulfGolf Problem

D

600
5

Number of Deluxe Bags 400 Feasible 4 3

Region
200

1 2
S
0 200 400 600 800
Number of Standard Bags

What observations can you make about the location of the optimal solutions in the
two linear programming problems solved thus far? Look closely at the graphical
solutions in Figures 2.9 and 2.12. Notice that the optimal solutions occur at one of
the vertices or ‘corners’ of the feasible region. In linear programming terminology,
these vertices are referred to as the extreme points of the feasible region. The GulfGolf
feasible region has five vertices, or five extreme points (see Figure 2.13). We can now
formally state our observation about the location of optimal solutions as follows:

The optimal solution to a linear programme can be found at an extreme
point of the feasible region. 2
For additional practise in This property means that if you are looking for the optimal solution to a linear
identifying the extreme programme, you do not have to evaluate all feasible solution points. In fact, you have
points of the feasible to consider only the feasible solutions that occur at the extreme points of the feasible
region and determining
the optimal solution by region. So, for the GulfGolf problem, instead of computing and comparing the profit
computing and contributions for all feasible solutions, we can find the optimal solution by evaluating
comparing the objective the five extreme-point solutions and selecting the one that provides the largest profit
function value at each
extreme point, try contribution. Actually, the graphical solution procedure is nothing more than a
Problem 9. convenient way of identifying an optimal extreme point for two-variable problems.

2.4 Computer Solution of the GulfGolf Problem

We have deliberately used a simple example to show the basics of LP. In the real
world, of course, LP problems are not this easy! LP problems may easily have several
hundred decision variables and thousands of constraints and clearly these cannot be

2
We will discuss in Section 2.6 the two special cases (infeasibility and unboundedness) in linear programming
that have no optimal solution, and for which this statement does not apply.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.