научная статья по теме БЛИЗКОЕ К ОПТИМАЛЬНОМУ НЕПОЛНОЕ ПОКРЫТИЕ СФЕРЫ ОБОБЩЕННЫМИ СФЕРИЧЕСКИМИ СЕГМЕНТАМИ Математика

Текст научной статьи на тему «БЛИЗКОЕ К ОПТИМАЛЬНОМУ НЕПОЛНОЕ ПОКРЫТИЕ СФЕРЫ ОБОБЩЕННЫМИ СФЕРИЧЕСКИМИ СЕГМЕНТАМИ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 7, с. 1125-1135

УДК 519.147

БЛИЗКОЕ К ОПТИМАЛЬНОМУ НЕПОЛНОЕ ПОКРЫТИЕ СФЕРЫ ОБОБЩЕННЫМИ СФЕРИЧЕСКИМИ СЕГМЕНТАМИ

© 2015 г. А. M. Дуллиев

(420111 Казань, ул. К. Маркса, 10, КНИТУим. А.Н. Туполева (КАИ)) e-mail: dulliev@yandex.ru Поступила в редакцию 12.07.2014 г.

Переработанный вариант 19.11.2014 г.

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

Ключевые слова: неполное покрытие сферы, обобщенный сферический сегмент, круговой конус, численный метод оптимизации, кратный минимакс.

DOI: 10.7868/S0044466915070066

1. ВВЕДЕНИЕ

Пусть имеется некоторое множество XФ 0 и некоторое семейство {Q} множеств Q. Говорят, что семейство {Q,} покрывает множество X, если Xс ^ Qt. При выполнении более слабого условия

X n (^ Qt) Ф 0 говорят о неполном покрытии. Если имеет место обратное включение: ^ Qt с X,

то говорят, что {Q,} вписано в X. Ясно, что из вписанности {Q,} в X и непустоты хотя бы одного из множеств Qi следует, что {Q,} неполно покрывает X, но не наоборот. Всюду далее полагаем, что множество индексов i конечно: i = 1, ..., N.

Обычно множества Xи Qi считаются принадлежащими некоторым классам множеств, наделенных той или иной структурой. Среди них особо выделяются те, которые позволяют каким-либо образом сравнивать между собой произвольные {Q,} и {Q}. При этом, например, естественно считать, что неполное покрытие тем лучше, чем меньше непокрытая им часть множества X. Для измерения качества покрытия используются те или иные функционалы, построенные с использованием особенностей структур множеств X и Q. К сожалению, применяемые на сегодняшний день функционалы в подавляющей своей части либо сложно устроены, либо обладают весьма небольшим набором свойств, которые мало что могут дать при желании воспользоваться ими для выявления других значимых свойств посредством аналитических (не численных) методов. Вместе с тем исследование многих из них довольно хорошо осуществляется численными методами, которые зачастую допускают очень простую программную реализацию на вычислительных устройствах. Весьма отчетливо это проявляется при простых множествах Xи Q, например, когда X и Qi — параллелепипеды, шары или сферы. Причем как для простых, так и для более сложных множеств весьма остро стоит вопрос о выборе того или иного численного метода. И здесь, как правило, предпочтительнее те из них, которые требуют меньших вычислительных затрат, что нередко приводит к необходимости привлечения специальных методов.

После того как выбран некоторый функционал качества покрытия, как правило, ставится задача об оптимальном выборе параметров семейства {Q}. Среди них, в частности, можно отметить следующие: число покрывающих множеств, их размеры, положение в пространстве, равномерность покрытия, кратность покрытия и т.д. При решении этих задач используются различные подходы, некоторые из которых ввиду очевидной сложности оптимизационных задач базируются на эвристических соображениях. Последние, хоть и не имеют строгого математического обоснования, позволяют создавать весьма эффективные численные методы решения. Здесь достаточно упомянуть работы [1]—[4]. В первых двух исследуется задача покрытия множества на плоскости кругами, где основная оптимизационная задача редуцируется к линейной задаче целочисленного программирования. В [3], [4] исследуется задача покрытия сферы круговыми сегментами, причем в [3] используются области Вороного и сглаживание целевой функции, а в [4] применяется теоретико-групповой подход анализа параметров покрывающих множеств.

В настоящей статье рассматривается задача покрытия двумерной сферы так называемыми обобщенными сферическими сегментами — множествами, получающимися в результате пересечения сферы с конусом, вершина которого находится внутри сферы (см. [5]); при этом на множество конусов нами накладывается требование, чтобы все конусы являлись круговыми, а вершины располагались на некоторой концентрической сфере меньшего радиуса. К настоящему времени более или менее изучены лишь задачи покрытия сферы круговыми сегментами (см., например, [6] и имеющуюся там библиографию). Что касается обобщенных сферических сегментов, то использование уже имеющихся подходов затруднительно, ибо в отличие от круговых сегментов они даже не гомотетичны — их форма и размер напрямую зависят от параметров конусов, их определяющих. Вначале нами строится минимаксный функционал качества покрытия и на основании результатов из [5] предлагается численный способ его нахождения. Далее рассматривается оптимальная задача выбора осей конусов, обеспечивающих наилучшее покрытие сферы. Привлечением геометрических соображений, основанных на некоторой симметрии расположения осей конусов, она редуцируется к аналогичной задаче очень малой размерности. Такой подход позволяет резко сократить объем вычислений по сравнению с исходной задачей. В заключительной части работы предложенная методика численного анализа задачи покрытия иллюстрируется несколькими примерами.

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

