Синтез системи підтримки прийняття рішень (СППР) для оптимізації парку транспортних засобів

МІНІСТЕРСТВО  ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

Чорноморський державний  університет імені Петра Могили

Факультет комп’ютерних наук

Кафедра інтелектуальних  інформаційних систем

 

 

 

 

 

КУРСОВА РОБОТА

" Синтез системи підтримки прийняття рішень (СППР) для оптимізації парку

транспортних  засобів та оптимізації маршрутів  вантажних перевезень в умовах

невизначеності  "

Дисципліна " Системи підтримки прийняття рішень"

Спеціальність "Системи і методи прийняття рішень"

 

7.050101–КР.ПЗ.00–402.2710314

 

 

 

 

                                                                                      Студентка _____________ І.О. Дорошенко

                         (підпис)

 

                  _____________

 (дата)

 

                                                                                    Викладач,

проф., д.т.н.______________  Ю.П. Кондратенко

    (підпис)

 

           ______________

   (дата)

 

 

Миколаїв – 2012

 

Оглавление

1 ФОРМУВАННЯ ВХІДНИХ ДАНИХ 4

1.1. Генерація загальних обсягів замовлень для трьох можливих програм загальних вантажних перевезень F₁, F_2, F₃ 4

1.2. Генерація замовлень вантажу в кожному з вузлів (чіткі значення) 4

2 ФОРМУВАННЯ СИМЕТРИЧНОЇ МАТРИЦІ ВІДСТАНЕЙ МІЖ ЗАДАНИМИ ВУЗЛАМИ. 7

3 ФОРМУВАННЯ ПОСЛІДОВНОСТІ ОБХОДУ (ЗАДАЧА TSP – TRAVELING SALESMAN PROBLEM АБО ЗАДАЧА КОМІВОЯЖЕРА) НА ОСНОВІ SAVING-АЛГОРИТМУ 10

3.1 Формування saving-таблиці відстаней 10

3.2 Графічна візуалізація гамільтонового циклу сформованого за saving-алгоритмом 13

4 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ SAVING-АЛГОРИТМУ 14

5 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ  МОДИФІКОВАННОГО SAVING-АЛГОРИТМУ 19

5.1 Програма F₁ 20

5.2 Програма F₂ 21

5.3 Програма F₃ 22

6 Формування послідовності обходу вузлів (задача tsp-комівояжера) на основі sweeping-алгоритму 24

6.1 Графічна візуалізація відповідного Гамільтонового циклу. 24

7 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ SWEEPING-АЛГОРИТМУ 25

7.1 Програма F1 26

7.2 Програма F₂ 27

7.3 Програма F₃ 28

8 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ МОДИФІКОВАННОГО SWEEPING-АЛГОРИТМУ 30

8.1 Програма F₁ 31

8.2 Програма F₂ 32

8.3 Програма F₃ 33

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

10 ОПТИМІЗАЦІЯ МАРШРУТІВ 36

10.1 Програма F₁ 37

10.2 Програма F₂ 39

11 ПОШУК ОПТИМАЛЬНОЇ КІЛЬКОСТІ ТРАНСПОРТНИХ ЗАСОБІВ 41

11.1 Формування матриці рішень стосовно розміру парку транспортних засобів 41

11.2 Пошук оптимальної кількості транспортних засобів шляхом використання класичних критеріїв 43

11.2.1 Мінімаксний критерій (ММ) 43

11.2.2 Критерій Байєса-Лапласа 43

11.3 Пошук оптимальної кількості транспортних засобів шляхом використання похідних критеріїв 46

11.3.1 Критерій Гурвіца 46

11.3.2 Критерій Ходжа-Лемана 46

11.3.3 Критерій Гермейєра 47

11.3.4 Критерій добутків 48

11.4 Пошук оптимальної кількості транспортних засобів шляхом використання комбінованих критеріїв 49

11.4.1 Критерій Байєса-Лапласа-Мінімаксний 49

11.4.2 Критерій Байєса-Лапласа-Севіджа 49

