Проектирование оптимального плана доставки строительных материалов

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

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

i – поставщик;

j –потребитель;

n – количество поставщиков;

m –количество потребителей;

a_i – запас на поставку;

b_j –потребность в поставке;

x_ij – партия поставки;

c_ij – стоимость доставки;

B –базисная клетка;

p_ij – потенциал поставки (клетки);

u_i-потенциал поставщика(строки);

v_j – потенциал потребителя (столбца)

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

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

∑∑х_ij, c_ij → min. (3.1)

Задача решается методом потенциалов. Метод потенциалов можно разделить на два вида в зависимости от применяемого метода построения первоначального графика поставок: метод наименьшей стоимости и метод северо-западного угла.

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

Алгоритм решения транспортной задачи.

1. Построение первичного распределения:

– проверить на закрытость (открытость) задачи (сумма объемов поставки должна быть равна сумме потребностей);

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

– подсчитать стоимость доставки по полученному графику.

2. Проверка на плана оптимальность:

– проверить на выраженность (если m+n – 1 = В, то задачу можно проверить на оптимальность, иначе необходимо ввести дополнительную клетку с нулевой поставкой для продолжения решения);

– подсчитать потенциалы строк и столбцов (С_jj = u_i + v_j для каждой базисной клетки);

– подсчитать потенциалы клеток (р_jj = u_i + v_j для всех клеток);

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

3. Построение цикла перераспределения:

– выбрать перспективную клетку (определяем клетку, где разница потенциала клетка и стоимости наименьшая, и присваиваем ей знак «+»);

– построить цикл переноса (количество «+» и «–» должно быть одинаковое в каждом столбце и в каждой строке);

– произвести перераспределение на минимальную величину объема поставки попавшего в цикл переноса.

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

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

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

Рис. 9. Первичное распределение

Стоимость доставки при таком плане равна 302 +103 +204+302= = 230 руб.

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

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

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

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

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

Стоимость доставки при новом плане – 102 +303 + 201 + 302 = = 190 руб.

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

Дата добавления: 2013-12-13