Конспект лекций по теме "Компьютерное моделирование"

Введение

Слово «модель» (от лат. modelium) означает «мера», «способ», «сходство с какой–то вещью».

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

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

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

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

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

Для моделей, предназначенных для приблизительных расчетов, удовлетворительной считается точность 10-15%, а для моделей, предназначенных для использования в управляющих и контролирующих системах – 1-2%.

Любая модель обладает следующими свойствами:

·        конечностью: модель отображает оригинал лишь в конечном числе его отношений;

·        упрощенностью: модель отображает только существенные стороны объекта;

·        приблизительностью: действительность отображается моделью грубо или приблизительно;

·        адекватностью: модель успешно описывает моделируемую систему;

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

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

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

Компьютерное моделирование как метод научного познания

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

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

·        для ВЭ не требуется сложного лабораторного оборудования;

·        существенное сокращение временных затрат на эксперимент;

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

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

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

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

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

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

Лекция №1. Понятие Модель. Области применения моделей. Основные определения. Классификация моделей. Этапы моделирования.

Человек в своей деятельности постоянно создает и использует модели окружающего мира.

1. Модели позволяют представить в наглядной форме объекты и процессы, недоступные для непосредственного восприятия:

Физика: модели различных явлений;

География: глобус – модель земли (реальный размер очень большой);

Химия – модели кристаллическая решетка молекул (реальные размеры очень маленькие);

Биология – по муляжу человека изучаем внутреннее строение

2. При проектировании механизмов и устройств, зданий, электрических цепей используют модели – чертежи и макеты. Математика – изучение объемных фигур

3. Теоретические модели (для развития науки) – теории законов, гипотез и т.д. Иногда создание таких моделей коренным образом меняет представления человека об окружающем мире: Коперник- гелиоцентрическая система мира, модель атома Резерфорда-Бора, геном человека)

4. Художественное творчество - перенос реальной действительности на полотно, скульптура, театр, басня – отношения между животными – отношения между людьми

Основные определения:

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

Моделирование – метод познания, состоящий в создании и исследовании моделей. Т.е. исследование объектов путем построения и изучения моделей.

Формализация – процесс построения информационных моделей с помощью формальных языков.

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

Параметр – признак или величина, характеризующая какое-либо свойство объекта и принимаемая различные значения.

Среда – условие существование объекта.

Операция – действие, изменяющее свойство объекта.

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

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

Один и тот же объект может иметь множество моделей:

объект «ЧЕЛОВЕК» его модели:

1) химия - БИОХИМИЧЕСКИЙ СОСТАВ

2) анатомия - СКЕЛЕТ, СТРОЕНИЕ ВНУТРЕННИХ ОРГАНОВ

3) физика - МАТЕРИАЛЬНАЯ ТОЧКА

Разные объекты могут описываться одной моделью:

модель «КАРТА» её объекты :

1) ПОЛЕЗНЫЕ ИСКОПАЕМЫЕ - на карте полезных ископаемых

2) КЛИМАТИЧЕСКИЕ ЗОНЫ - на карте климатических зон

3) ГОСУДАРСТВА, СТРАНЫ - на политической карте

4) ЗВЕЗДЫ - на звездной карте

5) ТУЗЫ, ДАМЫ, ВОЛЬТЫ и пр. - игральные карты 

Существуют различные классификации моделей.

1) по области использования:

·   Учебные модели – используются при обучении; (глобус, периодическая система элементов Менделеева, скелет, атлас)

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

·   Научно - технические - создаются для исследования процессов и явлений (модель движения планет Солнечной системы, прибор имитирующий молнию)

·   Игровые – репетиция поведения объекта в различных условиях (военные игры, экономические игры)

·   Имитационные – отражение реальности в той или иной степени (это метод проб и ошибок) (проверка действия лекарства на мышах, эксперименты в школе(12 летняя система обучения))

·   Функциональные – заменяют объекты при выполнении каких-либо функций (протезы, манипуляторы, аппарат искусственной почки)

2) по фактору времени:

·   Статические – модели, описывающие состояние системы в определенный момент времени (единовременный срез информации по данному объекту). Примеры моделей: классификация животных…., строение молекул, список посаженных деревьев, отчет об обследовании состояния зубов в школе и тд.

·   Динамические (дискретные и непрерывные) – модели, описывающие процессы изменения и развития системы (изменения объекта во времени). Примеры: описание движения тел, развития организмов, процесс химических реакций (карточка в стоматологической клинике).

3) по отрасли знаний - это классификация по отрасли деятельности человека:

·   математические,

·   биологические,

·   химические (перегонка нефти),

·   социальные,

·   экономические,

·   исторические (карта сражений)

·   физические (второй закон Ньютона)и тд

4) по форме представления, возможности реализации:

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

·   Абстрактные (нематериальные) – не имеют реального воплощения. Их основу составляет информация. это теоретический метод познания окружающей среды. По признаку реализации они бывают:  мысленные и вербальные; информационные

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

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

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

Типы информационных моделей:

o   Табличные – объекты и их свойства представлены в виде списка, а их значения размещаются в ячейках прямоугольной формы. Перечень однотипных объектов размещен в первом столбце (или строке), а значения их свойств размещаются в следующих столбцах (или строках) (расписание уроков, таблицы) (В табличной информационной модели перечень однотипных объектов или свойств размещен в первом столбце (или строке) таблицы, а значения их свойств размещаются в следующих столбцах (или строках) таблицы, Построим табличную информационную модель "Цены устройств компьютера".) (Периодическая система Менделеева)

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

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

По степени формализации информационные модели бывают образно-знаковые и знаковые.

Образно-знаковые модели:

·   Геометрические (рисунок, пиктограмма, чертеж, карта, план, объемное изображение)

·   Структурные (таблица, граф, схема, диаграмма)

·   Словесные (описание естественными языками) (Так в романе Л. Н. Толстого «Война и мир» можно найти словесное описание Бородинского сражения.)

·   Алгоритмические (нумерованный список, пошаговое перечисление, блок-схема)

Знаковые модели:

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

·   Специальные – представлены на спец. языках (ноты, хим. формулы)

·   Алгоритмические – программы

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

В настоящее время выделяют два вида компьютерных моделей:

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

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

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

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

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

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

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

Лабораторный эксперимент	Вычислительный эксперимент
Образец Физический прибор Калибровка прибора Измерение Анализ данных	Модель Программа для компьютера Тестирование программы Расчет Анализ данных

Рассмотрим этапы моделирования на примере.

Явление: полет тела, брошенного под углом к горизонту.

Цель моделирования: определить дальность полета тела, брошенного под углом к горизонту.

1 этап – построение описательной модели.

Упростим процесс.

Сопротивлением воздуха можно пренебречь.

Размеры тела малы с траекторией полета, поэтому тело можно считать материальной точкой.

2 этап – формализация (запись задачи при помощи формул)

Построим математическую модель.

Дано: V₀ – начальная скорость (м/с);

           a    –  угол бросания;

Найти: L – дальность полета (м).

Решение: , где t – время полета;

 - ордината точки падения;

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

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

 - ускорение свободного падения.

Ограничения:

Опишем метод решения последовательностью формул:

 

 

 

3 этап – алгоритмизация.

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

4 этап – составление программы:

Составим программу на языке программирования Паскаль.

Const g=9.8;

Var Vx, Vy, Vo, A, T, L: real;

Begin

         Write(‘Vo, A=’); readln(Vo, A);

         Vy:=Vo*sin(A);

         Vx:=Vo*cos(A);

         T:=2*Vy/g;

L:=Vx*T;

Writeln(‘L=’,L);

End.

5 этап – компьютерный эксперимент – запуск программы на выполнение (при необходимости – отладка программы) и получение результатов.

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

Общая схема процесса компьютерного математического моделирования:

Моделирование и его виды

Моделирование является одним из способов познания мира.

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

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

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

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

Моделирование проходит три этапа:

1.     Создание модели.

2.     Изучение модели.

3.     Применение результатов исследования на практике и/или формулирование теоретических выводов.

Видов моделирования огромное количество. Вот некоторые примеры типов моделей:

Математические модели. Это знаковые модели, описывающие определенные числовые соотношения.

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

Имитационные модели. Позволяют наблюдать изменение поведения элементов системы-модели, проводить эксперименты, изменяя некоторые параметры модели.

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

Особенности компьютерного моделирования

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

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

Для компьютерного моделирования важно наличие определенного программного обеспечения.

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

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

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

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

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

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

Методы исследования сложных систем

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

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

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

·        методом синтеза оптимальной структуры системы с заданными характеристиками;

·        методом анализа различных вариантов структуры системы для обеспечения требуемых технических характеристик.

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

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

Среди известных методов анализа показателей эффективности систем и исследования динамики их функционирования следует отметить:

·        аналитический метод;

·        метод натуральных испытаний;

·        метод полунатурального моделирования;

·        моделирование процесса функционирования системы на ЭВМ.

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

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

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

Исследование функционирования сложных систем с помощью моделирования их работы на ЭВМ помогает сократить время и средства на разработку.

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

Лекция №2. Математическое моделирование

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

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

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

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

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

Математическое моделирование можно условно подразделить по типу и методу построения решения модели: аналитическое, численное (разностное), диаграммное и имитационное.

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

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

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

Классификация математических моделей.

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

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

Математические модели с сосредоточенными параметрами.

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

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

Математические модели с распределенными параметрами.

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

Математические модели, основанные на экстремальных принципах.

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

Основной принцип классификации математических моделей

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

   физические процессы;

   технические приложения, в том числе управляемые системы, искусственный интеллект;

   жизненные процессы (биология, физиология, медицина);

   большие системы, связанные с взаимодействием людей (социальные, экономические, экологические);

   гуманитарные науки (языкознание, искусство).

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

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

По форме представления математических моделей различают инвариантную, алгоритмическую, аналитическую и графическую модели объекта проектирования.

Классификация математических моделей (ТО - технический объект)

Виды математических моделей технических объектов
По форме представления ММ		По характеру отображаемых свойств ТО		По степени абстрагирования		По способу получения ММ
Инвариантные		Функциональные		ММ микроуровня (с распределенными параметрами)		Теоретические
Алгоритмические		Структурные		ММ макроуровня (со средоточенными параметрами)		Экспериментальные факторные
Аналитические				ММ метауровня
Графические (схемные)

К математическим моделям предъявляются требования адекватности, экономичности, универсальности. Эти требования противоречивы.

По форме представления математических моделей различают инвариантную, алгоритмическую, аналитическую и графическую модели объекта проектирования.

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

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

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

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

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

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

Функциональные модели описывают процессы функционирования технических объектов и имеют форму систем уравнений. Они учитывают структурные и функциональные свойства объекта и позволяют решать задачи как параметрического, так и структурного синтеза. Их широко используют на всех уровнях  проектирования. На метауровне функциональные задачи позволяют решать задачи прогнозирования, на макроуровне - выбора структуры и оптимизации внутренних параметров технического объекта, на микроуровне - оптимизации параметров базовых элементов.

Этапы математического моделирования

·        Первый этап – построение математической модели

·        Второй этап – выбор метода решения

·        Третий этап – разработка и применение программного обеспечения

·        Четвертый этап моделирования –компьютерное исследование или вычислительный эксперимент

·        Пятый этап – обработка и анализ результатов вычислительного эксперимента

Методы решения математических моделей

Математические модели можно решать различными методами.

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

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

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

4.                 Использование различных информационных систем компьютерной математики, например, пакетов Maple, MathCad, Mathematics, Excel и т.д. для решения математических задач, в которых можно провести компьютерное моделирование реальных процессов и явлений. Отметим, что эти системы являются отражением разработанных численных методов на современном этапе и их возможности часто при решении сложных задач бывают ограниченными.

5.                 Метод виртуального эксперимента с помощью аналоговых вычислительных машин (АВМ). К сожалению, с бурным развитием ЭВМ, развитие АВМ отошло на второй план. Однако отметим, что появились информационные системы, в частности Electronics Workbench, Simulink+MatLAB, Maple, Vissim, позволяющие на ЭВМ имитировать работу АВМ. В этих пакетах имеется возможность решать и анализировать математические модели с помощью имитаторов электронных приборов и логических схем.

Уравнения матфизики

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

Напомню, что дифференциальным уравнением называется уравнение, куда входит искомая функция со своими производными

Лекция №3. Моделирование процесса теплопроводности

В качестве примера модели, в основе которой лежит уравнение матфизики, рассмотрим модель распространения тепла в однородном стрежне. Задача теплопроводности.

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

Обозначим температуру стержня в точке с координатой х в момент времени t через u(x,t). Уравнение теплопроводности имеет вид

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

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

u(x,0) = φ(x)

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

u(0,t)=ψ₀(t), u(l,t)=ψ_l(t)

Заметим, что начальные и граничные условия должны быть согласованы, т.е.

u(0,0) = φ(0)=ψ₀(0)

u(l,0) = φ(l)=ψ_l(0)

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

Введем равномерную прямоугольную сетку с помощью координатных линий

x_i=ih, i=0,1,....n,

t_j=jτ, j=0,1,....m,

где h - это шаг по пространству, по координате х, а τ - шаг по времени.

Значения функции в узлах сетки обозначим u_i^j=u(x_i,t_j).

Входящие в уравнение производные заменим их конечно-разностными аппроксимациями

получим

Построенная схема позволяет нам находить значение функции температур на j+1 слое через значения на j слое. Для начало счета при j=0 необходимо знать значения функции температур на нулевом слое. Они нам известны из начальных условий.

Лекция №4. Имитационное моделирование.

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

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

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

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

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

Применение имитационного моделирования

К имитационному моделированию прибегают, когда:

·        дорого или невозможно экспериментировать на реальном объекте;

·        невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические (случайные) переменные;

·        необходимо сымитировать поведение системы во времени.

