Решение задач по оптимизации транспортных перевозок

Транспортная задача – решение методом потенциалов

Одна из самых распространенных и востребованных оптимизационных задач в логистике – транспортная задача. В классическом виде она предполагает нахождение оптимального (т.е. сопряженного с минимальными затратами) плана грузоперевозок.

Например, у нас есть сеть розничных магазинов, которым требуется определенное количество товаров. Также имеется ряд складов поставщиков, где требуемые товары хранятся. При этом на каждом складе различный объем запасов этих товаров. Кроме этого нам известны тарифы – затраты на перевозку 1 товара от каждого склада к каждому магазину.

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

Теоретический материал по транспортной задаче

Транспортная задача (задача Монжа – Канторовича) – математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления (например, складов) в пункты потребления (например, магазины), с минимальными общими затратами на перевозки.

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

где: Z – затраты на перевозку грузов;
X – объем груза;
C – стоимость (тариф) перевозки единицы груза;
A – запас поставщика;
B – запрос потребителя;
m – число поставщиков;
n – число потребителей.

Общий план решения транспортной задачи методом потенциалов

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

Суть его в следующем: находим некий опорный план и проверяем его на оптимальность (Z → min). Если план оптимален – решение найдено. Если нет – улучшает план столько раз, сколько потребуется, пока не будет найден оптимальный план.

Ниже приведен алгоритм решения транспортной задачи в самом общем виде:

1. Построение транспортной таблицы.
2. Проверка задачи на закрытость.
3. Составление опорного плана.
4. Проверка опорного плана на вырожденность.
5. Вычисление потенциалов для плана перевозки.
6. Проверка опорного плана на оптимальность.
7. Перераспределение поставок.
8. Если оптимальное решение найдено, переходим к п. 9, если нет – к п. 5.
9. Вычисление общих затрат на перевозку груза.
10. Построение графа перевозок.

Подробная инструкция по решению транспортной задачи

1. Построение транспортной таблицы

Строим таблицу, где указываем запасы материалов, имеющиеся на складах поставщиков (Ai), и потребности заводов (Bj) в этих материалах.

В нижний правый угол ячеек таблицы заносим значение тарифов на перевозку груза (Cij).

2. Проверка задачи на закрытость

Обозначим суммарный запас груза у всех поставщиков символом A, а суммарную потребность в грузе у всех потребителей – символом B.

Транспортная задача называется закрытой, если A = B . Если же A ≠ B , то транспортная задача называется открытой. В случае закрытой задачи от поставщиков будут вывезены все запасы груза, и все заявки потребителей будут удовлетворены. В случае открытой задачи для ее решения придется вводить фиктивных поставщиков или потребителей.

Проверим задачу на закрытость:

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, следовательно данная транспортная задача – закрытая.

3. Составление опорного плана

Составляет предварительный (опорный) план перевозок. Он не обязательно должен быть оптимальный. Это просто своеобразный «черновик», «набросок», улучшая который мы постепенно придем к плану оптимальному.

Есть разные методы нахождения опорного плана. Наиболее распространены следующие:

Суть метода проста – ячейки транспортной таблицы последовательно заполняются максимально возможными объемами перевозок, в направлении сверху вниз и слева направо. То есть сперва заполняется самая верхняя левая ячейка (“северо-западная” ячейка), потом следующая справа и т.д. Затем переходят на новую строку и вновь заполняют ее слева направо. И так пока таблица не будет заполнена полностью.

Подробное описание метода и пример можно посмотреть здесь.

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

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

4. Проверка опорного плана на вырожденность

Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) – свободными.

План называется вырожденным, если количество базисных клеток в нем меньше, чем m + n -1. Если во время решения задачи получился вырожденный план, то его необходимо пополнить, проставив в недостающем числе клеток нулевую перевозку и превратив, тем самым, эти клетки в базисные (общий баланс и суммарная стоимость перевозок плана при этом не изменятся). Однако проводить пополнение плана, выбирая клетки произвольно, нельзя. План должен быть ациклическим!

План называется ациклическим, если его базисные клетки не содержат циклов. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ниже приведен пример цикла:

Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

Кол-во базисных клеток = 5

m + n – 1 = 3 + 3 – 1 = 5

Следовательно, первоначальный план перевозок – невырожденный.

5. Вычисление потенциалов для плана перевозки

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

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

Итак, сопоставим каждому поставщику Ai и каждому потребителю Bj величины Ui и Vj соответственно так, чтобы для всех базисных клеток плана было выполнено соотношение:

Ui + Vj = Cij

Добавим к транспортной таблице дополнительную строку и столбец для Ui и Vj.

Предположим, что U1 = 0.

Тогда мы сможем найти V3 = C13 – U1 = 1 – 0 = 1.

Зная V3, мы теперь можем найти U3:

