Динамическое программирование. Оптимальное распределение ресурсов. Задача коммивояжера

 После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d_i и d_j называются константами приведения.

i  j	1	2	3	4	5	6
1	M	0	20	19	2	25
2	44	M	24	0	7	8
3	33	11	M	0	14	16
4	21	41	29	M	0	10
5	0	24	0	13	M	0
6	0	37	24	18	31	M

 

2. Сумма констант приведения (сумма всех вычитаемых на предыдущем шаге минимумов) определяет нижнюю границу дерева решений H:

 H = ∑d_i + ∑d_j

 H = 14+4+24+9+18+1+0+0+6+0+0+12 = 88

3. Оценим штраф за отклонение  от каждого нуля приведенной  матрицы: 

i j	1	2	3	4	5	6	di
1	M	0(13)	20	19	2	25	2
2	44	M	24	0(7)	7	8	7
3	33	11	M	0(11)	14	16	11
4	21	41	29	M	0(12)	10	10
5	0(0)	24	0(20)	13	M	0(8)	0
6	0(18)	37	24	18	31	M	18
dj	0	11	20	0	2	8	0

 

d(1,2) = 2 + 11 = 13; d(2,4) = 7 + 0 = 7; d(3,4) = 11 + 0 = 11; d(4,5) = 10 + 2 = 12; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 20 = 20; d(5,6) = 0 + 8 = 8; d(6,1) = 18 + 0 = 18;

 Максимальное значение штрафа равно 20 за отклонение от узла (5,3). Следовательно, первым включаем в маршрут движения коммивояжера участок (5"3).

Если не включать этот участок в  путь коммивояжера, то значение нижней границы увеличится на 20 и будет  равным 88 + 20 = 108.

4. Оценим нижнюю границу при  выборе узла (5,3). Для этого вычеркиваем из последней матрицы 5-ю строку и 3-ий столбец, при этом запретим возврат из 3-го пункта в 5-ый. Получим матрицу:

i  j	1	2	4	5	6	di
1	M	0	19	2	25	0
2	44	M	0	7	8	0
3	33	11	0	M	16	0
4	21	41	M	0	10	0
6	0	37	18	31	M	0
dj	0	0	0	0	8	8

Сумма констант приведения сокращенной  матрицы (сумма всех вычитаемых на предыдущем шаге минимумов):

 ∑d_i + ∑d_j = 8

Нижняя граница (5,3) равна:

 H₁(5,3) = 88 + 8 = 96  <  108

Корень дерева решений будет выглядеть следующим образом: 

 

 

 

 

 

 

 

5. Оценим штрафы для нулевых  элементов последней приведенной  матрицы: 

i  j	1	2	4	5	6	di
1	M	0(13)	19	2	17	2
2	44	M	0(0)	7	0(2)	0
3	33	11	0(8)	M	8	8
4	21	41	M	0(4)	2	2
6	0(39)	37	18	31	M	18
dj	21	11	0	2	2	0

d(1,2) = 2 + 11 = 13; d(2,4) = 0 + 0 = 0; d(2,6) = 0 + 2 = 2; d(3,4) = 8 + 0 = 8; d(4,5) = 2 + 2 = 4; d(6,1) = 18 + 21 = 39;

Максимальное значение 39 дает отказ от узла (6,1). Следовательно, включаем в маршрут движения участок 6"1. При этом отказ от участка приводит к увеличению стоимости проезда, таким образом Н + d(6,1) = 96 + 39 = 135.

6. Оценим нижнюю границу при выборе узла (6,1). Вычеркиваем из матрицы стоимостей строку, соответствующую 6-му пункту, и 1-ый столбец, при этом запретим возврат из 1-го пункта в 6-ый. Получим матрицу:

i  j	2	4	5	6	di
1	0	19	2	M	0
2	M	0	7	0	0
3	11	0	M	8	0
4	41	M	0	2	0
dj	0	0	0	0	0

 

Сумма констант приведения сокращенной  матрицы (сумма всех вычитаемых на предыдущем шаге минимумов):

 ∑d_i + ∑d_j = 0

 

 Нижняя граница (6,1) равна:

 H₁(6,1) = 96 + 0 = 96  <  135

7. Оценим штрафы для нулевых элементов последней приведенной матрицы:

i  j	2	4	5	6	di
1	0(13)	19	2	M	2
2	M	0(0)	7	0(2)	0
3	11	0(8)	M	8	8
4	41	M	0(4)	2	2
dj	11	0	2	2	0

d(1,2) = 2 + 11 = 13; d(2,4) = 0 + 0 = 0; d(2,6) = 0 + 2 = 2; d(3,4) = 8 + 0 = 8; d(4,5) = 2 + 2 = 4;

Максимальное значение 13 дает отказ от узла (1,2). Следовательно, включаем в маршрут движения участок 1"2. При этом отказ от участка приводит к увеличению стоимости проезда, таким образом Н + d(1,2) = 96 + 13 = 109.

8. После выбора узла (1,2) вычеркиваем  1-ую строку и 2-ой столбец, при этом запретим возврат из 2-го пункта в 1-ый. Получим матрицу:

i  j	4	5	6	di
2	0	7	0	0
3	0	M	8	0
4	M	0	2	0
dj	0	0	0	0

Сумма констант приведения сокращенной матрицы (сумма всех вычитаемых на предыдущем шаге минимумов):

 ∑d_i + ∑d_j = 0

 

 Нижняя граница (1,2) равна:

 H₁(1,2) = 96 + 0 = 96  <  109

9. Оценим штрафы для нулевых элементов последней приведенной матрицы:

 

i  j	4	5	6	di
2	0(7)	7	M	7
3	0(6)	M	6	6
4	M	0(7)	0(6)	0
dj	0	7	6	0

d(2,4) = 7 + 0 = 7; d(3,4) = 6 + 0 = 6; d(4,5) = 0 + 7 = 7; d(4,6) = 0 + 6 = 6;

 Максимальное значение 7 дает отказ от узла (2,4). Следовательно, включаем в маршрут движения участок 2"4. При этом отказ от участка приводит к увеличению стоимости проезда, таким образом Н + d(2,4) = 96 + 7 = 103.

10.После выбора узла (2,4) вычеркиваем 2-ую строку и 4-ый столбец, при этом запретим возврат 4-го пункта во 2-ой. Получим матрицу:

i  j	5	6	di
3	M	6	6
4	0	0	0
dj	0	0	6

 

Сумма констант приведения сокращенной матрицы:

 ∑d_i + ∑d_j = 6

Нижняя граница (2,4) равна:

 H₁ (2,4) = 96 + 6 = 102  <  103

 

 В соответствии с этой  матрицей включаем в маршрут  (3,6) и (4,5).

 В результате по дереву  ветвлений цикл образуют узлы:

(5,3), (3,6), (6,1), (1,2), (2,4), (4,5).  
Последовательность объезда городов: 5"3"6"1"2"4"5

Стоимость проезда по этому пути равна 102.

Длина маршрута равна = (5,3) + (3,6) + (6,1) + (1,2) + (2,4) + (4,5) = 24 + 52 + 1 + 14 + 4 + 9 = 104 

 

 

 

 

д) Выводы:

Оптимальным маршрутом коммивояжера будет маршрут E"C"F"A"B"D"E

е) Анализ решения

Для того чтобы провести анализ решим эту задачу, изменив некоторые показатели затрат на перемещение между городами.

Получим следующую матрицу: 

	A	B	C	D	E	F
A	M	40	33	16	14	51
B	34	M	48	4	11	24
C	57	35	M	24	38	52
D	50	31	44	M	9	30
E	18	42	24	31	M	30
F	1	38	31	19	32	M

 

Для удобства изложения везде ниже в платежной матрице заменим  имена городов (A, B, …, F) номерами соответствующих  строк и столбцов (1, 2, …, 6).

i  j	1	2	3	4	5	6
1	M	40	33	16	14	51
2	34	M	48	4	11	24
3	57	35	M	24	38	52
4	50	31	44	M	9	30
5	18	42	24	31	M	30
6	1	38	31	19	32	M