Цель имитационного моделирования состоит в воспроизведении поведения исследуемой системы на основе результатов анализа наиболее существенных взаимосвязей между ее элементами или другими словами — разработке симулятора (англ. simulation modeling) исследуемой предметной области для проведения различных экспериментов.

Имитационное моделирование позволяет имитировать поведение системы во времени. Причём плюсом является то, что временем в модели можно управлять: замедлять в случае с быстропротекающими процессами и ускорять для моделирования систем с медленной изменчивостью. Можно имитировать поведение тех объектов, реальные эксперименты с которыми дороги, невозможны или опасны. С наступлением эпохи персональных компьютеров производство сложных и уникальных изделий, как правило, сопровождается компьютерным трёхмерным имитационным моделированием. Эта точная и относительно быстрая технология позволяет накопить все необходимые знания, оборудование и полуфабрикаты для будущего изделия до начала производства. Компьютерное 3D моделирование теперь не редкость даже для небольших компаний.

Имитация, как метод решения нетривиальных задач, получила начальное развитие в связи с созданием ЭВМ в 1950-х — 1960-х годах.

Можно выделить две разновидности имитации:

Метод Монте-Карло (метод статистических испытаний);

Метод имитационного моделирования (статистическое моделирование).

Виды имитационного моделирования

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

Дискретно-событийное моделирование — подход к моделированию, предлагающий абстрагироваться от непрерывной природы событий и рассматривать только основные события моделируемой системы, такие как: «ожидание», «обработка заказа», «движение с грузом», «разгрузка» и другие. Дискретно-событийное моделирование наиболее развито и имеет огромную сферу приложений — от логистики и систем массового обслуживания до транспортных и производственных систем. Этот вид моделирования наиболее подходит для моделирования производственных процессов. Основан Джеффри Гордоном в 1960-х годах.

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

Области применения

Бизнес-процессы

Боевые действия

Динамика населения

Дорожное движение

ИТ-инфраструктура

Математическое моделирование исторических процессов

Логистика

Пешеходная динамика

Производство

Рынок и конкуренция

Сервисные центры

Цепочки поставок

Уличное движение

Управление проектами

Экономика здравоохранения

Экосистема

Информационная безопасность

Cистемы имитационного моделирования

MATLAB

AutoMOD

AnyLogic

Aimsun (моделирование транспортных потоков)

Arena (моделирование транспортных потоков)

PTV Vision VISSIM (моделирование транспортных потоков и организации дорожного движения) eM-Plant

Powersim

GPSS

simuLab

Simplex3

Simul8

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

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

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

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

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

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

Этапы имитационного моделирования

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

1.     Выбрать основные объекты и величины, описывающие исследуемый процесс. Определить выходные показатели. Построить модель системы.

2.     Задать исходные ключевые  данные и определить выходные показатели, описывающие модель системы. Установить взаимосвязи между исходными и выходными показателями в виде математического уравнения или неравенства.

3.     Задать законы распределения вероятностей для ключевых параметров модели.

4.     Провести компьютерную имитацию значений ключевых параметров модели. Провести генерацию случайных значений.

5.     Рассчитать основные характеристики вероятностных распределений исходных и выходных показателей.

6.     Провести анализ полученных результатов и принять решение.

Рассмотрим наиболее важные отличия аналитической модели от имитационной:

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

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

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

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

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

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

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

Однако ИМ присущи и недостатки:

-     большой расход машинного времени;

-     малая точность вероятностных характеристик редких событий;

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

-     сложность оптимизации системы (многовариантность расчётов при наличии вероятностных помех);

-     вероятностная оценка погрешности.

Таким образом применение ИМ становится целесообразным:

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

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

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

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

Основные функции ИМ

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

ИМ контролируемого объекта или процесса обеспечивается двумя видами деятельности, выполняемыми с помощью компьютера:

-           работа по созданию или модификации ИМ;

-           эксплуатация ИМ и интерпретация результатов.

-           ИМ систем применяется в двух случаях:

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

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

Типовые задачи, решаемые средствами компьютерного моделирования

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

-     управление процессом реализации инвестиционного проекта на различных этапах его жизненного цикла с учётом возможных рисков и тактики выделения денежных средств;

-     анализ процессов в работе сети кредитных организаций с учётом процессов взаимозачётов в условиях Российской Банковской Системы;

-     прогнозирование финансовых результатов деятельности предприятия на конкретный период времени с учётом анализа динамики сальдо на счетах;

-     бизнес-реинженеринг несостоятельного предприятия (изменяя его структуры ресурсов, прогноз финансовых результатов, выбор того или иного варианта реконструкции);

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

-     оценка параметров надёжности и задержек в централизованной экономической информационной системе с возможностью коллективного доступа;

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

-     моделирование действий курьерской группы в регионе пострадавшем в результате природной катастрофы или промышленной аварии;

-     анализ сетевой модели для проектов замены и наладки производственного оборудования с учётом возникновения неисправностей;

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

-     расчёт параметров надёжности и издержек обработки информации в банковской информационной системе.

Имитационное моделирование

Лекция№5. Игра «Жизнь»

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

Для построения алгоритма игры рассмотрим квадратное поле из n+1 столбцов и строк с обычной нумерацией от 0 до n. Крайние граничные столбцы и строки для удобства определим как «мертвую зону», они играют лишь вспомогательную роль.

Для любой внутренней клетки поля с координатами (i,j) можно определить 8 соседей. Примем, что если клетка живая, то ее закрашиваем, если клетка мертвая, то она пустая.

Зададим правила игры.

Если клетка (i,j) живая и в окружении более трех живых клеток, то она погибает (от перенаселения). Живая клетка также погибает, если в окружении менее двух живых клеток (от одиночества). Мертвая клетка оживает, если вокруг нее имеется три живые клетки.

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

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

Примеры структур порождаемых клеточным автоматом «Жизнь»

Фигура «планер» (glider) В 2003 году была предложена в качестве эмблемы хакеров.За 4 хода транслируется на 1 клетку по диагонали вниз.

Лекция №6. Использование регрессионного и корреляционного анализа для моделирования систем

Понятие корреляционного и регрессионного анализа

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

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

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

Пример функциональной зависимости выпуск продукции и ее потребление в условиях дефицита.

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

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

Характер связи между показателями определяется по корреляционному полю. Если y зависимый признак, а x независимый, то, отметив каждый случай x ( i) с координатами x _i и y _i , получим корреляционное поле. По расположению точек можно судить о характере связи (рис.).

Рисунок – Примеры корреляционных полей:

а переменные x и y не коррелируют; б наблюдается сильная положительная корреляция; в наблюдается слабая отрицательная корреляция

Теснота связи определяется с помощью коэффициента корреляции, который рассчитывается специальным образом и лежит в интервалах от минус единицы до плюс единицы. Если значение коэффициента корреляции лежит в интервале от 1 до 0,9 по модулю, то отмечается очень сильная корреляционная зависимость. В случае, если значение коэффициента корреляции лежит в интервале от 0,9 до 0,6, то говорят, что имеет место слабая корреляционная зависимость. Наконец, если значение коэффициента корреляции находится в интервале от - 0,6 до 0,6, то говорят об очень слабой корреляционной зависимости или полном ее отсутствии.

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

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

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

