The result of solving the transport problem in the network formulation is the magnitude of the flows on the arcs of the network. However, this type of solution is not always satisfactory. In fact, it is often necessary to know not only the magnitude of the loads on the network arcs, but also the connections formed between suppliers and consumers. The presented connections are considered on the example of the market of the BRICS member countries. To establish such links within the framework of the optimal plan, algorithms for linking suppliers to consumers are used.
transport task, suppliers, consumers, BRICS, sustainability
- Введение
Для решения транспортных задач в классической постановке существует довольно много эффективных алгоритмов и программ [1−5]. Однако зачастую при решении практических проблем недостаточно один раз решить транспортную задачу. Часто транспортная задача используется как элемент итеративного процесса, например, при решении задач размещения с дополнительными ограничениями нетранспортного типа или задач с нелинейными ценами [6−11]. В таких случаях полученный в результате решения оптимальный план является лишь этапом работы [12–15, 31]. В зависимости от результатов изменяются исходные задачи, и транспортная задача решается заново. Однако такой способ нельзя признать экономным с точки зрения вычислительной эффективности [16−20]. Для этого необходимо при внесении изменений в исходные данные корректировать полученный ранее оптимальный план при помощи специальных процедур. В настоящей работе приводятся алгоритмы формирования связей поставщиков и потребителей.
- Типовая исходная задача
Пусть задана ориентированная сеть 
где 
– множество вершин сети, 
– множество ориентированных дуг, 
– величина потоков на дугах. Предположим, что 
для всех 
.
Для каждой вершины 
определим два множества дуг: 
– множество входящих дуг, 
– множество входящих.
Величину 
будем называть мощностью вершины. Если 
, то вершина является поставщиком, если 
– потребителем, а если 
– промежуточной вершиной.
Целью мы называем последовательность ориентированных дуг заданным на ней положительным потоком:
.
Началом цепи всегда будет поставщик, а концом – потребитель. Цепи служат для описания связей между поставщиками и потребителями. Задание цепи 
означает, что поставщик 
отправляет потребителю 
единиц продукта через пункты 
. Через 
будем обозначать начальную вершину цепи, через 
– конечную, а через 
– поток цепи.
В данной задаче требуется найти такое множество цепей 
чтобы выполнялись следующие условия.
Для любой цепи
(1)
Для каждой вершины
при
(2)
при
Для каждой дуги
(3)
Первое условие означает, что цепи начинаются в поставщиках и заканчиваются в потребителях. Второе условие означает, что сумма потоков по цепям, начинающимся в поставщике, равна мощности этого поставщика, а сумма потоков по цепям, заканчивающимся в потребителе, равна абсолютной величине его мощности. Из третьего условия следует, что сумма потоков по цепям, проходящим через данную дугу, не превосходит потока по этой дуге. Легко заметить, что эти три условия формализуют интуитивные представления о правилах привязки поставщиков к потребителям [21−25].
- Формализованное представление алгоритма
Представим алгоритм построения искомого множества цепей сначала в случае ациклической сети – сети без ориентированных циклов. На самом деле, в результате решения транспортной задачи в абсолютном большинстве случаев будет получена именно ациклическая сеть. Действительно, для транспортной задачи без ограничений пропускной способности решение будет деревом, а для транспортной задачи с ограничениями ориентированный цикл в оптимальном плане может появиться только тогда, когда в исходной сети существует ориентированный цикл, состоящий из дуг нулевой стоимости [26, 27].
Прежде чем перейти к описанию алгоритма, необходимо сформулировать определение и доказать одно свойство ациклических сетей.
Вершина, в которую не входит ни одна дуга, называется исходной, а вершина, из которой не выходит ни одной дуги, называется тупиковой [ 28−30].
Лемма 1. В ациклической сети найдется одна исходная вершина.
Доказательство. Пусть это не так и в любую вершину входит хотя бы одна дуга. Рассмотрим произвольную вершину сети . Возьмем (
, входящую в вершину сети . Далее возьмем дугу 
и т.д. Прерваться этот процесс не может, по предположению. Рассмотрим полученную последовательность вершин 
. Среди них найдутся одинаковые: 
. Но тогда дуги (
(
образуют ориентированный цикл, что противоречит ацикличности сети.
Коротко опишем структуру информации, необходимую для работы алгоритма. В каждой вершине нам нужен список выходящих из нее дуг. Обозначим этот список через . Кроме того, для каждой вершины будем помнить 
– количество входящих в нее дуг.
Алгоритм привязки выглядит следующим образом.
- Выбираем вершину такую, что
Если такой вершины нет, то заканчиваем работу. Иначе переходим к шагу 2. - Если вершина тупиковая, т.е.
пуст, то удаляем из сети и переходим к шагу 1. Если не пуст, то объявляем последней вершиной построенной цепи. Полагаем 
. Переходим к шагу 3. - Пусть последняя вершина цепи. Если
пуст, заканчиваем построение цепи и переходим к шагу 4. Если не пуст, то обозначим через 
конечную вершину 1-й дуги списка 
. Полагаем, 
Объявляем последней вершиной цепи и повторяем шаг 3. - Добавляем цепь
(
в список построенных цепей.
На всех дугах цепи производим пересчет потоков:
Если после пересчет 
, то выбрасываем дугу 
из списка 
и уменьшаем 
на единицу. Переходим к шагу 2.
Из леммы 1 следует, что алгоритм закончит работу, когда все вершины будут удалены из сети.
Рассмотрим теперь сеть, содержащую циклы. В этом случае описанный алгоритм не применим. Для того, чтобы получить возможность им пользоваться, необходимо предварительно «разорвать» в сети все ориентированные циклы, что и делает приведенный ниже алгоритм удаления циклов. Информация, используемая этим алгоритмом, такая же, как и у предыдущего.
Алгоритм удаления циклов выглядит следующим образом.
- Берем произвольную непросмотренную вершину сети . Если все вершины просмотрены, то заканчиваем работу. Объявляем последней вершиной построенной последовательности вершин.
- Пусть последняя вершина построенной последовательности.
- Пусть
пуст. Объявляем 
просмотренной.
- Пусть
Если 
, то объявляем 
последней вершиной последовательности; дугу 
удаляем из списка 
и повторяем шаг 2.
Если 
, то переходим к шагу 1.
-
- Пусть не пуст. Обозначим через
конечную вершину 1-й дуги списка .
- Пусть
Если вершина ранее не принадлежала построенной последовательности, то объявляем последней вершиной последовательности и повторяем шаг 2.
Если 
, то построен ориентированный цикл. Переходим к шагу 3.
- Вычисляем
– минимум величин потоков на цикле. На всех дугах цикла производим пересчет потоков:
Если на дуге 
поток стал равен нулю, то удаляем ее из списка 
и исключаем эту дугу из сети.
Объявляем 
последней вершиной построенной последовательности и переходим к шагу 2.
В следующем пункте будет доказано, что после окончания работы этого алгоритма получается ациклическая сеть и для привязки поставщиков и потребителей можно пользоваться ранее описанным алгоритмом.
- Прежде всего заметим, что при построении в первом алгоритме цепи, благодаря ацикличности сети, мы всегда достигнем тупиковой вершины за конечное число шагов. Ясно, что отсюда легко следут конечность описанного алгоритма. Докажем теперь, что множество построенных цепей удовлетворяет требованиям, сформулированным в п. 2.
Лемма 2. В описанном алгоритме началом построенной цепи может быть только поставщик, а концом – только потребитель.
Доказательство. Пусть 
`Если – исходная вершина цепи, то 
и, следовательно, множество входящих в дуг 
пуст. Отсюда следует, что 
и 
, а также 
и 
, т.е. мощность исходной вершины положительна, а конечной – отрицательна. Заметим, что после пересчета потоков на цепи мощности внутренних вершин не меняеются, мощность уменьшается на , а мощность увеличивается на . Но 
остается неотрицательной, а 
yе положительной, так как 
, а 
. Следовательно, знаки Q после пересчета сохраняются. Так как началом цепи всегда является вершина с положительной, а концом – вершина с отрицательной мощностью, то из того, что мощность сохраняет знак при преобразовании потоков, непосредственно следует утверждение леммы.
Лемма 3. Сумма потоков по всем цепям, выходящим из поставщика, равна мощности этого поставщика.
Доказательство. Пусть веришна – поставщик. Из леммы 2 следует, что не может быть конечной вершиной цепи. Значит прежде чем станет начальной вершиной, она может быть только промежуточной. Следовательно, в момент, когда стала начальной вершиной, мощность по сравнению с началом работы алгоритма не изменилась и равна сейчас 
. Пусть 
– цепи, началом которых является 
Если стала начальной вершиной цепи, то другая вершина может стать началом цепи только когда 
будет исчерпан. Однако, если исчерпан, то =0. Следовательно, 
, что и требовалось доказать.
Лемма 4. Сумма потоков по всем цепям, заканчивающимся в потребителе, равна по абсолютной величине мощности.
Доказательство. Во-первых, сумма потоков на заканчивающихся в потребителе цепях не может по абсолютной величине превышать мощность потребителя, так как, по лемме 2, потребитель может быть только концом цепи, а знаки мощности не меняются. Из определения следует, что сумма мощностей всех вершин сети равна нулю, значит 
Но, по лемме 3 
Так как сумма потоков на цепях, заканчивающихся в потребителе, не превосходит по абсолютной величине его мощности, то из равенства 
следует, что для каждого потребителя 
Лемма доказана.
Приведем теперь полное обоснование первого алгоритма. Из лемм 2-4 непосредственно следует справедливость условий (1) и (2) для построенного множетсва цепей. Условие (3) выполняется потому, что каждый раз, назначая поток по цепи, мы соотвественно уменьшаем потоки на дугах. Таким образом, для построенного множества цепей выполняются все три условия привязки.
Далее необходимо доказать, что после выполнения второго алгоритма будет получена ациклическая сеть. Докажем, что через пространственную вершину не может проходить ориентированный цикл. У просмотренной вершины список А пуст, поэтому достаточно доказать, что через дугу, выбрасываемую из списка А, цикл не проходит. Докажем это утверждение индукцией по порядку выбрасывания дуг. Дуга выбрасывается из списка, если поток на ней стал равен нулю или если она входит в вершину с пустым списком А. В первом случае очевидно, что никакой цикл по этой дуге пройти не может, так как дуга с нулевым потоком исключается из сети. Во втором случае, если это первая выбрасываемая дуга, то она входит в вершину, из которой вообще нет выходящих дуг, т.е. никакой цикл через эту дугу не пройдет. Если же это не первая выбрасываемая дуга, то она входит в вершину с пустым списком А, но через дуги, ранее выброшенные из списков, циклы не проходят по предположению индукции. Следовательно, циклы не проходят и через нашу дугу. Таким образом, доказано, что через просмотренную вершину циклы не проходят. Так как в конце работы алгоритма все вершины просмотрены, то результатом работы является ациклическая сеть.
- Также необходимо остановиться на оценке трудоемкости алгоритмов. Из описания первого алгоритма следует, что при построении одной цепи мы работаем только с принадлежащими этой цепи дугами. На обработку дуги требуется конечное число операций. Следовательно, общую трудоемкость алгоритма можно оценить величиной порядка
, где n – число вершин сети, а 
– сумма длин всех построенных цепей. Слагаемое 
появляется из-за того, что мы тратим некоторое количество действий на обработку первой вершины цепи; при этом цепь может и не быть построена. Трудоемкость второго алгоритма оценивается величиной порядка 
, где р – число дуг сети, а 
– сумма длин всех уничтожаемых циклов. Слагаемое 
появляется потому, что мы расходуем некоторое количество действий на удаление дуг из списков А, а слагаемое 
– потому что на каждой дуге построенного цикла (и только на них) мы выполняем некоторые действия. Из самого вида этих оценок ясно, что они близки к оптимальным. Отметим, что после пересчета потоков на цепи в первом алгоритме и на цикле во втором, хотя бы на одной дуге поток становится равным нулю. Таким образом, число цепей, получаемых в первом алгоритме, и циклов, уничтожаемых во втором, можно оценить сверху величиной р. Отсюда следует, что 
и 
и оба алгоритма имеют полиноминальную оценку трудоемкости относительно числа вершин и дуг сети.
Приведем теперь более точную оценку количества цепей, получившихся при работе первого алгоритма.
Пусть в сети 
вершин, 
дуг, 
поставщиков и 
потребителей.
Теорема. Число цепей не превосходит 
Доказательство. Заметим, что после окончания работы алгоритма потоки на всех дугах сети равны нулю. Каждой внутренней вершине сопоставим цепь 
после пересчета потоков, на которой 
становится равной нулю. Но, так как вершина 
становится равной нулю. Но, так как вершина внутренняя, то , а значит
и 
Следовательно, после пересчета потоков цепи для любой внутренней вершины поток станет равен нулю по крайней мере на двух дугах. После пересчета потоков на других цепях поток становится равным нулю, хотя бы одной дуге. Следовательно, общее количество цепей можно оценить величиной 
где 
– число внутренних вершин. Теперь из равенства 
следует справедливость утверждения теоремы.
Следствие. Если исходная сеть является деревом, то число цепей не превосходит 
4. Заключение
При использовании приведенных алгоритмов для привязки поставщиков к потребителям на рынке БРИКС алгоритмов после решения сетевых транспортных задач следует преобразовать полученный оптимальный план к виду, необходимому для работы алгоритмов привязки. Здесь мы отходим от принятых способов хранения оптимального плана в целях единообразия обработки решений транспортных задач с ограничениями пропускной способности и без ограничений. Отметим, что алгоритм удаления циклов следует применять только к решению задачи с ограничениями и только в том случае, когда в исходной сети есть ориентированные циклы из дуг нулевой стоимости.
Отметим, что для задачи без ограничений достаточно запомнить лишь начало цепи, конец цепи и поток по ней, так как маршрут перевозки однозначно восстанавливается по этим данным и по дереву оптимального плана, тогда как для задачи с ограничениями необходимо запоминать весь маршрут перевозки; здесь может быть, например, несколько различных цепей с одинаковыми началами и концами.
Описанный алгоритм привязки осуществляет закрепление поставщиков за потребителями на рынке БРИКС без учета каких-либо требований к этому закреплению. В некоторых случаях такое закрепление не является удовлетворительным.
1. Lipatova N.G., Chernysh A.Ya. Primenenie matematicheskih metodov pri provedenii dissertacionnyh issledovaniy. − Moskva: Rossiyskaya tamozhennaya akademiya, 2011. - 514 s.
2. Anisimov V.G., Anisimov E.G. Metod resheniya odnogo klassa zadach celochislennogo programmirovaniya // Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki. − 1989. − T. 29. − № 10. − S. 1586-1590.
3. Alekseev O.G. Modeli raspredeleniya sredstv porazheniya v dinamike boya / O.G. Alekseev [i dr.]. - Leningrad: Ministerstvo oborony SSSR. − 1989. − 109 s.
4. Anisimov V.G., Anisimov E.G. Algoritm optimal'nogo raspredeleniya diskretnyh neodnorodnyh resursov na seti // Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki. − 1997. − T. 37. − № 2. − S. 54-60.
5. Anisimov V.G., Anisimov E.G. Optimizacionnaya model' raspredeleniya vozobnovlyaemyh resursov pri upravlenii ekonomicheskimi sistemami // Vestnik Rossiyskoy tamozhennoy akademii. − 2007. − № 1. − S. 49-54.
6. Gubenko A.V., Sazykin A.M. Teoreticheskie osnovy sozdaniya sistem podderzhki prinyatiya resheniy v interesah kompleksnoy transportnoy bezopasnosti // Izvestiya Rossiyskoy akademii raketnyh i artilleriyskih nauk. − 2015. − № 3 (88). − S. 10-15.
7. Alekseev, A.O. Primenenie dvoystvennosti dlya povysheniya effektivnosti metoda vetvey i granic pri reshenii zadachi o rance / A.O. Alekseev, O.G. Alekseev [i dr.] // Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki. − 1985. − T. 25. − № 11. − S. 1666-1673.
8. Anisimov V.G. The model and the planning method of volume and variety assessment of innovative products in an industrial enterprise / V.G. Anisimov [i dr.] // Journal of Physics: Conference Series, 2017, 803(1), 012006. DOI: https://doi.org/10.1088/1742-6596/803/1/012006.
9. Anisimov E.G. Metodicheskie polozheniya matematicheskogo modelirovaniya zadach adaptivnogo raspredeleniya diskretnyh resursov pri upravlenii voyskami i oruzhiem v rezhime real'nogo vremeni / E.G. Anisimov [i dr.] // Izvestiya Rossiyskoy akademii raketnyh i artilleriyskih nauk. − 2016. − № 1 (91). − S. 32-37.
10. Zotova E. A model for setting up development programs for logistics systems in the electric power industry to achieve electric power security / E. Zotova [i dr.] // V sbornike: E3S Web of Conferences. Ser. "Ural Environmental Science Forum "Sustainable Development of Industrial Region", UESF 2021" 2021, s. 2027. DOI:https://doi.org/10.1051/e3sconf/202125802027.
11. Chernysh A.Ya., Mel'nik D.A. Model' podderzhki prinyatiya resheniy pri formirovanii programm innovacionnogo razvitiya predpriyatiy elektrotehnicheskoy otrasli mashinostroeniya // Vestnik Rossiyskogo ekonomicheskogo universiteta imeni G.V. Plehanova. − 2021. − T. 18. − № 4 (118). − S. 140-151.
12. Il'in I.V. Matematicheskie metody i instrumental'nye sredstva ocenivaniya effektivnosti investiciy v innovacionnye proekty / I.V. Il'in [i dr.]. − Sankt-Peterburg, 2018. − 289 s.
13. Anisimov V., Shaban A., Anisimov E., Saurenko T., Yavorsky V. Optimization of perishable goods delivery in supply chains with random demand // V sbornike: E3S Web of Conferences. Ser. "Ural Environmental Science Forum "Sustainable Development of Industrial Region", UESF 2021" 2021. S. 2017. DOI:https://doi.org/10.1051/e3sconf/202125802017.
14. Saurenko T.N. Model' sravnitel'noy ocenki morskih torgovyh portov v mezhdunarodnoy transportnoy infrastrukture / T. N. Saurenko [i dr.] // Uchenye zapiski Krymskogo federal'nogo universiteta imeni V.I. Vernadskogo. Ekonomika i upravlenie. − 2020. − T. 6. − № 1. − S. 153-160.
15. Rodionova E.S. Model' i metod kalendarnogo planirovaniya logisticheskih processov pererabatyvayuschih predpriyatiy agropromyshlennogo kompleksa / E.S. Rodionova [i dr.] // Upravlencheskoe konsul'tirovanie. − 2018. − № 11 (119). − S. 109-118.
16. Pak A.Yu., Chupina Zh.S., Chupin A.L., Fattyahetdinova V.R., Shobekova Sh.U. Metodicheskiy podhod k vyboru kompleksa sredstv dlya avtomatizacii operaciy transportnogo kontrolya v avtomobil'nyh punktah propuska cherez tamozhennuyu granicu EAES // Ekonomicheskie strategii EAES: problemy i innovacii. Sbornik materialov III Vserossiyskoy nauchno-prakticheskoy konferencii. − 2020. − S. 151-163.
17. Vedernikov Yu.V. Modeli i algoritmy intellektualizacii avtomatizirovannogo upravleniya diversifikaciey deyatel'nosti promyshlennogo predpriyatiya // Voprosy oboronnoy tehniki. Seriya 16: Tehnicheskie sredstva protivodeystviya terrorizmu. − 2014. − № 5-6 (71-72). − S. 61-72.
18. Tebekin A.V. Metodicheskiy podhod k modelirovaniyu processov formirovaniya planov innovacionnogo razvitiya predpriyatiy // Zhurnal issledovaniy po upravleniyu. − 2019. − T. 5. − № 1. − S. 65-72.
19. Anisimov V.G. Methodological approaches to accounting uncertainty when planning lgistic business processes / V.G. Anisimov, E.G Anisimov [i dr.] // V sbornike: Atlantis Highlights in Computer Sciences. Proceedings of the International Conference on Digital Technologies in Logistics and Infrastructure (ICDTLI 2019). 2019. S. 246-249.
20. Barabanov V.V. Metod optimizacii resheniy po organizacii logisticheskih processov // V sbornike: Logistika: sovremennye tendencii razvitiya: Materialy XVII Mezhdunarodnoy nauchno-prakticheskoy konferencii. − 2018. − S. 52-56.
21. Saurenko T.N.. Formalization of planning procedureproduction process of the complex industrial patterns of vertical integration / T.N. Saurenko, M.R Gapov [i dr.] // Ekonomicheskie strategii EAES: problemy i innovacii: Sbornik materialov Vserossiyskoy nauchno-prakticheskoy konferencii.- Moskva: Rossiyskiy universitet druzhby narodov, 2018. S. 154-161.
22. Bosov D.B. Setevye modeli i metody resursno-vremennoy optimizacii v upravlenii innovacionnymi proektami. − Moskva, 2006. − 117 s.
23. Gapov M.R., Saurenko T.N. Model' podderzhki prinyatiya resheniy pri formirovanii tovarnoy strategii i proizvodstvennoy programmy predpriyatiya // Vestnik Rossiyskogo universiteta druzhby narodov. Seriya: Ekonomika. − 2016. − № 2. − S. 62-73.
24. Chernysh A.Ya., Mel'nik D.A. Model' podderzhki prinyatiya resheniy pri formirovanii programm innovacionnogo razvitiya predpriyatiy elektrotehnicheskoy otrasli mashinostroeniya // Vestnik Rossiyskogo ekonomicheskogo universiteta imeni G.V. Plehanova. − 2021. − T. 18. − № 4 (118). − S. 140-151.
25. Anisimov V., Anisimov E., Sonkin M. A resource-and-time method to optimize the performance of several interrelated operations // International Journal of Applied Engineering Research. 2015. T. 10. № 17. S. 38127-38132.
26. Nikolaev G.A., Nichipor V.I., Osipenkov M.N. Tipovye modeli i algoritmy zadach podderzhki prinyatiya resheniy pri upravlenii obespechivayuschim komponentom voennoy organizacii gosudarstva. − Moskva: Voennaya akademiya General'nogo shtaba Vooruzhennyh sil Rossiyskoy Federacii, 2019. − 141 s.
27. Tebekin A.V., Anisimov V.G., Anisimov E.G. Nelineynaya model' optimizacii parametricheskih ryadov v sistemah upravleniya // Vestnik Rossiyskoy tamozhennoy akademii. − 2015. − № 3. − S. 115-122.
28. Kezhaev V.A. Obosnovanie resheniy v zadachah celeraspredeleniya s ispol'zovaniem innovacionnyh tehnologiy diskretnogo programmirovaniya / V.A. Kezhaev [i dr.] // Izvestiya Rossiyskoy akademii raketnyh i artilleriyskih nauk. 2012. № 2 (72). − S. 97-103.
29. Chernysh A.Ya., Chechevatov A.V. Optimizacionnye modeli i metody v upravlenii innovacionnymi processami. − Moskva, 2006. − 96 s.
30. Chupin A.L., Chupina Z.S., Morozova N.N., Vorotyntseva T.M., Levinskay E.V. Prediction model of the efficacy and the implementation time of transportation intelligent systems IOP Conference Series: Materials Science and Engineering. II International Scientific Practical Conference "Breakthrough Technologies and Communications in Industry and City", BTCI 2019. 2020. S. 012006.
31. Tebekin A.V. Logistika. / A. V. Tebekin. − Moskva: Dashkov i K°, 2014. − 354 s.
