• D. I. Symonov Department of Microprocessor Technology, V. M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kyiv, Ukraine
Keywords: Supply Chain, maximum flow, minimum cut, throughput, Ford–Fulkerson algorithm


The paper considers several methods of analyzing opportunities for optimizing supply chains. An iterative method of finding the optimal structure is proposed, considering the power of the supply chain links and the capacity of the paths between them. The theorem on the value of the maximum flow in the combined path is proved. A numerical simulation of the operation of the proposed algorithm for finding directions for the optimization of the network structure was performed.


Godonoga A. F., Blanutsa S. A., Chumakov B.M. Algorithm for adjusting input and output flows in a production process. Theory of Optimal Solutions. 2005. No 18. P. 34–39.

Symonov D. I. Algorithm for determining the optimal flow in Supply Chains, considering multi-criteria conditions and stochastic processes. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics. 2021. No 2. P. 109-116.

Stetsyuk P. I., Bysaha O. P., Tregubenko S. S. Two-stage transportation problem with constraint on the number of intermediate locations. Computer Mathematics. 2018. No 2. P. 119–128.

Zhang B., Peng J. Uncertain Graph and Network Optimization. Springer Singapore, 2022. P. 130.

Gulyanytskyi L.F., Pavlenko A.I. Modeling time-dependent problems of finding optimal routes: an overview. Mathematical modeling in economics. 2017. No 1-2. P. 102–116.

Chen L., Kyng R., Liu Y. P., Peng R., Gutenberg M. P., Sachdeva S. Maxi-mum Flow and Minimum-Cost Flow in Almost-Linear Time. IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 2022. P. 612–623.

Donets G. A., Kolechkina L. N. An approach to solving extremal problems using graphs. Theory of Optimal Solutions. 2016. P. 142–148.

Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms. Springer Berlin, Heidelberg, 2007. P. 627.

Dantzig G. B., Fulkerson D. R. On the Max Flow Min Cut Theorem of Networks. In: Linear Inequalities and Related Systems. Princeton: Princeton University Press, 1956. P. 215–221

Yemets O. O., Yemets E. M., Oleksiychuk Yu. F. Polynomial method of approximate solution of the combinatorial problem of finding the maximum flow in the network. Reports of the National Academy of Sciences of Ukraine. 2013. No 4. P. 33–37.