ПОСТРОЕНИЕ КОЛЬЦЕВОГО МАРШРУТА

Метод ветвей границ

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

Множество «S» (0) состоит из (n-1)! Циклов, которые разбиваются на 2 не пересекающихся множества «S» (ij) и «S» (ij) для которых вычисляются их оценки. Далее подмножества с минимальной оценкой разбивается вновь на 2 не пересекающихся подмножества, и вычисляются их оценки. Это разбиение продолжается до тех пор, пока не получится подмножество, содержащее замкнутый маршрут (цикл) удовлетворяющий наложенным ограничениям.

Этот кольцевой маршрут считается оптимальным. Ограничивающими условиями могут быть минимальный пробег автомашины или минимальные затраты времени на объезд маршрута.

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

Пункты начала движения	Пункты конца движения
	∞
		∞
			∞
				∞
					∞

· Выбираем самый минимальный элемент из каждой строки и записываем в графу константа приведения, вычитаем из каждого элемента константу приведения;

Таблица 2.1.2 - Приведенная матрица (по строкам)

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

Таблица 2.1.3 - Приведенная матрица (по столбцам)

Пункты начала движения	Пункты конца движения
	∞	1 0	0 0	1 0	19 19
	3 3	∞	3 3	3 2	0 0
	0 0	2 1	∞	5 4	6 6
	16 16	1 0	1 1	∞	0 0
	0 0	2 1	5 5	2 1	∞
Конст.

