Linear Programming

© 2007 Pearson Education

 Linear Programming

 Linear programming: A technique that is useful for

allocating scarce resources among competing
demands.
 Objective function: An expression in linear
programming models that states mathematically
what is being maximized (e.g., profit or present
value) or minimized (e.g., cost or scrap).
 Decision variables: The variables that represent
choices the decision maker can control.
 Constraints: The limitations that restrict the
permissible choices for the decision variables.
© 2007 Pearson Education
 Linear Programming

 Feasible region: A region that represents all

permissible combinations of the decision variables in a
linear programming model.
 Parameter: A value that the decision maker cannot
control and that does not change when the solution is
implemented.
 Certainty: The word that is used to describe that a
fact is known without doubt.
 Linearity: A characteristic of linear programming
models that implies proportionality and additivity –
there can be no products or powers of decision
variables.
 Nonnegativity: An assumption that the decision
variables must be positive or zero.
© 2007 Pearson Education
 Formulating a Problem

 Step 1. Define the Decision Variables.

 Step 2.Write Out the Objective
Function.
 Step 3. Write Out the Constraints.

 Product-mix problem: A one-period

type of planning problem, the solution of
which yields optimal output quantities (or
product mix) of a group of services or
products subject to resource capacity and
market demand constraints.
© 2007 Pearson Education
 Formulating a Problem
Example E.1
 The Stratton Company produces 2 basic
types of plastic pipe. Three resources are
crucial to the output of pipe: extrusion hours,
packaging hours, and a special additive to the
plastic raw material.
 Below is next week’s situation.
Product

Resource
Resource Type 1 Type 2
Availability
Extrusion 4 hr 6 hr 48 hr
Packaging 2 hr 2 hr 18 hr
Additive mix 2 lb 1 lb 16 lb
© 2007 Pearson Education
 Formulating a Problem
Example E.1 continued
Step 1 – Define the decision variables
x1 = amount of type 1 pipe produced and sold next
week, 100-foot increments
x2 = amount of type 2 pipe produced and sold next
week, 100-foot increments
Product
Resource
Resource Type 1 Type 2
Availability
Extrusion 4 hr 6 hr 48 hr
Packaging 2 hr 2 hr 18 hr
Additive mix 2 lb 1 lb 16 lb
© 2007 Pearson Education
 Formulating a Problem
Example E.1 continued
Step 2 – Define the objective function
Each unit of x1 yields $34, and each unit of x2
yields $40.
Objective is to
maximize profits (Z) Max Z = $34 x1 + $40 x2

Product
Resource
Resource Type 1 Type 2
Availability
Extrusion 4 hr 6 hr 48 hr
Packaging 2 hr 2 hr 18 hr
Additive mix 2 lb 1 lb 16 lb
© 2007 Pearson Education
 Formulating a Problem
Example E.1 continued
Step 3 – Formulate the constraints
Product
Resource
Resource Type 1 Type 2
Availability
Extrusion 4 hr 6 hr 48 hr
Packaging 2 hr 2 hr 18 hr
Additive mix 2 lb 1 lb 16 lb

Extrusion 4 x1 + 6 x2  48
Packaging 2 x1 + 2 x2  18
Additive mix
2 x1 + x2  16
© 2007 Pearson Education
 Formulating a Problem
with Inequalities
 Typically the constraining resources have upper or
lower limits.
 e.g., for the Stratton Company, the total extrusion time must
not exceed the 48 hours of capacity available, so we use
the ≤ sign.
 Negative values for constraints x1 and x2 do not
make sense, so we add nonnegativity restrictions to
the model:
x1 ≥ 0 and x2 ≥ 0 (nonnegativity restrictions)
 Other problem might have constraining resources
requiring >, >, =, or < restrictions.
© 2007 Pearson Education
 Formulating a Problem
Application E.1
 The Crandon Manufacturing Company produces two
