Методы безусловной многомерной оптимизации (стр. 2 из 6)
Функция Беллмана на k-м шаге решения задачи дает нам возможность рассчитать минимальную стоимость проезда из города S (k-го пояса) до конечного пункта. Для первого шага (k=1) эту величину отыскать не сложно – это стоимость проезда из городов 1-го пояса непосредственно до конечного пункта: F1(i)=Ci11. Для последующих же шагов стоимость проезда складывается из двух слагаемых – стоимости проезда из города S k-го пояса в город J (k-1)-го пояса и минимально возможной стоимости проезда из города J до конечного пункта, т.е. Fk-1(J).
Таким образом, функциональное уравнение Беллмана на k-м шаге решения будет иметь вид:
Минимум стоимости достигается на некотором значении J*, которое и является оптимальным направлением движения из пункта S в сторону конечного пункта.
Решение:
Этап I. Условная оптимизация.
Шаг 1. k = 1. F1(S) = ts11.
Таблица 2.2
| S | J = 11 | F1(S) | J* |
| 8 | 10 | 10 | 11 |
| 9 | 8 | 8 | 11 |
| 10 | 10 | 10 | 11 |
Шаг 2. k = 2. Функциональное уравнение на данном шаге принимает вид:
.Результаты расчета по приведенной формуле приведены в таблице 2.3:
Таблица 2.3
| S | J = 8 | J = 9 | J = 10 | F2(S) | J* |
| 6 | 4 + 10 | 5 + 8 | 4 + 10 | 13 | 9 |
| 7 | 5 + 10 | 12 + 8 | 6 + 10 | 15 | 8 |
Шаг 3. k = 3. Функциональное уравнение на данном шаге принимает вид:
.Результаты расчета по приведенной формуле приведены в таблице 2.4:
Таблица 2.4
| S | J = 6 | J = 7 | F3(S) | J* |
| 2 | 3 + 13 | 7 + 15 | 16 | 6 |
| 3 | 8 + 13 | 9 + 15 | 21 | 6/7 |
| 4 | 11 + 13 | 4 + 15 | 19 | 7 |
| 5 | 8 + 13 | 9 + 15 | 21 | 6/7 |
Шаг 4. k = 4. Функциональное уравнение на данном шаге принимает вид:
.Результаты расчета по приведенной формуле приведены в таблице 2.5:
Таблица 2.5
| S | J = 2 | J = 3 | J = 4 | J = 5 | F4(S) | J* |
| 1 | 5 + 16 | 7 + 21 | 6 + 19 | 10 + 21 | 21 | 2 |
Этап II. Безусловная оптимизация.
На этапе условной оптимизации получено, что минимальные затраты на проезд из пункта 1 в пункт 11 составляют F4(1) = 21, что достигается следующим движением по магистралям. Из пункта 1 следует направиться в пункт 2, затем из него в пункт 6, затем в пункт 9 и из него в пункт 11.
Ответ: Оптимальным маршрутом из пункта 1 в пункт 11 является маршрут 1 – 2 – 6 – 9 – 11.
3 Методы Хэмминга и Брауна
Задача: На эмпирическом временном ряде из 20 значений ( таблица 3.1), используя процедуры обычной регрессии, Хэмминга (А и Б-метод) и Брауна, выполнить прогноз на один шаг и на три-четыре шага вперед для каждого метода соответственно. Сравнить прогнозные процедуры. Сделать выводы.
Таблица 3.1
| t | Y(t) |
| 1 | 50 |
| 2 | 53 |
| 3 | 56,5 |
| 4 | 53,5 |
| 5 | 51 |
| 6 | 54 |
| 7 | 53,5 |
| 8 | 60 |
| 9 | 59 |
| 10 | 60 |
| 11 | 61 |
| 12 | 62 |
| 13 | 58 |
| 14 | 57 |
| 15 | 57,5 |
| 16 | 59,5 |
| 17 | 60,5 |
| 18 | 61 |
| 19 | 62 |
| 20 | 62,5 |
3.1 Метод Хемминга
Метод Хемминга обладает достоинствами, связанными с простотой и относительно небольшой погрешностью. Существует в двух модификациях. Базовый алгоритм (А-метод Хемминга) применяется для прогнозирования относительно стабильных или слабо изменяющихся динамических рядов, имеющих фиксированную структуру.
,где
– прогнозное значение; 
- значение функции; 
- порядковый номер элемента, входящего в состав исследуемого объекта; 
- время запаздывания или исследование обрабатываемых данных (реализация функций объекта); 
, 
, 
, 
, 
- коэффициенты настройки, задаваемые жестко, в виде числа.Для каждого ряда коэффициенты задаются индивидуально. Число коэффициентов всегда не четное. Сумма всех коэффициентов всегда должна быть равной 1 (
).Наиболее удачными, по мнению Хемминга, являются коэффициенты для 3 и 5 слагаемых (таблица 3.2).
Таблица 3.2
| А1 | А2 | А3 | А4 | А5 | |
| для трех | 0,60 | 0,30 | 0,10 | ||
| для пяти | 0,65 | 0,15 | 0,10 | 0,04 | 0,01 |
Данный алгоритм прошел апробацию и достаточно точно прогнозирует переменные различного рода технологических и транспортных операций в нормальном режиме эксплуатации. Однако при применении в случае нештатного и аварийного режимов производства имеет место значительная погрешность, т.е. больше 15%.
Исследования показали, что для увеличения адаптивных возможностей требуется методика настройки коэффициентов, алгоритм которой и включает В-метод Хемминга.
Идея заключается в следующем: в фиксированный момент времени t1 (в который обнаружилось превышение порога погрешности в 5%) рассматривается автокорреляционная функция (АКФ) ряда
. При этом оценивается величина вклада каждой из компонент 
в t2, и рассчитываются соответствующие коэффициенты:Шаг 1: оценивается величина площади под АКФ
;Шаг 2: коэффициенты рассчитываются по формуле
.Модифицированный метод проверялся на реальных данных нестационарной динамики, и погрешности не превышали 5-10%, что вполне приемлемо для подобных задач.
Решение:
Результаты моделирования по методу Хэмминга представлены в таблице 3.3.
Таблица 3.3
 |  |  |  |
