INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1264
GRAPHICAL METHOD FOR SOLVING LINEAR PROGRAMMING PROBLEMS
Mamatova Zilolakhon Khabibullokhonovna
Fergana state university associate professor ,
pedagogy sciences according to philosophy Doctor of Philosophy (PhD)
E-mail:
mamatova.zilolakhon@gmail.com
ORCID ID
Alimamadov Nurmuhammad Alimardon ugli
Fergana State University
Practical mathematics direction
3rd year student, student of group 22-08
Email:
alimamadovnurmuhammad02@gmail.com
Abstract:
The graphical solution of linear programming problems is based on the geometric
analysis of inequalities and the objective function in systems of two variables (n=2). Each
inequality represents a half-plane bounded by a straight line,
0
j
x
and the conditions
represent areas bounded by the coordinate axes. The solution domain of the system, which
can have a common solution, is formed as a convex polygon, a single point, or an empty set.
The graphical method includes the following steps: constructing graphs of inequalities,
determining the solution domain, drawing the objective function vector, finding the extreme
point by parallel displacement in the direction of the vector, and calculating the optimal
solution. In the example, the system of inequalities is analyzed graphically, and the maximum
(3,0) and minimum (0,3) values of the Z function are determined. This method allows you to
solve the problem visually and intelligibly, and practically demonstrates the main principles
of linear programming.
Keywords:
Linear programming, graphical method, system of inequalities, domain of
possible solutions, convex polygon, objective function, extremum point, vector direction,
optimal solution, half-plane, coordinate axes, maximum value, minimum value.
Literature review
The following sources and their content are considered for the analysis of the
literature on solving linear programming problems graphically. Below is a general analysis
and main directions, since a specific list of literature is not given. If you provide a specific list
of sources, I can deepen the analysis based on them. Classical textbooks (for example, VA
Yemelichev, MM Kovalev, LA Petrosyan, etc.) : In classical textbooks on linear
programming, the graphical method is presented as the main approach for problems with two
variables. In these sources, the system of inequalities, the concept of a convex polygon, and
the process of determining the extreme points of the objective function are explained
geometrically. As an advantage of the graphical method, its visual clarity is emphasized, but
as a limitation, the impossibility of applying it to problems with many variables is noted. The
practical significance of the method is shown through examples (for example, resource
allocation or production optimization). Modern literature on mathematical optimization (e.g.,
D. Bertsimas, JN Tsitsiklis) : In modern sources, the graphical method is discussed not as the
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1265
main theory of linear programming, but as a simplified approach used for educational
purposes. In this literature, concepts such as the geometric properties of a convex polygon,
the direction of the objective function vector, and the location of the optimal solution at the
edge points are thoroughly covered. At the same time, cases of the graphical method with
bounded and unbounded solution domains are analyzed. Examples are often focused on
logistics, economic modeling, and other areas. Uzbek-language sources (e.g., textbooks of
Uzbek universities) : Uzbek-language textbooks (e.g., textbooks on mathematical
programming of TDTU or NUU) present the graphical method in a way that is
understandable for students. They focus on more practical examples and explain step-by-step
the process of constructing a system of inequalities graphically, determining the solution
domain, and finding the optimal point. These sources often cite economic and technical
issues as examples, but theoretical depth may be limited.
Research methodology
Analysis of the effectiveness of solving linear programming problems graphically, its
geometric and analytical properties, as well as the study of the possibilities of educational and
practical application of the method. The research is focused on assessing the advantages,
limitations of the graphical method and its integration with modern technologies. Theoretical
analysis : Literature analysis on the basic concepts of linear programming (system of
inequalities, convex polygon, objective function). Study of the mathematical foundations of
the graphical method, including the theory of convex sets and the properties of extreme
points. Comparison of approaches to the graphical method from various sources (classical
and modern textbooks, scientific articles). Mathematical modeling : Formulation of linear
programming problems in two variables and their solution using the graphical method.
Modeling of cases of various solution domains (bounded polygon, unbounded domain,
singular point, empty set). Mathematical verification of the process of determining the
minimum and maximum values of the objective function.
Introduction.
Process research and optimal control are fields of science focused on
decision making and optimization of systems. Process research uses methods such as
mathematical models, linear programming, game theory, and network optimization to
efficiently allocate resources. Optimal control deals with determining the best control
strategies for systems. Its main methods Pontryagin's Maximum principle and Bellman's
dynamic programming .
Analyses and results
The following linear equations system given Let it be .
=
+
+
+
=
+
+
+
=
+
+
+
m
n
mn
m
m
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
...
...
..........
..........
..........
..........
...
...
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
These equations system vector in uniform as follows is written
A
X=B.
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1266
A - equation coefficients matrix ;
X – unknowns vector ;
B - equation free terms vector .
From higher algebra It is known that if n=m and matrix A determinant from scratch different
if , that is |A|
0 condition if done system to a single solution has will be .
n=2 when inequalities from the system following the system harvest we do :
.
0
,
0
;
,1
,
2
1
2
1
=
=
x
x
m
i
b
x
a
j
i
j
ij
Each of these inequalities is a half-plane bounded by a straight line,
1 1
2 2
i
i
i
a x a x b
=
+
and
0
j
x
=
the conditions for the non-negativity of the solutions are half-planes bounded by a
straight
0
1;2
j
x
j
=
line . Since the system of inequalities is coupled, it has at least one
solution, that is, the boundary straight lines intersect each other, forming a set of possible
(reasonable) solutions. Hence ,
2
n
=
when possible was solutions package polygon from the
points consists of will be .
1 picture
2 pictures
3 pictures
4 pictures
The domain (set) of possible solutions can be a convex polygon (Figure 1), a convex
domain with polygons (Figure 2), a singular point (Figure 3), and the empty set (Figure 4).
We write the linear programming problem for two variables as follows.
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1267
max(min)
)
,
1
(
0
....
..........
..........
2
2
1
1
2
2
1
1
2
2
22
1
21
1
2
12
1
11
®
+
=
=
+
+
+
x
c
x
c
Z
m
i
x
b
x
a
x
a
b
x
a
x
a
b
x
a
x
a
j
m
m
m
Each of the inequalities represents half-planes bounded by lines . A linear function
also represents a straight line at a certain constant value.
1 1
2 2
.
c x c x
const
+
=
Suppose that the possible solutions consist of a convex polygon. To form a
convex set of solutions, we construct a polygon bounded by straight lines. Let this polygon be
ABCDEF (Figure 5). The objective function is to give parallel straight lines in the plane X
1
OX
2 .
Let the linear function be equal to
1 1
2 2
0
c x c x
const
c
+
=
=
an arbitrary constant c
0 . It
forms a straight line. The perpendicular to it is b o ' The vector N(c
1
,c
2
) determines the
direction of increase of the function Z (Figure 5). If the convex polygon formed by the
solutions is not bounded, two cases are possible:
1- take it.
1 1
2 2
.
c x c x
const
+
=
straight line The vector N(c
1
,c
2
) moves along
or opposite to it , crossing each and every polygon . However , it does not reach a minimum
or maximum value. In this case , the linear function is unbounded from below and above
(Figure 6 ) .
Case 2.
1 1
2 2
c x c x
const
+
=
The straight line N(c
1
,c
2
) moves along the vector
and reaches a minimum or maximum value at one of the edges of the convex polygon. In this
case, the linear function may be bounded above and unbounded below (Figure 3.7) or
bounded below and unbounded above (Figure 3.8). Some linear functions limited both above
and below to be possible ( Figure 3.9 ).
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1268
Picture 7 Picture
8 Picture
9
a linear programming problem graphically is done in the following sequence:
1. Graphs of systems of equations or inequalities are constructed .
2. The sides (areas) of each inequality in the plane are determined.
3. The field of possible solutions is separated.
4. The vector N=(c
1
,c
2
) is constructed and a perpendicular is drawn to it at the point (0,0).
5. The extreme point is found by moving the line parallel to the perpendicular from the
polygon in the direction of the vector b . If it is necessary to find the point corresponding to
the minimum value of the function Z, then this point corresponds to the first point of the field
of possible points when the perpendicular to the vector p is moved in this vector direction.
The point giving the maximum value is the last point. If the vector value (negative sign) is -N,
the opposite of the above case will happen.
6. The optimal point coordinate is found and the value of the Z function is calculated .
Example.
Solve the linear programming problem in the Q -set graphically.
max
5
2
,
0
,
0
)
(
12
4
3
)
(
12
3
4
2
1
2
1
2
2
1
1
2
1
®
-
=
+
+
x
x
Z
x
x
L
x
x
L
x
x
Given inequalities graphs X
1
OX
2
on the plain we build and possible was solutions
field ( 10 pictures ) . on the graph cross-hatched place determines . Because this place is all
inequalities satisfactory is a field . Possible was
solutions the optimal solution from the
field Let's determine . Determine from the point (0,0) for the vector N=(2,-5) passing let's
make and his/her direction We define . At the point (0,0) this perpendicular to the vector N
we will spend and him/her vector direction according to we move . Soha with perpendicular
last intersection point to Z function maximum value giver is a point . This point is (3,0 )
his/her coordinate x1 =3,
x2 =
0 of the matter solution will be . From the graph apparently
so that Z is a function minimum value and the point giving is (0,3).
Conclusion
The research methodology for solving linear programming problems graphically was
aimed at a comprehensive study of the theoretical foundations, practical application and
significance of the method in the educational process. The study used theoretical analysis,
mathematical modeling, experimental and qualitative-quantitative methods to evaluate the
effectiveness of the graphical method in two-variable problems, its geometric properties and
integration with modern software tools. The main advantages of the graphical method were
its visual clarity and convenience for educational purposes, but its limitations in multivariable
problems and problems with accuracy in manual drawing were noted as the main
disadvantages. As a result of the study, the practical significance of the graphical method in
small-scale problems in the field of economics, logistics and production was confirmed, and
at the same time, recommendations were developed for automating the process using tools
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1269
such as MATLAB and GeoGebra. In the future, it is necessary to continue research to expand
the application of the method on interactive platforms and ensure its more effective
integration into educational programs.
REFERENCES USED:
1. Yemelichev, VA, Kovalev, MM, Kravtsov, MK (1984). *Mathematicheskie metody
programming*. Moscow: Nauka.
2. Bertsimas, D., Tsitsiklis, JN (1997). *Introduction to Linear Optimization*. Belmont, MA:
Athena Scientific.
3. Taha, HA (2017). *Operations Research: An Introduction* (10th ed.). Pearson.
4. Kholmirzayev, AA, Kuldoshev, Q. (2010). *Fundamentals of Mathematical
Programming*. Tashkent: Publishing House of the National University of Uzbekistan.
5. Anderson, DR, Sweeney, DJ, Williams, TA (2018). *An Introduction to Management
Science: Quantitative Approaches to Decision Making* (15th ed.). Cengage Learning.
