автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Задачи стохастической оптимизации параметров эксперимента на примере информационных систем

кандидата физико-математических наук
Шахов, Владимир Владимирович
город
Новосибирск
год
2000
специальность ВАК РФ
05.13.16
цена
450 рублей
Диссертация по информатике, вычислительной технике и управлению на тему «Задачи стохастической оптимизации параметров эксперимента на примере информационных систем»

Автореферат диссертации по теме "Задачи стохастической оптимизации параметров эксперимента на примере информационных систем"

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ

ЗАДАЧИ СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ ПАРАМЕТРОВ ЭКСПЕРИМЕНТА НА ПРИМЕРЕ ИНФОРМАЦИОННЫХ СИСТЕМ

05.13.16 - применение вычислительной техники, математического моделирования, математических методов в научных исследованиях

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

РГ Б ОД

ШАХОВ Владимир Владимирович

* 7 Дпр 2000

Новосибирск, 2000

Работа выполнена на кафедре вычислительных систем механико-математического факультета Новосибирского государственного университета.

Научный руководитель: к.т.н., доцент А.С.Родионов.

Официальные оппоненты: д. ф.-м. н., профессор Г.С. Лбов,

к. ф.-м. н., доцент C.B. Рогазинский.

Ведущая организация: Новосибирский государственный

технический университет

Защита состоится 11 апреля 2000 г. в 15 часов на заседании Специализированного совета Д.002.10.02 в Институте вычислительной математики и математической геофизики СО РАН (630090, Новосибирск, пр-т Акад. Лаврентьева, б).

С диссертацией можно ознакомиться в читальном зале библиотеки ИВМиМГ СО РАН.

Автореферат разослан "

Ж.-. сМ&Ц? Гй 2000 года.

Ученый секретарь диссертационного совета к. ф.-м. н., доцент С.Б.Сорокин

âm. 4> c3-f.es

Общая характеристика работы

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

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

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

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

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

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

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

Методика исследования. Методы данного исследования базируются на известных подходах к формализации ЙС и их имитационном моделировании, методах теории вероятности и математической статистики, планировании эксперимента, регрессионного и математического анализа, исследовании операций. При создании программных средств, для апробации полученных теоретических результатов, использовались языки программирования Simula-67, Modula-2 (Top Speed) и система моделирования СИДМ-2.

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

Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на Третьем Сибирском Конгрессе по Прикладной и Индустриальной Математике (ИНПРИМ-98) посвященном памяти С.Л.Соболева (Новосибирск, 1998 г.), 11-й

Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 1998 г.), Международной конференции "Математическое моделирование и информационные технологии в образовании и науке" (Алматы, Казахстан, 1998 г.), Конференции молодых ученых ИВМ и МГ (Новосибирск, 1999 г.), Международной конференции "Distributed Computer Communication Networks" (Тель-Авив, Израиль, 1999 г.), конференциях молодых ученых ИВМ и МГ (ВЦ) СО РАН (Новосибирск, 1995, 1997, 1999), а также на семинарах под руководством члена-корреспондента РАН Г.А.Михайлова (ИВМ и МГ СО РАН), профессора М.И.Нечепуренко (ИВМ и МГ СО РАН), профессора В.К.Попкова (ИВМ и МГ СО РАН), профессора Б.Ю. Лемешко (НГТУ), семинарах кафедры Теоретической кибернетики НГУ под руководством профессора В.Т.Дементьева (ИМ СО РАН).

Публикации. По материалам диссертации опубликовано 9 печатных работ.

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

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

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

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

ное планирование дискретного регрессионного эксперимента (ОПДЭ), рассмотрен критерий Б-оптимальности, и задача обнаружения разладки в дисциплине обслуживания устройства.

В главе подробно рассмотрены существующие подходы к решению задачи ОПДЭ, обоснована ограниченность их применения. Построен пример с уравнением регрессии т}{х^, д) = хь$ и функцией эффективности А(а^) = е~сх, где е - экспонента, а Ь и с - действительные числа, для которых выполняются неравенства 0 < 6 < 1/2 и с > 2, факторное пространство состоит из целых неотрицательных чисел. В данном случае округление непрерывного оптимального плана до ближайшего целого приводит к дискретному минимуму в точке х = 0, кроме того разность с оптимальным дискретным решением, которое достигается в точке х — 1, с увеличением количества измерений будет сколь угодно большой.

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

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

Обозначим Ф(п,...,гп,Х1,...,жп) = |М(елг)|-

Поскольку количество точек фазового пространства в регрессионных экспериментах с моделями ИС относительно не велико, то будем считать, что спектр плана состоит из всех п точек фазовой области X = {х\,..., хп). Тогда задача планирования состоит в распределении N наблюдений по точкам ж,-, если точка X] не входит в план, то г^ = 0.

Данный подход позволяет рассматривать решаемую проблему как задачу оптимизации только по целочисленным переменным г,-, г = 1,..., п.

В самом деле, стандартная постановка задачи ОПДЭ принимает вид:

Ф(п ...гп) —у max,

А (1)

У ^ п = N, ri > 0, г; - целое.

i=1

Во многих исследованиях, в особенности имитационных экспериментах, заранее задается устраиваемая точность оценок параметров уравнения регрессии 1?. С математической точки зрения это означает, что задано некоторое число Q, такое что Q~x > \D\. Обозначим стоимость наблюдения в г-й точке как а. Проблема состоит в том, чтобы получить оценки с заданной точностью при минимизации стоимости эксперимента, т. е.

п

У с«п —i- min, к (2)

rt > 0, г; — целое.

Возможен случай, когда задан бюджет исследования, обозначим его С. Тогда задача ОПЭ следующая:

Ф —> max,

у] CiTi < С, Ti > О, Г,- - целое. ^ ^

¿=1

В главе введены обозначения:

1т ={1 ,...,т},

J{ = {ji, • • jr- jk € Im;jk ф jr, если к ф г}, l

Sh-h — E^-k—1

Получены следующие результаты.

Теорема 1. В случае однопараметрической модели:

1) решением задачи ОПДЭ вида (1) является план, состоящий из одной точки: ri* = N, i* = Arg max сг-,-

2) решение задачи ОПДЭ вида (2) находится с помощью динамического программирования с трудоемкостью, не превышающей

uQ

тт. а,- ' '

3) решение задачи ОПДЭ вида (3) находится с помощью динамического программирования с трудоемкостью, не выше

О

71-

min с;

Показано, что динамическое программирование можно использовать и в случае моделей с двумя параметрами.

Лемма 1.

т

1=1 Л

Лемма 2. Обозначим