По числу факторов различают одно-, двух- и многофакторные уравнения регрессии.

По характеру связи однофакторные уравнения регрессии подразделяются:

а) на линейные:

,

где x экзогенная (независимая) переменная, y эндогенная (зависимая, результативная) переменная, a , b параметры;

б) степенные:                                    ,

в) показательные:                             ,

г) прочие.

Определение параметров линейного однофакторного уравнения регрессии

Пусть у нас имеются данные о доходах ( x ) и спросе на некоторый товар ( y) за ряд лет ( n):

Год i	Доход x	Спрос y
1	x 1	y 1
2	x 2	y 2
3	x 3	y 3
...	...	...
n	x n	y n

Предположим, что между x и y существует линейная взаимосвязь, т.е. .

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

Пусть

x ₁ , x ₂ , ..., x _n  совокупность значений независимого, факторного признака;

y ₁ , y ₂ , ..., y _n  совокупность соответствующих значений зависимого, результативного признака;

n  количество наблюдений.

Для нахождения уравнения регрессии вычисляются следующие величины:

1. Средние значения

 для экзогенной переменной;

 для эндогенной переменной.

2. Отклонения от средних величин

, .

3. Величины дисперсии и среднего квадратичного отклонения

, ;

, .

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

4. Вычисление корреляционного момента (коэффициента ковариации):

.

Корреляционный момент отражает характер взаимосвязи между x и y . Если K _x,y >0, то взаимосвязь прямая. Если K _x,y <0, то взаимосвязь обратная.

5. Коэффициент корреляции вычисляется по формуле

.

Доказано, что коэффициент корреляции находится в интервале от минус единицы до плюс единицы (- 1>=R_x,y <=1). Коэффициент корреляции в квадрате () называется коэффициентом детерминации.

Если R _x,y >|0,8|, то вычисления продолжаются.

6. Вычисления параметров регрессионного уравнения.

Коэффициент b находится по формуле

.

После чего можно легко найти параметр a:

.

Коэффициенты a и b находятся методом наименьших квадратов, основная идея которого состоит в том, что за меру суммарной погрешности принимается сумма квадратов разностей (остатков) между фактическими значениями результативного признака и его расчетными значениями, полученными при помощи уравнения регрессии

Построение уравнения степенной регрессии

Уравнение степенной агрессии имеет вид:

где a , b параметры, которые определяются по данным таблицы наблюдений.

Таблица наблюдений составлена и имеет вид

x	x 1	x 2	...	x n
y	y 1	y 2	...	y n

Прологарифмируем исходное уравнение и в результате получим

Обозначим ln  y через y' , ln  a как a' , а ln  x как x' .

В результате подстановки получим         

Данное уравнение есть не что иное, как уравнение линейной регрессии, параметры которого мы умеем находить.

Для этого прологарифмируем исходные данные:

ln x	ln x 1	ln x 2	...	ln x n
ln y	ln y 1	ln y 2	...	ln y n

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

Лекция№7. Геометрические и графические компьютерные модели

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

Сам термин «компьютерная графическая модель» говорит о том, что отражение свойств объекта-оригинала осуществляется средствами компьютерной графики, т.е. в наименовании модели отражен способ ее построения и реализации. Подобные модели, как наиболее наглядные, широко используются в практике моделирования.

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

·        геометрия Евклида и построения с помощью циркуля и линейки;

·        аналитическая геометрия, применение алгебраических методов в геометрии;

·        начертательная и проективная геометрия;

·        вычислительная геометрия (1940-1970) —разработка теории и прикладных методов геометрического моделирования на основе сплайн-функций и методов сплайн-аппроксимации трехмерных поверхностей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Системы поверхностного моделирования представляют тело просто как совокупность поверхностей, соединенных друг с другом и ограничивающих «пустой» объем. Поэтому применение данного метода моделирования, несмотря на ряд его достоинств, ограничено сложностью в отображении внутренних полостей тела. (Впрочем, при проектировании, например, корпуса автомобиля или фюзеляжа самолета этого и не требуется.)

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

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

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

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

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

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

Компьютерное графическое изображение объекта является результатом использования его геометрической модели. Чтобы показать модель объекта, необходимо смоделировать поток падающих и отраженных от его поверхностей лучей света. Модель можно «осветить» с разных сторон светом различного цвета и интенсивности. Исходную информацию для построения изображения на экране компьютера предоставляет геометрическая модель объекта. При этом можно полу-

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

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

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

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

Числовые результаты моделирования могут быть отображены и в виде виртуального движения трехмерных твердотельных моделей объектов. Действительно, если твердотельная модель —это объект, то программным путем можно изменять ее свойства и отображать поведение объекта, изменение его состояния и параметров на экране компьютера в виде 2D- или 3D-анимации (рис.).

Инструментальные системы моделирования MVS, Stratum, SolidWorks и т. п. позволяют использовать подобную технологию. Аналогичные технологии использует и современный кинематограф для создания сцен каких-либо фантастических событий.

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

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

Лекция №8. Понятие статистического моделирования

Статистическое моделирование – численный метод решения математических задач, при котором искомые величины представляют вероятностными характеристиками какого-либо случайного явления, это явление моделируется, после чего нужные характеристики приближённо определяют путём статистической обработки «наблюдений» модели. Например, требуется рассчитать потоки тепла в нагреваемой тонкой металлической пластине, на краях которой поддерживается нулевая температура. Распределение тепла описывается тем же уравнением, что и расплывание пятна краски в слое жидкости. Поэтому моделируют плоское броуновское движение частиц «краски» по пластине, следя за их положениями в моменты t_k, k = 0, 1, 2,... Приближённо принимают, что за малый интервал t частица перемещается на шаг h равновероятно во всех направлениях. Каждый раз направление выбирается случайным образом, независимо от всего предыдущего. Соотношение между t и h определяется коэффициентом теплопроводности. Движение начинается в источнике тепла и кончается при первом достижении края (наблюдается налипание «краски» на край). Поток Q(C) тепла через участок С границы измеряется количеством налипшей краски. При общем количестве N частиц согласно закону больших чисел такая оценка даёт ошибку порядка .

Области применения статистического моделирования

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

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

·        численное интегрирование,

·        расчеты в системах массового обслуживания,

·        расчеты качества и надежности изделий,

·        расчеты прохождения нейтронов сквозь пластину,

·        передача сообщений при наличии помех,

·        задачи теории игр,

·        задачи динамики разреженного газа,

·        задачи дискретной оптимизации,

·        задачи финансовой математики (оценивание опционов и др.)

и многие другие.

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

Метод статистических испытаний (методы Монте-Карло). История метода

Говоря о статистическом моделировании, люди часто подразумевают, что речь идет о так называемом методе статистических испытаний (методах Монте-Карло).

