‫ﻛﻠﯿﺔ اﻟﻜﻨﻮز اﻟﺠﺎﻣﻌﺔ‬

‫ﻗﺴﻢ ھﻨﺪﺳﺔ ﺗﻘﻨﯿﺎت اﻟﺤﺎﺳﻮب‬

Project Management
Chapter 7
Graphical Solution of Linear Programming Problems
4th Stage
Fall Semester 2023 – 2024
Prof. Dr. Taleb Obaid
 Graphical Method
Q1. For Max Z = 30 X1 + 10 X2 , and the points of feasible region bounded by the following points.
Points P1(0, 0) , P2(0,12), P3(10,0), P4(6, 8)
The Maximum value of Z is at Point
A. P1
B. P2
C. P3
D. P4 Fes. Point x y z
P1 0 0 0
P2 0 12 120
P3 10 0 300
P4 6 8 260

Prof. Dr. Taleb Obaid 2

 Graphical Method
• Linear programming is the simplest way of optimizing a problem.
• We can formulate a real-world problem into a mathematical model.
• Generally, LP used for the problem in which we have to maximize
profit, minimize cost, or to minimize the use of resources.
Some commonly used terms in linear programming problems are:
Objective function: The direct function of form Z = ax + by,
where a and b are constant, which is reduced or enlarged is called the
objective function.
Prof. Dr. Taleb Obaid 3
 Graphical Method
For example, If the object function

Z = 10x + 7y.

The variables x and y are called the decision variable.

Constraints: The restrictions that are applied to a linear inequality are

called constraints.

• Non-negative constraints: x ≥ 0, y ≥ 0 etc.

• General constraints: x + y > 40, 2x + 9y ≥ 40 etc.

Prof. Dr. Taleb Obaid 4

 Graphical Method
Optimization problem: A problem that seeks to maximization or minimization of
variables of linear inequality problem is called optimization problems.

•Feasible region: A common region determined by all given issues including the
non-negative (x ≥ 0, y ≥ 0) constrain is called the feasible region (or solution area)
of the problem. The region other than the feasible region is known as the infeasible
region.

•Feasible Solutions: These points within or on the boundary region represent

feasible solutions of the problem. Any point outside the scenario is called an
infeasible solution.

Prof. Dr. Taleb Obaid 5

 Graphical Method
Optimal (most feasible) solution: Any point in the emerging region that provides
the right amount (maximum or minimum) of the objective function is called the
optimal solution.

Theorem 1: Let us considered Y be the feasible region (convex polygon) for a

linear programming problem, i.e. Y = ax + by (objective function). So, when Y has
an optimal value (maximum or minimum), where x and y are subject to constraints
described by linear inequalities, then this optimal value occurs at corner points of
the feasible region, i.e., vertices.

Prof. Dr. Taleb Obaid 6

 Limitation of Graphical Methods
•Graphical solution is limited to linear programming models containing only two
decision variables.

Procedure
Step I: Convert each inequality as equality
Step II: Plot each equation on the graph
Step III: Shade the ‘Feasible Region’. Highlight the common Feasible region.
Feasible Region: Set of all possible solutions.
Step IV: Compute the coordinates of the corner points (of the feasible region).
These corner points will represent the ‘Feasible Solution’.

Prof. Dr. Taleb Obaid 7

 Limitation of Graphical Methods
These corner points will represent the ‘Feasible Solution’.

Feasible Solution: If it satisfies all the constraints and non-negativity restrictions.

Step V: Substitute the coordinates of the corner points into the objective function
to see which gives the Optimal Value. That will be the ‘Optimal Solution’.
❑ Optimal Solution: If it optimizes (maximizes or minimizes) the objective
function.
❑ Unbounded Solution: If the value of the objective function can be increased or
decreased indefinitely, Such solutions are called Unbounded solution.

❑ Infeasible (Inconsistent) Solution: It means the solution of problem does not

exist. This is possible when there is no common feasible region
Prof. Dr. Taleb Obaid 8
 Graphical Methods
Example
Max z = 5x1 + 7x2
Subject to:
x1 ≤6
2x1 + 3x2 ≤ 18
x1 + x2 ≤ 8
x1 , x2 ≥ 0

Prof. Dr. Taleb Obaid 9

 Graphical Methods
Example Now calculate Z ate each polygon
Max z = 5x1 + 7x2 vertices:
Subject to: ZA = Z(0,0), 5*0 + 7*0 , ZA = 0
x1 ≤ 6 ……. 1)
2x1 + 3x2 ≤ 18 ……. 2)
ZB = Z(6,0) , ZB = 30
x1 + x2 ≤ 8 …….. 3)
ZC = Z(6,2) , ZC = 44
x1 , x2 ≥ 0
The intersection points are: A, B, C, D ,E, F ZE = Z(0,6) , ZC = 42
The coordinate of these points are: So the optimize solution is Zc = 44 at the
A(0,0), B(6,0), C(6,2), E(0,6), calculate D point C(6, 2)
coordinate by intersect eq. 2) and 3) →(6,2)

Prof. Dr. Taleb Obaid 10

 Graphical Methods
Question 1. Solve the given linear A(0,0), B(30,0), C(20,20), D(0,30)
programming problems graphically:
Maximize: Z = 8x + y Vertex Z
and the constraints are : A(0,0) 0
x + y ≤ 40, B(30,0) 240

2x + y ≤ 60, C(20,20) 180

D(0,30) 30
x ≥ 0, y ≥ 0
Solution: The Objective function is:
Step 1: Constraints are : Z=240 at a vertex B
x + y ≤ 40, …….. 1)
2x + y ≤ 60, …….. 2)
x ≥ 0, y ≥ 0
Prof. Dr. Taleb Obaid 11
 Graphical Methods
Step 2: Draw the graph using these constraints.

Here both the constraints are less than or equal to, so they satisfy the below region
(towards origin). You can find the vertex of feasible region by graph, or you can
calculate using the given constraints:
Prof. Dr. Taleb Obaid 12
 Graphical Methods
x + y = 40 …(i)
2x + y = 60 …(ii)
Now multiply eq(i) by 2 and then subtract both eq(i) and (ii), we get y = 20
Now put the value of y in any of the equations, we get x = 20
So the third point of the feasible region is (20, 20)
Step 3: To find the maximum value of Z = 8x + y. Compare each intersection
point of the graph to find the maximum value
Points Z = 8x + y
(0,0) 0
(0, 40) 40
(20, 20) 180
(30, 0) 240
Prof. Dr. Taleb Obaid 13
 Graphical Methods
Example

Maximize: Z = 3x + 2y

subject to:

2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x≥0,y≥0

Prof. Dr. Taleb Obaid 14

 Graphical Methods
Maximize: Z = 3x + 2y

subject to:

2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x≥0,y≥0

The maximum value of the objective function is 33, and it corresponds to the
values x = 3 and y = 12 (G-vertex coordinates).

Prof. Dr. Taleb Obaid 15

 Graphical Methods
https://www.brainkart.com/article/Solution-of-LPP-by-graphical-method_37041/
Example 10.6
Solve the following LP by graphical method
Minimize z = 5x1+4x2
Subject to constraints
4x1+ x2 ≥ 40 ;
2x1+3x2 ≥ 90 and
x1, x2 > 0
Solution:
Since both the decision variables x1 and x2 are non-negative, the solution lies in
the first quadrant of the plane.
Consider the equations 4x1+x2 = 40 and 2 x1+3 x2 = 90

Prof. Dr. Taleb Obaid 16

 Graphical Methods
https://www.brainkart.com/article/Solution-of-LPP-by-graphical-method_37041/
4x1+x2 = 40 is a line passing
through the points (0,40) and
(10,0).Any point lying on or above
the line 4x1+x2= 40 satisfies the
constraint 4x1+ x2 ≥ 40.
2x1+3x2 = 90 is a line passing
through the points (0,30) and
(45,0). Any point lying on or above
the line 2 x1+3x2= 90 satisfies the
constraint 2x1+3x2 ≥ 90.
Draw the graph using the given
constraints.
Prof. Dr. Taleb Obaid 17
 Graphical Methods