где Р определитель подматрицы тхтп матрицы Р, вектор-столбцов /(атг-[) гу 6 1п\к.

Тогда если

4 > 4, (4)

то в оптимальном плане г; > г^.

Теорема 2. Задача (1) эквивалентна задаче

Пс

У dszY1 —>■ max,

h (5)

Az = Ь, г,- > 0, Zi — целое,

m

где пс = Е Сп, z = (¿1, ■ ■-^nj, b - вектор (N, ...,N) fc=1

размера nc 4- 1, A - матрица (jic -f 1) X nc, a,{j £ {0,1}, i -индекс, нумерует элементы множества (J J\.

1=1 ,...,m

Если i соответствует набору ji,ji, mo di = l- 1Г-' £ ajl,—Jr

Если индексы %i и ii соответствуют наборам ji,...,ji, ■ ■■Jl « jw-Ji, mo zL > zt.

Кроме того, если выполняется неравенство (4), индексы г'/, и ii, где L > /, нумеруют наборы из Jk для некоторого 1 < k < т, то zi <

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

Имеется последовательность независимых одинаково распределенных случайных величин такая что ... ,£t0_i имеют плотность

iV-^27 при х > 0, 0 при х < 0,

a Çt0 » 6o+i » • • • имеют плотность

Г при х >

\ 0 при ж < Ь.

Момент ¿о называется моментом разладки. Разладка считается обнаруженной, если сигнал подается не позднее, чем через Т наблюдений после момента возникновения разладки, т. е. шах{0,<* - ¿о} < Г. В противном случае разладка пропущена. Если решение о наличии разладки принимается в момент £ < ¿о, то имеет место ложная тревога. По условию рассмотренной задачи вероятность объявления ложной тревоги не может превосходить некоторое число а, которое будем называть уровнем ложной тревоги.

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

до =

91п

0; (б) тах^р^+к -^-Нп^-^+Ь^ ), если > Ь,

\ Щ / |

(7)

О,

если £„ < 6;

я1

1/1

тах(0, - + -г- + Ь , если > Ь,

(8)

если £п < Ь.

Правило подачи сигнала о разладки выглядит следующим образом: Г = ¡п^тг > 1 : дп > к}, где Л - некоторое пороговое значение, определение которого, в общем случае, является самостоятельной сложной проблемой, решаемой экспериментально.

Пороговое значение будем называть оптимальным и обозначать /гор);, если для заданных параметров распределения и уровня ложной тревоги а, минимизируется вероятность пропуска разладки. В рассмотренной постановке задачи о разладке удается получить аналитические выражения для /гор(;.

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

для

для д*

0102Ь + (01 - 02) 1П 2 + 1?! 1п ^ < О,

01

0102Ь+(01-02)1П2 4-021П^> 0;

wi

1-1п4 4-^г + 01Ь>О, 02

02

1 - 1п 4 + -г- - 02Ô < 0. 01

С помощью следующих двух лемм: Лемма 3. hopt не зависит от Т и

hopt = inf {h : P-e^ffn > h) < a},

Лемма 4. Случайная величина Sn, равная сумме п независимых случайных величин, распределенных по экспоненциальному закону со сдвигом, имеет следующее распределение:

» е R P(S„ <,)=i-.-*-» £ =

_ Ъ. ( Tt 11«

¿=0

и, соответственно, плотность:

U U) = (*-пЬГ-1Ге-Ч*-пЬ)

(9) (10)

Доказана Теорема 3.

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

;=о г!

где использованы обозначения:

для gl ki = 1, к2 = + j- + Ь

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

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

Обозначим:

1 при > m, О иначе,

/{& > то} = {

п ^

¿п = У2Н&> т], т = Ь + — In 2. ¿=i ^

Разладка объявляется, когда dn > «о, где По - некоторое целое положительное число. Тогда верна

Теорема 4. Справедливо

П\т По

Р(«*г < по|Я2) = Е^т,

где

п0 = тт{г:1-£ - е-^т)Т~к < а

^ к=о

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

В заключении приводятся основные выводы по результатам исследования.

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

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

задач и участие в обсуждении работы. •

Работы автора по теме диссертации

[1] Шахов В.В. Некоторые задачи планирования имитационного эксперимента // Труды конференции молодых ученых ВЦ СО РАН. -Новосибирск, 1995.- С. 200-212.

[2] Шахов В.В. Некоторые задачи планирования имитационного эксперимент // Труды ИВМиМГ. Сер. Системное моделирование. -Новосибирск, 1997, вып. 4(22). - С. 165-174.

[3] Шахов В.В. Анализ системы сбыта в условиях нестабильного спроса // Труды конференции молодых ученых ИВМиМГ СО РАН. - Новосибирск, 1997. - С. 238-245.

[4] Шахов В.В. Вопросы имитационного моделирования // Труды 11-й Байкальской междунар. школы-семинара "Методы оптимизации и их приложения". - 1998. том 3. - С. 191-195.

[5] Шахов В.В. Задачи оптимизации имитационного эксперимента // Материалы междунар. конференции " Математическое моделирование и информационные технологии в образовании и науке". -Алматы, 1998.- С .113.

[6] Шахов В.В. Некоторые задачи оптимизации имитационного эксперимента // Тез. докл. Третьей Сибирского конгресса по прикладной к индустриальной математике. - Новосибирск, 1998, ч. 3. -С. 81.

[7] Шахов В.В., Родионов А.С. О разладке в системах с экспоненциальным распределением // Труды ИВМ и МГ. Сер. Системное моделирование. - 1998, вып. 5(23). - 157-162.

[8] Shakhov V.V. The problems of similation optimization // Bull, of NCC. Special Issue. - 1999. - P. 145-150.

[9] Shakhov V.V., Rodionov A.S. About point-of-change problem in the information systems with exponetial distribution // Proceeding of Digital Computer Commmication Network Conference, Tel-Aviv (Israel). - 1999.-P. 141-145.

Оглавление автор диссертации — кандидата физико-математических наук Шахов, Владимир Владимирович

Введение.

1. Методология исследования ИС

1.1. Задачи исследования информационных систем и методы их решения.

1.2. Особенности планирования экспериментов по изучению ИС.

1.2.1. Роль регрессионного эксперимента в исследовании ИС.

1.2.2. Дискретность моделей ИС.

1.2.3. Основные понятия и обозначения теории планирования оптимального эксперимента.

1.2.4. Обзор алгоритмов ОПДЭ

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

Выводы.*.

2. Планирование экспериментов по изучению ИС.

2.1. Математическая постановка задач.

2.2. О получении точного решения задачи ОПДЭ.

2.2.1. Однопараметрические регрессионные модели.

2.2.2. Модели с двумя параметрами.

2.2.3. Общий случай.

Выводы.

3. Исследование экстремальных ситуаций в ИС с помощью разладки. 41 3.1. Математическая постановка задачи.

3.2. Область допустимого использования АКС.

3.3. Выбор h для заданного уровня пропуска разладки

3.4. Определение разладки по косвенным характеристикам

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

3.4.2. Обнаружение разладки по наблюдению длинны очереди.

3.5. Альтернативный способ обнаружения разладки . 56 Выводы.

4. Экспериментальное исследование предложенных алгоритмов

4.1. Вводные замечания.

4.2. Модель узла коммутации пакетов.

4.3. Модель системы с запросами на установление виртуальных цепей.

4.4. Простейшая модель канала передачи данных

4.5. Исследование поведения порога hopt.

Введение 2000 год, диссертация по информатике, вычислительной технике и управлению, Шахов, Владимир Владимирович

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

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

Статистические методы исследования сложных систем вообще и информационных сетей в частности были развиты в известных научных школах как в России, так и за рубежом. Можно упомянуть следующие фамилии: Авен О.И., Артамонов Г.Т., Башарин Г.П., Бочаров П.П., Беляков В.Г., Турин Н.Н., Калашников В.В., Коган Я.А., Литвинов В.В., Максимей И.В., Марчук Г.И., Мизин И.А., Митрофанов Ю.И., Морозов В.И., Нечепурен-ко М.И., Новиков Г.И., Попков В.К., Харкевич А.Д., Бертсекас Д., Вунш Г., Галлагер Р., Гармаш В.А., Клейнен Дж., Клейнрок JL, Нейлор Т., Саати Т., Феррари Д., Фишман Г.С., Шеннон Р.

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

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

Несмотря на то, что такое научное направление, как планирование эксперимента по поиску математических моделей изучаемых процессов, возникло сравнительно недавно, ему уже посвящено значительное число статей и книг следующих авторов: На-лимова В.В., Черновой Н.А., Клепикова Н.П., Соколова С.Н., Адлера Ю.П., Грановского Ю.В., Горского В.Г., Малютова М.Б., Попова А.А., Хикса Ч., Киефера Д., Карлина С., Стьюдена У., Дрейпера Н. Огромное влияние на автора данной диссертации оказали труды Федорова В.В. и Денисова В.И., обозначения и терминология которых будет использована в дальнейшем изложении.

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

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

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

Задачи исследования

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

2) Анализ существующих приближенных алгоритмов оптимального планирования дискретного регрессионного эксперимента (ОПДРЭ) по исследованию параметров ИС.

3) Разработка методов, позволяющих найти точное решение задачи ОПДЭ.