По аналогии вычисляем все оставшиеся потенциалы:

6. Проверка плана на оптимальность методом потенциалов

Для каждой свободной клетки плана вычислим разности

ΔCij = Cij – (Ui + Vj )

и запишем полученные значения в левых нижних углах соответствующих ячеек.

План является оптимальным, если все разности ΔCij ≥ 0.

В данном случае план – неоптимальный (ΔC22 7. Перераспределение поставок

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

Отметим ячейку с отрицательной разностью ΔCij знаком «+», следующую знаком «-», и так далее, поочередно.

Затем находим минимальной значение груза в ячейках цикла имеющих знак «-» (здесь это 5) и вписываем его в свободную ячейку со знаком «+». Затем последовательно обходим все ячейки цикла, поочередно вычитая и прибавляя к ним минимальное значение (в соответствии со знаками, которыми эти ячейки помечены: где минус – вычитаем, где плюс – прибавляем).

Получим новый опорный план перевозок:

Так как базисных клеток стало больше, чем m + n – 1, то базисную клетку с нулевым значением делаем свободной:

Снова вычисляем значения потенциалов и разности ΔCij:

На этот раз все разности ΔCij ячеек положительные, следовательно, найдено оптимальное решение.

8. Если оптимальное решение найдено, переходим к п. 9, если нет – к п. 5.

У нас оптимальное решение найдено, поэтому переходим к пункту 9.

9. Вычисление общих затрат на перевозку груза

Вычислим общие затраты на перевозку груза (Z), соответствующие найденному нами оптимальному плану, по формуле:

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 ден. ед.

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

10. Построение графа перевозок

Найдя оптимальный план перевозок, построим граф. Вершинами графа будут «склады» и «магазины». В вершинах укажем соответствующие объемы запасов и потребностей. Дугам, соединяющим вершины графа, будут соответствовать ненулевые перевозки. Каждую такую дугу подпишем, указав объем перевозимого груза.

В результате получится граф, аналогичный изображенному ниже:

Все, транспортная задача решена. Поздравляю!

Практическое применение транспортной задачи

Транспортная задача применяется во многих случаях. Это оптимизация поставок сырья и материалов на производственные предприятия. Это оптимизация доставок товаров со складов в розничные магазины. Это оптимизация пассажирских перевозок, и много-многое другое.

© Копирование материала допустимо только при указании прямой гиперссылки на источник: Галяутдинов Р.Р.

Пригодилась статья? Поделитесь с друзьями:

Библиографическая запись для цитирования статьи по ГОСТ Р 7.0.5-2008:
Галяутдинов Р.Р. Транспортная задача – решение методом потенциалов // Сайт преподавателя экономики. [2013]. URL: http://galyautdinov.ru/post/transportnaya-zadacha (дата обращения: 20.02.2020).

	Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl+Enter.

	ФОРМУЛЫ –>
	ТЕРМИНЫ –>
	БУХУЧЕТ –>
	НАЛОГИ –>
	СТАТИСТИКА –>
	БИОГРАФИИ –>
	ЗАДАЧИ –>
	ENGLISH –>

ГАЛЯУТДИНОВ
Руслан Рамилевич
старший преподаватель экономических дисциплин (маркетинг, логистика, рынок ценных бумаг). подробнее

Транспортная задача и оптимизация грузоперевозок Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Васильев О.В., Леденева Т.М.

В статье рассматривается транспортная задача . Предложена адаптация входных данных и модификация транспортной таблицы для работы со специфическими железнодорожными объектами. Получены результаты программного расчета транспортной задачи с модифицированными таблицами. Приводится пример использования данной адаптации входных данных для оптимизации реальных грузоперевозок

Похожие темы научных работ по математике , автор научной работы — Васильев О.В., Леденева Т.М.

FORECAST BUILDING ON THE BASE OF FUZZY COMPENSATOIN THEORY

In clause the transport task is considered. Adaptation of entrance data and updating of the transport table for work with specific railway objects is offered. Results of program calculation of a transport task with the modified tables are received. The example of use of the given adaptation of entrance data for optimization of real cargo transportations is resulted

Текст научной работы на тему «Транспортная задача и оптимизация грузоперевозок»

ТРАНСПОРТНАЯ ЗАДАЧА И ОПТИМИЗАЦИЯ ГРУЗОПЕРЕВОЗОК О.В. Васильев, Т.М. Леденева

В статье рассматривается транспортная задача. Предложена адаптация входных данных и модификация транспортной таблицы для работы со специфическими железнодорожными объектами. Получены результаты программного расчета транспортной задачи с модифицированными таблицами. Приводится пример использования данной адаптации входных данных для оптимизации реальных грузоперевозок

Ключевые слова: оптимизация, грузоперевозки, транспортная задача

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

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

Рассмотрим классическую модель транспортной задачи.

Имеется т пунктов производства (поставщиков) и п пунктов потребления (потребителей) однородного продукта. Заданы величины а. (объем производства или запас . -го поставщика, . = 1..т ), Ь(объем потребления или спрос ] -го потребителя, ] = 1..п ), с^ (стоимость перевозки, т.е. транспортные затраты, на единицу продукта от . -го поставщика к ] -му потребителю. Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен, и при этом общая стоимость всех перевозок была бы минимальна [1].

