Транспортная задача линейного программирования

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

Один из наиболее простых методов решения транспортных задач - распределительный метод.
Пусть для транспортной задачи найдено начальное опорное решение Х1 и вычислено значение целевой функции на этом решении F(Х1). По доказанной выше теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину  можно получить новое опорное решение Х2.
Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l,m), приращение целевой функции Δlm равно разности двух сумм:
где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+” ; - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”.
В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции.
Если разность сумм для свободной клетки ( l, m ) меньше нуля, т.е. Δ lm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θΔlm, т.е. опорное решение можно улучшить. Если же величины Δlm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

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

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

Количество столбцов (магазины)
Количество строк (поставщики)

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

    b1 b2 b3
    20 40 40
a1 20   1   3   2
           
a2 30   4   5   7
         
a3 50   6   8   15
           

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

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

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

Вычисляем Δ11 = (1 + 15 + 5) - (2 + 8 + 4) =7>0 , Δ12= (3 + 15) - (2 + 8) =8>0,   Δ 23 = (7 + 8) - (5 + 15)=-5<0, Δ31= (6 + 5) - (8 + 4) =-1<0. Оценки можно вычислять до первой отрицательной. Так какΔ23 =-5<0,  осуществляем сдвиг по циклу (2,3), (3,3), (3,2), (2,2) на величину . Приращение целевой функции ΔF=-5∙10=-50. Получаем третье опорное решение X3. Значение целевой функции на нем F(X3)=20∙2+20∙4+10∙7+40∙8+10∙15=660.

Вычисляем оценки для свободных клеток Δ11 = (1 + 7) - (2 + 4) =2>0 ,  Δ12 = (3 + 15) - (2 + 8) =8>0,   Δ22 =(5 + 15) - (7 + 8)  =5>0,   Δ31 = (6 + 7) - (4 + 15) =-6<0. Так как  Δ31 =-6<0, осуществляем сдвиг по циклу (3,1), (2,1), (2,3), (3,3), на величину   Приращение целевой функции ΔFm=-6∙10=-60. Получаем четвертое опорное решение X4 Значение целевой функции на нем F(X4)=20 ∙2+10∙4+20∙7+10∙6+40∙8=600.

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

Значение целевой функции на нем F(X5)=20 ∙2+10∙5+20∙7+20∙6+30∙8=590. Вычисляем оценки для свободных клеток Δ11 = (1 + 7) - (2 + 4) =2>0 ,  Δ12 = (3 + 7) - (2 +5) =3>0,   Δ33 =(15 + 5) - (7 + 8)  =5>0. Все оценки для свободных клеток положительные, следовательно, последнее опорное решение оптимально.

см. также Пример решения задачи распределительным методом, Распределительный метод решения транспортной задачи, Распределительный метод. Пример решения транспортной задачи, Решить транспортную задачу распределительным методом и методом потенциалов

загрузка...