Оптимизация расположения в пространстве систем массового обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Московский государственный университет имени М. В. Ломоносова

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

ЗАХАРОВА ТАТЬЯНА ВАЛЕРЬЕВНА

ОПТИМИЗАЦИЯ РАСПОЛОЖЕНИЯ В ПРОСТРАНСТВЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

01 01 05 — теория вероятностей и математическая статистика

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

МОСКВА 2008 г

003167178

Работа выполнена на кафедре математической статистики факультета вычислительной математики и кибернетики Московского государственного университета имени М В Ломоносова

Научный руководитель кандидат физико-математических наук

Ведущая организация Институт проблем информатики РАН

Защита диссертации состоится 14 марта 2008 г в 11 часов на заседании диссертационного совета Д 501 001 44 в Московском государственном университете имени M В Ломоносова по адресу 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ имени M В Ломоносова http //www eme msu ru в разделе „Наука"Работа диссертационных советов"-"Д 501 001 44"

Л В Назаров

Официальные оппоненты доктор технических наук,

профессор А И Костогрызов, кандидат физико-математических наук, профессор С H Смирнов

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

и

Ученый секретарь

диссертационного совета

профессор

^Ц»—> H П Трифонов

1 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Очень многие задачи из разных областей техники и народного хозяйства удается сформулировать и решить с помощью теории массового обслуживания Среди них можно выделить кла/с задач, к которому приводят такие реальные системы, где обслуживание производится территориально распределенными объектами [5,7,9] В качестве примеров подобных систем можно привести работу такси [39 40) функционирование сборочной линии [28,41], движение автомобиля < корой помощи в соответствии с адресами поступающих вызовов, перемещение ремонтных бригад, устраняющих отказы в какой-либо территориально распределенной структуре типа сети связи [9,36,37], пожарных час 1 ей и тп

В (вязи с Э1 им возникают задачи нахождения отимально! о или бли ¡-кого к оптимальному размещения станций Например, нефтяной компании надо так разместить автозаправочные станции, чтобы увеличип> прибыльность от их функционирования, задачи минимизации транс порь ных расходов, времени и тд

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

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

Первоначально задача по оптимизации расположения станций решалась для обслуживания конечного числа потребителей, адреса которых были известны, и сами станции могли располагаться в конечном числе точек заданного множества В такой постановке задача была проанализирована Альфредом Вебером в 1909 год> в работе ''О штандорте индустрии" Им были введены такие понятия, как склад и штандорг-ная фигура многоугольник, вершинами которого являют с« п складов и потребитель Решалась задача нахождения штандорта (размещения), минимизирующего транспортные издержки

В сходной постановке но в предположении, что станции могут располагаться в произвольных точках, задача оптимизации решалась И В Гирсановым, Б ТПоляком (1963 1965 гг)

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

В всроятносхной постановке задача была изначально сформулирована Г П Климовым в 1978 году и обобщена Л В Назаровым в 80-х годах В данном случае и станции обслуживания и вызовы могут быть расположены в произвольных точках некоторого пространства Вызовы являются реализацией некоторой случайной величины, у которой есть плотность распределения Выбранные критерии оптимальности зависят от расстоя-

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

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

Исследованию описанных проблем посвящена данная диссертационная работа

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

Научная новизна Все основные результаты диссертации являются новыми и состоят в следующем

- при довольно общих предположениях исследовано предельное пове дение критерия на поспедовательности оптимальных размещений,

- найдена предельная оптимальная плотность размещений,

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

- исследованы свойства оптимальных размещений для спсциалыго1 о класса нормированных пространств,

- при оптимизации расположения станций обслуживания при наличии очереди в стационарном режиме исследовалась дисциплина обслу-

живания в порядке поступления и обслуживания первым из очереди наикратчайшего требования без прерывания обсл/живания

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

Теоретическая и практическая значимость Результаты диссертации носяг как теоретический, гак и практический характер Полученные результаты могут быть применены при изучении реальных систем, перечисленных выше Алгоритмы построения асимптотически оптимальных размещений могут быть реализованы на ЭВМ, в то время, как oí ыс-кание оптимальных размещений представляет собой достаточно сложную задачу численного анализа[42,43]

Апробация работы и публикации. По теме диссертации опубликовано 5 печатных работ Результаты работы докладывались и обсуж дались на научно-исследовательском семинаре по теории массово!о обслуживания кафедры математической статистки факультета Вычислительной математики и кибернетики МГУ (2007), на конференции "Рас прсдолсиные автоматизированные системы массового обслуживания" (Кишинев, 1987), на научно-исследовательском семинаре Механико-млл соматического факультета МГУ "Вероятностные методы в технике"(1988), на научно-исследовательском семинаре ИППИ АН СССР (1989), на XXVI Международном семинаре по проблемам устойчивости стохастичес ких моделей (2007)

Структура диссертации Диссертация состоит из введения, двух глав, разбитых на параграфы, списка литературы, содержащего 44 наименования, приложения Общий объем работы - 106 страниц

2 КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Определение 1 Размещением п станций в пространстве назовем множество {^1, ,хп} точек пространства кк, в которых эти станции расположены

В первой главе рассматривается критерий оптимальности - среднее значение некоторой возрастающей функции расстояния от возникающею требования до ближайшей станции обслуживания Расстояние | и — г>| между точками и и V пространства задается различными нормами Рас стояние между точками и и г> будем также обозначать р(и, ь)

Определение 2 Зоной влияния станции ж, назовем множество Сг тех точек пространства для которых эта станция является ближай-шеи, те

С, - {V е к1^ |г> - хг\ < ¡г; - х3\, ^ = 1,2, ,п}

Точка £ пространства Ек, из которой поступает вызов, является случайной величиной с плотностью распределения р Станции обслуживаю I вызовы только из своих зон влияния Для оценивания оптимальности расположения этих станций задан критерий <р

1р(х) — Е ГП1П рв{£,хг) , 5 > О 5

Определение 3 Размещение х* — {ж*, , ж*} называется оптимальным по критерию <р среди размещений х — {хг, , хп], если

<р(х*) = гп1п <р(х) х

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

Корректность определения 3 следует из теоремы 1 приводимой ниже Теорема 1 Если Е|£|5 < оо , тогда в для любого п ^ 1 существуй оптимальное размещение х* = {ж^, , ж*}

В рассматриваемом критерии <р параметр в можно выбирать из следующих соображений Если то <р(х) — Е тш р(£,х,) и задача сво-дихся к минимизации среднего расстояния от вызова до ближайшои к нему станции Если в > 1, тогда оптимальным будет размещение, при котором не появляются слишком удаленные вызовы При & < 1 , наоборот, выгоднее размещать станции в точках с большой плотностью (в областях скопления вызовов)

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

Когда оптимальные размещения ищутся на плоскости (N1-2) то расстояние определяется по евклидовой норме р и норме р\

р(и, у) = лДйГ-щ)2 + ("2 ~ ^г)2,

рх{и,у) - |гц — г)х| + \и2 - у2\ , для и - (иьи2), V = (иьг>2)

В ТУ-мерном пространстве (N — 1,2, ) расстояние будет определяться следующей нормой

Poo{u,v) - max - ьг\ , и — (щ, , uN), v - (vj, ,vN)

lsji <iV

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

Определение 4 Диаметром множества А в метрическом простри.-с гве называется число

diam Л = sup р(х,у) ,

х,уС-А

где р - расстояние в данном пространстве

Лемма 1 Если Е|£|5 < оо , то lim <р(х*) — О

п—>по

Обозначим Dn{x) - max агат Аг, А, — {и е А[ р(и) > 0}, где

l^isjn

А[ - зона влияния станции xt на произвольном компакте G Лемма 2 Если lim ip(x) = 0 то lim Dn(x) = 0

П—>00 Tt->CO

Лемма 3 Пусть х = ,хп} - размещение на выпуклом к-

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

1Л к-6

- V тг < 6 +-

п ' п

г—1

Введем функцию

w(i) = j a{\u\)du, 0 ^ t < К/2 t

Лемма 4 Пусть в выпуклый ¿¡-угольник 5 помещается п точек II, ,хп Сг - зона влияния х, на 5 Справедливо следующее неравен-

ство

J а (|и — ж,|) du > п j а (|uj) du — (к — 6)i? , с, ff

где а - правильный mecrayi ольник площади S/n с центром в нуле

R - положительное число, определяемое соотношением

_ [ тшФ'(и), u е [6 + (к - 6)/п, 6], 3 < к < 6

I тахФ'(и),и е [6,6+ (к - 6)/гг], fc > 6

Замечание Эта оценка является обобщением результата Л Фейеша Тота [25]

Чтобы подчеркнуть с каким именно нормированным пространством мы работаем, будем обозначать пространства символами соо гветпвенно введенным нормам р, рьроо

Рассмотрим случаи метрических пространств Щ и R^ Лемма 5 Если Q - измеримое по Лебегу подмножество метрическо-1 о пространства, S - шар с центром в точке v из того же пространства и меры Лебега множеств Q и S равны тогда

J а(\и — v\)du ^ J а(\и — v\)du

Q S

для любой неубывающей на [0, оо) действилельной функции а(и)

Лемма 6 Пусть для г = 1,2, ,п St обозначает шар с центром

п

в пуле, ап - шар с центром в нуле и мерой ап — - Sz Справедливо

п t=i

следующее неравенство

£J

для любой неубывающей на [0, оо) действительной функции а(и

, I a(\u\)du ^ п / а(|и|)с£ы, (1)

I L

Введем следующие обозначения

(N hs)/N

дня пространства Лц

С=- J \u\"du ,

где Mfy - правильный шестиуюльник единичной меры Jleöeia с центром в нуле,

для пространств R\ и R^

С~- J \u\sdu,

Е

где Е - шар единичной меры Лебега с центром в нуле

Следующая теорема описывает предельное поведение критерия <р на последовательности оптимальных размещений

Теорема 2 Если Eps(0,£) < оо, функция p2/(2+s) интегрируема по Лебегу, то ддя всякой последовательности оптимальных размещений {.г*}

limns/V(0= С\\р\\,

в/Й

где

(2М)/2 ^

С —

12 / 1 У^^ Г dy

24 s \2%/3/ J cos

Для пространства Е\ справедливо аналогичное утверждение Основное енличие при доказательстве заключается в следующем оптимальные размещения зависят от выбранной системы координат, при ^гом константа С определяется по формуле

2 + 5 9

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

Следующая теорема описывает еще одно асимптотическое свойство оптимальных размещений

Теорема 3 Если Е|£|5 < оо, функция интегрируема по Де-

бет у, А - измеримое по Лебегу множество из Я", тогда для всякой последовательности оптимальных размещений {ж*} в Нд, или Я^

где х*А = х* (~).4, - число элементов в х*А

Определение 5. Пусть У - некоторый критерий для размещений Размещение х — {х\, ,хп} называется асимптотически оптимальным первого порядка или просто асимптотически оптимальным, если

[до х* = {ж*, , ж*} - оптимальное размещение по критерию F

Для каждого изучаемого пространства приведены алгоритмы построения асимптотически оптимальных размещений Для последовательности асимптотически оптимальных размещений также верны теоремы 2 и 3

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

а

п~>со F{x*)

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

Лемма 7. Пусть [¿х, 1] - носитель плотности распределения р и р - дифференцируема Тогда для всякого оптимального размещения х* = {г*, выполняются соотношения

1 V1

< = ¿г + -Дг + ^ Д2 о(А;) , V» = 1,2, , п ,

где Д, — [йг,(11+\\ - зона влияния станции х* на носителе плотности,

Рг --рШ,р{ =р'{<Лг)

Следствие Длины зон влияния станций на носителе плотности при оптимальном размещении х* = {а^, ,£*} имеют порядок

Определение 6 Размещение х = {а"х, , хп} будем называть асимптотически оптимальным второго порядка по критерию <р, если

Ьш Шх) - <р(х*))п2 = 0 ,

п-юо

где х* — {ж*, ,£*} - оптимальное размещение по критерию <р

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

Теорема 4 Если плотность р имеет непрерывную вторую производную, то для всякой последовательности оптимальных размещении {ж*}

Ьт п2= 0

п-+оо 4п

Построим последовательность {а;} - асимптотически оптимальных размещений второго порядка Такие размещения не являются единственными Укажем один из возможных алгоритмов построения асимптотически оптимальных размещений второго порядка х = {жь ,

Обозначим через М = тахр(и) , т — ттр(и) Исходный отрезок С разобьем на непересекающиеся множества С,, г — 1,2, ,к так чтобы выполнялись следующие условия

г, ^ ° „ м^с? Г 071

числа пг , определяемые соотношениями / р1'2{и)аи

СЦ

п, = —---—п, г = 1,2, ,к

в

должны быть натуральными

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

В параграфе 1 4 первой главы рассматривается специальный класс нормированных пространств

Пусть р некоторая норма, по которой определяется расстояние между точками пространства, и для нее известен алгоритм построения асимптотически оптимальных размещений По этой норме можно построить класс метрик Минковского М., в котором роль единичной сферы играет геометрическое тепо, полученное некоторым аффинным отображением ¡г единичной сферы в пространстве с нормой р Обозначим через 6 норму, принадлежащую такому классу Л4 Идея построения асимгиотически оптимальных размещений в пространстве с нормой 6 состой 1 в следую щем

Если в пространстве с нормой р х* - оптимальное размещение, то в пространстве с нормой 6 размещение, полученное отображением Л. размещения х*, будет обладать тем же свойством оптимальности

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

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

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

Вначале рассматривается проблема оптимизации расположения станций обслуживания по критерию стационарного среднего времени ожидания начала обслуживания для систем с дисциплиной обслуживания

Размещения х — ,хп} оцениваются по критерию оптимально-

сти

при условии, что max A,/?,i < 1, где Aj - интенсивность потока вызовов,

поступающих на станцию х%1 ДъАг соответственно первый и второй моменты времени обслуживания на хг

Описываются свойства оптимальных размещений и приводятся ал! о-

FIFO

Tsii^n

ритмы построения асимптотически оптимальных размещений

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

В этом случае исследованы асимптотические свойства оптимальных размещений по критерию

при условии, чю max A,/?,i < 1, где Л, - интенсивность потока вызо-

вов, поступающих на станцию хг, Вг функция распределения времени обслуживания на ж,, Д.i, Д2 ~ соответственно первый и второй моменты времени обслуживания на хг

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

Предполагается, что станции функционируют как независимые системы массового обслуживания типа M|G|1, тогда их средняя суммарная длина очереди L(x) при размещении х при условии, что загрузка каждой станции меньше единицы, те max \фг\ < 1, определяется по

о

IsCziCn

формуле

Для этой модели получены следующие результаты Теорема 5 Если плотность р ограниченная, интегрируемая по Лебегу функция, Е|£|? < оо и интенсивность входящего потока А(п) изменяется так, что

lim ^ = а/01 , а С [0,1) ,

П-¥ 00 П

мила для всякой последовательности оптимальных размещений {х*} справедливы равенства

1) hm^L^-O.ÖÄil-a)-1,

п ->оо ^ ^ >

2) hm = f plu) du ,

п-юо a д

где А - произвольное измеримое по Лебегу множество

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

Теорема 6 Если плотность р ограничена, интегрируема по Лебегу Е|£|2 <оо и интенсивность входящего потока требований изменяется так что

hm ^-а/(2/(б)Ь|2/3), (У fc [0,1) ,

71->00 fi I

го1да для всякой последовательности оптимальных размещений {х*}

1) hm щ^Ь{х*) 2g{b)\p\lß{\ - а)"1 ,

2) hm 1? = |РЙ/3/Р?/3(«)А»>

для любого измеримого по Лебегу множества А

Оказывается, что размещения станций обслуживания, являющиеся оптимальными по критерию W (стационарное среднее суммарное время ожидания начала обслуживания), не минимизируют критерий L (стационарная средняя суммарная длина очереди всех станций)

3 СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1 Новикова Т В Оптимальные размещения в пространсгве // Вопр вычисл мат и програм обесп ЭВМ М , 1984, с 95-100 Деп в ВИНИТИ, 23 И 84, № 7484-84

2 Захарова ТВ Оптимальные размещения для систем с оптимальной дисциплиной обслуживания - Вест Моек ун-та, сер 15 Вычисл матем и киберн , 1987, № 4, с 67-69

3 Захарова ТВ Ошимизация расположения станций обслуживания на плоскости// Изв АН СССР Техн киберн 1987 №6 с 83-91

4 Захарова ТВ Оптимальные размещения для систем с оптимальной дисциплиной обслуживания - Случайный анализ Сб научных статей - М Изд-во Моек ун-та, 1987, с 43-50

5 Захарова ТВ Оптимальные размещения систем массового обслуживания с дисциплиной обслуживания FIFO - Вест Моек ун-та сер 15 Вычисл матем и киберн , 2007, N° 4, с 32-37

Издательство ООО «ПКЦ Альтекс» Издательская лицензия ЛР № 065802 от 09.04 98

Формат 60x901/16 Усл.леч.л 1 Тираж 100 экз. Заказ № 76

Отпечатано в типографии ООО «Мультипринт» 121360, г. Москва, ул. Верейская, д 29. Тел 518-76-24,230-45-55,411-96-97

тиЬфпи^ша!! ги тллу k-multlprшt ги

Введение

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

2. Краткое содержание диссертации.

3. Список публикаций автора.

1 РАЗМЕЩЕНИЯ В ПРОСТРАНСТВЕ

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

1.2. Оценки снизу для оптимальных размещений по различным критериям.•.

1.3. Построение асимптотически оптимальных размещений

1.4. Асимптотически оптимальные размещения для специального класса нормированных пространств.

1.5. Асимптотически оптимальные второго порядка размещения на прямой.

2 ОПТИМИЗАЦИЯ РАСПОЛОЖЕНИЯ

СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ 65 2.1. Размещение станций обслуживания по критерию среднего виртуального времени ожидания.

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

2.1.2. Свойства оптимальных размещений.

2.2. Размещения систем массового обслуживания, минимизирующие среднюю длину очереди.

2.3. Размещения систем массового обслуживания с дисциплиной обслуживания первым наикратчайшего требования без прерывания обслуживания

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

Актуальность темы. Очень многие задачи из разных областей техники и народного хозяйства удается сформулировать и решить с помощью теории массового обслуживания. Среди них можно выделить класс задач, к которому приводят такие реальные системы, где обслуживание производится территориально распределенными объектами [5,7,9]. В качестве примеров подобных систем можно привести работу такси [39,40], функционирование сборочной линии [28,41], движение автомобиля скорой помощи в соответствии с адресами поступающих вызовов, перемещение ремонтных бригад, устраняющих отказы в какой-либо территориально распределенной структуре типа сети связи [9,36,37] и т.п.

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

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

Исследованию описанных проблем посвящена данная диссертационная работа.

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

Научная новизна. Все основные результаты диссертации являются новыми и состоят в следующем:

- при довольно общих предположениях исследовано предельное поведение критерия на последовательности оптимальных размещений;

- найдена предельная оптимальная плотность размещений;

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

- исследованы свойства оптимальных размещений для специального класса нормированных пространств;

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

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

Теоретическая и практическая значимость. Результаты диссертации носят как теоретический, так и практический характер. Полученные результаты могут быть применены при изучении реальных систем, перечисленных выше. Алгоритмы построения асимптотически оптимальных размещений могут быть реализованы на ЭВМ, в то время, как отыскание оптимальных размещений представляет собой достаточно сложную задачу численного анализа[42,43].

Апробация работы. Результаты работы докладывались и обсуждались на научно-исследовательском семинаре по теории массового обслуживания кафедры математической статистики факультета ВМиК МГУ, на конференции "Распределенные автоматизированные системы массового обслуживания "(Кишинев, 1987), на семинаре "Вероятностные методы в технике", на научно-исследовательском семинаре ИППИ АН СССР, на XXVI Международном семинаре по проблемам устойчивости стохастических моделей (2007).

Публикации. Основные результаты диссертации опубликованы в 5 работах автора[10-13,25], список которых приводится в конце введения.

Структура диссертации. Диссертация состоит из введения, двух глав, разбитых на параграфы, списка литературы, содержащего 44 наименования, приложения. Общий объем работы - 106 страниц.

1. Акимова И.Я. Задача оптимального размещения и обобщения одной теоремы Фейеша Тота.- Изв. АН СССР. Техн. кибернет., 1982. М. С.224-228.

2. Алон Н., Спенсер Дж. Вероятностный метод.- М.: Бином. Лаборатория знаний, 2007.

3. Бабенко В.Ф. Об асимптотически наилучшей квадратурной фор-, муле для одного класса функций двух переменных.- В сб. Исследования по современным проблемам суммирования и приближения функций, вып. 5.- Днепропетровск, 1974, с. 3-5.

4. Бабенко В.Ф. Точная асимптотика остатков оптимальных для некоторых классов функций весовых кубатурных формул.- Ма-тем. заметки., 1976, т.20, № 4, с.589-595.

5. Боровков А.А. К вероятностной постановке двух экономических задач,- ДАН СССР, 1962, т. 146, № 5, с.983-986.

6. Вероятность и математическая статистика. М.: Большая Российская Энциклопедия. 1999.

7. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания.- М.: Изд-во Моск. ун-та, 1973.

8. Гордиенко Е.И. Модель управления обслуживающим объектом в территориально распределенной системе.- Изв. АН СССР. Техн.кибернет., 1980, № 6, с.77-85.

9. Захарова Т.В. Оптимальные размещения для систем с оптимальной дисциплиной обслуживания.- Вест. Моск. ун-та, сер. 15. Вы-числ. матем. и киберн., 1987, № 4, с.67-69.

10. Захарова Т.В. Оптимизация расположения станций обслуживания на плоскости// Изв. АН СССР. Техн.киберн. 1987. №6. с. 8391.

11. Захарова Т.В. Оптимальные размещения для систем с оптимальной дисциплиной обслуживания.- Случайный анализ: Сб. научных статей М.: Изд-во Моск. ун-та, 1987, с.43-50.

12. Захарова Т.В. Оптимальные размещения систем массового обслуживания с дисциплиной обслуживания FIFO.- Вест. Моск. ун-та, сер.15. Вычисл. матем. и киберн., 2007, № 4, с.32-37.

13. Захарова Т.В., Петухов А.В, Рвачева И.А. О диалоговой системе для расчета характеристик СМО.- Распределенные автоматизированные системы массового обслуживания.- Кишинев, Картя молдавеняске, 1987, с .245-246.

14. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М.: Высшая школа, 1982.

15. Климов Г.П. Стохастические системы обслуживания. М: Наука, 1978.

16. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа.- М.: Наука, 1981.

17. Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. М.: Наука, 1976.

18. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М: Наука, 1973.

19. Назаров Л.В. Об асимптотически оптимальных размещениях станций обслуживания на плоскости.- В сб.: Некоторые вопросы прикладной математики и программного обеспечения ЭВМ.-М. : Изд-во Моск. ун-та, 1982, с.80-81.

20. Назаров Л.В. Системы массового обслуживания с вызовами, возникающими в пространстве. 4.II. Методическая разработка.- М., 1984, 44с.

21. Назаров Л.В., Смирнов С.Н. Обслуживание вызовов распределенных в пространстве. Изв. АН СССР. Техн. кибернет., 1982, №1. С.95-99.

22. Нартов Б.К. Оптимальное размещение управляемых подвижных объектов на заданных начальных позициях. Мехатроника, автоматизация, управление, 2004, № 2, с.43-47.

23. Неве Ж. Математические основы теории вероятностей.- М.: Мир, 1969.

24. Новикова Т.В. Оптимальные размещения в пространстве // Вопр. вычисл. мат. и програм. обесп. ЭВМ.- М., 1984, с.95-100. Деп. в ВИНИТИ, 23.11.84, № 7484-84.

25. Печинкин А.В. Система с дисциплиной обслуживания первым наикратчайшего требования без прерывания обслуживания. Ч.1.-Автоматика и телемеханика, 1985, № 2, с.53-62.

26. Привалов А. А. Теория интерполирования функций. Саратов: Изд-во Саратов, ун-та, 1990.

27. Самандров Э.Г. О системе с движущимся прибором обслуживания. ДАН Тадж. ССР, 1976, т. 19, № 12, с. 3-6.

28. Сантало Л. Интегральная геометрия и геометрические вероятности.- М.: Наука, 1983.

29. Тот Ф.Л. Расположение на плоскости, на сфере и в пространстве. М.: ГИФМЛ, 1958.

30. Феллер В. Введение в теорию вероятностей и ее приложения.- М.: Мир. 1984, т.2.

31. Халмош П. Теория меры. М., 1953.

32. Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии.- М.: Наука, 1966.

33. Харди Г. Расходящиеся ряды,- М.: ИЛ, 1951.

34. Эрдейи А. Асимптотические разложения. Физматгиз, 1962.

35. Bollobas В. The optimal arrangement of producers.- J.London Math. Soc., second series, 1973, v.6, part 4, p.605-613.

36. Bollobas B. Random graphs.- N.Y.: Academic Press, 1985.

37. Brostow W. Equilibrium properties in the liquid state from interactions of walks.- Phys. Chem. Liquids, 1972, v.3.

38. Crane M.A. Queues in transportation systems. J. Appl. Probab.,1973, v. 10, n 3, p. 630-643.

39. Crane M.A. Queues in transportation systems. J. Appl. Probab.,1974, v. 11, n 1, p.115-148.

40. McMillan В., Riozdan J. A moving single server problem.- Ann. Math. Statist., 1957, v.28, № 2, p.471-478.

41. Nurmela K. J., Ostergard P.R. Asymptotic behaviour of optimal circle packings in a square.- Can. Math. Bull., 1999, v.42, p.380-385.

42. Szabo P.G. Optimal substructures in optimal and approximate circle packings.- Contrib. Alg. and Geom., 2005, v.46, № 1, p. 103-118.

43. Ziman J.M. Principles of the theory of solids.- L.-N.Y.: Cambridge Univ. Press, 1972.