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

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

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

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

Например, у нас есть сеть розничных магазинов, которым требуется определенное количество товаров. Также имеется ряд складов поставщиков, где требуемые товары хранятся. При этом на каждом складе различный объем запасов этих товаров. Кроме этого нам известны тарифы – затраты на перевозку 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 < 0), и его следует улучшить путем перераспределения поставок.

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. Построение графа перевозок 

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

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

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

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

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

Галяутдинов Р.Р.

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

Еще можно почитать:

Источник: http://galyautdinov.ru/post/transportnaya-zadacha

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

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

Изучение того, какие ставятся задачи для такой деятельности в организации, позволяет не путаться в понятиях и вести эффективную хозяйственную деятельность.


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

Что это такое

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


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

 Использует на практике сейчас – и то и другое.

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

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

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

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

Переменными в решении таких задач являются пункты – от точки поставщика к точке потребителя (клиента).

Главной целью решения таких задач является снижение затрат и максимальная оптимизация грузоперевозочной транспортной деятельности предприятия.

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

Какие проблемы решает

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

  1. Как определить оптимальность маршрутов?
  2. Насколько можно максимально наметить короткие пути для доставки груза?
  3. На чем, как и где можно сэкономить?
  4. Как распорядиться ведением хозяйственной деятельности и контроля маршрутов, если диспетчера нет на месте или диспетчер – новичок в работе? И другие вопросы.

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

  1. В некоторых случаях ограничение количества тары, а также размеров грузоперевозочных машин.
  2. Сведение к минимуму перепогрузок с одного транспортного средства в другое, из одной тары для транспортировки в другую.
  3. Организация удобства погрузочных или разгрузочных работ в самом кузове грузовика.
  4. Автоматизация маркировки грузов либо полное исключение такового освобождает процесс доставки от затягивания сроков перевозки.
  5. Укрупнения количества единиц или самого груза в целом по машине, с механизацией разгрузки на месте у заказчика.
  6. Учет типа машины для лучшей грузовместимости.
  7. Добиться того, чтобы грузы имели одинаковый размер от заказа к заказу.
  8. Сделать частоту поставок больше, при этом не увеличивать стоимость единицы груза, который перевозится.
  9. Снижение затрат на процесс упаковки перевозимого товара вместе с тем, чтобы максимально сохранить его целостность в процессе перемещения из одной точки в другую.
  10. Стандартизация подбора типов машин под каждый заказ, его размер.
  11. Быстро определить, какие поставки клиентам максимальные, а какие – минимальные.
  12. Сведение к минимуму затрат на перевозку бракованного товара, возвратной продукции.
  13. Путем системы распределения сократить брак, возникающий в процессе перевозок.
  14. Снизить величину времени, затрачиваемую на каждый транзит груза.
  15. Уменьшение времени, затрачиваемого на каждый простой, который происходит по естественным причинам – загрузка/разгрузка.
  16. Сведение к минимуму затрат, что приходятся на доставку груза клиенту.
  17. Сделать равномерным поток движения грузовых поставок. Особенно это касается сезонной специфики.
  18. Если речь идет о партиях поставок, тогда желательно использовать минимум количества машин, задействованных для этих целей.
  19. Сортировка грузов таким образом, чтобы максимально его вместить в машину.
  20. Снижение времени, затрачиваемого на поступление и получение той или иной информации касательно грузов, заявок на поставку и самой транспортировки. Например:
    • сведения о простое;
    • оперативная информация о месте нахождения грузовиков;
    • когда прибыла машина в пункт назначения (время указывается с точностью до секунд);
    • своевременное сообщение диспетчеру о поломках в пути или иных возникших препятствиях к благополучному прибытию в пункт назначения и другое.

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

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

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

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

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

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

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

Однако эвристика лишена гибкости, а потому ее современные логисты еще дорабатывают. Одно, несомненно – за данным методом явно видится будущее для наиболее эффективного транспортного перемещения.

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

  1. Исследование операций.
  2. Линейное математическое программирование (ЛП):
    • применение линейных уравнений при расчетах – линейной функцией от элементов путей решения является целевая (эффективная) функция L (х);
    • линейные равенства/неравенства представляют собой ограничительные условия для возможных решений;
    • целевой функцией является самое большее ил меньшее значение, которое ищут в математическом программировании, учитывая ограничения;
    • ограничения могут встречаться строгими (ровно столько и никак иначе) и нестрогими (не более или не менее какого-то ориентировочного значения).
  3. Техника северо-западных углов (эвристика).
  4. Методика мини-тарификации (эвристика).
  5. Метод Фогеля (эвристика).
  6. Способ коммивояжера.
  7. Применение алгоритма Свира (или еще как говорят – «дворника-очистителя», задачи решаются нематематической эвристикой).

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

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

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

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

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

