SOLVING LPP

USING
GRAPHIC
METHOD
INSTRUCTOR: MILLION A. (PhD can)

August, 2021
GRAPHICAL REPRESENTATION AND
SOLUTION

conditions for Graphical Method

1. Is the problem an LP? Yes, if
and only if:
All variables have power of 1, and they are
added or subtracted (not divided or multiplied).
The constraint must be of the following forms
(≥, ≤, or =, that is, the LP-constraints are
always closed)

2.the
objective must be either
maximization or minimization.
3. Can I use the graphical method? Yes, if the
number of decision variables is either 1 or 2.
06/27/2025 2
CONT…
 Steps for Graphical Solution
A. Corner Point Method

1. Define the problem mathematically

2. Graph by constraints by treating
each inequality as equality.
3. Locate the feasible region and the
corner points.
4. Find out the value of objective
function at these points.
5. Find out the optimal solution and the
optimal value of O.F. if it exists.
06/27/2025 3
CONT…
 Steps for Graphical Solution
 B. Iso-Profit or Iso-Cost Line Method

1. Define the problem mathematically

2. Graph by constraints by treating each inequality
as equality.
3. Locate the feasible region and the corner points.
4. Draw out a line having the slope of Objective
Function Equation (this is called Iso-Cost / Profit
Line in Minimization and Maximization
problems respectively) somewhere in the
middle of the feasible region

06/27/2025 4
CONT…
 Steps for Graphical Solution
Iso-Profit or Iso-Cost Line Method ctd..

 5. Move this line away from origin (in case of

Maximization) or towards Origin (in case of
Minimization) until it touches the extreme
point of the feasible region.
 6.If a single point is encountered, that
reflects optimality and its coordination the
solution. If Iso-Profit/ Cost line coincides with
any constraint line at the extreme, then this
is the case of multiple optimum
solutions.
06/27/2025 5
CONT…
Maximization Problem

Constraints Model A Model B Maximum Available hrs.

(X1) (X2)
Labor hr. 2 1 40
Machine hr. 1 3 45
Marketing hr. 1 0 12
Profit $300 $250

06/27/2025
CONT…
A Maximization Problem

Solution
1. Formulation of mathematical modeling of LPP
Max Z = 300X1 +250X2
St:
 2X1 +X2 < 40
 X1 +3X2 < 45
 X1 < 12
 X1, X2 >0
2. Convert constraints inequalities into
equalities
 2X1 +X2 = 40
 X1 +3X2 = 45
 X1 = 12
06/27/2025 7
CONT…
A Maximization Problem

 Solution

3. Draw the graph by intercepts

2X1 +X2 = 40 ==> (0, 40) and (20, 0)

X1 +3X2 = 45 ==> (0, 15) and (45, 0)
X1 = 12 ==> (12, 0)
X1, X2 = 0

06/27/2025 8
CONT…
 Solution

2X1
X2 +X2
X1=0 =
40
40
X1=12

X1
+X2
B
15 =
45

Feasible C (12, 11)

Region
X2=0
X1
D
A 12 20 45

06/27/2025
9
CONT…
 A Maximization Problem
Solution
 4. Identify the feasible area of the solution which satisfies
all constrains.
 5. Identify the corner points in the feasible region
 A (0, 0), B (0, 15), C (12, 11) and D (12, 0)
 6. Identify the optimal point
 7. Interpret the result
 Corners Coordinates MaxZ=300 X1 +250X2
A (0, 0) $0
B (0, 15) $3750
C (12, 11) $6350
D (12, 0) $3600
Interpretation:
12 units of product A and 11 units of product B should be
produced so that the total profit will be $6350.
06/27/2025 10
CONT…
Example ABE 2.1
Solve using Graphical method
Maximize {w = 2X1 + 5X2 }
Subj. to:
X1 ≤ 4
X2 ≤3
X1 + X 2 ≤6
X1 ≥ , X 2 ≥ 0
06/27/2025 11
 CONT…
 Solving graphically

X1 = 4

(3,3) X2 =3

(4,2)

X1 + x2= 6

06/27/2025
12
CONT…
 Minimization Problem
 Minimize Z with inequalities of constraints in > form
Example:
Suppose that a machine shop has two different types of machines;
machine 1 and machine 2, which can be used to make a single
product .These machine vary in the amount of product produced per
hr., in the amount of labor used and in the cost of operation.
Assume that at least a certain amount of product must be produced
and that we would like to utilize at least the regular labor force. How
much should we utilize each machine in order to utilize total costs
and still meets the requirement? The data are given below.
__________________________________________________________
Resource used
Machine 1 (X1) Machine (X2) Mini. requirement
hrs ____________________________________________________
Product produced/hr 20 15 100
Labor/hr 2 3 15
Operation Cost $25 $30_
06/27/2025 13
FORMULATE THE LP
Min.Z 25 X 130 X 2
St :
20 X 115 X 2100
2 X 13 X 215
X 1 , X 2 0

