Практику по транспортной задаче (о назначениях)

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

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

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

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

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

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

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

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

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

- подсчитать потенциалы строк и столбцов (Сjj = ui + vj для каждой базисной клетки);

- подсчитать потенциалы клеток (рjj = ui + vj для всех клеток);

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

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

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

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

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

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

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

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

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

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

Вторым этапом проверяем план на оптимальность с помощью потенциалов. Обнулив один любой потенциал строк или столбцов, находим остальные, из условия, что в базисных клетках (где запланирована поставка) сумма потенциалов строки ui и столбца vj должна быть равна стоимости доставки cij. Потенциалы клеток pij находим из того же условия, но для всех клеток. Количественные значения потенциалов указаны на рис. 24.

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

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

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

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

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

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

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