principal product lines. One is a portable circular saw, and
the other is a precision table saw. Two basic operations are
crucial to the output of these saws: fabrication and
assembly. The maximum fabrication capacity is 4000 hours
per month; each circular saw requires 2 hours, and each
table saw requires 1 hour. The maximum assembly
capacity is 5000 hours per month; each circular saw
requires 1 hour, and each table saw requires 2 hours. The
marketing department estimates that the maximum market
demand next year is 3500 saws per month for both
products. The average contribution to profits and overhead
is $900 for each circular saw and $600 for each table saw.

© 2007 Pearson Education

 Application E.1
 Management wants to determine the best product
mix for the next year so as to maximize contribution
to profits and overhead. Also, it is interested in the
payoff of expanding capacity or increasing market
share.
Maximize: 900x1 + 600x2 = Z
Subject to: 2x1 + 1x2  4,000 (Fabrication)
1x1 + 2x2  5,000 (Assembly)
1x1 + 1x2  3,500 (Demand)
x1, x2 ≥ 0 (Nonnegativity)

© 2007 Pearson Education

 Graphic Analysis

 Most linear programming problems are solved with a

computer.
 However, insight into the meaning of the computer output,
and linear programming concepts in general, can be
gained by analyzing a simple two-variable problem
graphically.
 Graphic method of linear programming: A type of
graphic analysis that involves the following five
steps:
 plotting the constraints
 identifying the feasible region
 plotting an objective function line
 finding a visual solution
 finding the algebraic solution
© 2007 Pearson Education
 Graphic Analysis
Example E.2
x2
18 —
We begin by plotting the constraint equations,
disregarding the inequality portion of the constraints
16 — (< or >). Making each constraint an equality (=)
transforms it into the equation for a straight line.
14 —

12 — 2x1 + x2  16 (additive mix)

10 — 2x1 + 2x2  18 (packaging)
8—

6—

4— 4x1 + 6x2  48 (extrusion)

2—
| | | | | | | | |
0 x1
© 2007 Pearson Education 2 4 6 8 10 12 14 16 18
 Graphic Analysis
Example E.3
 The feasible region is the area on the graph that
contains the solutions that satisfy all the constraints
simultaneously.
 To find the feasible region, first locate the feasible
points for each constraint and then the area that
satisfies all constraints.
 Generally, the following three rules identify the feasible
points for a given constraint:
1. For the = constraint, only the points on the line are feasible solutions.
2. For the ≤ constraint, the points on the line and the points below or to
the left of the line are feasible.
3. For the ≥ constraint, the points on the line and the points above or to
the right of the line are feasible.
© 2007 Pearson Education
 Graphic Analysis
Identify the feasible region
x2
18 —

16 —

14 —

12 — 2x1 + x2  16 (additive mix)

10 — B 2x1 + 2x2  18 (packaging)
8—
C
6—

4— 4x1 + 6x2  48 (extrusion)

Feasible D
2 — region
| | |E | | | | | |
0 x1
© 2007 Pearson Education A 2 4 6 8 10 12 14 16 18
 Application E.2

Plotting Crandon Mfg. Constraints

0 4,000 2,000 0

0 2,500 5,000 0

0 3,500 3,500 0

© 2007 Pearson Education

 Plotting Crandon Mfg.
Constraints

© 2007 Pearson Education

 Graphic Analysis
Plotting an Objective Function Line

 Now we want to find the solution that optimizes the

objective function.
 Even though all the points in the feasible region represent
possible solutions, we can limit our search to the corner
points.
 Corner point: A point that lies at the intersection of
two (or possibly more) constraint lines on the
boundary of the feasible region.
 No interior points in the feasible region need be
considered because at least one corner point is better
than any interior point.
 The best approach is to plot the objective function
on the graph of the feasible region for some
arbitrary Z values.
© 2007 Pearson Education
 Graphic Analysis
Plotting an Objective Function Line
x2
18 — For Example E.3, the equation for an
arbitrary objective function line passing
16 —
through E is 34x1 + 40x2 = 272
14 —

12 — 2x1 + x2  16 (additive mix)

10 — B 2x1 + 2x2  18 (packaging)
8—
C 34x1 + 40x2 = $272
6—

4— 4x1 + 6x2  48 (extrusion)

