Распределительный метод

Алгоритм решения транспортной задачи распределительным методом состоит в следующем:

1. Находится начальный план (любым методом).

2. Для каждой свободной клетки () находится оценка .

3. Если все , то это распределение перевозок является оптимальным, т.е. дает минимальную стоимость перевозок. Если среди есть хотя бы одна отрицательная оценка, то переходим к новому распределению перевозок.

Для этого выбирается наибольшая по модулю отрицательная оценка свободной клетки . Среди перевозок, стоящих в отрицательных клетках цикла для , выбираем наименьшую перевозку. Пусть это будет . Производим сдвиг по циклу на . При этом клетка выходит из базиса (становится свободной). После получения нового базиса переходим к выполнению п.2 и так до тех пор, пока не получим оптимальное распределение перевозок.

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

Пример 2. Найти оптимальное распределение перевозок распределительным методом.

Таблица 1.7.1

Найдем начальный план методом северо-западного угла (табл. 1.7.2)

Таблица 1.7.2

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

ед.

Найдем оценки свободных клеток. Для этого составим для каждой свободной клетки цикл, содержащий ее и базисные клетки. Причем свободной клетке припишем знак “+”.

Наибольшая по модулю отрицательная оценка

. Сдвиг по циклу производим на (см. определение 5).

Полученное распределение перевозок записываем в (табл. 1.7.3)

Таблица 1.7.3

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

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

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

,

,

,

,

.

План не оптимальный, так как имеются отрицательные оценки. Наибольшая по модулю отрицательная оценка .

Сдвиг по циклу производим на . Полученное распределение перевозок записываем (табл. 1.7.4).

Таблица 1.7.4

Стоимость перевозок по плану стала равной

ед.

Находя далее оценки свободных клеток, получим, что наибольшая по модулю отрицательная оценка . Произведем сдвиг по циклу, содержащему клетку (4, 2), на 90. Из базиса выведем клетку (4, 4), в то время, как клетка (3, 2) останется базисной клеткой с перевозкой, равной 0. Полученное распределение перевозок запишем (табл. 1.7.5).

Таблица 1.7.5

Величина стоимости перевозок стала равной

ед.

На четвертом шаге имеем: . Сдвиг по циклу на 50ед.

Полученное распределение запишем (табл. 1.7.5).

Таблица 1.7.6

Стоимость перевозок на четвертом шаге равна

ед.

На пятом шаге:

, ,

, ,

, ,

, ,

,

Таким образом, полученный план является оптимальным, так как все оценки стали положительными. Минимальная стоимость перевозок равна ед. Оптимальный план перевозок представлен в табл.10.

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