Коэффициент будет равняться разности тарифов (двух самых минимальных), которые имеются в строке или столбце. Распределение коэффициентов следует по принципу «от наибольшего к наименьшему».

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

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

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

Как организована на предприятии

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

  1. Организация координационного отдела или постановка задачи перед одним сотрудником-координатором (чаще всего таковым является начальник или менеджер логистического отдела).
  2. Смежная работа между отделами, издание соответствующих распоряжений и приказов и иное взаимодействие между отделами.
  3. Совместное планирование маршрутов, согласование и реализация этих планов, построение графиков между отделами или подразделениями.
  4. Установка между операциями единых показателей таким образом, чтобы достичь более функциональной работы.
  5. При необходимости привлекается руководство для налаживания связей между подразделениями, отделами предприятия.
  6. Обязанности между отделами и сотрудниками должны быть четко разделены.
  7. Если возникают какие-либо споры, тогда должны быть обозначены те лица, которые будут уполномочены принимать окончательные решения.
  8. Организовать единое информационное поле, которое бы показывало состояние маршрутов и грузоперевозок.

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

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

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

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

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

: О программе оптимизации транспортной логистики

Источник: http://avtourist-DTP.ru/reshenie-zadach-po-optimizacii-transpo/

Как решить транспортную задачу?

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

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

Транспортная задача — это математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение

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

Ну, начнем! Далее Вводная часть, с которой желательно ознакомиться.

Вводная часть, с которой желательно ознакомиться

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

  • решение транспортной задачи методом потенциалов (рассмотрен в данной статье)
  • решение транспортной задачи с использованием симплекс метода.

Решение задачи методом потенциалов происходит в несколько этапов:

  1. Определение опорного решения.
  2. Применение к найденному опорному решению самого метода потенциалов.
  3. Проверка единственности решения.

Определение опорного плана, в свою очередь, можно выполнить несколькими способами. Мы рассмотрим два из них:

  • метод северо-западного угла
  • метод минимальных стоимостей

(не путать с методами решения самой транспортной задачи!!!)

О чем говорится в определении транспортной задачи?

У нас есть некоторый груз, который находится на складах: склад 1, склад 2, …, склад  — это пункты отправления.

Этот груз нам необходимо развести по магазинам: магазин 1, магазин 2, …, магазин k — это пункты назначения.

Нам выгоднее как можно эффективнее выполнить работу, т.е. найти такой вариант перевозки, при котором затраты будут минимальными.

Рассмотрим пример решения транспортной задачи подробно. 

Транспортная задача задается следующей таблицей:  

Что означают числа в условии транспортной задачи?

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

Это наши «склады» — пункты отправления: два склада с товаром: А1 и А2

Это объем товара — количество груза, соответственно на складах А1 и А2:

Далее имеем дело с пунктами назначения — с «магазинами». В нашем случае их 4 штуки: В1, В2, В3 и В4.

И соответственно потребности каждого из магазинов — потребности пунктов назначения:

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

Например, для перевозки 1 единицы груза из пункта отправления («склада») А2 в пункт назначения («магазин») В3 надо заплатить 4 условные единицы стоимости, например 4 руб.

Аналогично, мы заплатим 6 рублей за перевозку 1 единицы груза из «склада» А1 в «магазин» В4. 

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

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

Рассмотрим самый распространенный метод получения опорного плана — метод северо-западного угла

Называется он так потому, что заполнение таблицы начинается с самой верхней левой (северо-западной) ячейки. 

Перед тем, как распределять ресурсы по «магазинам», проверим, равны ли общие потребности имеющимся ресурсам?

Потребности:  50 + 100 + 75 + 75 = 300

Ресурсы:        100 + 200 = 300

Потребности = Ресурсам

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

Начнем нахождение опорного решения:

Заполним клетку (1;1).

