(4 часа)
1. ЦЕЛЬ РАБОТЫ:
1.1. Научиться решать задачи динамического программирования.
2. СОДЕРЖАНИЕ РАБОТЫ:
2.1. Ознакомьтесь с теоретическим материалом;
2.2. Выполните задания из пункта 4;
2.3. Ответьте на контрольные вопросы.
3. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:
3.1. ПК;
3.2. MS Office 2007;
3.3. MathCAD.
4. ВЫПОЛНЕНИЕ:
4.1. Ознакомьтесь с условием задачи динамического программирования. Составьте ее математическую модель.
4.2. Решите задачи динамического программирования в ручную.
4.3. Решите задачи динамического программированная, использую MS Excel.
5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ:
В формализме решения задач методом динамического программирования будут использоваться следующие обозначения:
N – число шагов.
– вектор, описывающий состояние системы на k-м шаге.
– начальное состояние, т. е. состояние на 1-м шаге.
– конечное состояние, т. е. состояние на последнем шаге.
Xk – область допустимых состояний на k-ом шаге.
– вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния xk-1 в состояние xk.
Uk – область допустимых УВ на k-ом шаге.
Wk – величина выигрыша, полученного в результате реализации k-го шага.
S – общий выигрыш за N шагов.
– вектор оптимальной стратегии управления или ОУВ за N шагов.
Sk+1(
) – максимальный выигрыш, получаемый при переходе из любого состояния 
в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.
S1() – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления 
. Очевидно, что S = S1(), если –фиксировано.
Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.
Условие отсутствия последействия. Состояние , в которое перешла система за один k-й шаг, зависит от состояния 
и выбранного УВ 
и не зависит от того, каким образом система пришла в состояние , то есть
Аналогично, величина выигрыша Wk зависит от состояния и выбранного УВ , то есть
Условие аддитивности целевой функции. Общий выигрыш за N шагов вычисляется по формуле
Определение. Оптимальной стратегией управления называется совокупность УВ 
, то есть , в результате реализации которых система за N шагов переходит из начального состояния в конечное и при этом общий выигрыш S принимает наибольшее значение.
Условие отсутствия последействия позволяет сформулировать принцип оптимальности Белмана.
Принцип оптимальности. Каково бы ни было допустимое состояние системы 
перед очередным i-м шагом, надо выбрать допустимое УВ 
на этом шаге так, чтобы выигрыш Wi на i-м шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.
В качестве примера постановки задачи оптимального управления продолжим рассмотрение задачи управления финансированием группы предприятий. Пусть в начале i-го года группе предприятий 
выделяются соответственно средства: 
совокупность этих значений можно считать управлением на i-м шаге, то есть 
. Управление 
процессом в целом представляет собой совокупность всех шаговых управлений, то есть 
.
Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления оценивается показателем S. Возникает вопрос: как выбрать шаговые управления 
, чтобы величина S обратилась в максимум?
Поставленная задача является задачей оптимального управления, а управление, при котором показатель S достигает максимума, называется оптимальным. Оптимальное управление 
многошаговым процессом состоит из совокупности оптимальных шаговых управлений:
Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге 
(i=1,2,...N) и, значит, оптимальное управление всем процессом .
6. ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:
6.1. Номер практической работы, ее название, номер выполняемого варианта.
6.2. Номер задания.
6.3. Условие решаемой задачи.
6.4. Математическая модель задачи.
6.5. Решение ЗНЛП градиентным методом.
7. КОНТРОЛЬНЫЕ ВОПРОСЫ:
7.1. Условие отсутствия последействия.
7.2. Условие аддитивности функции.
7.3. Оптимальная стратегия.
7.4. Принцип Беллмана.
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА
1. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов.— М.: Высш. шк., 2006.— 319 с, ил.
2. Аронович Д.Б., Афанасьев М.Ю., Суворов Б.П. «Сборник задач по исследованию операций.» - М.: Издательство Московского университета, 2007.
3. Банди Б. Основы линейного программирования: Пер. сангл. — М.: Радио и связь, 2009. - 176 с: ил.
4. Вентцель Е. С. Исследование операций: задачи, принципы, методология.— 2-е изд., стер — М.І Наука. Гл. ред. физ.-мат. лит., 2007.—208 с
5. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб для вузов / Под ред. В.С. Зарубина, А П. Крищенко. - М.: Иэд-во МГГУ им. Н.Э. Баумана. 2000 - 436 с (Сер Математика в техническом университете. Вып. XX).
6. Калихман И. Л. Сборник задач по математическому программированию. Изд. 2-е, доп. и перераб. М., «Высш. школа», 2005. -270 с. с ил.
7. Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е изд., стереотип. — М.: ФИЗМАТЛИТ, 2004. — 264 с.
8. Косоруков О.А, Мищенко А.В. Исследование операций: Учебник / Косоруков О.А., Мищенко А.В. // Под общ. ред. д.э.н., проф. Н.П. Тихомирова. — М: Издательство «Экзамен», 2003. — 448 с.
9. Лунгу К. Н. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 2010. - 128 с.
10. Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. — М.: Издательский дом "Вильямс", 2009. — 912 с: ил.
11. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении. - М., Дело, 2010. - 440 с.
12. Шихин Е. В., Шикина Г. Е. Исследование операций: учеб. — М.: ТК Велби, Изд-во Проспект, 2006. - 280 с.
[1] Средний выигрыш равен частному от деления общего выигрыша на количество повторений игры.
