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

Серой заливкой выделены оптимальные  значения величин Х₁ + Х₂, соответствующих в сумме возможному объему выделенных этим предприятиям средств.  
Шаг 2. Затем, рассматривая предприятия 1 и 2 как единый комплекс (1,2), выполним аналогичную процедуру распределения ресурса между ним и 3-им предприятием. Для вычисления значения общей прибыли при этом будем пользоваться уже найденным на предыдущем шаге оптимальным решением. Далее все три предприятия опять-таки рассматриваются как некий единый комплекс (1,2,3).

X123	Х12	Х*3	V*123
50	50	0	7
	0	50	6
100	100	0	12
	50	50	13
	0	100	8
150	150	0	21
	100	50	18
	50	100	15
	0	150	21
200	200	0	34
	150	50	27
	100	100	20
	50	150	28
	0	200	35
250	250	0	40
	200	50	40
	150	100	29
	100	150	33
	50	200	42
	0	250	40

 

 Шаг 3. Выполним аналогичную предыдущему процедуру распределения ресурса между комплексом (1,2,3) и предприятием 4. Полученный результат и даст нам оптимальное решение поставленной задачи.

X1234	Х*123	Х*4	V*1234
50	50	0	7
	0	50	4
100	100	0	13
	50	50	11
	0	100	11
150	150	0	21
	100	50	17
	50	100	18
	0	150	19
200	200	0	35
	150	50	25
	100	100	24
	50	150	26
	0	200	33
250	250	0	40
	200	50	39
	150	100	32
	100	150	32
	50	200	40
	0	250	41

Из таблицы 3-го шага имеем V* (250) = 41. То есть максимальный доход всей системы при количестве средств 250 равен 41

 

Согласно полученным данным оптимальным  будет следующее распределение  ресурсов:

i	1	2	3	4
Xi	0	0	0	250

 

Прирост выпуска продукции будет максимальным, если распределить инвестиции следующим образом: 250 млн. р. четвертому предприятию. Это обеспечит максимальный доход, равный 41 млн. р.

 

 

2. Задача коммивояжера

 

а) Содержательная история

Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей: 

	A	B	C	D	E	F
A	M	14	40	33	16	51
B	48	M	34	4	11	24
C	57	35	M	24	38	52
D	30	50	44	M	9	31
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	14	40	33	16	51
2	48	M	34	4	11	24
3	57	35	M	24	38	52
4	30	50	44	M	9	31
5	18	42	24	31	M	30
6	1	38	31	19	32	M

 

б) Математическая модель задачи коммивояжера

    (1)

При ограничениях

 

 

Условия (2) – (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)).

 

в) Метод решения – метод ветвей и границ

 В задаче коммивояжера для  формирования оптимального маршрута  объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений.  
Вершина (i,j) соответствует подмножеству всех маршрутов, содержащих ребро (i,j), а вершина (i*,j*) — подмножеству всех маршрутов, где это ребро отсутствует.  
Процесс разбиения на эти подмножества можно рассматривать как ветвление дерева. Поэтому метод называется методом поиска по дереву решений, или методом ветвей и границ.  
Метод ветвей и границ представляет собой алгоритм направленного перебора множества вариантов решения задачи. Сущность метода ветвей и границ состоит в том, что от корня дерева ветвятся не все вершины.

 

г) Решение задачи

1. Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.

 d_i = min(j) d_ij

i  j	1	2	3	4	5	6	di
1	M	14	40	33	16	51	14
2	48	M	34	4	11	24	4
3	57	35	M	24	38	52	24
4	30	50	44	M	9	31	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	0	26	19	2	37
2	44	M	30	0	7	20
3	33	11	M	0	14	28
4	21	41	35	M	0	22
5	0	24	6	13	M	12
6	0	37	30	18	31	M

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

 d_j = min(i) d_ij

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