4) Моделирование экстремальных ситуаций в ИС, исследование процессов нарушения дисциплины обслуживания в СМО.

5) Анализ работоспособности алгоритмов кумулятивных сумм (АКС) при обнаружении разладки для экспоненциального распределения со сдвигом.

6) Исследование пороговых значений в АКС для обнаружения разладки с фиксированной зоной обнаружения.

7) Разработка алгоритмов обнаружения разладки, удобных для практической реализации.

Научная новизна и значимость заключаются в: постановке задач ОПДЭ с учетом специфики исследования ИС и создании метода, позволяющего найти точное решение данных задач с помощью методологии динамического программирования; предложении способа обнаружения аварийных ситуаций в ИС, обусловленных частичной потерей работоспособности; постановке, исследовании и разработке алгоритмов решения задачи о разладке распределения обслуживания с фиксированным временем обнаружения;

Часть результатов по ОПДЭ получены в рамках проекта НИП № 1084 ГНТП"Перспективные информационные технологии".

Исследования процессов экстремального функционирования сети выполнены при поддержке РФФИ, грант 98-01-00721.

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

Основные положения, представляемые к защите

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

2) Инструментарий для обнаружения нештатного состояния узла ИС, обусловленного частичной потерей работоспособности.

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

4) Метод обнаружения разладки, основанный на сравнении наблюдаемых стохастических переменных с медианой их распределения.

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

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

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

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

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

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

В Заключении приводятся основные выводы по результатам исследования.

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

Основные результаты работы:

1) Обоснованна необходимость разработки методов оптимального планирования эксперимента по изучению моделей ИС.

2) Предложен новый метод получения точного решения задач D-оптимального планирования дискретного эксперимента с помощью динамического программирования.

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

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

5) Для проблемы обнаружения разладки, с учетом специфики ИС, получены оптимальные пороговые значения в АКС.

6) В случае невозможности наблюдения непосредственно времени обслуживания предложены методы обнаружения разладки по косвенным характеристикам системы.

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

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

Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на конференции молодых ученых ВЦ СО РАН (Новосибирск, 1995), Третьем Сибирском Конгрессе по Прикладной и Индустриальной Математике (ИНПРИМ-98) посвященном памяти С. JI. Соболева (Новосибирск, 1998 г.), 11-й Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 1998 г.), Международной конференции "Математическое моделирование и информационные технологии в образовании и науке" (Ал-маты, Казахстан, 1998 г.), Конференции молодых ученых ИВМ и МГ (Новосибирск, 1999 г.), Международной конференции "Distributed Computer Communication Networks" (Тель-Авив, Израиль, 1999 г.)

В выполнение работы внес вклад А.С. Родионов, осуществлявший постановку задач исследования, научное руководство и оценку значимости результатов. Совместно с ним сделаны публикации: [17] и [79]

Заключение диссертация на тему "Задачи стохастической оптимизации параметров эксперимента на примере информационных систем"

Выводы

1. С учетом специфики модели ИС поставлена задача о разладке с фиксированной длиной зоны обнаружения.

2. Получены условия, при которых допустимо использование АКС для рассмотренных распределений.

3. Получено выражение для оптимального значения порога в АКС, изучены его свойства.

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

5. Предложен собственный метод обнаружения разладки, более удобный для практического использования.

Глава 4

Экспериментальное исследование предложенных алгоритмов

4.1. Вводные замечания.

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

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

В качестве критерия оптимальности планов выбрал критерий D-оптимальности, соответственно, под оптимальным планом подразумевается локально D-оптимальный план, если специально не оговаривается иная ситуация. Заметим, что оптимальные плалы для большинства регрессионных моделей, рассмотренных в данном разделе, совпадают с А-оптимальными.

Не уменьшая общности будем полагать, что дисперсия наблюдения одинакова во всех точках для всех экспериментов и равна 1.

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

4.2. Модель узла коммутации пакетов

При организации функционирования сетей связи используется способ передачи пакетов с промежуточным накоплением, когда пакет передается по линии связи, используя всю ее пропускную способность, а поступившие позже требования ожидают в очереди (т.н. буфер) освобождения линии. Узел, в который поступают пакеты для дальнейшей передачи по следующей линии к пункту их назначения, называют узлом коммутации пакетов [31].

Для построения модели узла коммутации пакетов удобно воспользоваться СМО вида М/М/1/К, где входной Пуассоновский поток соответствует поступлению пакетов, длительность обслуживания заявки прибором, распределенное по экспоненциальному закону, соответствует времени передачи пакета по линии связи, наибольшее возможное количество заявок в системе К соответствует максимальному количеству пакетов в узле коммутации, т.е. находит отражение тот факт, что в реальной сети связи любой узел коммутации пакетов имеет буфер конечного объема.

Таким образом, если поступающее требование застает в системе К требований (количество пакетов в очереди + передаваемый пакет), то ему отказывается в обслуживании.

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

Согласно [42] для доли отказов имеем следующее уравнение регрессии: где, исходя из практических соображений, переменная количества мест в очереди, которая, здесь, играет роль факторного пространства, принимает значения от 1 до 64.

Обычно, для аналогичных экспериментов используют равномерный план, (замечание по этому поводу есть, например, в [69]), т.е. проводят одинаковое количество измерений во всех точках факторного пространства.

Проведем сравнение для оценок, полученных по равномерному плану и по оптимальному плану, полученному с помощью предложенных выше методов. Будем обозначать р - истинное значение Л параметра, р* - оценка коэффициента использования, полученная по оптимальному плану, р - оценка, полученная по равномерному плану. Одно наблюдение соответствует отношению количества требований, получивших отказ, к общему числу требований, вычисленных за один прогон модели М/М/1/К в течении 100 у.е. модельного времени. Модель реализована на языке Симула-67, ее листинг приводится в приложении.

Эксперименты проводились при нескольких уровнях коэффициента использования:

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

2) среднем (р = 0.5), имеет место при низких темпах роста числа пользователей в эксплуатируемой сети.

3) высоком (р = 0.9), сеть не имеет резерва для наращивания количества пользователей и обслуживания, возможно сезонного, всплеска заявок абонентов.

4) избыточном (р = 1.1 ), ситуация не желательна (возможно технические неисправности оборудования), узел не справляется с обработкой потока пакетов, необходимы срочные меры.

В эксперименте с равномерным планом, проводится по одному наблюдению (у{) в каждой точке факторного пространства (всего 64 наблюдения). В эксперименте с оптимальным планом столько же наблюдений проводятся в единственной точке, определяемой, согласно п. 2.2.1.

Вычислим частную производную:

-dp'-(1 -

Отсюда информационная матрица Фишера для равномерного плана имеет вид:

64

M=Zf2(xiiP)t :'= 1 для оптимального плана:

Mopt - 64 /2(ж,-*,р), где г* = Arg min /2(ж{,р)

Используя результаты п. 1.4 [69] получим формулы для расчета оценок: „ , Dfei(yi~ri(xi*,p)f(xi*)

-щ-• где yi - это г—ое наблюдение, проводимое в точке оптимального плана.

Й1 (У1-ФьрШЪ) р = Р + М где yi - это наблюдение в 2-й точке равномерного плана (наблюдение доли отказов при ограничении на буфер, равном г).

Результаты моделирования, точные значения функции регрессии и другие вычисления приведены в приложении А. Итоги сравнения оценок, полученных по равномерному и по оптимальному плану, продемонстрированы в таблице: р А р Д£ р А p* р Mopt м

0,100 0,163 63,4% 0,102 0,03% 4032

0,500 0,638 27,5% 0,515 0,05% 2092

0,900 1,004 11,5% 0,893 0,01% 279

1,100 0,985 10,5% 1,071 0,04% 88

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

Для большей наглядности приведем графики функций rf(k, р), 7](к,р), г](к, р*), а также графики отношения данных функций и функции регрессии.

Будем сплошной тонкой линией отображать график функции задаваемый уравнением регрессии с истинным значением параметра, т.е. г}(к,р), графики функций г]{к, р), т](к,р*) будем отображать соответственно сплошной толстой линией и пунктиром. Графики функций отношения j^j- и ^ р) расположим на отдельных рисунках. Для конкретных значений указанных функций в приложении имеются таблицы.

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

