Лекции.Орг


Поиск:




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




Введение

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

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

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

Пусть 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 ):

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

 





Поделиться с друзьями:


Дата добавления: 2015-09-20; Мы поможем в написании ваших работ!; просмотров: 1850 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Если президенты не могут делать этого со своими женами, они делают это со своими странами © Иосиф Бродский
==> читать все изречения...

996 - | 939 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.