2. 3 Решение задачи нахождения оптимального маршрута доставки груза

Нахождение оптимального, с точки зрения расстояния, маршрута по формализованной сети возможно с помощью математической модели (2.28) - (2.32) задача о нахождении кратчайшего пути в ациклических сетях.

(2.28)

; (2.29)

; (2.30)

; (2.31)

(2.32)

Смысл целевой функции и ограничений:

(2.28) - целевая функция, минимизирует затраты при формировании маршрута,

(2.29) - требование, чтобы искомый путь начинался в вершине 1,

(2.30) - требование чтобы искомый путь заканчивался в вершине n;

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

(2.32) - требование, чтобы все переменные модели были булевыми.

Решение задачи для маршрута Каменка – Новороссийск

Экономико-математическая модель в числовом виде:

Целевая:

Z=94* x₁₂ + 151 * x₁₃ + 363* x₁₆ + 188 * x₂₃ +169* x₂₄ +370 * x₃₅+ 100 * x₄₆+ 904 * x₄₉ + 158* x₅₆ +161* x₅₇ + 386 * x₆₈ + 485 * x₇₉ +418 * x_{89 →} min

Требование, чтобы искомый путь начинался в вершине 1

x₁₂ + x₁₃ + x₁₆=1

Требование чтобы искомый путь заканчивался в вершине 9;

x₄₉ + x₇₉+ x₈₉=1

Требование, чтобы искомый путь был связным, то есть проходил через вершины графа:

х₁₂-x₂₃- x₂₄=0 узел 2

х₁₃+x₂₃- x₃₅=0 узел 3

х₂₄-x₄₆- x₄₉=0 узел 4

х₃₅-x₅₆- x₅₇=0 узел 5

х₁₆+x₅₆+x₄₆-x₆₈=0 узел 6

х₅₇–x₇₉=0 узел 7

х₆₈–x₈₉=0 узел 8

Требование, чтобы все переменные модели были булевыми:

Таблица 2.3.1 Решение задачи нахождения оптимального маршрута доставки груза по маршруту Каменка – Новороссийск

Пункт отпр. (вершина 1)	Промежут. (конечный n) пункт назначен.	Расстояние	Переменные	Ограничение
1	2	94	1	0
1	3	151	0	0
1	6	363	0	0
2	3	188	0	0
2	4	169	1	0
3	5	370	0	0
4	6	100	0	0
4	9	904	1	0
5	6	158	0	0
5	7	161	0	0
6	8	386	0	0
7	9	485	0	0
8	9	418	0	0

Затраты при формировании маршрута составляют 1167

Подтверждается отчетом по результатам, сформированым программой.

Графическая интерпретация решения задачи по маршруту Каменка-Новороссийск.

94

169

904

Решение задачи для маршрута Каменка - Ильичевск.

Экономико-математическая модель в числовом виде:

Целевая:

Z=73* x₁₂ + 124 * x₁₃ + 356* x₁₆ + 51 * x₂₃ +179* x₂₄ + 206 * x₃₅+ 104 * x₄₆+ 177 * x₄₉ + 26* x₅₆ +61* x₅₇ + 43* x₆₈ + 38* x₇₉ + 30* x_{89 →} min

Требование, чтобы искомый путь начинался в вершине 1

x₁₂ + x₁₃ + x₁₆=1

Требование чтобы искомый путь заканчивался в вершине 9;

x₄₉ + x₇₉+ x₈₉=1

Требование, чтобы искомый путь был связным, то есть проходил через вершины графа:

х₁₂-x₂₃- x₂₄=0 узел 2

х₁₃+x₂₃- x₃₅=0 узел 3

х₂₄-x₄₆- x₄₉=0 узел 4

х₃₅-x₅₆- x₅₇=0 узел 5

х₁₆+x₅₆+x₄₆-x₆₈=0 узел 6

х₅₇–x₇₉=0 узел 7

х₆₈–x₈₉=0 узел 8

Требование, чтобы все переменные модели были булевыми:

Таблица 2.3.1 Решение задачи нахождения оптимального маршрута доставки груза по маршруту Каменка – Ильичевск

