Подход к нахождению максимального двухпродуктового потока в нечеткой транспортной сети

УДК 519.178 DOI 10.23683/2311-3103-2018-4-111-120

Е.М. Герасименко

ПОДХОД К НАХОЖДЕНИЮ МАКСИМАЛЬНОГО ДВУХПРОДУКТОВОГО ПОТОКА В НЕЧЕТКОЙ ТРАНСПОРТНОЙ СЕТИ*

Данная статья посвящена решению задачи нахождения максимального двухпродукто-вого потока в нечеткой транспортной сети. Задача определения объема многопродуктового потока, проходящего по транспортной сети, является актуальной задачей при транспортном планировании и оптимизации перевозок. Данная статья описывает разновидность такой задачи - в частности, проблему определения потока двух продуктов в транспортной сети. Основной сложностью данной задачи является тот факт, что теорема о максимальном потоке и минимальном разрезе не выполняется для такого рода задач, однако, она выполняется для нахождения протока двух продуктов в неориентированной транспортной сети. Особенностью данной задачи является возможность первого потока блокировать поток второго продукта таким образом, что мы можем не получить оптимальный результат. Центральной частью данной задачи являются параметры транспортной сети, представленные в нечеткой форме, такие как пропускные способности ее дуг. Разработанный метод использует модифицированный алгоритм поиска увеличивающего пути, позволяющий учитывать нечеткие параметры сети, приписанные дугам графа. Описанный метод может применяться при планировании перевозок двух типов товаров, каждый из которых имеет свой источник и сток, например, в случае пассажирских и грузовых поездов или легковых и грузовых машин. Рассмотрен метод оперирования нечеткими числами, не приводящий к «размытию» границ результирующего числа и позволяющий оперировать нечеткими границами на последних итерациях, в то время как на остальных предшествующих итерациях производятся вычислениями только с центрами нечетких чисел. Рассмотрен численный пример, который иллюстрирует работу предложенного алгоритма.

Двухпродуктовый поток; нечеткий граф; нечёткий двойной путь.

E.M. Gerasimenko

APPROACH TO THE MAXIMUM TWO-COMMODITY FLOW DETERMINING IN A FUZZY NETWORK

This article is devoted to solving the problem of the maximum two-commodity flow finding in a fuzzy transportation network. The task of determining the volume of a multi-commodity flow passing through the transportation network is an important task in transport planning and optimization of traffic. This article describes a variation of this task, in particular, the problem of determining the flow of two commodities in a transportation network. The main difficulty of this task is the fact that the max-flow min- cut theorem is not fulfilled for such tasks, however, it is performed to find the flow of two commodities in the undirected transportation network. A feature of this task is the ability of the first flow to block the flow of the second product in such a way that we may not get the optimal result. The central part of this task is the parameters of the transportation network, presented in a fuzzy form, such as the arc capacities of its arcs. The developed method uses a modified search path method for augmented paths, allowing to take into account fuzzy network parameters assigned to the arcs of the graph. The described method can be applied when planning the transportation of two types of goods, each of which has its own source and sink, for example, in the case of passenger and freight trains or cars and trucks. The method of operating with fuzzy numbers is considered, which does not lead to a "blurring" of the boundaries of the resulting number and allows operating with fuzzy boundaries at the last iterations, while at the previous preceding iterations they are performed with calculations only with centers of fuzzy numbers. A numerical example is considered which illustrates the operation of the proposed algorithm.

Two-commodity flow; fuzzy graph; fuzzy double path..

*

Работа выполнена при поддержке гранта РФФИ (проект № 16-01-00090 a).

Введение. Задача нахождения однопродуктового потока, широко освещённая в литературе в ряде статей, имеет важное практическое применение при планировании перевозок, управлении траффиком, определении оптимальных путей транспортировки и нахождении потока максимального объема. Кроме того, при рассмотрении транспортных систем часто возникает ситуация нескольких различных товаров (грузов), одновременно проходящих через транспортную сеть, но имеющих различные источники и стоки [1-2]. Данная ситуация возникает при прохождении различных типов поездов по транспортной сети (пассажирских и грузовых), легковых автомобилей различного типа (грузовых и легковых), перевозке скоропортящегося груза или, наоборот, груза, который может увеличивать свое значение при перевозке.

Следовательно, мы приходим к двухпродуктовому потоку в транспортной сети, задача определения которого является разновидностью задачи нахождения многопродуктового потока, когда три или более видов груза одновременно проходят по дугам транспортной сети [2-3]. Основной сложностью данной задачи является тот факт, что теорема о максимальном потоке и минимальном разрезе не выполняется для такого рода задач [4]. Однако, упомянутая теорема справедлива для потоков двух продуктов в неориентированном графе [1]. Особенностью данной задачи является возможность первого потока блокировать поток второго продукта таким образом, что мы можем не получить оптимальный результат. Т. Ху разработал алгоритм для решения данной задачи и получил оптимальный результат [1].

Несмотря на обширные исследования в области потоковых задач существует пробел в исследованиях в области нечеткости, присущей транспортным сетям, хотя данная характеристика транспортных сетей является основообразующей. Традиционно, нечеткие транспортные сети включают несколько видов неопределенности, связанной с нечеткостью при измерении параметров транспортных сетей, изменениями в погодных условиях, дорожных ситуациях. Информация относительно параметров сетей может отсутствовать в силу уникальности постановок задач, следовательно, предлагается исследовать эти задачи в условиях неопределенности и переходить к нечетким графам для решения такого рода задач [5-8].

Обобщая вышесказанное, мы приходим к постановке задачи нахождения максимального двухпродуктового потока в нечёткой транспортной сети.

Обзор источников. Задача нахождения двухпродуктового потока в транспортной сети является разновидностью задачи нахождения многопродуктового потока, когда различные типы товаров перевозятся по дугам транспортной сети, причем каждый из них имеет свой источник и сток [9-13]. Основной сложностью данной задачи является тот факт, что теорема о максимальном потоке и минимальном разрезе не выполняется для такого рода задач [4]. Однако, упомянутая теорема справедлива для потоков двух продуктов в неориентированном графе [1].

Задача нахождения максимального двухпродуктового потока была рассмотрена и решена автором Т. Ху [1], который предложил алгоритм поиска увеличивающего пути и концепцию алгоритма двойного пути для таких задач.

А. Итаи [2] модифицировал алгоритм в аспекте увеличения максимального потока итерационно и использовал более быстрые алгоритмы для нахождения потока, которые привели к итоговой временной сложности 0( ^ 2| \Е\). Похожие результаты были получены многими авторами. М. Коста [4] исследовал и обобщил задачи нахождения целочисленного многопродуктового потока. В 2008 г. А. Седе-но-Нода и др. предложили алгоритм, упрощающий поиск двухпродуктового потока изменением переменных и преобразованием задачи к задаче поиска однопро-дуктового потока [14].

Актуальной задачей при анализе транспортных сетей является задача нахождения максимального потока двух продуктов, которая состоит в нахождении максимальных значений потоков двух видов в транспортной сети [15-16]. Ее особенность состоит в возможности первого потока блокировать второй поток таким образом, что мы не получим оптимальное значение.

Постановка задачи. Особенностью рассматриваемой задачи нахождения двухпродуктового потока является тот факт, что вычисляемый поток может блокировать поток второго продукта. Следовательно, необходимо найти двойной путь и перераспределить поток таким образом, чтобы избежать блокирования. Если такого пути не существует, соответствующий максимальный поток найден [17].

Разработанный метод основан на следующем правиле.

Правило 1 передачи потока по двойному пути [1].

Определим потоки обратного и прямого пути в зависимости от значений потоков: с, = mine,1, . с,1, > 0 . с,' = min с,1, . с,1, > 0, где - поток по прямому пу-

J 1 j 1 j j 1 j i J

ти, ¿,1 - поток по обратному пути.

Таким образом, поток вдоль двойного пути определяется как минимальное значение из потоков по прямому и обратному путям: ch/ = min) •

Пропускная способность двойного пути определяется как минимальное значение из остаточных пропускных способностей прямого и обратного путей:

übf = vcari(üb,üf).

Так как двойной путь состоит из двух путей передаем г =тт

единиц потока каждого вида по двойному пути следующим образом: передаем г единиц потока первого вида от источника к стоку по обратному пути, затем передаем г единиц потока первого вида от источника к стоку вдоль прямого пути.

Затем передаем г единиц потока второго типа по двойному пути следующим образом: передаем г единиц потока второго типа от истопника к стоку по обратному пути, затем передаем г единиц потока товара второго вида от источника к стоку по прямому пути.

Представим постановку задачи нахождения максимального потока двух продуктов в неориентированном двухпродуктовом графе в условиях присутствующей в сети неопределённости, представленную моделью (1)-(3).

2

Maximize ^v

X X Zki

