Graphical Solution of Problems in Operation Research

University of Duhok
College of Basic Education
Department of Mathematics
Graphical solution of problems in operation research
A report submitted by
Khawla Hussein Haji
Supervised by
Dr. Sizar Abid Mohammed

1 . introduction
If the quantity to be maximized/minimized can be written as a linear
combination of the variables, it is called a linear objective function. Linear
programming is the business of finding a point in the feasible set for the
constraints, which gives an optimum value (maximum or a minimum) for the
objective function.
The graphical method considered as an easy or simple method to
process a problems of linear programing , in particular this problem that has
no increasing at two or three variable and has contain the simple’s number of
restrictions . This method can be using as an introduction to study another
method has so difficult for solving a problems of linear programing , as
simplex method .
We’ll see how a linear programming problem can be solved graphically
2 . graphically
Definition 2.1 : Closed Half Plane
A linear inequality in two variables is known as a half plane. The
corresponding equality or the line is known as the boundary of the half
plane. The half plane along with its boundary is called a closed half plane.
Thus, a closed half plane is a linear inequality in two variables, which
include the value of the variable for which equality is attained.
Definition 2.2 : Feasible Solution
Any non-negative solution which satisfies all the constraints is known
as a feasible solution of the problem.
Definition 2.3 : Feasible Region
The collection of all feasible solutions is known as a feasible region.
Steps graph method 2.4 :
1. Draw the X1, -axis and X2 (The positive part of each)
x2
The positive part
of each
x1 +,+
x1
jjjjjjjjjjjj
2. Transfer restrictions to equation.

3.Specify two points for each straight (equation).
4. Drawing lines expressing the equations.
5. Determine the feasible available.
6. Determine the optimal solution (maximization or minimization)
Example 2.5 :
Find the optimal solution for the following LP by using graphical mothed:
Objective function Max Z= 10X1+ 40 X2
S.t X1 + 2X2 ≤ 100

X1 + 5X2 ≤ 150
Non negative X1, X2 ≥0 Solution:

(1) Transfer restrictions to equation as follows
The straight 1 X1 + 2X2 = 100
The straight 2 X1 + 5X2 = 150
Straight 1 Straight 2
X1 X2 X1 X2
0 50 0 30
100 0 150 0
(2) Determine of two points for each straight:
Can be drawn straight 1 and the straight 2
X2
Straight 1
50 100=2X2+X1
D
30
Straight 2
C 150=5X2+X1
16.6
A
B 150
(0) X1
50 66.6 100
(3) The joint solution, an area ( A B C D ) shaded.

The objective function is tested at these points, ( A B C D )
- Extreme Points [Points (C)]
It is the intersection of the straight 1 and the straight 2. x1 +2x2=100
x1 +5x2=150
Using a calculator : x2 =
x1 = 66.7 16.7
Point X1 X2 Z=10 x1+40 x2 The result
C 66.7 16.7 16.7 ×40 +66.7 ×10 1335
Example 2.6 :
Find the optimal solution (writing and draw book) by using graphical
method :
Max Z = 12 x1+ 14 x2
Subject to:
2 x1 +3 x2 ≤ 24
2 x1+ 1 x2 ≤ 16
x1 ≤ 7
x2 ≤ 6 x 1 , x2 ≥ 0
Solution:
Straight 1 Straight 2
2X1 +3X2 =24 2X1 +X2 =16
X1 X2 X1 X2
0 8 0 16
12 0 8 0
Straight 3
Straight 4
X1 =7
X2 =6
X1 X2
7 6
- -
The joint solution, an area (A B C D E F) shaded

Find Extreme Points (C D E):
1- Point (E) is intersection of the straight 1 and the straight 4:
x2 = 6 2x1+3x=24 So (x2 =6 , x1 = 3)
2- Point (D) is intersection ofthe straight 1 and the

straight 2.
2 x1+ 3x2 = 24
2 x1+ x2= 16
Use a calculator
( x1 =6 , x2 =4 )
3- Point (C) is intersection of the straight 2 and the straight 3:
x1=7 2x1+x2= 16 So (x1 =7 , x2 =2)
Point X1 X2 Z= 12x1+14x2 Max The result

