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

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

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

(ВФ  УГТУ) 
 
 
 
 

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

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

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

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

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

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

                                                                                              шифр:  052130

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

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

                                                                                             Проверил:              _________________

                                                                                                                                                                                                         ( подпись )

                                                                                             _________________________________

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

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

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

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

 

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

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

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

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

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

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

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

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

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