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

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

Курсовая

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

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

Студент группы: ГМУОб-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…) находя каждый раз оптимальные сочетания между Х₁ и Х₂. При этом, очевидно, мы должны соблюдать условие Х₁ + Х₂ = Х₁₂.

X1,2	Х1	Х2	V1,2
50	50	0	5
	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).

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	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. Полученный результат и даст нам оптимальное решение поставленной задачи.

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	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
Xi	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

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

X1,2	Х1	Х2	V1,2
50	50	0	5
	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