Problem of Distribution of Goods by Logistics Centers Anatoly Panyukov and Khalid Z. Chaloob South Ural State University, 76 Lenina Ave., 454080, Chelyabinsk, Russia paniukovav@susu.ru khalid.e@mail.ru Abstract. Effective logistics management is recognized as a key factor in improving the performance of companies and their competitiveness. The econometric methods used in practice do not provide the means for promptly solving a multitude of emerging problems, in particular for effective operational management of a network marketing organiza- tion. In the paper, algorithms for analyzing and solving the problem of distribution of goods by logistics centers, including decision support sys- tem in case of incorrectness of the arising problem are proposed: (1) the method of regularization of the decomposable distribution problem; (2) an effective algorithm for approximating an indecomposable problem by a decomposable problem. The software implementation of the proposed algorithms is easily encapsulated in the MS Office system. Keywords: Logistics center · Transport problem · Operational manage- ment · Distribution task · Regularization · Decomposition · Algorithm 1 Introduction A enterprise is a complex and dynamic system actively interacting with the exter- nal environment. Currently, effective logistics management is recognized as a key factor in improving the performance of companies and their competitiveness [9, 3]. Budashevsky, and Pastukhova [2] propose constructive comparative analysis of methods and models for estimating demand used in economics and market- ing and system technology for analyzing and forecasting consumer preferences. Bayev and Drozin [1] consider questions of the dynamics of consumer demand. Levin notes [4] that these methods do not provide the means to quickly solve a lot of emerging problems, in particular for effective operational management of the network marketing organization. Algorithms for analyzing and solving the problem of the distribution of goods by logistics centers, including a decision support system in case of illposed arising Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org Problem of Distribution of Goods 305 problem are proposed in the paper. Software implementation of these algorithms is easily encapsulated in the MS Office system [5, 6]. In the first section we give a formal statement of the problem and introduce the main notation used of this paper. In the second section we consider the de- composable case of a problem reducible to the transport problem with matrix formulation. In the third section we propose a method for regularizing a decom- posable problem in the case of its illposed formulation. In the fourth section we propose a method for approximating the problem of the original problem with a decomposable problem. 2 Statement of the Problem The problem of distributing a set I of goods over a set J of logistics centers is considered. Let xij be the volume of the commodity i ∈ I distributed to the center j ∈ J. Let pij be the marginal profit from the sale of a unit of commodity i ∈ I at the center j ∈ J. Let λij be the cost of distribution of a unit of commodity i ∈ I by the center j ∈ J. Let di be the effective demand for the commodity i ∈ I. Let bj be the resource for the maintenance of the center j ∈ J. The formal formulation of the problem consists in finding the distribution of goods i ∈ I at the centers j ∈ J, for which the marginal profit is maximal XX xo = arg max pij xij , (1) x∈D j∈J i∈I all goods are satisfied with the effective demand X xij = di , i ∈ I, (2) j∈J resource constraints have been met for all centres X λij xij ≤ bj , j ∈ J, (3) i∈I the condition of non-negativity is fulfilled xij ≥ 0, i ∈ I, j ∈ J. (4) The problem (1)-(4) is the known distribution task of linear programming [7, 8]. In general, for this task is not known methods that take into account its specificity, so to solve it apply universal methods of linear programming. For large-scale tasks, this approach requires commercial software. In addition, if problem (1)-(4) has no solution, the principle of making an acceptable decision is not clear in this statement. 306 A. Panyukov, K. Z. Chaloob 3 The Decomposable Case of Task (1)-(4) For some cases, the parameter λij can be represented as the product λij = αi · βj , i ∈ I, j ∈ J (5) where αi is the resource intensity of the commodity i ∈ I in conventional units, βj is the cost of servicing the conventional unit at the center j ∈ J. This case of the problem (1)-(4) is called as decomposable problem. It is possible decomposable problem (1)-(4) reducing to the matrix transportation problem. Indeed, for all j ∈ J we have ! ! X X λij xij ≤ bj ⇔ αi βj xij ≤ bj ⇔ i∈I i∈I ! ! X bj X bj αi xij ≤ ⇔ yij ≤ , βj βj i∈I i∈I here yij = αi · xij for all i ∈ I, j ∈ J. Passing to the variables yij = αi · xij for all i ∈ I, j ∈ J in problem (1)-(4) get     X X di   xij = di  ⇔  yij = , i ∈ I, αi j∈J j∈J XX X X pij y ij pij xij = . αi j∈J i∈I j∈J i∈I Thus, the problem (1)-(4) is equivalent to the following one X X pij y ij y o = arg max , (6) x∈D αi j∈J i∈I X di yij = , i∈I (7) αi j∈J X bj yij ≤ , j∈J , (8) βj i∈I yij ≥ 0, i ∈ I, j ∈ J. (9) The problem (6)-(9) is open matrix transportation problem [7, 8]. The encapsu- lated in the MS Office system software to solve such problems of large dimension is known [6]. Problem of Distribution of Goods 307 4 Regularization of Problems (1)-(4) and (6)-(9) Problem (6)-(9) (hence and (1)-(4)) has a solution when demand does not exceed the supply, i.e. X di X bj S= − ≤ 0. αi βj i∈I j∈J Otherwise (that is, if S > 0), the problems (1)-(4) and (6)-(9) do not have admissible solutions, and it is required to correct the original problem to find a suitable solution. Possible ways to adjust the conditions of these tasks are: 1. To allow the supply of all goods below the effective demand X di yij = − yi0 , yi0 ≥ 0, i ∈ I; αi j∈J 2. To develop the infrastructure of all routes in order to effectively support the effective demand X bj yij = + y0j , y0j ≥ 0, j ∈ J, βj i∈I where y0j is the amount of investment (in conventional units) in the devel- opment of the route j ∈ J. Let ki be the allowed fraction of the unsatisfied demand for the commodity i ∈ I (i.e. yi0 ≤ ki di ). Let p0j be the amount of investment required to expand the resources of the center j ∈ J by one conditional unit. Let us consider the corrected problem taking into account the variables and restrictions introduced in this section. ! X X pij y ij o y = arg max − p0j y0j , (10) y∈D αi j∈J i∈I X di yij + yi0 = , i ∈ I, (11) αi j∈J X bj yij − y0j = , j ∈ J, (12) βj i∈I yi0 ≤ ki di , i ∈ I, (13) yij , yi0 , y0j ≥ 0, i ∈ I, j ∈ J. (14) The problem (10)-(14) is closed matrix transportation problem [7]. The encapsu- lated in the MS Office system software to solve such problems of large dimension is known [6]. 308 A. Panyukov, K. Z. Chaloob Obviously, problem (10)-(14) has an optimal solution. The regularization is carried out by introducing additional endogenous variables yi0 , y0j ≥ 0, i ∈ I, j ∈ J, exogenous variables ki , i ∈ I, and constants p0j , j ∈ J. It is evident from the constructed model that at fixed prices maintaining effective demand leads to a decrease in marginal profit. Preservation of marginal profit requires an increase in the selling price of goods, which can lead to an irreversible decrease in demand and a decrease in marginal profit. Thus, the task of decision-making in conditions of risk and uncertainty arises. The controlled parameters in this case are the exogenous variables ki , i ∈ I. Let us use the marginal profit M and the amount of unmet demand S as criteria in the decision-making model. It is obvious that all solutions of problem (10)-(14) are Pareto optimal ones for fixed values of the exogenous variables ki , i ∈ I. The problem of choosing specific values of these variables is difficult to formalize and requires the participation of the decision-maker (DM). 5 Approximation of the Problem (1)-(4) by the Decomposable Problem As was noted above, problem (1)-(4) is decomposable if the equalities (5) hold. The value of the parameter λij is interpreted as the cost of distributing a unit of commodity i ∈ I by the center j ∈ J, and its value can be determined us- ing statistical measurements. On the contrary, the parameters {αi > 0 : i ∈ I}, {βj > 0 : j ∈ J} are interpreted using the term ”conventional unit”, therefore their direct statistical measurement is impossible. Therefore, we consider the equalities (5) as a system of algebraic equations with unknowns {αi > 0 : i ∈ I}, {βj > 0 : j ∈ J}. It is clear that for arbitrary values λij the system of equations (5) may be inconsistent. Let us introduce the function X αi βj Fλ (α, β) = log . λij i∈I, j∈J Obviously, inf Fλ = 0 if and only if the system of equations (5) is consistent. It follows from the nonnegativity of the function Fλ () that the value of inf Fλ can be considered as the degree of incompatibility of the system (5). Function Fλ (), λ > 0 is continuous in the neighborhood of any minimum, so the infimum is reached, and the optimal approximate solution of the system (5) with a minimal degree of incompatibility   X α β i j  (αo , β o ) = arg min  log {βj >0: j∈J} λij i∈I, j∈J {αi :>0: i∈I} can be considered. Problem of Distribution of Goods 309 It is easy to see that the optimality of the solution (αo , β o ) implies the op- timality of the solution set D = {(αo · c, β o /c) : c > 0}. We shall assume that the solution of the approximating problem is (α∗ , β ∗ ) = arg min k(α, β)k∞ . (15) (α,β)∈D Note that if (α, β) ∈ D then ( s )   max β maxi∈I αi r j∈J j α∗ = ak · , ∗ β = βk · . maxi∈I αi maxj∈J βj k∈J k∈I Thus, the correct formulation of the approximating problem is two-level, but for its solution it is sufficient to find any solution of the problem (1) of the lower level. 6 Algorithm to Solve Problem (15) The following algorithm allows us to solve the problem (15). Decomposition algorithm Input: I, J, Λ = {λij }i∈I, j∈J ; Output: α = {αi }i∈I , β = {βj }j∈J , FΛ (α, β); Step 1. (Construct matrix Λ̂). For each line i ∈ I of the matrix Λ execute steps 1.1, 1.2 and 1.3, then go to step 2. Step 1.1. Build sorted line i ∈ I n (k) Λ [i] = λij (k) : o (1) (2) (|J|) k = 1, 2, . . . , |J| , j (k) ∈ J, λij (1) ≤ λij (2) ≤ . . . ≤ λij (|j|) , . j k l m r |J|+1 |J|+1 (k ) (k ) Step 1.2. Let k− = 2 , k+ = 2 , αi = λ (+k+ ) · λ (−k− ) . ij ij (k) (k) λ (k) ij Step 1.3. For k = 1, 2, . . . , |J| let λ̂ij (k) = αi . Step 2. (Construct matrix Λ̃). For each column j ∈ J of the matrix Λ̂ execute steps 2.1, 2.2 and 2.3, then go to step 3. Step 2.1. Build sorted column j ∈ J n (k) Λ̂ [∗] [j] = λ̂i(k) j : o (1) (2) (|I|) k = 1, 2, . . . , |J| , j (k) ∈ J, λ̂i(1) j ≤ λ̂i(2) j ≤ . . . ≤ λ̂i(|I|) j . j k l m r |I|+1 |I|+1 (k ) (k ) Step 2.2. Let k− = 2 , k+ = 2 , βj = λ̂ (k++ ) · λ̂ (k−− ) . i j i j 310 A. Panyukov, K. Z. Chaloob (k) (k) λ̂ (k) li(k) j = iβj j . Step 2.3. For k = 1, 2, . . . , |I| let e Step 3. (Normalization). r Follow steps 3.1, 3.2, and 3.3, and then go to step 4. maxi∈I αi Step 3.1. Let c = . maxj∈J βj Step 3.2. For all i ∈ I let αi = αi /c. Step 3.3. For all j ∈ J let βj = βj · c. P α β Step 4. Let FΛ (α, β) = i∈I, j∈J log λi ij j . n o Step 5. Return α = {αi }i∈I , β = {βj }j∈J , FΛ (α, β) . End. Theorem 1. Decomposition algorithm correctly solves problem (15). Its alge- braic computational complexity does not exceed the value O (|I| · |J| · log (|I| · |J|)). Proof. Monotony of the logarithmic function implies   αi βj log = 0 ⇔ (− log λij + log αi + log βj = 0) λij  ⇔ −lij + xi − yj = 0, lij = log λij , xi = log αi , y j = log βj , i ∈ I, j ∈ J, Therefore problem (15) is equivalent to problem X (xo , y o ) = arg min |−lij + xi − yj | (16) x∈R|I| i∈I, j∈J y∈R|J| and there is the one-to-one correspondence between the optimal solutions of these problems. Problem (16) is equivalent to linear programming problem X wij → min , (17) x,y,w i∈I, j∈J −wij ≤ −lij + xi + yj ≤ wij , wij ≥ 0, i ∈ I, j ∈ J. (18) Dual problem (17)-(18) is the problem X lij (fij − fji ) → max , (19) f i∈I, j∈J X (fij − fji ) = 0, i ∈ I, (20) j∈J X (fij − fji ) = 0, j ∈ J, (21) i∈I fij + fji ≤ 1, fij , fji ≥ 0, i ∈ I, j ∈ J. (22) Problem of Distribution of Goods 311 Making the change of variables gij = fij − fji , i ∈ I, j ∈ J in problem (19)-(22) we get the problem of maximum weight circulation X lij gij → max , (23) g i∈I, j∈J X gij = 0, i ∈ I, (24) j∈J X gij = 0, j ∈ J, (25) i∈I −1 ≤ gij ≤ 1, i ∈ I, j ∈ J. (26) Dual problem (23)-(26) is the problem X TΛ (r, s, t) = (tij + tji ) → min , (27) r,s,t i∈I, j∈J ri + sj + tij − tji = lij , tij , tji ≥ 0, i ∈ I, j ∈ J. (28) Let us compare problem (17)-(18) constraints system and problem (27)-(28) constraints system. It is easy to see that the admissibility of the basic solution (r, s, t) of problem (27)-(28) implies the admissibility of solution R = (x = r, y = s, w = {wij = tij + tji : i ∈ I, j ∈ J}) of problem (17)-(18). Moreover, if (r, s, t) is an optimal solution of problem (27)- (28), then R is an optimal solution of problem (17)-(18), since dual problems (19)-(22) and (23)-(26) have corresponding optimal solutions. The one-to-one compilation of algorithm Decomposition in terms of values (x, y, l)) can be represented as following algorithm. Log Decomposition algorithm Input: I, J, L = {lij i ∈ I, j ∈ J}; Output: x = {xi i ∈ I} , y = {yj j ∈ J} , FL (x, y); Step 1. (Construct matrix L̂). For each line i ∈ I of the matrix L execute steps 1.1, 1.2 and 1.3, then go to step 2. Step 1.1. Build sorted line i ∈ I n (k) L [i] = lij (k) : o (1) (2) (|J|) k = 1, 2, . . . , |J| , j (k) ∈ J, lij (1) ≤ lij (2) ≤ . . . ≤ lij (|j|) , . (k+ ) (k− ) j k l m l k ) +l (k ) |J|+1 |J|+1 ij + ij − Step 1.2. Let k− = 2 , k+ = 2 , ri = 2 . (k) (k) Step 1.3. For k = 1, 2, . . . , |J| let ˆlij (k) = lij (k) − ri . Step 2. (Construct matrix L̃). For each column j ∈ J of the matrix L̂ execute steps 2.1, 2.2 and 2.3, then go to step AUX. 312 A. Panyukov, K. Z. Chaloob Step 2.1. Build sorted column j ∈ J n (k) L̂ [∗] [j] = ˆli(k) j : o (1) (2) (|I|) k = 1, 2, . . . , |J| , j (k) ∈ J, ˆli(1) j ≤ ˆli(2) j ≤ . . . ≤ ˆli(|I|) j . (k ) (k ) j k l m l̂ (k+ ) +l̂ (k− ) |I|+1 |I|+1 + j − j Step 2.2. Let k− = 2 , k+ = 2 , sj = i 2 i . (k) (k) li(k) j = ˆli(k) j − sj . Step 2.3. For k = 1, 2, . . . , |I| let e Step AUX. (Construct matrix T) For all i ∈ I, j ∈ J execute steps AUX.1 and AUX.2 then go to step 3. Step AUX.1 If ˜lij > 0, then put tij = ˜lij , tji = 0, otherwise put tji = −˜lij , tij = 0. Step AUX.2 Calculate X TΛ (r, s, t) = (tij + tji ) . i∈I, j∈J Step 3. (Normalization). Follow steps 3.1, 3.2, and 3.3, and then go to step 4. Step 3.1. Let maxi∈I xi − maxj∈J yj c= . 2 Step 3.2. For all i ∈ I let ri = ri − c. n all j ∈ J let sj = sj + c. Step 3.3. For o Step 4. Return x = {ri }i∈I , y = {sj }j∈J , TΛ (r, s, t) . End. Here an auxiliary step AUX is introduced to prove the effectiveness of the algorithms. The optimal values of the variables tij , tji , i ∈ I, j ∈ J and the optimal value TΛ (r, s, t) for the problem (27)-(28) are calculated at step AUX. It is obvious that the solution (r, s, t), constructed by Log Decomposition algorithm, meets all constraints of the problem (27)-(28). On the other hand problem (23)-(26) has an integral-valued optimal solution [10], i.. in the optimal solution g for all i ∈ I, j ∈ J there is an inclusion gij ∈ {−1, 0, 1}. Let us to construct the solution {gi j i ∈ I, j ∈ J} of problem (23)-(26) using the conditions of complimentary with respect to solutions (r,s,t) of the dual problem (27)-(28), i.e. put (1) gij = −1 for all i ∈ I, j ∈ J such that tij = 0, tji > 0; (2) gij = 1 for all i ∈ I, j ∈ J such that tij > 0, tji = 0; (3) gij = 0 for all i ∈ I, j ∈ J such that tij = tji = 0. It is easy to see that the constructed solution {gij i ∈ I, j ∈ J} is an admissible solution of problem (23)-(26). It follows form the second duality theorem in linear programming that (r, s, t) and {gij i ∈ I, j ∈ J} are optimal solutions Problem of Distribution of Goods 313 of the problems (23)-(26) and (27)-(28) correspondingly. The effectiveness of Log Decomposition algorithm, hence Decomposition algorithm, is proved. Let us to turn to the estimation of Decomposition algorithm computational complexity. The body of Step 1 contains the sorting of the elements of the row (computational complexity O(|J| log |J|)) and recalculation of its elements (computational complexity O(|J|)). Consequently, computational complexity of Step 1 does not exceed values O(|I||J| log (|J|) ). Analogous arguments for Step 2 lead to the validity of the assertion that computational complexity of Step 2 does not exceed O(|I||J| log (|I|) ). Therefore, the total computational complexity of Steps 1 and 2 will not exceed the values O(|I||J| log (|I||J|) ). Step 3 consists of computation of value c and recalculation of values α = {αi i ∈ I} , β = {βj j ∈ J} , its computational complexity does not exceed O(|I||J|). Step 4 consists of summing the O(|I||J|) elements, its computational complexity does not exceed O(|I||J|) as well. Thus, computational complexity of the algorithm does not exceed O(|I||J| log (|I||J|) ). The theorem is proved. 7 Conclusion The proposed algorithms solve the problems of analyzing the distribution of goods by logistics centers, including a decision support system in case of in- correctness of the task. Software implementation of these algorithms is easily encapsulated in the MS Office system. References 1. Bayev, I.A., Drozin, D.A.: Dinamika pokupatel’skogo sprosa innovatsionnogo to- vara (Dynamics of consumer demand for innovative goods). Bulletin of the South Ural State University. Ser. Economics and Management 8(2), 80–85 (2014), (in Russian) 2. Budashevsky, V.G., Pastukhova, O.N.: Tekhnologiya adaptivnogo upravleniya sinergeticheskim vzaimodeystviyem sprosa i predlozheniya na osnove proyektno- issledovatel’skogo kompleksnogo marketingovogo eksperimenta (Technology of adaptive management of the synergistic interaction of supply and demand on the basis of a project-research complex marketing experiment). Bulletin of the South Ural State University. Ser. Economics and Management 10(4), 60–65 (2016), (in Russian) 3. Galyautdinov, R.R.: The mechanisms of interaction of flows and stocks at enter- prise from the perspective of logistics. Bulletin of the South Ural State University. Ser. Economics and Management 10(1), 157–163 (2016) 4. Levina, A.L.: Klassifikatsiya predpriyatiy roznichnoy torgovli s uchetom priznakov logisticheskoy integratsii (Classification of retail enterprises taking into account the signs of logistical integration). Bulletin of the South Ural State University. Ser. Economics and Management 10(4), 170–175 (2016), (in Russian) 5. Panyukov, A., Teleghin, V.: Forming of discrete mechanical assembly production program. Journal of Computational and Engineering Mathematics 2(1), 57–64 (2015) 314 A. Panyukov, K. Z. Chaloob 6. Panyukov, A., Telegin, V.: Tekhnika programmnoy realizatsii potokovykh algo- ritmov (Engineering software implementation flow algorithms). Vestnik Yuzhno- Ural’skogo gosudarstvennogo universiteta. Seriya: Matematicheskoe modelirovanie i programmirovanie (Bulletin of South Ural State University. Series: Mathematical modeling and programming) 27(127), 78–99 (2008), (in Russian) 7. Raskin, L., Kirichenko, I.: Mnogoindeksnyye Zadachi Lineynogo Program- mirovaniya (Multi-index Problems of Linear Programming). Radio i svyaz’, Moscow (1989), (in Russian) 8. Sira, O.V.: Raspredelitel’naya zadacha lineynogo programmirovaniya (Distribu- tion linear programming problem). Systemy obrobky informatsiyi (Information Processing Systems) 2(109), 168–170 (2013), (in Russian) 9. Stok, J.R., Lambert, D.M.: Strategic Logistics Management. McGraw-Hill/Irwin (2000) 10. Yemelichev, V.A., Kovalev, M.M., Kravtsov, M.K.: Polytopes, Graphs and Opti- mization. Cambridge University Press, New York (1986)