В магазин В1 требуется 50 единиц товара. Со склада А1 отправим в этот магазин 50 единиц.

Потребности магазина В1 выполнены, следовательно, нет необходимости везти туда груз со склада А2. 

На складе А1 еще осталось 50 единиц груза. Эти остатки можем направить в магазин В2. Ресурсы склада А1 исчерпаны. 

Переходим к складу А2. 

Так как потребности магазина В1 выполнены полностью, рассмотрим магазин В2, которому требуется 100-50=50 единиц товара. Направим их туда.

Заметим, на складе А2 осталось еще 200-50=150 единиц груза, которые мы распределим по магазинам В3 и В4, полностью удовлетворяя и их потребности. 

Склады пусты! 

Потребности магазинов в товаре полностью выполнены! 

Получен опорный (первоначальный) план транспортной задачи. 

Рассмотрели северо-западный метод построения первоначального плана (опорного решения).

Метод минимальных стоимостей получения опорного плана

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

Направляем 100 единиц груза из склада А2 в магазин В2.

Остатки на складе А2 — 100 единиц. Потребности магазина В2 выполнены.

Груз со склада А2 отправим в магазин, у которого стоимость перевозки ниже — магазин В3, так как  мин(4;7)=4 

Размер поставки равен потребности магазина — 75. Остатки со склада 200-100-75=25 перенесем  в магазин В4.

Остается только раскидать груз со склада А1 по магазинам: В1 — 50 единиц, В4 —  75-25=50 единиц.

Получили два опорных плана: методом северо-западного угла и методом минимальных стоимостей.

Первый опорный план (по методу северо-западного угла):

Второй опорный план (по методу минимальных стоимостей):

Проверка правильности вычисления первоначального плана

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

Количество заполненных клеток (базисных клеток) в первоначальном плане ВСЕГДА должно быть равно m + n — 1, где m — количество строк, n — количество столбцов

В нашем случае условие выполняется: 2 + 4 — 1 = 5

Что же делать, если количество заполненных ячеек меньше необходимого?

Подробно об этом с разбором примеров в статье Вырожденность опорного плана транспортной задачи. Как избавиться?

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

100 = 50 + 50

200 = 100 + 75 + 25

По столбцам:

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

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

Метод потенциалов решения транспортной задачи — шаг 1

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

Выпишем матрицу стоимостей, данную в условии задачи.

Далее строим рядом две таблицы. Размерность таблиц как и в матрице стоимостей:

количество строк = количеству складов, количество столбцов = количеству магазинов. 

Заполняем первую — левую таблицу в соответствии с полученным опорным планом.

Переходим в правую таблицу.

Переносим из матрицы стоимостей значения, которые соответствуют занятым клеткам левой таблицы.

В матрице стоимости эти значения подчеркнуты. 

Припишем каждой строке правой таблице потенциалы u1, u2. Каждому столбцу — потенциалы v1, v2, v3, v4.

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

Мы будем определять значения потенциалов непосредственно из правой таблицы.  

Составим систему уравнений по следующему правилу: 

Каждое из значений в ячейке (правая таблица) равно сумме потенциалов соответствующей строки и соответствующего столбца. 

Например: значение 4 находится в 1-й строке и 1-м столбце. Тогда сумма потенциалов 1-й строки (u1) и 1-ого столбца(v1) равна 4.

Первое уравнение системы: u1 + v1 = 4 

Рассмотрим следующее значение таблицы.  

Значение 3 находится в первой строке (потенциал u1), втором столбце (потенциал v2). 

Второе уравнение системы: u1 + v2 = 3

Аналогично для каждого значения таблицы составим уравнение.

Получим систему уравнений:

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

Для удобства в качестве этого потенциала всегда будем брать v4. 

Тогда система уравнений будет выглядеть: 

Решим систему уравнений и получим значения потенциалов:

Наглядно:

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

Покажем подробно:

Сумма отмеченных потенциалов равна 7, следовательно, потенциал u2 = 7

Значение 4 базисной ячейки находится во 2-й строке, 3-м столбце, тогда рассмотрим сумму соответствующих потенциалов.

v3 + 7 = 4 откуда v3 = -3

Далее все аналогично:

Значение 2 равно сумме потенциалов 2-й строки и 2-го столбца:

2 = v2 + 7 откуда v2 = -5

