Библиографическое описание:

Афанасьева В. Г. Определение рациональных маршрутов доставки транспортных потоков в региональной транспортно-логистической системе с помощью транспортной задачи линейного программирования // Молодой ученый. — 2015. — №20. — С. 195-202.

 

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

Ключевые слова: региональная экономика, региональные транспортно-логистические системы, линейное программирование.

 

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

В структуре общественного производства РТЛС относится к сфере производства материальных услуг. Значительная часть логистических операций на пути движения материального потока от первичного источника сырья до конечного потребителя осуществляется с применением различных транспортных средств. Затраты на выполнение различных логистических операций порой составляют значительную часть расходов предприятия. В связи с этим возникает необходимость уделить должное внимание определению рациональных и оптимальных маршрутов доставки продукции.

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

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

Поставим транспортную задачу для холдинга. Для изготовления продукции требуются определенные ресурсы. У холдинга имеется определенная часть ресурсов, другая часть закупается у поставщиков. И прежде чем ресурсы появятся на предприятии нужно их доставить от поставщика. Рассмотрим модель транспортной задачи для минимизации затрат на маршрут и доставку материалов. Для определения расстояния воспользуемся on-line сервисом автомобильного портала грузоперевозок [1] (пример определения расстояния представлен на рис.1).

В качестве отправных пунктов взяты следующие города. У холдинга есть 5 баз хранения в разных городах России, куда нужно доставить по 1 заказу.

Санкт-Петербург, Москва, Псков, Старая Русса (Ленинградская область, Сланцевский район), Смоленск.

Поставщики:

  1.                Ульяновск
  2.                Тула
  3.                Волгоград
  4.                Казань
  5.                Томск

Запишем данные в таблице 1:

Таблица 1

Расстояние в км.

Поставщики сырья

Ульяновск

Тула

Волгоград

Казань

Томск

Расстояние от СПб до поставщика

1572

873

1628

1512

4162

Расстояние от МСК до поставщика

885

184

941

825

3612

Расстояние от Пскова до поставщика

1960

904

1665

1549

4336

Расстояние от Старой Руссы до поставщиками

1453

754

1517

1393

4106

Расстояние от Смоленск до поставщика

1283

465

1293

1223

4010

 

Рис. 1. Расстояние между Санкт-Петербургом и Ульяновском

 

Примечание: Длина пути: 1572 км; Время пути: 17:07; Топливо: 471,6 л.

Расстояние для остальных пунктов считается таким же образом как на рис.1.

Теперь у нас есть все данные для нахождения минимальной дальности доставки поставок.

Исходная матрица представлена на табл.2 (матрица дополнена столбцом из минимальных по каждой строке элементов):

Таблица 2

1572

873

1628

1512

4162

873

885

184

941

825

3612

184

1960

904

1665

1549

4336

904

1453

754

1517

1393

4106

754

1283

465

1293

1223

4010

465

 

Шаг № 1.

  1. Проводим редукцию матрицы по строкам, т. е. вычитаем минимальный элемент из всех элементов каждой строки. В связи с этим во вновь полученной матрице (табл.3) в каждой строке будет как минимум один ноль:

Таблица 3

699

0

755

639

3289

701

0

757

641

3428

1056

0

761

645

3432

699

0

763

639

3352

818

0

828

758

3545

699

0

755

639

3289

 

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент (табл.4):

Таблица 4

0

0

0

0

0

2

0

2

2

139

357

0

6

6

143

0

0

8

0

63

119

0

73

119

256

 

После вычитания минимальных элементов получаем полностью редуцированную матрицу (табл.4).

  1. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

Фиксируем нулевое значение в клетке (1, 2). Другие нули в строке 1 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 2), (3; 2), (4; 2), (5;2), (1;1), (1;3), (1;4), (1;5)

В таблице 5 количество нулей равно 2 (должно быть 5)

Таблица 5

[-0-]

0

[-0-]

[-0-]

[-0-]

2

[-0-]

2

2

139

357

[-0-]

6

6

143

0

[-0-]

8

[-0-]

63

119

[-0-]

73

119

256

 

Поскольку расположение нулевых элементов в матрице (табл.5) не позволяет образовать систему из 5-х независимых нулей (в матрице их только 2), то решение недопустимое.

  1. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:

Строка 1;

Столбец 2;

Строка 4;

Получаем сокращенную матрицу (табл.6) (элементы выделены)

Таблица 6

0

0

0

0

0

2

0

2

2

139

357

0

6

6

143

0

0

8

0

63

119

0

73

119

256

 

Минимальный элемент сокращенной матрицы (2) вычитаем из всех ее элементов (табл.7):

Таблица 7

0

0

0

0

0

0

0

0

0

137

355

0

4

4

141

0

0

8

0

63

117

0

71

117

254

 

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов (табл.8):

Таблица 8

0

2

0

0

0

0

0

0

0

137

355

0

4

4

141

0

2

8

0

63

117

0

71

117

254

 

Шаг № 2.

  1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль (табл.9).

Таблица 9

0

2

0

0

0

0

0

0

0

0

137

0

355

0

4

4

141

0

0

2

8

0

63

0

117

0

71

117

254

0

 

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент (табл.10):

Таблица 10

0

2

0

0

0

0

0

0

0

137

355

0

4

4

141

0

2

8

0

63

117

0

71

117

254

0

0

0

0

0

 

После вычитания минимальных элементов получаем полностью редуцированную матрицу (табл.10).

  1. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

В данной таблице количество нулей равно 3 (должно быть 5).

Таблица 11

0

2

[-0-]

[-0-]

[-0-]

[-0-]

0

[-0-]

[-0-]

137

355

[-0-]

4

4

141

[-0-]

2

8

0

63

117

[-0-]

71

117

254

 

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только3 (табл.11)), то решение недопустимое

1.Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов (табл.12):

Таблица 12

0

2

0

0

0

0

0

0

0

137

355

0

4

4

141

0

2

8

0

63

117

0

71

117

254

 

Минимальный элемент сокращенной матрицы (4) вычитаем из всех ее элементов (табл.13):

Таблица 13

0

2

0

0

0

0

0

0

0

137

351

0

0

0

137

0

2

8

0

63

113

0

67

113

250

 

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов (табл.14):

Таблица 14

0

6

0

0

0

0

4

0

0

137

351

0

0

0

137

0

6

8

0

63

113

0

67

113

0

 

Шаг № 3.

  1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль (табл.15).

Таблица 15

0

6

0

0

0

0

0

4

0

0

137

0

351

0

0

0

137

0

0

6

8

0

63

0

113

0

67

113

250

0

 

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент (табл.16):

Таблица 16

0

6

0

0

0

0

4

0

0

137

351

0

0

0

137

0

6

8

0

63

113

0

67

113

250

0

0

0

0

0

 

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

В таблице 17 количество найденных нулей равно к = 5. в результате получаем эквивалентную матрицу:

Таблица 17

[-0-]

6

[-0-]

[-0-]

0

[-0-]

4

[-0-]

0

137

351

[-0-]

0

[-0-]

137

0

6

8

[-0-]

63

113

0

67

113

250

 

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

Таблица 18

1572

873

1628

1512

4162

885

184

941

825

3612

1960

904

1665

1549

4336

1453

754

1517

1393

4106

1283

465

1293

1223

4010

 

Cmin = 4162+ 825+ 1665+ 465+ 1453 = 8570

Имеется альтернативный вариант № 2 (табл.18).

Таблица 19

[-0-]

6

[-0-]

[-0-]

0

0

4

[-0-]

[-0-]

137

351

[-0-]

0

[-0-]

137

[-0-]

6

8

0

63

113

0

67

113

250

 

Таблица 20

1572

873

1628

1512

4162

885

184

941

825

3612

1960

904

1665

1549

4336

1453

754

1517

1393

4106

1283

465

1293

1223

4010

 

Cmin = 4162+ 885+ 1665+ 1393+ 465= 8570

Таким образом, реализация модели показывает нам, что ресурсы из Ульяновска нужно везти в Старую Руссу или в Москву, из Тулы в Смоленск, из Волгограда удобно будет везти в Псков, из Казани в Старую Руссу или в Москву, из Томска в Санкт-Петербург (табл.20). При этом минимальное суммарное расстояние составляет 8970 км.

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

Интересно отметить, что алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. [Красс, c.289] Например:

        Оптимальное закрепление за станками операций по обработке деталей. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей.

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

        Задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции.

        Увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега, сокращение которого позволит уменьшить количество автомобилей для перевозок за счет увеличения их производительности. Это подчеркивает актуальность использования транспортной задачи линейного программирования. Занимательно, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый — Леонид Витальевич Канторович. В 1939 году он опубликовал свой труд «Математические методы организации и планирования производства», в работе был сформулирован новыйклассэкстремальныхзадачс ограничениямии разработанэффективныйметодихрешения.

 

Литература:

 

  1.                Автомобильный портал грузоперевозокhttp://www.avtodispetcher.ru/distance
  2.                Афанасьев М. Ю., Суворов Б. П. Исследование операций в экономике: модели, задачи, решения/ М. Ю. Афанасьев, Б. П. Суворов// Учебное пособие. — Москва: ИНФРА-М, 2003. — С. 444.
  3.                Красс, М. С. Математические методы и модели для магистрантов экономики / М. С. Красс, Б. П. Чупрынов// Учебное пособие по направлению «Экономика» и другим экономическим специальностям — СПб.: Питер, 2006. — С 496.

Обсуждение

Социальные комментарии Cackle