Рис. 1.1. Оптимизация местоположения склада

Методом центра тяжести

На рисунке 1 обозначено несколько объектов: поставщики, заказчики и в центре – складской комплекс. Стрелками указано направление грузовых потоков. Географическое расположение объектов представлено в декартовой прямоугольной системе координат, причем координаты поставщиков и получателей известны, а координаты оптовой базы остаются неизвестными. Требуется найти оптимальные значения величин x₀, y₀, при которых суммарные годовые затраты на транспортировку грузов в рассматриваемой системе будут минимальными. Транспортные затраты рассчитываются как произведение следующих величин:

• объем грузопотока, т/год;

• расстояние между поставщиком/заказчиком и складским комплексом, км;

• транспортный тариф, руб/ткм.

Единица измерения «руб/ткм» означает «рубль на тонно-километр», то есть во сколько обходится транспортной организации перемещение одной тонны груза на один километр.

Рассмотрим следующую задачу. Известны следующие исходные данные:

Таблица 1.1

№ п/п	Объект	Объем грузопотока, т/год	Тариф, руб/ткм	Координаты
				x	y
1	A	3500	5	25	78
2	B	4000	8,5	10	34
3	C	6000	8,5	72	88
4	D	2300	5	85	50
5	E	4200	5	65	18

Введем следующие условные обозначения:

• n – количество поставщиков и заказчиков;

• q_i – объем грузопотока i-го поставщика/заказчика, т/год;

• r_i – транспортный тариф i-го поставщика/заказчика, руб/ткм;

• x_i, y_i – координаты i-го поставщика/заказчика;

• x₀, y₀ – координаты складского комплекса;

• d_0i – расстояние между складским комплексом и i-м поставщиком/заказчиком.

Требуется определить оптимальные значения величин x₀, y₀, при которых будет выполняться следующее условие:

,

где TC (Total Cost) – суммарные затраты на транспортировку, руб/год.

Нахождение оптимальных координат x₀, y₀ осуществляется с помощью итерационного сходящегося алгоритма. Количество итераций определяется требованиями к степени точности получаемого решения.

Алгоритм решения задачи методом центра тяжести

Шаг 0. Начальный расчет величин x₀, y₀:

; .

На основании расчетов, приведенных в таблице 2, определяем начальные значения координат оптовой базы: x₀ = 6792000/135000 = 50,3; y₀ = 7962000/135000 = 59,0.

Таблица 1.2

№ п/п	Объект	xiqiri	yiqiri	qiri
1	A	437 500	1 365 000	17 500
2	B	340 000	1 156 000	34 000
3	C	3 672 000	4 488 000	51 000
4	D	977 500	575 000	11 500
5	E	1 365 000	378 000	21 000
Сумма		6 792 000	7 962 000	135 000

Шаг 1. Расчет расстояний между складским комплексом и множеством поставщиков/заказчиков (см. табл. 3, графа 3):

Шаг 2. Расчет суммарных затрат на транспортировку (см. табл. 3, графа 4):

Шаг 3. Повторный расчет координат оптовой базы (см. табл. 3, графы 5-7):

; .

Таблица 1.3

№ п/п	Объект	d0i	qirid0i	xiqiri/d0i	yiqiri/d0i	qiri/d0i
1	2	3	4	5	6	7
1	A	31,7	554 089	13 817,7	43 111,3	552,7
2	B	47,4	1 612 358	7 169,6	24 376,7	717,0
3	C	36,2	1 847 789	101 349,2	123 871,3	1 407,6
4	D	35,8	412 066	27 280,2	16 047,2	320,9
5	E	43,5	914 149	31 357,0	8 683,5	482,4
Сумма		–	5 340 452	180 973,8	216 089,9	3 480,7

В соответствии с проведенными вычислениями, определяем новые координаты оптовой базы: x₀ = 180973,8/3480,7 = 52,0; y₀ = 216089,9/3480,7 = 62,1. Отметим также, что при старых координатах оптовой базы (50,3; 59,0) суммарные затраты на транспортировку, согласно табл. 3., составляют: TC = 5340452 руб/год.

Шаг 4. Повторять шаги 1, 2 и 3 до тех пор, пока суммарные транспортные затраты TC не перестанут изменяться на значимую величину.

Результаты выполнения шага 4 представлены в следующей таблице:

Таблица 1.4

Номер итерации	Координаты		TC
	xo	yo
0	50,3	59,0	5 340 452
1	52,0	62,1	5 305 197
2	53,3	63,8	5 291 233
3	54,2	64,9	5 285 120
4	54,8	65,6	5 282 289
5	55,3	66,1	5 280 933
6	55,6	66,4	5 280 269
7	55,8	66,6	5 279 939
8	56,0	66,8	5 279 773
9	56,1	66,9	5 279 689
10	56,2	67,0	5 279 646
…	…	…	…
100	56,3	67,2	5 279 601

Как хорошо видно в данной таблице, уже на первых десяти итерациях можно получить достаточно точные значения координат оптовой базы, которые дают вполне приемлемые результаты по величине суммарных транспортных затрат TC. Выполнение дальнейших итераций (в данном случае, для сравнения, представлена сразу 100-я итерация) незначительно влияет на конечный результат. Это говорит о том, что уже на первых нескольких итерациях можно прекратить дальнейшие вычисления.