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

Найдем стандартную ошибку предсказания для нашего примера:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Проверим  гипотезу о значимости выборочного  коэффициента корреляции при уровне значимости р=0,05

 

 

 

 

 

 

Поскольку t>t0.05, то на уровне значимости 0,05 отклонением гипотезу Н0, т.е. коэффициент регрессии является статистически значимым.

 

 

 

 

 

 

 

Решение задачи в Excel:

 

В меню СЕРВИС выбираем команду ПОИСК РЕШЕНИЯ (если нет такого пункта меню, то сначала  необходимо в меню СЕРВИС выбрать  команду НАДСТРОЙКИ, в появившемся диалоговом окне установить флажок на пункте ПОИСК РЕШЕНИЯ и нажать кнопку ОК; теперь в меню СЕРВИС будет команда ПОИСК РЕШЕНИЯ).

 

В окне ПОИСК  РЕШЕНИЯ введем необходимые параметры:

– укажем целевую ячейку (В8) – та, в которой  вычисляется значение целевой функции;

– выберем  переключатель МИНИМАЛЬНОМУ ЗНАЧЕНИЮ (целевую функцию необходимо минимизировать);

– в поле ИЗМЕНЯЯ ЯЧЕЙКИ укажем диапазон, который  играет роль переменных, т.е. В2:В4;

– введем систему ограничений с помощью, нажав кнопку ДОБАВИТЬ. При этом появится диалоговое окно ДОБАВЛЕНИЕ ОГРАНИЧЕНИЯ (ервое ограничений:

Þ в поле ССЫЛКА НА ЯЧЕЙКУ вводим диапазон, где вычислены левые части неравенств из системы ограничений задачи (все три неравенства можно ввести сразу, так как они одного смысла – больше или равно) – В12:В14;

Þ в открывающемся списке выбираем знак неравенства;

Þ в поле ОГРАНИЧЕНИЕ указываем диапазон, где хранятся правые части неравенств системы ограничений задачи – C12:C14;

Þ нажимаем кнопку ДОБАВИТЬ (при этом окно не исчезнет и можно будет ввести новое ограничение).

 

Второе ограничение (условие неотрицательности переменных):

Þ в поле ССЫЛКА НА ЯЧЕЙКУ вводим диапазон ячеек, которые играют роль переменных – В2:В4;

Þ выбираем знак неравенства;

Þ в поле ОГРАНИЧЕНИЕ вводим с клавиатуры ноль;

Þ нажимаем кнопку ОК.

4. Осталось  в окне ПОИСК РЕШЕНИЯ нажать  кнопку ВЫПОЛНИТЬ и увидеть результат решения задачи:

 

Получили: . Так как и , то , – это решение для игры, заданной матрицей В (преобразованной матрицы). Для матрицы А: компоненты смешанной стратегии не меняются, а цена игры меньше на число, которое прибавляли ко всем элементам матрицы А, т.е. на 4.

Окончательный результат: , .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Решение в maple:

 

Проверим  сначала не имеет ли задача решения  в чистых стратегиях. Для этого  вычислим верхнюю и нижнюю цену игры по формулам, приведенным в примере 5. Получим  . Так как , решения в чистых стратегиях не существует.

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

.

Минимальное значение целевой функции при  этом равно величине, обратной ожидаемой цене игры , а вероятности выбора той или иной стратегии первым игроком вычисляются по формуле

.

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

,

и вычислить  вероятности выбора той или иной стратегии вторым игроком по формуле:

.

Для нахождения величин  можно также воспользоваться формулами, связывающими решения прямой и двойственной задач (см. пример 2).

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

Прямая  задача линейного программирования в этом случае выглядит так:

Решить  эту задачу можно симплекс-методом (см. примеры 3 и 4) или воспользоваться соответствующим программным обеспечением, например, пакетом simplex компьютерной системы символьной математики Maple. Решение сформулированной задачи оформляется следующим образом:

> restart: with(simplex):

Warning, the protected names maximize and minimize have been redefined and unprotected

> cond:=x1+x2+x3: ne1:=19*x1+10*x2+20*x3>=1: ne2:=10*x1-0*x2+6*x3>=1: ne3:=4*x1+16*x2+23*x3>=1:   minimize(cond,{ne1,ne2,ne3},NONNEGATIVE); PI:=subs(%,cond);

 

,

 

Решение двойственной задачи имеет вид

,

т.е. справедливы равенства

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

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

Программа Mathcad нашла применение в различных  областях науки, она позволяет производить символьные и аналитические вычисления, производит операции с матрицами, системами уравнений, функциями, а так же строить графики и диаграммы по полученным результатам. Эффективность применения данной программы очень высока и важна для экономики России.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература

1. Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,2001.
2. Аоки М. Введение в методы оптимизации. –М.: Наука,2007.
3. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,2001.
4. Вентцель Е. С. Исследование операций. –М.: Наука,2006.
5. Вилкас Э.И. Оптимальность в играх и решениях. - М.: Наука,1990.
6. Давыдов, Э.Г. Исследование операций : учеб. пособие для студ. вузов / Э.Г. Давыдов. - М. : Высш. школа, 2000.
7. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,2005.
8. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы. – М.: Просвещение, 2001 г.
9. Интрилигатор М. Математические методы оптимизации и экономическая теория. - М.: Прогресс, 2005.
10. Кузнецов Ю. Н. Математическое программирование. –М.: Наука,2006.
11. Конюховский П.В. Математические методы исследования операций: пособие для подготовки к экзамену. – Спб.:Питер, 2001
12. Карманов В. Т. Математическое программирование. –М.:Наука,2006.
13. Муну М. Математическое программирование. Теория алгоритмов. –М.: Наука,2000.
14. Методологические аспекты динамического программирования // Динамические системы, 2007.
15. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр: Учебное пособие для университетов. - М.: Высшая школа, Книжный дом “Университет”, 2008
16. Таха Х. Введение в исследование операций.–М.: Мир,2005.
17. Шикин Е.В. Чхартишвили А.Г. Математические методы и модели в управлении: Учебник для ВУЗов. - М.: Дело, 2000.
18. Щербина О.А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005.