· Сумма констант = 41. Так как во всех строках и столбцах есть «0», то рассчитываем для всех нулевых элементов приведенной матрицы значения Q (i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q (i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

Q3.1=0+1=1 Q1.3=0+1=1

Q5.1=0+1=1 Q1.4=1+0=1

Q1.2=0+0=0 Q2.5=0+2=2

Q4.2=0+0=0 Q4.5=0+0=0

· Выбираем наибольшее значение и осуществляем ветвление (множество развивается на 2 непересекающихся множества). Наибольшее значение Q2.5. Столбец и строка данного элемента вычеркивается, в клетке Q5,2 ставится бесконечность и составляется ветвление.

Все циклы

2.5

2.5

 

43 41

 

Рисунок 2.1.1 - Начало ветвления дуги 2.5

Рассчитываем нижние границы подмножества.

Нижние границы всех циклов, есть сумма констант приведения.

h 1=4+5+6+10+14+1+1=41 h 1+Q2.5=41+2=43

Далее проводим вторую итерацию:

Так как во всех строках и столбцах есть «0», то константу приведения мы не рассчитываем, а считаем сразу элемент Q (i, j)

Для проведения второй итерации выполняются все те же операции вычисления как при первой итерации.

Таблица 2.1.4 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	∞
			∞
				∞
		∞

 

· Сумма констант = 0. Так как во всех строках и столбцах есть «0», то рассчитываем для всех нулевых элементов приведенной матрицы значения Q (i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q (i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

· Получилось 5 возможных вариантов.

Выбираем первое наибольшее значение и осуществляем ветвление. Наибольшее значение Q 3.1. Столбец и строка данного элемента вычеркивается, в клетке Q 1.3 ставится бесконечность и составляется ветвление.

 

Все циклы

2.5

2.5

 

43 41

42 41

3.1

3.1

 

 

Рисунок 2.1.2 - Начало ветвления дуги 3.1

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=41+0=41 h1+h2+Q3.1=41+0+1=42

Таблица 2.1.5 – Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения	Конст.
		∞
			∞
	∞	5 4	1 0

 

· Сумма констант = 1. Сделав нули в необходимой строке, рассчитываем для всех нулевых элементов приведенной матрицы значения Q (i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q (i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0» находящихся в i-строке и в j-столбце.

 

Q1.3=0+1=1 Q4.2=0+1=1

Q5.4=0+4=4 Q1.4=0+0=0

Q1.2=0+0=0

Рассчитываем нижние границы подмножества.

h3=1 h1+h2+h3=41+0+1=42 h1+h2+Q5.4=41+0+4=45

 

Все циклы

2.5

2.5

 

 

43 41

 

42 41

3.1

3.1

 

5.4

45

5.4

42

 

 

Рисунок 2.1.3 - Начало ветвления дуги 5.4

Таблица 2.1.6 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
		∞

 

 

На этом ветвление заканчивается. Включение в варианты дуг Q_4.3 и Q_1.2 образуют дерево.

Полученный вариант: Z (2.5, 3.1, 5.4, 4.3, 1.2)

Затраты времени в первом варианте составили 42 минуты.

 

Рисунок 2.1.4 – Схема кольцевого маршрута методом ветвей

Выбираем второе наибольшее значение и осуществляем ветвление. Наибольшее значение Q5.1. Столбец и строка данного элемента вычеркивается, в клетке Q1,5 ставится бесконечность и составляется ветвление.

Таблица 2.1.7 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	∞
			∞
				∞
		∞

 

 

· Сумма констант = 0. Так как во всех строках и столбцах есть «0», то рассчитываем для всех нулевых элементов приведенной матрицы значения Q(i и j). Для каждой клетки содержащей «0» записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца.

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

Все циклы

2.5

2.5

 

43 41

 

 

5.1

5.1

42 41

 

 

Рисунок 2.1.5 - Начало ветвления дуги 5.1

h 2=0 h1+h2=41+0=41 h1+h2+Q5.1=41+0+1=42

Таблица 2.1.8 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
			Конст.
	1 0	∞	4 3
			∞

 

· Сумма констант = 1. Сделав нули в необходимой строке, рассчитываем для всех нулевых элементов приведенной матрицы значения Q(i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

Q3.2=0+3=3 Q4.2=0+1=1

Q1.3=0+1=1 Q1.4=0+1=1

Q1.2=0+0=0

Рассчитываем нижние границы подмножества.

h 3=1 h1+h2+h3=41+0+1=42 h1+h2+Q3.2=41+0+3=44

· h AQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQA4 /SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQD6 FqhzggQAAKoTAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9jLnhtbFBLAQItABQABgAIAAAA IQBRDUhz4gAAAAoBAAAPAAAAAAAAAAAAAAAAANwGAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAQA BADzAAAA6wcAAAAA ">

Все циклы

2.5

2.5

Для каждой клетки содержащей «0» приведенной матрицы записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0», находящихся в i-строке и в j-столбце.

 

43 41

 

 

5.1

42 41

5.1

 

44 42

3.2

3.2

 

 

Рисунок 2.1.6 - Начало ветвления дуги 3.2

Таблица 2.1.9 - Приведенная матрица (четвёртая итерация)

Пункты[A1] начала движения	Пункты конца движения
		∞

 

 

На этом ветвление заканчивается. Включение в варианты дуг Q_4.3 и Q_1.4 образуют дерево.

Полученный вариант: Z (2.5, 5.1, 3.2, 4.3, 1.4)

Затраты времени во втором варианте составили 42 минуты.

 

l JJqEhZ5kKXk8xVIHsmE4WIxzYWE8MGF2gkml9QAs7wYe8hNU5NEdwJO7wQMiv+wsDGCjrAt/I4Dd sWTZ5x8d6HUnCy5dvc+tzdbgDGavDv8lDfmv+wz/+asXPwAAAP//AwBQSwMEFAAGAAgAAAAhABXU 3cjfAAAACAEAAA8AAABkcnMvZG93bnJldi54bWxMj8tOwzAQRfdI/IM1SOyoTVTSEuJUPMSiQgi1 YcHSjadJRDyOYqdJ/55hBcvRvTr3TL6ZXSdOOITWk4bbhQKBVHnbUq3hs3y9WYMI0ZA1nSfUcMYA m+LyIjeZ9RPt8LSPtWAIhcxoaGLsMylD1aAzYeF7JM6OfnAm8jnU0g5mYrjrZKJUKp1piRca0+Nz g9X3fnQakrA6j09vTdzR8ePdl9uX6Wtban19NT8+gIg4x78y/OqzOhTsdPAj2SA6Zqi7JVc13Kcg OF+qNAFx0LBapyCLXP5/oPgBAAD//wMAUEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAA AAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACU AQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEAJyQ5UQoCAAAd BAAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEAFdTdyN8A AAAIAQAADwAAAAAAAAAAAAAAAABkBAAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAHAF AAAAAA== " strokecolor="#4f81bd [3204]" strokeweight="3pt"> I NAkbPclS8niKlQ5kw3CwGOfCwnhgwuwEk0rrAVjeDzzkJ6jIozuAJ/eDB0Su7CwMYKOsC38jgN2x ZdnnHx3odScLrl29z0+brcEZzG9y+C9pyH/dZ/jPX738AQAA//8DAFBLAwQUAAYACAAAACEAb0av V+EAAAAKAQAADwAAAGRycy9kb3ducmV2LnhtbEyPy07DMBBF90j8gzVI7KiTtCQ0xKl4iEWFEGrD oks3duOIeBzFTpP+PcMKlqN7dO+ZYjPbjp314FuHAuJFBExj7VSLjYCv6u3uAZgPEpXsHGoBF+1h U15fFTJXbsKdPu9Dw6gEfS4FmBD6nHNfG22lX7heI2UnN1gZ6BwargY5UbnteBJFKbeyRVowstcv Rtff+9EKSHx2GZ/fTdjh6fPDVdvX6bCthLi9mZ8egQU9hz8YfvVJHUpyOroRlWedgOX9ck2ogFUW AyNglUUpsCMlSZwCLwv+/4XyBwAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAA AAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAA lAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAAdfPXQJAgAA HQQAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAG9Gr1fh AAAACgEAAA8AAAAAAAAAAAAAAAAAYwQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABx BQAAAAA= " strokecolor="#4f81bd [3204]" strokeweight="3pt">

 

Рисунок 2.1.7 – Схема кольцевого маршрута методом ветвей

Выбираем третье наибольшее значение и осуществляем ветвление. Наибольшее значение Q1.3. Столбец и строка данного элемента вычеркивается, в клетке Q3,1 ставится бесконечность и составляется ветвление.

Таблица 2.1.10 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	∞
			∞
				∞
		∞

 

 

· Сумма констант приведения = 0. Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца.

 

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

Все циклы

2.5

2.5

 

42 41

 

 

1.3

1.3

42 41

 

 

Рисунок 2.1.8 - Начало ветвления дуги 1.3

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=41+0=41 h1+h2+Q1.3=41+0+1=42

Таблица 2.1.11 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
			Конст.
	∞	1 0	4 3 2
			∞
		∞	1 0
Конст.

Q3.2=0+2=1 Q5.1=0+2=2

Q4.2=0+16=16 Q5.4=0+2=2

Рассчитываем нижние границы подмножества.

h 3=2 h1+h2+h3=41+0+2=43 h1+h2+Q4.2=41+0+16=57

Все циклы

2.5

2.5

 

43 41

 

 

42 41

1.3

1.3

 

4.2

57 43

4.2

 

Рисунок 2.1.9 - Начало ветвления дуги 4.2

Таблица 2.1.12 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
	∞

 

На этом ветвление заканчивается. Включение в варианты дуг Q_5.1 и Q_3.4 образуют дерево.

Полученный вариант: Z (2.5, 1.3, 4.2, 5.1, 3.4)

Затраты времени в третьем варианте составили 43 минуты.

 

Рисунок 2.1.10 – Схема кольцевого маршрута методом ветвей

Выбираем четвёртое наибольшее значение и осуществляем ветвление. Наибольшее значение Q1.4. Столбец и строка данного элемента вычеркивается, в клетке Q4.1 ставится бесконечность и составляется ветвление.

 

Таблица 2.1.13 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	∞
			∞
				∞
		∞

 

 

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Q1.2=0+0=0 Q4.2=0+1=1 (5)

1.4

Все циклы

2.5

2.5

 

43 41

 

 

1.4

42 41

 

 

Рисунок 2.1.11 Начало ветвления дуги 1.4

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=41+0=41 h1+h2+Q1.4=41+0+1=42

Таблица 2.1.14 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
			∞
	∞		1 0
		∞	5 4

 

· Сумма констант приведения = 0. Сделав нули в необходимой строке, рассчитываем для всех нулевых элементов приведенной матрицы значения Q(i и j). Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0» находящихся в i-строке и в j-столбце.

Q3.1=0+1=1 Q4.2=0+1=1

Q5.1=0+4=4 Q4.3=0+1=1

Рассчитываем нижние границы подмножества.

h 3=1 h1+h2+h3=41+0+1=42 h1+h2+Q5.1=41+0+4=45

· Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j). Определяется как сумма минимального элемента i-строки и минимального элемента j-столбца, исключая «0» находящихся в i-строке и в j-столбце.

Все циклы

2.5

2.5

 

 

43 41

 

 

1.4

42 41

1.4

 

45 42

5.1

5.1

 

 

Рисунок 2.1.12 Начало ветвления дуги 5.1

Таблица 2.1.15 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
		∞

 

 

На этом ветвление заканчивается. Включение в варианты дуг Q_4.3 и Q_3.2 образуют дерево.

Полученный вариант: Z (2.5, 1.4, 5.1, 4.3, 3.2)

Затраты времени в четвёртом варианте составили 45 минут.

 

 

 

Рисунок 2.1.13 – Схема кольцевого маршрута методом ветвей

Выбираем пятое наибольшее значение и осуществляем ветвление. Наибольшее значение Q4.2. Столбец и строка данного элемента вычеркивается, в клетке Q2.4 ставится бесконечность и составляется ветвление.

Таблица 2.1.16 - Приведенная матрица (вторая итерация)

Пункты начала движения	Пункты конца движения
	∞
			∞
				∞
		∞

 

 

· Сумма констант приведения = 0. Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j).

Q3.1=0+1=1 (1) Q1.3=0+1=1 (3)

Q5.1=0+1=1 (2) Q1.4=1+0=1 (4)

Все циклы

2.5

2.5

Q1.2=0+0=0 Q4.2=0+1=1 (5)

4.2

4.2

 

43 41

 

 

42 41

 

 

Рисунок 2.1.14 Начало ветвления дуги 4.2

Рассчитываем нижние границы подмножества.

h 2=0 h1+h2=4+0=41 h1+h2+Q4.2=41+0+1=42

Таблица 2.1.17 - Приведенная матрица (третья итерация)

Пункты начала движения	Пункты конца движения
	∞
		∞

 

· Сумма констант приведения = 0. Для каждой клетки содержащей «0» приведенной матрицы в правом верхнем углу клетки записываем значения Q(i и j).

Q3.1=0+4=4 Q1.3=0+4=4

Q5.1=0+5=5 Q1.3=0+4=4

Рассчитываем нижние границы подмножества.

h 3=0 h1+h2+h3=41+0+0=41 h1+h2+Q5.1=41+0+5=46

Все циклы

2.5

2.5

 

 

43 41

 

 

4.2

4.2

42 41

 

 

5.1

5.1

46 41

 

 

Рисунок 2.1.15 Начало ветвления дуги 5.1

Таблица 2.1.18 - Приведенная матрица (четвёртая итерация)

Пункты начала движения	Пункты конца движения
	∞

 

 

На этом ветвление заканчивается. Включение в варианты дуг Q_1.3 и Q_3.4 образуют дерево.

Полученный вариант: Z (2.5, 4.2, 5.1, 1.3, 3.4)

Затраты времени в пятом варианте составили 41 минута.

 

 

 

Рисунок 2.1.16 – Схема кольцевого маршрута методом ветвей

Вывод: Данный вариант получился наиболее оптимальным из пяти предложенных вариантов. Затраты времени при расчете методом ветвей и границ получились минимальными, и составили 41 минуту. Рассмотренный метод «Ветвей и границ» является точным и обеспечивает возможность получения оптимального маршрута, однако, применение этого метода без электронных средств требует проведения громоздких расчетов.

Метод Дакея

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

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

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

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

Пункты начала движения	Пункты конца движения
	∞
		∞
			∞
				∞
					∞

 

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 минут.

 

 

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

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

 

 

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

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

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

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
	∞					9,25
		∞				7,25
			∞			9,25
				∞		14,50
					∞	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[A2] – 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 – Следующий этап решений

Пункты начала движения	Пункты конца движения
	∞	-9,25	-11,75	-9,25	24,25
	-4,75	∞	-1,75	-1,25	-9,75
	-10,75	-3,25	∞	2,75	2,25
	24,00	-2,50	-3,20	∞	-7,00
	-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 минуты.

 

 

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

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

.

 

ЗАКЛЮЧЕНИЕ

В данной курсовой работе использовались три метода для расчета затрат времени: метод ветвей границ, метод Дакея и метод Дакея-Габра.

При расчете методов ветвей границ было 5 вариантов использования разных дуг для расчета затрат времени. Варианты, где использовалась дуги 3.1. 5.1. и 1.4. не целесообразно использовать, т.к. время при использовании данных дуг по правой ветке начало увеличиваться (стало 42 минуты), когда до этого время было 41 минута. При использовании дуги 1.3. стало понятно, что этот вариант не стоит рассматривать, так как там время ещё больше увеличивается (43 минуты). А вот при использовании дуги 4,2 время составило 41 минуту и на протяжении решения не увеличивалось. Следовательно, последний (пятый) вариант с использованием дуги 4,2 целесообразно использовать.

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

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

Исходя из этого можно сделать общий вывод.

Вывод:Кольцевой маршрут в данном случае лучше прокладывать воспользовавшись методом ветвей и границ, с использованием дуги 4.2., так как время на затраты составило 41 минуту. Всё это даёт возможность сократить 1 работника, что позволит уменьшить расходы на топливо и заработную плату.