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

КАРПОВА Марина Александровна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МНОГОКРАТНОГО ПОКРЫТИЯ

Специальность: 05.13.18 - математическое моделирование, численные методы и комплексы программ

1 3 ОКТ 2011

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Казань 2011

4856929

Работа выполнена в «Казанском национальном исследовательском техническом университете им. А.Н. Туполева-КАИ»

Научный руководитель

д-р тех. наук, проф. Галиев Шамиль Ибрагимович

Официальные оппоненты

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

д-р тех. наук, проф. Захаров Вячеслав Михайлович

Ведущая организация

Казанский национальный исследовательский технологический университет

Защита диссертации состоится «_»

2011 года в

часов на заседании диссертационного совета Д 212.079.01 в «Казанском национальном исследовательском техническом университете им. А.Н. Туполева-КАИ» по адресу: 420111, г. Казань, ул. К. Маркса, д. 10, зал заседаний Учёного совета. Автореферат диссертации размещен на сайте «Казанского национального исследовательского технического университета им. А.Н.Туполева-КАИ» www.kai.ru и направлен для размещения в сети Интернет Министерством образования и науки Российской Федерации по адресу référât vak@mon.gov.ru.

С диссертацией можно ознакомиться в библиотеке «Казанского национального исследовательского технического университета им. А.Н.Туполева-КАИ» по адресу: 420111, г. Казань, ул. К. Маркса, д. 10.

Автореферат разослан «_»__ 2011 года.

Учёный секретарь Й^ЙЬ /¿¿сЛ

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

д-р физ.-мат. наук, проф. П. Г. Данилаев

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

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

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

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

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

Оптимизации расположения различных станций обслуживания посвящены специальные монографии и большое число статей, исследующих как общие вопросы, так и решение задач для выбранных областей. Обзоры по этим задачам и достаточно детальное исследование приложений содержатся в монографиях Дрезнера Ц., Дрезнера Ц. и Гамахера Г., Шиллера Дж. и Войсарда А., Купера А., Фарахани Р. 3. и Гекматфара М., Финкельштейна Ю. Ю., Ковалева М. М., Сигала И. X. и Ивановой А. П. и в ряде других работ.

По различным вариантам задач покрытий (и связанных с ними задач упаковок) имеется большое число работ, укажем только некоторые, а именно, работы Роджерса К., Конвея Дж. и Сло-эна Н., Фейеша Тота Л., Фейеша Тота Г., Леонтьева В. К., Брусова В. С. и Пиявского С. А., Колоколова А. А., Еремеева А. В., Кузю-ринаН. Н., Мухачевой Э. А., Залгаллера В. А., Галиева Ш. И., За-ботина В. И., Захарова В. М., Бухараева Р. Г., Емалетдиновой Л. Ю. Задача однократного покрытия N кругами ограниченной части плоскости (как в евклидовой метрике, так и в некоторых других метриках) известна также как задача об М-центре, для которой многими авторами предложены различные алгоритмы.

В дискретной постановке задачи покрытия и упаковок являются вариантами дискретных оптимизационных задач. По задачам дискретной оптимизации и их интересным и важным приложениям имеется большое число монографий и научных статей. Часть из них указана выше. Необходимо также указать важные работы Аар-дала К., Немхаузера Г. Л. и Вейсмантела Р., Леонтьева В. К., Журавлева Ю. Н., Коннова И. В., Емеличева В. А., Ковалева М. М. и Кравцова М. К, Ревелле К. С., Ейселта X. А. и Даскина М. С.

Цель работы:

• анализ свойств математических моделей и развитие методов оптимизации многократных покрытий;

• повышение эффективности алгоритмов решения непрерывных и дискретных задач многократного покрытия ограниченных множеств.

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

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

• разработать численные алгоритмы оптимизации числа кругов или (и) их расположения для ¿-кратного (к > 1) покрытия заданных областей или заданного конечного множества точек;

• получить оценки минимальных радиусов покрывающих кругов;

• подобрать метрики и их параметры для выбранных районов Татарстана;

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

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

• выявлены новые свойства математических моделей задач покрытия:

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

- для непрерывных моделей однократного и многократного покрытия ограниченной области установлена недифференцируемость целевых функций в точке (точках) глобального экстремума;

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

• получены экстремальные и предполагаемые значения радиусов п кругов для двукратного покрытия единичного квадрата при п<9 и'#1 = 11,13,15,17,19,21;

• подобраны метрики для отдельных районов Татарстана;

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

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

Апробация работы/ Результаты исследований докладывались и обсуждались на конференциях: Международная конференция «Туполевские чтения» (г. Казань, 2008, 2009, 2010); Международная научно-техническая конференция «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2008); Международная научно-образовательная конференция «Наука в вузах: математика, физика, информатика» (г. Москва, 2009); Международная научно-практическая конференция «Современные достижения в науке и образовании: математика и информатика» (г. Архангельск, 2010); Общероссийская научно-практическая конференция на основе интернет-форума с международным участием «Актуальные вопросы современной науки и образования» (г. Красноярск, 2010); Всероссийская межвузовская научная конференция «Наука и образование в развитии промышленной, социальной и экономической сфер регионов России» (г.Муром, 2011).

Публикации. Основные результаты исследований опубликованы в трех статьях в журналах из списка, рекомендованного ВАК РФ, и в 8 сборниках материалов конференций.

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения, списка цитированной литературы и приложения. Общий объем диссертации составляет 140 страниц машинописного текста, включая 35 рисунков и список цитированной литературы из 154 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Пусть С - ограниченное множество на плоскости Р. Множество N замкнутых кругов К), 1 < ] < N, одинакового радиуса г образует ¿-кратное (\<к<Ы) покрытие (7, если каждая точка .у из С принадлежит к этим кругам как минимум. Сформулируем следующую задачу.

(21): Требуется выбрать расположение N кругов К., 1 </< N, одинакового радиуса г, образующих ¿-кратное покрытие О таким образом, чтобы их радиус г достигал наименьшего возможного значения гт1п.

Известны задачи 0-1 минимального покрытия и многократного покрытия как задачи целочисленного линейного программирования:

(22): 1тп{сг:Аг > q, г, е {0,1}} или шп{сг:Аг ^ д, г, е 2+ }, здесь: сг - скалярное произведение векторов сиг, с = (с,,...,с„)Г, г = (г,,...,г„)г; А -тхп -матрица, элемента-

ми которой являются 0 или 1; q - заданный ш-мерный вектор; Z+ - множество целых неотрицательных чисел. Задачу Z1 считаем непрерывной задачей покрытия, a Z2 -дискретной задачей покрытия.

Пусть с j(Xj, у j) - центры кругов Ку, 1 < j<N. Положим,

что ^ = (xt,yi,...,xN,yN), a d(s,t) - евклидово расстояние между точками 5 и t на плоскости Р. Задача Z1, как известно, сводится при ¿ = 1 к следующей задаче:

min шах min ¿(i, с ). rn

i ¡Ей \<i<s ' Ш

Для ¿-кратного покрытия (¿ > 1) имеем задачу:

min max min d (s, с), n\

4 JSC j: Jk

где Jk - множество индексов N - к + I центров c], которые отстоят от s не ближе чем к - 1 оставшихся центров с,, 1 < j <N. Задачи

(1) и (2) являются задачами негладкой оптимизации и решение их нетривиально.

Для совокупности N точек су., 1 < j < N , ¿-кратной (1 < к < N) областью Вороного D;. с центром с] считается

D* ={seG:d(s,cJ)<mirid(s,ci)}, l<j<N. (3)

Построение многократных областей Вороного в данной работе реализовано в алгоритме А 1.1 диссертации.

В случае, когда множество G является конечным множеством М = [pf. р^Р, l<i < N }, определяются дискретные ¿-кратные множества (дискретные ¿-кратные области) Вороного £>*', вводимые по (3), в которых условие se G заменено на ¿еМ.

Для задачи Z1 введем функцию: у/(£) = max mind(s,с.) или

геС 1 <j<N J

у/(£) = max min d{s,c.). Функцию у/ можно считать заданной на

KG JcJU-.,, 1

некотором ограниченном замкнутом множестве G*. Известно, что является дифференцируемой почти всюду. Согласно модели (1) или (2) нужно минимизировать . Используя производную Кларка, в работе доказана следующая теорема.

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

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

Пусть задано множество точек £ = {£>,,...,&„}. Положим, что заданы круги известного радиуса г, центры су которых могут

находиться в некоторых точках из В. Требуется найти минимальное число кругов заданного радиуса г, которые образуют ¿-кратное, 1 < к < п, покрытие множества В. Для решения этой задачи вводят: |1, если сКЬпЬ})<г,

10, если(1 (Ь[,Ь])> г, 1</, }<п.

Введем также переменную г, следующим образом:

г, = числу центров кругов совпадающих с точкой Ь„ 1 < / < п. Теперь, если в целевой функции задачи 72 положим все с] = 1, 1 < г < п , а в правой части ограничений Ь = 1, тогда задача 22, как известно, является задачей (однократного) покрытия множества В минимальным числом кругов заданного радиуса г;

п п

= ->пип>1, г = 1,..,и;г, е {ОД},7 = ■

.-=1 . (■+)

Если в задаче 72 все с,. = 1, 1 < г < п , а Ь = к, то имеем:

п п

= г = 1,..,«;г, е {0,1},

м м Р)

которая является задачей ¿-кратного покрытия множества В минимальным числом кругов радиуса г. Можно ввести условие, что ц принимает значения от 0 до к. Тогда имеем задачу:

п п

Fint(z) = 2>; н>min,>к, 1 = 1,..,л,г('б {0,1...,*}, (6) В случае введения условий z,eZ\ 1 <i<n, получим задачу:

п п

Fim(z) = 'Lzi >к, i = l,..,n;z,e Z+,i = l,...,n. (7)

В работе Сигала И. X. и Ивановой А. П. сформулированы необходимые условия разрешимости однократной задачи покрытия (4), которые, оказывается, являются и достаточными условиями. Запишем это в виде теоремы.

Теорема 1.2. Для разрешимости систем (4), (6) или (7) необходимо и достаточно, чтобы выполнялись условия:

п

-1 Для всех i = 1,..., п.

i'l

Также в диссертации доказана теорема: Теорема 1.3. Для разрешимости системы (5) необходимо и достаточно, чтобы выполнялись условия:

п

Y^a^k для всех 1 = 1,..., п.

7=1

В дальнейшем будем, в основном, рассматривать задачу (6), если не оговорено иное. Задача минимального покрытия, как известно, является NP полной, поэтому для ее решения естественно (пока Р& NP) использовать эвристики или методы случайного перебора. В работе предлагается новая эвристика для задачи покрытия, реализованная в алгоритме А 1.3, который использует вспомогательный алгоритм А 1.2 приведенный в диссертации. Запишем ЛП-релаксацию для задачи (6):

п

Fcont = Iг,- min; Az>k; 0<Zj<k, 0<г </г. (8)

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

Алгоритм А 1.3 для решения задач (4)-(7) сводится к следующему:

- решение релаксированной задачи;

- если все решения целочисленные, то задача решена, иначе специальным способом выделяется множество переменных для построения ядерной задачи;

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

- точное решение построенной ядерной задачи.

Рассмотрим дискретный подход к задаче 21. С шагом Дх = А)' построим сетку на С, и пусть Ь: - узлы сетки, 1 < / < п , где п - число точек . Выберем (зададим) радиус г покрывающих кругов, и пусть с] - центры кругов К1 радиуса г, 1< у'< N , Ы<п.

Получим задачу (4) в случае однократного покрытия и (5)-(7) в случае ¿-кратного. Эти задачи являются дискретным вариантом задачи 21, в которой покрываемое множество равно {¿ , 1 <1<п\.

Методика решения задачи 21 состоит в согласованном решении задач (1) и (4) для однократного покрытия и задач (2) и выбранной одной из задач (5)—(7) для ¿-кратного (к>1) покрытия. В данной работе для ¿-кратного (к > 1) покрытия выбирается задача (6). При решении задачи 21 используется вспомогательный алгоритм А 1.4.

Алгоритм А 1.5 (решения задачи 21) сводится к следующему:

• приближенное решение непрерывной задачи;

• решение релаксированной дискретной задачи;

• выделение ядерной задачи;

• точное решение ядерной задачи;

• решение непрерывной задачи с использованием решения

ядерной задачи.

В диссертации при некоторых условиях получена оценка минимального значения радиуса покрывающих кругов для задачи 21\ эта оценка предполагает нахождение точного решения задачи (6). Также в диссертации получены некоторые экстремальные и пред-

полагаемые двукратные покрытия единичного квадрата для некоторых значений числа кругов. Пусть гп к - значение радиусов кругов, такое, что п таких кругов обеспечивает ^-кратное (1 <к<п) покрытие квадрата, и положим, что гпЛ - наименьшее возможное значение гп к по всевозможным положениям центров кругов.

Теорема 1.4. Для 2-кратного покрытия квадрата 5 имеет место: г4*2 = гъл = л/5/4, 0,5 < г1я < 0,503891109, 0,5 < г7\ < 0,503891109,

<2 =<2=^2/4.

Найденные автором значения радиусов кругов для двукратного покрытия единичного квадрата при п = 11, 13, 15, 17, 19 и 21 приведены ниже.

Л,, =0.29873 < гП2 =0.31280 < г5| = 0.32616, г„ =0.27429 <г1ЪЛ= 0.29106 <г61 =0.29873, г81 -0.26030 < гш = 0.26650 < г1Л = 0.27429, г9 ,= 0.23064 <г172= 0.25372 <г81 =0.26030, г10, = 0.21823 < г19-2 = 0.22766 < г91 = 0.23064, гИ1 =0.21251 <г2] 2=0.21601 <г101 =0.21823. Значения г5, и г6, доказаны Мелиссеном Г. Предполагаемые значения г1А, г8д найдены в работах Мелиссена Г.; г91 - в работе Нурмеллы К. и Остергарда П.; гт - в работе Тарнаи Т., а гш - в

