Региональная транспортно-логистическая система служит материальной базой производственных связей между отдельными территориями. Значительная часть логистических операций на пути движения материального потока от первичного источника сырья до конечного потребителя осуществляется с применением различных транспортных средств. В связи с этим возникает необходимость уделить должное внимание определению рациональных и оптимальных маршрутов доставки продукции. Для определения рациональных маршрутов доставки воспользуемся транспортной задачей линейного программирования. Определение рациональных маршрутов доставки транспортных потоков в региональной транспортно-логистической системе с помощью транспортной задачи линейного программирования в данной работе позволяет разработать наиболее рациональные способы и пути транспортировки товаров, тем самым избежать дополнительных затрат предприятия, связанных с осуществлением процессов снабжения сырьем, материалами, топливам, оборудованием.
Ключевые слова: региональная экономика, региональные транспортно-логистические системы, линейное программирование.
Глобализация экономики сопровождается небывалыми раньше темпами роста торговли. В этих условиях максимально вырастает значение транспортно-логистической системы. Региональная транспортно-логистическая система (РТЛС) служит материальной базой производственных связей между отдельными территориями, выступает как фактор, организующий экономическое пространство и обеспечивающий дальнейшее географическое разделение труда.
В структуре общественного производства РТЛС относится к сфере производства материальных услуг. Значительная часть логистических операций на пути движения материального потока от первичного источника сырья до конечного потребителя осуществляется с применением различных транспортных средств. Затраты на выполнение различных логистических операций порой составляют значительную часть расходов предприятия. В связи с этим возникает необходимость уделить должное внимание определению рациональных и оптимальных маршрутов доставки продукции.
Для определения рациональных маршрутов доставки воспользуемся транспортной задачей линейного программирования. Это задача линейного программирования специального вида о поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.
Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Поставим транспортную задачу для холдинга. Для изготовления продукции требуются определенные ресурсы. У холдинга имеется определенная часть ресурсов, другая часть закупается у поставщиков. И прежде чем ресурсы появятся на предприятии нужно их доставить от поставщика. Рассмотрим модель транспортной задачи для минимизации затрат на маршрут и доставку материалов. Для определения расстояния воспользуемся on-line сервисом автомобильного портала грузоперевозок [1] (пример определения расстояния представлен на рис.1).
В качестве отправных пунктов взяты следующие города. У холдинга есть 5 баз хранения в разных городах России, куда нужно доставить по 1 заказу.
Санкт-Петербург, Москва, Псков, Старая Русса (Ленинградская область, Сланцевский район), Смоленск.
Поставщики:
- Ульяновск
- Тула
- Волгоград
- Казань
- Томск
Запишем данные в таблице 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.
- Проводим редукцию матрицы по строкам, т. е. вычитаем минимальный элемент из всех элементов каждой строки. В связи с этим во вновь полученной матрице (табл.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, 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;
Столбец 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.
- Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль (табл.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).
- Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
В данной таблице количество нулей равно 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.
- Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль (табл.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 году он опубликовал свой труд «Математические методы организации и планирования производства», в работе был сформулирован новыйклассэкстремальныхзадачс ограничениямии разработанэффективныйметодихрешения.
Литература:
- Автомобильный портал грузоперевозокhttp://www.avtodispetcher.ru/distance
- Афанасьев М. Ю., Суворов Б. П. Исследование операций в экономике: модели, задачи, решения/ М. Ю. Афанасьев, Б. П. Суворов// Учебное пособие. — Москва: ИНФРА-М, 2003. — С. 444.
- Красс, М. С. Математические методы и модели для магистрантов экономики / М. С. Красс, Б. П. Чупрынов// Учебное пособие по направлению «Экономика» и другим экономическим специальностям — СПб.: Питер, 2006. — С 496.