Васильев Олег Вячеславович – ВГТУ, аспирант, тел. (473) 243-77-18

Леденева Татьяна Михайловна – ВГУ, д-р техн. наук, профессор, 8 903 850 29 96

Математическая модель транспортной задачи имеет вид

x > 0, i = 1, m, j = 1, n,

Z = ££ cj ■ xj ® min (3)

Формулы (1) и (2) описывают количество товара, которое имеется у поставщиков и которое требуется потребителям соответственно, и обозначают место данных чисел в матрице решения Xij. Все элементы матрицы Xij должны ij j

быть либо положительными (это значит, что от поставщика ai перевезено соответствующее количество товара к потребителю bj), либо нулевыми (это значит, что от поставщика ai к потребителю bj товар не перевозится). Отрицательных чисел матрица решений содержать не может. Это ограничение связано с логикой задачи: перевезти отрицательное количество товара невозможно [2].

Суть решения транспортной задачи содержится в формуле (3): проблему можно свести к минимизации целевой функции Z , которая является общей стоимостью перевозок и вычисляется как сумма произведений элементов матрицы решения Xij. и соответствующих элементов

матрицы стоимостей CiJ- . План перевозок, согласно которому целевая функция Z минимальна, называется оптимальным планом и является решением транспортной задачи.

Для решения транспортной задачи требуется пройти два этапа: сначала построить опорный план (опорное решение), а потом оптимизировать его.

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

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

Особенностью решения практических задач по оптимизации железнодорожных перевозок является их большая размерность. В частности, транспортная таблица может иметь размерность 500х600 клеток. Кроме того, стоимость перевозок обычно достаточно сильно различается, т.к. значение имеет не только расстояние, но и железнодорожные тарифы для каждого перегона. Таким образом, если составлять опорное решение с достаточно высокой оптимизированно-стью, т.е. по методу двойного предпочтения или аппроксимации Фогеля, то это займет значительное время, хотя дальнейшая его оптимизация будет недолгой. С другой стороны, неопти-мизированное опорное решение, составленное очень быстро (по методу северо-западного угла), из-за высокой разницы стоимостей будет оптимизироваться тоже достаточно быстро. Поэтому мы выбираем метод северо-западного угла. Он очень прост: заполнение происходит по мере использования товара, с верхнего левого угла.

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

Математическая модель метода потенциалов выглядит следующим образом. Если допустимое решение транспортной задачи Х = (ху) (при i = 1,2. т , у = 1,2. п ) является оптимальным, то существуют потенциалы (числа) поставщиков ui, i = 1,2. т , и потребителей , у = 1,2. п, удовлетворяющее следующим условиям:

иг + = су (хЧ > 0К и + ^ = СУ (ХЧ= 0).

Данная группа равенств используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде:

А у = и + V’ – С’ 0 , то для соответствующей клетки

строят цикл и улучшают решение, перераспределяют груз согласно формуле:

Алгоритм решения транспортных задач методом потенциалов:

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

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

3. Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений ui + Vу = с у при

х^ > 0 , которая имеет бесконечное множество

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

при x, > 0 , если известен потенциал v. , и v, = е.. — u. при x,, > 0, если известен потен-

4. Проверить выполнения условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам А. = ui + v. — е , , и те из

них, которые больше нуля, записываются в левые нижние углы клеток. Если для всех свободных клеток А.. £ 0, то вычисляют значение целевой функции и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, опорное решение не является оптимальным.

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

Далее строится цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину d = щщ . Клетка со

знаком «-», в которой достигается ос-

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

Далее снова возвращаемся к третьему пункту алгоритма.

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

1. Пупков К.А., Коньков В.Г. Интеллектуальные системы. М.: Изд-во МГТУ им. Н.Э.Баумана, 2003. 348 с.

2. Борисова Е.А., Финаев В.И. Вероятностный прогноз в распределительных задачах. Таганрог: ТРТУ, 2006. 128 с.

3. Голыптейн Е.Г., Юдин Д.В. Задачи линейного программирования транспорного типа. М.: Наука, 1969.

4. Интрилигатор М. Математические модели оптимизации и экономическая теория. М.: Наука, 2002. 1020 с.

Воронежский государственный технический университет Воронежский государственный университет

FORECAST BUILDING ON THE BASE OF FUZZY COMPENSATOIN THEORY

O.V. Vasilev, T.M. Ledeneva

In clause the transport task is considered. Adaptation of entrance data and updating of the transport table for work with specific railway objects is offered. Results of program calculation of a transport task with the modified tables are received. The example of use of the given adaptation of entrance data for optimization of real cargo transportations is resulted

Key words: optimization, cargo transportations, a transport task

Оптимизация работы транспорта: методы и решения логистики

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

Основные задачи транспортной оптимизации

Основная задача, которая стоит перед менеджерами организации в данном аспекте, это снижение затрат на перевозки без потери их качества. Про планирование логистических процессов было рассказано в отдельной статье. Рассмотрим основные типы издержек, характерных для процесса перевозки сырья, готового товара или персонала:

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

Анализу подвергаются такие аспекты транспортной системы предприятия:

• способ перемещения грузов;
• выбор типа транспортного средства и его конкретной модели;
• подбор компании-перевозчика и прочих логистических посредников;
• схема расположения складских терминалов компании.

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

Приоритетные задачи, которые должны быть решены в ходе оптимизации процессов транспорта:

• развитие МТБ предприятия. Основной упор нужно делать на максимальную автоматизацию трудоемкой работы;
• своевременное обновление и капитальное обслуживание парка транспортных средств;
• внедрение автоматизированных логистических систем, способных предоставлять сводные данные обо всех перевозках за требуемый период. И также система должна предоставлять детализацию по каждой отдельной поездке.

В рамках «оздоровления» логистического направления предприятия нужно придерживаться таких мер, которые не скажутся на безопасности груза или пассажиров, соблюдении времени прибытия-отбытия, увеличении времени простоя на этапе погрузки/разгрузки.

Как оптимизировать транспортную работу предприятия

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

1. Выбор оптимальных ТС: эксплуатационные характеристики транспортного средства формируют уровень затрат на транспорт. Важно, чтобы в парке компании были негабаритные модели для перевозок в пределах населенного пункта;
2. Подбор оптимально расположенных разгрузочно-погрузочных пунктов: склады нужно анализировать не только по уровню удобства подъезда/погрузки, но и по степени удаленности поставщиков;
3. Анализ целесообразности владения собственным парком ТС: этот аспект актуален для субъектов малого бизнеса. Логистическое подразделение должно сопоставить затраты на владение собственным парком с расценками на услуги транспортных фирм.

После анализа приоритетных направлений логистики предприятия нужно инициировать разработку плана оптимизации транспортных расходов на предприятии. Этот план имеет, как правило, общую конфигурацию вне зависимости от типа предприятия:

1. Постановка задачи перед группой менеджеров логистического отдела;
2. Координация межведомственной работы, издание директив и регламентов, регулирующих взаимодействие между подразделениями;
3. Внедрение единых показателей эффективности работы для отделов, связанных с логистикой;
4. Привлечение топ-менеджмента для эффективной коммуникации между отделами и формирования отчетной документации;
5. Делегирование полномочий, назначение группы работников, отвечающих за достижение плановых показателей.

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

Основные методы снижения транспортных расходов

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

Например, широко используются такие методы оптимизации транспортных процессов:

1. «Метод северо-западного угла»: используется для решения исключительно транспортных задач. Транспортная таблица перебирается от самого левого столбца верхней строки. В таблицу вписываются максимальные значения, при которых не будут превышены возможности поставщика и потребности покупателя. Описываемый метод не принимает в расчет такой ключевой фактор, как стоимость доставки;
2. «Метод Фогеля»: по этому методу для каждого столбца ТТ(транспортной таблицы) нужно вычислить разницу между двумя наименьшими тарифами;
3. Метод минимальных затрат: логист записывает отгрузку в те ячейки, которые имеет наименьший тариф на перевозку.

Данные методы реализованы в рамках CRM-системы «1С: Предприятие». Расчет транспортных задач можно вести в автоматическом режиме, активируя различные подстройки в программной оболочке.

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

Использование автоматизированных логистических систем

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

Такое ПО должно иметь следующий функционал:

• обработка заявок на перевозку;
• подбор транспортного средства с учетом характеристик груза;
• формирование ТТН , иной сопроводительной документации;
• расчет стоимости перевозку.

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

Оптимизация транспортного отдела предприятия – важнейшая задача корпоративного менеджмента, так как от этого направления зависит коммуникация с поставщиками, партнерами и конечными потребителями. Нельзя придерживаться одного аспекта совершенствования перевозок – нужно вводить инновации комплексно. Современное ПО позволяет нивелировать долю человеческого участия в моделировании перевозок, поэтому менеджмент должен быть задействован в обновлении МТБ предприятия, формировании отчетности и разработке предложений по дальнейшему совершенствованию логистики.

Математическая модель оптимизации транспортных перевозок (транспортная задача)

Принцип выбора теоретических вопросов: 1 вопрос по последней цифре зачётки, 2 вопрос – к последней цифре зачётки прибавляется 10.

1. Функции и принципы построения транспортно-логистической системы предприятия.

2. Структурно-функциональные связи транспортного отдела с другими отделами предприятия.

3. Транспортно–распределительные комплексы. Логистическая концепция “just-in-time” в транспортировке.

4. Нормативно-правовые акты, регламентирующие внутренние перевозки грузов.

5. Нормативные документы, регламентирующие взаимоотношения стран в международных перевозках грузов.

6. Обязанности и ответственность экспедитора и агента мультимодальных перевозок.

7. Основные виды транспорта (морской, речной, авиационный, железнодорожный, автомобильный, смешанный). Условия транспортировки, хранения. Основные типы транспортных средств.

8. Экономическая целесообразность доставки товара различными видами транспорта. Управление и организация внутренних и внешних перевозок грузов различными видами транспорта.

9. Сроки и тарифы. Отслеживание груза. Документация. Порядок расчётов. Международные конвенции и соглашения в области перевозок грузов различными видами транспорта.

10. Выбор перевозчика или оператора транспортировки.

11. Перевозчик: преимущества и недостатки.

12. Экспедитор: определение, классификация по виду оказываемых услуг, преимущества и недостатки.

13. Методы и критерии, влияющие на выбор перевозчика/оператора. Принципы ценообразования в зависимости от способа транспортировки.

14. Внешнеторговые операции и экспортно–импортные контракты.

15. Виды, структура, содержание, порядок оформления экспортно-импортных контрактов.

16. Транспортные аспекты контракта купли-продажи. Особенности выбора базисных условий поставки в договоре купли–продажи. Франко-условия.

17. Термины группы EFCD, международные торговые правила. Условия поставки ИНКОТЕРМС. Общий обзор

18. Таможенная очистка товара.

19. Стоимость товара при таможенной очистке: порядок расчета. Методы определения и корректировка таможенной стоимости товара.

20. Алгоритм расчета таможенных платежей в ГТД. Таможенный брокер–логистический посредник в ВЭД.

21. Расчет фактической стоимости товара.

22. Аудит товароматериальных ценностей при доставке товара.

Математическая модель оптимизации транспортных перевозок (транспортная задача)

Стандартная задача оптимизации транспортных перевозок (транспортная задача) определяется как задача разработки наиболееэкономичного плана перевозки продукции одного вида из нескольких пунктовотправления в пункты назначения. При этом величина транспортных расходовпрямо пропорциональна объему перевозимой продукции и задается с помощьютарифов на перевозку единицы продукции.

Транспортная задача ставится следующим образом: имеется m пунктов отправления А₁, А₂, …, А_m, вкоторых сосредоточены запасы какой-либо однородной продукции в количестве соответственно а₁, а₂, …, а_mединиц. Имеется n пунктов назначения B₁, B₂, …,B_n, где имеется спрос на указанную продукцию соответственно на b₁, b₂, …, b_n единиц. Переменные х_ij– количество продукции, перевозимой из пункта отправления A_i в пункт назначения B_j. Известны стоимости C_ij перевозки единицы груза от каждого пункта отправления А_i до каждогопункта назначения B_j. Требуется составитьтакой план перевозок (откуда, куда и сколько единиц груза перевести), чтобы все заявки были выполнены, аобщая стоимость всех перевозок была минимальна.

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

. , (1)

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

1. По количеству перевозимой продукции от поставщика к потребителям:

, (2)

, (3)

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

Тогда целевая функция задачи – минимальные транспортные расходы на перевозку всей продукции L (х) будет иметь вид:

, (4)

Совокупность выражений (1-4), представляет собой математическую модель транспортной задачи.

В случае, когда суммарные запасы превышают суммарные потребности (вариант открытой транспортной задачи), то есть

,

следует ввести фиктивного потребителя, который будет условно потреблять излишки продукции

, (5)

а цена перевозки ему товара от любого поставщика будет равна нулю.

В том случае, когда суммарные запасы меньше суммарных потребностей (вариант открытой транспортной задачи), то есть

,

следует ввести фиктивного поставщика, который условно будет восполнять недостаток продукции в количестве

, (6)

а цена перевозки от него к любому потребителю также будет равна нулю.

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

. (7)

В случае, когда требуется ограничить перевозки от поставщика с номеромl к потребителю с номером k на каком либо уровне. Возможны ограничения двух типов: 1) x_lk≥a; 2) x_lk≤b, где a и b – постоянные величины.