E 3 6 Z= 6×14 +3 ×12 120
D 6 4 Z=4×14 +6 ×12 128 Max
C 7 2 Z=2×14 +7 ×12 112
Must produce (6 writing books, 4 draw) to achieve a return of $ 128
Example 2.7 :
Find the optimal solution by using graphical method: Min Z = 5 x1 +
2x2
S.t.
2x1 + 5x2 > 10
4x1 - x2 > 12
x1 + x2 > 4 x1, x2 > 0
Solution:
The same steps as in the first example:
Straight 1 Straight 2 Straight 3

2x1 + 5x2 > 10 4x1 - x2 > 12 x1 + x2 > 4
X1 X2 X1 X2 X1 X2
0 2 0 - 12 0 4
5 0 3 0 4 0
- Point B is intersection of the straight 2 and the straight 3.
Use a calculator: ( x1 =16/5=3.2 , x2 =4/5=0.8 )
- Point C is intersection of the straight 1 and the straight 3.
Use a calculator: ( x1 =10/3=3.33 , x2 =2/3=0.66 )
Point X1 X2 Min Z=5 x1+2 x2 The result

B 3.2 0.8 Z = 5(3.2) + 2(0.8) = 17.6 Min
C 3.33 .66 Z = 5(3.33) + 2(0.67) = 18
3. Special Cases in Graphical Method to solve linear programing :
3.1 Multiple Optimal Solution
Example 3.1.1
Solve by using graphical method
Max Z = 4x1 + 3x2 Subject to

4x1+ 3x2 ≤ 24
x1 ≤ 4.5
x2 ≤ 6
x1 ≥ 0 , x2 ≥ 0
Solution
The first constraint 4x1+ 3x2 ≤ 24, written in a form of equation 4x1+ 3x2 = 24
Put x1 =0, then x2 = 8 Put x2 =0, then x1 = 6
The coordinates are (0, 8) and (6, 0)
The second constraint x1 ≤ 4.5, written in a form of equation

x1 = 4.5
The third constraint x2 ≤ 6, written in a form of equation

x2 = 6
The corner points of feasible region are A, B, C and D. So the coordinates for
the corner points are
A (0, 6)
B (1.5, 6) (Solve the two equations 4x1+ 3x2 = 24 and x2 = 6 to get the
coordinates) C (4.5, 2) (Solve the two equations 4x1+ 3x2 = 24 and x1 = 4.5 to get
the coordinates) D (4.5, 0)
We know that Max Z = 4x1 + 3x2 At A (0, 6)

Z = 4(0) + 3(6) = 18
At B (1.5, 6)
Z = 4(1.5) + 3(6) = 24
At C (4.5, 2)
Z = 4(4.5) + 3(2) = 24
At D (4.5, 0)
Z = 4(4.5) + 3(0) = 18
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.
3.2 No Optimal Solution
Example 3.2.1
Solve graphically

x1+ x2 ≤ 1
x1+ x2 ≥ 3
x1 ≥ 0 , x2 ≥ 0
Solution
The first constraint x1+ x2 ≤ 1, written in a form of equation

x1+ x2 = 1
The first constraint x1+ x2 ≥ 3, written in a form of equation

x1+ x2 = 3
There is no common feasible region generated by two constraints together i.e.
we cannot identify even a single point satisfying the constraints. Hence there is no
optimal solution.
3.3 Unbounded Solution
Example 3.3.1
Solve by graphical method

2x1+ x2 ≥ 7 x1+ x2 ≥ 6 x1+ 3x2 ≥ 9 x1 ≥ 0 , x2 ≥ 0
Solution
The first constraint 2x1+ x2 ≥ 7, written in a form of equation

2x1+ x2 = 7
Put x1 =0, then x2 = 7 Put x2 =0, then x1 = 3.5
The coordinates are (0, 7) and (3.5, 0)
The second constraint x1+ x2 ≥ 6, written in a form of equation

x1+ x2 = 6
The third constraint x1+ 3x2 ≥ 9, written in a form of equation

x1+ 3x2 = 9
The corner points of feasible region are A, B, C and D. So the
coordinates for the corner points are
A (0, 7)
B (1, 5) (Solve the two equations 2x1+ x2 = 7 and x1+ x2 = 6 to get the
coordinates)
C (4.5, 1.5) (Solve the two equations x1+ x2 = 6 and x1+ 3x2 = 9 to get
the coordinates) D (9, 0)
We know that Max Z = 3x1 + 5x2 At A (0, 7)

Z = 3(0) + 5(7) = 35
At B (1, 5)
Z = 3(1) + 5(5) = 28
At C (4.5, 1.5)
Z = 3(4.5) + 5(1.5) = 21
At D (9, 0)
Z = 3(9) + 5(0) = 27
The values of objective function at corner points are 35, 28, 21 and 27.
But there exists infinite number of points in the feasible region which is
unbounded. The value of objective function will be more than the value of
these four corner points i.e. the maximum value of the objective function
occurs at a point at ∞. Hence the given problem has unbounded solution.
References
[1] Dalgobind Mahto ( 2015 ) , Essentials of Operations Research : Ch3 .
Linear Programming –II ( Graphical Method ) , in Research Gate , PP. 1 – 9
[2] J. Reeb and S. Leavergeed ( 1998 ) , Operation Research , Using
Graphical Method to Solve Linear Programming , Extension forest products
manufacturing specialist . PP. 1 - 21
[3] Jone Wiley and Sons. Lnc. ( 2011 ) , Graphical Methods in Linear
Programming , Optimization Modeling with Spread Sheets , PP. 387 -383 .
[4] Juraj Stacho ( 2014 ) , Introduction to Operations Research ,
Department of Industrial Engineering and Operation Research ( Columbia
University ) , PP. 1 – 115
[5] Halidi Lyeme and Mohamed Abdullah Selemani ( 2012 ) , To
Operation Research : Theory and Application , Lap Lambert Academic
Publishing , PP. 1 - 83

Graphical Solution of Problems in Operation Research

Uploaded by

Copyright:

Available Formats

Graphical Solution of Problems in Operation Research

Uploaded by

Document Information

Original Description:

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

Graphical Solution of Problems in Operation Research

Uploaded by

Copyright:

Available Formats

University of Duhok

College of Basic Education

Graphical solution of problems in operation research

Khawla Hussein Haji

Dr. Sizar Abid Mohammed

2. Transfer restrictions to equation.

S.t X1 + 2X2 ≤ 100

Non negative X1, X2 ≥0 Solution:

(3) The joint solution, an area ( A B C D ) shaded.

Point X1 X2 Z=10 x1+40 x2 The result

C 66.7 16.7 16.7 ×40 +66.7 ×10 1335

The joint solution, an area (A B C D E F) shaded

2- Point (D) is intersection ofthe straight 1 and the

Point X1 X2 Z= 12x1+14x2 Max The result

Straight 1 Straight 2 Straight 3

Point X1 X2 Min Z=5 x1+2 x2 The result

Max Z = 4x1 + 3x2 Subject to

The coordinates are (0, 8) and (6, 0)

The second constraint x1 ≤ 4.5, written in a form of equation

The third constraint x2 ≤ 6, written in a form of equation

We know that Max Z = 4x1 + 3x2 At A (0, 6)

Max Z = 24, which is achieved at both B and C corner points. It can be

Max Z = 3x1 + 2x2 Subject to

The first constraint x1+ x2 ≤ 1, written in a form of equation

The first constraint x1+ x2 ≥ 3, written in a form of equation

Max Z = 3x1 + 5x2 Subject to

The first constraint 2x1+ x2 ≥ 7, written in a form of equation

The second constraint x1+ x2 ≥ 6, written in a form of equation

The third constraint x1+ 3x2 ≥ 9, written in a form of equation

We know that Max Z = 3x1 + 5x2 At A (0, 7)

You might also like