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

 

Пусть имеется исходное базисное решение транспортной задачи.

1. Для каждой свободной клетки строят цикл пересчета и подсчитывают алгебраические суммы стоимостей.

2. Если среди алгебраических сумм стоимостейАСС есть отрицательные, то план не оптимальный и следует перейти к пункту 3.

Если все АСС неотрицательные, то данное базисное решение является оптимальным. Подсчитывают оптимальное значение стоимости перевозок.

3. Среди всех алгебраических сумм стоимостей(АСС) выбирают наибольшую по величине отрицательную АСС и соответствующую ей свободную клетку матрицы перевозок.

4. Для свободной клетки, найденной в п.3, составляют цикл пересчета. Производят сдвиг, преобразовав свободную клетку в базисную. Получают новое базисное решение. Записывают его в таблицу перевозок.

5. Возвратиться к пункту 1 алгоритма.