Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Оптимизация работы блока выполнения запросов в автоматизированной информационной системе

ВОРКУТИНСКИЙ ФИЛИАЛ

УХТИНСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО

УНИВЕРСИТЕТА

(ВФ УГТУ)

КУРСОВАЯ РАБОТА № 1

по СИСТЕМНОМУ АНАЛИЗУ И ИСЛЕДОВАНИЙ ОПЕРАЦИЙ

Тема: «ОПТИМИЗАЦИЯ РАБОТЫ БЛОКА ВЫПОЛНЕНИЯ ЗАПРОСОВ В

АВТОМАТИЗИРОВАННОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ»

студента 5 курса, группы АИС – 05

НИКУЛИНА АЛЕКСАНДРА ВИКТОРОВИЧА

шифр: 052130

домашний адрес: 169901, г. Воркута,

ул. Ленина, д. 7а, кв. 32

Проверил: _________________

( подпись )

_________________________________

( Ф.И.О. преподавателя )

Дата проверки _____________ 200__г.

г. Воркута, 2009г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ …………………………………………………………………………………..	3

ПОСТАНОВКА ЗАДАЧИ ………………………………………………………………….	4

ЗАДАНИЕ К КУРСОВОЙ РАБОТЕ ……………………………………………………..	7

РЕШЕНИЕ ЗАДАНИЯ ……………………………………………………………………..	9

1 ЭТАП ………………………………………………………………………………..	9

2 ЭТАП ………………………………………………………………………………..	14

3 ЭТАП ………………………………………………………………………………..	15

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА ………………………………………………………..	17

ВВЕДЕНИЕ

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

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

Что это означает?

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

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

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

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

ПОСТАНОВКА ЗАДАЧИ

1. Оптимизация программы "диспетчер-кодировщик" в блоке предварительной обработки запросов

В некоторой автоматизированной информационной системе (АИС) поток запросов представляет собой последовательность "пачек" информации, каждая объемом Н байт. Эта информация направляется вначале в блок предварительной обработки, попадая в пять независимых модулей А1, А2, А3, А4, А5, и распределяется между ними в количествах а₁, а₂, а₃, а₄ и а₅ байт соответственно (а₁ + а₂ + ... + а₅ = Н). После использования в блоках А1 - А5 каждая пачка информации специальной программой "диспетчер-кодировщик" (ДК) направляется в другую группу модулей В1, В2, В3, В4, В5 так, чтобы в каждый из этих модулей попало ровно b₁, b₂, b₃, b₄ и b₅ байт информации соответственно (b₁ + b₂ + ... + b₅ = H).

На рисунке показан один из возможных вариантов распределения информации между модулями типа А и модулями типа В.

Блок предварительной обработки запросов

Прежде чем направить какую-то часть информации из модуля Аi в модуль Вj, программа ДК перекодирует ее, затрачивая время с_ij на перекодировку одного байта информации. Передача (с предварительной кодировкой) информации от модулей группы А к модулям группы В происходит последовательно: сначала от модуля А1 к какому-то модулю группы В, затем к другому модулю той же группы и так до тех пор, пока А1 не очистится; далее точно так же освобождается от своего запаса информации модуль А2 и так до тех пор, пока все пять модулей группы А не очистятся.

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

2. Определение характера и интенсивности информационного потока, поступающего на вход блока выполнения запросов

После использования в модулях В1 - В5 (определение характера запросов, их сортировка по трудоемкости выполнения, регистрация и т.д.) вся информация направляется единым потоком (пуассоновский стационарный поток интенсивностью l) в блок выполнения запросов БВЗ

Каждая пачка формируется из k последовательных сигналов, появляющихся в пределах отрезка времени Y в случайные моменты, равномерно распределенные на интервале времени (0, Y). Между этими сигналами установлена определенная "дисциплина ожидания", а именно: сигнал, пришедший первым, ожидает последнего в течение времени u (u < Y) и если k-тый сигнал приходит вовремя, пачка формируется. Если же после прихода первого сигнала и до прихода последнего проходит время, большее, чем u, первый сигнал "уходит" и вся пачка теряется, не доходя до БВЗ.

Необходимо определить характер и интенсивность потока информационных пачек, достигающих БВЗ.

3. Оптимизация работы БВЗ

Блок выполнения запросов состоит из N независимых друг от друга, равнодоступных для потока запросов модулей. Каждый модуль при получении запроса выполняет его в течение случайного времени, имеющего показательное распределение со средним значением Т.