Метод статистических испытаний – метод вычислительной и прикладной математики, основанный на моделировании случайных величин и построении статистических оценок для искомых величин; то же, что Монте-Карло методы. Принято считать, что метод статистических испытаний возник в 1944 году, когда в связи с работами по созданию атомных реакторов американские учёные Дж. фон Нейман и С. Улам начали широко применять аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. Первоначально метод использовался главным образом для решения сложных задач теории переноса излучения и нейтронной физики, где традиционные численные методы оказались мало пригодными. Затем его влияние распространилось на больший класс задач статистической физики, очень разных по своему содержанию. Метод применяется для решения задач теории игр, теории массового обслуживания и математической экономики, задач теории передачи сообщений при наличии помех и т.д.

Итак, таинственное название «Методы Монте-Карло». Откуда оно взялось и что стоит за этим звучным наименованием? Попробуем разобраться, для чего обратимся к истории.

Некоторые эксперименты по использованию метода статистических испытаний проводились достаточно давно. Так, еще французский естествоиспытатель Бюффон выполнял эксперименты по вычислению числа p путем подбрасывания иглы и вычисления частоты пересечения иглы одной из параллельных прямых. В 1930 году Э. Ферми использовал то, что сейчас носит название методов Монте-Карло, в исследовании нейтронных потоков. Позже, он разработал «Fermiac», механическое устройство, которое использовалось в вычислениях в задачах ядерной физики. Настоящее распространение идей, связанных с подобными методами, стало реальностью с началом эры вычислительной техники, которая позволила проводить компьютерные эксперименты, в том числе и по получению случайных чисел.

Пионерами методов Монте-Карло принято считать американских математиков Стэнли Улама, Джона фон Неймана и Николаса Метрополиса. В сороковых годах XX века Джон фон Нейман заложил основу методов Монте-Карло, создав математический базис для функций плотности вероятности, интегральных функций обратного распределения и генераторов псевдослучайных чисел. Исследования выполнялись в тесном сотрудничестве со Стэнли Уламом, считается, что именно он первым осознал и продвинул в массы идею о необходимости компьютера для выполнения вычислений по методам Монте-Карло.

Происхождение названия методов связано с одноименным городом в княжестве Монако, в котором расположены одни из самых известных казино в мире. Дело в том, что случайные числа и их генерация составляют «сердце» методов Монте-Карло. Рулетка казино – один из наиболее простых приборов для генерации случайных чисел. Именно это и явилось наводящим соображением для названия. Как писал Стэнли Улам в автобиографии «Приключения математика», метод был назван в честь его дяди, который был заядлым игроком, по совету Метрополиса.

Датой рождения методов Монте-Карло принято считать 1949 год, когда появилась статья Улама и Метрополиса «Метод Монте-Карло». Как это часто бывало в истории науки, основным побуждающим фактором в развитии статистического моделирования стали военные исследования по заказу Министерства обороны США. Далее эти исследования не стали носить секретного характера, и результаты были успешно внедрены в разных областях, благодаря общности схемы метода и отсутствию привязки к конкретному объекту или предметной области.

Еще один интересный факт связан с тем, что некие случайные методы вычислений и проведения экспериментов разрабатывались и применялись и в «доисторическую компьютерную эру». Основная разница методов Монте-Карло с ранними исследованиями в области статистического моделирования заключается в следующем: Монте-Карло моделирование перевернуло стандартные представления о том, как нужно решать задачу, используя средства теории вероятности и математической статистики. Так, ранее предполагалось, что необходимо изучить детерминированную проблему, а потом использовать имитацию, чтобы проверить сделанные ранее выкладки. В Монте-Карло моделировании предполагается, что надо взять детерминированную проблему и найти ее стохастический аналог. Эта идея стала общим принципом, применимым для решения задач различной  природы, благодаря фон Нейману, Метрополису и Уламу.

Методы Монте-Карло. Анализ общей схемы, достоинства и недостатки

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

Принципиальная математическая основа использования методов Монте-Карло – Усиленный закон больших чисел в форме А.Н. Колмогорова.

Теорема Колмогорова.

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

Итак, первое несомненное достоинство методов Монте-Карло – простая схема вычислительного алгоритма.

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

Следующая важная составляющая – моделирование случайных величин с заданными распределениями. Как правило, такое моделирование осуществляется путём преобразования одного или нескольких независимых значений случайного числа a, распределённого равномерно в интервале (0,1). Последовательности «выборочных» значений a обычно получают на ЭВМ с помощью теоретико-числовых алгоритмов, среди которых наибольшее распространение получил «метод вычетов». Такие числа называются «псевдослучайными», они проверяются статистическими тестами и решением типовых задач. Итак, существенную роль играет качество используемых генераторов случайных чисел. Написание корректных генераторов – сложная задача, успешно решаемая в рамках разных научных и инженерных математических библиотек, например, в одной из лучших из них - Intel® Math Kernel Library (Intel® MKL), которой мы будем неоднократно пользоваться в рамках нашего курса.

Продолжая разговор о точности вычислений, посмотрим на этот вопрос немного с другой стороны. Как известно, ошибка вычислений по методу Монте-Карло обычно пропорциональна , где d – некоторая константа, а N – количество испытаний. Из формулы очевидно, что для повышения точности в 10 раз необходимо увеличить количество испытаний в 100 раз, а это значит, что метод Монте-Карло требует больших вычислительных ресурсов.

Примеры применения методов Монте-Карло

В данном разделе мы рассмотрим некоторые примеры применения методов Монте-Карло в практических задачах. Как Вы увидите, речь пойдет об известных математических задачах – вычислении площади фигуры и определении числа p. Выбор данных задач вовсе не означает, что именно в них методы Монте-Карло ведут себя особенно эффективно, напротив, в этих задачах, как правило, применяются другие способы достижения результата. Дело в том, что в ходе изучения курса мы неоднократно будем встречаться с примерами применения методов Монте-Карло в реальных экономических, физических, математических задачах. Каждая из таких задач требует некоторой подготовки, как с точки зрения изучения метода статистических испытаний, так и подробного рассмотрения собственно постановки задачи. Поэтому в этом разделе мы и рассматриваем иллюстративные, сравнительно несложные примеры. Итак, для начала совсем простой пример.

Задача вычисления площади фигуры на плоскости

Пусть дана некоторая плоская фигура F, для которой требуется найти площадь.

Введем следующие предположения:

1.     Для определенности предположим, что эта фигура целиком расположена внутри единичного квадрата.

2.     С учетом предположения 1 периметр фигуры может быть устроен совершенно произвольно.

3.     Фигура может не быть связной, т.е. может состоять из нескольких областей.

4.     Фигура может быть задана аналитически или графически.

Рис. 1.1      Площадь фигуры на плоскости. Метод Монте-Карло

Сгенерируем в квадрате N случайных точек (рис. 1.1). Пусть N* – количество точек, попавших внутрь рассматриваемой фигуры.

Тогда при достаточно больших значениях N площадь фигуры F может быть оценена как

        (1.3)

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

Задача оценивания числа p

Из школьного прошлого всем известно, что число p есть отношения длины окружности к ее диаметру. С древних времен внимание человечества было приковано к вычислению этого замечательного числа. Первоначально, заметив, что искомое отношение постоянно и не зависит от окружности, люди пытались представить его рациональной дробью. Такие попытки предпринимались в Древнем Египте, Индии, Древней Греции. Постепенно ученые осознали бесплодность попыток найти рациональную дробь, представляющую число p, и дело сдвинулось с мертвой точки. Так Архимед, в III в до н.э. создал некоторый алгоритм приближенного вычисления p и определил, что p = 3.1419.... Далее более точные решения были найдены в Древнем Китае, в Самарканде. В Европе результатами в данной области отметились Виет, Джонсон, Эйлер, ван Цейлен, Лежандр (доказал иррациональность числа), Лейбниц, Малчин.

Известен одновременно забавный и грустный факт, состоящий в том, что после более чем 20 лет работы в конце XIX века англичанин В. Шенкс нашел 707 знаков числа, но в 1945 году при помощи компьютера определили, что он ошибся в 520-м знаке и дальнейшие вычисления оказались неверными.

В эру современных компьютеров не составляет проблемы вычислить число p с необходимой точностью (так, в 2002 году было вычислено 1 241 100 000 000 знаков числа). Все эти вычисления обычно проводятся при помощи суммирования некоторых рядов.

Мы в данном разделе рассмотрим подход к нахождению числа p методом статистического моделирования.

Метод Hit-Or-Miss

Еще один метод оценивания числа p называется Hit-Or-Miss («попал – не попал»). Метод состоит в следующем: рассмотрим единичный квадрат на координатной плоскости и четверть окружности единичного радиуса с центром в начале координат (рис.).

Рис.   Метод Hit-Or-Miss

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

Площадь квадрата S_max = 1, площадь выделенной области .

Рассмотрим случайную величину .

Введем частота наступления события A.

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

Будем рассматривать  – частоту наступления события A – в качестве оценки величины p – вероятности того, что точка попала в указанный сектор окружности. Зная теоретическую вероятность этого события , мы можем оценить эту вероятность по достаточно большой выборке () и рассмотреть следующее равенство:

        (1.10)

Тогда можно рассмотреть

     (1.11)

, таким образом (1.11) дает несмещенную оценку.

Случайность и имитация случайности

Всякий, кто питает слабость

к арифметическим методам

получения случайных чисел,

грешен вне всяких сомнений.

Джон фон Нейман

В данном разделе мы кратко коснемся инструментального аппарата методов Монте-Карло – случайных чисел и способов их получения.

Случайность и непредсказуемость

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

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

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

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

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

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

Случайные числа и генераторы случайных чисел

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

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

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

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

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

Генераторы псевдослучайных чисел (PRNG)

Генератор псевдослучайных чисел (ГПСЧ, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел.

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

Первый алгоритм для получения псевдослучайных чисел был предложен Джоном фон Нейманом. Он называется методом середины квадратов. Поясним его на примере. Пусть задано 4-значное целое число n₁ = 9876. Возведем его в квадрат. Получим, вообще говоря, 8-значное число 97 535 376. Выберем четыре средние цифры из этого числа и обозначим n₂ = 5353. Затем возведем его в квадрат (28 654 609) и снова извлечем 4 средние цифры. Получим n₃ = 6546. Далее, 42 850116, n₄ = 8501 и т. д. В качестве значений случайной величины предлагалось использовать значения 0,9876; 0,5353; 0,6546; 0,8501; 0,2670; 0,1289 и т. д.

Но этот алгоритм не оправдал себя: получалось больше чем нужно малых значений. Поэтому разными исследователями были разработаны другие алгоритмы. Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, linear feedback shift registers, generalized feedback shift registers.

Из современных ГПСЧ широкое распространение получил Mersenne twister, предложенный в 1997 году Мацумото и Нишимурой. Его достоинствами являются колоссальный период (2¹⁹⁹³⁷-1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение от силы в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют сложные алгоритмы, распознающие последовательность, порождаемую с помощью Mersenne twister, как неслучайную. Это в частности делает Mersenne twister неподходящим для криптографии.

Достоинства метода псевдослучайных чисел довольно очевидны.

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

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

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

Один из главных недостатков метода – ограниченность «запаса» псевдослучайных чисел (наличие периода, ГПСЧ рано или поздно зацикливается). Однако существуют генераторы с очень большим периодом. Подавляющее большинство расчетов по методам Монте-Карло в настоящее время осуществляется с использованием псевдослучайных чисел.

Экологические модели

Лекция №9. Динамика численности популяций хищника и жертвы

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

Модель состоит из двух компонентов: y - численность популяции хищника и x - численность популяции жертвы.

Предполагается, что в отсутствие хищника популяция жертвы растет экспоненциально. Чем больше численность той и другой популяции, тем чаще происходят встречи. Число встреченных и съеденных жертв будет зависеть от эффективности, с которой хищник находит и ловит жертву. Если обозначить через b «эффективность поиска», то скорость поедания жертвы будет равна bxy, и окончательно для численности жертвы получаем

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

(c - смертность). Скорость рождения новых особей в данной модели полагается зависящей от двух обстоятельств: скорости потребления пищи и эффективности, с которой эта пища переходит в потомство хищника. Итак, для численности хищника окончательно получаем

Так как процессы надо рассматривать вместе, объединим уравнения в систему:

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

Рис. Динамика численности популяции хищника и жертвы при a = 5, b = 0,1, c = 2, d = 0,06, x₀ = 150, y₀ = 50. Сплошная линия - численность жертвы, штриховая - хищника

Лекция №10 .Моделирование систем массового обслуживания

Общие понятия систем массового обслуживания

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

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

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

Примерами систем массового обслуживания могут служить:

- посты технического обслуживания автомобилей;

- посты ремонта автомобилей;

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

- станции технического обслуживания автомобилей;

- аудиторские фирмы;

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

- телефонные станции и т. д.

Основными компонентами системы массового обслуживания лю­бого вида являются:

•   входной поток поступающих требований или заявок на обслужи­вание;

•   дисциплина очереди;

•   механизм обслуживания.

Входной поток требований. Для описания входного потока тре­буется задать вероятностный закон, определяющий последователь­ность моментов поступления требований на обслуживание и ука­зать количество таких требований в каждом очередном поступле­нии. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (требования поступают группами в систему). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслужи­ванием.

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

- первым пришел — первый обслуживаешься;

- пришел последним — обслуживаешься первым;

- случайный отбор заявок;

- отбор заявок по критерию приоритетности;

-          ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания
обслуживания, что ассоциируется с понятием «допустимая дли­на очереди»).

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

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

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

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

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

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

- вероятностным распределением времени продолжительности об­служивания;

- конфигурацией обслуживающей системы (параллельное, после­довательное или параллельно-последовательное обслуживание);

- количеством и производительностью обслуживающих каналов;

- дисциплиной очереди;

- мощностью источника требований.

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

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

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

- относительная и абсолютная пропускная способность системы;

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

- среднее время ожидания в очереди;

- средняя длина очереди;

- средний доход от функционирования системы в единицу времени и т.п.

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

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

Независимо от характера процесса, протекающего в системе мас­сового обслуживания, различают два основных вида СМО:

- системы с отказами, в которых заявка, поступившая в систему в
момент, когда все каналы заняты, получает отказ и сразу же по­кидает очередь;

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

Системы массового обслуживания с ожиданием делятся на си­стемы с ограниченным ожиданием и системы с неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться:

- длина очереди;

- время пребывания в очереди.

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

Все системы массового обслуживания различают по числу каналов обслуживания:

- одноканальные системы;

- многоканальные системы.

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

Одноканальная модель с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания

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

            (1)

где λ. — интенсивность поступления заявок в систему.

Плотность распределения длительностей обслуживания:

                                                   (2)

где μ - интенсивность обслуживания.

Потоки заявок и обслуживании простейшие.

Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы.

Представим данную систему массового обслуживания в виде графа (рис. 4.1), у которого имеются два состояния:

S₀ — канал свободен (ожидание);

S₁— канал  занят (идет обслуживание заявки).

Рисунок 4.1 – Граф состояний одноканальной СМО с отказами

Обозначим вероятности состояний:

P₀(t) — вероятность состояния «канал свободен»;

P₁(t) — вероятность состояния «канал занят».

По размеченному графу состояний (рис. 1) составим систему дифференциальных уравнений Колмогорова для вероятностей стояний:

                           (3)

Система линейных дифференциальных уравнений имеет решение с учетом нормировочного условия P₀(t) + P₁(t) = 1. Реше­ние данной системы называется неустановившимся, поскольку оно непосредственно зависит от t и выглядит следующим образом:

                         (4)         (5)

Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P₀(t) есть не что иное, как относительная пропускная способность системы q.

Действительно, P₀ — вероятность того, что в момент t канал сво­боден и заявка, пришедшая к моменту t, будет обслужена, а следо­вательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно P₀(t), т. е.

                                                (6)

По истечении большого интервала времени (при t → ∞) дости­гается стационарный (установившийся) режим:

          (7)

Зная относительную пропускную способность, легко найти аб­солютную. Абсолютная пропускная способность (А) — среднее чис­ло заявок, которое может обслужить система массового обслужива­ния в единицу времени:

                                               (8)

Вероятность отказа в обслуживании заявки будет равна вероят­ности состояния «канал занят»:

                  (9)

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

Пример 1. Пусть одноканальная СМО с отказами представля­ет собой один пост ежедневного обслуживания (ЕО) для мойки ав­томобилей. Заявка — автомобиль, прибывший в момент, когда пост занят, — получает отказ в обслуживании. Интенсивность потока ав­томобилей λ = 1,0 (автомобиль в час). Средняя продолжительность обслуживания — 1,8 часа. Поток автомобилей и поток обслужива­нии являются простейшими.

Требуется определить в установившемся режиме предельные значения:

- относительной пропускной способности q;

- абсолютной пропускной способности А;

- вероятности отказа Pотк;

Сравните фактическую пропускную способность СМО с номи­нальной, которая была бы, если бы каждый автомобиль обслужи­вался точно 1,8 часа и автомобили следовали один за другим без перерыва.

Решение

1. Определим интенсивность потока обслуживания:

2. Вычислим относительную пропускную способность:

Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост ЕО авто­мобилей.

3. Абсолютную пропускную способность определим по формуле:

Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час. 3. Вероятность отказа:

Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.

4. Определим номинальную пропускную способность системы:

(автомобилей в час).

Оказывается, что А_ном в 1,5 раза больше, чем фактическая пропускная способность, вычисленная с учетом случай­ного характера потока заявок и времени обслуживания.

Одноканальная  СМО с ожиданием

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание — простейший поток с интенсивно­стью λ,. Интенсивность потока обслуживания равна μ, (т. е. в сред­нем непрерывно занятый канал будет выдавать μ обслуженных за­явок). Длительность обслуживания — случайная величина, подчи­ненная показательному закону распределения. Поток обслужива­нии является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

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

Граф состояний СМО в этом случае имеет вид, показанный на рис. 2

Рисунок 5.2 –  Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)