Пункт отпр. (вершина 1)	Промежут. (конечный n) пункт назначен.	Расстояние	Переменные	Ограничение
1	2	73	1	0
1	3	124	0	0
1	6	356	0	0
2	3	51	0	0
2	4	179	1	0
3	5	206	0	0
4	6	104	0	0
4	9	177	1	0
5	6	26	0	0
5	7	61	0	0
6	8	43	0	0
7	9	38	0	0
8	9	30	0	0

Затраты при формировании маршрута составляют 429

Подтверждается отчетом по результатам, сформированным программой.

Графическая интерпретация решения задачи по маршруту Каменка - Ильичевск.

Каменка

Николаев

73

Ильичевск

179

177

Кировоград

Решение задачи для маршрута Краснознаменка - Новороссийск.

Экономико-математическая модель в числовом виде:

Целевая:

Z=204* x₁₂ + 307* x₁₃ + 428* x₁₆ +66 * x₂₃ +150* x₂₄ + 337 * x₃₅+346 * x₄₆+ 986 * x₄₉ + 93* x₅₆ +248* x₅₇ + 212* x₆₈ + 485* x₇₉ + 312* x_{89 →} min

_{Требования аналогичны 1 и 2 маршруту}

Таблица 2.3.1 Решение задачи нахождения оптимального маршрута доставки груза по маршруту Краснознаменка-Новороссийск

Пункт отпр. (вершина 1)	Промежут. (конечный n) пункт назначен.	Расстояние	Переменные	Ограничение
1	2	204	0	0
1	3	307	0	0
1	6	428	1	0
2	3	66	0	0
2	4	150	0	0
3	5	337	0	0
4	6	346	0	0
4	9	986	0	0
5	6	93	0	0
5	7	248	0	0
6	8	212	1	0
7	9	485	0	0
8	9	312	1	0

Затраты при формировании маршрута составляют 952

Подтверждается отчетом по результатам, сформированным программой.

Графическая интерпретация решения задачи по маршруту Краснознаменка - Новороссийск.

Краснознаменка

Батайск

Мангуш

428

212

312

Новороссийск

ийск

Решение задачи для маршрута Заводское-Ейск

Экономико-математическая модель в числовом виде:

Целевая:

Z=47* x₁₂ + 209* x₁₃ + 571* x₁₆ + 162 * x₂₃ +191* x₂₄ + 216 * x₃₅+ 333* x₄₆+ 686* x₄₉ + 146* x₅₆ +302* x₅₇ + 200* x₆₈ + 197* x₇₉ + 153* x_{89 →} min

_{Требования аналогичны 1 и 2 маршруту}

Таблица 2.3.1 Решение задачи нахождения оптимального маршрута доставки груза по маршруту Заводское-Ейск

Пункт отпр. (вершина 1)	Промежут. (конечный n) пункт назначен.	Расстояние	Переменные	Ограничение
1	2	47	1	0
1	3	209	0	0
1	6	571	0	0
2	3	162	0	0
2	4	191	1	0
3	5	216	0	0
4	6	333	0	0
4	9	686	1	0
5	6	146	0	0
5	7	302	0	0
6	8	200	0	0
7	9	197	0	0
8	9	153	0	0

Затраты при формировании маршрута составляют 924

Подтверждается отчетом по результатам, сформированным программой.

Графическая интерпретация решения задачи по маршруту Заводское-Ейск

Харьков

Заводскоей

191

Ейск

686

47

Гадяч

Вывод

В пункте 2.2 были построены исходные транспортные сети.

В пункте 2.3 в результате решения задачи в программе Excel удалось рассчитать оптимальные и кратчайшие маршруты доставки нашего груза от выбранных поставщиков в порты отправления:

Маршрут Каменка-Новороссийск через промежуточные пункты Александрия-Днепр, затраты составили 1167.

Маршрут Каменка-Ильичевск через промежуточные пункты Кировоград-Николаев, затраты составили 429.

Маршрут Краснознаменка-Новороссийск через промежуточные пункты Мангуш-Батайск, затраты составили 952.

Маршрут Заводское-Ейск через промежуточные пункты Гадяч-Харьков, затраты составили 924.

3. ПОСТРОЕНИЕ СИСТЕМЫ УПРАВЛЕНИЯ ЗАПАСАМИ