Более наглядными представляются графики функции отношении, изображенные на рисунках 4,5 из которых видно, что значение функций ч](к, р) и г}(к, р) в процентном отношении отличаются очень сильно, в то время как значения функций г)(к, р* и т}(к, р) близки. В таблице 2 приложения А имеются конкретные данные. Столбец, пронумерованный цифрой 1, содержит значения функции г}(к,р)) цифрой 2 - г](к,р), цифрой 3 - и цифрой 4 чМ п(М '

Оптимальный план, в данном случае, содержится в точке, соответствующем минимально возможному значению буфера к = 1 (см. табл. 1 в приложении А.

Рис. 4. Отношение функций регрессии с р* и р = 0.1

Рис. 6. Функция регрессии, вычисленная для параметра д = 0.5 и его оценок

Рис. 8. Отношение функций регрессии с р и р = 0.5

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

Рис. 9. Функция регрессии, вычисленная для параметра i? = 0.9 и его оценок

Рис. 11. Отношение функций регрессии с р и р = 0.9

Рис. 13. Отношение функций регрессии с р* и р = 1.1

Таким образом показано существенное преимущество оптимальных оценок над равномерными. Заметим, что при значениях параметра 0.9 и 1.1 качество равномерных оценок может считаться приемлемым (до 20 % при нелинейной функции регрессии), но в данном случае, оценки, полученные по равномерному плану, дают неправильное представление о сути процесса - получается, что система не справляется с потоком заявок в первом случае, и справляется во втором, хотя в реальности все наоборот.

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

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

4.3. Модель системы с запросами на установление виртуальных цепей.

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

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

Для уравнения регрессии, соответствующего средней доли потерянных требований, согласно В-формуле Эрланга имеем :

Рт — vm ' п=0 п! где коэффициент р имеет тот же смысл, что и в предыдущем разделе.

Будем полагать, что максимально возможное количество соединений не превосходит 12, р принимает значения 0.1, 1, 2, 3, 4, 5. Техника вычислений плана и оценок такая же как в п.4.2. Для данной модели оптимальный план также дает существенный выйгрыш перед равномерным, что отражено в таблице 9,

Заключение

По результатам работы можно сделать следующие выводы.

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

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

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

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

Библиография Шахов, Владимир Владимирович, диссертация по теме Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)

1. Ashish. Sen, Muni S. Srivastava. On multivariate tests for detecting change in median. - Sankhya, 1973, ser. A, v. 35, №2, p. 173-186.

2. Ashish Sen, Muni S. Srivastava. Some one-sided test for change in level. Technometrics, 1975, v. 17, №1, p. 173-186.

3. Ashish Sen, Muni S. Srivastava. On test for detecting change in mean. Ann. of Stat., 1975, v.3, №1, p. 98 - 108.

4. D.S. van Dobben de Bruyn. Cumulative sum tests: theory and practice. London: Griffin, 1968.

5. Hinkley D. V. Inference about the change-point from cumulative sum tests. Biometrika, 1971, v. 58, № 3, p. 509 - 523.

6. Hinkley D. V. Time-ordered classification. Biometrika, 1972, v. 59, № 3, p. 509 - 523.

7. Johnson R. A., Bagshaw M. L. The effect of serial correlation on the performance of CUSUM tests. I, II. Technometrics, 1974, v. 16, №1, p. 73-80, 1975, v. 17, №1, p. 103-112.

8. Johnson R. A., Bagshaw M. L. Sequential procedures for detecting parameter changes in a time-series model. JASA, 1977, v. 72, №359, p. 593-597.

9. Itai A., Perl Y., Shiloach Y. The complexity of finding maximum disjoint paths with length constraints. Networks, 1982, V.12, N3, p. 277-286.

10. Kajitani Y., Ueno S. The minimum augmentation of a directed tree to a K-edge connected directed graph. Networks, 1986, V.16, N2.

11. Lee G.B. Science information Service directions Changing Patterns in Information Retrieval Philadelphia: ASIS,1974,p. 130136.

12. Page E.S. Continuous inspection schemes. Biometrika, 1954, v.41, N2, p.100-114.

13. Page E.S. A test for a change in parameter occuring at an unknown point. Biometrika, 1955,v.42, N4, p.523-527.

14. Page E.S. On problems in which a change in parameter occurs at an unknownpoint. Biometrika, 1957,v.44, N2, p.248-252.

15. Pettit A.N. A simple cumulative sum type statistic for the change point with zero-one observations. Biometrika, 1980, v. 67, № i, p. 79 . 84.

16. Reynolds A. Approximations to the overage run length in cumulative sum control charts. Technometrics, 1975, v. 17, № 1, p. 65 - 71.

17. Rodionov A.S., Shakhov V.V. About point-of-change problem in the information systems with exponetial distribution. Proceeding of Digital Computer Comminication Network Conference, Tel-Aviv (Israel), 1999, p.141 145 .

18. Ronen D., Perl Y. Heuristics for finding a maximum number of disjoint bounded path. Networks, 1984, V.14, N4.

19. Royston J. P., Abrams R. M. An objeective method for detecting the shift in basal body temperature in women. Biometrics, 1980, v. 36, p. 217 - 224.

20. Shalchov V.V. The problems of similation optimization. Bulletin of the Novosibirsk Computing Center, Special Issue, 1999.

21. Takacs L. Introduction to the Theory of Queues. London and New York: Oxford Univ. Press, 1962.

22. Watanable Т., Nakamura A. Edge-connectivity augmentation problems. J. of Computer and System Sciences, 1987, V.35.

23. Авен О.И., Турин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.

24. Адлер Ю.П., Маркова Е.В., Грановский Ю.В. Планирование эксперимента при поиске оптимальных условий. 2-е изд., перераб. и дополн. - М.: Наука, 1976. - 184 с.

25. Айламазян А.Н. Информация и информационные системы. -М.: Радио и Связь, 1982.

26. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.

27. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. М.: Наука, 1989.

28. Башарин Г.П., Куренков Б.Е. О дискретной модели узла одной сети передачи данных. В кн.: Системы управления информационных сетей. М.: Наука, 1983. 82 с.

29. Беляков В.Г. и др. Об исследовании систем и сетей с бимодальной плотностью длительности обслуживания./ Труды ИВМ и МГ, серия: информатика, вып.З, 1998.

30. Берестнев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1976.

31. Бертсекас Д., Галагер Р. Сети передачи данных. М.: Мир, 1989.

32. Бродкин Л.И., Моттль В.В. Алгоритм обнаружения моментов изменения параметров уравнения случайного процесса. -Автоматика и телемеханика, 1976, №6, с. 23 -32.

33. Бусленко Н.П. Моделирование сложных систем. -М.: Наука, 1968.

34. Вальд А. Последовательный анализ.- М.: Физматгиз.1960, с. 328.

35. Гэри М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М.: Мир, 1982.

36. Дарховский Б.С., Бродский Б.Е. Непараметрический метод скорейшего обнаружения изменения свойств случайной последовательности. Теория вероятности и ее применение, 1987, т. 32, вып. 4.

37. Денисов В.И. Математическое обеспечение системы ЭВМ-экспериментатор. М.: Наука, 1977.

38. Денисов В.И., Попов А.А. Пакет программ оптимального планирования эксперимента. М.: Финансы и статистика, 1986.

39. Дрейпер Н., Смит Т. / Прикладной регрессионный анализ./М:" Статистика", 1973.

40. Зайченко Ю.П. Исследование операций Киев: В ища школа, 1975.

41. Клеинрок. Вычислительные системы с очередями. М.: Наука, 1982.

42. Клеинрок. Теория массового обслуживаниям. М.: Наука, 1982.

43. Клейнен Дж. Статистические методы в имитационном моделировании. Пер. с англ./Под ред. Адлера Ю.П.и Варыгина В.Н. М,-.Статистика,1978.

44. Клигене Н., Телькснис JI. Методы обнаружения моментов изменения свойств случайных процессов./ АиТ, 1983, н.10, с.5-56.

45. Кокс Д.Р., Смит B.JI. Теория очередей. М.: Мир, 1966.

46. Куликовский Л.Ф., Морозов В.К. Основы информационной техники.- М.:Наука, 1977.

47. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М.: Радио и связь, 1986.

48. Мизин И.А., Уринсон JI.C., Храмешин Г.К. Передача информации в сетях с коммутацией сообщений. М.: Связь, 1972.

49. Мину М. Математическое программирование. М.: Наука, 1990.

50. Морозов В.К., Долганов А.В. Основы теории информационных сетей.- М. .'Высшая школа. 1987.

51. Налимов В.В., Чернова Н.А. Статистические методы планирования экспериментов. М.: Наука, 1965.

52. Нейлор Т. Машинные имитационные эксперименты с моделями экономических систем. М.: Мир, 1975.

53. Никифоров И. В. Модификация и исследование процедуры кумулятивных сумм. Автоматика и телемеханика, 1980, № 9, с. 74 - 80.

54. Никифоров И.В. Применение кумулятивных сумм для обнаружения изменения характеристик случайного процесса./ АиТ, 1979, № 2, с.48-58.

55. Никифоров И. В. Применение последовательного анализа к процессам авторегрессии. Автоматика и телемеханика, 1975, №8, с. 174 -177.

56. Никифоров И.В. Последовательное обнаружение изменения свойств временных рядов. М.: Наука,1983.

57. Новые идеи в планировании эксперимента: Сб.статей. М.: Наука, 1969.

58. Попов О.В., Жигулин Л.Ф., Петровский И.Б. Об оценке вероятностных характеристик системы передачи данных впроцессе ее работы. Вопросы кибернетики, 1978, вып. 42, с. 57-63.

59. Риордан Дж., Вероятностные системы обслуживания. М.: Сов. радио, 1966.

60. Рогинский В.Н. Теория сетей связи. М.: Радио и связь, 1981, 192 с.

61. Родионов А.С. К вопросу автоматизации имитации сетей интегрального обслуживания. Труды ВЦ СО РАН. сер. Моделирование информационных сетей. Новосибирск, 1995.

62. Родионов А.С. Объектная ориентация в интеллектуальных системах моделирования. Труды ВЦ СО РАН. сер. Системное моделирование, вып.2, Новосибирск, 1994.

63. Саати T.JL, Элементы теории массового обслуживания с применениями. М.: Сов. радио, 1965.

64. Саати Т, Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. М.: Мир, 1973.

65. Системы управления информационных сетей: Сб.статей. -М.: Наука, 1983.

66. Солтон Дж. Динамические библиотечно-информационные системы: Пер. с англ./Под ред. Петрова.-М,:Мир,1979.

67. Труды международной научно-технической конференции "Проблемы функционирования информационных сетей". Новосибирск: 1991.

68. Федоров В.В. Теория оптимального эксперимента. М.: Наука, 1971.

69. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.

70. Фрэнк Г., Фриш И. Сети, связи и потоки. М.: Связь, 1978. 192 с.

71. Хикс Ч. Основные принципы планирования эксперимента. -М.: Мир, 1967.

72. Шахов В.В. Анализ системы сбыта в условиях нестабильного спроса. Труды конференции молодых ученых ИВМ и МГ СО РАН. Новосибирск, 1997.

73. Шахов В.В. "Вопросы имитационного моделирования". Труды 11-й Байкальской международной школы-семинара Методы оптимизации и их приложения, 1998, том 3, с. 191-195.

74. Шахов В.В. Задачи оптимизации имитационного эксперимента. Материалы международной конференции "Математическое моделирование и информационные технологии в образовании и науке". Алматы, Казахстан, 1998, с. 113.

75. Шахов В.В. Некоторые задачи оптимизации имитационного эксперимента. Третий Сибирский конгресс по прикладной и индустриальной математике, тезисы докладов, часть 3, Новосибирск, 1998.

76. Шахов В.В. "Некоторые задачи планирования имитационного эксперимента". Труды ИВМ и МГ, Серия: Системное моделирование, вып.4(22), 1997.

77. Шахов В.В. Некоторые задачи планирования имитационного эксперимента// Труды конференции молодых ученых ВЦ СО РАН. Новосибирск, 1995. - С. 200-212.

78. Шахов В.В., Родионов А.С. "О разладке в системах с экспоненциальным распределением". Труды ИВМ и МГ, Серия: Системное моделирование, 1998.

79. Шенннон Р. Имитационное моделирование систем искусство и наука. Пер. с англ./Под ред. Масловского Б.К. -М,:Мир,1978.

80. Ширяев А.Н.Вероятность. М.: "Наука", 1989, с.258.

81. Ширяев А. Н. Статистический последовательный анализ. -М.: "Наука", 1976.

82. Шметтеррер JL Введение в математическую статистику. -М.: "Наука", 1976, с.104.

83. Якубайтис Э.А. Информационно-вычислительные сети.-М: Высшая школа,1987.