https://www.brainkart.com/article/Solution-of-LPP-by-graphical-method_37041/
The feasible region is ABC (since the problem is of minimization type
we are moving towards the origin.

The minimum value of Z occurs at B(3,28).

Hence the optimal solution is x1 = 3, x2 = 28 and Z min=127

Prof. Dr. Taleb Obaid 18

 Graphical Methods
Example 10.7
Solve the following LPP.
Maximize Z= 2 x1 +3x2
subject to constraints
x1 + x2 ≤ 30 ;
x2 ≤ 12; x1 ≤ 20 and
x1, x2≥ 0
Solution:
We find the feasible region using the given conditions. Since both the decision
variables x1 and x2 are non-negative, the solution lies in the first quadrant of the
plane. Write all the inequalities of the constraints in the form of equations.
Therefore we have the lines

Prof. Dr. Taleb Obaid 19

 Graphical Methods
x1+x2=30;
x2 =12; x1= 20
x1+x2 =30 is a line passing through the points (0,30) and (30,0)
x2 = 12 is a line parallel to x1–axis
x1 = 20 is a line parallel to x2–axis.

The feasible region satisfying all the conditions x1+ x2≤ 30; x2≤ 12 ; x1≤ 20 and x1 ,
x2 ≥ 0 is shown in the following graph.

Prof. Dr. Taleb Obaid 20

 Graphical Methods

Prof. Dr. Taleb Obaid 21

 Graphical Methods
The feasible region satisfying all the conditions is OABCD.
The co-ordinates of the points are O(0,0) ; A(20,0); B(20,10) ; C(18,12)
and D(0,12).

Maximum value of Z occurs at C. Therefore the solution is x1 = 18 , x2=

12, Z max = 72

Prof. Dr. Taleb Obaid 22

 Graphical Methods/
Example 10.8
Maximize Z = 3x1 + 4x2
subject to
x1 – x2 < –1;
–x1+x2 < 0 and
x1, x2 ≥ 0
Solution:
Since both the decision variables x1, x2 are non-negative ,the solution
lies in the first quadrant of the plane.
Consider the equations x1– x2 = –1 and – x1 + x2 = 0
Prof. Dr. Taleb Obaid 23
 Graphical Methods
x1– x2 =–1 is a line passing through the points (0,1) and (–1,0)
–x1 + x2 = 0 is a line passing through the point (0,0)
Now we draw the graph satisfying the conditions x1 – x2 < –1; –x1+x2 <
0 and x1, x2≥0

There is no common region

(feasible region) satisfying
all the given conditions.
Hence the given LPP has
no solution.
Prof. Dr. Taleb Obaid 24
 Graphical Methods, e.g.
Minimize: Z = 20x + 10y So we take eq(i), now in this equation
and the constraints are : When x = 0, then y = 20
L1: x + 2y ≤ 40, and when y = 0, then x = 40
L2: 3x + y ≥ 30,
So, points are (0, 20) and (40, 0)
L3: 4x + 3y ≥ 60,
x ≥ 0, y ≥ 0 Similarly, in eq(ii)
Solution: When x = 0, then y = 30
Step 1: Finding points When y = 0, then x = 10
We can also write as So, points are (0, 30) and (10, 0)
l1 = x + 2y = 40 ….(i)
Similarly, in eq(iii)
l2 = 3x + y = 30 ….(ii)
l3 = 4x + 3y = 60 ….(iii) When x = 0, then y = 20
Now we find the points When y = 0, then x = 15
So, points are (0, 20) and (15, 0)
Prof. Dr. Taleb Obaid 25
 Graphical Methods, e.g.
Step 2: Now plot these points in As you can see from the graph at point
A is a intersect lines l2 and l3 , so we
the graph and find the feasible find the coordinate of point A by
region. solving these equations.
l2 : 3x + y = 30 ….(iv)
l3 : 4x + 3y = 60 ….(v)
Now multiply eq (iv) with 4 and
eq(v) with 3, we get
D
12x + 4y = 120
A
C
12x + 9y = 180
B Now subtract both the equation
we get coordinates A(6, 12)

Prof. Dr. Taleb Obaid 26

 Graphical Methods, e.g.
Point B is intersect L3: 4x + 3y = 60 The feasible solution of objective
with x-axis, so B(15, 0) function, Z = 20x + 10y :
Point C is intersect L1: x + 2y = 40 ZA(6, 12) = 240
with x-axis, C(40, 0) ZB(15, 0) = 300
Point D is intersect L1 : x + 2y = 40 ZC(40, 0) =800
and L2: 3x + y = 30
ZD(4, 18) = 260
Now multiply L1 by 3 , and
The optimal solution is 240 at A
subtract from L2,
3x +6y = 120
3x + y = 30
To get D( 4 , 18)
Prof. Dr. Taleb Obaid 27
 Graphical Methods, e.g.
Solve by using graphical method The second constraint x1=4.5
Max Z = 4x1 + 3x2
Subject to The third constraint x2=6
4x1+ 3x2 ≤ 24
x1 ≤ 4.5
x2 ≤ 6
x1 ≥ 0 , x2≥ 0
Solution
The first constraint 4x1+ 3x2 ≤ 24
Written in in a form of equation
4x1+ 3x2 = 24
Put x1= 0, then x2=9
Put x2=0, then x1=6
The coordinate are (0, 8) and (6,0)
Prof. Dr. Taleb Obaid 28
 Graphical Methods, e.g.
The corner points of feasible region We know that Max Z = 4x1++3x2
are A, B, C and D. So the At A (0, 6)
coordinates for the corner points Z = 4(0) + 3(6) = 18
are A (0, 6) , B (1.5, 6) At B (1.5, 6)
(Solve the two equations 4x1 +3x2= Z = 4(1.5) + 3(6) = 24
24 and x = 6 to get the coordinates) At C (4.5, 2)
C (4.5, 2) Z = 4(4.5) + 3(2) = 24
(Solve the two equations 4x1+ 3x2 At D (4.5, 0)
Z = 4(4.5) + 3(0) = 18
= 24 and x2 = 4.5 to get the
coordinates) D (4.5, 0) Max Z = 24, which is achieved at both
B and C corner points. It can be
achieved not only at B and C but every
point between B and C. Hence the given
problem has multiple optimal solutions.
Prof. Dr. Taleb Obaid 29
 Graphical Methods, e.g.
No Optimal Solution The second constraint
Solve graphically x1 + x2 ≥ 3, written in a form of
Max Z=3x1 + 2x2 equation x1+x2=3
Subject to Put x1=0, then x2=3
x1 + x2 ≤ 1 Put x2=0, then x1=3
x1 + x2 ≥ 3 The coordinates are (0,3), and (3,0)
x1 ≥ 0 , x2 ≥ 0 • There is no common feasible region
Solution generated by two constraints together
i.e. we cannot identify
The first constraint x1 + x2 ≤ 1
• even a single point satisfying the
Put x1=0, the x2=1 constraints. Hence there is no optimal
Put x2=0, the x1=1 solution
The coordinates are (0, 1) and (1, 0)
Prof. Dr. Taleb Obaid 30
 Graphical Methods, e.g.

Prof. Dr. Taleb Obaid 31

 Graphical Methods, e.g.
Unbounded Solution The coordinates of third constraint are
Example (0, 3) and (9, 0)

Solve by graphical method

Max Z = 3x1 + 5x2
Subject to
2x1 + x2 ≥ 7
x1+ x2 ≥ 6
x1 + 3 x2 ≥ 9
x1 ≥ 0, x2 ≥0
The coordinates of the first constraint are
(0, 7) and (3.5, 0)
The coordinates of the second constraint
are (0, 6) and (6, 0)
Prof. Dr. Taleb Obaid 32
 Graphical Methods, e.g.
The corner points of feasible region are The values of objective function at corner
A, B, C and D. So the coordinates for the
points are 35, 28, 21 and 27.
corner points
are But there exists infinite number of points in
A (0, 7), B(1, 5), C(4.5, 1.5), D(9,0) the feasible region which is unbounded.
At A (0, 7), Z = 3(0) + 5(7) = 35 The value of objective function will be
At B (1, 5), Z = 3(1) + 5(5) = 28
more than the value of these four corner
At C (4.5, 1.5) , Z = 3(4.5) + 5(1.5) = 21
points i.e. the maximum value of the
At D (9, 0), Z = 3(9) + 5(0) = 27
objective function occurs at a point at ∞.
Hence the given problem has unbounded
solution.

Prof. Dr. Taleb Obaid 33

za 49.5
zb 145.36
zc
zd
78
144
Graphical Methods, e.g.
Max z = 3x1 + 10x2
s.t .
L1: x1 + 4x2 ≥ 20
L2: x1 + 20x2 ≤ 80
L3: 2x1 + 35 x2 ≥ 70
L4: x1 –25x2 ≤ 50
A
X1 ≥ 0, x2 ≥0
L1: (0, 5) , ( 20, 0)
L2: (0 , 4), ( 80, 0)
E
L3: (0, 2), ( 35, 0) B

L4: (0, -2), (50, 0) C D

A(4,3.75), B (16.12,0,97), C(26,0), D(48,0), f(66.7,0.67)
ZA=49.5, ZB=145.36, ZC=78, ZD=144, ZF =206.8

Prof. Dr. Taleb Obaid 34