06/27/2025 14
CONT…
X2
X1 =0

 Optimal solution
A (0, 20/3)

Feasible Region

B (2.5, 3.33)
X2 =0

X1

5 C (7.5, 0)

06/27/2025
15
CONT…
 Final solutions

 Corners Coordinates MinZ=25 X1

+ 30X2
 A (0, 20/3) 200

 B (2.5, 3.33) 162.5
 C (7.5, 0) 187.5

 X1 =2.5
 X2 =3.33 and
 MinZ = 162.5
06/27/2025 16
CONT…
 SPECIAL CASES IN GRAPHICS METHODS
1. Redundant Constraint
 If a constraint when plotted on a graph doesn’t
form part of the boundary making the feasible
region of the problem that constraint is said to be
redundant.

Example:
A firm is engaged in producing two products A and B .Each unit of
product A requires 2Kg of raw material and 4 labor-hrs for
processing. Where as each unit of product B requires 3Kg of raw
materials and 3hrs of labor. Every nit of product A needs 4 hrs and B
needs 3.5hrs for packaging. Every week the firm has availability of
60Kg of raw material, 96 labor-hours and 105 hrs I the packaging
department. 1 unit of product A sold yields $40 profit and 1 unit
of B sod yields $35 profit.
Required:
a. Formulate this problem as a LPP
b. Find the optimal solution
06/27/2025 17
CONT….
 SPECIAL CASES IN GRAPHICS METHODS
 Solution
 ___________________________________________________________
 Products Resource
available
 Resources A B per
week
 _____________________________________________________________
 Raw materials (Kg) 2 3 60
 Labor (hr) 4 3 96
 Packaging (hr) 4 3.5 105

 Profit per unit $40 $35

 Let X1 =The No of units f product A produced
per week
 X2 =The No of units f product B produced
per week
 LPP Model:
06/27/2025 18
CONT…
Max.Z 40 X 135 X 2
St :
2 X 13 X 260
4 X 13 X 296
4 X 1  3.5 X 2 105
X 1 , X 2 0

06/27/2025 19
CONT…
 SPECIAL CASES IN GRAPHICS METHODS

 After drawing the graph, The packaging hr is

redundant.
 Corners Coordinates Zmax =40 X1 + 35X2
 A (0, 0) 0
 B (0, 20) 700
 C (18, 8) 1000
 D (24, 0) 960
 X1 =18
 X2=8 and
 Zmax= 1000
 Interpretation:
 The company should produce and sale 18 units of
product A and 8 units of product B per week so as to
get a maximum profit of 1000.
06/27/2025 20
CONT….
 Possible solutions to LP Problems

Alternative optimal solutions

Unbounded solution
No feasible solution
Degeneracy solution (optional) we will see it
latter

06/27/2025 21
CONT…
 Alternative solution
 (line segment of alternative optimal
solution)

 E.g. Maximize {w = 2X1 + 2X2 }

 Subj. to:
 X1 ≤4
 X2 ≤ 3
 X1 + X 2 ≤6
 X1 ≥ , X 2 ≥ 0
06/27/2025 22
CONT…
 Alternatives solution

X1 = 4

(3,3) X2 =3

(4,2)

X1 + x2= 6

06/27/2025
23
CONT…
Unbounded solution

Eg. Max {W= 4x1 + x2}

Subj. to:
x1 + x2 ≥ 3
-2x2 + 2x2 ≤ 2
X1, x2 ≥ 0

06/27/2025 24
CONT…
 Unbounded soln.

-2x1+2X2 =2
X1 + x2= 3

(1,2)

06/27/2025
25
CONT…
Un LP problem with unbounded feasible
area depends on the objective function
and can be;
 one (finite) solution
 a line segment or half-line
alternative optimal solution
 unbounded

06/27/2025 26
CONT…
No feasible solution

Eg. Max {W= x1 + 4x2}

Subj. to:
x1 ≥4
x2 + x 2 ≤ 3
X 1, x 2 ≥ 0

06/27/2025 27
CONT…
 No feasible solution The feasible area is
empty, therefore, no
feasible solution
x1 = 4

X1 + x2= 3

06/27/2025
28
CONT…
Binding (active) and non binding (in
active) constraints
From the ABE example,
Constraint x1 ≤ 4 is non binding
The other two are binding namely:
X2 ≤ 3
X1 + X2 ≤ 6 are
binding

06/27/2025 29