Курсовые работы по информатике
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Кафедра Кибернетики и Вычислительной Техники

Пояснительная записка к курсовому проекту по дисциплине «Теория систем» на тему: «Исследование вычислительных систем неоднородной структуры».

 

Содержание.

 

Введение………………………………………………………………………………………….2

1. Постановка задачи…………………………………………………………………...............3

2. Разработка имитационной модели………………………………………………………..4

3. Проверка адекватности модели…………………………………………………………..5

4. Изучение влияния параметров на критерии качества моделируемой системы…….6

5. Оценка погрешности имитации, обусловленная наличием в ИМ генераторов псевдослучайных чисел…………………………………………………………………...8

6. Определение длительности переходного процесса………………………………………9

7. Статистическая оценка устойчивости и чувствительности имитационной модели к изменению параметров……………………………………………………………11

7. 1 Оценка устойчивости ……………………………………………………………..11

7.2 Оценка чувствительности………………………………………………………...11

8. Численные методы многопараметрической оптимизации…………………………..14

8.1 Постановка задачи…………………………………………………………………14

8.2 Аналитический метод…………………………………………………………….14

8.3 Нулевого порядка: поиска по симплексу………………………………………….15

8.4 Метод первого порядка: наискорейшего спуска (Коши)………………………18

8.5 Методы второго порядка Ньютона……………………………………………..20

Заключение……………………………………………………………………………………21

Список литературы…………………………………………………………………………..22

 

Введение

 

В жизни равно как и в научной деятельности появляются такие ситуации, которые необходимо или хотелось бы повторить. Однако не всегда повторение опыта «в живую» является возможным, бывают ситуации, когда опыт является довольно дорогостоящим, но все-таки нам необходимо замерить или оценить какие-либо параметры, присущие этому опыту. Именно тут нам на выручку приходит имитационное моделирование. Качество моделирования напрямую зависит от тщательности проработки всех деталей моделирования и от сложности моделируемого объекта. Например, если моделировать процесс обслуживания клиентов в банке, недостаточно просто учесть количество окошек для выдачи/приема денег, необходимо иметь в виду огромное количество других параметров, таких, например, как скорость доставки денег из хранилища, сложность различных видов банковских операций, возможность нахождения большого количества людей в помещении и т. д. Даже получив результат нельзя сказать, что работа закончена. Немаловажную роль в процессе моделирования играет статистическая оценка полученных параметров, т. к. от качества оценки зависят рекомендации по устранению тех или иных проблем. Обобщая можно сказать, что процесс моделирования является довольно многогранным и неоднозначным и зависит в первую очередь от способностей разработчика.

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

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

1.  Постановка задачи.

На рисунке 1 представлена структурная схема системы массового обслуживания (далее СМО). В систему поступает простейший поток заявок со средним временем поступления заявок, равным 10 минут. Времена обработки заявок в системе распределены экспоненциально со средним временем обработки для прибора A – 25, для B – 7 минут. Вероятности переходов указаны на схеме.

Рисунок 1 – схема моделируемой системы

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

- разработать имитационную модель системы;

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

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

- определить длительность переходного процесса;

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

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

 

2. Разработка имитационной модели.

Для разработки имитационной модели использована система General Purpose Simulation System (GPSS), так как в настоящее время она является одним из наиболее эффективных и распространенных программных средств моделирования сложных систем на ЭВМ и успешно используется для моделирования систем, формализуемых в виде систем массового обслуживания. Сбор информации осуществляется при помощи статистических объектов GPSS и табличных данных.

Ниже приведен текст программы на GPSS моделирования работы СМО

EXPON FUNCTION RN1,C24

0,0/.1,.104/.2,.222/.3,.355/.4,.509/.5,.69/

.6,.915/.7,1.2/.75,1.38/.8,1.6/.84,1.83/.88,2.12/

.9,2.3/.92,2.52/.94,2.81/.95,2.99/.96,3.2/.97,3.5/

.98,3.9/.99,4.6/.995,5.3/.998,6.2/.999,7.0/.9997,8.0/

AA STORAGE 3

GENERATE 10,FN$EXPON

QUEUE OCH1

ENTER AA

DEPART OCH1

ADVANCE 25,FN$EXPON

LEAVE AA

MET1 QUEUE OCH2

SEIZE B

DEPART OCH2

ADVANCE 7,FN$EXPON

RELEASE B

TRANSFER 0.1,,MET1

TIME TABLE M1,20,10,15

TABULATE TIME

TERMINATE 1

START 100

3. Проверка адекватности модели

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

 

Реальная система

Моделируемая система

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

Загрузка А

Загрузка В

Загрузка А

Загрузка В

10

0.852

0.764

0.854

0.767

15

0.509

0.389

0.511

0.386

20

0.380

0.339

0.382

0.336

25

0.29

0.256

0.287

0.261

30

0.283

0.215

0.288

0.212

35

0.209

0.150

0.206

0.154

40

0.175

0.128

0.176

0.127

50

0.183

0.165

0.188

0.163

55

0.167

0.147

0.170

0.151

65

0.130

0.139

0.133

0.143

85

0.103

0.107

0.100

0.103

Так как отклик реальной системы близок к отклику моделируемой системы, то можно сделать вывод об адекватности моделируемой системы.

4. Изучение влияния параметров на критерии качества моделируемой системы

Критерии качества моделируемой СМО: загрузка СМО (приборов A, В), пропускная способность прибора A и В, среднее время обработки одной заявки в приборе A, В

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

Прибор A

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

Пропускная способность

Загрузка

10

115

0.854

15

105

0.511

20

102

0.382

25

100

0.287

30

101

0.288

35

102

0.206

40

102

0.176

50

101

0.188

55

100

0.170

65

101

0.133

85

100

0.100

Прибор В

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

Пропускная способность

Загрузка

10

118

0.767

15

109

0.386

20

115

0.336

25

112

0.261

30

111

0.212

35

110

0.154

40

114

0.127

50

110

0.163

55

110

0.151

65

113

0.143

85

115

0.103

 

Ср. время обработки заявок

Ср. время

обработки

заявки прибором А

Ср. время

обработки

заявки прибором В

10

1.282

9.297

15

1.711

14.240

20

2.040

18.070

25

2.257

25.367

30

2.983

29.782

35

2.988

36.155

40

2.989

37.357

50

2.991

46.619

55

2.993

57.538

65

2.993

58.731

 

5. Оценка погрешности имитации, обусловленная наличием в ИМ генераторов псевдослучайных чисел

Погрешность имитации обусловлена наличием в имитационной модели генератора псевдослучайных чисел. Определим погрешность для загрузки прибора A. Организуется 10 прогонов модели в системе с 8 генераторами. Полученные значения зафиксированы в таблице 1:

Таблица 1

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

Rn1

Rn2

Rn3

Rn4

Rn5

Rn6

Rn7

Rn8

Yn

Dn

1

10

0.854

0.804

0.693

0.712

0.694

0.830

0.650

0.745

0.748

0.005

2

20

0.382

0.483

0.499

0.336

0.383

0.464

0.371

0.508

0.428

0.0045

3

30

0.288

0.310

0.327

0.278

0.295

0.281

0.231

0.316

0.291

0.0009

4

40

0.176

0.242

0.260

0.263

0.169

0.237

0.200

0.212

0.220

0.0014

5

50

0.188

0.207

0.191

0.198

0.148

0.182

0.181

0.177

0.184

0.003

6

60

0.136

0.172

0.164

0.162

0.128

0.160

0.163

0.152

0.155

0.0002

7

70

0.129

0.128

0.148

0.139

0.122

0.156

0.116

0.135

0.134

0.0002

8

80

0.113

0.108

0.131

0.125

0.106

0.137

0.112

0.117

0.119

0.0001

9

90

0.094

0.105

0.120

0.114

0.097

0.116

0.095

0.104

0.106

0.0001

10

100

0.082

0.095

0.109

0.098

0.087

0.095

0.082

0.097

0.093

0.0008

Определим оценки математического ожидания и дисперсии для каждого прибора по формулам:

где N2 – число опытов,

Ynk – отклик модели по n-той компоненте для k-того опыта (n=1,..,8, k=1,..,10).

Задавшись уровнем значимости a =0,05, можно с вероятностью 0,95 утверждать, что истинное значение Ynи лежит в пределах

,

где t0,05 - значение t-статистики, определяемое при (N-1) степенях свободы и уровне значимости a =0,05 .

Доверительный интервал для среднего значения n-й компоненты вектора отклика (при N=10 и a=0,05) можно записать в виде

.

Определим

Значение dn и определяет погрешность n-й компоненты отклика модели. Затем из всех dn находят максимальное значение, которое в данном случае и будет верхней границей погрешности, связанной с использованием в ИМ генераторов случайных величин:

6. Определение длительности переходного процесса

В качестве контролируемого параметра выбирается загрузка СМО (приборов A, В), длины очередей Och1 и Och2. Проводится моделирование системы с шагом =100, результаты приведены в таблице 2.

Таблица 2.

Длина очереди Och1

Загрузка A

Длина очереди Och2

Загрузка B

 

100

0.303

0.762

0.056

0.374

200

0.152

0.654

0.101

0.478

300

0.182

0.723

0.279

0.542

400

0.136

0.659

0.762

0.643

500

0.180

0.686

0.683

0.612

600

0.946

0.738

0.782

0.676

700

1.154

0.775

0.823

0.697

800

1.172

0.799

1.400

0.735

900

1.647

0.822

2.009

0.751

1000

2.226

0.839

1.827

0.735

1100

2.677

0.853

1.900

0.748

1200

2.603

0.855

2.553

0.769

1300

2.798

0.866

3.109

0.787

1400

2.688

0.861

3.644

0.802

1500

2.990

0.871

4.034

0.816

1600

3.279

0.879

4.389

0.827

1700

3.514

0.886

4.827

0.837

1800

3.679

0.892

5.408

0.846

1900

3.674

0.895

5.972

0.854

2000

3.514

0.898

6.562

0.862

2100

3.372

0.887

6.789

0.868

2200

3.408

0.892

6.782

0.874

2300

3.518

0.897

6.549

0.880

2400

3.575

0.901

6.312

0.884

2500

3.453

0.899

6.080

0.874

2600

3.331

0.892

5.862

0.865

2700

3.226

0.889

5.674

0.851

2800

3.111

0.872

5.545

0.857

2900

3.040

0.869

5.364

0.844

3000

3.115

0.873

5.187

0.824

3100

3.197

0.878

5.117

0.828

3200

3.195

0.881

5.147

0.833

3300

3.255

0.884

5.058

0.836

3400

3.267

0.888

4.922

0.828

3500

3.385

0.891

4.802

0.819

3600

3.422

0.894

4.693

0.815

3700

3.383

0.893

4.664

0.820

3800

3.497

0.896

4.621

0.824

3900

3.447

0.899

4.526

0.822

4000

3.493

0.901

4.417

0.812

График 1. - Переходный процесс

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

7. Статистическая оценка устойчивости и чувствительности имитационной модели к изменению параметров

7. 1 Оценка устойчивости

При статистической оценке устойчивости имитационной модели будем анализировать изменение загрузки устройств от времени моделирования. Результаты моделирования приведены в таблице 3:

Таблица3.

Загрузка A

Загрузка B

5000

0.919

0.815

5100

0.921

0.811

5200

0.919

0.813

5300

0.913

0.813

5400

0.914

0.804

5500

0.914

0.805

5600

0.907

0.808

5700

0.904

0.799

5800

0.906

0.796

5900

0.907

0.799

Загрузка (средняя) прибора А=0.912

Загрузка (средняя) прибора В=0.806

Модель находится в устойчивом состоянии, так как разброс значений невелик.

7.2 Оценка чувствительности

Вектор параметров : времена обработок заявок на устройстве А – t(A), интенсивность поступления заявок.

Вектор отклика Y (по прибору А): загрузка СМО (А)

Вектор отклика Y (по прибору В): загрузка СМО (В)

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

№ п/п

t(A)

Загрузка (А)

Загрузка (В)

1

2

0.079

0.787

2

4

0.222

0.631

3

6

0.310

0.621

4

8

0.353

0.687

5

10

0.428

0.664

6

12

0.478

0.640

7

14

0.627

0.377

8

16

0.751

0.351

9

18

0.784

0.494

10

20

0.760

0.075

График 2.- Зависимость загрузки от времени обслуживания прибором А

№ п/п

Интенсивность поступления заявок

Загрузка (А)

Загрузка (В)

1

10

0.762

0.374

2

20

0.565

0.260

3

30

0.449

0.033

4

35

0.360

0.008

5

40

0.278

0.008

6

45

0.232

0.008

7

50

0.217

0.008

8

55

0.201

0.008

9

60

0.186

0.008

10

65

0.171

0.008

График 3.- Зависимость загрузки от интенсивности поступления заявок в систему

(minXq, maxXq) – интервал изменения q-й компоненты вектора X.

(minY, maxY) – отклики модели, где minY и maxY означают соответственно векторы отклика, полученные при минимальном и максимальном значениях q-й компоненты вектора X.

Приращение q-й компоненты вектора параметров модели вычисляется по формуле:

,

которое и будет приращением вектора параметров X при изменении только одной компоненты q. Затем находится приращение n-й компоненты вектора отклика:

.

Изменения вектора отклика выбирается как . Полученные значения зафиксированы в таблице:

,%

,%

,%

164

163

165

147

127

192

 

8. Численные методы многопараметрической оптимизации

 

8.1 Постановка задачи.

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

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

- аналитический;

- метод Ньютона;

- метод Коши;

- поиск по симплексу.

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

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

8.2 Аналитический метод.

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

Исходная функция .

Найдем =>

Найдем =>

Получаем систему уравнений:

Получаем Х {2,7}.

В результате.

 

8.3 Метод нулевого порядка: поиска по симплексу.

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

Для поиска очередной вершины используются формулы

,

где

x1i-1 – базовая точка.

и

где

N – число переменных, находящихся в функции;

α –масштабирующий множитель, выбрано значение.

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

Зададим значение

Тогда получим решение в результате 20 итераций

и

Зададим значение

Тогда

и соответственно получим решение в результате 50 итераций

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

В точке (1,226;7,307) функция достигает минимума: f(1,226;7,307) = 0,694.

Представим решение графически

8.4 Метод первого порядка: наискорейшего спуска (Коши).

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

Для нахождения координаты следующей точки используется формула:

, где

Xi – это новые координаты

Xi+1 – координаты на текущем шаге

α – длина шага поиска вдоль направления Si-1

Si-1 – вектор, задающий направление

Проделаем несколько итераций вручную:

Искомая функция ;

начальная точка [-1, -1];

из предыдущих методов возьмем значения градиента

И частные производные:

пусть α =0.1.

Отсюда

1)

2)

3)

Как видно, на каждой итерации значение целевой функции уменьшается. В конечном итоге функция достигает минимума на n-ом шаге. Пример программной реализации данного метода в среде MathCad приведен ниже.

В точке (1,894;6,719) функция с допустимой точностью достигает минимума: f(1,894;6,719) = 0,09.

 

 

 

 

 

 

8.5 Метод второго порядка: Ньютона.

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

Из предыдущего метода возьмем частные производные.

, тогда градиент будет равен:

.

Подставим начальные значения [-1, -1]:

.

Найдем :

=>

Определитель матрицы равен 4.

Получаем обратную матрицу :

=>

По формуле найдем значение точки минимума:

=>

В результате.

 

Заключение.

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

Список литературы

1.Разработка САПР. В 10 кн. Кн.9. Имитационное моделирование: Практ. пособие / В. М.Черненький; Под ред. А. В.Петрова. – М.: Высш. шк., 1990.

2.Советов Б. Я., Яковлев С. А. Моделирование систем: Курсовое проектирование: Учеб. пособие для вузов по спец. АСУ. – М.: Высш. шк., 1998.

3.Основы теории вычислительных систем. Под ред. С. А.Майорова. Учеб. пособие для вузов. – М.: Высш. шк., 1978.

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство