Условие статической устойчивости позволяет использовать в процессе принятия решений эффективные математические методы теории случайных процессов и, в частности, одного из ее разделов - теории марковских процессов.

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

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

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

Как указывалось, марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

Случайной функцией называется функция, значение которой при любом значении аргумента является случайной величиной (СВ). По иному, СФ можно назвать функцию, которая при каждом испытании принимает какой-либо заранее неизвестный вид.

Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.

Как правило, считают, что если аргументом СФ является время, то такой процесс называют случайным. Существует и другое, более близкое к теории принятия решений, определение СП. При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.

Нетрудно заметить, что если обозначить состояние S_i и изобразить зависимость S_i(t), то такая зависимость и будет случайной функцией.

СП классифицируются по видам состояний S_i и аргумента t. При этом СП могут быть с дискретными или непрерывными состояниями или временем. Например, любой выборочный контроль продукции будет относиться к СП с дискретными состояниями (S₁- годная, S₂ - негодная продукция) и дискретным временем (t₁ , t₂ - времена проверки). С другой стороны, случай отказа любой имашины можно отнести к СП с дискретными состояниями, но непрерывным временем. Проверки термометра через определенное время будут относиться к СП с непрерывным состоянием и дискретным временем. В свою очередь, например, любая осцилограмма будет записью СП с непрерывными состояниями и временем.

Кроме указанных выше примеров классификации СП, существует еще одно важное свойство. Это свойство описывает вероятностную связь между состояниями СП. Так, например, если в СП вероятность перехода системы в каждое последующее состояние зависит только от предыдущего состояния, то такой процесс называется процессом без последействия (рис.8.1):

Рис.8.1. Схема процесса без последействия

Зависимость P _i/i+1 = f(S_i) называют переходной вероятностью, часто говорят, что именно процесс без последействий обладает марковским свойством, однако, строго говоря, здесь есть одна неточность. Дело в том, что можно представить себе СП, в котором вероятностная связь существует не только с предшествующими, но и более ранними - S_i-1, S_i+2 ... состояниями, т.е.

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

Это обстоятельство должно обязательно учитываться при составлении математических моделей принятия решений.

Выше мы совершили незаметный терминологический переход от понятия СП к "марковской цепи". Теперь эту неясность следует устранить. Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.

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

С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется марковским процессом с непрерывным временем.

Марковский СП называется однородным, если переходные веро-ятности P_i/i+1 остаются постоянными в ходе процесса.

Цепь Маркова считается заданной, если заданы два условия:

1. Имеется совокупность переходных вероятностей в виде матрицы:

П _[n] = . (8.2)

2. Вектор начальных вероятностей

P⁽⁰⁾_<n> = < P₀₁, P₀₂,..,P_0n > , (8.3)

описывающий начальное состояние системы.

Матрица (2) называется переходной матицей (матрицей перехода). Элементами матрицы являются вероятности перехода из i-го в j-е состояние за один шаг процесса. Переходная матрица (8.2) обладает следующими свойствами:

Матрица, обладающая свойством (8.3), называется стохастической.

Кроме матричной формы модель марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 8.2).

Рис.8.2. Ориентированных взвешенный граф

Вершины графа обозначают состояние S_i , а дуги - переходные вероятности.

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

1. Невозвратное множество ( рис. 8.3)

Рис. 8.3. Невозвратное множество

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

2. Возвратное множество (рис. 8.4)

Рис. 8.4. Возвратное множество

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

3. Эргодическое множество (рис. 8.5)

Рис. 8.5. Эргодическое множество

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

4. Поглощающее множество (рис. 8.6)

Рис. 8.6. Поглощающее множество

При попадании системы в это множество процесс заканчивается.

Кроме описанной выше классификации множеств различают состояния системы:

а) существенное состояние (рис.8.7): возможны переходы из S_i в S_j и обратно

Рис. 8.7. Существенное состояние

б) несущественное состояние (рис. 8.8): возможен переход из S _i в S _j, но невозможен обратный.

Рис. 8.8. Несущественное состояние

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

Как указывалось выше, основным признаком ДМЦ является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако, часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими.

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

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

Рис. 8.9. Классификация марковских цепей

В дальнейшем рассматриваются простые однородные марковские цепи с дискретным временем. Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом к-том ее шаге. Это уравнение имеет вид:

и называется уравнением Колмогорова-Чепмена.

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

Дальнейшие математические соотношения зависят от конкретного вида марковской цепи.

Как указывалось выше, у поглощающих ДМЦ имеется множество, состоящее из одного или нескольких поглощающих состояний.

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

Практически важным является вопрос о том, сколько шагов сможет пройти система до остановки процесса, то есть поглощения в том или ином состоянии.Для получения дальнейших соотношений путем переименования состояний матрицу (8.5) переводят к блочной форме:

Такая форма позволяет представить матрицу (8.6) в каноническом виде:

где - единичная матрица;

На основании канонической формы (8.6а) получена матрица, называемая фундаментальной.

M _[2] = ( I _[2] - Q _[2] ) ^-1 , (8.7)

В матрице (8.7) символ (^-1) означает операцию обращения, то есть

После соответствующих преобразований матрица (8.7) примет вид:

Каждый элемент матрицы (8.7а) соответствует среднему числу раз попадания системы в то или иное состояние до остановки процесса (поглощения).

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

Для иллюстрации приведем конкретный числовой пример: пусть известны значенияпереходных вероятностей матрицы П_[3] с одним поглощающим состоянием: P₁₁ = 1; P₁₂ = P₁₃ = 0; P₂₁ = 0,25; P₂₂ = 0,5; P₂₃ = 0,25; P₃₁ = 0,5; P₃₂ = 0,5; P₃₃ = 0.

Переходная матрица в блочной системе будет выглядеть так:

В данном случае

Проделаем необходимые вычисления:

Так, если задать в нашем примере время пребывания в состоянии S₂ t₂ = 20 час, а в состоянии S₃ - t₃ = 30 час, то общее время до поглощения будет равно:

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

Обозначим через b_ij вероятность того, что процесс завершится в некотором поглощающем состоянии S_j при условии, что начальным было состояние S_i. Множество состояний b_ij снова снова образует матрицу, строки которой соответствуют невозвратным состояниям, а столбцы - всем всем поглощающим состояниям. В теории ДМЦ доказывается, что матрица В определяется следующим образом:

где

М - фундаментальная матрица с размерностью S;

R - блок фундаментальной матрицы с размерностью r.

Рассмотрим конкретный пример системы с четырьмя состояниями S₁ - S₄ , две из которых - S₁ , S₂ - поглощающие, а две - невозвратные: S₃ и S₄ (рис.8.10):

S₁ S₂ S₃ S₄

Рис. 8.10. Система с четырьмя состояниями

Для наглядности и простоты вычислений обозначим переходные вероятности следующим образом:

P₁₁ = P₂₂ = 1; P₃₁ = P₄₃ = q ; P₃₄ = P₄₂ = P.

Остальные значения вероятностей будут нулевыми. Каноническая форма матрицы перехода в этом случае будет выглядеть так:

Фундаментальная матрица после вычислений примет вид:

Тогда, согласно формуле (8.9), матрица вероятностей поглощения вычисляется так:

Поясним вероятностный смысл полученной матрицы с помощью конкретных чисел. Пусть p = 0,7 , а q = 0,3. Тогда, после подстановки полученных значений в матрицу В, получим:

S₁ S₂

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

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

где

М_dg - диагональная матрица, т.е. матрица, полученная из М путем оставления в ней лишь диагональных элементов и замены остальных элементов нулями. Например, приведенная выше матрица (8.7а) будет иметь вид:

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

.

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

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

все компоненты которого положительны.

Вектор (8.12) в теории ДМЦ занимает особое место из-за наличия многих приложений и называется вектором предельных или финальных вероятностей (иногда - стационарным вектором). Финальные вероятности определяют с помощью векторно-матричного уравнения

которое в развернутом виде будет выглядеть так:

К уравнениям (8.13а) можно дополнительно добавить условие нормировки:

Тогда любое из уравнений в (8.14) можно исключить.

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

Для эргодических цепей характеристикой, имеющей важное практическое значение, является продолжительность времени, за которое процесс из состояния S_i впервые попадает в S_j , так называемое время первого достижения. Матрица средних времен достижения определяется по формуле:

где

Матрица дисперсий времени первого достижения имеет несколько более сложный вид:

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

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

Очевидно, что при создании математических моделей в данном случае должны фигурировать следующие компоненты:

• конечное множество решений (альтернатив) K_i ,

• матрицы переходов П_[s]^(k), соответствующие тому или иному принятому к-решению;
• матрицы доходов (расходов) R_[s]^(k), также отражающие эффективность данного решения.

Таким образом, процесс функционирования системы описываемой УЦМ, выглядит следующим образом:

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

где

Задание стратегии означает полное описание конкретных решений, принимаемых на всех шагах процесса в зависимости от состояния, в котором находится в этот момент процесс.

Оптимальной будет такая стратегия, которая максимизирует полный ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода определения оптимальных стратегий: рекуррентный и итерационный [].

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

где

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

Конкретное применение метода будет рассмотрено ниже на примере.

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

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

Представим графически линейную зависимость суммарного дохода от числа шагов u_i (n) (рис. 8.11)

Рис.8.11. Зависимость суммарного дохода от числа шагов

Для наглядности график (рис. 8.11) изображен для УМЦ с двумя состояниями S₁ и S₂ . На графике прямая V₁(n) показывает зависимость суммарного дохода, если система "стартовала" из состояния S₁. Соответственно, прямая V₂(n) изображает ту же зависимость для состояния S₂ . Обе прямые могут быть описаны линейными уравнениями V_i(n):

где

g - угловой коэффициент прямой V_i(n);

V_i(0) - доход в i-том состоянии в конце процесса.

Легко заметить, что при таком представлении зависимости V_i(n) величина непосредственно ожидаемого дохода q (см. формулу (8.23)) заменяется g. Отличие здесь лишь в том, что g является величиной постоянной для всего процесса, в то время как q меняется на каждом шаге. Величина V_i(n) показывает, на сколько в среднем отличается доход, когда процесс заканчивается в том или ином состоянии, В теории марковских цепей V_i(n) называют весом, так как разница V_i(0) - V₂(0) при двух состояниях показывает средний выигрыш от того, в каком состоянии мы находимся в конце процесса (независимо от выбранной стратегии). Таким образом, подводя итоги общих рассуждений, можно сказать, что свойство эргодичности позволяет нам считать справедливым приближенное равенство:

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

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

Конкретные примеры расчетов как по первому, так и по второму методам будут даны ниже.

Как указывалось выше, простота и наглядность математического аппарата ДМЦ позволяет эффективно использовать его для принятия решений. При этом можно выделить два подхода:

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

Рассмотрим сначала примеры первого типа.

Предположим, что начало работы машины и подготовки саженцев происходит с одной и той же вероятностью p (причем отказ равен q=1-p ). Очевидно, что после успешного начала работы ЛПМ могут произойти следующие случайные события:

В₁ - посадка всех саженцев произошла успешно и ЛПМ в конце работы исправна (цель операции достигнута);

В₂ - во время работы ЛПМ произошел отказ, который может быть устранен на месте (обычно время восстановления лимитируется 30 мин.);

В₃ - во время работы машины произошел неустранимый отказ и она должна быть заменена;

В₄ - при исправной работе машины из-за нарушения технологии посадка саженцев произведена некачественно и требуется пересев;

В₅ - из-за неисправной работы машины посадка произведена некачественно.

Вероятность указанных условных событий (при условии успешного начала - p) обозначим:

а поскольку они несовместны и образуют полную группу, то

В результате реализации событий В_i [i=1,2,...,5] используемый процесс в любой момент времени может находиться в одном из следующих состояний (рис.8.12)

Рис. 8.12. Состояния системы

А₁ - посадка произведена успешно и в конце дня ЛПМ исправна;

А₃ - план не выполнен, требуется замена машины;

А₄ - план не выполнен, требуется новый комплект саженцев, ма-шина исправна;

А₅ - требуется новый комплект саженцев и исправная машина.

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

Таким образом, согласно принятым допущениям модель рассматриваемой операции представляет собой простую однородную поглощающую дискретную марковскую цепь с пятью состояниями. Переходные вероятности такой цепи определим с помощью алгебры событий:

А₁ А₂ А₃ А₄ А₅

В соответствии с приведенным выше математическим аппаратом матрица (8.29) может быть представлена в каноническом виде:

где, в данном случае,

- одноэлементная единичная под-матрица;

- нулевая вектор.строка;

Подматрица Q, описывающая процесс переходов в системе до выхода из невозвратного множества состояний выделена двойным пунктиром в матрице (8.29).

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

1. вероятность успешного проведения операции при заданном расходе средств на ее проведение Р(С₂) - (прямая задача);

2. необходимое (гарантированное) количество средств, обеспечивающее проведение работы с заданной вероятностью;

3. математические ожидания и дисперсии случайных расходов средств на операцию.

Рассмотрим в качестве критериев средние значения количеств ремонтов (или замен) ЛПХ - m_z1 и комплектов саженцев m_z2. Кроме того, в расходы войдут: стоимость частичного ремонта ЛПХ, а также расходы, связанные с дополнительным высевом саженцев при попадании в состояние А₂.

Таким образом, если задать величины расходов, связанные с попаданием в то или иное состояние (А₂, А₃, А₄, А₅) и опре-делить среднее число раз попадания в эти состояния, то в целом будут определены расходы на операцию.

Представим таблицу (или матрицу) расходов в виде:

где

С_с - стоимость комплекта саженцев и их посадки.

Среднее количество раз попадания в то или иное состояние (до поглощения) определится, как указывалось с помощью фундаментальной матрицы (стр. ). При этом надо иметь в виду, что, поскольку в данном случае процесс начинается только с состояния А₅ , то вычислять надо не все элементы матрицы (8.7), а лишь члены последней строки, т.е. m₄₁, m₄₂, m₄₃ и m₄₄.

В буквенном выражении все элементы матрицы (8.7) представляют довольно сложные выражения, поэтому далее приведем конкретный числовой пример:

Пусть значения r_i будут равны: r₁ = 0,77; r₂ = 0,1; r₃ = 0,05; r₄ = 0,04; r₅ = 0,03; р = 0,8.

Тогда после вычислений матрица (8.7) будет иметь вид:

Тогда среднее число замен посадочного материала и трактора будет равно, соответственно:

m_с = m₄₂ + m₄₄ = 1,296;

m_тр = m₄₃ + m₄₄ = 1,375;

а с учетом стоимости комплекта саженцев и материала:

Полученное выражение (8.31) позволяет решить три задачи:

1. Определить, соответствуют ли расходы на операцию располагаемым;

3. Оценить степень влияния каждой вероятности r_i на эффек-тивность операции и наметить мероприятия по ее провышению.

В качестве состояний системы принимаются:

S₁- болото; S₂ - Calluna ( вереск); S₃ - лес; S₄ - мелкий подрост, выеденный крупными травоядными.

Матрица перехода с учетом принятых в цитируемой работе переходных вероятностей P_ij в начальный момент имеет вид:

S₁ S₂ S₃ S₄

Несмотря на наличие нулей в первоначальной матрице, в работе показано, что в данной цепи отсутствуют поглощающие состояния и через некоторое количество шагов в ней возможны любые переходы и оно является эргодической. Так, например, с помощью уравнения Колмогорова-Чепмена (8.4) показано, что уже через два шага матрица имеет вид:

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

На основании формулы (8.20) вычисляются средние времена первых достижений каких-либо состояний. При этом матрица M_t будет иметь вид:

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

В приведенном выше примере финальная вероятность эргодической цепи определялись с помощью уравнения Колмогорова-Чепмена, однако, как указывалось выше, эти вероятности могут определяться и иным путем, с помощью решения системы уравнений вида (8.14). Такая задача возникает, в частности, при определении оптимальной стратегии контроля.

Как известно, существует два принципиально разных метода контроля: сплошной и выборочный.

Как показывают сами названия, при сплошном контроле проверяются подряд все образцы продукции. При этом методе, конечно, есть полная уверенность в отсутствии брака, однако, велики материальные затраты. При выборочном контроле существует вероятность пропуска бракованной продукции, но резко снижаются расходы, связанные с проверкой. Очевидно, при этом возникает задача определения оптимальной стратегии контроля. Одним из вариантов, в частности, может быть переменный контроль, когда при нормальном ходе производства контролируются малые выборки образцов продукции, а при повышении числа дефектных изделий контоль усиливается за счет больших размеров выборок. После проведения каких-либо мероприятий, направленных на устранение причин брака, можно вернуться к прежнему методу контроля. При такой формулировке задачи, очевидно, мы имеем дело со случайной последовательностью событий, обладающей марковским свойством. В данном случае ДМЦ будет иметь всего два состояния: S₁ - контроль при большой выборке и S₂ - контроль при малой выборке.

Изобразим одну реализацию процесса графически (рис. 8.13):

Рис. 8.13. Реализация процесса

Матрица перехода в этом случае будет иметь очень простой вид:

Легко убедиться, что данная цепь обладает свойством эргодичности. Использование этого свойства дает возможность ответить на некоторые практически важные вопросы:

1. Сколько раз в среднем в течение наблюдаемого перода мы попадаем в то или иное состояние?

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

2. Какова степень уверенности в том, что будет выпускаться требуемое количество годной продукции, или каково среднее значение брака во всей партии?

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

Ответ на первый вопрос получается довольно просто, если использовать приведенные выше уравнения для определения финальных вероятностей. В данном случае эти уравнения имеют вид:

Дополнительно может использоваться условие нормировки

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

Среднее число дефектных изделий, которое можно ожидать, если партия контролируется выборкой n _i (i = 1,2), равно:

Тогда, если учесть вероятность, с которой при контроле встретится та или иная выборка, общее среднее число дефектных изделий во всей продукции будет равно:

Далее с помощью какого-либо метода оптимизации можно определить стратегию и размеры выборок, обеспечивающие минимум потерь.

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

Мебельная фабрика выпускает новый вид продукции - комплект мебели. После выпуска пробной партии предприятие может оказаться в двух состояниях: S₁ - продукция оказалась удачной и пользуется спросом; S₂ - продукция оказалась неудачной. Допустим, что предполагается выпускать данный вид продукции в течение года, При этом, очевидно, руководство фабрики должно реагировать на то или иное состояние путем выбора определенной стратегии, которую по условиям производства можно менять не чаще и не реже, чеи один раз в квартал. Очевидно, вид той или иной стратегии зависит от состояния, в котором оказалась фабрика в начале текущего квартала. Предположим, что в распоряжении руководства имеется следующий набор мероприятий (стратегий):

- использование рекламы - стратегия 1;

- проведение дополнительных исследований требований потре-бителя и своих возможностей - стратегия 2.

Предположим также, что при попадании в то или иное состояние возможно объединение этих стратегий, то есть:

- в состоянии S₁ - реклама не используется и исследования не проводятся (стратегия 1);

- в состоянии S₂ - используются и реклама и дополнительные исследования (стратегия 2).

Очевидно, что переходы из состояния в состояние образуют случайную последовательность, обладающую свойством последействия.

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

Таблица 8.1.

В табл. 8.1 обозначены:

Р^k_ij - вероятность перехода из i-того состояния в j-е состояние

при стратегии К ;

u^k_ij - доходы (расходы) при переходе из i -ого в j -е состояние

при стратегии К ( в условных единицах).

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

При этом следует учесть, что поскольку в самом начале мы можем оказаться в одном из двух состояний, то этому будут соответствовать и два значения суммы среднего дохода, которые обозначим как v₁(n) и v₂(n), где n - количество шагов (этапов) до окончания процесса. В нашем случае n = 4. Как указывалось выше , v_i(n) будет равно:

v_i(n) = q_i + v_i (n-1), i = 1, 2,... (8.42)

где

Для стратегии 1 (к = 1):

При подсчете величины v_i (n - 1) удобнее начинать с конца процесса, так как при снятии продукции v_i(0) = v₂(0) = 0. Тогда за один квартал (шаг) до конца процесса

v⁽¹⁾₁(1) = q⁽¹⁾₁ = 5;

v₂(1) = q⁽¹⁾₂ = -2,6.

Для определения полного ожидаемого дохода за два квартала (шага) до смены продукции надо учесть, что система может оказаться в одном из двух состояний. При этом величины ожидаемых доходов v_i (n - 1) определяются с учетом переходных вероятностей по формуле ( 8. ):

Тогда полный суммарный доход за два квартала при первой стратегии будет равен:

Соответственно, доход за три квартала подсчитается аналогично:

Полный доход будет равен:

Окончательный доход при первой стратегии будет равен:

Тогда полный окончательный доход будет равен:

Аналогичные расчеты должны быть теперь проделаны при второй стратегии. Не приводя тривиальных вычислений, укажем их результаты и графики ( рис. 8. 14 )).

В верхней части графика показаны зависимости ожидаемых доходов при начале процесса из состояния S₁ (удачная модель), в нижней - при состоянии S₂ (неудачная модель).

Из этого графика можно сделать следующие выводы:

• оптимальная стратегия на каждом шаге должна выбираться по максимальному значению помимо дохода. Оптимальность стратегии на всем многошаговом процессе обеспечивается применением принципа оптимальности Беллмана, согласно которому оптимальное управление в многошаговом процессе должно быть оптимальным на каждом шаге с учетом предистории процесса;
• в данном случае на основании расчетов при начале процесса из состояния S₁ , вектор оптимальных стратегий будет иметь вид:

Это означает, что, если фабрика начала выпускать сразу удачную модель, то первые три квартала выгодно применять вторую стратегию (реклама и исследование). За один квартал до перехода на новую модель целесообразно прекратить и рекламу и исследования.

Если же начальным было состояние S₁ , то рекламу и иссле- дования следует применить лишь два первых квартала, затем следует освободившиеся средства употребить на подготовку производства новой модели. Таким образом, и при удачной и неудачной моделях оказывается все же выгодным начинать производство, обеспеченное как рекламой, так и исследованиями.

Заметим, что в данном случае не был ясным вопрос о том, с какой вероятностью наступят состояния S₁ и S₂ . Для этого следовало бы ввести вектор начальных вероятностей, что несколько усложнило бы вычисление. Описанный выше метод, как указывалось выше, обладает сравнительной простотой, но при малом числе этапов. Кроме того, в этом методе несколько затруднен процесс автоматизации расчетов на ЭВМ. Более универсальным и удобным в этом смысле является итерационный метод.

На лесозаготовительном предприятии производится сплошная рубка леса с помощью трех валочно-пакетирующих машин (ВПМ), работающих на трех лесосеках, соединенных между собой дорогами. Техническое обслуживание и текущий ремонт машин осуществляется с помощью передвижной ремонтной мастерской (ПРМ), базирующейся, в свою очередь, в центральной ремонтной мастерской (ЦРМ). Все три ВПМ имеют разный ресурс и, естественно, разную вероятность безотказной работы (ВБР).

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

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

Стратегия 1 - поочередный объезд всех машин с одновременной диагностикой состояния и устранением мелких отказов (настройка, регулировка и т.д.).

Стратегия 2 - дежурство ПРМ вблизи самой изношенной машины и выезд к двум другим ВПМ в случае необходимости. При этом сокращается время поездки, обеспечивается быстрое устранение отказа у самого "слабого" звена, но не всегда возможен быстрый и качественный ремонт из-за отсутствия необходимых запчастей и инструмента.

Стратегия 3 - дежурство ПРМ на центральной мастерской и срочный выезд к отказавшей ВПМ по вызову. При такой стратегии за счет времени поездки к данной ВПМ увеличивается время простоя, но устранение отказа может быть выполнено быстро и качественно, так как при известной причине отказа в ЦРМ могут быть взяты необходимые запчасти и приспособления.

Очевидно, что вследствие случайных событий (отказов), которые могут произойти у любой машины, передвижения ПРМ по какому-либо маршруту будут также событиями случайными.

В качестве состояний примем местонахождение ПРМ у какой-либо ВПМ (рис. 8.15):

Обозначим эти состояния, соответственно, S_А, S_Б , S_В .

Вероятность каждой последующей поездки ПРМ и переход в соответствующее состояние зависят только от того, в каком состоянии она находится в данный момент.

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

Допустим, что в результате предварительного анализа известны значения переходных вероятностей, связанные с данной стратегией Р^(k)_ij , а также доходы u^(k)_ij . Эти исходные данные сведем в табл. 8.2:

Таблица 8.2

Примечание: для каждого состояния и соответствующих стратегий в таблице заранее подсчитаны значения непосредственно ожидаемых доходов q^k_i , например,

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

Процедура стратегий, также как и ранее в рекурентном методе начинается с предположения, что

v₁ (0) = v₂ (0) = v₃ (0). (8.45)

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

Это означает, что, где бы не находилась ПРМ после окончания поездки, выгоднее использовать первую стратегию (переезды от одной ВПМ к другой). Значения непосредственно ожидаемого дохода , равные в данном случае угловым коэффициентам прямых v_i (0) (см. рис. 8. ) будут, соответственно, равны:

q⁽¹⁾₁ = q₁ = 8; q⁽¹⁾₂ = q₂ = 7; q⁽¹⁾₃ = q₃ = 16.

Произведем теперь первое уточнение (итерацию) для первого этапа n = 1. Для нашего случая с учетом данных (табл. 8.2) систем уравнений (8.47) будет иметь вид:

В системе (8.47) четыре неизвестных. Для ее решения необходимо произвольнозадаться одним из них. Положим, например, v₃ = 0.

Тогда v₁ = 1,33; v₂ = 7,47; v₃ = 0; g = 9,2.

для первого состояния и второй стратегии:

q⁽²⁾_i + Р⁽²⁾₁₁v ₁ + Р⁽²⁾₁₂v₂ + P⁽²⁾₁₃v₃ =

Таблица 8.3

Судя по данным таблицы, оптимальным решением будут теперь стратегии:

т.е. на основании уточнения, при попадании в состояние S_А(1) следовать первой стратегии. В случае, если в результате очередной поездки мы попали в состояние S_Б(2), выгоднее следовать к изношенной машине.

Матрица перехода и вектор непосредственно ожидаемого дохода теперь будут иметь вид:

Определим снова значения весов:

g + v₁ = 8 + 0,5 v₁+ 0,25 v₂+ 0,25 v₃;

g + v₂= 4 + 0,125 v₁ + 0,75 v₂+ 0,125 v₃;

g + v₃ = 15 + 0,0625 v₁ + 0,875 v₂ + 0,0625 v₃;

Принимая снова v₃= 0, получим:

v₁ = -3,88 ; v₂ = 12,85; v₃ = 0; g = 13,15.

Обратите внимание, что даже одна итерация дала существенное увеличение дохода ( с 9,2 до 13,15 у.е.)

Сделаем еще одну итерацию, используя данные, полученные при первой итерации. Приведем снова уравнение для первого состояния:

q⁽¹⁾₁ + Р⁽¹⁾₁₁v₁ + Р⁽¹⁾₁₂v₂ + P⁽¹⁾₁₃v₃ =

q⁽²⁾₁+ Р⁽²⁾₁₁v ₁ + Р⁽²⁾₁₂v₂ + P⁽²⁾₁₃v₃ =

q⁽³⁾₁+ Р⁽²⁾₁₁v ₁ + Р⁽²⁾₁₂v₂ + P⁽²⁾₁₃v₃ =

Таблица 8.4

Значит снова получается, что оптимальной во всех состояниях оказывается стратегия (2) и вектор решений имеет вид:

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