работе Мелиссена Г. и Шура П. Полученные в диссертации результаты показывают высокую результативность и хорошую точность предложенного метода.

При решении применялись программы, разрешенные для свободного использования: РСх, ЬРБо^е и, купленная нашим университетом, библиотека ПХЮСРЬЕХ 11.2. Строились релаксиро-ванные задачи размерности до 10000x10000, а ядерные - размерности т х 10000, где т = 300 - 500.

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

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

Пусть центры покрывающих кругов могут располагаться в любых точках области G , Ge: Р. Требуется ¿-кратно (к > 1) покрыть конечное множество точек М-\р}, 1< j < т\ плоскости Р. Рассмотрим следующие задачи.

(Z5): Выбрать расположение N кругов K¡, 1 < j <N , одинакового радиуса г, образующих ¿-кратное (1 <k<N) покрытие конечного множества М, таким образом, чтобы их радиус г достигал наименьшего возможного значения.

(ТА): Определить минимальное число кругов заданного радиуса г, образующих ¿-кратное (к > 1) покрытие множества М, и указать расположения их центров.

Задача Z3 является обобщением известной задачи N центров для случая к- кратного покрытия. Нетрудно убедиться, что получим следующую минимаксиминную задачу:

min шах mini/(с,., р,),с; е G,l</<iV . cq\

f 1<j<m isJk ' ' (?)

Если G - выпуклое множество, p¡e G, 1 <i < m, и применяется евклидовая метрика, то вместо (9) можно рассматривать задачу: minmaxmind2(c,,p,). Последнюю можно решать, минимизи-

í 1 <jüm is/j '

ш

руя функцию у/с(£) = £ехр[С min ¿2(с,,/?,)], где С - штрафной коэффициент.

Для получения решений с оценкой радиусов выберем Ах (Ах = Ау), построим сетку на G, и пусть В = {£>,•, 1 <;' < п) - множество, состоящее из узлов сетки. Выберем радиус г полученный, например, по алгоритму А 1.4. Тогда получим задачу:

■t.ayZj >к, /=1,..,т; z¡e {0,1,...,к\ 1<;<л1 (10)

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

Для задачи 24 предложен алгоритм решения, основанный на построении сетки на С и сведении к задаче вида (10).

Пусть С (всР) - ограниченное связное множество. Положим, что центры покрывающих кругов могут располагаться в некоторых точках множества С = [ср I < /<ш), Ссб. Требуется ¿-кратно покрыть все множество & Рассмотрим задачи.

(25): Выбрать на множестве С расположение центров N кругов К}, 1 < '] < /V, одинакового радиуса г, образующих

¿-кратное (1 < к < Ы) покрытие множества С таким образом, чтобы их радиус г достигал наименьшего возможного значения.

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

Для решения задачи 25 предложен свой алгоритм, в некоторой степени, аналогичный алгоритму решения задачи (6), и получены оценки для минимального радиуса кругов. Задачу 26 предлагается решать аналогично как задачу ТА.

Также в работе рассмотрены задачи, когда покрывается конечное множество точек, и центры находятся в некоторых из точек конечного множества.

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

Кх2,у2) вводится следующим образом:

с!(5,0 = 1Кр (5-, о = [¿, 1-Х, - х2 [" + ¿2|у, - у2Р ,

где К = (кгк2), ¿,,¿2^0, р>1.Для р = °° полагаем:

0 = ^ О, г) = тах(/г, |дГ[-х2\,к2\у^-у21). Также вводят повороты осей координат на угол в.

Многократные области Вороного в литературе подробно рассмотрены при евклидовой и 1р -метрике. В диссертации рассматриваются области Вороного, в следующей метрике полученной из /кр-метрики:

1/Р

№0 =

х,-х2\Р + к%-у2\>

здесь к, к > 0, - параметр.

Бисектором точеки г при любой метрике называется

множество точек 5(>,/) = {уе Р = Бисекторы точек 5

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

Теорема 3.1. Для множества точек я = {с,,с2,...,си} из Р ¿-кратная (к >1) область Вороного V., 1 < у < п, в Гкр -метрике является звездно-выпуклой областью на Р.

В работе выяснялось (по критерию ошибок измерений) какая из метрик лучше подходит для территории Татарстана. Была установлена предпочтительность 1Крв -метрики. Для выбора параметров

метрик применялся критерий известный под названием Ж-критерий.

Для минимизации 5£>-критерия при подборе параметров взвешенной 1р -метрики и угла поворота осей координат применялась методика, представленная в работе Устера X. Для подбора параметров 1Крв -метрики в работе предложена модернизация метода

работы Устера X., отличие состоит в критерии выбора оптимального угла.

Обозначим территорию Татарстана через G. Для более точного подбора метрик область G была поделена на три части: G, - часть G на левом берегу Волги и правом берегу Камы, G2 - часть G на левых берегах Волги и Камы и G} - часть G, лежащая на правом берегу Волги. Для каждой из областей G,, G2 и G3 подбирались свои параметры указанных метрик. По приведенным выше алгоритмам были рассчитаны параметры для 1Крв -метрики. Полученные значения наборов параметров kt,k2, р и в (в градусах) для G,, G2 и G3 равны соответственно (1,5943; 1,8043; 1,8374; 84), (1,713672; 1,700481; 1,713400, -32) и (1,7502; 1,6612; 1,7223; 8). Значения этих наборов параметров, как известно, для территории США равны (1,1358; 1,1748; 1.6956; 0), а для Канады - (1,9325; 1,3500; 2,2317; 45). В США имеется множество дорог, напоминающих сетку, поэтому параметры к\ и кг близки к единице. Канада менее испещрена дорогами (в ее северной части) поэтому указанные параметры дальше от единицы. Для Татарстана получаем, в некоторой степени, средние значения этих параметров.

Рассмотрим разности действительных (фактических) расстояний и расстояний, измеренных по 1Крв -метрике с полученными параметрами. Эти разности представляют собой ошибки измерений: e{ai = r(aj, а.) - 1Крв (ai, а.;). Полагаем ег (aj ,а}) =

= е(а,,а;.)/г(а,.,я.).

В результате применения критерия Колмогорова-Смирнова-Лиллиефорса было выяснено, что распределение ошибок измерений e^a^aj) ни в одной из областей G,, G2 и G3 не подчиняется

нормальному закону. Для выявления, насколько точно параметры метрики описывают реальные расстояния, важную роль играет построение доверительных интервалов. Нахождение доверительных интервалов осуществлялось с помощью статистического пакета SPSS Statistics.

В работе рассмотрена задача многократного покрытия всей территории Татарстана N зонами обслуживания, для которых расстояние от станций до клиентов можно измерять, используя евклидово расстояние. Получены результаты для различных значений N, когда кратность покрытия к равна 1, 2 и 3.

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

Более шести лет эксплуатируется германская система Fire-Watch. Эта система обеспечивает, по заявлению разработчиков, оптимальный охват для распознавания в радиусе 15 км. В России создается и уже действует в некоторых областях система видеонаблюдения «Лесной Дозор», которая позволяет отследить, по заверению разработчиков системы, расстояние до 25 км. Каждая камера в указанных системах может вращаться на 360 градусов.

Пусть Gj - ранее введенная часть территории Республики Татарстан, из которой дополнительно исключена территория города Казань. Были разработаны программы, и проведены расчеты числа камер наблюдения и возможные места их расположений на Gj. В таблице 1 приведены только некоторые из полученных результатов для N - числа камер при выбранных значениях дальности наблюдения камер - R.

Таблица 1

R, км 15 17 19 20 25 30

N 40 33 27 26 17 13

Рассмотрим указанную в начале автореферата задачу расположения пунктов хранения реагентов для нефтепромыслов. Для решения этой задачи используется 1Крв -метрика. Областью обслуживания выбиралась область С2 без трех районов: Спасского, Алексеевского и Алькеевского. Необходимые числа станций для ¿-кратного (к = 1 или к = 2) обслуживания приведены в таблице 2.

В таблице указаны Я - «радиус» зон обслуживания в 1Крв -метрике,

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

Таблица 2

К - «радиус» зон обслуживания, км к= 1 к = 2

40 ¿V, = 18 N2 = 32

50 N¡=12 N¡ = 21

60 N, = 9 N2= 16

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

В приложении приведены оптимальные расположения кругов, обеспечивающих двукратное покрытие квадрата, при N равных 11, 13, 15, 17, 19 и 21.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Выявлены свойства математических моделей задач покрытия:

• для дискретных моделей получены достаточные условия разрешимости некоторых дискретных задач однократного и многократного покрытия; необходимые и достаточные условия разрешимости для одного из вариантов дискретной задачи многократного покрытия. Также установлены некоторые вспомогательные свойства этих моделей;

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

2. Разработаны численные алгоритмы решения непрерывной задачи многократного покрытия (задачи 21) и решения дискретной задачи многократного покрытия (задачи 22). Решение непрерывной задачи осуществляется комбинированным ис-

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

3. Получены оценки минимальных радиусов покрывающих кругов (для задачи 21).

4. Получены экстремальные и предполагаемые значения радиусов п кругов для двукратного покрытия единичного квадрата при п<9 и п = 11,13,15,17,19,21.

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

6. Выбрана метрика для части регионов территории Татарстана, подобраны параметры этой метрики. Исследованы свойства бисекторов и областей Вороного при выбранной метрике.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ В изданиях, рекомендованных ВАК:

1. Галиев Ш.И., Карпова М.А. Оптимизация многократного покрытия ограниченного множества кругами // Журнал вычисл. матем. и матем. физ. 50. - Москва, 2010. - №7. - С. 757-769.

2. Карпова М.А., Галиев Ш.И. Оптимизация расположения станций обслуживания. Часть 1 // Вестник КГТУ им. А.Н. Туполева. - Казань, 2011. - № 1. - С. 104-109.

3. Карпова М.А., Галиев Ш.И. Оптимизация расположения станций обслуживания. Часть 2 // Вестник КГТУ им. А.Н. Туполева. -Казань, 2011.-№ 2. - С. 67-71.

В других журналах и материалах научно-технических конференций

1. Карпова М.А. Оптимизация расположения станций обслуживания заданной области // Туполевские чтения: Материалы 16-й Междунар. молод, научн. конф. - Казань: КГТУ, 2008. - Т.4. -С.18-20.

2. Карпова М.А. Многократное покрытие заданной области зонами обслуживания // Матем. методы и информ. технологии в экономике, социологии и образовании: Тезисы доклада 21 Междунар. научно-техн. конф. - Пенза, 2008 . - С. 26-28.

3. Карпова М.А. Оптимизация расположения станций обслуживания заданной области с учетом подбора метрики // Туполевские чтения: Материалы 17-й Междунар. молод, научн. конф. - Казань,

2009.-С. 14-16.

4. Галиев Ш.И., Карпова М.А. Многократное покрытие ограниченного множества кругами // Наука в вузах: математика, физика, информатика: Тезисы доклада Междунар. научно-образовательной конф.-Москва, 2009. - С. 338-340.

5. Галиев Ш.И., Карпова М.А. Математические модели для выбора расположения станций обслуживания // Современные достижения в науке и образовании: математика и информатика: Тезисы доклада Междунар. научно-практической конф. - Архангельск,

2010. - С. 225-229.

6. Карпова М.А. Программное обеспечение решения задач многократного покрытия ограниченного множества кругами // Туполевские чтения: Материалы 18-й Междунар. молод, научн. конф-Казань, 2010. - С. 140-142.

7. Карпова М.А. Подбор метрики и оптимизация расположения станций обслуживания на территории Татарстана // Актуальные вопросы современной науки и образования: Тезисы доклада V Общероссийской научно-практической конф. на основе интернет-форума с междунар. участием. - Красноярск, 2010. - С. 168-170.

8. Карпова М.А., Галиев Ш.И. Использование многократных областей Вороного для выбора расположений станций обслуживания // Наука и образование в развитии промышл., социальной и эконом, сфер регионов России: Тезисы докл. 3 Всерос. межвузовской научн. конф. - Муром, 2011. - С. 889-890.

КАРПОВА Марина Александровна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МНОГОКРАТНОГО ПОКРЫТИЯ

Специальность: 05,13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,25. Усл. печ. л. 1,16. Уч. изд. л. 1,0. Тираж 100. Заказ 0108.

Типография Казанского государственного технического университета 420111, Казань, К. Маркса, 10

ВВЕДЕНИЕ.

Глава 1. ЗАДАЧА ПОКРЫТИЯ.

1.1. Постановка задач покрытия.

1.2. Области Вороного.

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

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

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

1.6. Решение непрерывной задачи покрытия.

1.7. Некоторые экстремальные и предполагаемые двукратные покрытия квадрата.

Глава 2. ЗАДАЧИ ПОКРЫТИЯ С ДОПОЛНИТЕЛЬНЫМИ УСЛОВИЯМИ НА ПОЛОЖЕНИЯ ЦЕНТРОВ И НА ПОКРЫВАЕМЫЕ МНОЖЕСТВА.

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

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

2.3. Оптимизация покрытия конечного множества точек, когда центры располагаются в некоторых точках заданного конечного множества.

Глава 3. ОПТИМИЗАЦИЯ РАСПОЛОЖЕНИЙ.

СТАНЦИЙ ОБСЛУЖИВАНИЯ.

3.1. Постановка задачи и математические модели. Используемые метрики.

3.2. Бисекторы и многократные области Вороного для 1Крв-метрики.

3.3. Подбор параметров 1Крв -метрики.

3.4. Вычисление параметров метрики для регионов Татарстана.

3.5. Построение доверительных интервалов.

3.6. Оптимизация расположения станций обслуживания на территории Татарстана.

3.7. Определение числа и расположения видеокамер противопожарной системы наблюдения части территории Татарстана.

3.8. Определение числа пунктов хранения химических реагентов для обслуживания нефтепромыслов.

4.1. Назначение и структура программного комплекса.

4.2. Работа с библиотекой ILOG CPLEX 11.2.

4.3. Интерфейс программного комплекса и методика использования.

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

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

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

При определении расстояний можно использовать готовые матрицы расстояний или геоинформационные системы типа Агс!п&, Мар1пй), Панорама, Агс018 или функции оценки расстояний. Матрицы расстояний и геоинформационные системы сложно использовать для качественного анализа областей обслуживания отдельных станций — областей Вороного. Поэтому во многих работах используются функции для оценки расстояний, которые порождают некоторую метрику- на рассматриваемой области. В литературе используются различные метрики: евклидова, / -метрика, взвешенная /^-метрика [120-122], взвешенная 1р-метрика с возможным поворотом осей координат [121], -метрика [94, 146], манхэттенская [109], московская [107], блок-метрики [149-150] и ряд других метрик. Выбор метрики зависит от свойств рассматриваемой области и существующих связей центра с клиентами. В диссертации выбрана 1Крд -метрика, как наиболее подходящая для регионов Татарстана.

Оптимизации расположения различных станций обслуживания посвящены специальные монографии и большое число статей, исследующих как общие вопросы, так и решение задач для выбранных областей. Например, в ряде работ рассматривается оптимизация расположений станций для отдельных стран (США, Германия, Индия) [58, 62, 81, 82, 88, 120, 144], отдельных регионов или городов и даже для отдельных частей населенных пунктов [69].

Актуальность тематики определяется не только важными разнообразными приложениями задач покрытий, но имеет также самостоятельный математический аспект, ибо к таким задачам (моделям) сводится исследование многих комбинаторных и других задач, см., например, работы [18, 37, 46, 48, 49].

Цель работы

• анализ свойств математических моделей и развитие методов оптимизации многократных покрытий;

• повышение эффективности алгоритмов решения непрерывных и дискретных задач многократного покрытия ограниченных множеств.

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

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

• разработать численные алгоритмы оптимизации числа кругов или (и) их расположения для ^-кратного (к > 1) покрытия заданных областей или заданного конечного множества точек;

• получить оценки насколько далеки результаты решений от глобальных экстремумов;

• подобрать метрики и их параметры для выбранных районов Татарстана;

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

Апробация работы и публикации. Основные результаты исследований опублйкованы в трех статьях [10, 22, 23] в журналах из списка, рекомендованного ВАК РФ. Результаты исследований докладывались и обсуждались на различных конференциях [8, 9, 24—29].

Структура и объем диссертации

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

ЗАКЛЮЧЕНИЕ (ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ)

1. Выявлены свойства математических моделей задач покрытия:

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

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

2. Разработаны численные алгоритмы решения дискретной задачи многократного покрытия и алгоритмы решения непрерывной задачи многократного покрытия. Решение осуществляется комбинированным использованием математических* моделей непрерывных и дискретных задач покрытия.

3. Получены оценки, минимальных радиусов покрывающих кругов.

4. Получены экстремальные и предполагаемые значения радиусов п кругов для двукратного покрытия единичного квадрата при п < 9 и п = 11,13,15,17,19,21.

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

6. Выбрана метрика для части регионов территории Татарстана, подобраны параметры этой метрики. Исследованы свойства бисекторов и областей Вороного при выбранной метрике.

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

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

9. В работе сформулированы и доказаны 5 теорем, 6 лемм и 2 следствия. Имеется справка об использовании результатов работы из Минлесхоза Татарстана и акт внедрения в учебный процесс Казанского национального исследовательского технического университета им. А.Н. Туполева-КАИ.

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

1. Брусов B.C., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журнал вычисл. матем. и матем. физ. -Москва, 1971 (11). -№2. -С. 304-312.

2. Бухараев Р.Г., Захаров В.М. и др. Программная система для анализа методов стохастической геометрии в распознавании образов // Распознавание образов и изображений: Тезисы доклада межд. конф. -Ульяновск: Изд-во УГТУ, 1995. С. 39-41.

3. Галиев Ш.И. Максимин задачи покрытий и упаковок. Казань: Изд-во Казан, гос. техн. ун-та, 1997. - 260 с.

4. Галиев Ш.И. Многократные упаковки и покрытия сферы // Дискретная математика. 1996. - Т. 8. № 3. - С. 148-160.

5. Галиев Ш. И. Направления убывания для минимаксиминных задач // Журнал вычисл. матем. и матем. физ. 1994. - Т. 34. № 3. - С. 323343.

6. Галиев Ш.И., Заботин В.И. О непрерывном обзоре поверхности Земли // Исследование Земли из космоса. 1983. - №1. - С. 117-120.

7. Галиев Ш.И., Карпова М.А. Многократное покрытие ограниченного множества кругами // Наука в вузах: математика, физика, информатика: Тезисы доклада Международной научно-образовательной конференции 23 27 марта 2009 г. - г.Москва, 2009. -С. 338-340.

8. Галиев Ш.И., Карпова М.А. Оптимизация многократного покрытия ограниченного множества кругами // Журнал вычисл. матем. и матем. физ. 2010. - Т. 50. №7. - С. 757-769.

9. Демьянов В.Ф., Васильев JI.B. Недифференцируемая оптимизация. -М.: Наука, Главная редакция физико-математической литературы, 1981.-384 с.

10. Демьянов В.Ф. Минимакс: дифференцируемость по направлениям. -Л., Изд-во Ленингр. ун-та, 1974. 112 с.

11. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.-368 с.

12. Емалетдинова Л.Ю., Галиев Ш.И., М.А.Разина. Нахождение глобального экстремума и субоптимальных решений для задач размещения станций скорой помощи // Вестник КГТУ им. А.Н.Туполева. 2004. - №3. - С. 40^5.

13. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, Главная редакция физико-математической литературы, 1981. 344 с.

14. Еремеев A.B. Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. 2000. - Сер. 2. Т. 7. №1. - С. 47-60.

15. Еремеев A.B., Заозерская Л.А., Колоколов A.A. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования//

16. Дискретный анализ и исследование операций. -2000. Серия 2. Т. 7. № 2. - С. 22^6.

17. Журавлев Ю. И. Избранные труды. М.: Магистр, 1998. 420 с.

18. Заозерская JI.A., Китриноу Е., Колоколов A.A. Задача оптимального размещения центров телекоммуникаций в регионе // Тр. 13 Байкал, междунар. шк.-семинара "Методы оптимизации и их приложения". -Иркутск, 2005. Т. 1. - С. 469-475.

19. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации: Учеб. пособие. — М.: Физматлит, 2005. — 304 с.

20. Кабатянский Г.А., Левенштейн В.И. О границах для упаковки на сфере и в пространстве // Проблемы передачи информации. 1978. -Т. 14. №1.-С. 3-25.

21. Карпова М.А., Галиев Ш.И. Оптимизация расположения станций обслуживания. Часть 1 // Вестник КГТУ им. А.Н. Туполева. 2011. -№ 1. - С. 104-109.

22. Карпова М.А., Галиев Ш.И. Оптимизация расположения станций обслуживания. Часть 2 // Вестник КГТУ им. А.Н. Туполева. 2011. -№2.-С. 67-71.

23. Карпова М.А. Оптимизация расположения станций обслуживания заданной области // Туполевские чтения: Материалы 16-й Междунар. молод, научн. конф. Казань: КГТУ, 2008. - Т.4. - С. 18-20.

24. Карпова М.А. Многократное покрытие заданной области зонами обслуживания // Математические методы и информационные технологии в экономике, социологии и образовании: Тезисы доклада XXI Международной научно-техн. конф. г. Пенза, 2008. - С. 26-28.

25. Карпова М.А. Оптимизация расположения станций обслуживания заданной области с учетом подбора метрики // Туполевские чтения:

26. Материалы 17-й Междунар. молод, научн. конф. Казань, 2009. — С. 14-16.

27. Карпова М.А. Программное обеспечение решения задач многократного покрытия ограниченного множества кругами // Туполевские чтения: Материалы 18-й Междунар. молод, научн. конф.-Казань, 2010.-С. 140-142.

28. Кларк Ф. Оптимизация и негладкий анализ: Пер. с англ. М.: Наука, 1988.-280 с.

29. Ковалев М.М., Пирьянович В.А. Случайный поиск локально-оптимальных планов задач дискретной оптимизации // Вопр. совершенствования планирования и управления народным хозяйством. Минск: НИИЭМП, 1975. С. 215-223.

30. Ковалев М.М. Дискретная оптимизация (целочисленное программирование) Изд. 2-ое, стереотипное. М.: Едиториал УРСС, 2003.- 192 с.

31. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1972. 496 с.

32. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. Т. 1 и 2. М.: Мир, 1990.-415 с.

33. Кониов И.В. Адаптивный алгоритм неявного перебора в задачах дискретной оптимизации // Исслед. по прикл. матем. Казань, 1999. — Вып.21. - С. 140-154.

34. Коннов И.В. Методы недифференцируемой оптимизации. Казань: Казанск. ун-т, 1993. - 100 с.

35. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-429 с.

36. Кузюрин H.H. О сложности построения асимптотически оптимальных покрытий и упаковок // Докл. РАН. 1998. - Т. 363. №1. - С. 11-13.

37. Левенштейн В.И. Границы для упаковок метрических пространств и некоторые их приложения // Проблемы кибернетики. 1983. — Т. 40. — С. 43-110.

38. Леонтьев В.К. Дискретная оптимизация // Журнал вычисл. матем. и матем. физ. 2007. - Т. 47. № 2. - С. 338-352.

39. Михалевич B.C., Гупал A.M., Норкин В.Н. Методы невыпуклой оптимизации. М.: Наука, 1987.-280с.

40. Мухачева Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Дискретный анализ и исследование операций: Материалы конференций. Институт математики СО РАН. Новосибирск, 2002. - С. 80-70.

41. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. САПР раскроя: основные проблемы и опыт их решения // М.: Машиностроение. Вестник компьютерных и информационных технологий. 2004. — № 2. -С. 31^10.

42. Мухачева Э.А., Залгаллер В.А. Линейное программирование в задачах раскроя // Международный журнал программного обеспечения в инженерных знаниях. 1993. - Т. 3. № 4. - С. 463-476.

43. Пиявский С.А. Об оптимизации сетей // Известия АН СССР. Техническая кибернетика. 1968. — №1. — С. 68-80.

44. Роджерс К. Укладки и покрытия. М.: Мир, 1968. 134 с.

45. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Физматлит, 2007. 240 с.

46. Сидельников В.М. О плотнейшей укладке шаров на поверхности п-мерной сферы и числе векторов двоичного кода с заданным кодовым расстоянием // Докл. АН СССР. 1973. - Т. 213. - С. 1029-1032.

47. Фейеш Тот Л. Расположения на плоскости, на сфере и в пространстве. М.: Физматгиз, 1958. 364 с.

48. Финкелыптейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 с.

49. Aardal К., Nemhauser G.L., Weismantel R. Discrete optimization. North Holland, 2005. - 606 pp.

50. Al-Sultan K.S. and Al-Fawzan M.A. A tabu search approach to the uncapacitated facility location problem // Annals of Operations Research. -1999.-V. 86.-C. 91-103.

51. Alves M.L. and Almeida M.T. Simulated annealing algorithm for simple plant location problems // Rev. Invest. 1992. - № 12. - P. 167.j

52. Arya V., Garg N., Khandekar R., Meyerson A., Munagala K. and Pandit V. Local search heuristics for k-median and facility location problems // ACM Symposium on Theory of Computing. 2001. - P. 21-29.

53. Aurenhammer F. Voronoi diagram — a survey of a fundamental geometric data structure // ACM Computing Surveys. 1991. - V.33. №3. - P. 345405.

54. Balas E., Caprrera M.C. A dynamic subgradient-based branch and bound procedure for set covering // Oper. Res. 1996. - V. 44. № 6. - P. 875-890.

55. Balas E., Ho A. Set covering algorithms using cutting planes, heuristics and subgradient optimization: a computational study // Math. Prog. Study. -1980.-V. 12.-P. 37-60.

56. Banerji S.H., Fisher H.B. Hierarchical location analysis for integrated area planning in rural India // Papers of the Regional Science Association 33. -1974.-P. 177-194.

57. Barahona F. and Chudak F.A. Near-optimal solutions to large scale facility location problems // Technical Report, IBM Watson Research Center. -2000.-P. 168, 169, 172.

58. Beasley J. E., Jornston K. Enhancing an algorithm for set covering problems // Europ. J. Oper. Res. 1992. - V. 58. - P. 293-300.

59. Belacel N., Hansen P. and Mlladenovic N. Fuzzy J-means: A new heuristic for fuzzy clustering // Pattern Recognition. 2002. - V. 35. - P. 21932200.

60. Berens W., Korling E.J. Estimating road distances by mathematical functions // European Journal of Operational Research. 1985. - V. 21. - P. 54-56.

61. Bertsimas D., Vohra R. Rounding algorithms for covering problems // Mathematical Programming. 1998. - V. 80. - P. 63-89.

62. Bilde O. and Krarup J. Sharp lower bounds and efficient algorithms for the simple plant location problem // Annals of Discrete Mathematics. 1977. -V. l.-P. 79-97.

63. Brimberg J., Love R. F., Walker J. H. The effect of axis rotation on distance estimation // European Journal of Operational Research. 1995. -V. 80.-P. 357-364.

64. Buharaev R.G., Zaharov V.M., Salimov F.I., Frolov V.B. The model of specialized stohchastic network // Inter. Work shop on mathem. Method and tools in computer simul. Saint-Peter. Msa-bo C-FI rocyHHBepcuTexa, 1994. Preprint MM-94-01. C. 27-29.

65. Caprara A., Fischetti M., Toth P. Algorithms for the set covering problem // DEIS Operations Res. Group. - 1998. - Technical Rep. N OR-98-3. http://citeseer.ist.psu.edu/Caprara 98 algorithms.html

66. Caprara A., Toht P., and Fischetti M. Algorithms for the set covering problem H Annals of Operations Research. 2000. - Vol. 98. - P. 353-371.

67. Carson Y, Butta R. Location an ambulance on the Amherst campus of State University of New York at Buffalo // Interfaces. Vol. 20. - P. 43-49.

68. Ceria S., Nobili P. and Sassano A. A Lagrangian-based heuristic for large-scale set covering problems // Mathematical Programming. -1998. Vol. 81. №2.-P. 215-228.

69. Chen L., Yuan D. Solving a minimum-power covering problem with overlap constraint for cellular network design // European Journal of Operational Research. 2010. - Vol. 203. - P. 714-723.

70. Chudak F.A. Improved approximation algorithms for uncapacitated facility location // In Proceedings of the 6th IPCO Conference. 1998. - P. 180194.

71. Chvatal V. A greedy heuristic for the set covering // Mathematics of Optimization Research. 1979. - Vol. 4. - P. 233-235.

72. Cordone R., Ferrandi F., Sciuto D., Calvo R.W. An efficient heuristic approach to solve the unate covering problem // IEEE Transactions oncomputer-aided design of integrated circuits and systems. 2001. - Vol. 120. № 12.-P. 1377-1387.

73. Coudert O. On solving covering problems // In proceedings of 30th ACM/IEEE Design automation conference. 1996. - P. 197-202.

74. Daskin M.S. Network and discrete location: Models, algorithms, and applications. Wiley, New York, 1995. 520 pp.

75. Drezner Z. (editor). Facility location: A survey of applications and methods. Springer-Verlag, N.Y., 1995. 572 pp.

76. Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin, 2002. P. 233-274.

77. Drezner Z. The p-centre problem heuristic and optimal algorithms // J. OR Soc. - 1984. - Vol. 35. - P. 741-748.

78. Drezner Z. A general global optimization approach for solving location problems in the plane // J Glob. Optim. 2007. - Vol. 37. - P. 305-319.

79. Eaton D., Hector M., Sancher V., Latingua R., Morgan I. Determing ambulance deployment in Santo Doming, Dominican Respublic // Journal of the Operational Research Society. 1986. - Vol. 37. - P. 113-126.

80. Eaton D.J., Daskin M.S., Simmons D., Bulloch B. and Jansma G. Determing emergency medical deployment in Austin. Texas // Interfaces. -1985.-Vol. 15. № l.-P. 96-108.

81. Eremeev A.V., Kolokolov A. A., Zaozerskaya L. A. A hybrid algorithm for set covering // Proc. of Intern, workshop on discrete optimization methods design.-Minsk: S. n., 2000.-P. 123-129.

82. Farahani R. Z., Hekmatfar M. (eds.). Facility location. Concepts, models, algorithms and case studies. Springer-Verlag. - Berlin, Heidelberg. -2009. - 530 pp.

83. Fejes Tot G. Multiple packing and covering of the plane with circles // Acta Math. Acad. Sci. Hungar. 1976. - Vol. 27. № 1-2. - P. 135-140.

84. Fejes Tot G. Multiple packing and covering of spheres // Acta Math. Acad. Sci. Hungar. 1979. - Vol. 34. № 1-2. - P. 165-176.

85. Fisher M.L., Kedia P. Optimal solution of set covering/ partitioning problems using dual heuristics // Management Sci. — 1990. Vol. 36. — P. 674-688.

86. Fugerholt K., Lindstad H. Optimal policies for maintaining a supply service in the Norwegian Sea//0mega.-2000. Vol. 28. № 3.-P. 269 - 275.

87. Fujito T. On combinatorial approximation of covering 0-1 integer programs and partial set cover // Journal of Combinatorial Optimization. -2004. Vol. 8. - P. 439^152.

88. Galinier P. and Heztz A. Solution techniques for the large set covering problem // Discrete applied Mathematics. 2007. - Vol. 155. Issue 3.-P. 312-326.

89. Galv~ao R.D. and Raggi L.A. A method for solving to optimality uncapacitated facility location problems // Annals of Operations Research. — 1989,- Vol. 18.-P. 225-244.

90. Guha S. and Khuller S. Greedy strikes back: Improved facility location algorithms // Journal of Algorithms. -1999. Vol. 31. - P. 228-248.

91. Hall N., Hochbaum D. A fast approximation algorithm for the multicovering problem // Discrete Applied Mathematics. 1989. - Vol. 15. -P. 35-40.

92. Hardy G.H., Littlewood J.E., Polya G. Inequalties. — London: Cambridge University Press, 1934. -312 pp.

93. Hentenryck P. Van and Michel L. A simple tabu search for warehouse location // Technical Report, CS-02-05. Brown University. - 2002. - P. 167, 172.

94. Heppes A. and Melissen H. Covering a rectangle with equal circles // Period. Math. Hungar. 1997. - Vol. 34. - P. 65-81.

95. Hochbaum D. S. In approximation algorithms for NP-hard problem. -1997. D. S. Hochbaum Ed. PWS Publishing Company. - P. 46-93.

96. Hochbaum D. S. Approximation algorithms for set covering and vertex cover problems // SIAM Journal of Computing. — 1982. Vol. 11. — P. 555-556.

97. Iwamura K., Okaday N., Deguchiz Y. Recent advancements of a genetic algorithm to solve the set covering problem. — 2004. P. 392-404.

98. Jain K., Vazirani V.V. Approximation algorithms for metric facility location and A:-median problems using the primal-dual schema and langrangian relaxation // Journal of the ACM. 2001. - V. 48. № 2. - P. 274-296.

99. Jain K., Mahdian M. and Saberi A. A new greedy approach for facility location problems // In Proceedings of the 34th Symposium on Theory of Computing. 2002, forthcoming, 2002. - P. 166.

100. Jandl H., Wieder K. A continuous set covering problem as a quasidifferentiable optimization problem // Optimization. J. of Math. Progr. and Operat. Res. 1988. - V. 19. № 6. - P. 781-802.

101. Johnson D. Approximation algorithms for combinatorial problems // Journal of computer and System Science. 1974. - V. 9. - P. 256-248.

102. Kolokolov A.A., Zaozerskaya L.A. A bicriteria problem of optimal service centers location // Proc. of 12th IFAC intern, symp., St. Etienne (France), 17-19 May 2006. Elsevier, 2006. S. 1.: V. 3. - P. 429^134.

103. Konnov I.V. Equilibrium models and variational inequalities. — Elsevier B.V., Amsterdam, e.a. 2007. - 248 pp.

104. Klein R. Voronoi diagrams in the Moscow metric // Graph-Theoretic Concepts in Computer Science International Workshop WG'88. Amsterdam June 15-17, 1988. Proceedings. P. 432^141.

105. Klose A., Drexl A. Facility location models for distribution system design // European Journal of Operational Research. 2004. - V. 162. - P. 4-29.

106. Kolesar P., Walker W. and Hausner J. Determining the relation between fire engine travel times and travel distanses in New York city // Operational Research. 1975. - V. 23. - P. 614-625.

107. Korupolu M.R., C.G. Plaxton and Rajaraman R. Analysis of a local search heuristic for facility location problems // In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. -1998. P. 1-10.

108. Kratica J., Tosic D. and Filipovic V. Solving the uncapacitated warehouse location problem by sga with add-heuristic // In XV ECPD International Conference on Material Handling and Warehousing, 1998. -P. 167.

109. Kratica J., Tosic D., Filipovic V. and Ljubic I. Solving the simple plant location problem by genetic algorithm // RAIRO Operations Research. -2001.-V. 35.-P. 127-142.

110. Kratica J., Filipovic V., Sesum V. and Tosic D. Solving the uncapacitated warehouse location problem using a simple genetic algorithm // In Proceedings of the XIV International Conference on Material Handling and Warehousing. -1996. P. 3.33-3.37.

111. Kupper A. Location-based services. Fundamentals and Operation. John Wiley & Sons, Ltd. - 2005. - 368 pp.

112. Lee D.T. and Wong C.K. Voronoi diagrams in Z, metrics with 2dimensional storage applications // SIAM J. COMPUT. -1980. V. 9. - P. 200-211.

113. Lee D.T. Two-dimensional Voronoi diagrams in the Lp -metric // JACM. 1980.-V. 27.-P. 604-618.

114. Lifschitz V., Pittel B. The worst and the most probable performance of a class of set-covering algorithms // SIAM J. Comput. 1983. - V. 12. № 2. -P. 329-346.

115. Lilliefors H.W. On the Kolmogorov-Smirnov test for normally with mean and variance unknown // American Statistical Association Journal. — 1967.-P. 399-402.

116. Love R. F., Uster H. A statistical comparasion of three goodness-of-fit criteria used in modelling distances // Journal of Applied Mathematics and Decision Sciences. -2001. -V.5 № 4. P. 235-251.

117. Love R.F., Morris J.G. Mathematical models of road travel distances // Mamagement Science. 1979. - V. 25. - P. 130-139.

118. Love R.F., Morris J.G. Modeling inter-city road distances by mathematical models // Operational Research Quarterly. —1972. — V. 23. — P. 61-71.

119. Love R.F., Morris J.G. On estimating road distances by mathematical functions // European Journal of Operational Research. 1988. - V. 36. - P. 251-253.

120. Mahdian M., Marakakis E., Sabieri A. and. Vazirani V.V. A greedy facility location algorithm analyzed using dual fitting // In Proceedings of 5th International Workshop on Randomization and Approximation

121. Techniques in Computer Science, Lecture Notes in Computer Science. v. 2129. - Springer-Verlag, 2001. - P. 127-133.

122. Mahdian M., Ye Y. and Zhang J. Improved approximation algorithms for metric facility location problems // In Proceedings of the 5th APPROX• Conference, Lecture Notes in Computer Science. — v. 2462. 2002. - P.229.242.

123. Melissen H. Loosest circle coverings of an equilateral triangle // Math. Mag. 1997. - V. 70. - P. 119-125.

124. Melissen J.B.M. and Schuur P.C. Covering a rectangle with six and seven circles // Discrete Appl. Math. 2000. - V. 99. - P. 149-156.

125. Melissen J.B.M. and Schuur P.C. Improved coverings of a square with six and eight equal circles // Electron. J. Combin. 1996. - 3. R32. - 10 pp. (electronic).

126. Mirchandani P.B., Francis R.L. (eds) Discrete location theory. Wiley, New York. - 1990. - 576 pp.

127. Molin P., Abdi H. New Tables and numerical approximation for the Kolmogorov-Smimov/Littlefors/Van Soest test of normality // Technical report, University of Bourgogne // www.utd.edu/wherve/MolinAbdil998-LittleforsTechReport.pdf

128. Murray A. T., K. Kim, J. W. Davis, R. Machiraju, R. Parent. Coverage optimization to support security monitoring // Computers, Environment and Urban Systems.-2007.-V. 31.-P. 133-147.

129. Nickel S., Justo P. Location theory: a unified approach. SpringerVerlag. - Berlin, Heidelberg. - 2005. - 434 pp.

130. Novaesa A.G.N., Souza de Cursib J.E., A.C.L. da Silvac, Souzaa J. C. Solving continuous location-districting problems with Voronoi diagrams // Computers & Operations Research. 2009. - V. 36. - P. 40-59.c

131. Nurmella K.J. Conjectually optimal covering of an equilateral triangle with up to 36 equal circles // Experiment. Math. 2000. - V. 9. № 2. - P. 241-250.

132. Oded B., Drezner Z., Krass D., Wesolowsky G.O. The variable radius covering problem // European Journal of Operational Research. 2009. — V. 196.-P. 516-525.

133. Rahoual M., Hadji R., Bachelet V. Parallel ant system for the set covering problem // Lecture notes in computer science. S. 1.: Springer, 2002.-P. 262-267.

134. Repede J.F., Bernardo J.J. Developing and validating a decision support system for location emergency medical vehicles in Louisville, Kentucky // European Journal of Operational Research. 1994. — V. 40. - P. 58-69.

135. ReVelle C.S., Eiselt H.A., Location analysis: A synthesis and survey // European Journal of Operational Research. 2005. - V. 165. - P. 1-19.

136. ReVelle C.S., Eiselt H.A., Daskin M.S., A bibliography for some fundamental problem categories in discrete location science // European Journal of Operational Research. 2008. - 184. - P. 817-848.

137. Schiller J., Voisard A. Location-based services-Elsevier, 2004. 256p.

138. Solar M. Parada V., Urrutia R. A parallel genetic algorithm to solve the set-covering problem // Computer and Operations Research. 2002. - V. 29.-P. 1221-1235.

139. Sun M. A tabu search heuristic procedure for the uncapacitated facility location problem. In C. Rego and B. Alidaee (eds.) Adaptive Memory and Evolution: Tabu Search and Scatter Search, Kluwer Academic Publishers, forthcoming. 2002. - 167 pp.

140. Sviridenko M. An improved approximation algorithm for the metric uncapacitated facility location problem // In Proceedings of the 10th IPCO Conference, Lecture Notes in Computer Science. V. 2337. - 2002. - V. 166.-P. 230-239.

141. Talmar M. Location of rescue helicopters in South Tyrol // Papers Presented at 37th Annual ORSNZ Conference. Auckland, New Zealand. -2001.-386 p.

142. Tarnai T. and Gaspar Zs. Covering a square by equal circles // Elem. Math. -1995. V. 50. - P. 167-170.

143. Uster H., Love R.F. Application of weighted sum of order p to distance estimation // HE Transactions. 2001. - V. 33. № 8. - P. 675-684.

144. Uster H., Love R.F. Formulation of confidence intervals for estimated actual distances// Eur. J. Oper. Res. 2003. - V. 151. - P. 586 - 601.

145. Uster H., Love R.F. Application of weighted sum of order p»to distance estimation // HE Transactions. 200. - V.33. № 8. - P. 675-684.

146. Ward J.E., Wendell R.E. A new norm for measuring distance which yields linear location problems // Operations Research. 1980. - Vol. 28, № 3, Part II, May-June. - P. 836-844.

147. Ward James E., Richard E. Wendell. Using block norms for location modeling // Operations Research. 1985. - V. 33. - P. 1074-1090.

148. Zahn. C. T. Black box maximization of circular coverage // J. Res. Nat. Bur. Standards Sect. B. 1962. -V. 66. - P. 181-216.152. www2stetson.edu/~efriedma/packing.html153. http:// www.fire-watch.de154. http:// www.lesdozor.ru