Случай 1. Если x_lk≥a, то необходимо прежде, чем решать задачу, сократить запасы l-го поставщика и запросы k-го потребителя на величину а (зарезервировать перевозку некоторого количества продукции x_lk≥a). После решения задачи в оптимальном решении следует увеличить объем перевозки x_lk на величину a.

Случай 2. Если x_lk≤ b, то необходимо вместо k-го потребителя с запросами b_k ввести двух других потребителей. Один из них с номером k должен иметь запросы b_k = b, а другой с номером n + 1 – запросы b_n+1 =b_k – b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c_l(n+1), для которой используется запрещающий тариф (формула (7). После получения оптимального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как c_l(n+1) = – самая большая стоимость перевозки, то в оптимальном решении переменная x _l(n+1) = 0 и объем перевозки x_lk не превзойдет b.

Пример 1.Необходимо организовать перевозку муки с трех складов в три хлебопекарни, исходные данные приведены в табл. 1, при дополнительных условиях: временно запрещена перевозка от 1-го поставщика к 3-му потребителю, объем перевозки груза от l-го поставщика 2-му потребителю должен быть неменее 100 единиц (x₁₂≥ 100), а от 3-го 1-му не более 200 единиц (x₃₁≤ 200). Требуется так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

Таблица 1 – Исходные данные для решения транспортной задачи.

Поставщик	Потребитель (хлебопекарня)
№ склада	Запасы продукции на складах, ед.	№1	№2	№3
Стоимость перевозок продукции от поставщиков к потребителям, руб.
Потребность в продукции, ед.

Решение примера 1.

1. Определим ограничения для переменных.

1.1 Для запрета перевозок от 1-го поставщика к 3-му потребителю введем запрещающий тариф в размере с₁₃=1000 руб.

1.2Для того чтобы в оптимальном решении объем перевозки x₁₂ от l-го поставщика 2-му потребителю был не менее 100 единиц (х₁₂≥100), при решении задачи будем предполагать, что запасы 1-го поставщика а₁ и запросы 2-го потребителя b₂ меньше фактических на 100 единиц, то есть 100 ед. и 320 ед. соответственно. После получения оптимального решения объем перевозки x₁₂увеличим на 100 единиц.

1.3Для того чтобы объем перевозки х₃₁от 3-го поставщика 1-му потребителю был не более 200 единиц(x₃₁≤ 200), вместо 1-го потребителя введем двух других.Один из них под прежним первым номером имеет запасы b₁ = 200 единиц и прежние стоимости перевозок единиц груза. Другому потребителю присвоим четвертый номер. Его запросы равны b₄ = 500 – 200 = 300 единиц истоимости перевозок единиц груза те же, что и у 1-го потребителя. Для стоимости перевозок с₃₄ введем запрещающий тариф с₃₄=1000 руб. После нахождения оптимального решения задачиобъемы перевозок для 4-го потребителя необходимо прибавить к соответствующим объемам перевозокдля 1-го потребителя.

В результате преобразований таблица будет иметь вид (табл.2).

Таблица 2– Промежуточные данные к транспортной задаче

Поставщик	Потребитель (хлебопекарня)
№ склада	Запасы, ед.	№1	№2	№3	№4
Потребность, ед.

1.4Проверяем выполнение необходимогои достаточного условия существования решения задачи (формула (1)). Находим суммарные запасы поставщиков и запросы потребителей:

Задача с неправильным балансом. Вводим фиктивного поставщика, которому присвоим номер четыре (склад №4) с запасами а₄ = 1050 – 900 = 150 ед.

Стоимость перевозок от поставщика с фиктивного склада №4 к любому потребителю будет равна нулю.

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

Таблица 3 – Итоговая таблица исходных данных

Поставщик (склады)	Потребитель (хлебопекарня)
№ склада	Запасы, ед.	№1	№2	№3	№1*
Потребность, ед.

2. Для нахождения переменных и целевой функции используем пакет «Принятие решений» редактора электронных таблиц MSExcel.

3. Запустить табличный процессор MS Excel.

4. Открыть книгу MS Excel с именем «Моделирование».

5. Лист 2 переименовать в лист с названием Транспортная задача. Двойной щелчок левой кнопкой мыши (ЛКП) по имени листа Лист 2 и ввести новое имя.

6. На рабочем листе Транспортная задача ввести исходные данные согласно табл.1 (рис. 1). Введите в диапазон D4:G7стоимости перевозок.

7. Отведите под неизвестные объемы перевозок – переменные х_ij, диапазон ячеек D12:G15 (рис.2).

8. Введите в ячейки диапазона I12:I15 заданное количество муки на складах у поставщиков. В ячейки диапазона D17:G17 введите потребность в муке у потребителей.

9. В ячейку D19 введите формулу для расчета целевой функции, которая соответствует формуле (29) =СУММПРОИЗВ(D4:G7;D12:G15).

Рис.1. Рабочий лист «Транспортная задача».

10. Введите ограничения согласно рисунку 1, таблице 3 и в соответствии с математической моделью задачи (формулы (1–3)), вычисляющие объемы запасов муки у поставщиков и объемы спроса на неё у потребителей (табл.4).

Таблица 4 –Формулы рабочего листа Примера 1

Адрес ячейки	Формула	Адрес ячейки	Формула
H12	=СУММ(D12:G12)	D16	=СУММ(D12:D15)
H13	=СУММ(D13:G13)	E16	=СУММ(E12:E15)
H14	=СУММ(D14:G14)	F16	=СУММ(F12:F15)
H15	=СУММ(D14:G14)	G16	=СУММ(G12:G15)

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

11. Выбрать пункт меню СервисðПоиск решения. Заполните поля в диалоговом окне Поиск решения,в соответствиис (рис.46), установите параметры решения задачи, запустите задачу на решение, выполните анализ решения на чувствительность (рис.3).

12. Для того чтобы решение приняло окончательный вид объем перевозок x₁₂ от 1-го поставщика 2-му потребителю и увеличим на 100 единиц, суммируем соответствующие объемы перевозок 1-го потребителя и 4-го потребителя. Также исключим из решения объемы перевозок от фиктивного 4-го поставщика. При этом значение целевой функции изменится. Итоговое решение представлено в таблице 5.

Рис.2. Диалоговое окно «Поиск решения» транспортной задачи.

Рис.3. Результаты поиска решения транспортной задачи.

Таблица 5 – Итоговые результаты поиска оптимальных объемов перевозок в транспортной задаче.

Склады	Запасы продукции на складах, ед. (заданные в табл. 1)	Хлебопекарни
№1	№2	№3
№1
№2
№3
Потребность в продукции, ед. (заданная табл.1)

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

Транспортная задача

11.05.2017, 17:39

Задача линейного программирования, транспортная задача
Всем привет. сижу на экзамене, помогите пожалуйста решить,сроно. заранее спасибо.

Транспортная задача
Тут человек искал решение транспортной задачи в теме.

Транспортная задача
Поставщики товара – оптовые коммерческие предприятия имеют запасы товаров соответственно в.

Транспортная задача
Условие: Найти в кировоградской области точку( населённый пункт ), от которого до всех остальных.

Транспортная задача
Я решаю закрытую транспортную задачу в условии уже есть значение потенциалов. Необходимо расписать.

11.05.2017, 22:112

Могу вам разве что ответ написать:
I этап:
на А1 доставить 18 тонн, из которых 15 тонн уйдёт к В4 и 3 тонны к В5
на А2 доставить 13 тонны, из которых 13 тонн уйдёт к В1 и 19 тонн к В3
на А3 доставить 99 тонн, из которых 18 тонн уйдёт к В2 и 41 тонна к В3, на складе останется 40 тонн до II этапа
Стоимость I этапа 660 ДЕ.

II этап:
на А1 доставить 50 тонн, из которых 45 тонн уйдёт к В4 и 5 тонн к В5
на А2 доставить 23 тонны, из которых 15 тонн уйдёт к В1 и 8 тонн к В4
на А3 доставить 57 тонн, из которых (сложить с 40 тоннами, оставшимися от I этапа) 61 тонна уйдёт к В2, на складе останется 36 тонн.
Стоимость II этапа 962 ДЕ.
Суммарная стоимость двух этапов 1622 ДЕ.

Этапы независимые – нужно сделать оптимальный план для I этапа, результат плана (сколько останется на каждом складе после него) известен: 0 , 0 и 40 тонн. Дальше точно так же делается II этап.

Ошибся, синие числа – уже исправленные.

11.05.2017, 23:25313.05.2017, 14:56 [ТС]413.05.2017, 15:15513.05.2017, 19:22613.05.2017, 22:23 [ТС]7

Во вложении, продублирую:
На строительство магистрали периодически доставляются материалы, которые со станции же-
лезной дороги вначале поступают на 3 промежуточных склада, а затем непосредственно к 5
объектам магистрали. Два первых склада А1, А2 имеют ограниченную емкость 50 т, и поступив-
шие на них грузы расходуются полностью. С учетом направлеления строительства магистрали
последний склад А3 с неограниченной емкостью допускает резервирование грузов от периода
к периоду. Транспортные расходы (в условных денежных единицах — ДЕ) на перевозку од-
ной тонны груза со станции на промежуточные склады составляют 4, 2, 3 ДЕ, а со складов к
объектам В1–В5 представлены в табл. 1; там же приведены потребности объектов (в тоннах) в
течение двух периодов.
таблица:
-|B1|B2|B3|B4|B5
A1|4|15|15|4|4
A2|4|12|12|13|14
A3|8|1|3|14|13
1период|13|18|41|15|3
2период|15|61|0|53|5
Рассматривается работа системы в течение двух периодов при условии доставки на станцию
по 130 т груза в каждый из периодов.

Пока думаю перевозки от станции до склада как подзадача, найти таким образом стоимость этих перевозок и объем материалов, которые будут храниться на станции. Возможно я себе усложняю жизнь. По ограничениям думаю так:
, т к на первые два склада нельзя привезти больше материала, чем по 50 тонн каждый. Для третьего склада – раз допускается резервирование и емкость не ограничена, то исходя из потребностей в течение двух периодов , и при этом . Как учесть цены на перевозки от жд станции с учётом того, что часть товара остаётся на складе А3? Хороший вопрос.

Решение транспортной задачи в Excel с примером и описанием

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

Планирование перевозок с помощью математических и вычислительных методов дает хороший экономический эффект.

Виды транспортных задач

Условия и ограничения транспортной задачи достаточно обширны и разнообразны. Поэтому для ее решения разработаны специальные методы. С помощью любого из них можно найти опорное решение. А впоследствии улучшить его и получить оптимальный вариант.

Условия транспортной задачи можно представить двумя способами:

В процессе решения могут быть ограничения (либо задача решается без них).

По характеру условий различают следующие типы транспортных задач:

• открытые открытые транспортные задачи (запас товара у поставщика не совпадает с потребностью в товаре у потребителя);
• закрытые (суммарные запасы продукции у поставщиков и потребителей совпадают).

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

Пример решения транспортной задачи в Excel

Предприятия А1, А2, А3 и А4 производят однородную продукцию а1, а2, а3 и а4, соответственно. В условных единицах – 246, 186, 196 и 197. Затем товар поступает в пять пунктов назначения: В1, В2, В3, В4 и В5. Это потребители продукции. Они готовы ежедневно принимать 136, 171, 71, 261 и 186 единиц товара.

Стоимость перевозки единицы продукции с учетом удаленности от пункта назначения:

Производители	Потребители					Объем производства
В1	В2	В3	В4	В5
А1	4,2	4	3,35	5	4,65	246
А2	4	3,85	3,5	4,9	4,55	186
А3	4,75	3,5	3,4	4,5	4,4	196
А4	5	3	3,1	5,1	4,4	197
Объем потребления	136	171	71	261	186

Задача: минимизировать транспортные расходы по перевозке продукции.

1. Проверим, является ли модель транспортной задачи сбалансированной. Для этого все количество производимого товара сравним с суммарным объемом потребности в продукции: 246 + 186 + 196 + 197 = 136 + 171 + 71 + 261 + 186. Вывод – модель сбалансированная.
2. Сформулируем ограничения: объем перевозимой продукции не может быть отрицательным и весь товар должен быть доставлен к пунктам назначения (т.к. модель сбалансированная).
3. Введем стоимость перевозки единицы продукции в рабочие ячейки Excel.
4. Введем формулы для расчета суммарной потребности в товаре. Это будет первое ограничение.
5. Введем формулы для расчета суммарного объема производства. Это будет второе ограничение.
6. Вносим известные значения потребности в товаре и объема производства.
7. Вводим формулу целевой функции СУММПРОИЗВ(B3:F6; B9:F12), где первый массив (B3:F6) – стоимость единицы перевозки товаров. Второй (B9:F12) – искомые значения транспортных расходов.
8. Вызываем команду «Поиск решения» на закладке «Данные» (если там нет данного инструмента, то его нужно подключить в настройках Excel, а как это сделать описано в статье: расширенные возможности финансового анализа). Заполняем диалоговое окно. В графе «Установить целевую ячейку» – ссылка на целевую функцию. Ставим галочку «Равной минимальному значению». В поле «Изменяя ячейки» – массив искомых критериев. В поле «Ограничения»: искомый массив >=0, целые числа; «ограничение 1» = объему потребностей; «ограничение 2» = объему производства.
9. Нажимаем «Выполнить». Команда подберет оптимальные переменные при заданных ограничениях.

Так выглядит «сырой» вариант работы инструмента. Экспериментируя с полученными данными, находим подходящие значения.

Решение открытой транспортной задачи в Excel

При таком типе возможны два варианта развития событий:

• суммарный объем производства превышает суммарную потребность в товаре;
• суммарная потребность больше суммы запасов.

Открытую транспортную задачу приводят к закрытому типу. В первом случае вводят фиктивного потребителя. Его потребности равны разнице всего объема производства и суммы существующих потребностей.

Во втором случае вводят фиктивного поставщика. Объем его производства равен разнице суммарной потребности и суммарных запасов.

Единица перевозки груза для фиктивного участника равняется 0.

Когда все преобразования выполнены, транспортная задача становится закрытой и решается обычным способом.