Единое окно доступа к образовательным ресурсам

Моделирование: задачи, задания, тесты: Учебное пособие

Голосов: 3

Пособие содержит задачи, задания и тестовые вопросы, предназначенные для закрепления теоретического материала по моделированию дискретных систем с использованием аналитических, численных и имитационных методов. Аналитические методы исследования базируются на аппарате теории массового обслуживания, численные - на аппарате теории Марковских случайных процессов, статистические - на методах имитационного моделирования, которое реализуется в среде GPSS World. Многочисленные примеры и задачи направлены на развитие умения и навыков применять простейшие модели и методы для расчѐта характеристик функционирования систем, представляемых моделями массового обслуживания или моделями Марковских случайных процессов. Пособие предназначено для студентов, изучающих дисциплину "Моделирование" и связанные с ней дисциплины в рамках подготовки бакалавров и магистров по направлениям "Информатика и вычислительная техника" и "Программная инженерия".

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
                 Т.И. Алиев,
Л.А. Муравьева-Витковская, В.В.Соснин


        МОДЕЛИРОВАНИЕ:
     ЗАДАЧИ, ЗАДАНИЯ, ТЕСТЫ




                         П




             Санкт-Петербург
                  2011


Алиев Т.И., Муравьева-Витковская Л.А., Соснин В.В. Моделирование:
задачи, задания, тесты. – СПб: НИУ ИТМО, 2011. – 197 с.

Пособие содержит задачи, задания и тестовые вопросы, предназначенные для
закрепления теоретического материала по моделированию дискретных
систем с использованием аналитических, численных и имитационных
методов. Аналитические методы исследования базируются на аппарате
теории массового обслуживания, численные – на аппарате теории
Марковских случайных процессов, статистические – на методах
имитационного моделирования, которое реализуется в среде GPSS World.
Многочисленные примеры и задачи направлены на развитие умения и
навыков применять простейшие модели и методы для расчѐта характеристик
функционирования     систем,    представляемых    моделями     массового
обслуживания или моделями Марковских случайных процессов.
 Пособие предназначено для студентов, изучающих дисциплину
«Моделирование» и связанные с ней дисциплины в рамках подготовки
бакалавров и магистров по направлениям «Информатика и вычислительная
техника» и «Программная инженерия».
Рекомендовано к печати Советом факультета компьютерных технологий и
управления 15 ноября 2011 г., протокол № 9.




В 2009 году Университет стал победителем многоэтапного конкурса, в
результате которого определены 12 ведущих университетов России, которым
присвоена категория «Национальный исследовательский университет».
Министерством образования и науки Российской Федерации была
утверждена программа его развития на 2009–2018 годы. В 2011 году
Университет получил наименование «Санкт-Петербургский национальный
исследовательский университет информационных технологий, механики и
оптики»

      Санкт-Петербургский национальный исследовательский университет
                   информационных технологий, механики и оптики, 2011

                                                          Алиев Т.И.,
                                             Муравьева-Витковская Л.А.,
                                                      Соснин В.В., 2011


                               Введение
      Математическое моделирование заключается в применении адекватных
моделей исследуемых систем для решения задач анализа и синтеза с
использованием аналитических и имитационных методов. В процессе
моделирования решаются задачи разработки модели, анализа свойств и
выработки     рекомендаций по модернизации существующей               или
проектированию новой системы.
      Эффективность решения этих задач в значительной степени
определяется     квалификацией    исследователя,    умением    применять
существующие методы и средства, а также разрабатывать новые для
достижения поставленной цели. Эти умения приобретаются как в процессе
изучения теоретических вопросов моделирования, так и в процессе решения
практических задач.
      Настоящий сборник содержит множество задач, заданий и тестовых
вопросов, предназначенных для закрепления теоретического материала по
моделированию дискретных систем, излагаемого в учебном пособии [1].
      Многочисленные примеры и задачи направлены на развитие умения и
навыков применять простейшие модели и методы для расчѐта характеристик
функционирования      систем,   представляемых     моделями     массового
обслуживания или моделями Марковских случайных процессов.
      Структура сборника. Сборник содержит 4 раздела и Список
литературы.
      В первом разделе приводятся краткие теоретические сведения,
необходимые для решения задач и выполнения заданий, представленных во
втором и третьем разделах соответственно. Более подробная информация по
всем теоретическим вопросам представлена в учебном пособии [1].
      Второй раздел содержит простейшие задачи, решение которых
базируется на аналитических методах расчета систем (СМО) и сетей (СеМО)
массового обслуживания, методах Марковских случайных процессов и
имитационного моделирования в среде GPSS World. Основное назначение
этих задач – закрепление теоретического материала и грамотное применение
основных математических зависимостей, методов и средств моделирования в
процессе решения конкретных задач.
      Третий раздел содержит задания на учебно-исследовательские работы,
которые могут выполняться как домашние задания, лабораторные или
курсовые работы. В отличие от задач второго раздела, выполнение заданий
предполагает     использование    специальных     программных     средств
аналитического, численного и имитационного моделирования и требует
подготовки отчета, содержащего не только расчет характеристик
функционирования исследуемых систем, но и всесторонний анализ свойств
системы, рекомендации по проектированию и, в некоторых случаях, решение
задачи синтеза.
      В качестве программных средств, реализующих аналитические и
численные методы расчѐта, рекомендуется использовать разработанные и


внедрѐнные в учебный процесс кафедры вычислительной техники
следующие программы:
      ITMOdel – аналитический расчет моделей массового обслуживания;
      MARK – расчѐт Марковских процессов.
     Имитационное       моделирование     предполагает   использование
следующих систем имитационного моделирования:
      GPSS World фирмы Minuteman Software;
      Any Logic фирмы XJ Technologies.
     В четвёртом разделе представлен примерный перечень вопросов по
компьютерному тестированию, охватывающих все разделы пособия [1].
     Список литературы содержит ограниченный перечень литературных
источников, которые в той или иной мере могут быть использованы при
решении задач и выполнении заданий, а также при подготовке к
компьютерному тестированию. Этот перечень включает учебные пособия и
монографии, которые можно разбить на две группы, содержащие материал:
      по аналитическим и численным методам моделирования систем и
        сетей массового обслуживания [1-3];
      по имитационному моделированию систем и сетей массового
        обслуживания в среде GPSS World [4, 5].

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


                                Раздел 1. Краткие теоретические сведения


     Раздел 1. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
                     1.1. Элементы теории вероятностей
       Закон распределения случайной величины – соотношение,
устанавливающее связь между возможными значениями случайной
величины и соответствующими им вероятностями.
       Закон распределения дискретной случайной величины может быть
задан:
        аналитически в виде математического выражения;
        таблично в виде ряда распределения;
        графически в виде многоугольника распределения.
       Закон распределения непрерывной случайной величины может быть
задан в виде:
        функции    распределения     F(x)      случайной величины  X,
представляющей собой вероятность того, что случайная величина X
примет значение меньшее, чем некоторое заданное значение x:
F ( x)  P( X  x);
        плотности распределения f(x), определяемой как производная от
функции распределения F(x) по x: f ( x)  F ( x).
       Функция распределения однозначно определяется через плотность
распределения как
                 x
      F ( x)     f ( x) dx.
                 
     Свойства функции распределения:
      F(x) – неубывающая функция: если xj > xi , то F ( x j )  F ( xi );
      функция распределения принимает значения от 0 до 1 , причѐм:
F ()  0 и F ( )  1.
     Свойства плотности распределения:
      плотность распределения принимает только неотрицательные
значения: f ( x)  0;
      площадь на графике, ограниченная плотностью распределения и
                                                    
осью абсцисс, всегда равна единице:                  f ( x) dx  1.
                                                   
     Числовые характеристики случайных величин:
      начальные  s [X ] моменты:
            n s
             xi pi         для дискретной случайной величины;
             i 1
 s [ X ]                                                                (1)
             x s f ( x) dx  для непрерывно й случайной величины;
            
             
         центральные  s [X ] моменты:
                                                                                   5


                       Раздел 1. Краткие теоретические сведения


             n
              ( xi  M[ X ]) pi             для дискретной величины;
                                  s

              i 1
 s [ X ]                                                           (2)
              ( x  M[ X ]) s f ( x) dx  для непрерывно й величины.
             
              
         Первый начальный момент случайной величины Х называется
математическим ожиданием и характеризует среднее значение случайной
величины:
                       n
                        xi pi            для дискретной величины;
                        i 1
M [ X ]   1[ X ]                                                  (3)
                        x f ( x) dx  для непрерывно й величины.
                       
                        
         Второй начальный момент  2 [ X ] случайной величины X
характеризует разброс значений случайной величины относительно
начала координат.
         Второй центральный момент называется дисперсией случайной
величины: D[ X ]   2 [ X ] и характеризует разброс значений случайной
величины относительно математического ожидания:
           n
            ( xi  M[ X ]) pi              для дискретной величины;
                                2

            i 1
D[ X ]                                                              (4)
            ( x  M[ X ]) f ( x) dx  для непрерывно й величины.
           
                              2

            
         Дисперсия и второй начальный момент связаны зависимостью
         D[ X ]  2 [ X ]  ( M[ X ])2 .                               (5)
         Среднеквадратическое отклонение  [X ] – характеристика разбро-
са, размерность которой совпадает с размерностью случайной величины:
          [ X ]  D[ X ] .                                             (6)
         Коэффициент вариации  [X ] – безразмерная характеристика
разброса случайных величин, определенных в области положительных
значений:
          [ X ]   [ X ] / M[ X ]       ( M[ X ]  0 ).               (7)

      В моделях дискретных систем наиболее широко применяются
следующие законы распределений случайных величин:
       распределение Пуассона (дискретный закон):
                         a k a
       pk  P( X  k )     e    (k  0, 1, 2,) ,       (8)
                         k!
где a – параметр распределения ( a  0 );
       геометрическое распределение (дискретный закон):
6


                                Раздел 1. Краткие теоретические сведения


      pk  P( X  k )   k (1   )   k  0, 1, 2,  ,       (9)
где  – параметр распределения ( 0    1 );
      равномерное распределение (непрерывный закон) с плотностью
                1
                       при a  x  b;
      f ( x)   b  a                                          (10)
               0
                       при x  b;
      экспоненциальное распределение (непрерывный закон) с функцией
и плотностью
        F ( x)  1  ex ;                   f ( x)   e x ,                            (11)
где   0  параметр распределения; x  0 ;  эксп[ X ]  1
        распределение Эрланга k-го порядка (непрерывный закон) с
функцией и плотностью:
                               k 1
                                     (x )i                        (x )k 1 x
        Fk ( x )  1  ex                 ;        fk ( x)               e ,               (12)
                               i 0     i!                         (k  1)!
где  и k – параметры распределения (  0; k  1, 2,) ; x  0 ;
               1
 Эk [ X ]         1 математическое ожидание распределения Эрланга
                k
зависит от значения параметра k;
        нормированное распределение Эрланга (непрерывный закон) с
функцией и плотностью:
                                  k 1
                                       (k x)i                         k (k x) k 1  k x
        Fk ( x)  1  e    k x
                                   i! ;                   f k ( x) 
                                                                          (k  1)!
                                                                                     e       ; (13)
                                  i 0
коэффициент вариации нормированного распределения Эрланга также
                                                                       1
меньше или равен единице:  нЭk [ X ]                                     1 , но математическое
                                                                        k
ожидание не зависит от значения параметра k;
         гипоэкспоненциальное распределение (непрерывный закон),
преобразование Лапласа которого определяется как:
                      k                  k
                                               i      k
                                                              1
        F ( s)   Fi ( s)  
           *               *
                                                                   ,
                    i 1               i 1  i  s  i 1 1  sxi
                   i               1
где Fi* ( s)                              – преобразование Лапласа экспоненциального
                  i  s 1  sxi
распределения (i-й составляющей) с параметром  i и математическим
ожиданием xi  1/ i ;
математическое ожидание, дисперсия и коэффициент вариации
гипоэкспоненциального распределения равны:
                k                    k                      k         k
        M k   xi ;          Dk   xi2 ;       k       xi2       xi ,                 (14)
               i 1                 i 1                   i 1      i 1



                                                                                                 7


                            Раздел 1. Краткие теоретические сведения

причѐм коэффициент вариации  k гипоэкспоненциального распределения
может принимать любые значения в интервале (0; 1), в том числе, в
отличие от распределения Эрланга, нецелочисленные значения;
       гиперэкспоненциальное распределение (непрерывный закон):
                  n                       n
                                                        
       F ( x)   qi (1  e )  1   qi e  i x ; 
                              i x

                i 1                    i 1            
                  n                                     .                             (15)
       f ( x)   qi  i e  i x                       
                i 1
                                                        
                                                        
      Для аппроксимации реальных распределений по двум первым
моментам – математическому ожиданию t и коэффициенту вариации
 – могут использоваться следующие аппроксимирующие распределения:
       если коэффициент вариации случайной величины меньше
единицы (                 ) – гипоэкспоненциальное распределение, параметры
которого рассчитываются по формулам:

       k
            2
              1           t
                         k
                                     
                                     k
                                                          t
                ; t1  1  2 k 2  1 ; t 2  1  1 k 2  1  ;
                                                                     k
                                                                                 
                                                                                       (16)
                                     k1                    k      k2             
       если коэффициент вариации временного интервала больше
единицы (            ) – гиперэкспоненциальное распределение, параметры
которого рассчитываются по формулам:
       2                      1 q 2                           q               
 q          ; t1  1              (  1) t ; t 2  1             ( 2  1) t . (17)
    1   2
                                 2q                        2 (1  q)           
      1.2. Параметры и характеристики моделей массового
                         обслуживания
     Ниже     рассматриваются модели массового обслуживания,
представляющие собой системы (СМО) и сети (СеМО) массового
обслуживания.
                1.2.1. СМО с однородным потоком заявок
     Для компактного описания систем массового обслуживания (СМО)
используются обозначения в виде A/B/N/L , где A и В – задают законы
распределений соответственно интервалов времени между моментами
поступления заявок и длительностей обслуживания в приборе; N – число
обслуживающих приборов в системе; L – число мест в накопителе.
     Для описания СМО, в простейшем случае, необходимо задать
следующие параметры:
      количество обслуживающих приборов K;
      количество k и емкости накопителей Ej ( j  1, k ) ;
      количество поступающих в систему классов заявок H;
      интенсивность i потока и коэффициент вариации  ai интервалов
времени между поступающими в систему заявками класса i  1, H ;

8


                     Раздел 1. Краткие теоретические сведения


      среднее значение bi и коэффициент вариации  bi длительности
обслуживания заявок класса i  1, H ;
      дисциплина буферизации и дисциплина обслуживания заявок.
     В режиме перегрузки, когда система не справляется с нагрузкой,
характеристики функционирования СМО с накопителем неограниченной
емкости с течением времени растут неограниченно.
     Для того чтобы в такой СМО не было перегрузок, необходимо,
чтобы нагрузка системы была меньше, чем число обслуживающих
приборов, или, что то же самое, загрузка системы была строго меньше
единицы. В СМО с накопителем ограниченной ѐмкости перегрузки не
приводят к неустановившемуся режиму.

      В качестве основных характеристик СМО с однородным потоком
заявок используются:
       нагрузка системы:
       y   /   b ;                                           (18)
       вероятность потери заявок (для СМО с накопителем
ограниченной ѐмкости):
                   N (T )
       п  lim п           ;                                     (19)
             T  N (T )

       вероятность того, что заявка будет обслужена, т.е. не потеряна
(для СМО с накопителем ограниченной ѐмкости):
       о  (1   п );                                           (20)
       загрузка системы:
                  (1   п ) y 
        min                 ; 1 ;                             (21)
                       K         
       коэффициент простоя системы:
        1  ;                                                  (22)
       производительность системы:
      '   о   (1   п ) ;                                  (23)
       интенсивность потока потерянных заявок:
      "   п   (1   о ) ;                                  (24)
       среднее время ожидания заявок в очереди:
      w  ? (подлежит определению для каждой конкретной СМО);
       среднее время пребывания заявок в системе:
      u  w b;                                                   (25)
       средняя длина очереди заявок:
      l  ' w ;                                                  (26)
       среднее число заявок в системе:
      m  ' u .                                                  (27)

                                                                    9


                             Раздел 1. Краткие теоретические сведения

               1.2.2. СМО с неоднородным потоком заявок
      Для СМО с неоднородным потоком заявок определяются две
группы характеристик обслуживания заявок: характеристики по каждому
классу заявок по формулам (18) – (27) и характеристики суммарного
(объединенного) потока заявок:
      суммарная интенсивность поступления заявок в систему
(интенсивность суммарного потока):
           H
         i ;                                                        (28)
          i 1
        суммарная нагрузка Y и суммарная загрузка R системы:
           H
     Y   yi ;                                                         (29)
          i 1
                  H
      R  min(   i ;1) ,                                              (30)
                  i 1
где i , yi и  i – соответственно интенсивность поступления, нагрузка и
загрузка, создаваемые заявками класса            ; – количество классов
заявок; причем условие отсутствия перегрузок в СМО с неоднородным
потоком заявок и накопителем неограниченной ѐмкости имеет вид:
       R  1;                                                       (31)
      коэффициент простоя системы:
        1  R                     (32)
      среднее время ожидания W и среднее время пребывания U заявок
объединѐнного потока в системе:
           H                          H
     W   i wi ;             U    i ui ,                           (33)
           i 1                       i 1
где i  i /  – коэффициент, учитывающий долю заявок класса i в
суммарном потоке, который может трактоваться как вероятность того,
что поступившая в систему заявка принадлежит классу i;
      суммарная длина очереди и суммарное число заявок в системе:
           H                           H
      L   li ;                M   mi .                              (34)
          i 1                        i 1
      Для характеристик объединѐнного (суммарного) потока справедливы
те же фундаментальные соотношения (25) – (27) , что и для однородного
потока:
      U W  B;      L  W ;        M  U ,
где B – среднее время обслуживания любой заявки суммарного потока:
           H
      B   i bi .
          i 1




10



    
Яндекс цитирования Яндекс.Метрика