| 1 | 50,0 | 50,000 | 0,00 |
| 2 | 53,0 | 53,000 | 0,00 |
| 3 | 56,5 | 54,800 | 1,70 |
| 4 | 53,5 | 54,350 | 0,85 |
| 5 | 51,0 | 52,300 | 1,30 |
| 6 | 54,0 | 53,050 | 0,95 |
| 7 | 53,5 | 53,400 | 0,10 |
| 8 | 60,0 | 57,450 | 2,55 |
| 9 | 59,0 | 58,750 | 0,25 |
| 10 | 60,0 | 59,700 | 0,30 |
| 11 | 61,0 | 60,500 | 0,50 |
| 12 | 62,0 | 61,500 | 0,50 |
| 13 | 58,0 | 59,500 | 1,50 |
| 14 | 57,0 | 57,800 | 0,80 |
| 15 | 57,5 | 57,400 | 0,10 |
| 16 | 59,5 | 58,650 | 0,85 |
| 17 | 60,5 | 59,900 | 0,60 |
| 18 | 61,0 | 60,700 | 0,30 |
| 19 | 62,0 | 61,550 | 0,45 |
| 20 | 62,5 | 62,200 | 0,30 |
| 21 | 61,855 | ||
| 22 | 61,928 | ||
| 23 | 61,933 | ||
| 24 | 61,924 |
Прогнозные значение на основе базового алгоритма Хэмминга (А-метод ):
; 
; 
; 
.На основе полученных данных построим график прогнозирования по адаптивной модели Хемминга (рисунок 2)
Рисунок 2
Оценим адекватность модели с помощью коэффициента детерминации. Для этого рассчитаем
,остальные расчеты представлены в таблице 3.4.
Таблица 3.4
| |  |  |
| 50,0 | 0,000 | 57,381 |
| 53,0 | 0,000 | 20,931 |
| 56,5 | 2,890 | 1,156 |
| 53,5 | 0,722 | 16,606 |
| 51,0 | 1,690 | 43,231 |
| 54,0 | 0,903 | 12,781 |
| 53,5 | 0,010 | 16,606 |
| 60,0 | 6,503 | 5,881 |
| 59,0 | 0,063 | 2,031 |
| 60,0 | 0,090 | 5,881 |
| 61,0 | 0,250 | 11,731 |
| 62,0 | 0,250 | 19,581 |
| 58,0 | 2,250 | 0,181 |
| 57,0 | 0,640 | 0,331 |
| 57,5 | 0,010 | 0,006 |
| 59,5 | 0,723 | 3,706 |
| 60,5 | 0,360 | 8,556 |
| 61,0 | 0,090 | 11,731 |
| 62,0 | 0,203 | 19,581 |
| 62,5 | 0,090 | 24,256 |
 | 17,735 | 282,138 |
Коэффициент детерминации находится по формуле: