Материал: Имитационное и статистическое моделирование — копия

Форма отчёта

Для защиты лабораторной работы необходимо подготовить отчёт, оформить его и передать на проверку в установленном порядке. Файлы, полученные при выполнении работы в Ms Excel (см. рис. 3.17) и в GPSS World, рекомендуется хранить в личном архиве до завершения аттестации по дисциплине «Моделирование систем».

В отчёте необходимо объяснить причины расхождения или близости результатов имитации СеМО и результатов расчёта её системных показателей.

Примечание 2 . Для определения пропускных способностей Ai и Bi путём имитации необходимо проводить специальный эксперимент. Его основная идея состоит в поддержании постоянного наличия некоторого числа внешних заявок на выбранном входе СеМО (например, путём установки пакета из нескольких тысяч заявок) и последующей обработке статистики по «узким местам» СеМО. Определять пропускные способности Ai, Bi и запасы Di путём имитации в вашей работе не требуется (колонку «СпЭксп.», подобную представленной на рис. 3.17, формировать не нужно).

Примечание 3 . Для определения путём имитации среднего времени E пребывания заявок в сети следует все заявки, проходящие через сеть (независимо от числа входных потоков), проводить через очередь general и через блок

TABULATE E_time.

Контрольные вопросы

1.Чем отличаются разомкнутые и замкнутые СеМО?

2.Чем объясняются выступы на хвостах гистограмм на рис. 3.16?

3.Какой из двух показателей (Аi и Вi) в общем случае больше?

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

5.Объясните смысл всех числовых показателей на листе Excel на рис. 3.17.

Лабораторная работа 5 ОПТИМИЗАЦИЯ ОТКРЫТЫХ МАРКОВСКИХ СеМО

Цель работы. Оптимизация открытой марковской СеМО.

Содержание работы:

1.Постановка задачи оптимизации для заданного в лабораторной работе 3 варианта СеМО (теперь СеМО считаем экспоненциальной, т. е. марковской).

2.Определение центра области допустимых решений (ОДР) задачи.

3.Решение задачи на Ms Excel. Расчет эффекта оптимизации.

4.Проверка оптимального решения путем имитационного моделирования.

Краткая теория и методические указания

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

121

т. е.

Фиксированный суммарный ресурс M * определяется как сумма интенсивностей обслуживания всех каналов и в рассматриваемом примере составляет 30:

Теперь, поскольку сеть марковская, можно в явном виде выразить среднее время ответа E (среднее время пребывания заявки в СеМО) через заданные ее параметры и потребовать минимизации E за счет оптимального распределения ресурса M * по узлам сети. Эту оптимизационную задачу можно записать в следующей, состоящей из стандартных частей, форме задачи нелинейного программирования:

i=1

где n = 9, параметры αi перечислены в формуле (3.26), параметры ci – в (3.29), параметры μi min – в (3.28), {pij} – на рис. 3.18, μi являются варьируемыми параметрами, а выражения wi (μi ) для рассматриваемой экспоненциальной СеМО таковы:

вывести из формул (3.6), (3.4) (для одноканальных узлов) и соответствующих формул (3.14), (3.11) и (3.12) (для многоканальных 2-го и 8-го узлов СеМО).

Параметры λi для (3.32) перечислены в формуле (3.27).

Таким образом, задача оптимизации открытой марковской СеМО, представленной на рис. 3.18, сформулирована как задача нелинейного программиро-

123

вания. В задаче требуется отыскать значения (μ1,...,μ9 ), доставляющие мини-

мум функции (3.30), и удовлетворяющие ограничениям (3.31).

2. Пример определения центра ОДР. Область допустимых решений задачи (3.30), (3.31) задана формулами (3.31) и представляет собой кусок n-мерной

плоскости ∑9i=1ci μi =30, координаты μi всех точек которого положительны и ограничены снизу соответствующими константами μi min (3.28).

Центром ОДР назовем принадлежащую ОДР такую точку μc , представ-

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

j=1

Итак, вычисляем центр ОДР:

μc = (μc1,...,μc9 ) = (0,3862, 0,2897, 0,9656, 2,639, 11,39, 0,7918, 1,055, 3,418, 1,931).

3.Пример решения задачи оптимизации СеМО средствами Ms Excel.

Принимая μc в качестве начальной точки, можно, двигаясь из нее каким-либо

градиентным методом, достаточно быстро попасть в искомую точку μopt , дос-

тавляющую минимум целевой функции (3.30). Используя Ms Excel, задачу перехода из μc в μopt можно решить следующим образом.

На листе Excel сформируйте диапазоны данных ci, αi, λi, μi min (неважно, в строках или столбцах). Добавьте диапазон с координатами точки μ : они

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

∑9i=1ciμi . Назовем эту ячейку индикатором суммарного ресурса. Скопируйте

в диапазон координат точки μ координаты точки μc (взятые как значения);

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

Теперь организуем вычисление среднего времени ответа E(μ) . Параллельно диапазону с координатами точки μ добавьте диапазон с формулами, вычисляющими Wi (μi ) , и на одной с ним линии в отдельной ячейке запишите формулу для вычисления E(μ) . Эта ячейка примет значение 10,759.

Лист Excel для решения оптимизационной задачи готов.

Итак, в точке μc , задающей «справедливое» распределение ресурса по узлам нашей СеМО, обеспечивающее равную их загрузку, среднее время ответа E

124

составляет 10,759. Теперь решим задачу оптимизации и проверим, можно ли улучшить E(μ) , отклоняясь от «справедливого» распределения μc .

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

–в микроокне Установить целевую ячейку укажите ячейку, вычисляющую E(μ) ;

–далее выберите в этом диалоговом окне опцию минимальному значе-

нию;

–в боксе Изменяя ячейки укажите диапазон ячеек с координатами точ-

ки μ ;

–в боксе Ограничения нажмите кнопку Добавить и добавьте два ограни-

чения:

1) в появившемся после нажатия кнопки Добавить диалоговом окне сформируйте требование (в виде условия-равенства), что ячейка с суммарным ресурсом (индикатор суммарного ресурса) должна быть равна 30; нажмите мышкой кнопку ОК;

2) в основном диалоговом окне еще раз нажмите кнопку Добавить, в появившемся диалоговом окне в боксе Ссылка на ячейку укажите сразу весь диапазон ячеек с координатами точки μ , затем выберите условие «≥» и в боксе

Ограничение укажите диапазон ячеек с величинами μi min ; нажмите ОК.

Основное диалоговое окно сервиса Поиск решения... готово для решения вашей задачи. Целевая ячейка указана, выбрано требование минимизации, диапазон изменяемых ячеек задан, два ограничения сформированы. Нажмите кнопку Выполнить. Практически мгновенно появится сообщение, что решение найдено. С деталями этого сообщения легко разобраться самостоятельно. Найденное оптимальное решение дает для E(μopt ) значение 7,938, заметно мень-

шее (т. е. лучшее), чем достигаемое в центре ОДР значение E(μc ) = 10,759. Варьируемые параметры – координаты точки μ – в процессе поиска оптимума изменились и приняли оптимальные значения μ = μopt . Сохраните решение. Найденные оптимальные значения координат точки μopt будут нужны при вы-

1,5923, 2,9290, 2,4142). Они заметно отличаются от найденных выше в п. 2 координат центра ОДР μc .

Самостоятельно оцените различие в процентах между E(μc ) и E(μopt ). Вычислите евклидово расстояние между точками μc и μopt .

Построенный только что лист Excel используйте, насколько это возможно, при оптимизации вашего варианта СеМО (выбранного при выполнении работы 3).

4. Пример проверки оптимального решения путем ИМ. Проверку оп-

тимального решения выполним путем ИМ сети при оптимальных интенсивностях обслуживания заявок в ее узлах.

125