Anatolii Iusiumbeli, year V, Faculty Mathematic and Informatics
Dumitru Lozovanu, dr.hab., prof.univ., scientific advisor

We study an optimization problem on network which arose as auxiliary one when solving discrete optimal control problems with the dynamics of system described by a directed graph of passages. The vertices of the graph in such problems correspond to the states of system and its edges signify the possibility of the system passage from one state to another. Moreover the cost functions on edges of the graph are defined, which depend on time and express the expenditure or the income when the system passes from one state to another.

Let L be a dynamic system with the finite set of states V, |V| = n and at every moment of the time t = 0,1,2,… the state of system L is v(t)ÎV. Two states v₀ and w are chosen in V where v₀ is the initial state (v₀ = v(0)) and w is the final state of the system. The dynamic of the system is described by the directed graph of passages G = (V,E),for which an edge e = (u,v) signifies the possibility of passage of system L from the state u=v(t) to the state v= v(t+1) at any moment of the time t = 0,1,2,… A function c_e(t) is assigned to each edge e = (u,v) which reflects the cost of system’s passage from the state v(t) = uÎV to the state v(t+1) = vÎV at the moment of the time t. We consider the problem of finding the sequence of passages (v(0),v(1),v(2),…,v(t-1),w) where (v(0),v(1)),((v1),v(2)),…,(v(t-1),w)ÎE which transfers system L from state v₀ to state w(w=v(t)) and has the minimal sum cost by the trajectory v₀ = v(0), … ,v(t) = w during the time period [0,t].

The algorithm.

Step1. We build a new extended graph with n*n vertices. Every vertex is represented by the pair of numbers (i,j). Number i corresponds the vertex of the old graph, j corresponds the time the vertex i can be reached from initial state. We have g_{i j} = (i,j). Let’s introduse signs : I_i – line i, J_i – column j.

Step2. Let Aux_(i) ={Æ } , " iÎ1,…n. Find(g_{i j} ) = i, Sind(g_{i j} ) = j.

h 1. Aux₍₁₎={v₀}." i =1,…,n , where iÎ Aux₍₁₎ and " j =1,..n if(i,j)ÎE then C(g_{i 1}, g_{j 2}) = e_(i,j)(0) and Aux₍₂₎= Aux_{(2) È} j.

h k. " i =1,…,n , where iÎAux_(k) and " j =1,..n if (i,j)ÎE then C(g_{i k}, g_{j k+1}) = e_(i,j)(k-1) and Aux₍₂₎= Aux_{(2) È} j. If Aux_(k) ¹ {Æ } then go to h (k+1) else Stop.

Step3. We use Dejkstra’s algorithm for the obtained graph to find the optimal path from v₀ to one of the vertices of the I_w.