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 1256
MATHEMATICAL MODEL OF THE TRANSPORT PROBLEM AND OPTIMAL
SOLUTION METHODS
Mamatova Zilolakhon Khabibullokhonovna
Associate Professor, Fergana State University ,
Doctor of Philosophy (PhD) in Pedagogical Sciences
E-mail:
mamatova.zilolakhon@gmail.com
ORCID ID
Numonova Malakhat Akmaljon kizi
Fergana State University
Applied Mathematics 3rd year student, student of group 22-08
Email:
igf5284@gmail.com
Abstract:
The transportation problem is an optimization problem aimed at finding a plan for
transporting goods from the points of departure to the points of reception with minimal cost.
Based on the given cargo stocks, requirements and transportation prices, the objective
function
·
Z
cij xij
= S
is minimized. An initial plan is created using the “Northwest Corner”
and “Small Elements” methods, and the optimal plan is determined using the potential
method. In the example, the minimum cost
375
Zmin
=
is achieved.
Keywords:
Transportation problem, optimization, tariff matrix, base plan, Northwest corner
method, Finite element method, potential method, objective function.
Literature analysis on the issue of transportation
The transportation problem occupies an important place in the field of mathematical
programming and optimization. The literature listed below provides fundamental and
practical knowledge on this topic. Akulich I.
L.
Mathematical programming in in
examples and задачах (1996) – The book explains the transport problem through practical
examples and problems, emphasizing methods for creating a basic plan and finding optimal
solutions. Badalov FB Optimization Theory and Mathematical Programming (1989) – This
resource in Uzbek describes the mathematical model of the transport problem and methods
for solving it in a simple language, convenient for local readers. Kuznetsov A.V., Novikova
G.I., Kholod N.I. Collection of problems on mathematical programming (1985) – As a
collection of problems, it is useful for studying various aspects of the transport problem and
developing practical skills. Kuritsky B. I. Search
optimal decision with Excel tools
(1997) – presents a modern approach to solving the transport problem in Excel, with high
practical applicability. Safa e and K., Be knazarova N. Mathematical methods for verifying
operations (1984) – explains the theoretical foundations of the transport problem and the
method of potentials, but may be outdated.
Research methodology
The following methodology is used to solve the transportation problem. Mathematical
modeling: The problem
(
· )
Z
cij xij
= S
is formulated in the form of linear programming,
based on the objective function and boundary conditions (cargo stocks, requirements). Initial
plan: Northwest corner method: Load distribution starting from the upper left corner of the
table. Small element method: Distribution starting from the cells with the lowest cost.
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 1257
Optimal solution: The difference in empty cells
(
)
(
)
Sij
cij
ui
vj
=
-
+
is calculated using
the potential method, the loads are redistributed using a closed loop, and the optimal plan is
found until Sij ≥ 0. Analysis: Costs of plans
( )
Z
is compared, for example,
375
Zmin
=
to
obtain . Tools like Excel or Python automate the calculation.
Analyses and results
The problem of finding the optimal plan for transporting goods from shipping points
to given receiving points is called the transportation problem and is formulated as follows:
a
1
, a
2
,..., a
m
quantities of homogeneous cargoes
1
2
, ,..,
m
А А
А
at their respective
points.
1
2
, ,..,
m
А А
А
We call these points of departure. These cargoes must be received by n
1
2
, ,...,
n
В В
В
points and their requirements are given accordingly . Let
1
2
, ,...,
n
b b
b
the cost of
transporting each
ij
x
unit of cargo
i
-
from the chith point of departure to the chith point of
reception be known as c
j
-
ij
. We must design a plan for transporting these cargoes in such a
way that the demand points receive maximum satisfaction and the sum of the operations
spent on transporting all cargoes is minimal.
We present the transportation problem conditionally in the form of a table. The table
shows: receiving points, sending points, cargo stocks, cargo demand, and the cost of cargo
units sent from each
i
-
sending point
j
-
to each receiving point (i.e., the tariff matrix).
Shipping
Pick-up points
Cargo
punks
B
1
B
2
. . . .
B
n
Zapatistas
A
1
с
11
x
11
c
12
x
12
. . . .
c
1n
x
1n
a
1
A
2
с
21
x
21
c
22
x
22
. . . .
c
2n
x
2n
a
2
. . .
. . . . . . . .
. . . .
. . . .
...
A
m
with
m1
x
m 1
m2
x
m2
. . . .
c
m n
x
mn
a
n
The
need
for
luggage
b
1
b
2
. . . .
b
n
e a
i
= e b
j
Here,
{ }
ij
C
c
=
the matrix is called the tariff matrix or transportation costs.
{ }
ij
X
x
=
and the matrix is called the transportation problem plan. Here is
ij
x
i
-
the volume
(number) of goods to be transported from point i to point j. The total cost associated with the
transportation plan is expressed by the following objective function.
11 11
12 12
1 1
21 21
22 22
2
2
1
1
2
2
. . .
. . .
. . .
. . .
.
n n
n
n
m m
m
m
mn mn
Z
c x
c x
c x
c x
c x
c x
c x
c x
c x
=
+
+
+
+
+
+
+
+
+
+
+
Here,
ij
x
the variables must satisfy the conditions (constraints) of load capacity, load
demand, and non-negativity.
Taking the above into account, the mathematical model of the transportation problem
can be written 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 1258
min
)
,
1
(
)
,
1
(
0
)
,
1
(
,
)
,
1
(
,
1
1
1
1
®
=
=
=
=
=
=
=
=
=
=
=
n
j
m
i
ij
ij
ij
m
i
j
ij
n
j
i
ij
x
c
Z
n
j
m
i
x
n
j
b
x
m
i
a
x
The mathematical formulation of the transportation problem is interpreted as follows:
Given a boundary system, a non-negative condition, and an objective function, the task is to
find a non-negative solution (plan) from the solution set of the system such that the objective
function attains a minimum value.
The transportation problem is divided into two types, open and closed. If the sum of
the cargo stocks is equal to the sum of the cargo demands, that is,
=
=
=
n
j
j
m
i
i
b
a
1
1
the issue will be a closed type issue
If the sum of the cargo stocks is not equal to the sum of the required cargoes, i.e.
=
=
n
j
j
m
i
i
b
a
1
1
The issue will be an open-ended issue.
2. Methods for solving the transportation problem
Solving the transportation problem consists of two stages.
1. Find a basic plan.
2. Finding the optimal plan from among the basic plans.
There are several ways to create a basic plan: "Northwest corner", "Small elements",
"Fogel'", etc.
"Northwest corner" method.
The use of the "northwest corner" method when drawing up a preliminary cargo
transportation plan is carried out as follows:
1. A tariff schedule is drawn up.
b
1
b
2
..... .. .
b
n
a
1
с
11
c
12
. . . . .
c
1n
a
2
с
21
c
22
. . . . .
c
2n
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
a
m
с
m1
c
m2
. . . . .
c
mn
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 1259
2. Left on the side above corner , that is ( north - west ) corner ) from starting line
according to or column according to we move to cell (1,1) a
1
and b
1
of the most the
youngest we place , that is ,
(
)
11
1
1
,
.
x
min a b
=
3. If
1
1
a b
>
if
11
1
x
b
=
what we give , first column this with is closed , that is
(
)
1
0
2,
.
i
x
i
m
=
=
( First acceptance the one who does demand complete satisfied ).
4. We move along the first line to the cell (1;2), where
1
1
2
,
a b b
-
we place the smallest
of , that is, x
12
= min(a
1
-b
1
,b
2
).
5.
1
1
b a
>
If so, the 1st line is closed, i.e.
(
)
1
0
2, .
j
x
j
n
=
=
6. We proceed to fill in the adjacent cells (2.1), i.e.
(
)
21
2
1
1
,
.
x
min a b a
=
-
7. We move on to filling in the cells of the second row or the second column, and so
on. This process continues until the resources run out.
"Small elements" method.
Finding the base plan using the "small elements" method is done as follows:
1. Freight begins with filling in the box corresponding to the lowest shipping cost in
the tariff table for the recipients.
2. The smallest of a
i
or b
j is placed in the lowest tariff c ij
box .
3. Then, when the row or receiving point requirement is met, the corresponding
column is deleted.
4. If the cargo stocks at the shipping point are fully distributed and the recipient's
request is fully fulfilled, the corresponding row and column will be deleted.
5. A further small definition is obtained from the remaining rows and columns. The
process of distributing cargo stocks continues until the cargo stock is exhausted and the
requirements are satisfied.
Potential method.
If an initial base plan is found using the above methods, finding the optimal plan is
performed using the potential method.
The potential method for finding the optimal plan for the transportation problem is as
follows:
1. Using the methods listed above, a basic cargo transportation plan is determined.
i
and v
j are determined
for the points receiving and sending cargo, respectively .
3. The sum of potentials in empty cells is
.
ij
i
j
сў
u v
=
+
4. The difference between the rates
ij
c
and the empty cells
ij
сў
is calculated.
The resulting plan is optimal if all empty cells have the same difference .
0
ij
S
>
6. If it is in one of the empty cells , the variable value x
0
ij
S
<
ij is entered
in the non-
empty cells , that is, the above difference is minimal. For this cell, a closed contour is formed
using the non-empty cells and the loads are redistributed in this contour. As a result, we get a
new transportation plan.
This process
0
ij
S
>
continues until there is no difference and the final cargo
transportation plan is optimal.
Example.
Solve the transportation problem given in the table below.
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 1260
b
k
oh
my
40
25
20
50
60
5
4
1
2
40
4
2
6
3
35
7
3
5
4
Solution: We find the initial base plan using the "Northwest corner" and "Small
elements" methods. According to the "Northwest corner" method,
(
)
1,1
60, 40
40
X
min
=
=
we
place
the
number
in
the
(1,1)
cell
of
the
table,
and
the
next
(
)
12
60 40,25
20
X
min
=
-
=
number in the (1,2) cell. Thus, the load at the first point is
completed, and the next cells (1,3) and (1,4) are closed.
We start distributing the cargo at the next point.
(
)
22
40,5
5
X
min
=
=
We place the
number in the (2,2) cell. Thus, the requirements of the 1st and 2nd applicants are satisfied,
that is, the 1st and 2nd columns are closed.
(
)
23
35, 20
20
X
min
=
=
It is placed in the (2,3)
cell. The requirement of the 3rd applicant is fulfilled. We place the remaining cargo in the
(2,4) cell, that is,
(
)
24
15,50
15
X
min
=
=
and the cargo at the second dispatch point is finished.
We start distributing the cargo at the 3rd dispatch point.
The cells (3,1), (3,2), (3,3) are closed, that is, the demands of applicants 1,2 and 3 are
satisfied.
(
)
34
35,35
35
X
min
=
=
We write in cell (3,4). Thus, the loads are completely
distributed, that is, we have the following plan.
=
35
0
0
0
15
20
5
0
0
0
20
40
X
The objective function value
595
Z
=
is .
We will now find the base plan of the problem using the "Least Elements" method.
Solution: We find the smallest cost by column or row.
This element is located in the cell (1;3) in the row, i.e. c
13
=1. Therefore,
(
)
13
60, 20
20
X
min
=
=
we place the load in this cell. The requirement of the third applicant is
satisfied. Therefore, the 3rd column is not considered in further calculations. We find the next
smallest element. This element is located in the cells (1,4) and (2,2), i.e.
14
2
с
=
and
22
2
с
=
.
We place the loads in these cells.
(
)
(
)
14
22
60 20,50
40,
40, 25
25
X
min
X
min
=
-
=
=
=
. The
requirement of the second applicant is satisfied, therefore, the 2nd column is not considered
in further calculations.
The next smallest elements are located in cells (2,4) and (3,2), i.e.
24
3
с
=
and
32
3.
с
=
We place loads in these cells.
(
)
24
40 25,50 40
10.
X
min
=
-
-
=
The cell (3,2) is not
considered, because this column is excluded. We look for the next smallest element, this is
element
21
4
с
=
. We place the load in this cell.
(
)
21
15 10, 40
5.
X
min
=
-
=
The last smallest
element
31
7
с
=
. We also place the load in this cell
(
)
31
35,40 5
35.
X
min
=
-
=
. As a result,
we have distributed the loads and obtained the initial base plan, i.e.
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 1261
=
0
0
0
35
10
0
25
5
40
20
0
0
X
We calculate the objective function
415
Z
=
.
Now we find the optimal plan for the problem. To find the optimal plan, we use the
method of potentials. Suppose the initial base plan was found using the "Least Elements"
method. We write it in the form of a table below.
b
k
a
i
40
25
20
50
u
60
5
4
1
20
2
40
0
40
+
4
5
-
2
25
6
3
10
1
35
-
7
35
+
3
5
4
4
V
3
1
1
2
Non-empty cells in the table satisfy the following condition.
3 4 1 6
r
= + - =
We determine the potential of the shipper and the demander and obtain the following
equations.
1
3
1
4
2
1
2
2
2
4
3
1
1;
2 ;
4;
2;
3 ;
7
u v
u v
u v
u v
u v
u v
+ =
+
=
+ =
+
=
+
=
+ =
It is known that the number of equations is 1 less than the number of unknowns, that
is, 1 of the unknowns is free and it can take any value. For example, let's say u
1
=0. Then the
remaining potentials are determined as follows
1
3
4
2
2
1
3
0,
1,
2,
1,
1,
3,
4.
u
v
v
u
v
v
u
=
=
=
=
=
=
=
Empty in cells s
ij
value following formula with we will determine S
ij
= c
ij
-( u
i
+ v
j
). In that case
(
)
(
)
(
)
(
)
(
)
(
)
11
12
23
32
11
34
5 0 3
2;
4 0 1 3;
6 1 1 4;
3 4 1
2;
5 4 1 0;
4 4
2
2.
S
S
S
S
S
S
= - +
=
= - + =
= - + =
= - + = -
= - + =
= - - + = -
The resulting plan cannot be optimal, because there are also negative ones in
32
34
2
S
S
=
= -
the s
ij s
. We create a closed contour (cycle) for these cells. For cell (3,2), the
contour is (3,2),(3,1),(2,1),(2,2). We draw the contour clockwise or counterclockwise,
starting from cell (3,2), sequentially placing + and - signs. We choose the smallest of the
negative cells
(
)
25;35
25
min
=
, i.e.
22
25
x
=
. We redistribute the loads in the cells. When
distributing, the overall balance should not be disturbed in these cells and the costs should be
minimal. We add the load in the negative cell (2,2) to the load in the next positive cell. In this
case,
5 25 30
+
=
there will be a load in cell (2,1). In order not to disturb the balance, we load
25 units of the load in cell (3,1) to cell (3,2). Thus, we have a new plan. We define the
potentials for this table and calculate the s
ij in the empty cells:
(
)
(
)
(
)
(
)
(
)
(
)
11
12
23
22
33
34
5 0 3
2;
4 0 1 3;
6 1 1 4;
2 2 1 0;
5 4 1 0;
4 4
2
2;
S
S
S
S
S
S
= - +
=
= - + =
= - + =
= -
+ =
= -
+ =
= -
- + = -
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 1262
b
k
a
i
40
25
20
50
u
60
5
4
1
20
2
40
0
60
5
4
1
20
2
40
0
40
+
4
30
2
0
6
-
3
10
1
35
- 7
10
3
25
5
+ 4
4
and
3
1
1
2
The newly obtained plan is also not optimal, because S
34
=-2. We construct a closed
contour and redistribute the loads within this contour, resulting in the following plan.
b
k
oh
my
40
25
20
50
she
is
60
5
4
1
20
2
40
0
40
4
40
2
0
6
3
1
35
7
3
25
5
4
10
2
V
3
1
1
2
The resulting plan is an optimal plan because all empty cells have positive S
ij
.
Therefore, the optimal plan is as follows.
=
10
0
25
0
0
0
0
40
40
20
0
0
X
The value of the objective function
375.
min
z
=
Conclusion
The transportation problem is a linear programming problem aimed at optimizing the
delivery of goods from the point of shipment to the point of reception with minimal cost. The
mathematical model is the objective function
(
· )
Z
cij xij
= S
and boundary conditions. The
initial plan is found by the “Northwest Corner” or “Small Elements” methods, and the
optimal solution is found by the potential method.
375
Zmin
=
In the example, was achieved.
The problem is of great importance in economics and logistics and is effectively solved using
modern software tools.
References:
1. Akulich I.L. Mathematical programming in primerax and zadachax. - M.: Vysshaya
shkola, 1996.
2. Badalov FB Optimallash nazariyasi va mat e matik dasturlash. “ O ' q ituvchi”, T. 1989
y.
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 1263
3. Kuznetsov A.V., Novikova G.I., Kholod N.I. Collection of problems in mathematical
programming. Minsk, Higher School, 1985.
4. Kuritsky B.Ya. Search for optimal solutions using Excel . “Saint Petersburg”, 1997.
5. Safaeva K., Beknazarova N. Operatsiyalarni tekshirishning matеmatik usullari.
“O'qituvchi”, 1984y. 1 qism.
6. Lesin V.V., Lisovets Yu.P. Fundamentals of optimization methods. Moscow, MAI
Publishing House, 1998.
