Page 60 -

40 CHAPTER 2 AN INTRODUCTION TO LINEAR PROGRAMMING

NOTES AND COMMENTS

1 The three key assumptions necessary for a linear nonnegativity constraints mean that decision
programming model to be appropriate are variables can take on any value greater than or
proportionality, additivity and divisibility. equal to zero.
Proportionality means that the contribution to the 2 Management scientists formulate and solve a
objective function and the amount of resources variety of mathematical models that contain an
used in each constraint are proportional to the objective function and a set of constraints.
value of each decision variable. Additivity means Models of this type are referred to as
that the value of the objective function and the mathematical programming models.Linear
total resources used can be found by summing programming models are one type of
the objective function contribution and the mathematical programming model in that the
resources used for all decision variables. objective function and all constraint functions
Divisibility means that the decision variables are are linear.
continuous. The divisibility assumption plus the

2.2 Graphical Solution Procedure

Kellogg’s KPS LP model A linear programming problem involving only two decision variables can be solved
has around 100 000 using a graphical solution procedure. Clearly, in the real world LP problems will
constraints and 700 000 have many more decision variables (and constraints) and cannot be solved graphi-
variables.
cally (we will see how bigger problems are solved in later chapters). However, the
graphical solution introduces some important principles of LP solution that we
need to understand. Let us begin the graphical solution procedure by developing a
graph that displays the possible solutions (S and D values) for the GulfGolf problem.
The graph (Figure 2.1) will have values of S on the horizontal axis and values of D on the
vertical axis (it wouldn’t matter if we put these the other way around). Any point on the
graph can be identified by the S and D values, which indicate the position of the point
along the horizontal and vertical axes, respectively. Because every point (S, D) corre-
sponds to a possible solution, every point on the graph is called a solution point.The
solution point where S ¼ 0and D ¼ 0 is referred to as the origin. Because S and D must
be nonnegative, the graph in Figure 2.1 only displays solutions where S 0and D 0.
Earlier, we saw that the inequality representing the cutting and dyeing constraint is:
0:7S þ 1D 630
To show all solution points that satisfy this relationship, we start by graphing the
solution points satisfying the constraint as an equality. That is, the points where
0.7S +1D ¼ 630. Because the graph of this equation is a line, it can be obtained by
identifying any two points that satisfy the equation and then drawing a line through
those points. Setting S ¼ 0 and solving for D, we see that the point (S ¼ 0, D ¼ 630)
satisfies the equation. To find a second point satisfying this equation, we set D ¼ 0
and solve for S.Bydoing so,weobtain0.7S +1(0) ¼ 630, or S ¼ 900. Thus, a
second point satisfying the equation is (S ¼ 900, D ¼ 0). Given these two points,
we can now graph the line corresponding to the equation. This line, which will be
called the cutting and dyeing constraint line, is shown in Figure 2.2. We label this
line ‘C & D’ to indicate that it represents the cutting and dyeing constraint line.

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.