11.5 Аналіз результатів застосування критеріїв прийняття рішень 50

ВИСНОВКИ 51

ПЕРЕЛІК ПОСИЛАНЬ 53

ДОДАТОК А 54

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. ФОРМУВАННЯ  ВХІДНИХ ДАНИХ

1. Генерація загальних обсягів замовлень  для трьох можливих програм загальних вантажних перевезень F₁, F_2, F₃

Значення F₁ обчислюється за наступною формулою:

F₁=3* D_max(1+η_k),

а значення інших програм за формулою

F_k = F_k-1(1+ η_k), k=2,3

де η_k ϵ 0,1 , k = 1,2,3  -  випадкові числа.

В результаті виконання програми, код якої наведено в додатку А.1, були згенеровані  наступні вхідні дані, які наведені в таблиці 1:

Таблиця 1. Згенеровані вхідні дані

i	η	F
1	0,6555	9,933
2	0,1712	7,0272
3	0,7060	10,236

 

2. Генерація замовлень вантажу в кожному  з вузлів (чіткі значення)

Замовлення  в вузлах для всіх програм визначається за наступним алгоритмом:

1. Генеруємо  значення випадкових чисел X_j ϵ 0,1 для кожного з вузлів за допомогою генератора випадкових чисел, j=1,...,N; N=25.

В результаті виконання програми, код якої наведено в додатку А.2, були згенеровані  дані які занесені до табл. 2.

Таблиця 2. Згенеровані випадкові числа

1	0,0318	6	0,6948	11	0,3816	16	0,4456		21	0,6797
2	0,2769	7	0,3171	12	0,7655	17	0,6463		22	0,6551
3	0,0462	8	0,9502	13	0,7952	18	0,7094		23	0,1626
4	0,0971	9	0,0344	14	0,1869	19	0,7547		24	0,1190
5	0,8235	10	0,4387	15	0,4898	20	0,2760		25	0,4984

 

1. Знаходимо суму всіх генерованих випадкових чисел.

 

2. Знаходимо нормалізований параметр µ_j, j=1,…,N для кожного j-го вузла

В результаті виконання програми, з додатку  А.2, був обрахований нормалізований параметр µ_j, результати були занесені до табл. 3.

Таблиця 3. Нормалізовані параметри µ_j.

1	0,0028	6	0,0616	11	0,0338	16	0,0395	21	0,0603
2	0,0246	7	0,0281	12	0,0679	17	0,0573	22	0,0581
3	0,0041	8	0,0843	13	0,0705	18	0,0629	23	0,0144
4	0,0086	9	0,0031	14	0,0166	19	0,0669	24	0,0106
5	0,0730	10	0,0389	15	0,0434	20	0,0245	25	0,0442

 

3. Замовлення в вузлах при реалізації i-ї програми F_i вантажних перевезень визначаються за формулою

 

В результаті виконання програми, з додатку  А.2, було обраховано замовлення в вузлах , дані були занесені до табл. 4.

Таблиця 4.  Замовлення в усіх вузлах

Q	F1	F2	F3
1	0,0280	0,0198	0,0289
2	0,2439	0,1726	0,2514
3	0,0407	0,0288	0,0419
4	0,0856	0,0605	0,0882
5	0,7253	0,5132	0,7475
6	0,6120	0,4330	0,6307
7	0,2793	0,1976	0,2878
8	0,8370	0,5922	0,8625
9	0,0303	0,0215	0,0313
10	0,3865	0,2734	0,3983
11	0,3361	0,2378	0,3464
12	0,6743	0,4770	0,6949
13	0,7005	0,4955	0,7218
14	0,1646	0,1165	0,1696
15	0,4314	0,3052	0,4446
16	0,3925	0,2777	0,4045
17	0,5693	0,4028	0,5867
18	0,6248	0,4421	0,6439
19	0,6648	0,4703	0,6851
20	0,2431	0,1720	0,2506
21	0,5987	0,4236	0,6170
22	0,5770	0,4082	0,5947
23	0,1432	0,1013	0,1476
24	0,1048	0,0742	0,1080
25	0,4390	0,3106	0,4524

 

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

 

 

 

 

