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

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

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

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

Δ_lk = - ,

где — сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+»;

— сумма стоимостей перево зок единиц груза в четных клетках цикла, отмеченных знаком «—».

В клетках, отмеченных знаком «+», величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком «—», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, k) меньше нуля, т.е. Δ_lk<0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ·Δ_lk, т.е. опорное решение можно улучшить. Если же величины Δ_lk, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие Δ_lk≥0 х_lk=0.

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

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

Пример 15. Решить распределительным методом транспортную задачу:

b j ai	20	40	40
20	1	3	2
30	4	5	7
50	6	8	15

Решение. Строим начальное опорное решение:

.

Затем вычисляем значение целевой функции на нем: F(X₁)=20·1+ +30·5+10·8 + 40·15 = 850.

b j ai	20	40	40
20	1 20	3	2 0
30	4	5 30	7
50	6	8 10	15 40

Находим цикл для свободной клетки (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). Оценка Δ₂₁=(4+2+8)-(1+15+5)=14-21=-7. Так как Δ₂₁ = -7 < 0, определяем величину груза, перераспределяемого по циклу, θ = {20, 40, 30} = 20. Приращение целевой функции ΔF= -7 · 20 = -140. Получаем новое опорное решение Х₂. Значение целевой функции на нем

F(X₂) = 20 · 2 + 20 · 4 + 10 · 5 + 30 · 8 + 20 · 15 = 710.

b j ai	20	40	40
20	1	3	2 20
30	4 20	5 10	7
50	6	8 30	15 20

Вычисляем Δ₁₁ = (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) на величину θ = {10, 20} = 10. Приращение целевой функции ΔF= -5 · 10 = -50. Получаем третье опорное решение Х₃. Значение целевой функции на нем

F(X₃) = 20 · 2 + 20 · 4 + 10 · 7 + 40 · 8 + 10 · 15 = 660.

b j ai	20	40	40
20	1	3	2 20
30	4 20	5	7 10
50	6	8 40	15 10

Вычисляем оценки для свободных клеток: Δ₁₁= (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) на величину θ = {20, 10} = 10. Приращение целевой функции ΔF= -6 · 10 = -60. Получаем четверки опорное решение Х₄. Значение целевой функции на нем

F(X₄) = 20 · 2 + 10 · 4 + 20 · 7 + 10 · 6 + 40 · 8 = 600.

b j ai	20	40	40
20	1	3	2 20
30	4 10	5	7 20
50	6 10	8 40	15

Вычисляем оценки для свободных клеток Δ₁₁ = (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) на величину θ= {10,40}=10. Приращение целевой функции ΔF= -1 · 10 = -10. Получаем пятое опорное решение Х₅.

b j ai	20	40	40
20	1	3	2 20
30	4 0	5 10	7 20
50	6 20	8 30	15

Значение целевой функции на нем

F(X₅) = 20 · 2 + 10 · 5 + 20 · 7 + 20 · 6 + 30 · 8 = 590.

Вычисляем оценки для свободных клеток: Δ₁₁= (1 + 7) — (2 + 4) =2 > 0, Δ₁₂ = (3 + 7) - (2 + 5) = 3 > 0, Δ₃₃ = (15 + 5) - (7 + 8) = 5 > 0. Все оценки для свободных клеток положительные, следовательно, реше­ние оптимально.

Ответ: min F(X) = 590 при .