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

(проверка на оптимальность, улучшение Т-плана)

Содержание метода:

1). Для каждой невыделенной клетки построим замкнутый контур следующим образом:

- начиная с невыделенной клетки по кратчайшему пути обходятся выделенные клетки по горизонтальному или вертикальному направлению;

- всем клеткам в строгом чередовании присваиваются знаки (+) или (-), причем первой присваивают знак (+) невыделенной клетке, с которой было начато построение контура.

2). Будем считать величину поставки и стоимость перевозки положительными, если клетка отмечена знаком (+) и отрицательными, если клетка отмечена знаком (-).

3). Вычислим алгебраическую сумму стоимостей перевозки с учетом знака клетки для каждого построенного контура - оценку клетки. Обозначим ее через δ_ij , где (i,j)- невыделенная клетка, с которой было начато построение замкнутого контура.

4). Если все δ_ij≥0, то построенный Т-план считают оптимальным. Остается вычислить затраты на перевозку груза. В противном случае – план перевозок не оптимальный и необходимо составить улучшенный Т-план (п.5).

5). Для построения улучшенного Т-плана выберем клетку (и соответствующий ей контур) с отрицательной оценкой, которой соответствует наименьшая удельная стоимость. Найдем в отрицательных вершинах этого контура минимальную по абсолютному значению величину поставки. Пусть это будет поставка x_lk. Тогда:

- клетку (l,k) исключим из числа выделенных и обнулим соответствующую ей величину поставки;

- величину поставки в положительных клетках контура увеличим на x_lk, а в отрицательных клетках – уменьшим на x_lk.

6). Получили новый Т-план (он отличается от предыдущего одной выделенной клеткой). Необходимо проверить его на оптимальность (начать с п.1).

Замечание 7:замкнутый контур, полученный при построении улучшенного Т-плана, содержит четное число вершин, причем число клеток со знаком (+) совпадает с числом клеток со знаком (-).

Замечание 8:Во избежание арифметических ошибок после построения нового Т-плана необходимо проверить совпадает ли

сумма поставок в стоке с объемом груза, имеющегося в наличии у соответствующего поставщика. Также сумма поставок в столбце должна совпадать с объемом поставки, необходимой соответствующему потребителю.

Найдем оптимальный план перевозок для задачи (*), используя распределительный метод . Для этого необходимо взять любой первоначальный Т-план из двух построенных ранее. К примеру возьмем Т-план, построенный по методу наименьшей стоимости. Рассмотрим таблицу перевозок, полученную при этом (Табл.15).

Таблица 15

	а	б	с	д

А

В

С

1). Чтобы определить является ли найденный Т-план оптимальным рассчитаем оценки каждой невыделенной клетки: (1,3), (1,4), (2,2), (2,3), (2,4), (3,1). Для этого необходимо для каждой из них построить замкнутый контур (6 невыделенных клеток – 6 контуров)

Клетка (1,3): Клетка (1,4): Клетка (2,2):

с₁₂=5 - (1,2)	с₁₃=7 + (1,3)	с₁₂=5 - (1,2)	с₁₄=4 + (1,4)	с₁₁=3 + (1,1)	с₁₄=5 + (1,2)

с₃₂=8 + (3,2)	с₃₃=12 - (3,3)	с₃₂=8 + (3,2)	с₃₄=7 + (3,4)	с₃₂=1 + (2,1)	с₃₄=4 + (2,2)

d₁₃= с₁₃- с₃₃+ с₃₂- с₁₂=7-12+8-5= -2 < 0	d₁₄= с₁₄- с₃₄+ с₃₂- с₁₂=4 -7+8 –5 = 0	d₂₂= с₂₂- с₁₂+ с₁₁- с₂₁=4 - 5+3 - 1=1 > 0

Клетка (2,3): Клетка (2,4):

с₁₁=3 + (1,1)	с₁₂=5 - (1,2)		с₁₁=3 + (1,1)	с₁₂=5 - (1,2)

с₂₁=1 - (2,1)		с₂₃=6 + (2,3)	с₂₁=1 - (2,1)		с₂₄=2 + (2,4)

	с₃₂=8 + (3,2)	с₃₃=12 - (3,3)		с₃₂=8 + (3,2)	с₃₄=7 - (3,4)

d₂₃= с₂₃- с₃₃+ с₃₂- с₁₂+ с₁₁- с₂₁= 6-12+8-5+3-1= -1 < 0	d₂₄= с₂₄- с₃₄+ с₃₂- с₁₂+ с₁₁- с₂₁= 2 -7+8-5+3-1= 0

Клетка (3,1):

с₁₁=3 - (1,1)		с₁₂=5 + (1,2)

с₃₁=5 + (3,1)		с₃₂=8 - (3,2)

d₃₁= с₃₁- с₁₁+ с₁₂- с₃₂= 5-3+5-8= -1 < 0

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

2). Выберем клетку с отрицательной оценкой. Их три: клетка (1,3) с удельной стоимостью с₁₃=7; клетка (2,3) где с₂₃=6 и клетка (3,1) где с₃₁=5. Минимальная удельная стоимость соответствует клетке (3,1). С нее начнем построение нового Т-плана.

3).Рассмотрим контур, соответствующий клетке (3,1):

с₁₁=3; х₁₁=20 - (1,1)		с₁₂=5; х₁₂=80 + (1,2)

с₃₁=5 + (3,1)		с₃₂=8; х₃₂=40 - (3,2)

Наименьший объем перевозки в отрицательных клетках контура соответствует клетке (1,1) и равен 20. Следовательно клетку (1,1) удалим из числа выделенных, выделим клетку (3,1) и присвоим значение х₃₁=20, х₁₂=80+20=100, х₃₂=40-20=20. Получили новый Т-план (Табл.20):

Таблица 20

L=2200	а	б	с	д

А

В

С

Проверим правильно ли был построен новый Т-план:

- число выделенных клеток не изменилось;

- 1 строка: 100=100; 2 строка: 130=130; 3 строка: 170 = 20 + 20 + 80 +50; 1 столбец: 150=130+20; 2 столбец: 120=100+20;

3 столбец: 80=80; 4 столбец: 50=50.

- суммарная стоимость перевозок уменьшилась: (изначально L=2220) L=5*100+1*130+5*20+8*20+12*80+7*50=2200 ден.ед.

Новый Т-план построен правильно. Проверим его на оптимальность - вычислим оценки невыделенных клеток: d₁₁= с₁₁-с₃₁+ с₃₂– с₁₂=3-5+8-5=1>0; d₁₃= с₁₃-с₃₃+ с₃₁– с₁₁=7-12+8-5= -2<0; d₁₄= с₁₄-с₃₄+ с₃₂– с₁₂= 4-7+8-5=0; d₂₂= с₂₂-с₃₂+ с₃₁– с₂₁=4-8+5-1=0; d₂₃= с₂₃-с₃₃+ с₃₁– с₂₁=6-12+5-1= -2<0; d₂₄= с₂₄- с₃₄+ с₃₁– с₂₁= 2 -7+5-1= -1< 0.

Получили три клетки с отрицательной оценкой: d₁₃, d₂₃, d₂₄. Это означает, что построенный Т-план также не является оптимальным. Наименьшая удельная стоимость соответствует клетке (2,4). С нее начнем построение нового Т-плана.

4). Рассмотрим контур, соответствующий клетке (2,4):

с₂₁=1; х₂₁=130 - (2,1)		с₂₄=2 + (2,4)

с₃₁=5; х₃₁=20 + (3,1)		с₃₄=7; х₃₄=50 - (3,4)

Наименьший объем перевозки в отрицательных клетках контура соответствует клетке (3,4) и равен 50. Следовательно клетку (3,4) удалим из числа выделенных, выделим клетку (2,4) и присвоим значение х₂₄=50, х₃₁=20+50=70, х₂₁=130-50=80. Получили новый Т-план (Табл.21):

Таблица 21

L=2150	а	б	с	д

А

В

С

Далее необходимо проверить правильно ли был построен новый план перевозки груза (Выполнение проверки упустим для краткости. Хотя на практике эта процедура обязательна!).

Проверим новый Т-план на оптимальность - вычислим оценки невыделенных клеток: d₁₁= с₁₁-с₃₁+ с₃₂– с₁₂=3-5+8-5=1>0; d₁₃= с₁₃-с₃₃+ с₃₁– с₁₁=7-12+8-5= -2<0; d₁₄= с₁₄-с₂₄+ с₂₁– с₃₁+ с₃₂- с₁₂= 4-2+1-5+8-5=1>0; d₂₂= с₂₂-с₃₂+ с₃₁– с₂₁=4-8+5-1=0; d₂₃= с₂₃- с₃₃+ с₃₁– с₂₁=6-12+5-1= -2<0; d₃₄= с₃₄-с₂₄+ с₂₁– с₃₁=7 – 2 +1-5 =1> 0.

Получили две клетки с отрицательной оценкой: d₁₃, d₂₃. Это означает, что построенный Т-план также не является оптимальным. Наименьшая удельная стоимость соответствует клетке (2,3). С нее начнем построение нового Т-плана.

5). Рассмотрим контур, соответствующий клетке (2,3):

С₂₁=1; х₂₁=80 - (2,1)		с₂₃=6 + (2,3)

с₃₁=5; х₃₁=70 + (3,1)		с₃₃=12; х₃₃=80 - (3,3)

Наименьший объем перевозки соответствует обеим отрицательным клеткам контура и равен 50. Удалим из числа выделенных (3,3), так как ей соответствует наибольшая удельная стоимость перевозки. Выделим клетку (2,3) и присвоим значение х₂₃=80, х₃₁=70+80=150, х₂₁=80-80=0. Получили новый Т-план (Табл.22):

Таблица 22

L=1990	а	б	с	д

А

В

С

Проверим новый Т-план на оптимальность - вычислим оценки невыделенных клеток: d₁₁= с₁₁-с₃₁+ с₃₂– с₁₂=3-5+8-5=1>0; d₁₃= с₁₃-с₂₃+ с₂₁– с₃₁+ с₃₂– с₁₂=7-6+1-5+8-5=0; d₁₄= с₁₄-с₂₄+ с₂₁– с₃₁+ с₃₂- с₁₂= 4-2+1-5+8-5=1>0; d₂₂= с₂₂-с₃₂+ с₃₁– с₂₁=4-8+5-1=0; d₃₃= с₃₃-с₂₃+ с₂₁– с₃₁=12 – 6 +1-5 =2>0; d₃₄= с₃₄-с₂₄+ с₂₁– с₃₁=7 – 2 +1-5 =1> 0.

Получили, что все клетки имеют неотрицательную оценку. Следовательно, построенный Т-план является оптимальным.

Сделаем выводы:

1. Оптимальный план заключается в перевозке груза в пункт а со складаС в объеме 150 усл.ед соответственно; в пункт бсо складов А и С в объеме 100 и 20 усл.ед.; 80 усл.ед в пункт с со склада В и 50 усл.ед. в пункт д со склада В.

2. Транспортные издержки при этом будут равны L=5*100+1*0+6*80+2*50+5*150+8*20=1990 ден.ед.