u1 — 5 = 3, откуда u1 = 8

v1 + 8 = 4, откуда v1 = -4 

В итоге получили:

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

Свободные ячейки подчиняются тому же правилу суммирования потенциалов.

Вычислим оценочную матрицу, по которой узнаем, оптимален ли рассматриваемый план.

Из каждого элемента матрицы стоимостей вычтем соответствующий элемент правой таблицы: 

 —  = 

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

если в оценочной матрице нет отрицательных элементов, то решение оптимально, в противном случае решение не оптимально. 

Согласно критерию оптимальности, решение выше не оптимально, так как в оценочной таблице присутствует отрицательное значение.

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

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

Для перехода к следующему опорному решению выполним следующее (построим цикл пересчета):

— найдем среди отрицательных значений оценочной матрицы максимальный по модулю (или по другому, минимальный среди отрицательных) 

— в соответствующей ячейке левой таблицы ставим знак » + «

В нашем примере наименьшее отрицательное значение -2.

Знак » + » ставим в ячейке 1-й строки, 4-го столбца левой таблицы — ячейка соответствующая значению (-2).

Необходимо расставить чередующиеся значения «+ » и » — » в левой таблице так, чтобы получился замкнутый цикл и выполнялись правила:

— остальные знаки цикла (все кроме уже поставленного первого » + «) ставим только в заполненных (базисных) ячейках таблицы,

— если в строке есть «плюс» («минус»), то в этой строке должен быть и «минус» («плюс»),

— если в столбце есть » плюс» («минус»), то в этом столбце должен быть и «минус» («плюс»).

Применим к нашей таблице:

В столбце В4 есть «плюс», следовательно в этом столбце должен быть и «минус». 

Аналогично, в строке А2 есть «минус», следовательно должен быть и «плюс». 

Если мы поставим этот «плюс» в столбце В3, то цепочка порвется, так как в этом же столбце невозможно поставить «минус» — нет заполненной ячейки. 

Ставим » + » в столбце В2 и продолжаем чередовать знаки. 

Получили замкнутый цикл чередующихся знаков. Цикл пересчета найден!

Далее обратимся к ячейкам, содержащим «минусы». Среди значений этих ячеек найдем минимальное:  Δ = мин {50;75} = 50 

К  «плюсам» прибавим найденное Δ = 50, в ячейках с «минусами» — вычтем Δ = 50.

Ячейка, в которой находилось значение  Δ = 50 останется пустой. В ячейке в которой мы поставили первый плюс появится значение, равное Δ = 50.

Общее количество заполненных (базисных) ячеек при пересчете не должно изменится! 

Получили следующий опорный план: 

Вычислим стоимость перевозки на первом шаге.

Для этого найдем сумму произведений значений опорного плана и матрицы стоимостей.

S1 = 50 · 4 + 100 · 2 + 75 · 4 + 25 · 7 + 50 · 6 = 1275 

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

Общая стоимость перевозки S1 = 1275

Метод потенциалов — шаг 2

Алгоритм проверки плана на оптимальность и построение цикла пересчета очень подробно расписан в шаге 1. 

Далее решение задачи будем излагать менее детально.

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

Вычисляем потенциалы строк и столбцов:

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

Вычисляем оценочные значения в свободных ячейках.

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

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

Получили оптимальный план. Итоговая стоимость перевозки S1 = 1275

Примеры решения транспортных задач:

Закрытая транспортная задача размерностью 2х2

Закрытая транспортная задача размерностью 3х4

Закрытая транспортная задача размерностью 2х3

Закрытая транспортная задача размерностью 4х5

Источник: http://matecos.ru/mat/matematika/kak-reshit-transportnuyu-zadachu-2.html

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

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

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

  1. Затраты на погрузку/разгрузку, а также доставку товара в торговую точку.
  2. Расходы на эксплуатацию, текущий и капитальный ремонт ТС.
  3. Топливные затраты.
  4. Оплата труда водителей, механиков, экспедиторов.
  5. Уплата налогов, пошлин, таможенных сборов.
  6. Затраты на проезд по платным автодорогам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нельзя придерживаться одного аспекта совершенствования перевозок – нужно вводить инновации комплексно.

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

Источник: http://arprime.ru/optimizacia/transportnye-processy-i-rashody-predpriatia

Адвокат 24/7
Добавить комментарий