3

-

7

-

3

25

25

4

1

4

3

-

5

17

5

3

24

Потребности

25

19

24

28

S = 96

Z = 1×22+1×19+1×7+3×25+1×4+5×17+5×3=226, в методе северо-западного угла стоимость перевозки была выше и составляла 350.

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

Распределительный метод представляет собой набор следующих действий: вначале строится исходный опорный план перевозок по одному из вышеизложенных правил, а затем последовательно производится его улучшение до получения оптимального. Для этого для каждой свободной клетки строят замкнутый цикл. Если в матрице перевозок содержится опорный план, то для каждой свободной клетки можно образовать и притом только один замкнутый цикл, содержащий эту свободную клетку и некоторую часть занятыx клеток.

Тарифы в клетках, находящихся в нечетных вершинах цикла, берем со знаком плюс, а в четных - со знаком минус. По каждому циклу подсчитываем алгебраическую сумму S ij тарифов.

Если замкнутый цикл имеет вид: (i, j) - >(k, j) - >(k, l) - >(t, l) - >... ->(u, v) - >(i, v), то S ij =C ij - C kj + C kl - C tl +... + C uv - C iv, где (i,j) - свободная клетка.

Если алгебраическая сумма S ij отрицательна, то путем изменения значений, стоящих в клетках замкнутого цикла, можно получить план с меньшим значением целевой функции. Критерием оптимальности при нахождении минимума функции служит неотрицательность алгебраических сумм S ij. Если указанное требование не соблюдено, план не оптимален и подлежит улучшению.

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