2. ПОСТАНОВКА ПРОБЛЕМЫ

Пусть S и S' с [3 — две сферы с центром в нуле радиусов 1 и r < 1 соответственно. Через Kс [n будем обозначать замкнутый круговой конус с углом раствора а е (0, я), ось вращения которого задается единичным вектором n, причем intKФ 0, Kn (—K) = {0}, n е K. На сфере S' выбраны N точек ci. Для каждой из них построен конус ci + K таким образом, чтобы 0 g ci + K. (Не исключен случай, когда S n (с,- + K)\{c ;} Ф 0.) Конусы Cj + K пересекают сферу Sпо множествам Q. Требуется определить, насколько хорошо множество Q = t Qi покрывает S, т.е. как малы непокрытые множествами Q, участки S, а также определить параметры осей конусов K, i = 1, ..., N, обеспечивающих наилучшее неполное покрытие S. Поскольку Qi с S, то, очевидно, неполное покрытие сферы S семейством {Q,-} эквивалентно вписанности в нее этого семейства.

Перечислим некоторые используемые далее в тексте обозначения. Через cl, int, fr, ö, lin обозначим операторы топологического замыкания, внутренности, границы, края и линейной оболочки соответственно. Под х будем понимать векторное произведение в [3, а под (,) и || || — скалярное произведение и соответствующую ему норму. Угол между векторами х и у обозначим через Z(x, y).

В качестве критерия качества покрытия можно выбирать различные функционалы. Как правило, они связаны либо с площадями областей Qi, либо с угловой удаленностью точек множества S\Q от множеств Qi. В настоящей работе нами выбран второй функционал ввиду простоты его построения и дальнейшего анализа. Опишем его подробнее.

Угловой удаленностью, или расстоянием точки x е S от множества Q, будем, как это принято, называть число minZ(x, y). Оно определено корректно ввиду компактности Q, Угловую удален-

У е Q,

ность точки x е S от множества Q определим как min minZ(x, y). Наконец, качество покрытия

i = 1, ..., Ny е Qt

множества S множеством Q будем измерять функционалом

/(nb..., nN) = max min minZ(x,y).

x е S i= 1, ..., Ny е Qt

Поскольку ||x|| = \\y || = 1, то угловая метрика Z(x, y) может быть без потери общности заменена

на скалярное произведение (x, y) с заменой min на max и наоборот. Функция /{пь ..., nN) перейдет в функцию

f(n1, ..., nN) = min max max(x, y). (2.1)

x е Si = 1, ..., Ny е Qt

Ясно, что чем меньше f (больше f), тем лучше множество Q вписано в S. В частности, при / = 0 (f =1) оно покрывает всю сферу S. Наряду с функцией (2.1) при A с S также будем рассматривать функцию вида

fA(n1, ..., nN) = min max max(x,y), A с S. (2.2)

x е At = 1, ..., Ny е Qt

3. ВЫЧИСЛЕНИЕ КРИТЕРИАЛЬНОЙ ФУНКЦИИ

Сначала займемся вопросом о вычислении значений функцииf Легко видеть, что здесь основная сложность связана с решением задач max и min . Первую задачу можно рассматривать

y е Qi x е S

как задачу минимизации линейной функции g(y) = — (x, y) на обобщенном сферическом сегменте Q, Решать ее можно различными способами. Поскольку решение y* записать в явной форме весьма затруднительно и, возможно, вряд ли удастся — нужно для этого решить систему из четырех уравнений (см. ниже), — то желательно воспользоваться каким-нибудь численным методом.

Прежде чем остановить свой выбор на том или ином методе, заметим, что минимизацию g(y) при x £ Qi достаточно произвести не на всем множестве Q, а только по его краю dQ j = S n frK. Действительно, для любой точки г е S n intK плоскость lin{x, z} пересекает край dQj в двух точках yi(z) и y2(z), для которых Z(x, yi(z)) <Z(x, z) < Z(x, y2(z)). Запишем эту задачу в виде задачи на минимум с ограничениями типа равенств, опуская в ней, а также всюду ниже в данном разделе, нижние индексы у символов c и n, определяющих конус cj + Kf.

-(x, y) —► min, (3.1)

||y|| = 1, (n, y - c) = ||y - 4 cos(a/2). (3.2)

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком