РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ МЕТОДОМ РАНЖИРОВАНИЯ В УСЛОВИЯХ НЕЧЕТКИХ ДАННЫХ
Аннотация и ключевые слова
Аннотация (русский):
В статье рассматривается применение метода ранжирования, посредством которого преобразуется транспортная задача с нечеткими данными и предлагается алгоритм нахождения оптимального решения. Приведенный численный пример демонстрирует, что предлагаемый метод является допустимым инструментом для решения транспортных задач на основе нечетких алгоритмов

Ключевые слова:
нечеткие данные, транспортная задача, метод ранжирования, оптимальное решение
Текст
Текст (PDF): Читать Скачать

Нечеткие множества играют важную роль в задачах принятия решений и анализа данных. Определение ранжирования нечетких чисел является неизбежным шагом во многих математических моделях [1]. Транспортная задача является частным случаем задач прикладной математики линейного программирования, которая позволяет определить оптимальную схему распределения потоков между грузообразующими и грузопоглащающими пунктами. Решение задачи позволяет определить общее количество груза, которое будет перевезено от грузоотправителя в определенный пункт назначения. В результате получается оптимальное решение, которое включает в себя минимальные временные затраты и максимальную полученную прибыль [2-4]. Задача нечеткой транспортировки является прогрессивным методом в том понимании, что данные о расходах на транспортировку, значение спроса и предложения могут быть заданы в виде нечетких величин. Впервые концепция нечеткого множества была введена Лотфи Заде в 1965 г.  [1]. В 2021 году авторами [5] была исследована двухэтапная задача нечеткой транспортировки, минимизирующая затраты, где спрос и предложение являются нечеткими числами, используя подход нечеткого решения. Предлагаемый алгоритм ранжирования заключается в поиске оптимального решения с использованием нечетких транспортных задач, учитывающих спрос, предложение и стоимость транспортировки в виде пятиугольных нечетких чисел.

Общая формулировка транспортной задачи может быть представлена следующим образом: значение ai  – определяется как количество груза, доступное у i-ого грузоотправителя; bi  – количество груза, необходимое в j-ом пункте назначения. Показатель aij  рассматривается как стоимость транспортировки груза от i-ого отправителя к конечному потребителю j, а Xij  количество перевозимого груза [6]. Для упрощенного ранжирования нечетких пятиугольных чисел вводится значение A  – это нечеткое множество, которое определяется как набор упорядоченных пар:

A=x0,μAx0/x0AμAx00,1

где μAx0  – функция принадлежности.

Кроме того, A  – это нечеткое множество на области допустимых значений R, ограниченное условиями, приведенными ниже:

  • μAx0  является непрерывным множеством;
  • существует по крайней мере одно значение, удовлетворяющее условию: x0R  с μAx0=1 ;
  • A  является правильным и выпуклым распределением (рисунок 1) [7].

Рисунок 1 – Схема построения задачи с помощью пятиугольных нечётких чисел [7]

 

Метод ранжирования для решения транспортной задачи с помощью пятиугольных нечетких чисел можно описать математическим выражением:

μAx=0,   x<a1u1~x-a2a3-a2,      a1xa21-1-u1~x-a2a3-a2a2xa31,         x=a31-1-u2~a4-xa4-a3a3xa4u2~a5-xa5-a4a4xa50,     x>a5

Средняя точка a3  имеет степень принадлежности, соответственно оценки имеют a4  и a2 . Каждое пятиугольное нечеткое число связано с двумя весами u1,  u2 .

Математическая формулировка пятиугольных нечетких чисел в случае, когда предложение эквивалентно спросу, приведена как:

Z=i=1sj=1taijxij

с учетом ограничений:

j=1txij=ai   j=1,2,…t

i=1txij=ai   i=1,2,…s

i=1sai=j=1tbj   i=1,2,…s, j=1,2,…t

xij≥0, i=1,2,…s, j=1,2,…t

Пусть aA=(a1,a2,a3,a4,a5)  это пятиугольные нечеткие числа с использованием метода центроидного ранжирования:

RaA=a52+a42+a5a4-a22-a12-a2a13.a5+a4-a2-a1

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

Шаг 1. Проверяется транспортная задача на сбалансированность:

i=1sai=j=1tbj

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

Шаг 2. Значение ранжирования присваивается для преобразования как спроса, так и предложения.

Шаг 3. Кратное по строкам между наибольшим и наименьшим значениями каждой строки делится на кратное по строкам и столбцам матрицы затрат.

Шаг 4. Кратное по столбцам между наибольшим и наименьшим значениями каждого столбца делится на кратное строк и столбцов матрицы затрат.

Шаг 5. Находится максимум результирующего значения и выделяется конкретная ячейка данной матрицы. Если есть более одного максимального результирующего значения, выбирается любое.

Шаг 6. Выполнять третий, четвертый и пятый шаг, пока не будут распределены группы (s+t-1) . Если выделенная ячейка не достигнута, применяется метод МОДИ для поиска оптимальности.

Рассмотрим числовой пример решения транспортной задачи в условиях нечетких данных, которая включает в себя стоимость транспортировки, объемы производства и потребления. Исходные данные задачи с использованием нечеткого множества пятиугольного вида приведены в таблице 1. Используя метод ранжирования, необходимо преобразовать нечеткие данные в четкие значения (таблица 2).

 

 

Таблица 1  – Исходные данные задачи с использованием нечеткого множества

 

Ra

Rb

Rc

Rd

Объём

производства, т

Ia

(2,4,6,8,9)

(3,5,7,8,9)

(2,4,5,6,7)

(3,4,6,7,12)

30

Ib

(0,2,5,6,8)

(4,5,6,8,11)

(2,3,5,7,11)

(1,5,6,9,11)

27

Ic

(1,2,3,4,5)

(2,3,4,6,8)

(4,5,6,8,9)

(6,7,8,9,13)

40

Id

(3,5,6,7,8)

(1,5,6,7,8)

(2,7,8,9,10)

(3,3,4,5,9)

50

Объём

потребления, т

20

38

34

55

 

 

Таблица 2  – Матрица затрат

 

Ra

Rb

Rc

Rd

Объём

производства, т

Ia

5,7272

6,2222

4,7143

6,6667

30

Ib

4,0000

7,0667

5,6970

6,4286

27

Ic

3,1111

4,7778

6,5000

8,8889

40

Id

5,7143

5,1111

6,8000

5,1667

50

Объём

потребления, т

20

38

34

55

 

 

Таблица 3 – Опорный план

 

Ra

Rb

Rc

Rd

Объём

производства, т

min∙maxряд∙столбец

Ia

5,7272

6,2222

4,7143

6,6667

30

1,964

Ib

4,0000

7,0667

5,6970

6,4286

27

1,766

Ic

3,1111

4,7778

6,5000

8,8889

40

1,728

Id

5,7143

5,1111

6,8000

5,1667

50

2,172

Объём

потребления, т

20

38

34

55

 

 

min∙maxряд∙столбец

1,1135

2,110

2,003

2,871

 

 

 

 

Таблица 4 – Оптимальный план перевозок

 

Ra

Rb

Rc

Rd

Объём

производства, т

Ia

5,7272

6,2222

30

4,7143

6,6667

30

Ib

18

4,0000

7,0667

4

5,6970

5

6,4286

27

Ic

2

3,1111

38

4,7778

6,5000

8,8889

40

Id

5,7143

5,1111

6,8000

50

5,1667

50

Объём

потребления, т

20

38

34

55

 

 

 

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

Подсчитаем число занятых клеток таблицы, их 7,  должно быть s + t – 1 = 7. Следовательно, опорный план является невырожденным. Общие затраты на транспортировку определим как:

min Z = 18 · 4,0000 + 2 · 3,1111 + 4 · 5,6970 +

+ 50 · 5,1667 + 5 · 6,4286 + 38 · 4,7778 + 30 ×

× 4,7143 = 714,4736

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

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

Нечеткие множества играют важную роль в задачах принятия решений и анализа данных. Определение ранжирования нечетких чисел является неизбежным шагом во многих математических моделях [1]. Транспортная задача является частным случаем задач прикладной математики линейного программирования, которая позволяет определить оптимальную схему распределения потоков между грузообразующими и грузопоглащающими пунктами. Решение задачи позволяет определить общее количество груза, которое будет перевезено от грузоотправителя в определенный пункт назначения. В результате получается оптимальное решение, которое включает в себя минимальные временные затраты и максимальную полученную прибыль [2-4]. Задача нечеткой транспортировки является прогрессивным методом в том понимании, что данные о расходах на транспортировку, значение спроса и предложения могут быть заданы в виде нечетких величин. Впервые концепция нечеткого множества была введена Лотфи Заде в 1965 г.  [1]. В 2021 году авторами [5] была исследована двухэтапная задача нечеткой транспортировки, минимизирующая затраты, где спрос и предложение являются нечеткими числами, используя подход нечеткого решения. Предлагаемый алгоритм ранжирования заключается в поиске оптимального решения с использованием нечетких транспортных задач, учитывающих спрос, предложение и стоимость транспортировки в виде пятиугольных нечетких чисел.

Общая формулировка транспортной задачи может быть представлена следующим образом: значение ai  – определяется как количество груза, доступное у i-ого грузоотправителя; bi  – количество груза, необходимое в j-ом пункте назначения. Показатель aij  рассматривается как стоимость транспортировки груза от i-ого отправителя к конечному потребителю j, а Xij  количество перевозимого груза [6]. Для упрощенного ранжирования нечетких пятиугольных чисел вводится значение A  – это нечеткое множество, которое определяется как набор упорядоченных пар:

A=x0,μAx0/x0AμAx00,1

где μAx0  – функция принадлежности.

Кроме того, A  – это нечеткое множество на области допустимых значений R, ограниченное условиями, приведенными ниже:

  • μAx0  является непрерывным множеством;
  • существует по крайней мере одно значение, удовлетворяющее условию: x0R  с μAx0=1 ;
  • A  является правильным и выпуклым распределением (рисунок 1) [7].

Рисунок 1 – Схема построения задачи с помощью пятиугольных нечётких чисел [7]

 

Метод ранжирования для решения транспортной задачи с помощью пятиугольных нечетких чисел можно описать математическим выражением:

μAx=0,   x<a1u1~x-a2a3-a2,      a1xa21-1-u1~x-a2a3-a2a2xa31,         x=a31-1-u2~a4-xa4-a3a3xa4u2~a5-xa5-a4a4xa50,     x>a5

Средняя точка a3  имеет степень принадлежности, соответственно оценки имеют a4  и a2 . Каждое пятиугольное нечеткое число связано с двумя весами u1,  u2 .

Математическая формулировка пятиугольных нечетких чисел в случае, когда предложение эквивалентно спросу, приведена как:

Z=i=1sj=1taijxij

с учетом ограничений:

j=1txij=ai   j=1,2,…t

i=1txij=ai   i=1,2,…s

i=1sai=j=1tbj   i=1,2,…s, j=1,2,…t

xij≥0, i=1,2,…s, j=1,2,…t

Пусть aA=(a1,a2,a3,a4,a5)  это пятиугольные нечеткие числа с использованием метода центроидного ранжирования:

RaA=a52+a42+a5a4-a22-a12-a2a13.a5+a4-a2-a1

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

Шаг 1. Проверяется транспортная задача на сбалансированность:

i=1sai=j=1tbj

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

Шаг 2. Значение ранжирования присваивается для преобразования как спроса, так и предложения.

Шаг 3. Кратное по строкам между наибольшим и наименьшим значениями каждой строки делится на кратное по строкам и столбцам матрицы затрат.

Шаг 4. Кратное по столбцам между наибольшим и наименьшим значениями каждого столбца делится на кратное строк и столбцов матрицы затрат.

Шаг 5. Находится максимум результирующего значения и выделяется конкретная ячейка данной матрицы. Если есть более одного максимального результирующего значения, выбирается любое.

Шаг 6. Выполнять третий, четвертый и пятый шаг, пока не будут распределены группы (s+t-1) . Если выделенная ячейка не достигнута, применяется метод МОДИ для поиска оптимальности.

Рассмотрим числовой пример решения транспортной задачи в условиях нечетких данных, которая включает в себя стоимость транспортировки, объемы производства и потребления. Исходные данные задачи с использованием нечеткого множества пятиугольного вида приведены в таблице 1. Используя метод ранжирования, необходимо преобразовать нечеткие данные в четкие значения (таблица 2).

 

 

Таблица 1  – Исходные данные задачи с использованием нечеткого множества

 

Ra

Rb

Rc

Rd

Объём

производства, т

Ia

(2,4,6,8,9)

(3,5,7,8,9)

(2,4,5,6,7)

(3,4,6,7,12)

30

Ib

(0,2,5,6,8)

(4,5,6,8,11)

(2,3,5,7,11)

(1,5,6,9,11)

27

Ic

(1,2,3,4,5)

(2,3,4,6,8)

(4,5,6,8,9)

(6,7,8,9,13)

40

Id

(3,5,6,7,8)

(1,5,6,7,8)

(2,7,8,9,10)

(3,3,4,5,9)

50

Объём

потребления, т

20

38

34

55

 

 

Таблица 2  – Матрица затрат

 

Ra

Rb

Rc

Rd

Объём

производства, т

Ia

5,7272

6,2222

4,7143

6,6667

30

Ib

4,0000

7,0667

5,6970

6,4286

27

Ic

3,1111

4,7778

6,5000

8,8889

40

Id

5,7143

5,1111

6,8000

5,1667

50

Объём

потребления, т

20

38

34

55

 

 

Таблица 3 – Опорный план

 

Ra

Rb

Rc

Rd

Объём

производства, т

min∙maxряд∙столбец

Ia

5,7272

6,2222

4,7143

6,6667

30

1,964

Ib

4,0000

7,0667

5,6970

6,4286

27

1,766

Ic

3,1111

4,7778

6,5000

8,8889

40

1,728

Id

5,7143

5,1111

6,8000

5,1667

50

2,172

Объём

потребления, т

20

38

34

55

 

 

min∙maxряд∙столбец

1,1135

2,110

2,003

2,871

 

 

 

 

Таблица 4 – Оптимальный план перевозок

 

Ra

Rb

Rc

Rd

Объём

производства, т

Ia

5,7272

6,2222

30

4,7143

6,6667

30

Ib

18

4,0000

7,0667

4

5,6970

5

6,4286

27

Ic

2

3,1111

38

4,7778

6,5000

8,8889

40

Id

5,7143

5,1111

6,8000

50

5,1667

50

Объём

потребления, т

20

38

34

55

 

 

 

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

Подсчитаем число занятых клеток таблицы, их 7,  должно быть s + t – 1 = 7. Следовательно, опорный план является невырожденным. Общие затраты на транспортировку определим как:

min Z = 18 · 4,0000 + 2 · 3,1111 + 4 · 5,6970 +

+ 50 · 5,1667 + 5 · 6,4286 + 38 · 4,7778 + 30 ×

× 4,7143 = 714,4736

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

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

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

1. Геращенко, И. П. Экономико-математические методы и модели: учебное пособие / И.П. Геращенко, Е.В. Шуль-га. - Омск: Изд-во Омского экономического института, 2007. 292 с.

2. Колесник, М. Н. Применение динамической транспортной задачи с задержками для согласования ритмов рабо-ты поставщиков и перевозчиков / М. Н. Колесник. - Текст: непосредственный // Вестник Иркутского государственного технического университета. 2009. № 1 (37). С. 63-65.

3. Минько, А. М. Дополнительные условия при решении транспортной задачи методом потенциалов / А.М. Минько, П.К. Ляпустин. - Текст: непосредственный // Сборник научных трудов Ангарского государственного технического университета. 2014. Т. 1. № 1. С. 212-215.

4. Лебедева, О. А. Решение транс-портной задачи с использованием алгоритма Дейкстры для грузовых перевозок / О.А. Лебедева, И.М. Кулакова. - Текст: непосредственный // Вестник Уральского государственного университета путей со-общения. 2022. № 2 (54). С. 24-31.

5. Srinivasan, R. A proposed ranking method to solve transportation problem by pentagonal fuzzy numbers / R. Srinivasan, N. Karthikeyan, A. Jayaraja // Turkish online journal of qualitative inquiry. Volume 12, Is-sue 3. 2021. pp. 277-286.

6. Ляпустин, П. К. Решение транс-портной задачи с учётом дополнительных условий / П.К. Ляпустин, А.М. Минько, К.А. Мальцева. - Текст: непосредственный // В сборнике: Международная научно-практическая конференция "Архитектура, строительство, транспорт" (к 85-летию ФГБОУ ВПО "СибАДИ"). Сборник науч-ных трудов № 8 кафедры "Организация перевозок и управление на транспорте". ФГБОУ ВПО «СибАДИ», Кафедра «ОПиУТ»; Ответственный за выпуск Е. Е. Витвицкий. 2015. С. 281-288.

7. Panda, A. A study on pentagonal fuzzy number and its corresponding matrices / A. Panda, M. Pal // Pacific Science Review B: Humanities and Social Sciences. Vol. 1 (3). 2015. pp. 131-139.

8. Полтавская, Ю. О. Сравнительный анализ результатов, полученных при решении транспортных задач разными способами / Ю.О. Полтавская. - Текст: непосредственный // Вестник Ангарского государственного технического университета. 2019. № 13. С. 183-186.

9. Лебедева, О. А. Сравнительный анализ методов решения транспортных за-дач при оптимальном планировании перевозочного процесса / О. А. Лебедева, В. Е. Гозбенко, А.А. Пыхалов, Ю.Ф. Мухопад. - Текст: непосредственный // Современные технологии. Системный анализ. Модели-рование. 2020. № 3 (67). С. 134-139.

10. Крипак, М. Н. Автоматизация алгоритма Литтла для решения задачи коммивояжера / М.Н. Крипак, И.М. Кула-кова, О.А. Лебедева. - Текст: непосредственный // Современные технологии. Системный анализ. Моделирование. 2015. № 4 (48). С. 160-163.

Войти или Создать
* Забыли пароль?