Feasible D
2 — region
| | |E | | | | | |
0 x1
© 2007 Pearson Education A 2 4 6 8 10 12 14 16 18
 Graphic Analysis
Plotting an Objective Function Line
x2
A series of dashed lines can be drawn parallel to
18 —
this first line. Each would have its own Z value.
16 — Lines above the first line would have higher Z
values. Lines below it would have lower Z values.
14 —

12 — 2x1 + x2  16 (additive mix)

10 — B 2x1 + 2x2  18 (packaging)
8—
C
6—

4— 4x1 + 6x2  48 (extrusion)

Feasible D
2 — region
| | |E | | | | | |
0 x1
© 2007 Pearson Education A 2 4 6 8 10 12 14 16 18
 Graphic Analysis
Identifying the Visual Solution
x2
18 — Our goal is to maximize profits, so the best
solution is a point on the iso-profit line farthest
16 — from the origin but still touching the feasible region.
14 —

12 — 2x1 + x2  16 (additive mix)

10 — B 2x1 + 2x2  18 (packaging)
8—
C Optimal solution (3,6)
6—

4— 4x1 + 6x2  48 (extrusion)

Feasible D
2 — region
| | |E | | | | | |
0 x1
© 2007 Pearson Education A 2 4 6 8 10 12 14 16 18
 Application E.3
Iso-profit Line
and Visual Solution
for Crandon Mfg.

© 2007 Pearson Education

 Finding the
Algebraic Solution
 Step 1: Develop an equation with just one
unknown.
 Start by multiplying both sides by a constant so
that the coefficient for one of the two decision
variables is identical in both equations.
 Then subtract one equation from the other and
solve the resulting equation for its single
unknown variable.
 Step 2: Insert this decision variable’s value
into either one of the original constraints
and solve for the other decision variable.
© 2007 Pearson Education
 Application E.4

Algebraic Solution
for Crandon Mfg.
Solve algebraically,
with two equations
and two unknowns

© 2007 Pearson Education

 Slack & Surplus Variables

 Binding constraint: A constraint that helps form

the optimal corner point; it limits the ability to
improve the objective function.
 Slack: The amount by which the left-hand side falls
short of the right-hand side.
To find the slack for a ≤ constraint algebraically, we add a
slack variable to the constraint and convert it to an equality.
 Surplus: The amount by which the left-hand side
exceeds the right-hand side.
To find the surplus for a ≥ constraint, we subtract a surplus
variable from the left-hand side to make it an equality.

© 2007 Pearson Education

 Application E.5

Slack Variables
for Crandon Mfg.

© 2007 Pearson Education

 Sensitivity Analysis

 Coefficient sensitivity: How much the objective function

coefficient of a decision variable must improve (increase for
maximization or decrease for minimization) before the optimal
solution changes and the decision variable becomes some
positive number.
 Range of feasibility: The interval over which the right-
hand-side parameter can vary while its shadow price remains
valid.
 Range of optimality: The lower and upper limits over
which the optimal values of the decision variables remain
unchanged.
 Shadow price: The marginal improvement in Z (increase
for maximization and decrease for minimization) caused by
relaxing the constraint by one unit.
© 2007 Pearson Education
 Computer Solutions

 Computer programs dramatically reduce the time

required to solve linear programming problems.
 Special-purpose programs can be developed for
applications that must be repeated frequently.
 Such programs simplify data input and generate the
objective function and constraints for the problem. In
addition, they can prepare customized managerial
reports.
 Simplex method: An iterative algebraic procedure
for solving linear programming problems.
 Most real-world linear programming problems are solved
on a computer. The solution procedure in computer
codes is some form of the simplex method.
© 2007 Pearson Education
 Computer Solution
Output from OM Explorer
for the Stratton Company

© 2007 Pearson Education

 Computer Solution
Output from OM Explorer
for the Stratton Company

Results Worksheet

© 2007 Pearson Education

 Computer Solution
The coefficient sensitivities
provide no new insight because
they are always 0 when
decision variables have positive
values in the optimal solution.

Optimal solution is to
make 300 ft of type 1
pipe and 600 ft of type 2
pipe. Thus the product
mix is x1 and x2.

Maximum profit

© 2007 Pearson Education

 Computer Solution

All of the extrusion and

packaging time was used.

An additional hour of
extrusion time would
contribute $3 to profits.

An additional hour of
packaging time is worth
$11.

4 lbs of additive were

unused (surplus) so its
© 2007 Pearson Education shadow price is zero.
 Computer Solution
If either objective function
coefficient goes above or
below its sensitivity
range, the product mix
will change.

If the availability of one

of the constraints goes
above or below its
sensitivity range, the
product mix will change.

Increased additive has

no limit because there
was a 4 lb surplus.
© 2007 Pearson Education
 APPLICATIONS OF LINEAR PROGRAMMING
 Product Mix: Find the best mix of products to produce.
 Shipping: Find the optimal shipping assignments.
 Stock Control: Determine the optimal mix of products to hold in
inventory.
 Supplier Selection: Find the optimal combination of suppliers to
minimize unwanted inventory.
 Plants or Warehouses: Determine optimal location of a plant or
warehouse.
 Stock Cutting: Find the cutting pattern that minimizes the amount of
scrap.
 Production: Find the minimum-cost production schedule.
 Staffing: Find the optimal staffing levels.
 Blends: Find the optimal proportions of various ingredients used to
make products.
 Shifts: Determine the minimum-cost assignment of workers to shifts.
 Vehicles: Assign vehicles to products or customers.
 Routing: Find the optimal routing of a service or product through
several sequential processes.
© 2007 Pearson Education
 Product Mix Problem
Application E.6
The Trim-Look Company makes several lines of skirts,
dresses, and sport coats for women. Recently it was
suggested that the company reevaluate its South Islander
line and allocate its resources to those products that would
maximize contribution to profits and overhead. Each product
must pass through the cutting and sewing departments. In
addition, each product in the South Islander line requires the
same polyester fabric. The following data were collected for
the study.

The Cutting department has 100 hours of capacity, sewing

has 180 hours, and 60 yards of material are available. Each
skirt contributes $5 to profits and overhead; each dress,
$17; and each sport coat, $30.
© 2007 Pearson Education
 Product Mix Problem
Application E.6

© 2007 Pearson Education

 Process Design
Application E.7
The plant manager of a plastic pipe manufacturer has the
opportunity to use two different routings for a particular type of
plastic pipe: Routing 1 uses extruder A, and routing 2 uses
extruder B. Both routings require the same melting process.
The following table shows the time requirements and capacities
of these processes.

In addition, each 100 feet of pipe processed on routing 1 uses 5

pounds of raw material, whereas each 100 feet of pipe
processed on routing 2 uses only 4 pounds. This difference
results from differing scrap rates of the extruding machines.
Consequently, the profit per 100 feet of pipe processed on
routing 1 is $60 and on routing 2, $80. A total of 200 pounds of
raw material is available.
© 2007 Pearson Education
 Process Design
Application E.7

© 2007 Pearson Education

 Blending Problem
Application E.8
Consider the task facing the procurement manager of a company that
manufactures special additives. She must determine the proper amounts
of each raw material to purchase for the production of a certain product.
Three raw materials are available. Each gallon of the finished product
must have a combustion point of at least 220°F. In addition, the gamma
content (which causes hydrocarbon pollution) cannot exceed 6 percent
of the volume. The zeta content (which cleans the internal moving parts
of engines) must be at least 12 percent by volume. Each raw material
has varying degrees of these characteristics.

Raw material A costs $0.60 per gallon; raw material B, $0.40; and raw
material C, $0.50. The procurement manager wishes to minimize the
cost of raw materials per gallon of product. What are the optimal
proportions of each raw material to use in a gallon of finished product?
Hint: Express your decision variables in terms of fractions of a gallon.
The sum of the fractions must equal 1.00.
© 2007 Pearson Education
 Blending Problem
Application E.8

© 2007 Pearson Education

 Portfolio Selection
Application E.9

E-Traders, Inc. invests in various types of securities. The firm

has $5 million for immediate investment and wishes to maximize
the interest earned over the next year. Risk is not a factor. There
are four investment possibilities, as outlined below.

To further structure the portfolio, the board of directors has

specified that at least 40 percent of the investment must be
placed in corporate bonds and common stock. Furthermore, no
more than 20 percent of the investment can be in real estate.

© 2007 Pearson Education

 Portfolio Selection
Application E.9

© 2007 Pearson Education

 Shift Scheduling
Application E.10

NYNEX has a scheduling problem. Operators work eight-hour

shifts and can begin work at either midnight, 4 A.M., 8 A.M.,
noon, 4 P.M., or 8 P.M. Operators are needed according to the
following demand pattern.

Hint: Let xj equal the number of operators beginning work (an

eight-hour shift) in time period j, where j = 1, 2, . . . , 6.
Formulate the model to cover the demand requirements
with the minimum number of operators.
© 2007 Pearson Education
 Shift Scheduling
Application E.10

© 2007 Pearson Education

 Production Planning
Application E.11
Bull Grin employs manual, unskilled labor, who require little or no
training. Producing 1000 pounds of supplement costs $810 on regular
time and $900 on overtime. These figures include materials, which
account for over 80 percent of the cost. Overtime is limited to production
of 30,000 pounds per quarter. In addition, subcontractors can be hired at
$1100 per thousand pounds, but only 10,000 pounds per quarter can be
produced this way.
The current level of inventory is 40,000 pounds, and management wants
to end the year at that level. Holding 1000 pounds of feed supplement in
inventory per quarter costs $110. The latest annual forecast follows.

The firm currently has 180 workers, a figure that management wants to
keep in quarter 4. Each worker can produce 2000 pounds per quarter, so
that regular-time production costs $1620 per worker. Idle workers must
be paid at that same rate. Hiring one worker costs $1000, and laying off
a worker costs $600.
© 2007 Pearson Education
 Production Planning
Application E.11

© 2007 Pearson Education

 Production Planning
Application E.11

© 2007 Pearson Education

 Solved Problem 1

 O’Connel Airlines is considering air service from its hub of

operations in Cicely, Alaska to Rome, Wisconsin, and Seattle.
 They have one gate at the Cicely Airport, which operates 12
hours per day. Each flight requires 1 hour of gate time.
 Each flight to Rome consumes 15 hours of pilot crew time and
is expected to produce a profit of $2,500.
 Serving Seattle uses 10 hours of pilot crew time per flight and
will result in a profit of $2,000 per flight.
 Pilot crew labor is limited to 150 hours per day.
 The market for service to Rome is limited to 9 flights per day.
1. Use the graphic method to maximize profits.
2. Identify slack and surplus constraints, if any.
© 2007 Pearson Education
 Solved Problem 1

The objective function is to maximize profits (Z)

Maximize Z = $2,500x1 + $2,000x2

where
x1 = number of flights per day to Rome, Wisconsin
x2 = number of flights per day to Seattle, Washington

The constraints are

x1 + x2 ≤ 12 (gate capacity)
15 x1 + 10 x2 ≤ 150 (labor)
x1 ≤9 (market)
x1 ≥ 0 and x2 ≥ 0
© 2007 Pearson Education
 Solved Problem 1

x2

15 — 15 x1 + 10 x2 ≤ 150 (labor)
E
2,500 x1 +2,000 x2 = $20,000
(iso-profit line)
10 —
x1 ≤ 9 (market)
D

5—

x1 + x2 ≤ 12 (gate)
C
| B | | x1
0 —A 5 10 15
© 2007 Pearson Education
 Solved Problem 1
x2

15 — 15 x1 + 10 x2 ≤ 150 (labor)

E´

A careful drawing 10 —
of iso-profit lines x1 ≤ 9 (market)
parallel to the one
shown indicates D´
that point D is the
optimal solution. 5—
x1 + x2 ≤ 12 (gate)
C
| B | | x1
A 5 10 15
0—
The maximum profit results from making six flights to Rome and six flights to Seattle:
© 2007 Pearson Education $2,500(6) + $2,000(6) = $27,000