Динамическое программирование. 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-м шаге.

– конечное состояние, т. е. состояние на последнем шаге.

X_k – область допустимых состояний на k-ом шаге.

– вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния x_k-1 в состояние x_k.

U_k – область допустимых УВ на k-ом шаге.

W_k – величина выигрыша, полученного в результате реализации k-го шага.

S – общий выигрыш за N шагов.

– вектор оптимальной стратегии управления или ОУВ за N шагов.

S_k+1() – максимальный выигрыш, получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.

S₁() – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления . Очевидно, что S = S₁(), если –фиксировано.

Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.

Условие отсутствия последействия. Состояние , в которое перешла система за один k-й шаг, зависит от состояния и выбранного УВ и не зависит от того, каким образом система пришла в состояние , то есть

Аналогично, величина выигрыша W_k зависит от состояния и выбранного УВ , то есть

Условие аддитивности целевой функции. Общий выигрыш за N шагов вычисляется по формуле

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

Условие отсутствия последействия позволяет сформулировать принцип оптимальности Белмана.

Принцип оптимальности. Каково бы ни было допустимое состояние системы перед очередным i-м шагом, надо выбрать допустимое УВ на этом шаге так, чтобы выигрыш W_i на 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] Средний выигрыш равен частному от деления общего выигрыша на количество повторений игры.