Решение задачи методом полного перебора

Введение

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

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

Случайный процесс называется марковским процессом (или «процессом без последствия»), если для каждого момента времени t₀вероятность любого состояния системы в будущем (при t>t₀) зависит только от её состояния в настоящем (при t= t₀) и не зависит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлом).

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

Расчетно-графическая работа выполняется с помощью программы ²Оптимальное моделирование и управление в системах марковского типа². Программа написана на алгоритмическом языке VISUAL BASIC и оформлена в виде модуля табличного процессора EXCEL. Программа позволяет решать задачи марковского типа с помощью метода полного перебора и метода итераций.

Решение задачи методом полного перебора

Метод полного перебора основан на переборе всех стационарных стратегий.

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

1) “Создать таблицы”;

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

1) число альтернатив управления;

2) число состояний системы;

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

1) "Начальные вероятности состояний системы;

2) "Возможные стратегии" – таблица для ввода правил, в соответствии с которыми на каждом шаге марковского процесса выбирается управленческая альтернатива в зависимости от состояния системы;

3) "Матрицы переходных вероятностей" - таблица для ввода всех переходных вероятностей, т.е. условных вероятностей того, что из состояния i в результате испытания система перейдет в состояние j (от 1 до 8)

4) "Матрицы доходов" (от 1 до 8)

5) "Ожидаемый одношаговый доход";

6) "Стационарные вероятности"

7) "Оптимальный доход";

8) "Максимальный доход "

Данные для начальных вероятностей системы, матриц переходных вероятностей 1 и 2 и матриц доходов 1 и 2 берутся из лабораторной работы «Оптимальное моделирование и управление в системах марковского типа».

Далее для каждой стационарной стратегии формируются матрицы переходных вероятностей 3-8 и матрицы доходов 3-8. Для этого необходимо модернизировать состояния согласно возможным стратегиям поведения.

Следующим шагом является формирование матрицы переходных вероятностей 3 и матрицы дохода 3. В таблице «Возможные стратегии» стационарной стратегии 3 соответствуют состояния 2, 1, 1:

Матрицы переходных вероятностей и матрицы дохода 1 и 2 заданы и имеют вид:

Например, при формировании матрицы переходных вероятностей 3 и матрицы дохода 3, происходит модернизация состояния 1.

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

Метод полного перебора включает в себя 4 шага:

1. Вычисление ожидаемого одношагового дохода по формуле:

- ожидаемый одношаговый доход;

– переходная вероятность – условная вероятность того, что из состояния i в результате испытания система перейдет в состояние j;

– значение i доходности

Результаты вычислений заносим в таблицу:

2. Вычисляются стационарные вероятности матрицы переходных вероятностей из уравнений :

- матрица переходных вероятностей;

- стационарная вероятность

Далее необходимо убрать из каждой системы уравнений одно любое уравнение и найти решение систем методом обратной матрицы с использованием встроенных функций Excel (в нашем случае из системы уравнений (страт_1) убираем второе уравнение, из системы уравнений (страт_2) убираем третье уравнение). Для нахождения решений используется формула:

Результаты решения систем уравнений заносятся в таблицу и формируются согласно возможным стратегиям стационарные вероятности для стратегий 3-8:

3. Необходимо найти ожидаемый доход для стратегии S по формуле:

- ожидаемый доход;

- стационарная вероятность;

- ожидаемый одношаговый доход

4. Выбирается максимальное значение среди одношаговых доходов (max ):

Таким образом, была найдена оптимальная стратегия: