Anale. Seria Informatică. Vol. XVIII fasc.
2 – 2020
Annals. Computer Science Series. 18th Tome 2nd Fasc. – 2020
GRAPHICAL SOLUTION OF NON LINEAR PROGRAMMING PROBLEM
Zahidullah Rehan
Department of mathematics, Sayed Jamaluddin Afghan University, Kunar, Afghanistan
Corresponding author: Zahidullah Rehan, [email protected]
ABSTRACT: In this paper, a graphical solution of the 3. SOME STEPS IN SOLVING NLP
nonlinear programming problem was presented the result PROBLEM GRAPHICALLY
satisfies the graphical solution of the nonlinear
programming problem and we also solved some NLPP The following steps are used in the graphical solution
question in this paper by graphical method.
of the nonlinear problem. We will apply these steps
KEYWORDS: Non linear programming problem, in some examples.
Objective function, Constraint, Graphical solution,
Feasible region a. Formulate. First of all we must write the NLP
problem in standard form. Which have the
1. INTRODUCTION objective function and constraint set.
b. In this step we construct the graphs and plot the
As we are familiar with the graphical of solving the constraint curve. Where the constraint curve
non linear programming problem thus by the some represent the limitation of the available
way the graphical method can be employed to solve resource.
the two variable NLP problem also. c. Identified the convex region of the (solution
In linear programming problem the solution point is space) generated by the objective function and
generally a corner point of the convex solution space. constraints of the given problem.
While in NLPP the solution point is not necessarily a d. Determine the point in the convex region in
corner point or an edge. We will illustrate the solution which the optimum solution always accrues
of NLPP by graphical method by some examples. and the most attractive corner is the last point
in feasible region.
2. GRAPHICAL METHOD e. Determine the optimal solution by
algebraically calculating coordinates of the
One of the solving methods of non-linear most attractive point.
programming problem is graphical method which is f. For the optimal solution of the problem we
also called geometrical method. must determine the value of the objective
As we know there some more method for solving of function.
non-linear programming problem like Wolf, Beal and
separable method but the graphical method is the Example1. Solve the following NLP problem
easiest method for solving NLPP is defend on well- graphically.
defined sets of logical steps. NLPP which contain two 𝑀𝑎𝑥 𝑧 = 2𝑥1 + 3𝑥2
variables can be easily solved by graphical method. Subject to the constraints
As we can abserve that from the characteristic of the 𝑥1 𝑥2 ≤ 8
curve we can achieve more information and from 𝑥1 2 + 𝑥2 2 ≤ 20
these information we can obtain the optimal solution 𝑥1 , 𝑥2 = 0
of the given problem.
But in the case of NLP problem the optimum solution Solution. Let 𝑂𝑥1 and 𝑂𝑥2 be the set of rectangular
or may not be occur at one of the extreme points of Cartesian coordinate axes in the plane.
the solution space, generated by the constraints and Clearly, the feasible region will lie in the first
the objective Function of the given problem. quadrant only, because 𝑥1 ≥ 0 , 𝑥2 ≥ 0. Now we plot
the curve of the given constraint 𝑥1 2 + 𝑥2 2 = 20
and𝑥𝑦 = 8.
109
Anale. Seria Informatică. Vol. XVIII fasc. 2 – 2020
Annals. Computer Science Series. 18th Tome 2nd Fasc. – 2020
Since 𝑥1 2 + 𝑥2 2 = 20 represent a circle of radius Hence the graphical solution of the problem finally
√20 with center at the origin and 𝑥1 𝑥2 = 8 represent obtained as 𝑥1 = 2 , 𝑥2 = 4 and max 𝑧 = 16.
a rectangular hyperbola whose asymptotes are the
coordinate’s axes. Example 2. Solve the following NLP problem
Solving the equations 𝑥1 2 + 𝑥2 2 = 20 and 𝑥𝑦 = 8 graphically.
Since we know 𝑀𝑎𝑥 𝑧 = 8𝑥1 − 𝑥12 + 8𝑥2 − 𝑥22
(𝑥1 + 𝑥2 )2 = 𝑥1 2 + 𝑥2 2 + 2𝑥1 𝑥2 (𝑥1 + 𝑥2 )2 = Subject to the constraint
20 + 2(8) = 36 (1) 𝑥1 + 𝑥2 ≤ 12
2 2 2
𝑥1 − 𝑥2 ≥ 4
Also (𝑥1 − 𝑥2 ) = 𝑥1 + 𝑥2 − 2𝑥1 𝑥2 𝑎𝑛𝑑 𝑥1 , 𝑥2 ≥ 0
(𝑥1 − 𝑥2 )2 = 20 − 2(8) = 4 (2)
Adding (1) and (2) we get Solution. Let 𝑂𝑥1 and 𝑂𝑥2 be the set of rectangular
𝑥1 = 4 𝑎𝑛𝑑 𝑥2 = 2 Cartesian coordinate axes in the plane of the paper.
Since 𝑥1 ≥ 0 and 𝑥2 ≥ 0, the feasible region will lie
Thus the intersection coordinate of these two curves in the first quadrant only, the feasible region is shown
are 𝐵(4,2) and 𝐷(2,4) in the figure by the shaded region in the figure.
As shown in the figure, the point (𝑥1 , 𝑥2 ) lying in the
Thus the optimal point ((𝑥1 , 𝑥2 ) must somewhere in
first quadrant shaded by the horizontal lines satisfies
the convex region ABC. However the desired point
the constraints
will be that at which a side of the convex region is
𝑥1 2 + 𝑥2 2 ≤ 20 , 𝑥1 ≥ 0 , 𝑥2 ≥ 0 tangent to the circle
Where the points (𝑥1 , 𝑥2 )lying in the area shaded by 𝑧 = 8𝑥1 − 𝑥12 + 8𝑥2 − 𝑥22 .
vertical lines satisfy the constraint 𝑥1 𝑥2 = 8 , 𝑥1 ≥ The gradient of the tangent to this circle can be
0 , 𝑥2 ≥ 0 obtained by differentiating the equation
Thus the desired solution point (𝑥1 , 𝑥2 )may be 𝑧 = 8𝑥1 − 𝑥12 + 8𝑥2 − 𝑥22
somewhere in the non-convex feasible region With respect to 𝑥1 i.e
𝑂𝐴𝐵𝐶𝐷𝐸 shaded by both the horizontal and vertical 𝑑𝑥 𝑑𝑥
8 − 2𝑥1 + 8 𝑑𝑥2 − 2𝑥2 𝑑𝑥2 = 0
lines. 1 1
𝑑𝑥2 2𝑥1 −8
Or = 8−2𝑥 (3)
𝑑𝑥1 2
The gradient of the line 𝑥1 + 𝑥2 = 12 and
𝑥1 − 𝑥2 = 4 is
𝑑𝑥1 + 𝑑𝑥2 = 0 Or
𝑑𝑥2
= −1
𝑑𝑥1
And
𝑑𝑥1 + 𝑑𝑥2 = 0 Or
𝑑𝑥2
=1
𝑑𝑥1
Figure (1) - show the graph and feasible region
of the given problem.
The required point is obtained by moving parallel to
the objective line 2𝑥1 + 3𝑥2 = 𝑐 for some constant
𝑧 = 𝑐, i.e. we go on moving parallel to the objective
line 2𝑥1 + 3𝑥2 = 6 (for 𝑐 = 6 say)away from the
origin so long as the line 𝑐 = 2𝑥1 + 3𝑥2 touches the
extreme boundary of the feasible region.
In this problem the boundary point 𝐷(2,4) gives the
Figure (2), show the graph and feasible region of
maximum value of the 𝑧.
the given problem.
110
Anale. Seria Informatică. Vol. XVIII fasc. 2 – 2020
Annals. Computer Science Series. 18th Tome 2nd Fasc. – 2020
If the line 𝑥1 + 𝑥2 = 12 is the tangent to the circle, This point lies in the feasible region and satisfies with
𝑑𝑥2 the constraints. Thus the optimal solution is
then substituting = −1 from equation (2) in
𝑑𝑥1
equation (1), we have 𝑥1 = 6 , 𝑥2 = 2 , max 𝑧 = 24.
2𝑥1 − 8
= −1 CONCLUSION
8 − 2𝑥2
The graphical method is proposed to solve the NLP
Or 2𝑥1 − 8 = −8 + 2𝑥2 problem. This based on the plot of the curve of the
Or 2𝑥1 = 2𝑥2 constraints. The graphical solution can help us to
Or 𝑥1 = 𝑥2 make any decision and determining a particular plan
And here for 𝑥1 = 𝑥2 , the equation 𝑥1 + 𝑥2 = 12 of action from amongst several alternatives in a short
gives time. The graphical method is the best method to
(𝑥1 , 𝑥2 ) = (6,6) make any decision for modern game theory, dynamic
programming problem, economics and management.
This means that the tangent of the line 𝑥1 + 𝑥2 = 12
is at (6,6)
REFERENCE
Similarly, if the line 𝑥1 − 𝑥2 = 4 is the tangent to the
𝑑𝑥
circle, then substituting 𝑑𝑥2 = 1 from equation (2) in [1]. N. K. Keak, Mathematical programming with
1
equation (1), we have business application (Mc Graw-hill book
company New York 1990).
2𝑥1 − 8 [2]. Kanti Sawrup, P. K Gupta, Manmonhan,
=1
8 − 2𝑥2 Operation research (Sultan Chandra and sons.
Or 2𝑥1 − 8 = 8 − 2𝑥2 New Delhi, India, 12th edition 2004).
Or 2𝑥1 + 2𝑥2 = 16 [3]. Ravindran A., D.T. Phillips and J.J. Solberg,
Or 𝑥1 + 𝑥2 = 8 Operations Research Principal and practice (John
Adding the equations 𝑥1 + 𝑥2 = 8 and 𝑥1 − 𝑥2 = 4, Wiley and Sons, New York, second edition,
we have 1987).
(𝑥1 , 𝑥2 ) = (6,2) [4]. S. D. Sharma, Operation research (kedar Nath
Ram Nath and Co. 14th Edition, 2004).
This means that the tangent of the circle to the line [5]. J. K Sharma, Operation research (Macmillan
𝑥1 − 𝑥2 = 4 is at (6,2). India Pvt. Ltd. 2003).
111