Xj-ЕГ

v,x,=s, -v,xt=t,

Ö, X,. Ф S, t.

2

<й,,У

В модели (1)-(3) йу - нечеткие верхние границы потоков дуг вида (х,. ). V - максимальное значение потока, ^ - поток 5-ого вида по дуге ('х , х.).

s=\

Шаг 1. Ищем максимальный поток первого товара, полагая поток второго вида товара равным нулю, от искусственного источника х] к стоку искусственному х] в соответствие с поиском в ширину.

Шаг 2. Находим максимальный поток второго вида, полагая пропускные способности ребер как й\ = йц . Ищем увеличивающий путь из искусст-

венного источника к искусственному стоку '* в построенном нечетком остаточном графе.

Шаг 3. Находим двойной путь из 25 в 2'. В двойном пути присутствуют два вида путей: прямой и обратный. Обратный путь состоит из ребер, содержащих поток первого типа, идущий в противоположном направлении (отрицательные значения) и ненасыщенные ребра.

Остаточная пропускная способность обратного вида определяется как: йь = й, + с ', - > 0. Прямой путь - это путь с ненулевыми положительными значениями потока первого типа или отрицательными значениями потока второго типа. Остаточная пропускная способность прямого пути: й^ = й1у + - ^ > 0.

3.1. Если весь двойной путь или одна из его составляющих не существуют, полученный поток г = тах(<^ ^ + ^ ^) является максимальным потоком в исходном графе, конец.

3.2. Если путь найден, передаем значение г =тт(<^,0.5м4/) потока первого

типа вдоль двойного пути, где ¿1 и йЬ! вычисляются согласно правилу 2.

Шаг 4. Увеличиваем количество потока второго типа на 2г, передавая значение г = тт(<^,0.5м4/) потока второго типа по двойному пути, где и ЛЬ! вычисляются по правилу 2.

Шаг 5. Обновляем значения потоков в графе Ор(£) и переходим к шагу 2.

Численный пример. Представим численный, иллюстрирующий работу алгоритма нахождения нечеткого максимального двухпродуктового потока. Задача заключается в поиске максимального суммарного потока двух видов перевозимого груза из источника в сток в графе, представленном на рис. 1.

©-:->©

Рис. 1. Исходная транспортная сеть а

Шаг 1. Ищем увеличивающие пути, полагая поток второго вида груза равным нулю, следовательно, значение максимального потока груза первого вида будет эквивалентно потоку, представленному на рис. 2. Следующие пути х\ —> х5 —> х) с 10 единицами потока, х' —> х3 —> х6 —> х5 —> х) с 20 единицами потока,

хз Х6 х? х9 х! с 18 единицами потока, х] -> х3 -> х6 -> х9 -> х] с 7 единицами потока найдены и определяют найденный суммарный максимальный поток, равный 55 единицам.

Рис. 2. Граф с максимальным потоком первого типа

Шаг 2. Находим максимальное значение потока груза второго типа, полагая вычисленный поток первого типа й\ = /7(; - | + таким образом, чтобы суммарные ограничения на пропускную способность выполнялись. Таким образом, мы находим следующие пути: х] —> х8 —> х(2 и передаем 8 единиц потока по нему, х] —> х7 —> х] и передаем 20 единиц потока по нему, х] —> х7 —> х9 —> х(2 с 4 единицами потока. Соответствующее значение потока показано на рис. 3.

г|\!21 © '©

Рис. 3. Граф с максимальным потоком товара первого вида и максимальным значением потока второго вида

Шаг 3. Найдем двойной путь из 21 в 2', если он существует. Двойной путь должен содержать два пути: прямой и обратный.

Обратный путь имеет следующую цепочку: x] ^ x1 ^ x6 ^ xg ^ x2t . Поток первого вида протекает в противоположном направлении, а остальные ребра не насыщены в дуге (х7, х6). Поток этого пути может быть вычислен по правилу 1, и

он равен ¿j1 = mine,' , =18 единицам. Результирующая пропускная способность остаточного пути вычисляется как минимальная из остаточных пропускных способностей обратного пути, т.е. йь = min(18,36,76,10) = 10 единиц.

Затем мы получаем прямой путь, который имеет следующее распределение потока: х] —> х7 х,} x2t . Поток по этому пути определяется по правилу 1, и он

равен £,xf = mini,1, =18 units. Пропускная способность остаточного пути определяется как минимальная из остаточных пропускных способностей прямого пути, т.е. йу =min(18,36,10) = 10 единиц.

