3. Транспортная логистика

З

Потр.

Потр.

Пост.

адача 3.1. В пунктах С, D и Е находятся заводы по производству кирпича, в пунктах – А и В карьеры, снабжающие их песком. Заводу С необходимо 30 т песка, заводу D– 30 т, заводу Е –30 т. Карьер А готов перевезти 40 т песка, а карьер В – 50 т. Требуется спланировать перевозки так, чтобы затраты на перевозку были минимальными, если стоимость доставки от поставщиков к потребителям известна (рис. 4).

Рис.4. Графическое изображение транспортной задачи

Р

Потр.

Пост.

ешение 3.1. Решим задачу методом потенциалов и конкретно методом северо-западного угла, то есть распределим поставки начиная с верхней левой клетки. От поставщика А запланируем поставку к потребителю С, в размере 30т., так как это минимальная величина между имеющейся и требующейся партией. Оставшиеся у поставщика А –10 т песка отправим следующему по порядку потребителю Д (следующей северо-западной клетке). Возможности поставщика А распределены, переходим к поставщику В и от него к потребителю Д отправляем требуемые 30–10 = 20 тонн. Потребителю Е запланируем поставку от поставщика В, в размере 30 т. Рис. 5. Первичное распределение (рис. 5).

Стоимость доставки при таком плане

равна 30*2 +10*3 +20*4+30*2=230 руб.

Вторым этапом проверяем план на оптимальность, с помощью потенциалов. Обнулив один любой потенциал строк или столбцов находим остальные, из условия что в базисных клетках (клетках где запланирована поставка) сумма потенциалов строки (u_i) и столбца (v_j) должна быть равна стоимости доставки (c_ij). Потенциалы клеток (p_ij) находим из того же условия, но для всех клеток. Количественные значения потенциалов указаны на рис.5.

Если во всех клетках потенциал клетки (p_ij) меньше или равен стоимости поставки (c_ij), то план оптимальный. Иначе необходимо построить новый план.

Для вторичного построения плана поставок используют алгоритм построения цикла переноса. Для этого необходимо определить перспективную клетку, то есть клетку где разница между потенциалом клетки (p_ij) и стоимостью поставки (c_ij) – максимальное положительное число (в решаемой задаче перспективной является клетка ВС). И перераспределить объемы поставки добавив в перспективную клетку некоторый объем. При добавлении поставки в перспективную клетку баланс объемов нарушится, следовательно необходимо определить базисные клетки из которых можно изъять требуемый объем, и построить замкнутый контур. Построение цикла переноса оформляется графически с помощью знака «+» при добавлении поставки и знака «–» при уменьшении объема поставки в базисной клетке. Количество «+» и «–» в любом столбце или строке должно быть о

Потр.

Потр.

Пост.

Пост.

динаковым (рис. 6).

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

Объем переноса определяется из условия возможного минимума, так что бы избежать отрицательного объема поставок практически нереализуемого. В данной задачи перераспределение производим на 20 т. материала, так как это минимальная величина в клетках со знаком «–». Результат перераспределения указывается на новом рисунке, при этом первоначально записываются условия задачи потом заполняются клетки непопавшие в цикл переноса и затем указываются перераспределенные объемы (рис. 7).

Стоимость доставки при новом плане – 10 2 +30 3 + 20 1 + 30 2 = 190 руб.

При полученном распределении, условие оптимальности выполняется.

Задача 3.2. На комбинатах ЖБК имеется 50, 40 и 70 единиц железобетонных панелей. Их необходимо доставить на объекты К, Л и М с учетом их потребностей (рис. 8).

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

Задача 3.3. Строительная подрядная компания «Монолитстрой» занимается возведением домов по адресу К, М, Н и О. С баз А и В компании необходимо доставить строительные материалы на эти объекты. Стоимость и потребность указана на рис. 9.

Постройте оптимальный план поставок двумя методами: методом северо-западного угла и методом наименьшей стоимости. Сравните результат.

Пост.

Пост.

Потр.

Потр.

Рис.8. План объемов материалов Рис.9. План объемов материалов

на комбинате ЖБК в СК «Монолитстрой»

Задача 3.4. Промышленное предприятие имеет запас готовой продукции:

• 80 единиц хранится на распределительном складе А;

• 50 единиц хранится на складе В;

• 30 единиц хранится на складе С.

П остроите логистическую распределительную сеть, если известна стоимость доставки посредникам К, М, Н и О. Так же известно, что количество потребностей этих посредников не превышает суммарного запаса готовой продукции. Построите оптимальный план перевозок и определите стоимость доставки (рис.10).

Пост.

Потр.

Рис.10. План объемов готовой Рис.11. Матрица расстояний

продукции между городами

Задача 3.5. Имеется 6 городов, которые должен посетить коммивояжер по одному разу и вернуться в исходный город. Расстояния между городами заданы матрицей С = (C_ij), где i = 1,2, ..., 6; j = 1, 2, ..., 6.

Определите маршрут движения коммивояжера, минимизируя пройденный путь (рис.11).

Пост.