Транспортные задачи в логистике

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

1. Задача о ранце. Здесь речь идет о собравшемся в поход путешественнике, который должен упаковать в ранец различные полезные предметы n наименований, причем может потребоваться несколько одинаковых предметов. Имеется m ограничений такого типа, как вес, объем, линейные размеры и т. д. При формулировке задачи в строительстве место ранца может занять кузов автомобиля, длинновоза и пр.

2. Задача о коммивояжере. Имеются объекты, пронумерованные числами 0,1,2, … n. Выехав из базы, коммивояжер должен объехать все объекты, побывав в каждом из них по одному разу и вернуться на базу. Известны расстояния Cij между объектами, требуется найти самый короткой маршрут. Применение этой задачи необходимо, когда существует большая разница в расстояниях, например при строительстве объектов в разных городах области. На основе задачи коммивояжера составляют кольцевые и маятниковые маршруты доставки строительных материалов.

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

4. Задача о назначениях. Имеется n однотипных конструкций, которые требуется распределить между m объектами. Известно, что для доставки на j-й объект требуется доставить i-е количество конструкций, причем стоимость доставки равна – Cij Требуется расставить маршруты таким образом, чтобы расходы на доставку были минимальными. Чаще всего задача о назначениях решается при обеспечении строительства крупногабаритными материалами, количество которых при разовой поставке ограничено возможностями транспортных средств.

Общепринято задачу о назначениях называть транспортной задачей.

Транспортная задача – это задача прикрепления поставщика к потребителям. Рассмотрим условия задачи.

Математическая модель этой задачи такова:

∑∑хij, cij → min. (8.1)

Имеется m поставщиков определенного вида продукции. Максимальные объемы возможных поставок заданы и равны Аi при i = 1,2, …, m. Эта продукция используется n потребителями. Объемы потребностей заданы и равны Вj при j = 1,2, … n. Стоимость перевозок единицы продукции от поставщика к потребителю известна и равна Cij. Требуется установить такие объемы перевозок Хij от каждого поставщика к потребителю, чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были бы удовлетворены (рис. 23).

сij
сij
сij
сij
сij
сij
cij
сij
сij
xij
xij
xij
xij
xij
xij
ai
xij,pij
xij
xij
ai
ai
bj
bj
bj
ui
ui
ui
vi
vi
vi
j
i
i
n
j
m
Потреб
Постав

Рис. 23. Графический вид транспортной задачи

i – поставщик; j –потребитель; n – количество поставщиков; m – количество потребителей; ai – запас на поставку; bj – потребность в поставке; xij – партия поставки; cij – стоимость доставки; B – базисная клетка; pij – потенциал поставки (клетки); ui – потенциал поставщика (строки); vj – потенциал потребителя (столбца).

Наши рекомендации