Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

ВОЛГО-ВЯТСКАЯ АКАДЕМИЯ ГОСУДАРСТВЕННОЙ СЛУЖБЫ

Факультет управления, экономики и права (очное отделение)

Кафедра математики и системного анализа

Курсовая

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

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

Выполнила: Дарья Юрьевна Мануйлова

Студент группы: ГМУОб-31

Научный руководитель: Бибишкина
Татьяна Евгеньевна

Нижний Новгород

2011 г.

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

а) Содержательная история
Совет директоров фирмы рассматривает предложения по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырёх предприятиях, принадлежащих фирме. Для модернизации предприятия совет директоров инвестировал средства в объёме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причём на одно предприятие можно осуществить только одну инвестицию.

б)Математическая модель
V_n* = max {f_n (S_n-1, x_n)},

x_n= _φ(S_n-1)_,S_n-1- x_{n =} S_n, S_n-1= S_n + x_n;

V_n-1* = max {f_n-1 (S_n-2, x_n-1) + V_n* },

^{xn-1}

x_n-1= _φ(S_n-2);

V_n-2* = max {f_n-2 (S_n-3, x_n-2) + V_{n, n-1}* }.

^{^xn-2}

в) Метод решения

Метод динамического программирования.
В основе динамического метода программирования лежит принцип оптимальности Р. Беллмана, сформулированный впервые в 1953 г.: каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно, в совокупности с оптимальным управлением на всех последующих шагах, включая данный.

Согласно этому принципу следует, что если траектория движения системы из некоторой промежуточной точки до конечной точки является оптимальной, то она не зависит от того, по какой траектории система перешла из начальной точки движения в рассматриваемую, промежуточную. Беллманом были сформулированы и условия, при которых принцип верен. Основное требование – процесс управления должен быть без обратной связи, т. е. управление на данном шаге не должно оказывать влияние на предшествующие шаги. Решение на каждом шаге оказывается наилучшим с точки зрения управления в целом.

г) Решение
Исходные данные

Инвестиции (млн. р.)	Прирост выпуска продукции (млн. р.)
Инвестиции (млн. р.)	Предприятие 1	Предприятие 2	Предприятие 3	Предприятие 4
50	5	7	6	4
100	9	10	8	11
150	21	20	21	19
200	33	34	32	35
250	38	39	40	41

Шаг 1. Проведем процесс распределения ресурса. Для этого предположим, что задача полностью решена и осталось только распределить оставшийся ресурс Х₁₂между 1-ым и 2-ым предприятием. Поскольку мы не знаем заранее, какова будет величина Х₁₂, то мы должны рассмотреть все возможности (Х₁₂= 50, 100, 150…) находя каждый раз оптимальные сочетания между Х₁ и Х₂. При этом, очевидно, мы должны соблюдать условие Х₁ + Х₂ = Х₁₂.

X_1,2	Х₁	Х₂	V_1,2
50	50	0	5
50	0	50	7
100	100	0	9
	50	50	12
	0	100	10
150	150	0	21
	100	50	16
	50	100	15
	0	150	20
200	200	0	33
	150	50	28
	100	100	19
	50	150	25
	0	200	34
250	250	0	38
	200	50	40
	150	100	31
	100	150	29
	50	200	39
	0	250	39

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

X₁₂₃	Х₁₂	Х*₃	V*₁₂₃
50	50	0	7
50	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	32
250	250	0	40
	200	50	40
	150	100	29
	100	150	33
	50	200	39
	0	250	40

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

X₁₂₃₄	Х*₁₂₃	Х*₄	V*₁₂₃₄
50	50	0	7
50	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	34
	150	50	25
	100	100	24
	50	150	26
	0	200	35
250	250	0	40
	200	50	38
	150	100	32
	100	150	32
	50	200	42
	0	250	41

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

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

i	1	2	3	4
X_i	0	50	0	200

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

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

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

Исходные данные

Инвестиции (млн. р.)	Прирост выпуска продукции (млн. р.)
Инвестиции (млн. р.)	Предприятие 1	Предприятие 2	Предприятие 3	Предприятие 4
50	5	7	6	4
100	9	10	8	11
150	21	20	21	19
200	34	32	35	33
250	38	39	40	41

X_1,2	Х₁	Х₂	V_1,2
50	50	0	5
50	0	50	7
100	100	0	9
	50	50	12
	0	100	10
150	150	0	21
	100	50	16
	50	100	15
	0	150	20
200	200	0	34
	150	50	28
	100	100	19
	50	150	25
	0	200	32
250	250	0	38
	200	50	41
	150	100	31
	100	150	29
	50	200	37
	0	250	39

X₁₂₃	Х₁₂	Х*₃	V*₁₂₃
50	50	0	7
50	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

X₁₂₃₄	Х*₁₂₃	Х*₄	V*₁₂₃₄
50	50	0	7
50	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
X_i	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	d_i
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
d_j	0	0	6	0	0	12

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

	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

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

i j	1	2	3	4	5	6	d_i
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

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	0	0	6	0	0	12

	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

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

i j	1	2	3	4	5	6	d_i
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

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	0	0	6	0	0	12

	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

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

i j	1	2	3	4	5	6	d_i
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

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	0	0	6	0	0	12