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

Решим задачу по аналогии:

1.Определим нижнюю границу (в каждой строке матрицы D найдем минимальный элемент).

 d_i = min(j) d_ij

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

 Затем вычесть его из элементов  рассматриваемой строки. В связи  с этим во вновь полученной  матрице в каждой строке будет  как минимум один ноль.

i  j	1	2	3	4	5	6
1	M	26	19	2	0	37
2	30	M	44	0	7	20
3	33	11	M	0	14	28
4	41	22	35	M	0	21
5	0	24	6	13	M	12
6	0	37	30	18	31	M

 Затем такую же операцию  редукции проводим по столбцам, для чего в каждом столбце  находим минимальный элемент:

 d_j = min(i) d_ij

i  j	M	26	19	2	0	6
1	M	26	19	2	0	37
2	30	M	44	0	7	20
3	33	11	M	0	14	28
4	41	22	35	M	0	21
5	0	24	6	13	M	12
6	0	37	30	18	31	M
dj	0	11	6	0	0	12

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

i  j	1	2	3	4	5	6
1	M	15	13	2	0	25
2	30	M	38	0	7	8
3	33	0	M	0	14	16
4	41	11	29	M	0	9
5	0	13	0	13	M	0
6	0	26	24	18	31	M

 

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

 H = ∑d_i + ∑d_j

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

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

i  j	1	2	3	4	5	6	di
1	M	15	13	2	0(2)	25	2
2	30	M	38	0(7)	7	8	7
3	33	0(11)	M	0(0)	14	16	0
4	41	11	29	M	0(9)	9	9
5	0(0)	13	0(13)	13	M	0(8)	0
6	0(18)	26	24	18	31	M	18
dj	0	11	13	0	0	8	0

 

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

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

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

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

i  j	2	3	4	5	6	di
1	15	13	2	0	M	0
2	M	38	0	7	8	0
3	0	M	0	14	16	0
4	11	29	M	0	9	0
5	13	0	13	M	0	0
dj	0	0	0	0	0	0

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

 ∑d_i + ∑d_j = 0

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

 H₁(6,1) = 99 + 0 = 99  <  117

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

 

 

 

 

 

 

 

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

i  j	2	3	4	5	6	di
1	15	13	2	0(2)	M	2
2	M	38	0(7)	7	8	7
3	0(11)	M	0(0)	14	16	0
4	11	29	M	0(9)	9	9
5	13	0(13)	13	M	0(8)	0
dj	11	13	0	0	8	0

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

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

i  j	2	4	5	6	di
1	15	2	0	M	0
2	M	0	7	8	0
3	0	0	M	16	0
4	11	M	0	9	0
dj	0	0	0	8	8

 

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

 ∑d_i + ∑d_j = 8

 

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

 H₁(5,3) = 99 + 8 = 107  <  112

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

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

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

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

i  j	4	5	6	di
1	2	0	M	0
2	0	7	0	0
4	M	0	1	0
dj	0	0	0	0

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

 ∑d_i + ∑d_j = 0

 

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

 H₁(3,2) = 107 + 0 = 107  <  110

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