Реферат: Методы безусловной многомерной оптимизации

--PAGE_BREAK--
Таблица 2.1



В данной задаче имеется ограничение – двигаться по магистралям можно только слева направо. Это дает нам возможность разбить всю транспортную сеть на пояса и отнести каждый из десяти пунктов к одному из четырех поясов. Будем говорить, что пункт принадлежит k-му поясу, если из него можно попасть в конечный пункт ровно за k шагов, т.е. заездом ровно в k-1 промежуточный пункт. Таким образом, пункты 8, 9 и 10 принадлежат к первому поясу; 6 и 7 – ко второму; 2, 3, 4 и 5 – к третьему; 1 – к четвертому. На k-м шаге будем находить оптимальные маршруты из городов k-го пояса до конечного пункта.

Оптимизацию будем производить с хвоста процесса, и потому, добравшись до k-го шага, мы не можем знать, в какой именно из городов k-го пояса мы попадем, двигаясь из пункта 1. Поэтому для каждого из этих городов мы должны будем найти оптимальный маршрут до конечного пункта. Очевидно, что минимально возможная стоимость проезда до пункта 11 будет зависеть только от того, в каком из городов этого пояса мы оказались. Номер S города, принадлежащего k-му поясу, и будет называться переменной состояния данной системы на k-м шаге. Нужно помнить, что, добравшись до k-го шага, мы уже осуществили предыдущие шаги, в частности, нашли оптимальные маршруты по перемещению из любого города (k-1)-го пояса в конечный пункт. Таким образом, находясь в некотором городе S k-го пояса, мы должны принять решение о том, в какой из городов (k-1)-го пояса следует отправиться, а направление дальнейшего движения уже известно нам из предыдущих шагов. Номер J города (k-1)-го пояса будет являться переменной управления на k-м шаге.

Функция Беллмана на k-м шаге решения задачи дает нам возможность рассчитать минимальную стоимость проезда из города S (k-го пояса) до конечного пункта. Для первого шага (k=1) эту величину отыскать не сложно – это стоимость проезда из городов 1-го пояса непосредственно до конечного пункта: F1(i)=Ci11. Для последующих же шагов стоимость проезда складывается из двух слагаемых – стоимости проезда из города S k-го пояса в город J (k-1)-го пояса и минимально возможной стоимости проезда из города J до конечного пункта, т.е. Fk-1(J).

Таким образом, функциональное уравнение Беллмана на k-м шаге решения будет иметь вид:
<img width=«191» height=«32» src=«ref-1_864019521-683.coolpic» v:shapes="_x0000_i1030">
Минимум стоимости достигается на некотором значении J*, которое и является оптимальным направлением движения из пункта S в сторону конечного пункта.

Решение:

Этап I. Условная оптимизация.

Шаг 1. k = 1. F1(S) = ts11.
Таблица 2.2



Шаг 2. k = 2. Функциональное уравнение на данном шаге принимает вид:
<img width=«180» height=«32» src=«ref-1_864020204-663.coolpic» v:shapes="_x0000_i1031">.
Результаты расчета по приведенной формуле приведены в таблице 2.3:
Таблица 2.3



Шаг 3. k = 3. Функциональное уравнение на данном шаге принимает вид:
<img width=«181» height=«32» src=«ref-1_864020867-666.coolpic» v:shapes="_x0000_i1032">.
Результаты расчета по приведенной формуле приведены в таблице 2.4:
Таблица 2.4



Шаг 4. k = 4. Функциональное уравнение на данном шаге принимает вид:
<img width=«181» height=«32» src=«ref-1_864021533-665.coolpic» v:shapes="_x0000_i1033">.
Результаты расчета по приведенной формуле приведены в таблице 2.5:
Таблица 2.5



Этап II. Безусловная оптимизация.

На этапе условной оптимизации получено, что минимальные затраты на проезд из пункта 1 в пункт 11 составляют F4(1) = 21, что достигается следующим движением по магистралям. Из пункта 1 следует направиться в пункт 2, затем из него в пункт 6, затем в пункт 9 и из него в пункт 11.

Ответ: Оптимальным маршрутом из пункта 1 в пункт 11 является маршрут 1 – 2 – 6 – 9 – 11.




3 Методы Хэмминга и Брауна
Задача: На эмпирическом временном ряде из 20 значений ( таблица 3.1), используя процедуры обычной регрессии, Хэмминга (А и Б-метод) и Брауна, выполнить прогноз на один шаг и на три-четыре шага вперед для каждого метода соответственно. Сравнить прогнозные процедуры. Сделать выводы.
Таблица 3.1



3.1 Метод Хемминга
Метод Хемминга обладает достоинствами, связанными с простотой и относительно небольшой погрешностью. Существует в двух модификациях. Базовый алгоритм (А-метод Хемминга) применяется для прогнозирования относительно стабильных или слабо изменяющихся динамических рядов, имеющих фиксированную структуру.
<img width=«441» height=«24» src=«ref-1_864022198-656.coolpic» v:shapes="_x0000_i1034">,
где <img width=«53» height=«21» src=«ref-1_864022854-149.coolpic» v:shapes="_x0000_i1035"> – прогнозное значение;

<img width=«15» height=«17» src=«ref-1_864023003-91.coolpic» v:shapes="_x0000_i1036">  — значение функции;

<img width=«9» height=«17» src=«ref-1_864023094-80.coolpic» v:shapes="_x0000_i1037">  — порядковый номер элемента, входящего в состав исследуемого объекта;

<img width=«13» height=«15» src=«ref-1_864023174-85.coolpic» v:shapes="_x0000_i1038">  — время запаздывания или исследование обрабатываемых данных (реализация функций объекта);

<img width=«19» height=«23» src=«ref-1_864023259-103.coolpic» v:shapes="_x0000_i1039">,<img width=«20» height=«23» src=«ref-1_864023362-104.coolpic» v:shapes="_x0000_i1040">,<img width=«20» height=«24» src=«ref-1_864023466-103.coolpic» v:shapes="_x0000_i1041">,<img width=«20» height=«23» src=«ref-1_864023569-105.coolpic» v:shapes="_x0000_i1042">,<img width=«20» height=«24» src=«ref-1_864023674-104.coolpic» v:shapes="_x0000_i1043"> — коэффициенты настройки, задаваемые жестко, в виде числа.

Для каждого ряда коэффициенты задаются индивидуально. Число коэффициентов всегда не четное. Сумма всех коэффициентов всегда должна быть равной 1 (<img width=«60» height=«27» src=«ref-1_864023778-252.coolpic» v:shapes="_x0000_i1044">).

Наиболее удачными, по мнению Хемминга, являются коэффициенты для 3 и 5 слагаемых (таблица 3.2).
Таблица 3.2



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

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

Идея заключается в следующем: в фиксированный момент времени t1 (в который обнаружилось превышение порога погрешности в 5%) рассматривается автокорреляционная функция (АКФ) ряда <img width=«35» height=«21» src=«ref-1_864024030-128.coolpic» v:shapes="_x0000_i1045">. При этом оценивается величина вклада каждой из компонент <img width=«124» height=«23» src=«ref-1_864024158-228.coolpic» v:shapes="_x0000_i1046"> в t2, и рассчитываются соответствующие коэффициенты:

Шаг 1: оценивается величина площади под АКФ
<img width=«95» height=«51» src=«ref-1_864024386-377.coolpic» v:shapes="_x0000_i1047">;
Шаг 2: коэффициенты рассчитываются по формуле
<img width=«52» height=«41» src=«ref-1_864024763-185.coolpic» v:shapes="_x0000_i1048">.
Модифицированный метод проверялся на реальных данных нестационарной динамики, и погрешности не превышали 5-10%, что вполне приемлемо для подобных задач.

Решение:

Результаты моделирования по методу Хэмминга представлены в таблице 3.3.
Таблица 3.3



Прогнозные значение на основе базового алгоритма Хэмминга (А-метод ):
<img width=«337» height=«25» src=«ref-1_864025375-554.coolpic» v:shapes="_x0000_i1053">    продолжение
--PAGE_BREAK--;
<img width=«340» height=«25» src=«ref-1_864025929-557.coolpic» v:shapes="_x0000_i1054">;
<img width=«340» height=«25» src=«ref-1_864026486-554.coolpic» v:shapes="_x0000_i1055">;
<img width=«340» height=«25» src=«ref-1_864027040-558.coolpic» v:shapes="_x0000_i1056">.
На основе полученных данных построим график прогнозирования по адаптивной модели Хемминга (рисунок 2)


Рисунок 2
<img width=«613» height=«421» src=«ref-1_864027598-3280.coolpic» v:shapes="_x0000_i1057">
Оценим адекватность модели с помощью коэффициента детерминации. Для этого рассчитаем
<img width=«145» height=«45» src=«ref-1_864030878-458.coolpic» v:shapes="_x0000_i1058">,
остальные расчеты представлены в таблице 3.4.
Таблица 3.4



Коэффициент детерминации находится по формуле:
<img width=«288» height=«88» src=«ref-1_864031922-972.coolpic» v:shapes="_x0000_s1061">



3.2 Метод Брауна
Также считается адаптивным алгоритмом прогнозирования, и в основном используется при краткосрочном прогнозировании.
<img width=«183» height=«27» src=«ref-1_864032894-342.coolpic» v:shapes="_x0000_i1063">,
где k – количество шагов прогнозирования (k=1).

Это значение сравнивается с фактическим уровнем
<img width=«123» height=«25» src=«ref-1_864033236-264.coolpic» v:shapes="_x0000_i1064">,
который затем используется для корректировки модели.
<img width=«195» height=«24» src=«ref-1_864033500-360.coolpic» v:shapes="_x0000_i1065">,
<img width=«261» height=«25» src=«ref-1_864033860-444.coolpic» v:shapes="_x0000_i1066">,
где <img width=«16» height=«21» src=«ref-1_864034304-96.coolpic» v:shapes="_x0000_i1067"> – коэффициент дисконтирования данных, отражает большую степень доверия к более поздним данным, <img width=«57» height=«21» src=«ref-1_864034400-163.coolpic» v:shapes="_x0000_i1068">.

Решение:

Начальные оценки параметров получим по первым пяти точкам (они представлены в таблице 3.5) по формулам:
<img width=«199» height=«52» src=«ref-1_864034563-711.coolpic» v:shapes="_x0000_i1069">, <img width=«112» height=«25» src=«ref-1_864035274-222.coolpic» v:shapes="_x0000_i1070">
Таблица 3.5



Для расчета этой таблицы нам понадобилось <img width=«45» height=«25» src=«ref-1_864036310-135.coolpic» v:shapes="_x0000_i1076"> и <img width=«68» height=«25» src=«ref-1_864036445-174.coolpic» v:shapes="_x0000_i1077">.

Результаты моделирования по методу Брауна представлены в таблице 3.6.
Таблица 3.6



Для осуществления прогноза на несколько точек вперед рассмотрели полученную на последнем шаге модель
<img width=«156» height=«25» src=«ref-1_864037254-296.coolpic» v:shapes="_x0000_i1084">    продолжение
--PAGE_BREAK--
Прогнозные оценки по этой модели получаются подстановкой в нее значений <img width=«187» height=«21» src=«ref-1_864037550-292.coolpic» v:shapes="_x0000_i1085">, таким образом:

<img width=«107» height=«25» src=«ref-1_864037842-243.coolpic» v:shapes="_x0000_i1086">,

<img width=«108» height=«25» src=«ref-1_864038085-243.coolpic» v:shapes="_x0000_i1087">,

<img width=«108» height=«25» src=«ref-1_864038328-244.coolpic» v:shapes="_x0000_i1088">,

<img width=«109» height=«25» src=«ref-1_864038572-243.coolpic» v:shapes="_x0000_i1089">.

На основе полученных данных построим график прогнозирования по адаптивной модели Брауна (рисунок 3)
Рисунок 3

<img width=«600» height=«441» src=«ref-1_864038815-3617.coolpic» v:shapes="_x0000_i1090">
Оценим адекватность модели с помощью коэффициента детерминации. Для этого рассчитаем
<img width=«144» height=«45» src=«ref-1_864042432-462.coolpic» v:shapes="_x0000_i1091">,
остальные расчеты представлены в таблице 3.7.


Таблица 3.7



Коэффициент детерминации находится по формуле:
<img width=«288» height=«88» src=«ref-1_864043480-984.coolpic» v:shapes="_x0000_s1062">



Вывод: Сравнивая коэффициенты детерминации по методам Хемминга и Брауна, равные 0,937 и 0,213 соответственно, делаем вывод что модель Хемминга является наиболее адекватной.




4 Идентификация как функция управления
В таблице 4.1 приведены данные о стоимости эксплуатации винтовых самолетов в зависимости от возраста:
Таблица 4.1



1. Провести процедуру структурно-параметрической идентификации математической модели для исходных данных. Оценить адекватность.

2. Проанализируйте данные, исключив повторы. Ответьте на вопросы: изменилось ли математическая модель? Как изменился коэффициент детерминации? Адекватна ли подобранная модель данным?

Решение:

Построим график эмпирических данных (рисунок 4).




Рисунок 4- График эмпирических данных

<img width=«566» height=«315» src=«ref-1_864044464-1925.coolpic» v:shapes="_x0000_i1096">
Проведем все необходимые расчеты для составления статистического уравнения однофакторной зависимости и дальнейшего анализа этой зависимости. Для этого рассмотрим три модели:

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

логарифмическая модель (прямая гипербола, когда уровень результативного признака возрастает, а затем его рост приостанавливается, оставаясь почти на одном уровне);

прямая логическая зависимость (когда происходит неустойчивое возрастание уровня результативного признака).

Линейная модель.

Уравнение модели прямой однофакторной линейной связи:
<img width=«232» height=«37» src=«ref-1_864046389-769.coolpic» v:shapes="_x0000_i1097">
Для вычисления параметра <img width=«13» height=«19» src=«ref-1_864047158-88.coolpic» v:shapes="_x0000_i1098">, составления уравнения однофакторной зависимости и дальнейшего анализа этой зависимости заполним таблицу 4.2.


Таблица 4.2
    продолжение
--PAGE_BREAK--


Примечание. Предпоследний и последний столбцы таблицы 4.2 заполняются после отыскания параметра уравнения зависимости <img width=«13» height=«19» src=«ref-1_864047158-88.coolpic» v:shapes="_x0000_i1106"> и составления самого уравнения зависимости.

В рассматриваемом примере параметр <img width=«13» height=«19» src=«ref-1_864047158-88.coolpic» v:shapes="_x0000_i1107">, при <img width=«52» height=«23» src=«ref-1_864048500-138.coolpic» v:shapes="_x0000_i1108"> и <img width=«72» height=«23» src=«ref-1_864048638-172.coolpic» v:shapes="_x0000_i1109"> вычисляется по формуле:
<img width=«280» height=«95» src=«ref-1_864048810-1132.coolpic» v:shapes="_x0000_i1110">
В рассматриваемом примере окончательный вид уравнения зависимости находим по формуле.:
<img width=«311» height=«43» src=«ref-1_864049942-719.coolpic» v:shapes="_x0000_i1111">
Отобразим эмпирические и теоретические значения результативного признака на графике (рисунок 4).
Рисунок 4

<img width=«619» height=«286» src=«ref-1_864050661-2139.coolpic» v:shapes="_x0000_i1112">
Информация для расчета коэффициента детерминации в типовой задаче в полном объеме представлена в таблице 4.3.
Таблица 4.3



По данным таблицы 4.3 коэффициент детерминации составит:
<img width=«305» height=«57» src=«ref-1_864054289-971.coolpic» v:shapes="_x0000_i1123">
Логарифмическая модель

Уравнение модели прямой гиперболы:
<img width=«187» height=«45» src=«ref-1_864055260-550.coolpic» v:shapes="_x0000_i1124">
Для вычисления параметра <img width=«13» height=«19» src=«ref-1_864047158-88.coolpic» v:shapes="_x0000_i1125">, составления уравнения однофакторной зависимости и дальнейшего анализа этой зависимости заполним таблицу 4.4.
Таблица 4.4



Примечание. Предпоследний и последний столбцы таблицы 4.4 заполняются после отыскания параметра уравнения зависимости <img width=«13» height=«19» src=«ref-1_864047158-88.coolpic» v:shapes="_x0000_i1133"> и составления самого уравнения зависимости.

В рассматриваемом примере параметр <img width=«13» height=«19» src=«ref-1_864047158-88.coolpic» v:shapes="_x0000_i1134">, при <img width=«52» height=«23» src=«ref-1_864048500-138.coolpic» v:shapes="_x0000_i1135"> и <img width=«72» height=«23» src=«ref-1_864048638-172.coolpic» v:shapes="_x0000_i1136"> вычисляется по формуле:
<img width=«283» height=«91» src=«ref-1_864057280-1089.coolpic» v:shapes="_x0000_i1137">    продолжение
--PAGE_BREAK--
В рассматриваемом примере окончательный вид уравнения зависимости находим по формуле:
<img width=«324» height=«39» src=«ref-1_864058369-725.coolpic» v:shapes="_x0000_i1138">
Отобразим эмпирические и теоретические значения результативного признака на графике (рисунок 5).
Рисунок 5

<img width=«605» height=«364» src=«ref-1_864059094-2812.coolpic» v:shapes="_x0000_i1139">
Информация для расчета коэффициента детерминации в типовой задаче в полном объеме представлена в таблице 4.5.
Таблица 4.5
    продолжение
--PAGE_BREAK--


По данным таблицы 4.5 коэффициент детерминации составит:
<img width=«305» height=«57» src=«ref-1_864063362-965.coolpic» v:shapes="_x0000_i1150">
Логическая модель

Уравнение модели прямой логической зависимости:
<img width=«166» height=«80» src=«ref-1_864064327-520.coolpic» v:shapes="_x0000_i1151">
Для вычисления параметра <img width=«13» height=«19» src=«ref-1_864047158-88.coolpic» v:shapes="_x0000_i1152">, составления уравнения однофакторной зависимости и дальнейшего анализа этой зависимости заполним таблицу 5.
Таблица 4.6
--PAGE_BREAK--