Решением будет я-, = 0,4286 и лг = 0,5714. Эти результаты очень близки к значениям элементов вектора а(8) (и строкам матрицы Р8) из примера 19.5.1. Далее получаем значения среднего времени возвращения в первое и второе состояния

р = -= 2,3, р22 = -= 1,75 . я, я2

Пример 19.5.4

Рассмотрим следующую цепь Маркова с тремя состояниями:

1 2

Р=1 2

0 ±

4 1 4 1 2

Такая матрица называется дважды стохастической, так как

1=1 у.

где i - число состояний цепи Маркова. В таких случаях установившиеся вероятности равны л., = 1/s для всех j. Поэтому для данной задачи л0 = лх = л2 = 1/3.

УПРАЖНЕНИЯ 19.5

1. Определите класс состояний приведенных ниже цепей Маркова и найдите их стационарные распределения.

2. Найдите среднее время возвращения в каждое состояние цепи Маркова, заданной следующей матрицей переходных вероятностей.

(1 I Л 3 3 3

111 2 4 4

111 ч5 5 5)

ЛИТЕРАТУРА

1. Derman С. Finite State Markovian Decision Process, Academic Press, New York, 1970.

2. Howard R. Dynamic Programming and Markov Processes, MIT Press, Cambridge, Mass., 1960. (Русский перевод: Ховард P. Динамическое программирование и марковские процессы. - М.: Сов. радио, 1964.)

Литература, добавленная при переводе

1. Дынкин Е. Б., Юшкевич А. А. Теоремы и задачи о процессах Маркова. - М.: Наука, 1967.

2. Кемени Дж., Снелл Дж. Конечные цепи Маркова. - М.: Наука, 1970.

ГЛАВА 20

КЛАССИЧЕСКАЯ ТЕОРИЯ ОПТИМИЗАЦИИ

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

В этой главе изложены необходимые и достаточные условия существования экстремумов функций при отсутствии ограничений на переменные задачи, методы Якоба и Лагранжа для решения задач с ограничениями на переменные в форме равенств, а также условия Куна-Таккера для задач с ограничениями в виде неравенств.

20.1. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ БЕЗ ОГРАНИЧЕНИЙ

Экстремальная точка функции /(X) определяет либо ее максимальное, либо минимальное значение. С математической точки зрения точка Х.0 = (х1,xjyxj является точкой максимума функции /(X), если неравенство

/(X0 + h)</(X0)

выполняется для всех h = (А А;, Ап) таких, что Aj достаточно малы при всех j. Другими словами, точка Х0 является точкой максимума, если значения функции / в окрестности точки Х0 не превышают /(Х0). Аналогично точка Х0 является точкой минимума функции /(X), если для определенного выше вектора h имеет место неравенство

/(X0 + h)>/(X0).

На рис. 20.1 показаны точки максимума и минимума функции одной переменной f(x) на интервале [а, Ь]. Точки xv х2, х3, х4 и хв составляют множество экстремальных точек функции f(x). Здесь точки xv х3 и х6 являются точками максимума, а точки х2их4 - точками минимума функции f(x). Поскольку

f(x6) = max{/(t), f(x3), /(* )}, значение f(x6) называется глобальным или абсолютным максимумом, а значения f{xx) и f(x3) - локальными или относительными максимумами. Подобным образом, значение f(x4) является локальным, a f(x2) - глобальным минимумом функции f(x).