Page 72 -

52 CHAPTER 2 AN INTRODUCTION TO LINEAR PROGRAMMING

Max 10S þ 9D þ 0S 1 þ 0S 2 þ 0S 3 þ 0S 4
s:t:
7
/ 10 S þ 1D þ 1S 1 ¼ 630
1 5
/ 2 S þ / 6 D þ 1S 2 ¼ 600
2
1S þ / 3 D þ 1S 3 ¼ 708
1 1
/ 10 S þ / 4 D þ 1S 4 ¼ 135
S; D; S 1 ; S 2 ; S 3 ; S 4 0
Whenever a linear programme is written in a form with all constraints expressed
Can you write a linear as equalities, it is said to be written in standard form.
programme in standard Referring to the standard form of the GulfGolf problem, we see that at the
form? Try Problem 11.
optimal solution (S ¼ 540 and D ¼ 252), the values for the slack variables are:

Constraint Value of Slack Variable
Cutting and dyeing S 1 =0
Sewing S 2 = 120
Finishing S 3 =0
Inspection and packaging S 4 =18

Could we have used the graphical solution to provide some of this information? The
answer is yes. By finding the optimal solutionpointon Figure2.5,we can seethatthe
cutting and dyeing and the finishing constraints restrict, or bind, the feasible region at this
point. Thus, this solution requires the use of all available time for these two operations. In
other words, the graph shows us that the cutting and dyeing and the finishing depart-
ments will have zero slack. On the other hand, the sewing and the inspection and
packaging constraints are not binding the feasible region at the optimal solution, which
means we can expect some unused time or slack for these two operations.
As a final comment on the graphical analysis of this problem, look at the sewing
capacity constraint as shown in Figure 2.5. Note, in particular, that this constraint did
not affect the feasible region. That is, the feasible region would be the same whether
the sewing capacity constraint were included or not, which tells us that there is enough
sewing time available to accommodate any production level that can be achieved by
the other three departments. The sewing constraint does not affect the feasible region
and thus cannot affect the optimal solution; it is called a redundant constraint.

NOTES AND COMMENTS

1 In the standard-form representation of a linear variables representing the amount of unused
programming model, the objective function resources to be sold. For each of these variables,
coefficients for slack variables are zero. This zero a nonzero coefficient in the objective function
coefficient implies that slack variables, which would reflect the profit associated with selling a
represent unused resources, do not affect the unit of the corresponding resource.
value of the objective function. However, in some 2 Redundant constraints do not affect the feasible
applications, unused resources can be sold and region; as a result, they can be removed from a linear
contribute to profit. In such cases, the programming model without affecting the optimal
corresponding slack variables become decision solution. However, if the linear programming model is

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.