Транспортные задачи в логистике
Существует ряд классических методов, применяемых для решения задач транспортной логистики.
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).
Рис. 23. Графический вид транспортной задачи
i – поставщик; j –потребитель; n – количество поставщиков; m – количество потребителей; ai – запас на поставку; bj – потребность в поставке; xij – партия поставки; cij – стоимость доставки; B – базисная клетка; pij – потенциал поставки (клетки); ui – потенциал поставщика (строки); vj – потенциал потребителя (столбца).