Конспект лекций case cals. Конспект_САСТ-2. Конспект лекций по дисциплине case и cals технологии по направлению подготовки
 Скачать 3.53 Mb.
|
|
Всегда следует помнить о потребителе информации, которую позволя- ет получить наша модель. Нельзя оправдать разработку имитационной мо- дели, если ее в конечном счете нельзя использовать или если она не прино- сит пользу лицу, принимающему решения. Приведем критерии, которым должна удовлетворять хорошая модель. Мо- дель должна быть: • простой и понятной пользователю, • целенаправленной, • надежной в смысле гарантии от абсурдных ответов, • удобной в управлении и обращении, т. е. общение с ней должно быть легким, • полной с точки зрения возможностей решения главных задач, • адаптивной, позволяющей легко переходить к другим модификациям или обновлять данные, • допускающей постепенные изменения в том смысле, что, будучи внача- ле простой, она может во взаимодействии с пользователем становиться все более сложной. 187 10.1.9 Процесс имитации Исходя из того, что имитация должна применяться для исследования ре- альных систем, можно выделить следующие этапы этого процесса (рис. 10.2): Формули- рование проблемы Определение границ системы Применять имитационное моделирова- ние? Трансляция модели Подготовка данных Формулирова- ние модели Оценка адекватности Эксперементи- рование Тактическое планирование Стратегическое планирование Интерпретация результатов Результирую- щий документ Нет Да Положительная Отрицательная Полезны Бесполезны Рис. 10.2 Этапы имитационного моделирования 1. Определение системы - установление границ, ограничений и измерите- лей эффективности системы, подлежащей изучению. 188 2. Формулирование модели — переход от реальной системы к некоторой логической схеме (абстрагирование). 3. Подготовка данных - отбор данных, необходимых для построения моде- ли, и представление их в соответствующей форме. 4. Трансляция модели - описание модели на языке, приемлемом для ис- пользуемой ЭВМ. 5. Оценка адекватности — повышение до приемлемого уровня степени уверенности, с которой можно судить относительно корректности выводов о ре- альной системе, полученных на основании обращения к модели. 6. Стратегическое планирование - планирование эксперимента, который должен дать необходимую информацию. 7. Тактическое планирование — определение способа проведения каждой серии испытаний, предусмотренных планом эксперимента. 8. Экспериментирование - процесс осуществления имитации с целью по- лучения желаемых данных и анализа чувствительности. 9. Интерпретация — построение выводов по данным, полученным путем имитации. 10. Реализация - практическое использование модели и (или) результатов моделирования. 11. Документирование - регистрация хода осуществления проекта и его ре- зультатов, а также документирование процесса создания и использования моде- ли. 10.1.10 Проверка модели Такого процесса, как «испытание» правильности модели, не существует. Вместо этого экспериментатор в ходе разработки должен провести серию прове- рок, с тем, чтобы укрепить свое доверие к модели. Для этого могут быть исполь- зованы проверки трех видов. Применяя первую из них, мы должны убедиться, что модель верна, так сказать, в первом приближении. Например, следует поста- 189 вить такой вопрос: не будет ли модель давать абсурдные ответы, если ее пара- метры будут принимать предельные значения? Мы должны также убедиться в том, что результаты, которые мы получаем, по-видимому, имеют смысл. По- следнее может быть выполнено для моделей существующих систем методом, предложенным Тьюрингом [31]. Он состоит в том, что людей, непосредственно связанных с работой реальной системы, просят сравнить результаты, получен- ные имитирующим устройством, с данными, получаемыми на выходе реальной системы. Для того чтобы такая проверка была несколько более строгой в науч- ном отношении, мы можем предложить экспертам указать на различия между несколькими выборками имитированных данных и аналогичными выборками, полученными в реальной системе. Второй метод оценки адекватности модели состоит в проверке исходных предположений, третий - в проверке преобразований информации от входа к вы- ходу. Последние два метода могут привести к необходимости использовать ста- тистические выборки для оценки средних значений и дисперсий, дисперсионный анализ, регрессионный анализ, факторный анализ, спектральный анализ, авто- корреляцию, метод проверки с помощью критерия «хи-квадрат» и непараметри- ческие проверки. Поскольку каждый из этих статистических методов основан на некоторых допущениях, то при использовании каждого из них возникают вопро- сы, связанные с оценкой адекватности. Некоторые статистические испытания требуют меньшего количества допущений, чем другие, но, в общем, эффектив- ность проверки убывает по мере того, как исходные ограничения ослабляются. Оценку имитационной модели можно производить тремя способами: 1) верификацией, используя которую экспериментатор хочет убедиться, что модель ведет себя так, как было задумано; 2) оценкой адекватности - проверкой соответствия между поведением мо- дели и поведением реальной системы; 3) проблемным анализом - формулированием статистически значимых вы- водов на основе данных, полученных путем машинного моделирования. 190 10.2 Методы построения имитационных моделей Имитационное моделирование основано на воспроизведении с помощью ЭВМ развернутого во времени процесса функционирования системы с учетом взаимодействия с внешней средой. Основой всякой имитационной модели (ИМ) является: разработка модели исследуемой системы на основе частных имитацион- ных моделей (модулей) подсистем, объединенных своими взаимодействиями в единое целое; выбор информативных (интегративных) характеристик объекта, способов их получения и анализа; построение модели воздействия внешней среды на систему в виде сово- купности имитационных моделей внешних воздействующих факторов; выбор способа исследования имитационной модели в соответствии с мето- дами планирования имитационных экспериментов (ИЭ). Условно имитационную модель можно представить в виде действующих, программно (или аппаратно) реализованных блоков. На рис. 10.3. показана структура имитационной модели. Блок имитации внешних воздействий (БИВВ) формирует реализации случайных или детерми- нированных процессов, имитирующих воздействия внешней среды на объект. Блок обработки результатов (БОР) предназначен для получения информативных характеристик исследуемого объекта. Необходимая для этого информация по- ступает из блока математической модели объекта (БМО). Блок управления (БУИМ) реализует способ исследования имитационной модели, основное его на- значение – автоматизация процесса проведения ИЭ. Рис. 10.3 - Структура имитационной модели 191 Целью имитационного моделирования является конструирование ИМ объ- екта и проведение ИЭ над ней для изучения закона функционирования и поведе- ния с учетом заданных ограничений и целевых функций в условиях иммитации и взаимодействия с внешней средой. К достоинствам метода имитационного моделирования могут быть отнесе- ны: проведение ИЭ над ММ системы, для которой натурный эксперимент не осуществим по этическим соображениям или эксперимент связан с опасностью для жизни, или он дорог, или из-за того, что эксперимент нельзя провести с прошлым; решение задач, аналитические методы для которых неприменимы, напри- мер, в случае непрерывно- дискретных факторов, случайных воздействий, нели- нейных характеристик элементов системы и т.п.; возможность анализа общесистемных ситуаций и принятия решения с по- мощью ЭВМ, в том числе для таких сложных систем, выбор критерия сравнения стратегий поведения которых на уровне проектирования не осуществим; сокращение сроков и поиск проектных решений, которые являются опти- мальными по некоторым критериям оценка эффективности; проведение анализа вариантов структуры больших систем, различных ал- горитмов управления изучения влияния изменений параметров системы на ее характеристики и т.д. Принципы построения имитационных моделей Процесс функционирования сложной системы можно рассматривать как смену ее состояний, описываемых ее фазовыми переменными Z 1 (t), Z 2 (t), … Z n (t) в n – мерном пространстве. Задачей имитационного моделирования является получение траектории движения рассматриваемой системы в n – мерном пространстве (Z 1 , Z 2 , … Z n ), а также вычисление некоторых показателей, зависящих от выходных сигналов 192 системы и характеризующих ее свойства. В данном случае “движение” системы понимается в общем смысле – как любое изменение, происходящее в ней. Известны два принципа построения модели процесса функционирования систем: 1) Принцип Δt. Рассмотрим этот принцип сначала для детерминированных систем. Предположим, что начальное состояние системы соответствует значени- ям Z 1 (t 0 ), Z 2 (t 0 ), … Z n (t 0 ). Принцип Δt предполагает преобразование модели сис- темы к такому виду, чтобы значения Z 1 , Z 2 , … Z n в момент времени t 1 = t 0 +Δt можно было вычислить через начальные значения, а в момент t 2 = t 1 +Δt через значения на предшествующем шаге и так для каждого i-ого шага (Δt=const, i=1,…,M). Для систем, где случайность является определяющим фактором, принцип Δt заключается в следующем: Определяется условное распределение вероятности на первом шаге (t 1 = t 0 +t) для случайного вектора, обозначим его ( 0 1 z , 0 2 z , … 0 n z ). Условие состо- ит в том, что начальное состояние системы соответствует точке траектории. Вычисляются значения координат точки траектории движения системы (t 1 = t 0 +t), как значения координат случайного вектора, заданного распределени- ем, найденным на предыдущем шаге. Отыскиваются условное распределение вектора на втором ша- ге (t 2 = t 1 +Δt), при условии получения соответствующих значений на первом шаге и т.д., пока t i = t 0 + iΔt не примет значения (t М = t 0 + МΔt). Принцип Δt является универсальным, применим для широкого класса сис- тем. Его недостатком является неэкономичность с точки зрения затрат машинно- го времени. 2) Принцип особых состояний (принцип ). При рассмотрении некоторых видов систем можно выделить два вида состояний: 193 обычное, в котором система находится большую часть времени, при этом Z i (t), (i=1,…,n) изменяются плавно. особое, характерное для системы в некоторые моменты времени, причем состояние системы изменяется в эти моменты скачком. Принцип особых состояний отличается от принципа Δt тем, что шаг по времени в этом случае не постоянен, является величиной случайной и вычисля- ется в соответствии с информацией о предыдущем особом состоянии. Примерами систем, имеющих особые состояния, являются системы массо- вого обслуживания. Особые состояния появляются в моменты поступления зая- вок, в моменты освобождения каналов и т.д. Для таких систем применение принципа Δt является нерациональным, так как при этом возможны пропуски особых состояний и необходимы методы их обнаружения. В практике использования имитационного моделирования описанные вы- ше принципы при необходимости комбинируют. Пример применения принципа Δt. На рис. 10.4. приведена аналоговая схема дифференцирующего фильтра. Рис. 10.4. Аналоговая схема дифференцирующего фильтра Процесс, происходящий в фильтре, описывается дифференциальным урав- нением: 194 (10.1) В уравнении: K- коэффициент усиления, х(t) – входной сигнал. Доказано, что Преобразуем математическую модель фильтра (10.1) к виду, позволяюще- му применить принцип Δt. В простейшем случае достаточно уравнение (3.1) ап- проксимировать конечно-разностным уравнением: (10.2) Задав начальное условие Z(t 0 )=Z 0 можно построить траекторию процесса, происходящего в фильтре, с целью получения текущего значения производной любой детерминированной функции x(t), подаваемой на вход. 195 11 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СЛОЖНЫХ СИСТЕМ 11.1 Системы массового обслуживания 11.1.1 Основные сведения из теории массового обслуживания Объектами проектирования на системном уровне являются такие сложные системы, как производственные предприятия, транспортные системы, вычисли- тельные системы и сети, автоматизированные системы проектирования и управ- ления и т. п. В этих приложениях анализ процессов функционирования систем связан с исследованием прохождения через систему потока заявок (иначе назы- ваемых требованиями или транзактами). Разработчиков подобных сложных систем интересуют прежде всего такие параметры, как производительность (пропускная способность) проектируемой системы, продолжительность обслу- живания (задержки) заявок в системе, эффективность используемого в системе оборудования. Заявками могут быть заказы на производство изделий, задачи, решаемые в вычислительной системе, клиенты в банках, грузы, поступающие на транспорти- ровку и др. Очевидно, что параметры заявок, поступающих в систему, являются случайными величинами и при проектировании могут быть известны лишь их законы распределения и числовые характеристики этих распределений. Поэтому анализ функционирования на системном уровне, как правило, носит статистиче- ский характер. В качестве математического аппарата моделирования удобно принять теорию массового обслуживания, а в качестве моделей систем на этом уровне использовать системы массового обслуживания (СМО). Типичными выходными параметрами в СМО являются числовые характе- ристики таких величин, как время обслуживания заявок в системе, длины очере- дей заявок на входах, время ожидания обслуживания в очередях, загрузка уст- ройств системы, а также вероятность обслуживания в заданные сроки и т. п. В простейшем случае СМО представляет собой некоторое средство (уст- ройство), называемое обслуживающим аппаратом (ОА), вместе с очередями 196 заявок на входах. Более сложные СМО состоят из многих взаимосвязанных ОА. Обслуживающие аппараты СМО в совокупности образуют статические объек- ты СМО, иначе называемые ресурсами. Например, в вычислительных сетях ре- сурсы представлены аппаратными и программными средствами. В СМО кроме статических объектов фигурируют динамические объекты – транзакты. Например, в вычислительных сетях динамическими объектами явля- ются решаемые задачи и запросы на информационные услуги. Состояние СМО характеризуется состояниями составляющих ее объектов. Например, состояния ОА выражаются булевыми величинами, значения которых интерпретируются как true (занято) и false (свободно), и длинами очередей на входах ОА, принимающими неотрицательные целочисленные значения. Пере- менные, характеризующие состояние СМО, будем называть переменными со- стояния или фазовыми переменными. Правило, согласно которому заявки выбирают из очередей на обслужива- ние, называют дисциплиной обслуживания, а величину, выражающую преиму- щественное право на обслуживание, – приоритетом. В бесприоритетных дис- циплинах все транзакты имеют одинаковые приоритеты. Среди бесприоритетных дисциплин наиболее популярны дисциплины FIFO (первым пришел – первым обслужен), LIFO (последним пришел – первым обслужен) и со случайным выбо- ром заявок из очередей. В приоритетных дисциплинах для заявок каждого приоритета на входе ОА выделяется своя очередь. Заявка из очереди с низким приоритетом поступает на обслуживание, если пусты очереди с более высоким приоритетом. Различают приоритеты абсолютные, относительные и динамические. Заявка из очереди с более высоким абсолютным приоритетом, поступая на вход занятого ОА, пре- рывает уже начатое обслуживание заявки более низкого приоритета. В случае относительного приоритета прерывания не происходит, более высокоприори- тетная заявка ждет окончания уже начатого обслуживания. Динамические при- оритеты могут изменяться во время нахождения заявки в СМО. 197 Исследование поведения СМО, т.е. определение временных зависимостей переменных, характеризующих состояние СМО, при подаче на входы любых требуемых в соответствии с заданием на эксперимент потоков заявок, называют имитационным моделированием СМО. Имитационное моделирование проводят путем воспроизведения событий, происходящих одновременно или последова- тельно в модельном времени. При этом под событием понимают факт измене- ния значения любой фазовой переменной. Подход, альтернативный имитационному моделированию, называют ана- литическим исследованием СМО. Аналитическое исследование заключается в получении формул для расчета выходных параметров СМО с последующей под- становкой значений аргументов в эти формулы в каждом отдельном эксперимен- те. Модели СМО, используемые при имитационном и аналитическом модели- ровании, называются имитационными и аналитическими соответственно. Аналитические модели удобны в использовании, поскольку для аналити- ческого моделирования не требуются сколько-нибудь значительные затраты вы- числительных ресурсов. Часто без постановки специальных вычислительных экспериментов разработчик может оценить характер влияния аргументов на вы- ходные параметры, выявить те или иные общие закономерности в поведении системы. Но, к сожалению, аналитическое исследование удается реализовать только для частных случаев сравнительно несложных СМО. Для сложных СМО аналитические модели если и удается получить, то только при принятии упро- щающих допущений, ставящих под сомнение адекватность модели. Поэтому основным подходом к анализу САПР на системном уровне про- ектирования считают имитационное моделирование, а аналитическое исследова- ние используют при предварительной оценке различных предлагаемых вариан- тов систем. Некоторые компоненты СМО характеризуются более чем одним входным и (или) выходным потоками заявок. Правила выбора одного из возможных на- правлений движения заявок входят в соответствующие модели компонентов. В 198 одних случаях такие правила относятся к исходным данным (например, выбор направления по вероятности), но в некоторых случаях желательно найти опти- мальное управление потоками в узлах разветвления. Тогда задача моделирова- ния становится более сложной задачей синтеза, характерными примерами явля- ются маршрутизация заявок или синтез расписаний и планов. 11.1.2 Аналитические модели СМО Как отмечено выше, аналитические модели СМО удается получить при довольно серьезных допущениях. К числу типичных допущений относятся сле- дующие. Во-первых, как правило, считают, что в СМО используются бесприоритет- ные дисциплины обслуживания типа FIFO. Во-вторых, времена обслуживания заявок в устройствах выбираются в со- ответствии с экспоненциальным законом распределения. В-третьих, в аналитических моделях СМО входные потоки заявок аппрок- симируются простейшими потоками, т.е. потоками, обладающими свойствами стационарности, ординарности (невозможности одновременного поступления двух заявок на вход СМО), отсутствия последействия. В большинстве случаев модели СМО отображают процессы с конечным множеством состояний и с отсутствием последействия. Такие процессы называ- ют конечными марковскими цепями. Марковские цепи характеризуются множеством состояний S, матрицей ве- роятностей переходов из одного состояния в другое и начальными условиями (начальным состоянием). Удобно представлять марковскую цепь в виде графа, в котором вершины соответствуют состояниям цепи, дуги – переходам, веса дуг – вероятностям переходов (если время дискретно) или интенсивностям переходов (если время непрерывно). 199 11.1.3 Имитационное моделирование СМО Для представления имитационных моделей можно использовать языки программирования общего применения, однако такие представления оказывают- ся довольно громоздкими. Поэтому обычно применяют специальные языки ими- тационного моделирования на системном уровне. Среди языков имитационного моделирования различают языки, ориентированные на описание событий, средств обслуживания или маршрутов движения заявок (процессов). Выбор язы- ка моделирования определяет структуру модели и методику ее построения. Ориентация на устройства характерна для функционально-логического и более детальных иерархических уровней описания объектов. Для описания имитационных моделей на системном уровне (такие модели иногда называют сетевыми имитационными моделями – СИМ) чаще использу- ют языки, ориентированные на события или процессы. Примерами первых могут служить языки Симскрипт, SMPL и ряд других, К числу вторых относятся языки Симула, SOL, а также популярный язык GPSS. Языки имитационного моделирования реализуются в программно- методических комплексах моделирования СМО, имеющих ту или иную степень специализации. Так, комплексы на базе языка GPSS можно использовать во мно- гих приложениях, но есть специализированные комплексы для моделирования вычислительных сетей, систем управления предприятиями и т. п. При использовании языков, ориентированных на процессы, в составе СИМ выделяются элементарные части и ими могут быть источники входных потоков заявок, устройства, накопители и узлы. Источник входного потока заявок представляет собой алгоритм, в соот- ветствии с которым вычисляются моменты t k появления заявок на выходе источ- ника. Источники могут быть зависимыми и независимыми. В зависимых источ- никах моменты появления заявок связаны с наступлением определенных собы- тий, например, с приходом другой заявки на вход некоторого устройства. Ти- пичным независимым источником является алгоритм выработки значений t k слу- чайной величины с заданным законом распределения. 200 Устройства в имитационной модели представлены алгоритмами выработ- ки значений интервалов (длительностей) обслуживания. Чаще всего это алго- ритмы генерации значений случайных величин с заданным законом распределе- ния. Но могут быть устройства с детерминированным временем обслуживания или временем, определяемым событиями в других частях СИМ. Модель устрой- ства отображает также заданную дисциплину обслуживания, поскольку в модель входит алгоритм, управляющий очередями на входах устройства. Накопители моделируются алгоритмами определения объемов памяти, за- нимаемых заявками, приходящими на вход накопителя. Обычно объем памяти, занимаемый заявкой, вычисляется как значение случайной величины, закон и (или) числовые характеристики распределения могут зависеть от типа заявки. Узлы выполняют связующие, управляющие и вспомогательные функции в имитационной модели, например, для выбора направлений движения заявок в СИМ, изменения их параметров и приоритета, разделения заявок на части, их объединения и т. п. Обычно каждому типу элементарной модели, за исключением лишь неко- торых узлов, в программной системе соответствует определенная процедура (подпрограмма). Тогда СИМ можно представить как алгоритм, состоящий из упорядоченных обращений к этим процедурам, отражающим поведение модели- руемой системы. В процессе моделирования происходят изменения модельного времени, которое чаще всего принимается дискретным, измеряемым в тактах. Время из- меняется после того, как закончена имитация очередной группы событий, отно- сящихся к текущему моменту времени t k . Имитация сопровождается накоплени- ем в отдельном файле статистики таких данных, как количество заявок, вышед- ших из системы обслуженными и необслуженными, суммарное время занятого состояния для каждого из устройств, средние длины очередей и т. п. Имитация заканчивается, когда текущее время превысит заданный отрезок времени или ко- гда входные источники выработают заданное число заявок. После этого произ- 201 водят обработку накопленных в файле статистики данных, что позволяет полу- чить значения требуемых выходных параметров. 11.1.4 Событийный метод моделирования В программах имитационного моделирования СМО преимущественно реализуется событийный метод организации вычислений. Сущность событий- ного метода заключается в отслеживании на модели последовательности собы- тий в том же порядке, в каком они происходили бы в реальной системе. Вычис- ления выполняют только для тех моментов времени и тех частей (процедур) мо- дели, к которым относятся совершаемые события. 11.1.5 Классификация СМО 1) По характеру источника требований различают СМО с конечным и бес- конечным количеством требований на входе. В первом случае в системе циркулирует конечное, обычно постоянное ко- личество требований, которые после завершения обслуживания возвращаются в источник. Во втором случае источник генерирует бесконечное число требований. Пример 1. Цех с постоянным количеством станков или определенное ко- личество ПЭВМ в терминальном классе, требующих постоянного профилакти- ческого осмотра и ремонта. Пример 2. Сеть Internet с бесконечным требованием на входе, любой мага- зин, парикмахерская и т.д. Первый вид СМО называют замкнутой, второй – разомкнутой. 2) По дисциплине обслуживания: обслуживание в порядке поступления; 202 обслуживание в случайном порядке (в соответствии с заданным законом распределения); обслуживание с приоритетом. 3) по характеру организации: с отказами; с ожиданиями; с ограничением ожидания. В первом случае заявка получает отказ, когда канал занят. Во втором слу- чае – ставится в очередь и ждет освобождения канала. В третьем случае вводится ограничения на длительность ожидания. 4) По количеству единиц обслуживания: одноканальные; двухканальные; многоканальные. 5) По числу этапов (фаз) обслуживания - на однофазные и многофазные. (Примером многофазных СМО может служить любая поточная линия). 6) По свойствам каналов: на однородные, когда каналы имеют одинаковую характеристику и неоднородные в противном случае. 11.1.6 Основная задача теории СМО Основная задача ТСМО заключается в установлении зависимости между характером потока заявок на входе СМО, производительностью одного канала, числом каналов и эффективностью обслуживания. В качестве критерия эффективности могут быть использованы различные функции и величины: среднее время простоя системы; 203 среднее время ожидания в очереди; закон распределения длительности ожидания требования в очереди; средний % заявок, получивших отказ; и т.д. Выбор критерия зависит от вида системы. Например, для систем с отказа- ми главной характеристикой является абсолютная пропускная способность СМО; менее важные критерии - число занятых каналов, среднее относительное время простоя одного канала и системы в целом. Для систем без потерь (с неог- раниченным ожиданием) важнейшим является среднее время простоя в очереди, среднее число требований в очереди, среднее время пребывания требований в системе, коэффициент простоя и коэффициент загрузки обслуживающей систе- мы. Современная ТСМО является совокупностью аналитических методов ис- следования перечисленных разновидностей СМО. В дальнейшем из всех доста- точно сложных и интересных методов решения задач массового обслуживания будут изложены методы, описываемые в классе марковских процессов типа “ги- бель и размножение”. Это объясняется тем, что именно эти методы чаще всего используются в практике инженерных расчетов. 204 11.1.7 Математические модели потоков событий 11.1.7.1 Регулярный и случайный потоки. Одним из центральных вопросов организации СМО является выяснение закономерностей, которым подчиняются моменты поступления в систему требо- ваний на обслуживание. Рассмотрим наиболее употребляемые математические модели входных потоков. |