Accumulated experience of manufacture management shows that traditional opportunities and methods to increase effectiveness and development of management aimed at optimization of movement of material and cash flows have been exhausted and new shapes and methods are needed [1,2].
Conducted researches have shown that price of product which reached its final consumer consists of logistics (transportation, storage, packaging etc.) on more than 70%.
Large part of logistics operation during the movement of material flows from primary source of raw materials to final customer is conducted with the use of different transport means. Expenses for such logistics operations make up to 50% of total logistics expenses.
Transportation is a par t of logistics process and refers to the sphere of material service production. Management of material flow during the process of transportation and organization of carriage transportation are the spheres of transport logistics.
In the sphere of transport logistics the following tasks are set and solved: definition of optimal plan of transportation of homogeneous products, objective of placement considering transport and production costs, determination of rational routes and transit transportation of products.
During the solution of tasks of transport logistics network and graphic models are often used.
In network and graphical models the subject of research is a network which consists of communication centers and lines. It is assumed that the network has two special centers: input and output. Mathematical modeling is used as a graph theory and specially designed algorithm of problem solving. The following types of problems are solved most often:
- defining of maximum flow of freight through transport network;
- finding of the shortest or cheapest way between arbitrary network nodes;
- construction of the cheapest transport network, transmission line, pipeline;
- search of narrow places of transport network;
- optimal appointment of employees on work areas.
Technology of solving of these problems is based on the following definitions. Every arc of the graph, which connects two nodes xi and xj, characterized by length l(xi , xj). Every of nodes of the network (xi) is called top of the graph G, which represents the whole network. Arcs may be oriented (mentioned in graph G as arrows) and non-oriented. The total number of vertexes of graph G equals n, and indexes of vertexes xi , change from i=1 to i=n.
Let’s introduce the definition of transport network – bounded oriented multigraph without loops, in which:
- there is only one vertex x0, which is called network input;
- there is only one vertex xn, which is called network output;
- to every arc gij(xi , xj) refers integer number С(xi , xj)≥0, which is called capacity.
For arbitrary vertex xi many arcs which are part of this vertex, will be indicated as , while many arcs, which are part of it through xi will be indicated as . Then integer function defined on many arcs of graph G(x), which fulfills the requirements of characteristic (1), will be named flow of transport network.
(1)
Characteristic 2 means known condition of keeping substance in interim nodes . It shows that in every interim vertex of transport network substance is not created and doesn’t disappear.
Characteristic 3 shows that in one unit of time amount of substance can’t exceed the capacity of arc.
Inflow of substance in vertex is an amount of
transport flow in network and is defined by formula (2).
(2)
If to cut graph G through many vertexes
then many arcs, which go into many vertexes, will be called network incision. Capacity of incision equals sum of arcs’ capacities, which go into multiplicity А as shown in formula
- .
(3)
Every element of substance, moving from x0 to xn will go through an arc of incision at least once. Then
no matter what the flow and network incision
would be, inequality (4) always takes place.
(4)
There is a lemma which will be taken for granted.
If for any incision equality takes
place, then:
Flow has the largest value;
incision has the smallest capacity, which equals
to the sum of arcs’ capacities.
Problem on the largest flow in the network
Network is represented by graph G(x) with many
edges U, n vertexes , where x0 and xn – input and output respectively. For every edge of the network (xi , xj) or arc set capacity is shown in formula (5).
(5)
We have to find the system of numbers ,
which represents actual value of flows in arcs of graph G, for which inequality (6) is just.
(6)
This inequality means that flow on edge can’t
exceed capacity of arc. Based on the third condition of definition of flow every flow which is part of is
equal to the flow which comes out of vertex of
Condition of maximality of flow at transport network output is shown in formula (7).
(7)
This is a classic problem of lineal programming, but usually difficult to solve due to bad convergence of simplex-method algorithm, which requires many iterations. That is why American scientists Ford and Fulkerson offered simpler algorithm of solving it. The idea is in gradual increase of flow till it reaches maximum [3]
The only limitation of usage of Ford-Fulkerson algo
rithm is that С should be integer numbers. That
is why amount of flow is integer function.
Literature
Plotkin B., Delyukin L. Economic-mathematical methods and models in logistics: Tutorial. – СПб.: Изд- во СПбГУЭФ, 2010. – 96с.
Tihomirova A, Sidorenko Y. Mathematical models and methods in logistics: Tutorial. М.: НИЯУ МИФИ, 2010 – 320с.
Iskakova A., Kazangapova B., Hompysh A. Study of logistic system of distribution of production based on Ford-Fulkerson algorithm. Вестник КазАТК №1 2015г.