Запрос, заставший все модули занятыми, встает в очередь при условии, что в ней находится не более m ожидающих обслуживания запросов; в противном случае запрос теряется ("отказывается от обслуживания"). Для фирмы, эксплуатирующей АИС, такие ситуации (потеря запроса) при многократном их повторении чреваты в будущем потерей заказчика, вероятность которой пропорциональна вероятности отказа от обслуживания запроса Ротк.

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

С учетом всех указанных обстоятельств, совокупный средний доход в единицу времени D от эксплуатации АИС может быть записан в количественном виде следующей формулой: D = (d - e₁ * Wсист) * A - e₂ * n^3/2, где: d - доход, который приносит фирме один выполненный запрос; e₁ - штраф за единицу времени обслуживания одного запроса; Wсист - среднее время пребывания запроса в АИС; A - абсолютная пропускная способность блока выполнения запросов (среднее число выполняемых запросов в единицу времени); e₂ - убытки от неучастия в течение единицы времени одного модуля БВЗ в выполнении вспомогательных операций; n - количество модулей БВЗ, непосредственно занятых выполнением запросов

Необходимо выбрать оптимальное количество n_опт модулей БВЗ, предназначенных для непосредственного выполнения запросов, приняв во внимание одновременно два критерия оптимальности (направление оптимизации по обоим критериям - максимизация):

1) D - средний доход в единицу времени от эксплуатации АИС

2) Q - относительную пропускную способность АИС (среднюю долю выполняемых запросов) с весами (коэффициентами относительной важности) r_D и r_Q соответственно (r_D + r_Q = 1).

ЗАДАНИЕ К КУРСОВОЙ РАБОТЕ:

Как следует из постановки задачи, она состоит из трех частей и, следовательно, решение задачи необходимо провести в три этапа.

1. Первый этап

На первом этапе следует:

Формализовать работу блока предварительной обработки запросов как детерминированную модель транспортной задачи линейного программирования, где роль "поставщиков" играют модули А1 - А5 с запасами информации а₁ - а₅, а роль "потребителей" - модули В1 - В5 с потребностями b₁ - b₅ соответственно.
Одним из известных методов (северо-западного угла, минимального элемента, аппроксимации Фогеля ), а именно тем, который даст план меньшей стоимости, определить начальный опорный план.
Методом потенциалов найти оптимальное распределение информации от модулей группы А к модулям группы B.

2. Второй этап

На втором этапе необходимо:

2.1.Найти вероятность потери информационной пачки по пути ее следования от блока предварительной обработки запросов к блоку выполнения запросов.

2.2. Определить характер и интенсивность потока запросов, поступающих на вход БВЗ.

3 Третий этап

На третьем этапе следует:

3.1. Рассмотреть БВЗ как систему массового обслуживания типа M/M/n с ограничением по длине очереди, то есть как n-канальную СМО (канал - это модуль блока БВЗ) с простейшим потоком заявок (заявка - это запрос) и показательным законом обслуживания заявки.

3.2. Полагая количество модулей, занятых обслуживанием запросов в БВЗ, n = 1, 2, ... , N, для каждого из этих N вариантов рассчитать средний доход в единицу времени D от эксплуатации АИС и относительную пропускную способность АИС Q, рассматривая в дальнейшем параметры D и Q как компоненты векторного критерия оптимальности W = (D, Q), а пару D(n), Q(n) для каждого n как допустимое решение.

3.3. В множестве допустимых решений выделить паретооптимальное подмножество П.

3.4. Если множество П окажется одноэлементным, то значение n = n_опт, соответствующее этому единственному элементу, и будет искомым оптимальным решением. Если множество П содержит более одного элемента, необходимо, применив два различных метода скаляризации векторного критерия W (метод идеальной точки и линейную свертку), с учетом весовых коэффициентов r_D и r_Q, получить для каждого элемента множества П значение скалярного критерия оптимальности S, для удобства заменив вначале в координатной записи W параметр D на D/Dmax, где Dmax - наибольший доход среди всех паретооптимальных решений.

Применение ЭВМ и программных средств

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

Вероятность потери информационной пачки R и параметры D(n) и Q(n) системы массового обслуживания для различных значений n (n = 1, ... , N) следует рассчитывать программным путем.

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

РЕШЕНИЕ ЗАДАНИЯ:

№ Варианта = 5

Первый этап

1.1.

Из магического квадрата 5х5 находим данные с запасами информации а₁ - а₅ и потребностями b₁ - b₅ соответственно. Отсюда получим следующие значения:

а₁ = 9; а₂ = 21; а₃ = 13; а₄ = 5; а₅ = 17;

b₁ = 24; b₂ = 12; b₃ = 5; b₄ = 18; b₅ = 6.

Из полученных данных построим таблицу затрат времени с_ij на перекодировку и передачу единицы информации от блока Аi к блоку Bj из соответствующих элементов квадрата g_ij по формуле: c_ij = (g_ij + f₁(No)*) x 10^-3 сек, где f₁(No)* - номер варианта.

Для определения начального опорного плана решим данную транспортную задачу тремя методами ( северо - западного угла, минимального элемента и аппроксимации Фогеля ), сравним полученные результаты и найдём наименьший.

Метод «северо – западного угла»

При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов запаса и первый из оставшихся пунктов потребности. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x11 (“северо-западный угол”) и заканчивается для неизвестного xmn, т. е. идет как бы по диагонали таблицы с севера на запад.

W₁ = 9*8 + 15*25 + 6*13 + 6*30 + 5*18 +

+ 2*6 + 5*23 + 11*15 + 6*28 = 1255

Метод «минимального элемента»

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

W₂ = 9*8 + 15*25 + 6*7 + 13*6 + 5*10 +

+ 12*9 + 5*15 = 800

Метод «аппроксимации Фогеля»

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

W₃ = 9*8 + 10*25 + 5*19 +

+ 6*7 + 13*6 + 5*10 +

+ 5*16 + 12*9 = 775

Сравним полученные результаты W_1, W₂иW_3, результат с наименьшим числом и есть начальный опорный план. W₃ = 775

Начальный опорный план = 775 сек^-3

1.3. Методом потенциалов найдём оптимальное распределение информации от модулей группы А к модулям группы B.

Общий принцип определение оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана. Для определения опорного плана транспортной задачи будем пользоваться одним из методов, рассмотренных выше. Эти методы гарантируют получение m+n-1 занятых клеток в исходной таблице условий, причем в некоторых из них могут стоять нули. Полученный таким образом план следует проверить на оптимальность.

Для каждой базисной переменной должно выполняться следующее условие а_i + b_j = c_ij составляется системные уравнение и решая её находится потенциал. Так как переменных в системе больше уровней, то обычно а₁ = 0

a₁ + b₁ = 8 если a₁ = 0 , то b₁ = 8;

a₂ + b₁ = 25 a₂ = 17; b₂ = 1;

a₂ + b₄ = 19 a₃ = 4 ; b₃ = 5;

a₂ + b₅ = 7 a₄ = 5 ; b₄ = 2;

a₃ + b₄ = 6 a₅ = 8 ; b₅ = -10

a₄ + b₃ = 10

a₅ + b₁ = 16

a₅ + b₂ = 9

Для каждой небазисной переменной находим значение по следующей формуле х_ij = а_i + b_j - c_ijЕсли среди чисел х_ij нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки х_ij>0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых х_ij>0, и среди данных чисел выбирают максимальное. Клетку, которой соответствует это число, следует заполнить.

х₁₂ = 0 + 1 – 21 = -20

х₁₃ = 0 + 5 – 14 = -9

х₁₄ = 0 + 2 – 27 = -25

х₁₅ = 0 – 10 – 20 = -30

х₂₂ = 17 + 1 – 13 = 5

х₂₃ = 17 + 5 – 26 = -4

х₃₁ = 4 + 8 – 12 = 0

х₃₂ = 4 + 1 – 30 = -25

х₃₃ = 4 + 5 – 18 = -9

х₃₅ = 4 – 10 – 24 = -30

х₄₁ = 5 + 8 – 29 = -16

х₄₂ = 5 + 1 – 17 = -11

х₄₄ = 5 + 2 – 23 = -16

х₄₅ = 5 – 10 – 11 = -16

х₅₃ = 8 + 5 – 22 = -9

х₅₄ = 8 + 2 – 15 = -5

х₅₅ = 8 – 10 – 28 = -30

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

W = 9*8 + 10*13 + 5*19 + 6*7 + 13*6 +

+ 5*10 + 15*16 + 2*9 = 725

Снова выполним перерасчёт полученных результатов, используя метод потенциалов

Для каждой базисной переменной:

a₁ + b₁ = 8 если a₁ = 0 , то b₁ = 8;

a₂ + b₂ = 13 a₂ = 12; b₂ = 1;

a₂ + b₄ = 19 a₃ = -1; b₃ = 5;

a₂ + b₅ = 7 a₄ = 5 ; b₄ = 7;

a₃ + b₄ = 6 a₅ = 8 ; b₅ = -5

a₄ + b₃ = 10

a₅ + b₁ = 16

a₅ + b₂ = 9

Для каждой небазисной переменной:

х₁₂ = 0 + 1 – 21 = -20

х₁₃ = 0 + 5 – 14 = -9

х₁₄ = 0 + 7 – 27 = -20

х₁₅ = 0 – 5 – 20 = -25

х₂₁ = 12 + 8 – 25 = -5

х₂₃ = 12 + 5 – 26 = -9

х₃₁ = -1 + 8 – 12 = -5

х₃₂ = -1 + 1 – 30 = -30

х₃₃ = -1 + 5 – 18 = -14

х₃₅ = -1 – 5 – 24 = -30

х₄₁ = 5 + 8 – 29 = -16

х₄₂ = 5 + 1 – 17 = -11

х₄₄ = 5 + 7 – 23 = -11

х₄₅ = 5 – 5 – 11 = -11

х₅₃ = 8 + 5 – 22 = -9

х₅₄ = 8 + 7 – 15 = 0

х₅₅ = 8 – 5 – 28 = -31

Все числа отрицательны, значит найдено оптимальное решение распределение информации от модулей группы А к модулям группы B. = 725 сек^-3

Схема передачи информации от модулей группы А к модулям группы B блока предварительной обработки запросов выглядит следующим образом:

Второй этап

Исходные данные для решения данного этапа задания:

λ = 100 сек^-1;

k = 10;

U/Y = 0,93 + f₂( № )* ; где f₂( № )* = 1/10( №+1 ), где № - номер варианта.

2.1.

f₂( № )* = 1/10( 5+1 ) = 0,017

U/Y = 0,93 + 0,017 = 0,947

Используя формулу q = k (( U/Y )^k-1 * ( 1 – ( k-1/k ) * U/Y ) найдём вероятности формирования информационной пачки:

q = k (( U/Y )^k-1 * ( 1 – ( k-1/k ) * U/Y ) = 10 ((0,947)^10-1 * (1-(10-1/10) * 0,947 ) =

= 10 (0,613 * 0,1 * 0,947 ) = 0,581

Используя формулу Р = 1 – q найдём вероятность потери информационной пачки:

Р = 1 – q = 1 – 0,581 = 0,419

2.2.

Используя формулу λ₁ = Р * λ найдём характер и интенсивность потока запросов, поступающих на вход БВЗ:

λ₁ = Р * λ = 0,419 * 100 сек^-1 = 41,9 сек^-1

Третий этап

Исходные данные для решения данного этапа задания:

d = 100 + f₃( № )* ( руб. ), где f₃( № )* = № * N, где № - номер варианта

e₁ = 1000 + f₃( № )* ( руб./сек )

e₂ = 50 + f₃( № )* ( руб./сек )

T = 0,08 сек.

n = 10

m = 3

r_D = 0,5 + f₄( № )*, где f₄( № )* = 1/5( №+1 ), где № - номер варианта.

r_Q = 1 - r_D

3.1.

Используя следующие формулы сделаем расчёты в таблице Excel:

μ =	1	Интенсивность потока заявок обслуживаемых 1 каналом
	T

P =	λ₁
	μ

Xn =	P	где n = 1; 2: . . . . 10
	n

Po = ( 1 +	Р¹	+	Р²	+ . . . . +	Рⁿ	)	-1
	1i		2i		ni

Pk =	Р^k	где k = 1; 2; . . . .n
	ki

Pn+r =	Р^n+r	Po	где r = 1; 2; . . . . m
	n^r ni

Вероятность отказа: Р_отк = Р_n+m

Относительная пропускная способность: Q = 1 - P_n+m

Абсолютная пропускная способность: А = l₁Q

Среднее число занятых каналов:

Средняя длина очереди: L_сист = L_оч +

По формулам Литтла:

3.2.

Используя следующие формулы сделаем расчёты для D и Q в таблице Excel:

D = (d - e₁ * Wсист) * A - e₂ * n^3/2, где

d = 150 руб.

е₁ = 1050 руб./сек.

е₂ = 100 руб./сек.

Q = 1 – P_10+m

3.3.

На базе полученных данных D и Q построим график паретооптимальных подмножеств по которому сможем выделить максимально – эффективный метод использования схемы передачи данных.

Из данного графика видно что точка «1» является самой оптимальной, отсюда получим, что оптимальное количество n_опт модулей БВЗ = 1.

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА:

Казаков А.В. Системный анализ управления. - Барнаул, 1997. - 107 с.

Люблинский Р.Н., Оскорбин Н.М. Методы декомпозиции при оптимальном управлении непрерывными производствами. - Томск: Красное знамя, 1979. - 218 с.

Спицнадель В.Н. Основы системного анализа: Учебное пособие. - СПб.: Изд. дом "Бизнес-пресса", 2000. - 326 с.

Оптимизация работы блока выполнения запросов в автоматизированной информационной системе 📙 Курсовая → 🆔 150459