Локальное управление входящими потоками в регулярных ресурсных сетях с малым ресурсом

Локальное управление входящими потоками в регулярных ресурсных сетях с малым ресурсом

Евсеенко А. В., Скороходов В. А.
Дискретный анализ и исследование операций, 32, 2, 30-53 (2025)
Скачать статью

УДК 519.1 
DOI: 10.33048/daio.2025.32.823

Аннотация:

Работа посвящена решению задачи локального управления входящими потоками в регулярных ресурсных сетях с малым ресурсом. Для таких сетей указано множество управляемых вершин. Задача локального управления состоит в определении таких пропускных способностей дуг, входящих в управляемые вершины, что единственное предельное состояние регулярной ресурсной сети $Q^∗$ наиболее близко к заранее заданному состоянию $Q^′$. Получены условия недостижимости предельного состояния, совпадающего с заданным состоянием $Q^′$. Рассмотрены различные конфигурации ресурсных сетей относительно распределения управляемых вершин в них. Показано, что если условия недостижимости предельного состояния не выполняются, то всегда найдётся такой набор пропускных способностей дуг, входящих в управляемые вершины, для которого предельное состояние $Q^∗$ равно заданному состоянию $Q^′$. 

Ил. 2, библиогр. 21.

Литература:
  1. Ford L. R., Fulkerson D. R. Constructing maximal dynamic flows from static flows // Oper. Res. 1958. V. 6, No. 3. P. 419–433. DOI: 10.1287/opre.6.3.419.
     
  2. Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. М.: Мир, 1966. 276 c.
     
  3. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 c.
     
  4. Aronson J. E. A survey of dynamic network flows // Ann. Oper. Res. 1989. V. 20. P. 1–66. DOI: 10.1007/BF02216922.
     
  5. Fonoberova M. A., Lozovanu D. D. The maximum flow in dynamic networks // Comput. Sci. J. Moldova. 2004. No. 12. P. 387–396.
     
  6. Кузьминова М. В. Периодические динамические графы. Задача о максимальном потоке // Изв. вузов. Сев.-Кавказ. регион. Естеств. науки. 2008. № 5. С. 16–20.
     
  7. Жилякова Л. Ю. Несимметричные ресурсные сети. I. Процессы стабилизации при малых ресурсах // Автоматика и телемеханика. 2011. № 4. P. 133–143.
     
  8. Жилякова Л. Ю. Управление предельными состояниями в поглощающих ресурсных сетях // Пробл. упр. 2013. № 3. P. 51–59.
     
  9. Кузнецов О. П., Жилякова Л. Ю. Двусторонние ресурсные сети — новая потоковая модель // Докл. Акад. наук. 2010. Т. 433, № 5. С. 609–612.
     
  10. Kuznetsov O. P. Nonsymmetric resource networks. The study of limit states // Manage. Prod. Eng. Rev. 2011. V. 2, No. 3. P. 33–39.
     
  11. Скороходов В. А., Ерусалимский Я. М., Муртузалиева С. Ч. Задача нахождения начального состояния ресурсной сети // Итоги науки и техники. Соврем. математика и её прил. Тем. обзоры. Т. 209. М.: ВИНИТИ РАН, 2022. С. 42–52. DOI: 10.36535/0233-6723-2022-209-42-52.
     
  12. Жилякова Л. Ю., Чаплинская Н. В. Исследование полных однородных ресурсных сетей с «жадными» вершинами // Упр. большими системами. Вып. 89. М.: ИПУ РАН, 2021. С. 5–44. DOI: 10.25728/ubs.2021.89.1.
     
  13. Чаплинская Н. В. Исследование эргодических неоднородных ресурсных сетей с «жадными» вершинами // Упр. большими системами. Вып. 93. М.: ИПУ РАН, 2021. С. 5–50. DOI: 10.25728/ubs.2021.93.1.
     
  14. Kuznetsov O. P., Zhilyakova L. Yu. Flows and limit states in bidirectional resource networks // IFAC Proc. Vol. 2011. V. 44, No. 1. P. 14031–14035. DOI: 10.3182/20110828-6-IT-1002.00766.
     
  15. Zhilyakova L. Yu., Koreshkov V. R., Chaplinskaya N. V. Some properties of stochastic matrices and non-homogeneous Markov chains generated by nonlinearities in the resource network model // Mathematics. 2022. V. 10. Article ID 4095. 18 p. DOI: 10.3390/math10214095.
     
  16. Abdulrahman H. N., Erusalimskiy Ya. M. On the realizability of stationary flows in resource networks by flows in classical networks // J. Math. Sci. 2024. V. 280. P. 733–740. DOI: 10.1007/s10958-024-07093-1.
     
  17. Skorokhodov V. A., Erusalimskiy Ya. M. Flows local control in resource networks with a low resource // Math. Stat. 2023. V. 11, No. 2. P. 300–307. DOI: 10.13189/ms.2023.110208.
     
  18. Берж К. Теория графов и её применения. М.: Изд-во иностр. лит., 1962. 320 с.
     
  19. Скороходов В. А., Свиридкин Д. О. Потоки в сильно регулярных периодических динамических ресурсных сетях // Вестн. Удмурт. унта. Сер. Математика. Механика. Компьют. науки. 2021. Т. 31, вып. 3. С. 458–470. DOI: 10.35634/vm210308.
     
  20. Жилякова Л. Ю., Кузнецов О. П. Теория ресурсных сетей. М.: ИЦ РИОР, 2023. 283 с.
     
  21. Скороходов В. А. Задача нахождения порогового значения в эргодической ресурсной сети // Упр. большими системами. Вып. 63. М.: ИПУ РАН, 2016. С. 6–23.

Исследование выполнено за счёт бюджета Института математики, механики и компьютерных наук им. И. И. Воровича ЮФУ. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Евсеенко Александр Викторович
  1. Институт математики, механики и компьютерных наук им. И. И. Воровича 
    Южного федерального университета, 
    ул. Мильчакова, 8а, 344090 Ростов-на-Дону, Россия

E-mail: aevseenko@sfedu.ru

Скороходов Владимир Александрович
  1. Институт математики, механики и компьютерных наук им. И. И. Воровича 
    Южного федерального университета, 
    ул. Мильчакова, 8а, 344090 Ростов-на-Дону, Россия

E-mail: vaskorohodov@sfedu.ru

Статья поступила 11 декабря 2024 г
После доработки — 15 января 2025 г.
Принята к публикации 22 марта 2025 г.

Abstract:

The paper is devoted to solving the problem of local in-flows control in regular resource networks with a low resource. For such networks, a set of controlled vertices is specified. The local control problem is to determine such capacities of arcs entering the controlled vertices that the unique limit state of regular resource network $Q^∗$ is the closest to the given state $Q^′$. Conditions for the unreachability of the limit state that coincides with the state $Q^′$ are obtained. Various configurations of resource networks with respect to the distribution of controlled vertices in them are considered. It is shown that if the conditions for the unreachability of the limit state are not satisfied, then there is such a set of capacities of arcs entering the controlled vertices for which the limit state $Q^∗$ is equal to the given state $Q^′$. 

Illustr. 2, bibliogr. 21.

References:
  1. L. R. Ford and D. R. Fulkerson, Constructing maximal dynamic flows from static flows, Oper. Res. 6 (3), 419–433 (1958), DOI: 10.1287/opre.6.3.419.
     
  2. L. R. Ford and D. R. Fulkerson, Flows in Networks (Princeton Univ. Press, Princeton, NJ, 1962; Mir, Moscow, 1966 [Russian]).
     
  3. N. Christofides, Graph Theory: An Algorithmic Approach (Acad. Press, London, 1975; Mir, Moscow, 1978 [Russian]).
     
  4. J. E. Aronson, A survey of dynamic network flows, Ann. Oper. Res. 20, 1–66 (1989), DOI: 10.1007/BF02216922. 
     
  5. M. A. Fonoberova and D. D. Lozovanu, The maximum flow in dynamic networks, Comput. Sci. J. Moldova., No. 12, 387–396 (2004).
     
  6. M. V. Kuzminova, Periodic dynamic graphs. Maximum flow problem, Izv. Vyssh. Uchebn. Zaved., Sev.-Kavk. Reg., Estestv. Nauki, No. 1, 14–19 (2008) [Russian].
     
  7. L. Yu. Zhilyakova, Asymmetrical resource networks. I. Stabilization processes for low resources, Avtom. Telemekh., No. 4, 133–143 (2011) [Russian] [Autom. Remote Control 72 (4), 798–807 (2011), DOI: 10.1134/ S0005117911040102].
     
  8. L. Yu. Zhilyakova, The limit states control in absorbing resource networks, Probl. Upr., No. 3, 51–59 (2013) [Russian] [Autom. Remote Control. 75 (2), 360–372 (2014), DOI: 10.1134/S0005117914020143].
     
  9. O. P. Kuznetsov and L. Yu. Zhilyakova, Bidirectional resource networks: A new flow model, Dokl. Akad. Nauk 433 (5), 609–612 (2010) [Russian] [Dokl. Math. 82, 643–646 (2010), DOI: 10.1134/S1064562410040368].
     
  10. O. P. Kuznetsov, Nonsymmetric resource networks. The study of limit states, Manage. Prod. Eng. Rev. 2 (3), 33–39 (2011).
     
  11. V. A. Skorokhodov, Ya. M. Erusalimskiy, and S. Ch. Murtuzalieva, The problem of finding the initial state of a resource network, in Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz., Vol. 209 (VINITI RAN, Moscow, 2022), pp. 42–52, DOI: 10.36535/0233-6723-2022-209-42-52 [Russian].
     
  12. L. Yu. Zhilyakova and N. V. Chaplinskaya, Research of complete homogeneous “greedy-vertices” resource networks, in Upr. Bolsh. Sist., Vol. 89 (IPU RAN, Moscow, 2021), pp. 5–44, DOI: 10.25728/ubs.2021.89.1 [Russian].
     
  13. N. V. Chaplinskaya, Research of ergodic heterogeneous “greedy-vertices” resource networks, in Upr. Bolsh. Sist., Vol. 93 (IPU RAN, Moscow, 2021), pp. 5–50, DOI: 10.25728/ubs.2021.93.1 [Russian].
  14.  
  15. O. P. Kuznetsov and L. Yu. Zhilyakova, Flows and limit states in bidirectional resource networks, IFAC Proc. Vol. 44 (1), 14031–14035 (2011), DOI: 10.3182/20110828-6-IT-1002.00766.
     
  16. L. Yu. Zhilyakova, V. R. Koreshkov, and N. V. Chaplinskaya, Some properties of stochastic matrices and non-homogeneous Markov chains generated by nonlinearities in the resource network model, Mathematics 10, ID 4095 (2022), DOI: 10.3390/math10214095.
     
  17. H. N. Abdulrahman and Ya. M. Erusalimskiy, On the realizability of stationary flows in resource networks by flows in classical networks, J. Math. Sci. 280, 733–740 (2024), DOI: 10.1007/s10958-024-07093-1.
     
  18. V. A. Skorokhodov and Ya. M. Erusalimskiy, Flows local control in resource networks with a low resource, Math. Stat. 11 (2), 300–307 (2023), DOI: 10.13189/ms.2023.110208.
     
  19. C. Berge, Théorie des graphes et ses applications, (Dunod, Paris, 1958 [French]; Izd. Inostr. Lit., Moscow, 1962 [Russian]).
     
  20. V. A. Skorokhodov and D. O. Sviridkin, Flows in strongly regular periodic dynamic resource networks, Vestn. Udmurt. Univ., Mat. Mekh. Kompyut. Nauki 31 (3), 458–470 (2021), DOI: 10.35634/vm210308 [Russian].
     
  21. L. Yu. Zhilyakova and O. P. Kuznetsov, Theory of Resource Networks (ITs RIOR, Moscow, 2023) [Russian].
     
  22. V. A. Skorokhodov, The problem of finding the threshold value in ergodic resource network, in Upr. Bolsh. Sist., Vol. 63 (IPU RAN, Moscow, 2016), pp. 6–23 (2016) [Russian].