МЕТОДЫ СТРУКТУРИРОВАНИЯ НЕОПРЕДЕЛЕННОСТЕЙ ИСХОДНЫХ ДАННЫХ В ТРАНСПОРТНОЙ ЗАДАЧЕ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ

METHODS OF STRUCTURING UNCERTAINTIES IN UNCERTAINTY DATA IN THE TRANSPORT TASK WITH INTERMEDIATE ITEMS

Tebueva Fariza Bilyalovna

Doctor of Phys.-Math. Sci., Associate Professor, Head of the Department of Applied Mathematics and Computer Security North Caucasus Federal University,

Russia,​ Stavropol

Kabinyakov Mikhail Yurievich

Postgraduate student, Department of Applied Mathematics and Computer Security, North Caucasus Federal University,

Russia,​ Stavropol

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

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

Математическая постановка транспортной задачи с промежуточными пунктами в условиях недетерминированности исходных данных состоит в следующем. Являются известными:  – пункты отправления;  – промежуточные пункты;  – пункты назначения. Пусть  – предельный объем потребления ресурса пунктом ;  – объём необходимого для доставки - ому пункту потребления ресурса;  – предельный объём ресурса для перевозки из промежуточного пункта  к пункту потребления ;  – предельный объём ресурса при доставке из пункта отправления  в промежуточный пункт ;  – стоимость перевозки единицы ресурса из пункта отправления  через промежуточный пункт  к пункту назначения , , , .

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

– нечеткое множество  с множеством-носителем  и функцией принадлежности ;

– интервал значений  с началом  и концом ;

– временной ряд , .

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

, ;

, ;

, , ;

, , , .

Целевая функция определяет суммарные затраты на перевозку ресурса и имеет вид: .

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

Рассмотрим вначале неопределенность вида «нечеткое множество». При применении нечетких арифметических операций [4] могут возникнуть две проблемы: 1) несовпадающая размерность носителя не позволит выполнять арифметические операции векторным подходом, 2) несравнимость нечетких множеств со вложенными границами носителя. Для решения этих двух проблем предлагаются методы структурирования «Унификация размерностей нечетких множеств» и «Свертка центров тяжести носителя и функции принадлежности».

Метод «Унификация размерностей нечетких множеств» предназначен для сокращения размерности дискретных нечетких множеств до требуемого значения. Размерность дискретного нечеткого множества – число компонент носителя . Идея метода состоит в следующем. Пусть некоторое дискретное нечеткое множество  с размерностью носителя  нужно сократить до величины . И пусть тренд функции принадлежности может быть имеет одним их видов тренда: линейный ; экспоненциальный ; – логарифмический ; полиномиальный . В предлагаемом методе вначале следует изменить носитель путем оценки в интервале   равностоящих значений носителя . Получим новый носитель . Далее следует изменить степени принадлежности  путем подстановки аргументов  в функцию принадлежности выбранного тренда. В результате имеем новое дискретное нечеткое множество размерности : .

Метод структурирования «Свертка центров тяжести носителя и функции принадлежности» предназначен для возможности сравнения нечетких множеств со вложенными границами носителя. Дефазификация нечеткого множества  по центру тяжести [4] выполняется по формуле . Предлагается находить 2 центра тяжести:  и . Свертка центров тяжести носителя и функции принадлежности осуществляется по формуле , где  – коэффициенты важности центров тяжести  и . Для сравнения двух нечетких множеств  и  используются вычисленные величины  и : если , то .

Рассмотрим теперь неопределенность «интервальность значений» [5, 6]. В процессе обработки интервальных величин может возникнуть ситуация несравнимости двух интервалов со вложенными границами, аналогичная несравнимости нечетких множеств со вложенными границами носителя. Для решения этой проблемы предлагается метод структурирования «Свертка границ интервалов». Свертка границ интервала выполняется по формуле , где  – коэффициенты важности границ интервала, . Для равнозначных границ интервала .

Рассмотрим неопределенность вида «временной ряд». При наличии такого вида неопределенности исходных данных становятся неприменимыми все арифметические операции, включая операцию сравнения. Предлагается метод структурирования «Прогнозирование значений временного ряда». Технология прогнозирования состоит в следующем: вначале следует оценить класс принадлежности временного ряда, затем применить адекватный метод прогнозирования для этого класса временных рядов.

В настоящей работе предлагается рассматривать классификацию временных рядов по признаку персистентности (наличия/отсутствия долговременных корреляций настоящих и предыдущих значений). Оценить наличие/отсутствие свойства персистентности возможности на основе метода нормированного размаха [7], в котором рассчитывается усредненное по временному ряду значение показателя Херста . Персистентные временные ряды имеют усредненное значение показателя Херста , соответственно неперсистентные временные ряды имеют усредненное значение показателя Херста . Адекватными прогнозными моделями для неперсистентных временных рядов со свойством стационарности являются трендовые модели [8]. В работе [9] предложена прогнозная модель для временных рядов со свойствами нестационарности и персистентности, расчетная формула которой имеет вид , где  – усредненное значение показателя Херста.

Структурирование неопределенностей [7, 10] исходных данных в транспортной задаче с промежуточными пунктами позволят свести недетерминированную задачу к детерминированной задаче. Требуемый план поставок ресурса в рассматриваемой задаче можно на основе построения деревьев поиска на графах [11]. Методы структурирования неопределенностей исходных данных в транспортной задаче с промежуточными пунктами могут быть актуальными и в других прикладных областях. Например, эти методы могут быть успешно применены в робототехнике при разработке интеллектуальной системы поддержки принятия решений для управления поведением манипуляционных роботов [12]. Другой областью применения предлагаемых методов может защита сетей с пакетной передачей данных [13]. Практическая реализация предложенных методов структурирования в системах принятия решений возможна на основе имеющихся технических решений для построения вычислительных устройств. Например, в патентах [14-18] описаны методы и способы построения сумматоров, инверторов, умножителей, мультиплексора.

Список литературы:

1. Прилуцкий М.Х., Афраймович Л.Г. Многоиндексные задачи распределения ресурсов в иерархических системах// Автоматика и телемеханика. – 2006. – Вып. 6. – С.194-205.
2. Тебуева Ф.Б. Математические модели и методы для задач многокритериального выбора на графах в условиях недетерминированности исходных данных: Автореф. дис. докт. физ.-мат. наук. – Ставрополь, 2013. – 35 с.
3. Тебуева Ф.Б. Новые арифметические операции над нечеткими весами в дискретных задачах оптимизации на графах // Горный информационно-аналитический бюллетень. – 2008.– № 6. – С. 373-381.
4. Перепелица В.А., Тебуева Ф.Б. Задачи дискретной оптимизации с интервальными параметрами // Журнал вычислительной математики и математической физики. – 2010. – Т. 50. – № 5. – С. 836-847.
5. Perepelitsa V.A., Tebueva F.B. Discrete optimization problems with interval parameters/ Computational Mathematics and Mathematical Physics. – 2010. – Т. 50. – № 5. – С. 795-804.
6. Тебуева Ф.Б. Два подхода к реализации фрактального анализа временных рядов // Научно-технические ведомости СПбПУ. Естественные и инженерные науки. – 2007. – № 52-2. – С. 105-112.
7. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Структурирование данных методами нелинейной динамики для двухуровневого моделирования. Ставрополь: Ставропольское книжное издательство, 2006. – 284 с.
8. Федоткин М.А. Основы прикладной теории вероятностей и статистики. – М.: Высшая школа, 2006. – 368 с.
9. Kopytov V.V., Petrenko V.I., Tebueva F.B., Streblianskaia N.V. An improved brown's method applying fractal dimension to forecast the load in a computing cluster for short time series // Indian Journal of Science and Technology. – 2016. – Т.9 – № 19. – С. 93909.
10. Тебуева Ф.Б., Темирова Л.Г., Биджиев А.З., Коркмазова Ф.А. Структурирование данных для дискретных эволюционных процессов и прогнозирование временных рядов // Гуманитарные и социально-экономические науки. – 2006. – № 5. – С. 35.
11. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. – М.: Вильямс, 2013. – 1324 с.
12. Тебуева Ф.Б., Сычков В.Б., Огур М.Г. Общая схема системы поддержки принятия решений для оптимизации управления поведением мобильных манипуляционных роботов // Современная наука и инновации. – 2016. – №1 (13). – С. 22-29.
13. Сагдеев К.М., Петренко В.И., Чипига А.Ф. Физические основы защиты информации. – Ставрополь: Издательство Северо-Кавказского федерального университета, 2015. – 394 с.
14. Сныткин И.И., Петренко В.И. Устройство для формирования остатка по произвольному модулю от числа // Патент России № 1105895. 1983. Бюл. № 28.
15. Петренко В.И. Устройство для формирования остатка по произвольному модулю от числа // Патент России № 1396281. 1986. Бюл. № 25.
16. Петренко В.И., Чипига А.Ф. Умножитель на два по модулю // Патент России № 2015537. 1991. Бюл. № 12.
17. Петренко В.И., Чипига А.Ф. Комбинационный рекуррентный формирователь остатков // Патент России № 2029435. 1992. Бюл. № 5.
18. Петренко В.И., Кузьминов Ю.В. Умножитель по модулю // Патент России № 2299461. 2005. Бюл. № 14.