Кораблин М.А. Имитационное моделирование в задачах поиска управленческих решений - файл n1.doc

приобрести
Кораблин М.А. Имитационное моделирование в задачах поиска управленческих решений
скачать (3749.5 kb.)
Доступные файлы (1):
n1.doc3750kb.07.07.2012 04:10скачать

n1.doc

  1   2   3   4   5   6
Например, проект А связан с инвестициями, которые можно сделать в начале первого года на два следующих. Причем в конце второго года можно возвратить 0,3 руб. на каждый рубль, вложенный в начале первого года. Аналогично, в конце третьего года можно получить еще 1 руб. на рубль вложений в начале первого года. Максимальная сумма, которая может быть вложена в проект А, составляет 500 млн. руб. По другим проектам объем вложений не ограничен. Проект В аналогичен проекту А, но вложения можно сделать только в начале второго года, а выплаты по процентам – в конце третьего и четвертого года.

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

У компании имеется 1 млрд. руб. для инвестиций. Она хочет максимизировать сумму денег, получаемых к четвертому году инвестиционного процесса. Какова эта сумма и оптимальная стратегия инвестиций?

Имитационное моделирование в задачах поиска управленческих решений

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

Эта технология появилась в 60-х г. XX в., и на протяжении многих лет она не только остается одной из основных в исследовании операций, но и бурно развивается в области реинжиниринга бизнес-процессов [10] и новых направлений искусственного интеллекта (онтология предприятий [11], клеточные автоматы [12], мультиагентные системы [13] и др.).

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

Технология имитационного моделирования излагается на основе использования системы Micro Saint, одной из наиболее простых и адекватных задачам исследования систем операционного и производственного менеджмента. Micro Saint представлена на сайтах www.adeptscience.co.uk, www.maad.com, www.maad.com, используемая версия (студенческий вариант) взята на сайте www.radata.demon.co.uk (в настоящее время отсутствует). Система не русифицирована. Отличительными особенностями ее являются концептуальная завершенность, целостность и простота использования даже для исследования весьма сложных систем. На взгляд автора, система является прекрасным инструментом для изучения концепций и технологии имитационного моделирования систем управления в различных областях производственного и операционного менеджмента.

Быстрое начало: введение в систему Micro Saint

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

Сетевая структура модели

Модель исследуемой системы должна быть представлена в виде сетевой структуры. Пример такой структуры приведен на рис. 2.1.



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



Блок рисуется с помощью пиктограммы . Рис. 2.3. Вид блока действий показан на рис. 2.4.



Рис. 2.4.

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



Рис. 2.5.

В окне name пишем car coming и щелкаем на кнопке Accept Рис. 2.6.



Рис. 2.6
Содержательно эту простейшую схему рис. 2.1 мы будем интерпретировать как

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

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

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

Блок «Саг coming» определяет приезд автомобилей на заправку, а блок «Gas station» – обслуживание автомобиля у бензоколонки. Любой тэг, «входящий» в блок, может в этом блоке задерживаться на определенное время. Такое время имитирует интервалы между приходами автомобилей на заправочную станцию и собственно длительностью процедуры заправки.

Описание элементов модели

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

Мы можем имитировать эти состояния с помощью переменной Status, которая будет принимать два значения:

Status := 1; (колонка переходит в состояние «Занята»),

Status := 0; (колонка переходит в состояние «Свободна»).

Оператор «:=» называется оператором присваивания, он назначает переменной Status то значение, которое записано справа от оператора присваивания. В этом примере Status – имя переменной, а 0 и 1 – возможные значения переменной. Во многих случаях перечислить все значения переменной трудно (или невозможно), поэтому в таких ситуациях переменную характеризуют типом, определяющим ее возможные значения.

Например, переменную N – количество автомобилей, обслуженных на автозаправке, резонно охарактеризовать типом Integer (целое число), а переменную V – количество заливаемого бензина – типом Real (действительное число).

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

Все переменные модели должны быть внесены в список переменных.

Открытие такого списка реализуется нажатием кнопки (средний ряд, вторая кнопка слева, см. рис. 2.1). При этом откроется окно списка переменных (рис. 2.3).

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



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

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