Состояния СМО имеют следующую интерпретацию:

S0 — «канал свободен»;

S1 — «канал занят» (очереди нет);

S2 — «канал занят» (одна заявка стоит в очереди);

Sn — «канал занят» (п — 1  заявок стоит в очереди);

SN — «канал занят» (N — 1 заявок стоит в очереди).

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

                                           (10)

п — номер состояния.

Решение приведенной выше системы уравнений (10) для на­шей модели СМО имеет вид

                              (11)

                                                                     (12)

Тогда

Следует отметить, что выполнение условия стационарности

 для данной СМО не обязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превы­шать N — 1), а не соотношением между интенсивностями входного потока, т. е. не отношением λ/μ=ρ

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N — 1):

вероятность отказа в обслуживании заявки:

                                                (13)

относительная пропускная способность системы:

                                            (14)

абсолютная пропускная способность:

                                                         (15)

среднее число находящихся в системе заявок:

                            (16)

среднее время пребывания заявки в системе:

                                                              (17)

средняя продолжительность пребывания  клиента (заявки) в очереди:

                                                               (18)

среднее число заявок (клиентов) в очереди (длина очереди):

                                                             (19)

Рассмотрим пример одноканальной СМО с ожиданием.

Пример 2. Специализированный пост диагностики представ­ляет собой одноканальную СМО. Число стоянок для автомоби­лей, ожидающих проведения диагностики, ограниченно и равно 3[(N — 1) = 3]. Если все стоянки заняты, т. е. в очереди уже нахо­дится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток ав­томобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность λ = 0,85 (автомобиля в час). Вре­мя диагностики автомобиля распределено по показательному зако­ну и в среднем равно 1,05 час.

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

Решение

1. Параметр потока обслуживаний автомобилей:

2. Приведенная интенсивность потока автомобилей определя­ется как отношение интенсивностей λ, и μ, т. е.

3. Вычислим финальные вероятности системы

4. Вероятность отказа в обслуживании автомобиля:

5. Относительная пропускная способность поста диагностики:

6. Абсолютная пропускная способность поста диагностики

(автомобиля в час).

7. Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

8. Среднее время пребывания автомобиля в системе:

9. Средняя продолжительность пребывания заявки в очереди на обслуживание:

10. Среднее число заявок в очереди (длина очереди):

Работу рассмотренного поста диагностики можно считать удов­летворительной, так как пост диагностики не обслуживает автомо­били в среднем в 15,8% случаев (Р_отк = 0,158).

Лекция №11. Оптимизация и оптимизационные модели

Основные понятия

Оптимизация - поиск наилучшего решения с учетом ограничений.

Для оптимизации ищется целевая функция. Эта функция конструируется искусственно на основе уравнений, описывающих объект оптимизации. Целевая функция обычно имеет много аргументов: φ=f (х1, х2, ..., х n).

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

Поэтому разработаны десятки методов оптимизации:

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

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

Антиградиент - вектор, указывающий на направление максимального убывания функции. Чтобы повернуть вектор на 180╟, достаточно изменить все знаки у градиентов на противоположные (т.е. х (-1)).

Для иллюстрации поиска экстремума в процессе оптимизации функций двух переменных используют линии равного уровня (ЛРУ). Если задаться постоянным значением φ и так подбирать значения хi чтобы значение φ было равным заданному значению, то геометрическое место точек φ составит линию равного уровня.

В зависимости от целевой функции линий равного уровня могут характеризоваться следующими географическими понятиями:

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

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

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

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

МСС - простейший метод оптимизации, пригодный для сложных систем. Работа метода хорошо иллюстрируется с помощью линий равного уровня (ЛРУ).

Порядок поиска оптимума:

- выбирается исходная точка в виде значений параметров целевой функции:

φ=f (х1, х2, ..., х n).

- ищется градиент;

- движемся в направлении антиградиента с заданным шагом;

- на каждом шаге проверяем выполнение условия движения, оно такое: φi < φi-1 ( текущее значение φ должно быть меньше предыдущего).

- если условие движения нарушается, то процесс останавливается, иначе, движение продолжается;

- при нарушении условий движения уточняется одномерный минимум и ищется новый градиент;

- условие останова:

а) значение φ меньше заданного;

б) разность значений соседних φ меньше заданной;

в) количество шагов превышает допустимое.

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

Конструирования целевой функции

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

х² + у² = 1

х + у = 1

Графически эту систему можно представить как окружность и секущая прямая

Задача: найти минимальное расстояние между точками прямой и окружности.

В данном случае два минимума. Последовательность конструкция целая функции:

1. приводим систему уравнений к нулевому виду:

х² + у² - 1 = 0

х + у -1 = 0

2. складываем два уравнения:

1 ур. + 2 ур. = 0

3. для усиления чувствительности к изменению аргументов обе части уравнения можно возвести в квадрат:

(1 ур.)² + (2 ур.)² = 0

4. Целевую функцию представим в виде:

φ = (х² + у² - 1)² + (х + у - 1)²;

Численный поиск минимума

Составляется компьютерная программа, в которой значение х и у изменяется с заданным шагом в диапазоне +- 2. На каждом шаге вычисляется значение φ, с помощью плоттера рисуется картина ЛРУ.

Таким способом были построены ЛРУ еще для двух следующих целевых функций:

φ = 100(x²-y)²+(1-x)²

φ = (x-y)²+((x+y-10)/3)²

Многомерный и одномерный поиск оптимума 

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

Одномерный поиск

Для многомерного поиска разработаны десятки методов, для одного поиска около 1 десятка методов. Рассмотрим одномерное приближение.

Метод последовательных приближений

P - длина шага оптимизации;

φ - значение целевой функции

1. при нарушении условий движения (φi+1 > φi) движение останавливается

2. Возвращается на 1 шаг назад.

3. Делим длину шага на R где R = 3-10

4. Возобновляем движение с новым шагом.

5. При нарушении условий движения все повторяется, и т.д.

Условия останова:

- Значение j < заданного

- Разность между соседними значениями j < заданной

- Длина шага < заданной

- Кол-во шагов превышает заданное.

Любое из этих условий приводит к останову.

Метод золотого сечения

Если возьмем пропорцию:

x₁/x = x₂/x₁ = 0.618-m_o

Такое соотношение называется золотой пропорцией.

1. При нарушении условий движения последний шаг делим в отношении золотой пропорции слева на право.

2. Этот же отрезок делим в золотой пропорции справа на лево. В результате получим 2 новые точки

3. Сравниваем значения j в новых точках.

4. Выбираем отрезок, которому соответствует меньшее из этих двух j.

5. Полученный отрезок делим в отношении золотой пропорции слева направо, и т.д.

Условия останова те же, что и в предыдущем случае.

Метод параболической аппроксимации (МПА)

При нарушении условий значения j в последних 3-х точках подставляется в формулу решения системы 3-х уравнений для параболы. Это решение позволяет находить координаты минимума параболы, проходящий через 3 последние точки.

Сравнение методов одномерного поиска

МПП более прост (движемся, делим), но требует много шагов (м.б. 10 и 100 шагов).

МЗС позволяет найти min за 3-4 шага.

МПА более сложен, но позволяет найти min за 1 шаг. Но МПА обладает методической погрешностью, поскольку парабола отличается от истинной кривой; обычно эта погрешность невелика. В пакетах программ для расчета оптики обычно используется в качестве метода многомерного поиска демнорированый МСС, а в качестве метода одномерного поиска - МПА.

Оптимизационные модели

Понятие оптимизационных задач и оптимизационных моделей

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

Оптимизационные задачи (ОЗ) решаются с помощью оптимизационных моделей (ОМ) методами математического программирования.

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

o управляемых переменных;

o неуправляемых переменных;

o формы функции (вида зависимости между ними).

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

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

а) на линейные ( I и II  ) и нелинейные ( III и IV  ) (рис. 3.1);

б) детерминированные ( А , В  ) и стохастические (группы кривых С _i ) (рис. 3.2).

Рисунок 3.1– Линейные и нелинейные ограничения

Рисунок 3.2– Детерминированные и стохастические ограничения

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

ОЗ решаются методами математического программирования, которые подразделяются:

o на линейное программирование;

o нелинейное программирование;

o динамическое программирование;

o целочисленное программирование;

o выпуклое программирование;

o исследование операций;

o геометрическое программирование и др.

Главная задача математического программирования  это нахождение экстремума функций при ограничениях в форме уравнений и неравенств.

Рассмотрим ОЗ, решаемые методами линейного программирования.

Оптимизационные задачи с линейной зависимостью между переменными

Пусть:

b _i   количество ресурса вида i ( i  = 1, 2, ..., m );

a _{i ,  j}   норма расхода i -того ресурса на единицу j -того вида продукции;

x _j   количество продукции вида j ( j  = 1, 2, ..., n );

c _j   прибыль (доход) от единицы этой продукции (в задачах на минимум  себестоимость продукции).

Тогда ОЗ линейного программирования (ЛП) в общем виде может быть сформулирована и записана следующим образом:

Найти переменные x _j ( j =  1, 2, ...,  n ), при которых целевая функция

была бы максимальной (минимальной), не нарушая следующих ограничений:

Все три случая можно привести к так называемой канонической форме, введя дополнительные переменные

где k   количество дополнительных переменных, и условие неотрицательности искомых переменных: x _j  ³ 0.

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

---

Краткое описание документа:

Данный материал содержит 11 лекций по разделу "Компьютерное моделирование". Моделирование базируется на математической теории подобия, согласно которой абсолютное подобие может иметь место лишь при замене одного объекта другим, точно таким же. При моделировании большинства систем (за исключением, возможно, моделирования одних математических структур другими) абсолютное подобие невозможно, и основная цель моделирования – модель достаточно хорошо должна отображать функционирование моделируемой системы.