8

СПР_лаб4

Лабораторная работа №4

Тема: Использование метода динамического программирования при решении задач распределения ресурсов.

Цель работы:

• изучить условия применения метода динамического программирования для решения задачи распределения ресурсов;

• изучить алгоритмы использования метода динамического программирования;

• реализовать использование критериев в среде MS Excel;

• выполнить программную реализацию критериев и проверить адекватность полученных результатов.

Порядок выполнения работы

1. Изучить суть и особенности метода динамического программирования и принципа оптимальности Беллмана.

2. Рекуррентные соотношения Беллмана для своего варианта задачи.

3. Выполнить представление исходных данных и поиск оптимального решения с применением метода Беллмана в среде MS Excel.

4. Выполнить графическое представление задачи. Объяснить полученный результат, показав оптимальное решение на графе. Продемонстрировать ход поиска решения преподавателю.

5. Выполнить программную реализацию критериев согласно индивидуальному заданию.

6. Проверить адекватность работы программы. Продемонстрировать преподавателю работоспособность разработанного программного обеспечения.

7. Оформить отчет по лабораторной работе.

8. Защитить лабораторную работу.

Содержание отчета

1. Тема работы.

2. Цель работы.

3. Индивидуальное задание.

4. Описание хода выполнения работы.

5. Интерпретация полученных результатов.

6. Выводы.

Выполнение лабораторной работы оценивается из 10 баллов:

1. реализация критериев в MS Excel 3 балла;

2. программная реализация критериев 4 балла;

3. оформление отчета 1 балл;

4. защита лабораторной работы 2 балла.

Индивидуальные задания

1. Согласно индивидуальным заданиям (табл. 1 и табл. 2) найти наилучшие решения, выполнив необходимые вычисления в MS Excel.

2. Выполнить программную реализацию поиска многошаговых решений.

Таблица 1

№ вар	К-во шагов	К-во предприятий		№ вар	К-во шагов	К-во предприятий
1	5	2		9	5	2
2	4	3		10	4	3
3	3	4		11	3	4
4	4	3		12	4	3
5	5	3		13	5	3
6	4	4		14	4	4
7	4	5		15	4	5
8	5	5		16	5	5
Данные для вариантов 1-8				Данные для вариантов 9-16
	f1=2b	g1=0.1b			f1=3b	g1=0.5b
	f2=3c	g2=0.3c			f2=4c	g2=0.4c
	f3=2d	g3=0.2d			f3=3d	g3=0.3d
	f4=4e	g4=0.4e			f4=3e	g4=0.3e
	f5=1.5f	g5=0.4f			f5=2f	g5=0.3f

Таблица 2

Краткие теоретические сведения

1 Динамическое программирование

Суть динамического программирования заключается в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая задача. При этом осуществляется переход к еще более простым задачам и так далее, пока не доходят до тривиальной.

Динамическое программирование обычно применяется к задачам, в которых искомый ответ состоит из частей, каждая из которых в свою очередь дает оптимальное решение некоторой подзадачи.

Динамическое программирование полезно, если на разных путях многократно встречаются одни и те же подзадачи; основной технический приём - запоминать решения встречающихся подзадач и использовать их, если та же подзадача встретится вновь.

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

Пример решения задач

Задача 1

Для двух предприятий выделено а единиц средств. Необходимо распределить все средства в течение 4 лет так, чтобы доход был наибольшим. Известно, что доход от х единиц средств, вложенных в первое предприятие, равен f₁(x), а доход от y единиц средств, вложенных во второе предприятие, равен f₂(y). К концу года остаток средств составляет g₁(x) для первого предприятия и g₂(y) для второго предприятия. Данные для решения задачи сведены в табл. 3. Задачу необходимо решить методом динамического программирования.

Таблица 3

а	f1	g1	f2	g2
1000	3х	0,1х	2у	0,5у

Решение задачи.

Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

Обозначим a_k=x_k+y_k средства, которые распределяются на k–ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на k –ом шаге:

z_k = f₁(x_k) + f₂(a_k − x_k) = 3x_k + 2(a_k − x_k) = 2a_k + x_k

Остаток средств от обоих предприятий на k –ом шаге:

a_k+1 = g₁(x_k) + g₂(a_k - x_k) = 0,1x_k + 0,5(a_k - x_k ) = 0,5a_k - 0,4x_k

Обозначим z_k^*(a_k) максимальный доход, полученный от распределения средств a_k между двумя предприятиями с k -го шага до конца рассматриваемого периода.

Рекуррентные соотношения Беллмана для этих функций:

z₄^*(a₄) = max{2a_k + x_k} , 0<= x₄ <= a₄,

z_k^*(a_k) = max{2a_k + x_k + z_k+1^*(0,5a_k - 0,4x_k)} , 0<= x_k <= a_k

Проведем оптимизацию, начиная с четвертого шага.

4-й шаг.

Оптимальный доход равен:

z₄^*(a₄) = max{2a_k + x_k} = 3a₄, 0<= x₄ <= a₄,

т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при x₄ = a₄.

3-й шаг.

z₃^*(a₃) = max{2a₃ + x₃ + (0,5a₃ – 0,4x₃)} = max{3,5a₃ – 0,2x₃)}= 3,5a₃, 0<= x₃ <= a₃,

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₃ = 0.

2-й шаг.

z₂^*(a₂) = max{2a₂ + x₂ + 3,5(0,5a₂ – 0,4x₂)} = max{3,75a₂ – 0,4x₂)}= 3,75a₂, 0<= x₂ <= a₂,

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. x₂ = 0.

1-й шаг.

z₁^*(a₁) = max{2a₁ + x₁ + 3,75(0,5a₁ – 0,4x₁)} = max{3,875a₁ – 0,5x₁)}= 3,875a₁, 0<= x₁ <= a₁,

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₁ = 0.