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

Один из наиболее простых методов решения транспортных задач – распределительный метод.

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

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции равняется разности двух сумм

где – сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком "+"; – сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком "-".

В клетках, отмеченных знаком плюс, величины груза прибавляются, что приводит к увеличению значения целевой функции , а в клетках, отмеченных знаком "-", величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, k) меньше нуля,
т. е. , то перераспределение груза величиной q по соответствующему циклу приведет к уменьшению значения на величину , т. е. опорное решение можно улучшить. Если же величины , называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

. (6.11)

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку . Если оценка неотрицательная, переходят к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину . В результате получится новое опорное решение.

Для каждого нового опорного решения вычисление оценок начинается с первой свободной клетки таблицы. Очередность проверяемых свободных клеток целесообразно устанавливать в порядке возрастания стоимостей перевозок , так как решается задача на нахождение минимума.

Пример 6.4. Решить распределительным методом транспортную задачу, исходные данные которой приведены в табл. 6.7.

Т а б л и ц а 6.7

Решение. Строим начальное опорное решение методом минимальной стоимости (табл. 6.8).

Т а б л и ц а 6.8

Затем вычисляем значение целевой функции на нем

= 20×1 + 30×5 + 10×8 + 40×15 = 850.

Т а б л и ц а 6.9

Находим цикл для свободной клетки (1, 2) таблицы (1, 2), он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку
= (3 + 15) - (2 + 8)= 8. Так как = 8 > 0, переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1, 3), (3, 3), (3, 2), (2, 2) (см. табл. 6.8). Оценка = (4 + 2 + 8) - (1 + 15 + 5) = 14 - 21 = -7. Так как = -7 < 0, определяем величину груза, перераспределяемого по циклу . Приращение целевой функции DZ = -7 × 20 = -140. Получаем новое опорное решение (табл. 6.9).

Значение целевой функции на нем = 20 × 2 + 20 × 4 +
10 × 5 + 30 × 8 + 20 × 15 = 710.

Вычисляем = (1 + 15 + 5) - (2 + 8 + 4) = 7 > 0, = (3 + 15) - (2 + 8) = 8 > 0, = (7 + 8) - (5 + 15) = -5 < 0, = (6 + 5) - (4 + 8) = -1 < 0. Оценки можно вычислять до первой отрицательной. Так как = -5 < 0, осуществляем сдвиг по циклу (2, 3), (3, 3), (3, 2), (2, 2) на величину . Приращение целевой функции DZ = -5×10 = -50. Получаем третье опорное решение (табл. 6.10).

Т а б л и ц а 6.10

Значение целевой функции на нем = 20 × 2 + 20 × 4 +
10 × 7 + 40 × 8 + 10 × 15 = 660.

Вычисляем оценки для свободных клеток:

= (1 + 7) - (2 + 4) = 2 > 0,

= (3 + 15) - (2 + 8) = 8 > 0,

= (5 + 15) - (7 + 8) = 5 > 0,

= (6 + 7) - (4 + 15) = -6 < 0.

Так как = -6 < 0, осуществляем сдвиг по циклу (3, 1), (2, 1), (2, 3), (3, 3) на величину . Приращение целевой функции DZ = -6 × 10 = -60. Получаем четвертое опорное решение (табл. 6.11).

Т а б л и ц а 6.11

Значение целевой функции на нем = 20 × 2 + 10 × 4 +
20 × 7 + 10 × 6 + 40 × 8 = 600.

Вычисляем оценки для свободных клеток = (1 + 7) - (2 + 4) = 2 > 0, = (3 + 7 + 6) - (2 + 4 + 8) = 2 > 0, = (5 + 6) - (4 + 8) =
-1 < 0. Так как = -1 < 0, осуществляет сдвиг по циклу (2, 2),
(3, 2), (3, 1), (2, 1) на величину . Приращение целевой функции DZ = -1×10 = -10. Получаем пятое опорное решение (табл. 6.12).