В нашем случае это переменные Status – состояние бензоколонки и N – количество автомобилей, обслуженных на автозаправке. Для того чтобы ввести эти переменные в список, необходимо нажать кнопку (нижний ряд панели инструментов рис. 2.1, справа). При этом откроется окно рис. 2.4, в котором задается имя переменной, ее смысловое содержание, тип и начальное значение.



Нажатие кнопки Accept вводит переменную в список, только после этого она становится полноправным участником процесса моделирования.

Описание задачи

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

На рис. 2.5 приведено такое окно для первого блока сетевой структуры рис. 2.1 «Gar coming». Поля Time Distribution, Mean Time и Standard Deviation используются для задания интервала времени между приходами автомобилей на заправочную станцию. В списке Time Distribution содержатся различные законы распределения вероятностей. Для нашего примера мы использовали равномерное распределение (Rectangular) со средним значением 10 (мин) и отклонением от среднего, равным 3 (мин).



В поле Standard Deviation в этом случае записывается 10 - 3 = 7 (мин), т. е. нижняя граница равномерного распределения. Такое задание приведет к тому, что в нашу модель будут поступать автомобили (тэги) через интервал времени (10 ± 3) мин. Выбор в качестве единицы времени 1 мин. обусловлен только исследователем. В общем случае это может быть произвольная единица (день, час и т. п.).

Поле Release Condition в общем случае содержит условие возможности входа тэга в соответствующий блок. Если в этом поле присутствует любое число, большее 0, вход в блок открыт (в нашем примере для блока «Gar coming» любой автомобиль может въехать на заправочную станцию). Для блока «Gas station» в поле Release Condition должно быть размещено условие входа в этот блок: Status= =0, т. е. вход автомобиля в блок возможен только тогда, когда бензоколонка свободна. В противном случае автомобиль не сможет подъехать к бензоколонке и будет находиться в очереди (символ «= =» используется как отношение равенства).

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

В нашем примере для блока «Car coming» (рис. 2.5) мы использовали только поле Beginning Effect, в котором разместили оператор: tag:=tag+l. Этот оператор присваивания (см. выше) реализует алгоритм накопления: каждый раз при входе вновь приехавшего автомобиля в блок «Car coming» входной эффект будет увеличивать индивидуальный порядковый номер автомобиля на 1. Таким образом, через структуру модели будут последовательно проводиться тэги-автомобили с номерами 0, 1, 2 и т. д.

В аналогичном окне для блока «Gas station» в полях входного и выходного эффектов будут размещены действия по изменению состояния бензоколонки. В поле входного эффекта определяется действие по занятию бензоколонки: Status :=l; а в поле выходного – по ее освобождению: Status:=0. Кроме того, в этом поле определяется действие, связанное с подсчетом количества автомобилей, «прошедших» через автозаправочную станцию: N:=N+1.

В полях Time Distribution, Mean Time и Standard Deviation блока «Gas station» следует указать характеристики времени заправки автомобиля (например, равномерное распределение в интервале 12 ± 6 мин.).

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

Описание регистратора очереди



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

Поле Sorting Order определяет порядок элементов (тэгов) в очереди:

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

Использование полей Entering Effect и Departing Effect аналогично использованию полей входного и выходного эффекта в окне описания задачи.

Описание разветвителя

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

Разветвитель может использовать один из трех типов разветвления (Decision Type): Multiple, Probabilistic и Tactical. Первый тип разветвления уже обсуждался выше – он создает множество копий тэга, вошедшего в разветвитель, и отправляет их на все выходы разветвителя. Такой режим позволяет моделировать параллельные (одновременно протекающие) процессы в исследуемой системе.

Единицы в полях Routing Condition интерпретируются так же, как и в полях Release Condition описания задачи (см. рис. 2.5).

Тип Probabilistic определяет стохастический (случайный) механизм выбора тэгом направления дальнейшего движения. Для такого выбора в полях Routing Condition задаются вероятности переходов по выбранному направлению (их сумма должна быть равна 1).



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

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

Запуск модели

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



Кроме кнопок этой панели можно также обратиться к разделу Execute главного меню системы.

Остановка модели

Существует два основных способа остановки модели: «вручную» (меню Execute, оператор Halt) и по определенному условию (достижение в модели определенного состояния).

Второй способ связан с размещением оператора остановки halt() в определенных полях описания модели. Например, размещение опера тора halt() в поле Entering Effect очереди (см. рис. 2.6) приведет к тому, что, когда первый тэг войдет в очередь и произойдет вычисление этого эффекта, модель будет остановлена.

Сбор результатов компьютерного эксперимента

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

Список коллекций открывается нажатием кнопки Если для разработанной модели не определено ни одной коллекции, этот список пуст (рис. 2.9).



Для определения коллекции следует нажать кнопку при открытом списке коллекций. При этом открывается окно описания коллекции (рис. 2.10).

В поле Document Name указывается имя коллекции (Gas), в поле Variables to Store – имена переменных, которые мы включаем в коллекцию (в нашей коллекции три переменных: clock, N и Status). Кроме того, в этом же окне указываются условия, при которых будут регистрироваться значения переменных коллекции.

Для коллекции Gas значения всех переменных будут регистрироваться каждые 10 единиц модельного времени, начиная с 0 (запуск модели) и кончая 1440 единицами модельного времени (остановка модели). Эти данные размещены в полях: Trigger Type, Trigger at Time, Repeat Interval и Stop Time.

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





Варианты Begin Task и End Task определяют в качестве условий сбора значений переменных соответственно ситуации, когда тэг входит в блок задачи и выходит из блока задачи. При этом поле Trigger on будет определять номер этой задачи.

Варианты Enter Queue и Depart Queue определяют в качестве условий сбора ситуации, когда тэг входит в очередь и соответственно выходит из нее. При этом поле Trigger on будет определять номер очереди.

Вариант End of Run будет связан со сбором результатов только в момент окончания моделирования.

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

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



Теперь при необходимости внесения изменений в коллекцию (добавление или удаление переменных) можно открыть окно рис. 2.10 двойным кликом на строке коллекции в списке Snapshots.

Определение параметров прогона модели

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

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

  1. Trace of Tasks (трассировка задач).

  2. Snapshots of Variables (сбор значений переменных).

  3. Standard Deviations Set to Zero (не используется для простых задач).

  4. Action View Functions (анимация).

  5. Queue Data Collection (сбор данных о состояниях очередей).

  6. Time to begin Data Collection (модельное время начала сбора данных).

  7. Times to Run the Model (номер прогона модели).

  8. Show Entities With (форма показа динамических объектов – тэгов, символами или их количеством, обычно символами).

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



Структуры файлов результатов

На рис. 2.13 представлен фрагмент файла GAS.RES, в котором собрана коллекция Gas (рис. 2.10), а на рис. 2.14 – фрагмент файла EXAMPLE1.QUE, в котором собрана информация о состоянии очередей в течение прогона программы модели.

Файл рис. 2.13 содержит 4 поля, из них 3 хранят значения переменных коллекции, собранных через интервал в 10 ед. времени, а поле Trigger информирует нас об условии сбора данных (см. рис. 2.10, 2.11). Файл в целом содержит 144 записи о значениях переменных коллекции Gas. (Термин Snapshot определяет как бы моментальный снимок, фотографию, на которой запечатлено состояние модели, зафиксированное в определенный момент времени.)



Рис. 2.13. Фрагмент коллекции Gas

Файл рис. 2.14 содержит 6 полей:

1. Clock (момент времени, в который изменилось состояние очереди);

  1. Tag (номер объекта-тэга, который был активен в этот момент времени). Напомним, что активный тэг – это тэг, который в текущий момент времени передвигается по структуре модели и меняет ее состояние;

  2. Run (номер прогона программы модели, он для нас не информативен);

  3. Length (длина очереди тэгов в момент Clock);

  4. Wait (время ожидания в очереди активного тэга);

  5. Trigger (характер изменения состояния очереди).

Поскольку в нашем примере всего одна очередь с номером 2 (см. рис. 2.6), все записи файла рис. 2.14 свидетельствуют об изменении состояния очереди с номером 2.

В поле Trigger встречаются записи четырех видов:

  1. Start (старт для работы с очередью);

  2. Enter (вход тэга в очередь);

  3. Depart (выход тэга из очереди);

  4. Bypass (проход тэга через очередь без задержки, т. е. через пустую очередь).



Первая запись файла EXAMPLE.QUE говорит о том, что в начальный момент времени тэг с номером 0 вошел в очередь нулевой длины и тут же вышел из нее (в блок 2), вторая свидетельствует о проходе тэга 1 через пустую очередь. Тэг с номером 2 вошел в пустую очередь и простоял в ней (в одиночестве) 3,476 ед. времени в связи с занятостью блока 2 (заправка автомобиля – тэга с номером 1). Аналогично поведение тэгов с номерами 3 и 4. Всего за весь сеанс моделирования система зарегистрировала 259 изменений в очереди

Анализ результатов эксперимента

Результаты эксперимента могут быть проанализированы с использованием методов, инкапсулированных в меню Анализ (Analyze). Эти методы позволяют представить результаты прогона модели в наглядной лаконичной форме графика или таблицы. Использование методов анализа призвано способствовать выявлению «узких мест» в организации исследуемой системы и принятию управленческих решений по реорганизации бизнес-процессов.

Статистика очереди

Файлы результатов с расширением QUE анализируются методами «Статистика очереди» (Queue Statistics) и «Графы очереди» (Queue Graphs). Для вызова этих методов необходимо открыть соответствующий файл (сделать окно с файлом активным) и выбрать в меню нужный вам метод. Вызов метода «Статистика очереди» для файла EXAMPLE1.QUE приведет к выводу таблицы рис. 2.15.

В этой таблице для очереди 2 примера 1 представлены характеристики длины очереди (Length of Queue) и времени пребывания тэга в очереди (Wait Time) (Mean – среднее значение, Std.Def. – Standard Deviation – среднеквадратичное отклонение для каждой из характеристик).



Рисунок 2.16 иллюстрирует использование метода «Графы очереди» применительно к файлу EXAMPLE1.QUE.

На этом рисунке приведены 4 вида графиков:

Форма гистограммы обсуждается подробнее в пункте «Гистограммы» этого же раздела.



Зависимости

Методы анализа файла с расширением RES можно разделить на две группы: построение зависимостей и построение гистограмм. Построение зависимостей выполняется в три этапа:

• выбор формы представления графика зависимости.

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



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

Рис. 2.18 иллюстрирует разметку файла GAS.RES (рис. 2.13) для построения зависимости переменной N от модельного времени clock, а рис. 2.19 – график этой зависимости, построенный с помощью метода «Линейчатый граф» (Bar Graph) меню Анализ.





Оформление графика реализуется методами «Шкала графика» и «Заголовки графика» (Graph Scale, Graph Titles) меню Анализ.

Гистограммы

Гистограмма (Frequency Distribution) – это особый вид графика, для разметки которого указывается только одна горизонтальная ось (ось абсцисс). Столбец файла, используемый для определения такой оси, сортируется:

После этого в процессе сортировки подсчитывается количество значений Li, i = 1 + Int, попадающих в каждый из таких интервалов. Подсчитанные таким образом величины Li выводятся на вертикальную ось графика гистограммы. Гистограмма интерпретируется обычно как показатель эффективности использования того или иного оборудования в течение определенного интервала времени. Например, рис. 2.20 представляет гистограмму переменной Status, определяющей состояние бензоколонки в течение всего периода моделирования (1440 мин. = 1сутки). Эта переменная может принимать в модели только два значения: 1 (занята) и 0 (свободна).



Гистограмма представлена двумя столбиками: высота первого определяется количеством нулей в столбце Status файла GAS.RES, а высота второго – количеством единиц в том же столбце. Анализ этого графика наглядно показывает, что бензоколонка в течение суток простаивает менее 4 % времени, что свидетельствует о ее высокой загрузке.

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

Контрольные вопросы и предложения

  1. Из каких элементов строится сетевая структура модели?

  2. Охарактеризуйте понятие переменной и оператора присваивания.

  3. Опишите структуру окна описания переменной.

  4. Охарактеризуйте структуру окна описания задачи. Дайте характеристику основных эффектов.

  5. Охарактеризуйте структуру окна описания очереди.

  6. Охарактеризуйте структуру окна описания разветвителя.

  7. Дайте характеристику элементов управления, связанных с запуском и остановкой модели.

  8. Охарактеризуйте структуру окна описания коллекции регистрируемых переменных.

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

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

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

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

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

  5. Как построить график зависимости между переменными модели по результатам эксперимента, собранным в файле с расширением RES.

  6. Как построить гистограмму значений переменной по результатам эксперимента, собранным в файле с расширением RES.

Развитие концепций: дополнительные методы и средства имитации

Модели потоков в сетевых структурах

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

В общем случае элементом потока может являться
  1   2   3   4   5   6


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации