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

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

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

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

		а	б	с	д
		150	120	80	50
А	100	3	5	7	11
		20	80
В	130	1	4	6	2
		130
С	170	5	8	12	7
			40	80	50

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

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

с12=5 - (1,2)		с13=7 + (1,3)		с12=5 - (1,2)		с14=4 + (1,4)		с11=3 + (1,1)		с14=5 + (1,2)
с32=8 + (3,2)		с33=12 - (3,3)		с32=8 + (3,2)		с34=7 + (3,4)		с32=1 + (2,1)		с34=4 + (2,2)
13= с13 - с33+ с32 - с12 =7-12+8-5= -2 < 0				14= с14 - с34+ с32 - с12 =4 -7+8 –5 = 0				22= с22 - с12+ с11 - с21 =4 - 5+3 - 1=1 > 0

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

с11=3 + (1,1)		с12=5 - (1,2)				с11=3 + (1,1)		с12=5 - (1,2)
с21=1 - (2,1)				с23=6 + (2,3)		с21=1 - (2,1)				с24=2 + (2,4)
		с32=8 + (3,2)		с33=12 - (3,3)				с32=8 + (3,2)		с34=7 - (3,4)
23= с23 - с33+ с32 - с12 + с11 - с21 = 6-12+8-5+3-1= -1 < 0						24= с24 - с34+ с32 - с12 + с11 - с21 = 2 -7+8-5+3-1= 0

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

с11=3 - (1,1)		с12=5 + (1,2)
с31=5 + (3,1)		с32=8 - (3,2)
31= с31 - с11+ с12 - с32 = 5-3+5-8= -1 < 0

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

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

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

с11=3; х11=20 - (1,1)		с12=5; х12=80 + (1,2)
с31=5 + (3,1)		с32=8; х32=40 - (3,2)

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

Таблица 20

L=2200		а	б	с	д
		150	120	80	50
А	100	3	5	7	11
			100
В	130	1	4	6	2
		130
С	170	5	8	12	7
		20	20	80	50

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

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

• 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 ден.ед.

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

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

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

с21=1; х21=130 - (2,1)		с24=2 + (2,4)
с31=5; х31=20 + (3,1)		с34=7; х34=50 - (3,4)

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

Таблица 21

L=2150		а	б	с	д
		150	120	80	50
А	100	3	5	7	11
			100
В	130	1	4	6	2
		80			50
С	170	5	8	12	7
		70	20	80

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

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

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

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

С21=1; х21=80 - (2,1)		с23=6 + (2,3)
с31=5; х31=70 + (3,1)		с33=12; х33=80 - (3,3)

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

Таблица 22

L=1990		а	б	с	д
		150	120	80	50
А	100	3	5	7	11
			100
В	130	1	4	6	2
		0		80	50
С	170	5	8	12	7
		150	20

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

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