ch7_summary.htm
LINEAR PROGRAMMING
Properties
(LP problems have 4 properties in common.)
All problems have the following 4 properties
1) Objective Function
Seek to Maximize or Minimize some quantity
Usually profit or cost
Called the Objective Function
2) Constraints
Limit the degree to which we can pursue our objectives
Constraints
represent production capacity restrictions and affect the total profit.
3) There must be alternatives available
For example, how much of the resources to allocate to each
product
4) The mathematical relationships are linear
The equations are straight-line equations (linear, 1st
degree) or (linear) inequalities
Technical Assumptions
(LP problems have 5 technical assumptions.)
1) Certainty
The objectives and constraints do not change (during the
period being studied)
2) Proportionality
If x products use y units to produce, then 3x products use 3y
units to produce (this comes from linearity)
3) Additivity
If you make x dollars for one product and y dollars for a
second product, then if you make one of each, you must make x + y dollars.
4) Divisibility
Solutions need not be whole numbers
5) Non-negativity
Negative quantities do not make sense
Steps in Formulating LP Problems
Step 1) Understand the problem
Step
2) Identify the objectives and the constraints
Step
3) Define the decision variables
Step
4) Use the variables to write equations for the objective and the constraint
functions
Maximization Problem Example
Problem Statement
Flair Furniture Company wants to maximize its profits. The company
produces inexpensive tables and chairs. The production process for each is
similar in that both require a certain number of hours of carpentry work and a
certain number of labor hours in the painting and varnishing department.
Objective: (Seek to
Maximize...Maximize
profits)
1) Each
table sold yields a profit of $7; each chair produced is sold for a $5 profit.
Constraints: (Limit
the degree to which we can pursue our objectives)
1) Each table takes 4 hours of
carpentry and 2 hours in the painting and varnishing shop.
2) Each chair requires 3 hours in
carpentry and 1 hour in painting and varnishing.
3) During the current production
period, 240 hours of carpentry time are available and 100 hours in painting and
varnishing time are available.
Formulate
the Problem
Step 1) Understand the problem...summarize the data
|
|
Hours
Required to
Produce 1 Unit |
|
|
|
T |
C |
Available
Hours |
|
|
Tables |
Chairs |
This
Week |
|
Carpentry |
4 |
3 |
240 |
|
Painting
and varnishing |
2 |
1 |
100 |
|
Profit
per unit |
7 |
5 |
|
Step
2) Identify the objectives and the constraints
The objective is to Maximize profit
The constraints are
1.
The hours of carpentry time used cannot exceed 240 hours per week.
2. The hours of painting and varnishing time used
cannot exceed 100 hours per week.
Step
3) Define the decision variables...The
decision variables that represent the actual decisions we will make are defined
as
T
=
number of tables to be produced
C
= number of chairs to be produced
Step
4) Use the variables to write equations for the objective and the constraint
functions
|
The
objective function (to maximize profit ) |
|
Profit = (profit of a
table) x (number of tables produced)
+ (profit of a chair) x (number of chairs produced) |
|
P
=
7T
+ 5C |
|
. |
| The constraints:
The amount of a resource used is to be £ the amount of
resource available. |
|
Carpentry
(4 hours per table) x (number
of tables produced) + (3 hours per chair) x(number
of chairs produced) £
240 (hours of carpentry time)
|
| 4T
+ 3C
£
240 |
Painting
and varnishing
(2 hours per table)
x (number of tables produced) +
(1 hour per chair) x (number
of chairs produced) £
100 (hours of
carpentry time) |
| 2T
+ C £
100 |
| Non-negativity |
| C ³ 0
(y-axis),
T ³ 0
(x-axis) |
Solve the Problem
Steps
in Solving LP Problems
Step
1) Plot the Constraint boundary lines
Step
2) Find the Corner points and label them, and then substitute the points in the
objective function
Step 3)
State the Solution
Step 1) Plot the Constraint boundary lines (let C
be the vertical axis and T
be the horizontal axis...points (T,
C))
Carpentry
4T
+ 3C
=
240,
Painting
and varnishing 2T
+ C
£
100
|
Carpentry |
 
  |
|
Inequality |
4T
+ 3C
£
240
(shade below since £) |
|
Boundary line |
4T
+ 3C
=
240
for
calculator graphing, let X
= T
and
Y = C
and
solve
4X
+ 3Y
=
240
for
Y
calculator
entry Y1
=
(240
- 4X)/3
To
plot by hand, find the intercepts as below |
|
C-intercept |
When
T
= 0, 4(0)
+ 3C
= 240, C
= 80,
(0, 80) |
|
T-intercept |
When
C
= 0, 4T
+ 3(0)
= 240, T
= 60,
(60, 0) |
|
. |
Step 2) Find the Corner points and
label them, and then substitute the points in the objective function P
=
7T
+ 5C
| Point
(T,
C) |
Profit
P
=
7T
+ 5C |
Where
from (the point) |
|
| CP1
= (0, 0) |
P
=
7(0)
+ 5(0)
= 0 |
Origin |
|
| CP2
= (0, 80) |
P
=
7(0)
+ 5(80)
= 400 |
C-intercept
for 4T
+ 3C
= 240 |
|
| CP3
= (30,40) |
P
=
7(30)
+ 5(40)
= 410 |
simultaneously
solve the system 4T
+ 3C
= 240 and 2T
+ C =
100
(do by hand using the addition or substitution method, or on the TI-83,
use APPS, then PolySmlt (see below)
...on the 86 (get the software from your instructor),
use 2nd POLY and then it is similar to the 83) |
|
| CP4
= (50, 0) |
P
=
7(50)
+ 5(0)
= 350 |
T-intercept
for 2T
+ C =
100 |
|
Step 3) The chair and table quantities
for the point producing the largest Profit is the solution
CP3
= (30,40), P
=
7(30)
+ 5(40)
= 410...Produce 30
tables and 40 chairs
Minimization Problem Example
Many
LP problems involve minimizing an objective such as cost instead of maximizing a
profit function.
Problem
Statement
The Holiday Meal Turkey Ranch is
considering buying two different brands of turkey feed and blending them to
provide a good, low-cost diet for its turkeys. Each feed contains, in varying
proportions, some or all of the three nutritional ingredients essential for
fattening turkeys. The
owner of the ranch would like to use LP to determine the lowest-cost diet that
meets the minimum monthly intake requirement for each nutritional ingredient.
Each
pound of brand 1 purchased contains 5 ounces of ingredient A, 4
ounces of ingredient B, and 1/2 ounce of ingredient C.
Each pound of brand 2 contains 10 ounces of ingredient A, 3 ounces of ingredient
B, but no ingredient C.
The brand 1 feed costs the ranch 2 cents a pound, while the brand 2 feed costs 3
cents a pound. Ingredient A must exceed 90 ounces.
Ingredient B must exceed 48 ounces. Ingredient C must exceed 3/2 ounces.
Step 1) Understand the problem...summarize
the data
|
|
Composition
of each
pound of Feed (OZ) |
Minimum
Monthly
Requirement
per Turkey (OZ) |
|
Ingredient |
Brand
1 |
Brand
2 |
|
A |
5 |
10 |
90 |
|
B |
4 |
3 |
48 |
|
C |
1/2 |
0 |
3/2 |
|
Cost
per pound |
2
cents |
3
cents |
|
Step
2) Identify the objectives and the constraints
The objective is to Minimize cost
to feed each (1) turkey per month
The constraints are
1.
Ingredient A must exceed 90 ounces.
2. Ingredient B must exceed 48 ounces.
2. Ingredient C must exceed 3/2 ounces.
Step
3) Define the decision variables...The
decision variables that represent the actual decisions we will make are defined
as
X1 =
number of pounds of brand 1 feed purchased
X2
= number of pounds of brand 2 feed purchased
Step
4) Use the variables to write equations for the objective and the constraint
functions
|
The
objective function (to minimize cost) |
|
M = 2X1
+ 3X2
(in
cents) |
|
. |
| The constraints:
The amount of a resource used is to be ³ the amount of the
resource required. |
|
Ingredient
A
|
| 5X1
+ 10X2 ³ 90
(OZ) |
| Ingredient
B |
| 4X1
+ 3X2 ³ 48
(OZ) |
| Ingredient
C |
| X1/2 ³ 3/2
(OZ) |
| Non-negativity |
| X2 ³ 0
(y-axis),
X1 ³ 0
(x-axis) |
Solve the Problem
Step 1) Plot the Constraint boundary lines (let X2
be the vertical axis and X1
be the horizontal axis...points (X1,
X2))
Ingredient
A, 5X1
+ 10X2 ³ 90,
Ingredient
B, 4X1
+ 3X2 ³ 48,
Ingredient C, X1/2 ³ 3/2
|
Ingredient
A |
|
|
Inequality |
5X1
+ 10X2 ³ 90
(shade above since ³) |
|
Boundary line |
5X1
+ 10X2 = 90
for
calculator graphing, let X
= X1
and
Y = X2
and
solve
5X
+ 10Y = 90
for
Y
calculator
entry Y1
=
(90
- 5X)/10
To
plot by hand, find the intercepts as below |
|
X2-intercept |
When
X1
= 0, 5(0)
+ 10X2 = 90,
X2
= 9,
(0,
9) |
|
X1-intercept |
When
X2
= 0, 5X1
+ 10(0)
= 90,
X1
= 18,
(18, 0) |
|
. |
|
Ingredient
B |
|
|
Inequality |
4X1
+ 3X2 ³ 48
(shade above since ³) |
 
Views
of feasible region below
x2
 x1
 |
|
Boundary line |
4X1
+ 3X2 = 48
for
calculator graphing, let X
= X1
and
Y = X2
and
solve 4X
+ 3Y
=
48
for
Y
calculator
entry Y1
= (48
- 4X)/3
To
plot by hand, find the intercepts as below |
|
X2-intercept |
When
X1
= 0, 4(0)
+ 3X2 = 48,
X2
= 16
(0, 16) |
|
X1-intercept |
When
X2
= 0, 4X1
+ 3(0)
= 48,
X1
= 12
(12, 0) |
|
Ingredient
C
X1/2 ³ 3/2
X1 ³ 3
X1 = 3
is a vertical boundary line
Y3
=
-9999(X
-
3)
(shade
to right since ³)
trick
the calculator - can't normally graph
vertical lines using the function editor,
Y=, because they are not functions |
Step 2) Find the Corner points and
label them, and then substitute the points in the objective function M
= 2X1
+ 3X2
x2
x1
| Point
(X1,
X2) |
Profit
M = 2X1
+ 3X2 |
Where
from (the point) |
|
| CP1
= (3,
12) |
M
= 2(3)
+ 3(12)
= 42 (cents) |
Put
X1
=
3
in 4X1
+ 3X2 = 48
to
get 4(3)
+ 3X2 = 48,
3X2 = 48
- 12 = 36, X2 = 12 |
|
| CP2
= (8.4,
4.8) |
M
= 2(8.4)
+ 3(4.8)
= 31.2
(cents) |
simultaneously
solve the system 5X1
+ 10X2 = 90
and 4X1
+ 3X2 = 48
(do by hand using the addition or substitution method, or on the TI-83,
use APPS, then PolySmlt (see below)
...on the 86 (get the software from your instructor),
use 2nd POLY and then it is similar to the 83) |
|
| CP3
= (18,
0) |
M
= 2(18)
+ 3(0)
= 36
(cents) |
X1-intercept
for 5X1
+ 10X2 = 90 |
|
Step 3) The ingredient quantities for
the point producing the smallest Cost is the solution
CP2
= (8.4,
4.8),
M = 2(8.4)
+ 3(4.8)
= 31.2
(cents)...Order
8.4 pounds of brand A and 4.8 pounds of brand B per turkey should be ordered for
each turkey per month (for a cost of 31.2 cents per month per turkey. This
will minimize feed costs. end
