Вычисление площади произвольной фигуры методом Монте-Карло.

Площадь произвольной фигуры можно вычислить методом Монте-Карло.

Фигура вписывается в другую фигуру с известной площадью. Случайным образом на последнюю ставятся произвольное количество точек. Площадь определяется по формуле S=Nф/N, где Nф – количество точек попавших в заданную фигуру, N – общее количество точек. Достоинство данного метода заключается в простоте реализации, сложность состоит только в определении попадания точки внутрь заданной фигуры. Очевидно, что точность вычисленной площади зависит от количества точек. Приемлемая точность может быть достигнута только при большом их количестве. В этом заключается один из недостатков метода. Точность также сильно зависит от

качества генератора случайных чисел.

 

46. Дискетное программирование. Метод ветвей и границ. В основе метода “ветвей и границ ” лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода элементов разбиения подвергается проверке для выяснения содержит данное подмножество оптимальное решение или нет.

Проверка осуществляется посредством вычисления оценки снизу для целевой ф-ий на данном подмножестве. Если оценка снизу не меньше “рекорда ”-наилучший из Найденных решений,то подмножество может быть отброшено. Проверка подмножества может быть отброшено еще и в том случае, когда в нем удастся найти наилучшее решение. Если значение целевой ф-ции на найденном решении меньше “рекорда”,то происходит смена “рекорда”.

По окончании работы алгоритма “ рекорд” является результат его работы.

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

 

 

51. Имитационное моделирование. Метод Монте-Карло, область применения

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

1.Непрерывные

2.Дискретные

3.Пространственные

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

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

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

В случае пространственных моделей рассматриваются процессы, происходящие в пространстве на плоскости или в объеме

ДЛЯ ПОСТРОЕНИЯ ИМИТАЦИОННЫХ МОДЕЛЕЙ используются переменные типов – фонд (объем искомого продукта, оценка некоторых вероятностей), поток (объем количества продукта который поступает или извлекается из соответствующего фонда в единицу модельного времени), время, конвертор

Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а: М(Х)=а.

Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое и принимают x в качестве оценки (приближённого значения) a* искомого числа a:

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

 

48. Простешие задачи,решаемые методом динамическим программировании.

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

 

52. Метод Монте-Карло. Сущность, оценка погрешности, область применения.

Оценка погрешности метода Монте-Карло.

Пусть для получения оценки a* математического ожидания а случайной величины Х было произведено n независимых испытаний (разыграно n возможных значений Х) и по ним была найдена выборочная средняя, которая принята в качестве искомой оценки. Ясно, что если повторить опыт, то будут получены другие возможные значения Х, следовательно, другая средняя, а значит, и другая оценка a*. Уже отсюда следует, что получить точную оценку математического ожидания невозможно. Естественно возникает вопрос о величине допускаемой ошибки. Ограничимся отысканием лишь верхней границы d допускаемой ошибки с заданной вероятностью (надёжностью) g.

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

1. Случайная величина Х распределена нормально и её среднее квадратичное отклонение d известно.

В этом случае с надёжностью g верхняя граница ошибки, (*)

где n число испытаний (разыгранных значений Х); t – значение аргумента функции Лапласа, при котором, s - известное среднее квадратичное отклонение Х.

2. Случайная величина Х распределена нормально, причём её среднее квадратическое отклонение s неизвестно.

В этом случае с надёжностью g верхняя граница ошибки, (**)

где n – число испытаний; s – «исправленное» среднее квадратическое отклонение, находят по таблице приложения 3.

3. Случайная величина Х распределена по закону, отличному от нормального.

В этом случае при достаточно большом числе испытаний (n>30) с надёжностью, приближённо равной g, верхняя граница ошибки может быть вычислена по формуле (*), если среднее квадратическое отклонение s случайной величины Х известно; если же s неизвестно, то можно подставить в формулу (*) его оценку s – «исправленное» среднее квадратическое отклонение либо воспользоваться формулой (**). Заметим, что чем больше n, тем меньше различие между результатами, которые дают обе формулы. Это объясняется тем, что при распределение Стьюдента стремится к нормальному.

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

 

45 Дискетное программирование. Метод Гомори. Идея метода Гомори состоит в том,что поставленную задачу сначала решаем любым методом линейного программирования(напр симплекс методом),а затем в полученном ответе выделяем дробных части и составляем дополнительное ограничение. Полученное дополнительное ограничение вводим в последнюю(по ходу решения)матрицу симплексного метода и определяем целочисленный ответ.

54. Элементы теории матричных игр. Основные понятия и определения.

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

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

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

Целью игры является нахождение оптимальной стратегии для каждого игрока, т. е. такой, при которой достигается максимум ожидаемого

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

Матричная игра – это парная игра, которая задается набором чистых стратегий {1...n} и {1....m} первого и второго игроков, а также платежной матрицей (Ay)mxn, определяющей выигрыш первого игрока при выборе игроками стратегий i и j соответственно. Целью первого игрока является максимизация своего выигрыша, а целью второго – минимизация выигрыша противника.

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

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

Стратегия игрока называется оптимальной, если при многократном повторении игры его средний выигрыш максимален.

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

Стратегии бывают чистыми (неслучайные решения игроков) и смешанными (стратегию можно рассматривать как случайную величину).

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

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

 

41. Сетевая модель. Алгоритм ранжирования событий.

Нумерацию событий рекомендуется выполнять по след. Алгоритму:

1.Определить начальное событие.Это событие А.

2.Условно вычеркнуть работы, выходящие из начального события А. Событиям Б,В и Г, которые имеют только входящие работы, присвоить ранг 1.

3.Условно вычеркиваем работы, выходящие из событий 1-го ранга. Событиям Д и Е присваиваем ранг 2 и т.д. Событиям 3 и Ж – ранг 3, событию И- 4.

4.После назначения ранга событиям выполняется нумерация событий по след. Правилам:

-Собыитя нумеруются слева направо, т.е. от начального события к конечному

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

 

 

55. Элементы теории матричных игр. Цена игры, стратегии

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

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

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

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

Матричная игра – это парная игра, которая задается набором чистых стратегий {1...n} и {1....m} первого и второго игроков, а также платежной матрицей (Ay)mxn, определяющей выигрыш первого игрока при выборе игроками стратегий i и j соответственно. Целью первого игрока является максимизация своего выигрыша, а целью второго – минимизация выигрыша противника.

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

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

Стратегия игрока называется оптимальной, если при многократном повторении игры его средний выигрыш максимален.

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

Стратегии бывают чистыми (неслучайные решения игроков) и смешанными (стратегию можно рассматривать как случайную величину).

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

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

 

 

56. Игры с природой. Основные понятия и определения.

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

Игра с противодействием – конфликтная ситуация, развивающаяся спонтанно.

Игровая модель строится по определенным законам, а игроки придерживаются определенных правил.

Парная игра – игра с участием минимум двух человек.

Множественная игра – игра с участием нескольких человек.

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

Конечная игра – игра содержащая ограниченное количество стратегий.

Бесконечная игра – не имеющая ограничений на стратегию.

Оптимальная стратегия – приносящая игроку максимальный выигрыш.

Нулевая сумма – сумма выигрыша одного игрока является суммой проигрыша другого, итого в сумме нуль.

Нижняя цена игры – минимально гарантированный выигрыш.

Верхняя цена игры – минимально возможный проигрыш.

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

Устойчивая стратегия – стратегия, при которой нижняя цена игры = верхней цене игры (задача с Седловой точкой)

Формулировка осторожной стратегии – получить максимальный доход из возможных минимальных.

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

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

Доминирующий столбец – столбец, содержащий элементы меньшие

 

 

57. Игры с природой. Критерий Вальце и Гульвица.

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

Игра с противодействием – конфликтная ситуация, развивающаяся спонтанно.

Игровая модель строится по определенным законам, а игроки придерживаются определенных правил.

Парная игра – игра с участием минимум двух человек.

Множественная игра – игра с участием нескольких человек.

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

Конечная игра – игра содержащая ограниченное количество стратегий.

Бесконечная игра – не имеющая ограничений на стратегию.

Оптимальная стратегия – приносящая игроку максимальный выигрыш.

Нулевая сумма – сумма выигрыша одного игрока является суммой проигрыша другого, итого в сумме нуль.

Нижняя цена игры – минимально гарантированный выигрыш.

Верхняя цена игры – минимально возможный проигрыш.

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

Устойчивая стратегия – стратегия, при которой нижняя цена игры = верхней цене игры (задача с Седловой точкой)

Формулировка осторожной стратегии – получить максимальный доход из возможных минимальных.

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

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

Доминирующий столбец – столбец, содержащий элементы меньшие

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

Критерий Гурвица – занимает промежуточное значение между Вальде и максимума. Сам игрок определяет вероятность своего «везения». Max (αmina_ij+ (1- α) maxa_ij) где 0 <= α<= 1.