How To Solve Problem by Using Graphical Method

How to solve problem by using
graphical Method
 Find-out decision variables
 Write objective function
 Write constraint function
 Convert the constraint function in to equality form by
converting < or > to =.
 Solve each constraint for each product to get
quadrant for the graph
 Feasible solution is the region within the constraints
 Optimal solution is the one where both the line
intersects each other
Copyright © 2012 Pearson Education 7-1

Flair Furniture Company Data
The company wants to determine the best
combination of tables and chairs to produce to reach
the maximum profit.
HOURS REQUIRED TO
PRODUCE 1 UNIT
(T) (C) AVAILABLE HOURS
DEPARTMENT TABLES CHAIRS THIS WEEK
Carpentry 4 3 240
Painting and varnishing 2 1 100
Profit per unit $70 $50
Table 7.2

Flair Furniture Company
 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.
 The decision variables representing the actual
decisions we will make are:
T = number of tables to be produced per week.
C = number of chairs to be produced per week.

 We create the LP objective function in terms of T
and C:
Maximize profit = $70T + $50C
 Develop mathematical relationships for the two
constraints:
 For carpentry, total time used is:
(4 hours per table)(Number of tables produced)
+ (3 hours per chair)(Number of chairs
produced).
 We know that:
Carpentry time used ≤ Carpentry time available.
4T + 3C ≤ 240 (hours of carpentry time)

 Similarly,
Painting and varnishing time used
≤ Painting and varnishing time available.
2 T + 1C ≤ 100 (hours of painting and varnishing time)
This means that each table produced

requires two hours of painting and
varnishing time.
 Both of these constraints restrict production

capacity and affect total profit.

The values for T and C must be nonnegative.
T ≥ 0 (number of tables produced is greater
than or equal to 0)
C ≥ 0 (number of chairs produced is greater
than or equal to 0)
The complete problem stated mathematically:

Maximize profit = $70T + $50C
subject to
4T + 3C ≤240 (carpentry constraint)
2T + 1C ≤100 (painting and varnishing constraint)
T, C ≥ 0 (nonnegativity constraint)
Graphical Solution to an LP Problem
 The easiest way to solve a small LP

problems is graphically.
 The graphical method only works when
there are just two decision variables.
 When there are more than two variables, a
more complex approach is needed as it is
not possible to plot the solution on a two-
dimensional graph.
 The graphical method provides valuable
insight into how other approaches work.

Graphical Representation of a
Constraint
Quadrant Containing All Positive Values
C
100 –
– This Axis Represents the Constraint T ≥ 0
Number of Chairs
80 –
–
60 –
–
40 – This Axis Represents the
– Constraint C ≥ 0
20 –
–
|– | | | | | | | | | | |
Figure 7.1 0 20 40 60 80 100 T
Number of Tables
Constraint
 The first step in solving the problem is to
identify a set or region of feasible
solutions.
 To do this we plot each constraint
equation on a graph.
 We start by graphing the equality portion
of the constraint equations:
4T + 3C = 240
 We solve for the axis intercepts and draw
the line.

Constraint
 When Flair produces no tables, the
carpentry constraint is:
4(0) + 3C = 240
3C = 240
C = 80
 Similarly for no chairs:
4T + 3(0) = 240
4T = 240
T = 60
 This line is shown on the following graph:

Constraint
Graph of carpentry constraint equation
C
100 –
–
(T = 0, C = 80)
Number of Chairs
80 –
–
60 –
–
40 –
–
(T = 60, C = 0)
20 –
–
Figure 7.2 |– | | | | | | | | | | |
0 20 40 60 80 100 T
Copyright © 2012 Pearson Education Number of Tables 7-11
Constraint
 When Flair produces no tables, the
painting constraint is:
2T + 1C = 100
2(0)+1(C)=100
C=100
 Similarly for no chairs:
2T + 1C = 100
2(T)+1(0)=100
C=50
 This line is shown on the following graph:

Constraint
Region that Satisfies the Painting and
Varnishing Constraint
C
100 – (T = 0, C = 100)
–
Number of Chairs
80 –
–
60 –
–
40 –
–
(T = 50, C = 0)
20 –
–
Figure 7.4 |– | | | | | | | | | | |
0 20 40 60 80 100 T
Copyright © 2012 Pearson Education Number of Tables 7-13
Constraint
 To produce tables and chairs, both

departments must be used.
 We need to find a solution that satisfies both
constraints simultaneously.
 A new graph shows both constraint plots.
 The feasible region (or area of feasible
solutions)
solutions is where all constraints are satisfied.
 Any point inside this region is a feasible
solution.
 Any point outside the region is an infeasible
solution.

Constraint
Feasible Solution Region for the Flair
Furniture Company Problem
C
100 –
–
Number of Chairs
80 – Painting/Varnishing Constraint
–
60 –
–
40 –
–
Carpentry Constraint
20 – Feasible
Region
–
|– | | | | | | | | | | |
Figure 7.5
0 20 40 60 80 100 T
Number of Tables
Optimal profit Line Solution
Method
Optimal Solution to the Flair Furniture problem
C
100 –
–
Number of Chairs
80 –
Maximum Profit Line
–
60 – Optimal Solution Point
– (T = 30, C = 40)
40 –
– $4,100 = $70T + $50C
20 –
–
Figure 7.8 |– | | | | | | | | | | |
0 20 40 60 80 100 T
Copyright © 2012 Pearson Education
Number of Tables 7-16
Constraint
 For the point (30, 20)
Carpentry 4T + 3C ≤ 240 hours available

constraint (4)(30) + (3)(20) = 180 hours used 
Painting 2T + 1C ≤ 100 hours available
constraint (2)(30) + (1)(20) = 80 hours used


constraint (4)(70) + (3)(40) = 400 hours used 

Constraint

constraint (4)(50) + (3)(5) = 215 hours used 

Method
 For Flair Furniture, choose a profit of $2,100.
 The objective function is then
$2,100 = 70T + 50C
 Solving for the axis intercepts, we can draw the
graph.
 This is obviously not the best possible solution.
 Further graphs can be created using larger profits.
 The further we move from the origin, the larger the
profit will be.
 The highest profit ($4,100) will be generated when
the isoprofit line passes through the point (30, 40).

Method
Optimal Solution to the Flair Furniture problem
C
100 –
–
Number of Chairs
80 –
Maximum Profit Line
–
60 – Optimal Solution Point
– (T = 30, C = 40)
40 –
– $4,100 = $70T + $50C
20 –
–
Figure 7.8 |– | | | | | | | | | | |
0 20 40 60 80 100 T
Copyright © 2012 Pearson Education
Number of Tables 7-20
Corner Point Solution Method
 A second approach to solving LP problems
employs the corner point method.
 It involves looking at the profit at every
corner point of the feasible region.
 The mathematical theory behind LP is that
the optimal solution must lie at one of the
corner points,
points or extreme point,
point in the
feasible region.
 For Flair Furniture, the feasible region is a
four-sided polygon with four corner points
labeled 1, 2, 3, and 4 on the graph.
Four Corner Points of the Feasible Region
C
100 –
2 –
Number of Chairs
80 –
–
60 –
–
3
40 –
–
20 –
–
1 |– | | | | | | | | | | |
Figure 7.9
0 20 40
4 60 80 100 T
Number of Tables
 To find the coordinates for Point 3 accurately we have to
solve for the intersection of the two constraint lines.
 Using the simultaneous equations method,
method we multiply the
painting equation by –2 and add it to the carpentry equation
4T + 3C = 240 (carpentry line)
– 4T – 2C = –200 (painting line)
C = 40
 Substituting 40 for C in either of the original equations
allows us to determine the value of T.
4T + (3)(40) = 240 (carpentry line)
4T + 120 = 240
T = 30
Point 1 : (T = 0, C = 0) Profit = $70(0) + $50(0) = $0
Point 2 : (T = 0, C = 80) Profit = $70(0) + $50(80) =
$4,000
4
Point : (T = 50, C = 0) Profit = $70(50) + $50(0) =
3
$3,500
Point : (T = 30, C = 40) Profit = $70(30) + $50(40) =
Because
$4,100 Point 3 returns the highest profit, this is
the optimal solution.

Summary of Graphical Solution
Methods
SIMPLE GRAPHICAL METHOD
1. Graph all constraints and find the feasible region.
2. Select a specific profit (or cost) line and graph it to find the slope.
3. Move the objective function line in the direction of increasing profit (or
decreasing cost) while maintaining the slope. The last point it touches in the
feasible region is the optimal solution.
4. Find the values of the decision variables at this last point and compute the
profit (or cost).
CORNER POINT METHOD
1. Graph all constraints and find the feasible region.
2. Find the corner points of the feasible reason.
3. Compute the profit (or cost) at each of the feasible corner points.
4. Select the corner point with the best value of the objective function found in
Step 3. This is the optimal solution.
Table 7.4

LP Model Formulation
A Maximization Example (4 of 4)
Complete Linear Programming Model:
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2  40

4x1 + 3x2  120
x 1, x 2  0
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall

Feasible Solutions
A feasible solution does not violate any of the

constraints:
Example: x1 = 5 bowls
x2 = 10 mugs
Z = $40x1 + $50x2 = $700
Labor constraint check: 1(5) + 2(10) = 25 < 40

hours
Clay constraint check: 4(5) + 3(10) = 50 < 120
pounds
Infeasible Solutions
An infeasible solution violates at least one of

the constraints:
Example: x1 = 10 bowls
x2 = 20 mugs
Z = $40x1 + $50x2 = $1400
Labor constraint check: 1(10) + 2(20) = 50 >

40 hours

Graphical Solution of LP Models
 Graphical solution is limited to linear programming

models containing only two decision variables (can
be used with three variables but only with great
difficulty).
 Graphical methods provide visualization of how a

solution for a linear programming problem is
obtained.

Coordinate Axes
Graphical Solution of Maximization Model (1
of 12)
X2 is mugs

4x2 + 3x2  120
x1, x2  0
X1 is bowls
Figure 2.2 Coordinates for Graphical
Analysis
Labor Constraint
of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.3 Graph of Labor

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall Constraint
Labor Constraint Area
of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.4 Labor Constraint

Area
Clay Constraint Area
of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.5 Clay Constraint

Area
Both Constraints
of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.6 Graph of Both Model

Constraints
Feasible Solution Area
of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.7 Feasible Solution

Area
Objective Function Solution = $800
of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.8 Objection Function Line for Z

= $800
Alternative Objective Function Solution Lines
Graphical Solution of Maximization Model (8 of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.9 Alternative Objective Function

Lines
Optimal Solution
of 12)

4x2 + 3x2  120
x1, x2  0
Figure 2.10 Identification of Optimal Solution

Point
Optimal Solution Coordinates
Graphical Solution of Maximization Model (10 of
12)

4x2 + 3x2  120
x1, x2  0
Figure 2.11 Optimal Solution

Coordinates
Extreme (Corner) Point Solutions
Graphical Solution of Maximization Model (11 of
12)

4x2 + 3x2  120
x1, x2  0
Figure 2.12 Solutions at All Corner

Points
LP Model Formulation – Minimization (1 of 8)
 Two brands of fertilizer available - Super-gro, Crop-

quick.
 Field requires at least 16 pounds of nitrogen and 24
pounds of phosphate.
 Super-gro costs $6 per bag, Crop-quick $3 per bag.
 Problem: How much of each brand to purchase to
minimize total cost of fertilizer given
Chemical following data ?
Contribution
Nitrogen Phosphate
Brand
(lb/ bag) (lb/ bag)
Super-gro 2 4
Crop-quick 4 3

LP Model Formulation – Minimization (2 of 8)
Figure 2.15 Fertilizing

farmer’s field

LP Model Formulation – Minimization (3 of
8)
Decision Variables:
x1 = bags of Super-gro
x2 = bags of Crop-quick
The Objective Function:

Minimize Z = $6x1 + 3x2
Where: $6x1 = cost of bags of Super-
Gro
$3x2 = cost of bags of Crop-Quick
Model Constraints:
2x1 + 4x2  16 lb (nitrogen constraint)
4x1 + 3x2  24 lb (phosphate constraint)
x1, x2  0 (non-negativity constraint)
Constraint Graph – Minimization (4 of
8)
Minimize Z = $6x1 + $3x2

subject to: 2x1 + 4x2  16
4x2 + 3x2  24
x1, x2  0
Figure 2.16 Graph of Both Model

Constraints
Feasible Region– Minimization (5 of 8)

4x2 + 3x2  24
x1, x2  0
Figure 2.17 Feasible Solution

Area
Optimal Solution Point – Minimization (6 of
8)

4x2 + 3x2  24
x1, x2  0
Figure 2.18 Optimum Solution

Point
Problem Statement
Example Problem No. 1 (1 of 3)
■ Hot dog mixture in 1000-pound batches.

■ Two ingredients, chicken ($3/lb) and beef
($5/lb).
■ Recipe requirements:
at least 500 pounds of
“chicken”
at least 200 pounds of “beef”
■ Ratio of chicken to beef must be at least 2 to 1.
■ Determine optimal mixture of ingredients that
will minimize costs.
Solution
Step 1:
Identify decision variables.
x1 = lb of chicken in mixture
x2 = lb of beef in mixture
Step 2:
Formulate the objective function.
where Z = cost per 1,000-lb batch
$3x1 = cost of chicken
$5x2 = cost of beef
Solution
Step 3:
Establish Model Constraints
x1 + x2 = 1,000 lb
x1  500 lb of chicken
x2  200 lb of beef
x1/x2  2/1 or x1 - 2x2  0
x1, x2  0
The Model: Minimize Z = $3x1 + 5x2
subject to: x1 + x2 = 1,000 lb
x1  500
x2  200
x1 - 2x2  0
Solve the following model

graphically:
Maximize Z = 4x1 + 5x2
subject to: x1 + 2x2  10
6x1 + 6x2  36
x1  4
x1, x2  0
Step 1: Plot the

constraints as equations
Figure 2.23 Constraint

Equations

6x1 + 6x2  36
x1  4
x1, x2  0
Step 2: Determine the
feasible solution space
Figure 2.24 Feasible Solution Space and

Extreme Points

6x1 + 6x2  36
x1  4
x1, x2  0
Step 3 and 4: Determine
the solution points and
optimal solution
Figure 2.25 Optimal Solution

Point

How To Solve Problem by Using Graphical Method

Uploaded by

Copyright:

Available Formats

How To Solve Problem by Using Graphical Method

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

How To Solve Problem by Using Graphical Method

Uploaded by

Copyright:

Available Formats

How to solve problem by using

Copyright © 2012 Pearson Education 7-1

Painting and varnishing 2 1 100

Profit per unit $70 $50

Copyright © 2012 Pearson Education 7-2

Copyright © 2012 Pearson Education 7-3

Copyright © 2012 Pearson Education 7-4

This means that each table produced

 Both of these constraints restrict production

Copyright © 2012 Pearson Education 7-5

The complete problem stated mathematically:

 The easiest way to solve a small LP

Copyright © 2012 Pearson Education 7-7

Copyright © 2012 Pearson Education 7-9

Copyright © 2012 Pearson Education 7-10

Copyright © 2012 Pearson Education 7-12

 To produce tables and chairs, both

Copyright © 2012 Pearson Education 7-14

Carpentry 4T + 3C ≤ 240 hours available

 For the point (70, 40)

Carpentry 4T + 3C ≤ 240 hours available

Copyright © 2012 Pearson Education 7-17

Carpentry 4T + 3C ≤ 240 hours available

Copyright © 2012 Pearson Education 7-18

Copyright © 2012 Pearson Education 7-19

Copyright © 2012 Pearson Education 7-24

Copyright © 2012 Pearson Education 7-25

Complete Linear Programming Model:

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall

A feasible solution does not violate any of the

Labor constraint check: 1(5) + 2(10) = 25 < 40

An infeasible solution violates at least one of

Labor constraint check: 1(10) + 2(20) = 50 >

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall

 Graphical solution is limited to linear programming

 Graphical methods provide visualization of how a

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall

Maximize Z = $40x1 + $50x2

Maximize Z = $40x1 + $50x2

Figure 2.3 Graph of Labor

Maximize Z = $40x1 + $50x2

Figure 2.4 Labor Constraint

Maximize Z = $40x1 + $50x2

Figure 2.5 Clay Constraint

Maximize Z = $40x1 + $50x2

Figure 2.6 Graph of Both Model

Maximize Z = $40x1 + $50x2

Figure 2.7 Feasible Solution

Maximize Z = $40x1 + $50x2

Figure 2.8 Objection Function Line for Z

Maximize Z = $40x1 + $50x2

Figure 2.9 Alternative Objective Function

Maximize Z = $40x1 + $50x2

Figure 2.10 Identification of Optimal Solution

Maximize Z = $40x1 + $50x2

Figure 2.11 Optimal Solution

Maximize Z = $40x1 + $50x2