Сантылова Л.И. Вариационное исчисление и методы оптимизации
Подождите немного. Документ загружается.
F
1
(a )
=
max
a
1
x
1
≤a
f
1
( x
1
)
.
Во всех формулах (13) предполагается, что
x
j
≥0, x
j
−
целое.
4) На k-м этапе, применяя (13), можно для всевозможных значений a
найти
F
k
(a )
, выбирая при этом лишь управляющее решение
x
k
=
x
k
(a )
и используя найденные на предыдущем этапе значения
F
k−1
( a)
. Таким
образом, принимаемое на k-м этапе решение
x
k
(a )
зависит только от
параметра состояния a и не зависит от решений
x
1
, x
2
, ... , x
k−1
, принимаемых
на предыдущих этапах. Этим самым реализуется принцип оптимальности.
Описание вычислительной процедуры.
Номер k определяет номер этапа, параметр а – состояние системы.
Используя (13), для каждого k=1,…,n найдем значения
F
k
(a )
и
x
k
(a )
для
а=0,1,…,А.
При этом
x
k
(a )
есть значение
x
k
, на котором достигается максимум
в рекуррентном соотношении (13). Результаты вычислений заносим в таблицу
8. Выделенные клетки таблицы заполняются числовыми значениями указанных
в них выражений. Заполнение таблицы 8 называют прямым ходом
динамического программирования.
Таблица 8
Результаты вычислений при прямом ходе метода ДП
А
)a(F
1
)a(x
1
)a(F
2
)a(x
2
…
)a(F
n
)a(x
n
0
)0(F
1
)0(x
1
)0(F
2
)0(x
2
…
)0(F
n
)0(x
n
1
)1(F
1
)1(x
1
)1(F
2
)1(x
2
…
)1(F
n
)1(x
n
… … … … … … … …
A
)A(F
1
)A(x
1
)A(F
2
)A(x
2
…
)A(F
n
)A(x
n
31
Обратный ход позволяет по значениям таблицы 8 найти решение
исходной задачи.
Действительно, оптимальное значение целевой функции исходной задачи
f ∗¿ F
n
( A )
.
Найдем оптимальное решение:
1)
a=A , x
n
¿
=x
n
(a)
2)
a=a−a
n
x
n
, x
n−1
¿
=x
n−1
( a)
……………………………………..
n)
a=a−a
2
x
2
, x
1
¿
=x
1
(a )
Литература
1. Вентцель Е.С. Исследование операций. Задачи, принципы, методология.-
М.: Высш. шк.,2001.
2. Таха Х. Введение в исследование операций. -Минск:Вильямс,2001.
3. Вагнер Г. Основы исследования операций. Т.1-3- М.:Мир,1973.
4. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике:
модели, задачи, решения: Учеб. Пособие. – М.: ИНФА-М, 2003
5. Волков И.К. и др. Введение в исследование операций.-М.:Изд-во МГТУ им.
Баумана, 2000.
6. Моисеев и др. Методы оптимизации. М. Физматгис, 1978.
7. Реклейтис Г. и др. Оптимизация в технике. М. Мир, 1986.
32