ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. 1.1.Научиться решать задачи динамического программирования
(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] Средний выигрыш равен частному от деления общего выигрыша на количество повторений игры.