Следовательно, 4/ = min (18,18) = 18 единиц, й4/=min(10, 10) = 10 единиц, г = min(18,5) = 5 единиц.

Шаг 3.2. Передаем 5 единиц потока груза первого вида по двойному пути, как показано на рис. 4.

© " '©

Рис. 4. Граф после отправления 5 единиц потока товара первого вида по

двойному пути

Шаг 4. Увеличиваем значение потока товара второго вида: отправляем 5 единиц потока товара второго вида по двойному пути, как представлено на рис. 5.

Шаг 2. Поток товара второго вида не может быть увеличен, и увеличивающих путей не существует. Следовательно, максимальный поток получен, и он равен 55+42 = 97 единицам потока.

Предложенный метод определяет максимальный нечеткий поток в двухпродук-товом графе, следовательно, следующим шагом является нахождение результирующего нечеткого треугольного числа, учитывая степени размытия границ числа [18-19].

Применим метод, описанный в [20-21]. Суть данного метода заключается в том, что у нас нет необходимости оперировать границами отклонений нечетких чисел на первом шаге осуществления вычислений: достаточно оперировать цен-

тральными значениями треугольных чисел, «размывая» их границы на последнем шаге. Преимуществом данного подхода является сохранение результирующим значением потока своего значения без сильного размытия границ числа.

[|\12] © * * >©

Рис. 5. Граф после отправления 5 единиц потока товара второго вида

по двойному пути

Таким образом, рис. 6 показывает границы отклонений базовых нечётких пропускных способностей, заданных экспертами.

Результат операции расположен между двумя соседними базовыми значениями пропускных способностей: 77 с левой границей отклонения /,' = 20, правой границей отклонения - = 21 и 138 с левой границей отклонения /,' = 28, правой границей - /'' =41. В итоге, получаем конечные границы отклонений: И 22 , И 27.

В итоге, найденный максимальный суммарный поток в двухпродуктовом нечётком графе может быть представлен нечетким треугольным числом (75, 97, 124) единиц.

Ж,

10 182228 34 49 57 77 98 110 138 179 220 269

Рис. б. Функции принадлежности базовых значений пропускных способностей

ребер сети О

Заключение. Статья иллюстрирует подход к нахождению максимального потока двух продуктов в нечеткой транспортной сети. Данный метод оперирует нечеткими пропускными способностями дуг сети, заданными для каждого из идущих по ним потоков каждого вида из выделенных источников в выделенные стоки. Метод является модификацией алгоритма Ху поиска увеличивающего пути с учетом нечёткости, присущей транспортным сетям. В основе методе - правило передачи потока по двойному пути, а также правила оперирования нечеткими зна-

чениями пропускных способностей, которое обеспечивает более реалистичные решения, так как нет необходимости осуществлять рутинные арифметические операции с нечёткими числами, которые в конечном итоге приводят к сильному размытию границ чисел. Предложенный подход имеет важное практическое применение при транспортном планировании и оптимизации значений потоков на реальных сетях дорог в задачах, где необходимо учитывать товары (типы транспортных средств) двух видов, например, пассажирские и грузовые поезда или легковые автомобили и грузовики. В будущем планируется разработка алгоритмов нахождения минимального двух- и многопродуктового потока в нечётких условиях в статических и динамических транспортных сетях.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Hu T. Multi-commodity network flows // Oper. Res. - 1963. - No. 11. - P. 344-360.

2. Itai A. Two-commodity flow // Journal of the Association for Computing Machinery. - 1978.

- Vol. 25, No. 4. - P. 596-611.

3. Rajagopalan S. Two-commodity flow // Oper. Res. Lett. - 1994. - Vol. 15. - P. 151-156.

4. Costa M., LetocartL., Roupin F. Minimal multicat and maximal integer multiflow: A survey // Eur. J. Oper. Res. - 2005. - Vol. 162 (1). - P. 55-69.

5. Kureichik V., Gerasimenko E. Approach to the Minimum Cost Flow Determining in Fuzzy Terms Considering Vitality Degree. In Silhavy R., Senkerik R., Kominkova Oplatkova Z., Prokopova Z., Silhavy P. (eds) // Artificial Intelligence Trends in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing. - Springer, Cham, 2017. - Vol. 573.

- P. 200-209.

6. Bozhenyuk A., Gerasimenko E., Kacprzyk J., Rozenberg I. Flows in networks under fuzzy conditions // Studies in Fuzziness and Soft Computing. - Heidelberg: Springer-Verlag, 2017.

- Vol. 346. - P. 269-291.

7. Боженюк А.В., Герасименко Е.М., Розенберг И.Н. Разработка метода определения потока минимальной стоимости в транспортной сети с нечеткими пропускными способностями и стоимостями с помощью метода потенциалов // Известия ЮФУ. Технические науки. - 2015. - № 6 (167). - С. 138-149.

8. Bozhenyuk A, Gerasimenko E., Rozenberg I. Determining the Minimum Cost Flow in Fuzzy Dynamic Network with GIS «ObjectLand» // Proceedings of 9th International Conference on Application of Information and Communication Technologies, AICT 2015. - Rostov on Don, 2015. - P. 294-298.

9. Kolman P., Scheideler C. Improved bounds for the unsplittable flow problem // J. Algor.

- 2006. - Vol. 61 (1). - P. 20-44.

10. Barnhart C., Krishnan N., Vance P.H. Multicommodity Flow Problems. In Floudas C., Pardalos P. (eds) // Encyclopedia of Optimization. Springer, Boston, MA, 2008.

11. Barnhart C., Hane C.A., Vance P.H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems // Oper Res. - 2000. - Vol. 48 (2).

- P. 318-326.

12. Karakostas G. Faster approximation schemes for fractional multicommodity flow problems // Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms.

- 2002. - P. 166-173.

13. McBride R.D., Carrizosa E. Conde E. Munoz-Marquez M. Advances in solving the multi-commodity flow problem // Interfaces. - 1998. - Vol. 28 (2). - P. 32-41.

14. Sedeño-Noda A., González-Martín C., Alonso-Rodríguez S. A new strategy for the undirected two-commodity maximum flow problem // Computational Optimization and Applications.

- 2010. - Vol. 47 (2). - P. 289-305.

15. Kureichik V., Gerasimenko E. Multi-Commodity Maximum Flow Determining in a Fuzzy Graph with Vitality Degrees // Proceedings of 11th International Conference on Application of Information and Communication Technologies, AICT 2017, Moscow, Russia. - P. 347-351.

16. Bozhenyuk A., Gerasimenko E., Rozenberg I. Method of Maximum Two-Commodity Flow Search in a Fuzzy Temporal Graph // Proceedings of the 10th Conference of the European Society for Fuzzy Logic of and Technology EUSFLAT-2017, September 11-15, 2017, Warsaw, Poland. - P. 249-260.

17. Cormen T.H, Leiserson C.E, Rivest R.L., Stein C. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill, 2009.

18. Ganesan K., Veeramani P. Fuzzy Linear Programs with Trapezoidal Fuzzy Numbers // Ann Oper Res. - 2006. - P. 305-315.

19. Kumar A., Kaur J., Singh P. Fuzzy Optimal Solution of Fully Fuzzy Linear Programming Problems with Inequality Constraints // International Journal of Mathematical and Computer Sciences 6:1, 2010. - P. 37-41.

20. Боженюк А. Герасименко Е., Розенберг И. Алгоритм нахождения нечеткого потока в транспортной сети с нечеткими стоимостями и пропускными способностями // Известия ЮФУ. Технические науки. - 2012. - № 5 (130). - C. 118-122.

21. Герасименко Е. Нахождение потока минимальной стоимости в транспортной сети методом ранжирования математического ожидания нечетких функций стоимостей // Известия ЮФУ. Технические науки. - 2012. - № 4 (129). - C. 247-251.

REFERENCES

1. Hu T. Multi-commodity network flows, Oper. Res., 1963, No. 11, pp. 344-360.

2. Itai A. Two-commodity flow, Journal of the Association for Computing Machinery, 1978, Vol. 25, No. 4, pp. 596-611.

3. Rajagopalan S. Two-commodity flow, Oper. Res. Lett., 1994, Vol. 15, pp. 151-156.

4. Costa M., Letocart L., Roupin F. Minimal multicat and maximal integer multiflow: A survey, Eur. J. Oper. Res, 2005, Vol. 162 (1), pp. 55-69.

5. Kureichik V., Gerasimenko E. Approach to the Minimum Cost Flow Determining in Fuzzy Terms Considering Vitality Degree. In Silhavy R., Senkerik R., Kominkova Oplatkova Z., Prokopova Z., Silhavy P. (eds), Artificial Intelligence Trends in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing. Springer, Cham, 2017, Vol. 573, pp. 200-209.

6. Bozhenyuk A., Gerasimenko E., Kacprzyk J., Rozenberg I. Flows in networks under fuzzy conditions, Studies in Fuzziness and Soft Computing. Heidelberg: Springer-Verlag, 2017, Vol. 346, pp. 269-291.

7. Bozhenyuk A.V., Gerasimenko E.M., Rozenberg I.N. Razrabotka metoda opredeleniya potoka minimal'noy stoimosti v transportnoy seti s nechetkimi propusknymi sposobnostyami i stoimostyami s pomoshch'yu metoda potentsialov [Development of the minimum cost flow method with fuzzy arc capacities and costs by the potential method], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6 (167), pp. 138-149.

8. Bozhenyuk A, Gerasimenko E., Rozenberg I. Determining the Minimum Cost Flow in Fuzzy Dynamic Network with GIS «ObjectLand», Proceedings of 9th International Conference on Application of Information and Communication Technologies, AICT 2015. Rostov on Don, 2015, pp. 294-298.

9. Kolman P., Scheideler C. Improved bounds for the unsplittable flow problem, J. Algor., 2006, Vol. 61 (1), pp. 20-44.

10. Barnhart C., Krishnan N., Vance P.H. Multicommodity Flow Problems. In Floudas C., Pardalos P. (eds), Encyclopedia of Optimization. Springer, Boston, MA, 2008.

11. Barnhart C., Hane C.A., Vance P.H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems, Oper Res., 2000, Vol. 48 (2), pp. 318-326.

12. Karakostas G. Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, 2002, pp. 166-173.

13. McBride R.D., Carrizosa E. Conde E. Munoz-Marquez M. Advances in solving the multi-commodity flow problem, Interfaces, 1998, Vol. 28 (2), pp. 32-41.

14. Sedeño-Noda A., González-Martín C., Alonso-Rodríguez S. A new strategy for the undirected two-commodity maximum flow problem, Computational Optimization and Applications, 2010, Vol. 47 (2), pp. 289-305.

15. Kureichik V., Gerasimenko E. Multi-Commodity Maximum Flow Determining in a Fuzzy Graph with Vitality Degrees, Proceedings of 11th International Conference on Application of Information and Communication Technologies, AICT 2017, Moscow, Russia, pp. 347-351.

16. Bozhenyuk A., Gerasimenko E., Rozenberg I. Method of Maximum Two-Commodity Flow Search in a Fuzzy Temporal Graph, Proceedings of the 10th Conference of the European Society for Fuzzy Logic of and Technology EUSFLAT-2017, September 11-15, 2017, Warsaw, Poland, pp. 249-260.

17. Cormen T.H, Leiserson C.E, Rivest R.L., Stein C. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill, 2009.

18. Ganesan K., Veeramani P. Fuzzy Linear Programs with Trapezoidal Fuzzy Numbers, Ann Oper Res, 2006, pp. 305-315.

19. Kumar A., Kaur J., Singh P. Fuzzy Optimal Solution of Fully Fuzzy Linear Programming Problems with Inequality Constraints, International Journal of Mathematical and Computer Sciences 6:1, 2010, pp. 37-41.

20. Bozhenyuk A. Gerasimenko E., Rozenberg I. Algoritm nakhozhdeniya nechetkogo potoka v transportnoy seti s nechetkimi stoimostyami i propusknymi sposobnostyami [Algoritm nahozhdeniya nechetkogo potoka v transportnoy seti s nechetkimi stoimostyami i propusknyimi sposobnostyami], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 5 (130), pp. 118-122.

21. Gerasimenko E. Nakhozhdenie potoka minimal'noy stoimosti v transportnoy seti metodom ranzhirovaniya matematicheskogo ozhidaniya nechetkikh funktsiy stoimostey [Minimum cost flow finding in the network by the method of expectation ranking of fuzzy cost functions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 4 (129), pp. 247-251.

Статью рекомендовал к опубликованию д.т.н., профессор А.В. Боженюк.

Герасименко Евгения Михайловна - Южный федеральный университет; e-mail: egerasimenko@sfedu.ru; 347928, Таганрог, пер. Некрасовский, 44; тел.: 88634371621; кафедра систем автоматизированного проектирования; к.т.н.; доцент.

Gerasimenko Evgeniya Michailovna - Southern Federal University; e-mail: egerasimenko@sfedu.ru; 44, Nekrasovskiy, Taganrog, 347928, Russia; phone: +78634371621; the department of CAD; cand. of eng. sc.; associate professor.