2. ФОРМУВАННЯ  СИМЕТРИЧНОЇ МАТРИЦІ ВІДСТАНЕЙ  МІЖ ЗАДАНИМИ ВУЗЛАМИ.

Таблиця 5. Симетрична матриця відстаней між заданими вузлами

№ вузла	3	4	5	6	7	8	9	10	11	12	13	14
3	0	24	42,2018	16,2788	29,4278	34	14,8660	28,3196	39,4461	15,2315	42,2018	42,7200
4	24	0	26,9258	16,2788	7,0710	10	23,6008	21,5870	22,3606	11,6619	19,7230	20,8086
5	42,2018	26,9258	0	26,0768	30,4138	25	48,6004	48,3838	45	36,8917	16,5529	37,6563
6	16,2788	16,2788	26,0768	0	23,3452	24,5967	25,9615	32,7566	38,0131	17,1172	29,0172	37,0135
7	29,4278	7,0710	30,4138	23,3452	0	7,0710	25,6320	18,8679	15,8113	15,0332	19,2093	13,8924
8	34	10	25	24,5967	7,0710	0	32,2024	25,8069	20	20,8806	12,2065	13,8924
9	14,8660	23,6008	48,6004	25,9615	25,6320	32,2024	0	15,6524	29,6141	12,0415	43,2666	36,0555
10	28,3196	21,5870	48,3838	32,7566	18,8679	25,8069	15,6524	0	15,0332	15,8113	38,0131	23,7697
11	39,4461	22,3606	45	38,0131	15,8113	20	29,6141	15,0332	0	24,4131	30,8058	10,6301
12	15,2315	11,6619	36,8917	17,1172	15,0332	20,8806	12,0415	15,8113	24,4131	0	31,3847	27,6586
13	42,2018	19,7230	16,5529	29,0172	19,2093	12,2065	43,2666	38,0131	30,8058	31,3847	0	22
14	42,7200	20,8086	37,6563	37,0135	13,8924	13,8924	36,0555	23,7697	10,6301	27,6586	22	0
15	46,0651	27,0185	8,0622	30,6757	28,6356	22,1359	50,2095	47,4130	41,5932	38,1837	11	33
16	9	25,6320	37,5765	12,1655	32,2024	35,1710	23,5372	35,5105	44,6878	20,5182	41,0121	46,0651
17	12,0415	12,0415	32,5576	10	18,0277	22,0227	16,5529	23,0867	30,4138	7,2801	30,3644	31,7804
18	16,2788	37,6430	58,4123	32,5576	41,4366	47,2969	17,2626	32,5729	46,8721	26,4764	57,0087	53,0094
19	41,1096	17,2626	28,8617	32,2024	12,1655	7,6157	37,6430	28,4253	18,3847	27,1661	13	9
20	54,6443	37,4432	12,5299	38,5875	39,3954	32,8937	60,2079	58,1377	52,1727	48,2700	21,3775	43,1856
21	39,4081	32,0156	13,0384	23,7065	37,4833	33,8378	49,3963	53,1507	53,15072	39,0512	28,4253	47,5394
22	32,3882	37,2155	29,8328	22,1359	44,1021	43,1856	46	54,8178	59,5399	39,0512	42,1900	56,8506
23	19,7230	38,0131	44,7213	22,8035	44,7772	47,1699	34,4383	47,8016	57,4891	33,2415	51,4781	58,6685
24	14,1421	38,0525	53,2259	27,5136	43,5660	48,0416	24,8394	40,2243	52,8015	29,1204	55,5787	56,7538
25	19,4164	33,8378	58,1377	34	35,8468	42,4852	10,2956	23,0867	38,0131	22,2036	53,5350	45,5411
26	20,0249	4,1231	29,5296	14,4222	9,8488	14,0356	19,8494	20,0249	23,6008	7,8102	23,7065	23,7065
27	35,7351	14,8660	14	22	16,7630	11	38,2883	35,3411	31	26,2488	7,0710	24,0416