Економіка / Математичні методи в економіці

К.ф.м.н. Корольов Є.О., ст..Ковалинський К.Є.

Автомобільно-дорожній інститут ДНВЗ

«Донецький національний технічний університет»

ОПТИМАЛЬНЕ РОЗПОДІЛЕННЯ ТОВАРУ МІЖ МАГАЗИНАМИ АМСТОР МІСТА ДОНЕЦЬКА НАЙКОРОТШИМИ ШЛЯХАМИ.

Оптимальне розподілення товару по мережі магазинів здійснюється у два кроки:

1) Визначення мінімальних відстаней між магазинами (за допомогою метода Флойда)

2) Прорахунку оптимального товарообігу по мережі (за допомогою MS Excel).

Розглянемо сутність методів застосовуваних у даній задачі.

Метод Флойда (повна назва алгоритм Флойда-Уоршелла) динамічний алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа.

Основна ідея Флойда полягала у наступному. Нехай є три вузли i, j і k і задані відстані між ними (рис. 1). Якщо виконується нерівність dij + djk < dik, то доцільно замінити шлях i ® k шляхом i ® j ® k. Така заміна (трикутний оператор) виконується автоматично в процесі виконання алгоритму Флойда.

Рис.1 Трикутний оператор

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

Є пункти виробництва, проміжні пункти та пункти споживання однорідного продукту. При відомих витратах на перевезення продукції від пунктів виробництва через проміжні пункти до пунктів споживання, необхідно знайти план перевезень, що забезпечує мінімальні витрати.

Постановка задачі. Планується перерозподілити надлишки товару у мережі магазинів Амстор міста Донецька найкоротшими шляхами.

Розрахуємо мінімальні відстані між магазинами за методом Флойда.

Запишемо матрицю відстаней та матрицю маршрутів.

	1	2	3	4	5	6	7
1	-	2	3	4	5	6	7
2	1	-	3	4	5	6	7
3	1	2	-	4	5	6	7
4	1	2	3	-	5	6	7
5	1	2	3	4	-	6	7
6	1	2	3	4	5	-	7
7	1	2	3	4	5	6	-

Таблиця 1- Матриця відстаней D₀: Таблиця 2.2-Матриця маршрутів S₀:

	1	2	3	4	5	6	7
1	-	5	N	9	N	N	N
2	5	-	6	6	5	N	N
3	N	4	-	N	5	N	18
4	9	5	N	-	3	N	N
5	N	8	6	3	-	9	N
6	N	N	N	N	9	-	N
7	N	N	18	N	N	N	-

Виділяємо у матриці відстаней ведучий рядок і стовпець. Перевіряємо усі елементи матриці за допомогою трикутного оператора на можливість їх поліпшення , та записуємо проміжні пункти у матрицю маршрутів якщо вони є. У результаті розрахунку отримаємо кінцеву матрицю найкоротших відстаней та матрицю маршрутів.

Таблиця 1- Матриця відстаней : Таблиця 2-Матриця маршрутів :

	1	2	3	4	5	6	7
1	-	5	11	9	10	19	29
2	5	-	6	6	5	14	24
3	9	4	-	8	5	14	18
4	9	5	9	-	3	12	27
5	12	8	6	3	-	9	24
6	21	17	15	12	9	-	33
7	27	22	18	26	23	32	-

	1	2	3	4	5	6	7
1	-	2	2	4	2	5	3
2	1	-	3	4	5	5	3
3	2	2	-	5	5	5	7
4	1	2	5	-	5	5	5
5	4	2	3	3	-	6	3
6	5	5	5	5	5	-	5
7	3	3	3	5	3	5	-

Розрахуємо план оптимального перерозподілу товару.

Нехай задана матриця вартості перевезень.

Таблиця 3. Матриця вартості перевезень товарів по мережі.

	1	2	3	4	5	6
1	0	5		9
2	5	0	6	6	5
3		4	0		5
4	9	5		0	3
5		8	6	3	0	9
7			18

Розрахунок оптимального товарообігу зробимо за допомогою MS Excel (Данные- Поиск решения).У окремій комірці розрахуємо загальну вартість перевезення. Це буде сума добутків вартості товару С_ij (грошових одиниць) на обсяг товару. Обсяги та напрямок товару якого потрібно перерозподілити розрахуємо у Microsoft Excel за допомогою команди: Данные-Поиск решения. У якості обмежень приймемо що сума по рядкам дорівнює співвідношенню A_k=T_k+B, тобто сумі буфера та кількості зайвого товару у пункті. У джерелі A_k=200-кількість товару що у пункті 7. Також приймаємо, що сума по стовпцях дорівнює рівності B_к=В. У якості комірок які будуть змінюватися виділяємо комірки у матриці кількості товарів, що відповідають елементам матриці вартості перевезень. У якості цільової комірки приймаємо вартість пророблення перерозподілу .Значення буфера буде дорівнювати сумі всіх надлишків товарів по пунктах (В=270).

У результаті розрахунків отримаємо наступну матрицю.

Таблиця 4. Результати розрахунку оптимального товарообігу по мережі.

	1	2	3	4	5	6	∑	Ak=Tk+B	Tk
1	210	0		0			210	210	-60
2	60	260	0	0	0		320	320	50
3		10	70		50		130	130	-140
4	0	0		270	20		290	290	20
5		0	0	0	200	0	200	200	-70
7			200				200	200	200
∑	270	270	270	270	270	0
Bk=B	270	270	270	270	270	0

Рисунок 3. Результати перерозподілу товару по мережі магазинів.

З розрахованої схеми можна зробити висновок, що магазин 1 (джерело) відправляє 200 од. товару до магазина 3. Найкоротший шлях з магазину 7 до магазину3 (за таблицею 15) дорівнює 18 км. В магазині 3 покривається нестача товару в розмірі 140 од. та залишившийся товар перерозподіляємо наступним способом: 50 од. до магазину 5, та 10 од. до магазину 2.Найкоротший шлях з магазину 3 до магазину 5 не має проміжних пунктів та дорівнює 5 км, та з пункту 3 до пункту 2 також не має проміжних пунктів та дорівнює 4 км. Далі товар в розмірі 10 од. розподілившийся до магазину 2 в сукупності з надлишком товару магазина 2 в розмірі 50 од. розподіляється до магазину 1 шляхом довжиною 5км і не маючий проміжних пунктів та покриває нестачу магазина в розмірі 60 од товару.. Надлишок товару магазина 4 в сукупності з товаром перерозподіленим з магазину 3 до магазина 5 покриває нестачу у товарі магазина 5 в розмірі 70 од. Найкоротший шлях з магазину 4 до магазину 5 не має проміжних пунктів та дорівнює 3 км.

Після такого перерозподілу всі надлишки товарів мережі магазинів покривають усі недостачі у товарі. Даний перерозподіл здійснили мінімальними шляхами.

Література

1. Конюховский П.В. математические методы исследования операций.-СПб Питер, 2001.-192с.

2. Таха, Хэмди А.введение в исследование операцій, 6-е издание.:Пер.с англ. – М.:Издательский дом «Вильямс», 2001.-912с.