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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Решение задачи методом полного перебора - №1 - открытая онлайн библиотека

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

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

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

Решение задачи методом полного перебора - №2 - открытая онлайн библиотека

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

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

Решение задачи методом полного перебора - №3 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №4 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №5 - открытая онлайн библиотека

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

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

Решение задачи методом полного перебора - №6 - открытая онлайн библиотека

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

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

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

Решение задачи методом полного перебора - №7 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №8 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №9 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №10 - открытая онлайн библиотека

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

1. Вычисление ожидаемого одношагового дохода Решение задачи методом полного перебора - №11 - открытая онлайн библиотека по формуле:

Решение задачи методом полного перебора - №12 - открытая онлайн библиотека

Решение задачи методом полного перебора - №13 - открытая онлайн библиотека - ожидаемый одношаговый доход;

Решение задачи методом полного перебора - №14 - открытая онлайн библиотека – переходная вероятность – условная вероятность того, что из состояния i в результате испытания система перейдет в состояние j;

Решение задачи методом полного перебора - №15 - открытая онлайн библиотека – значение i доходности

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

Решение задачи методом полного перебора - №16 - открытая онлайн библиотека

2. Вычисляются стационарные вероятности матрицы переходных вероятностей из уравнений Решение задачи методом полного перебора - №17 - открытая онлайн библиотека :

Решение задачи методом полного перебора - №18 - открытая онлайн библиотека

Решение задачи методом полного перебора - №19 - открытая онлайн библиотека - матрица переходных вероятностей;

Решение задачи методом полного перебора - №20 - открытая онлайн библиотека - стационарная вероятность

Решение задачи методом полного перебора - №21 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №22 - открытая онлайн библиотека

Решение задачи методом полного перебора - №23 - открытая онлайн библиотека

Решение задачи методом полного перебора - №24 - открытая онлайн библиотека

Решение задачи методом полного перебора - №25 - открытая онлайн библиотека

Решение задачи методом полного перебора - №24 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №27 - открытая онлайн библиотека

3. Необходимо найти ожидаемый доход Решение задачи методом полного перебора - №28 - открытая онлайн библиотека для стратегии S по формуле:

Решение задачи методом полного перебора - №29 - открытая онлайн библиотека

Решение задачи методом полного перебора - №28 - открытая онлайн библиотека - ожидаемый доход;

Решение задачи методом полного перебора - №17 - открытая онлайн библиотека - стационарная вероятность;

Решение задачи методом полного перебора - №11 - открытая онлайн библиотека - ожидаемый одношаговый доход

Решение задачи методом полного перебора - №33 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №35 - открытая онлайн библиотека

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

Решение задачи методом полного перебора - №36 - открытая онлайн библиотека