Статья

Название статьи МЕТОД ПОТЕНЦИАЛОВ ДЛЯ ОПРЕДЕЛЕНИЯ ЗАДАННОГО ПОТОКА МИНИМАЛЬНОЙ СТОИМОСТИ В НЕЧЕТКОМ ДИНАМИЧЕСКОМ ГРАФЕ
Автор Е.М. Герасименко
Рубрика РАЗДЕЛ I. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ
Месяц, год 04, 2014
Индекс УДК 681.327
DOI
Аннотация Описывается метод нахождения потока минимальной стоимости в нечетком динамическом графе. Для вычисления потока минимальной стоимости будем применять алгоритм, основанный на введении потенциалов для каждой из вершин нечеткого графа. Данный алгоритм позволяет избежать необходимости оперирования отрицательными стоимостями, т.е. работает с так называемыми «приведенными стоимостями». Данная модификация приводит к увеличению быстродействия алгоритма. Значения потенциалов вычисляются согласно путям минимальной стоимости от начальной вершины к остальным вершинам графа. При этом нет необходимости просматривать все вершины графа, так как критерием окончания алгоритма является приписывание постоянной пометки конечной вершины. Использование потенциалов вершин ведет к необходимости оперирования «приведенными стоимостями», полученными на основе исходных стоимостей и вычисления потенциалов вершин. Описаны правила построения «развернутого во времени» графа, соответствующего исходному, а также правила построения нечеткой остаточной сети, оперирующей приведенными стоимостями. Учитывается возможность параметров графа меняться во времени.

Скачать в PDF

Ключевые слова Нечеткий динамический граф; поток минимальной стоимости; потенциалы вершин; развернутый во времени граф.
Библиографический список 1. Bozhenyuk Alexandr and Gerasimenko Evgeniya. Flows Finding in Networks in Fuzzy Conditions // Cengiz Kahraman, Basar Oztaysi (eds.), Supply Chain Management Under Fuzziness, Studies in Fuzziness and Soft Computing, Springer-Verlag Berlin Heidelberg. – 2014. – Vol. 313. – P. 269-291.
2. Боженюк А.В., Шадрина В.В. Использование нечеткого логического вывода для управления технологическим процессом на компрессорной станции // Обозрение прикладной и промышленной математики. – 2007. – Т. 14. – Вып. 5. – С. 857-858.
3. Bozhenyuk Alexander and Gerasimenko Evgeniya. Methods for Maximum and Minimum Cost Flow Determining in Fuzzy Conditions // World Applied Sciences Journal 22 (Special Issue on Techniques and Technologies). – 2013. – P. 76-81.
4. Боженюк А.В., Герасименко Е.М. Разработка алгоритма нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети // Инженерный Вестник Дона. – 2013. – № 1. – C. 12.
5. Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // In Combinatorial Structures and Their Applications, New York, NY, 1970, Gordon and Breach. – P. 93-96.
6. Tomizawa N. On some techniques useful for solution of transportation network problems // Networks. – 1971. – № 1. – P. 173-194.
7. Chabini I.,Abou-Zeid M. The Minimum Cost Flow Problem in Capacitated Dynamic Networks. In TRB 2003 Annual Meeting CD-ROM. – P. 1-30.
8. Боженюк А.В., Герасименко Е.М., Розенберг И.Н. Определение потока минимальной стоимости в нечетком динамическом графе // Известия ЮФУ. Технические науки. – 2013. – № 5 (142). – C. 149-154.

Comments are closed.