2.2 Метод Дакея

Метод Дакея может быть использован для приближенных расчетов кольцевых маршрутов.

Рассмотрим пример на данном этапе.

Метод предусматривает последовательное вычеркивание наибольших значений элементов матрицы:

Таблица 2.2.1 - Исходные данные

Пункты начала движения	Пункты конца движения
	1	2	3	4	5
1	∞	5	4	5	23
2	8	∞	8	8	5
3	6	8	∞	11	12
4	26	11	11	∞	10
5	14	16	19	16	∞

1. Максимальные значения в матрице: 26, 23, 19, 16, 16 они вычеркиваются. В 5 строке остается один не вычеркнутый элемент - Q5.1, он округляется, столбец 1 вычеркивается и элемент Q1,5 также вычеркивается.

2. Затем максимальные значения в матрице:12, 11, 11, 11 они вычеркиваются и в 4 строке остается один не вычеркнутый элемент - Q4.5, он округляется, столбец 5 вычеркивается и элемент Q5.4 также вычеркивается.

3. После этого в 3 строке остается один не вычеркнутый элемент - Q3.2, он округляется, столбец 2 вычеркивается и элемент Q2.3 также вычеркивается.

4. В 2 строке остается один не вычеркнутый элемент- Q2.4, он округляется, столбец 4 вычеркивается и элемент Q4.2 также вычеркивается.

5. В 1 строке в окончательном итоге остаётся один не вычеркнутый элемент, и он округляется.

Протяженность маршрута будет равна:

Z(5.1; 3.2; 4.5; 2,4; 1.3) = 14+8+10+8+4=44 минут.

1

2

5

3

4

Рисунок 2.2.1 – Схема маршрута методом Дакея

Вывод: При расчете данным методом затраты времени составили 44 минуты, а это значит, что метод Дакея в данном варианте не является самым оптимальным способом решения.

2.3 Метод Дакея-Габра

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

Расчет элементов матрицы ведется по формуле:

f(ij) = 2d(ij)-Z(i)-S(j), (2.3.1)

где f (ij) – величина элемента i-строки и j- столбца по методу Дакея-Габра

d (ij) – длина частичного маршрута

Z (i) – среднее значение расстояния (времени) по i-строке

S (j) – среднее значение (времени) по j-столбцу

Среднее значение определяется по формуле:

Z(i),S(j) = (2.3.2)

Таблица 2.3.1 - Исходные данные

Пункты начала движения	Пункты конца движения						Zi
	1	2	3	4	5
1	∞	5	4	5	23	9,25
2	8	∞	8	8	5	7,25
3	6	8	∞	11	12	9,25
4	26	11	11	∞	10	14,50
5	14	16	19	16	∞	16,25
Sj	13,5	10,0	10,5	10,0	12,5

f_1.2 = 2 * 5 – 9, 25 – 10, 0 = -9, 25 f_1.3 = 2 * 4 - 9, 25 - 10, 5 = -11, 75

f_1.4 = 2 * 5 – 9, 25 – 10, 0 = -9, 25 f_1.5 = 2 * 23 - 9, 25 - 12, 5 = 24, 25

f_2.1 = 2 * 8 - 7, 25 - 13, 5= -4, 75 f_2.3 = 2 * 8 - 7, 25 - 10, 5 = -1, 75

f_2.4 = 2 * 8 - 7, 25 – 10, 0 = -1, 25 f_2.5 = 2 * 5 - 7, 25 - 12, 5 = -9, 75

f_3.1 = 2 * 6 - 9, 25 - 13, 5 = -10, 75 f_3.2 = 2 * 8 - 9, 25 – 10, 0 = -3, 25

f_3.4 = 2 * 11 - 9, 25 – 10, 0 = 2, 75 f_3.5 = 2 * 12 - 9, 25 - 12, 5 = 2, 25

f_4.1 = 2 * 26 - 14, 50 - 13, 5 = 24 f_4.3 = 2 * 11 - 14, 50 - 10, 5 = -3

f_4.2 = 2 * 11 - 14, 50 – 10, 0 = -2, 5 f_4.5 = 2 * 10 - 14, 50 - 12, 5 = -7, 0

f_5.1 = 2 * 14 - 16, 25 - 13, 5 = -1, 75 f_5.3 = 2 * 19 - 16, 25 - 10, 5 = 11, 25

f_5.2 = 2 * 16 - 16, 25 - 10, 0 = 5, 75 f_5.4 = 2 * 16 - 16, 25 – 10, 0 = 5, 75

Таблица 2.3.2 – Следующий этап решений

Пункты начала движения	Пункты конца движения
	1	2	3	4	5
1	∞	-9,25	-11,75	-9,25	24,25
2	-4,75	∞	-1,75	-1,25	-9,75
3	-10,75	-3,25	∞	2,75	2,25
4	24,00	-2,50	-3,20	∞	-7,00
5	-1,75	5,75	11,25	5,75	∞

1. Максимальные значения в матрице: 24.25, 24,00, 11.25, 5.75, 5.75, они вычеркиваются.

2. В 5 строке остается один не вычеркнутый элемент - Q5.1, он округляется, столбец 1 вычеркивается и элемент Q1,5 также вычеркивается.

3. Максимальные значения в матрице: 2.75, 2.25, -1.25 они вычеркиваются.

4. В 1 строке остается один не вычеркнутый элемент - Q1.4, он округляется, столбец 4 вычеркивается и элемент Q4.1 также вычеркивается.

5. В 3 строке остается один не вычеркнутый элемент- Q3.2, он округляется, столбец 2 вычеркивается и элемент Q2.3 также вычеркивается.

6. В 4 строке остается один не вычеркнутый элемент- Q4.3, он округляется, столбец 3 вычеркивается и элемент Q3.4 также вычеркивается.

7. В 2 строке в окончательном итоге остаётся один не вычеркнутый элемент, и он округляется.

Протяженность маршрута будет равна:

Z(5,1; 3,2; 4,3; 1,4; 2,5) = 14+8+11+5+5=43 минуты.

1

2

5

3

4

Рисунок 2.3.1 – Схема маршрута методом Дакея-Габра

Вывод: При расчете данным методом затраты времени составили 43 минуты, а это значит, что метод Дакея-Габра в данном варианте не является самым оптимальным способом решения.

.