Модели решения задач построения и идентификации геометрического размещения: Исследование, алгоритмы, применения тема диссертации и автореферата по ВАК РФ 05.13.16, доктор физико-математических наук Панюков, Анатолий Васильевич

• Панюков, Анатолий Васильевич
• доктор физико-математических наук
• 1999

Оглавление диссертации доктор физико-математических наук Панюков, Анатолий Васильевич

Введение

1 Задачи построения размещения точечных объектов

1.1. Вычислительная сложность задачи Вебера.

1.2. Представление задачи Вебера в виде ЦЛП задачи

1.3. Релаксированная задача Вебера и ее многогранник

1.4. Алгоритм для задачи Вебера.

1.5. Задача Вебера для древовидной сети.

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

1.5.2. Случай алгоритмического представления функции Ь

1.5.3. Свойство релаксакционного многогранника.

1.6. Выводы.

2 Топологические методы решения задачи Штейнера

2.1. Декомпозиция задачи Штейнера.

2.2. Алгоритм для задачи Т-оптимизации

2.3. Применение Т-оптимизации в схеме метода ветвей и границ

2.3.1. Дерево решений.

2.3.2. Нижняя оценка

2.3.3. Допустимые топологии.

2.4. Выводы.

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

3.1. Декомпозиция задачи размещения прямоугольных объектов

3.2. Локальная оптимизация в евклидовом пространстве

3.3. Локальная оптимизация в метрических комбинаторных пространствах.

3.4. Генератор конкурентоспособных вариантов решения задачи размещения прямоугольных объектов

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

3.6. Выводы.

4 Техника программной реализации задачи построения оптимального потока

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

4.2. Прямой симплекс-алгоритм

4.3. Структуры данных.

4.4. Конструктор и деструктор. Построение начального базисного решения.

4.5. Метод Solve.

4.6. Изучение базисного дерева.

4.7. Ведущее преобразование.

4.8. Метод Perturb.

4.9. Пример.

4.10. Выводы.

5 Неатомические задачи размещения протяженных объектов

5.1. Неатомические задачи размещения протяженных объектов

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

5.1.2. Аппроксимация неатомической задачи общего вида задачей с конечным числом классов ^-эквивалентности

5.1.3. Анализ задачи с конечным числом классов ^-эквивалентности

5.1.4. Задача размещения равнозначных объектов на плоскости с манхеттеновым расстоянием.

5.1.5. Модельные задачи плотного размещения двух равновеликих взаимосвязанных множеств

5.2. Выводы.

6 Идентификация размещения точечного источника электромагнитного поля

6.1. Математическая модель задачи.

6.2. Местоопределение эквивалентного диполя по параметрам и, v, а.

6.2.1. Однопунктовое местоопределение.

6.2.2. Многопунктовое местоопределение.

6.3. Методы пеленгования грозовых разрядов

6.3.1. Определение псевдопеленга (р.

6.3.2. Исследование погрешности алгоритма определения псевдопеленга <р.

6.4. Прямой метод определения параметров и, V и а

6.4.1. Формирование сигналов е(£), Вычисление параметров ё\. и Ь,1.

6.4.2. Вероятностные характеристики параметров е* и к = 0,1,2.

6.4.3. Погрешность измерения расстояния

6.5. Оптимизационные параметрические методы

6.6. Экстремальные непараметрические методы определения параметров и, V и а.

6.6.1. Экстремальный метод определения параметров системы линейных функциональных уравнений по ее правой части.

6.6.2. Определение параметров и, V и а

6.7. Выводы.

Введение диссертации (часть автореферата) на тему «Модели решения задач построения и идентификации геометрического размещения: Исследование, алгоритмы, применения»

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

При моделировании проблем размещения в исследуемых системах выделяются следующие объекты: (1) множество 3 элементов, называемых размещаемыми (размещенными); (2) множество V, предназначенное для размещения элементов множества 3\ (3) множество И возможных размещении, являющееся подмножеством множества У всех отображений в V; (4) логико-предметный язык Ь для описания множеств «7, V, И и отношений между их элементами. После чего ставится задача размещения С — («7, V, - найти /(«/) : / £ Б. В данных терминах могут быть сформулированы задачи из самых разных областей, в частности, задачи проектирования, прогнозирования, планирования, определения местоположения источников физических полей и т. д.

Наиболее изученной является простейшая задача размещения и ее вариации. Здесь следует отметить работы В.Л. Береснева, Э.Х. Гима-ди, В.Г. Дементьева, В.П. Гришухина, В.А. Бмеличева, В.А. Трубина, В.Р.Хачатурова. Другой известной математической моделью задач размещения является квадратичная задача о назначении. Многие существенно упрощённые частные случаи квадратичной задачи о назначении остаются Л/^-трудными в сильном смысле. Некоторые полиномиально разрешимые частные случаи квадратичной задачи о назначении найдены М.А.Иорданским и Г.Г.Забудским. Идейно близкой к квадратичной задаче о назначении является задача Вебера. Для задачи Вебера полностью исследованы лишь частные случаи, когда пространством для размещения является К2 с прямоугольной метрикой (В.А.Трубин, Д.К.Замбицкий и Д.Д.Лозовану, Н.Ь.Ггапаэ, Л.А.\У11^е) и евклидовой метрикой (В.А.Вит-тих, Б.В.Калинин, В.А.Цыбатов, Н.\¥.Юшп, Ы.Е.Киеппе). В тоже время большое число практических задач требуют эффективных алгоритмов решения задачи Вебера общего вида.

Математическими моделями проблем размещения линейных объектов являются задачи маршрутизации в графах и задачи синтеза транспортной сети. Наиболее сложными задачами маршрутизации являются задачи типа комивояжера. Подобные задачи рассмотрены в работах И.X.Сигала, И.И Меламеда, С.И.Сергеева и др. авторов. Наиболее сложными задачами синтеза транспортной сети являются задачи типа Штейнера. Особенностями большого числа важных для практики задач Штейнера являются: 1) мощность множества V всех вершин существенно больше мощности множества <2 терминальных вершин; 2) граф (У, Е) в условиях задачи представляет математическую модель территории и поэтому, как правило, разрежен, достаточно регулярен и близок к планарному. Для решения подобных задач могут быть использованы: асимптотически оптимальный алгоритм А.И.Брзина; приближенные алгоритмы А.В.Злотова и В.Р.Хачатурова; эвристические алгоритмы Д.Т.Лотарева. Все отмеченные алгоритмы не являются точными. Более того, они не гарантируют, что построенное решение является локальным экстремумом, т.е. лучшим среди решений определенного множества. Вопрос построения эффективных локальных алгоритмов для задачи Штейнера и ее обобщений оставался открытым.

Математической моделью многих проблем размещения плоских объектов является задача размещения прямоугольных объектов с минимальной длиной связывающей сети. Большинство эвристических и стохастических алгоритмов размещения прямоугольных объектов использует метод последовательно-одиночного размещения (И.О.Ахмедов, Л.Н.Плужников, И.Х.Сигал, Ю.Г.Стоян). Основным недостатком метода последовательно-одиночного размещения является недостаточное качество построенных с его помощью решений, в частности из-за неудачного выбора последовательности размещения объектов и из-за жесткой фиксации ранее размещенных объектов. Первая из указанных причин устраняется использованием метода последовательно-одиночного размещения в совокупности с методами оптимизации на перестановках, определяющих последовательность размещения объектов (Ю.Г.Стоян, 1979). Тем не менее, остается невозможность гарантированного построения локального экстремума задачи. Точные алгоритмы решения задачи размещения прямоугольных объектов используют формализацию данной задачи в виде задачи целочисленного линейного программирования (С.В.Жак, А.Б.Зинченко). Недостатком указанного подхода является большая размерность вектора двоичных переменных, причем отдельному размещению из п объектов могут соответствовать 0(4П ) различных векторов двоичных переменных, что делает эффективность данных алгоритмов особенно низкой для задач, имеющих достаточно много допустимых решений. В этом случае более целесообразной представляется попытка улучшения качества текущего решения более эффективными алгоритмами локальной оптимизации. Однако вопрос построения эффективных локальных алгоритмов для данной задачи оставался открытым.

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

Задача идентификации размещения, заключающаяся в локализации источника физического поля по результатам наблюдения в некоторых точках, относится к классу обратных задач. Основная сложность, возникающая при разработке методов решения обратных задач состоит в нахождении корректных формулировок условий задачи и построении устойчивых (т.е. мало чувствительных к погрешностям моделирования) алгоритмов. Общие методы решения обратных задач рассмотрены в монографиях А.Н.Тихонова и В.Я.Арсенина; А.М.Денисова; В.А.Морозова; В.В.Васина, В.К.Иванова и В.П.Тананы; М.М.Лаврентьева и в других работах. Однако прямое использование описанных приемов приводит к сложным итеративным процедурам, имеющим зачастую недостаточную скорость сходимости. Для получения более эффективных устойчивых алгоритмов необходимо учитывать специфику задачи. В работе подробно рассматривается задача определения координат точки размещения произвольно ориентированного электрического диполя по результатам од-нопунктового наблюдения индуцируемого им электромагнитного поля. Практическая значимость данной модели состоит в том, что она адекватно описывает задачу местоопределения гроз для расстояний от ЗОкМ до 150кМ. Данный факт имеет теоретическое обоснование (М.АМтап, 1969; И.И.Кононов, 1970 г.) и подтвержден многочисленными практическими экспериментами, проведенными ГГО им. А. И. Воейкова, с использованием выпускавшегося отечественной промышленностью грозопеленгатора-дальномера "Очаг 2П". Алгоритмы местоопределения, использованные в изделии "Очаг 2П", предполагают вертикальность эквивалентного диполя грозового разряда. Эти эксперименты показали возможность получения значительных ошибок, обусловленных принятием гипотезы о вертикальности эквивалентного диполя источника излучения. Многочисленные попытки получения устойчивых алгоритмов местоопределения произвольно ориентированного электрического диполя оказывались неудачными. В диссертационной работе проведен математический анализ задачи, подтвердивший существенное влияние ориентации эквивалентного диполя на результаты измерения с помощью изделия "Очаг 2П", и найдены устойчивые алгоритмы решения задачи локализации дипольного источника излучения.

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

Цель и задачи исследования. Целью работы является разработка математических моделей, алгоритмов, программного обеспечения задач построения и идентификации геометрического размещения, их применения при проектировании объектов строительства и транспортных коммуникаций, а также для проблем местоопределения гроз. Для получения эффективных решений перечисленных проблем в диссертации поставлены задачи: 1) провести исследование задачи Вебера для конечного множества; задачи размещения древовидной сети; задачи синтеза транспортной сети на цифровой модели местности; задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети; методов качественного анализа оптимальных размещений; задачи местоопределения электрического диполя по индуцируемому им электромагнитному полю; 2) на основе проведенных исследований разработать программное обеспечение.

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

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

1. Доказана ЛЛР-трудность задачи Вебера и квазицелочисленность ее релаксационного многогранника. Разработан псевдополиномиальный алгоритм для задачи Вебера общего вида и полиномиальный алгоритм для случая размещения ациклической сети.

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

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

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

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

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

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

Практическая ценность и реализация результатов работы.

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

1. Решение задачи Вебера на графе для древовидной связывающей сети. Библиотека программных модулей [24].

2. Локально оптимальное размещение прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль [66].

3. Оптимальное размещение прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль [70].

4. Построение конкурентоспособных вариантов решения задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль [73].

5. Комплекс программ для системы местоопределения грозовых очагов в ближней зоне ("Гроза ") [82].

Результаты технического характера, полученные совместно с сотрудниками ЗАО "НИИИТРК", защищены авторскими свидетельствами СССР [1]- [12]

Результаты работы внедрены

• ЗАО "Гипротюменнефтегаз" в технологическую линию проектирования нефтяных и газовых месторождений Западной Сибири;

• ЗАО "НИИИТРК" в грозопеленгатор-дальномер "Очаг";

• в учебный процесс ЮУрГУ.

Связь работы с государственными программами. Часть исследований выполненно при проведении работ на кафедре прикладной математики Челябинского политехнического института им. Ленинского комсомола, связанных с разработкой математических моделей обустройства нефтяных месторождений Западной Сибири и соответствующего программного обеспечения для САПР "Нефть" института Гипротюменнеф-тегаз. Данные работы выполнялись в соответствии с планом научно-исследовательских работ по программе ГКНТ СССР ОЦ.026 (раздел 03.02.06), хоздоговорным и госбюджетным темам n0 ГР 01.820.075.098 (инв. NN отчетов во ВНТИЦ 02820061397, 02830064614, 02840081991), n0 ГР 01.960.009489 (инв. n0 отчета во ВНТИЦ 02970000159), n0 ГР 01.940.004404 (инв. n0 отчета во ВНТИЦ 0250001193).

В период с 1992-95 гг. под руководством автора проводились исследования по теме диссертации, финансировавшиеся грантом 93-1-109-29 конкурсного центра по исследованиям в областях математики и физики Госкомвуза РФ (соруководитель) и грантом конкурсного центра по исследованиям в области радиоэлектроники Госкомвуза РФ. В настоящее время работы по теме диссертации финансируются грантом 45Гр-98 конкурсного центра по грантам в области энергетики и электротехники при МЭИ (n0 ГР 01.980006959) и госбюджетной темой n0 ГР 01.980006118.

Апробация работы« Основные результаты и положения работы докладывались и обсуждались на следующих научных мероприятиях:

• П (Улан-Удэ, 1982) и Ш (Ташкент, 1984) Всесоюзные совещания "Методы и программы решения оптимизационных задач на графах и сетях" ;

• VIII (Нарва-Йыэссуу, 1984) IX (Минск, 1986), X (Нарва-Йыэссуу, 1988 г.) и ХП (Нарва-Йыэссуу, 1992) всесоюзные симпозиумы "Системы программного обеспечения решения задач оптимального планирования" ;

• VI (Свердловск, 1989), VП (Свердловск, 1991), VIII (Екатеринбург, 1993), IX (Екатеринбург, 1995), X (Екатеринбург, 1997) и XI (Екатеринбург, 1999) конференции Ассоциации математического программирования;

• IX (Тернополь, 1984), XI (Челябинск, 1986), ХП (Тамбов, 1987) и VXI (Нижний Новгород, 1991) Всесоюзные школы по теории операторов в функциональных пространствах;

• Ш (Звенигород, 1985) и V (Звенигород, 1990) Всесоюзные семинары "Методы синтеза и планирования развития структур крупномасштабных систем"

• Всесоюзные семинары "Применение автоматизированных систем в проектировании объектов строительства" (ЦНИПИАСС Госстроя СССР, Новосибирск, 1981); "Программное обеспечения для гибких автоматизированных производств" (Центрпрограммсистем, Калинин, 1985); П школа-семинар по вопросам автоматизированного проектирования объектов строительства (РИСИ, Туапсе, 1987 г.); П всесоюзный семинар "Роботы и гибкие производственные системы" (ИПУ АН СССР, Челябинск, 1988); IX Всесоюзное совещание по проблемам управления (ИПУ АН СССР, Ереван, 1983); IV всесоюзный симпозиум по атмосферному электричеству (Нальчик, 1990);

• II республиканская конференция "Проблемы вычислительной математики и автоматизации научных исследований" (Ин-т математики Казахской ССР, Алма-Ата, 1988); Республиканское совещание "Численные методы и средства проектирования и испытания элементов твердотельной электроники" (ТГТУ, Таллинн, 1989);

• Конференция " Обратные и некорректно поставленные задачи" (МГУ, Москва, 1998);

• IV Международный конгресс по вычислительной и прикладной математике (Льювен, Бельгия, 1990);

• международные конференции: - IX ICAE (Санкт-Петербург, 1992); "Актуальные проблемы фундаментальных наук" (Москва, 1994); "Комбинаторная оптимизация - 94" (Амстердам, Нидерланды, 1994); "Математические алгоритмы" (Нижний Новгород, 1995); "Параметрическая идентификация и обратные задачи гидрологии, геологии и экологии" (Карлсруэ, Германия); "Обратные и некорректно поставленные задачи" (Москва, 1996); XXIII ICLP (Флоренция, Италия, 1996); XXIVICLP (Бирмингам, Великобритания, 1998); SCOR-98 (Новосибирск, 1998); "Nonsmooth and discontinuous problems of control and optimization" (Челябинск, 1998);

• XI Международная Байкальской школа-семинар (Иркутск, 1998).

Публикации. По теме диссертации опубликовано более 100 работ. В их числе - 24 авторских свидетельств на изобретения и зарегистрированных программ для ЭВМ; 17 статей в рецензируемых журналах; 4 учебных пособия.

Первая глава работы посвящена задаче построения оптимального размещения конечного множества взаимосвязанных точечных объектов (.задаче Вебера) Q(G,V,b,c), которая состоит в нахождении р* = arg min £ c(j, <p(j)) + £ Ь([г, j], <p(i), <p(j)) v j&j [i,j]eE для заданного графа G = (J, E), множества V, симметричного отображения Ь : Е х V2 —> Z, и отображения с : J х V Z.

Данная задача является ослабленной версией квадратичной задачи о назначении, которая не требует инъективности отображения (р. Для задачи Вебера полностью исследован лишь частный случай, когда пространство для размещения имеет прямоугольную метрику (Francis R. L., White J. А., 1974; В. А. Трубин, 1978, Замбицкий Д. К., Лозовану Д. Д., 1983).

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

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

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

В случаях когда граф (V, .Р) является разреженным, а величина отношения числа вершин графа к числу выделенных вершин достаточно велика наиболее эффективными являются методы, основанные на синтезе топологии сети. Данные методы используют двухуровневую схему решения: на нижнем уровне определяется размещение точек Штейнера для сети с топологией, передаваемой с верхнего уровня; на верхнем уровне осуществляется синтез топологии сети.

Задача 3((У, Р), с?, Т) построения сети Штейнера с топологией Т (Т-оптимальной сети) представляет эффективно решаемый вариант задачи Вебера рассмотренный в первом разделе данной работы. В исследуемой здесь схеме повышена эффективность использования рассмотренных ранее алгоритмов решения задачи Вебера и получена возможность формирования нижней оценки частичного дерева Штейнера за счет модификации процедуры редукции. Модифицированная процедура редукции исходной задачи

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

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

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

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

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

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

В заключении третьей главы даны сведения о разработанном комплексе программного обеспечения для решения задач размещения прямоугольных объектов. Данный комплекс программ содержит: 1) модуль БЬОС построения локально оптимальных размещений по заданному допустимому размещению; 2) модуль ИХ/ОС генерации конкурентоспособных вариантов размещения для задач без ограничений на максимально допустимые расстояния, основанный на случайном поиске, механических аналогиях и локальной оптимизации; 3) модуль ВВЬОС построения е-оптимального решения методом ветвей и границ.

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

В пятой главе работы изучены неатомические задачи размещения протяженных объектов. Для многих задач характерно наличие большого числа индивидуально малозначимых объектов. Для качественного анализа оптимального решения в этом случае представляется целесообразным переход к задаче размещения континуума протяженных объектов. Протяженность объектов моделируется заданием меры ц на сг-алгебре А подмножеств множества размещаемых объектов, а удельная стоимость коммуникаций - интегрируемой неотрицательной ограниченной симметричной функцией. Область V, предназначенную для размещения элементов из 3, будем считать ограниченным замкнутым подмножеством 11п, на котором обычным образом вводится сг-алгебра подмножеств и мера Лебега V. Длина коммуникаций между размещаемыми объектами определяется в соответствии с заданной по условиям задачи метрике р, которая предполагается непрерывной по совокупности переменных. Под размещением 3 на V будем понимать такое инъективное отображение ф : 3 —У И, что образ любого подмножества А € А измерим и /л(А) = и(ф(А)). Пусть Ф - совокупность всех размещающих отображений. Под решением неатомической задачи размещения будем понимать нахождение как величины так и отображения ф*, для которого достигается точная нижняя грань, либо нахождение способа построения минимизирующей последовательности ф

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

Поставленная задача может быть упрощена за счет того, что некоторые элементы множества 3 являются в определенном смысле неразличимыми по отношению к целевому функционалу задачи. Элементы ш,г) £ 3 будем считать ^-эквивалентными, если для любого 7 € «7 имеет место равенство К(ш, у) = К(г), у). В работе показано, что любая: неатомическая задача может быть аппроксимирована с заданной степенью точности неатомической задачей с конечным числом классов ТГ-эквивалентности, найден способ сведения неатомической задачи размещения к задаче минимизации квадратичной формы с компактным самосопряженным оператором Грама на компактном в слабой топологии ограниченном выпуклом подмножестве гильбертова пространства. Дано аналитическое решение неатомических задач размещения одного множества взаимосвязанных равнозначных объектов и двух таких множеств.

Шестая глава работы посвящена задаче идентификации размещения точечного источника физического поля. Подход к постановке и решению задачи иллюстрируется на примере местоопределения произвольно ориентированного электрического диполя Р = р(Ь)щ6(г) (момент ориентация По, точка размещения г) в полупространстве, ограниченном бесконечно проводящей плоскостью, по его электромагнитному полю (Е,Н) в точке О, принадлежащей указанной плоскости.

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

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

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

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

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

Аг)к% = ^к5 ^ = 1)2,., 77., где {Аф : г] 6 И С И™}, к = 1,2, - заданные параметрические семейства линейных операторов, действующих в гильбертовом пространстве Н, О - заданный компакт. Ставится задача определения такого параметра г/ £ И, который делает систему уравнений совместной при заданных исходных данных г^ 6 Н, & = 1,2,. ,п и неизвестной ж £ Н. Найден способ сведения проблемы непараметрической идентификации к задаче конечномерной оптимизации. Доказана устойчивость полученной задачи. Применение найденного способа к задаче местоопределения электрического диполя приводит к задаче конечномерного квазивыпуклого программирования.

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

В заключении шестой главы дан анализ использования рассматри 26 — ваемой задачи в качестве математической модели проблемы местоопре-деления грозовых очагов в ближней (от 20км до 150км) зоне и показана возможность использования разработанных методов. Приведены сведения о разработанном комплексе программ для системы местоопределения грозовых очагов.

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

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Панюков, Анатолий Васильевич

Результаты работы внедрены

• ЗАО "Гипротюменнефтегаз" в технологическую линию проектирования нефтяных и газовых месторождений Западной Сибири;

• ЗАО "НИИИТРК" в грозопеленгатор-дальномер "Очаг";

• в учебный процесс ЮУрГУ.

Заключение

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

1. Доказана А/^-трудность задачи Вебера и квазицелочисленность ее релаксационного многогранника. Разработан псевдополиномиальный алгоритм для задачи Вебера общего вида и полиномиальный алгоритм для случая размещения ациклической сети.

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

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

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

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

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

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

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

1. Решение задачи Вебера на графе для древовидной связывающей сети. Библиотека программных модулей [24].

2. Локально оптимальное размещение прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль [66].

3. Оптимальное размещение прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль [70].

4. Построение конкурентоспособных вариантов решения задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль [73].

5. Комплекс программ для системы местоопределения грозовых очагов в ближней зоне ("Гроза ") [82].

Результаты технического характера, полученные совместно с сотрудниками ЗАО "НИИИТРК", защищены авторскими свидетельствами СССР [1]- [12]

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

1. Авторское свидетельство СССР 572132. 1977.

2. Авторское свидетельство СССР 583681. 1977.

3. Авторское свидетельство СССР 590786. Устройство для отображения информации на экране электронно-лучевой трубки. / А. В. Па-нюков, Я. И. Крохин, Я. А. Файзулин- БИ 4. 1978.

4. Авторское свидетельство СССР 592250. 1977.

5. Авторское свидетельство СССР 679894. 1979.

6. Авторское свидетельство СССР 698506. 1979.

7. Авторское свидетельство СССР 720384. Однопунктовая система мес-тоопределения гроз в ближней зоне. / Я А. Файзулин, Б. В. Сема-гин, Я. Я. Крохин, А. В. Панюков БИ 9. 1980.

8. Авторское свидетельство СССР 748274, Способ измерения фазового сдвига. / В. С. Галяминский, А. В. Панюков БИ 26. - 1980.

9. Авторское свидетельство СССР 749252. 1980.

10. Авторское свидетельство СССР 764489. 1980.

11. Авторское свидетельство СССР 818001. Преобразователь напряжения в код Грея. / А. В. Панюков, Н. И. Крохин, Н. А. Файзулин-БИ 12. 1981.

12. Авторское свидетельство СССР 868796. Устройство для регистрации информации. БИ 36. 1981. / Б. В. Семагин, А. В. Панюков, А. В. Мясоедов

13. Ахмедов И.О., Сигал И.Х. Задача компоновки генплана промпред-приятий и некоторые подходы к ее решению. М: ВЦ АН СССР. -1982. - 58 с. (Рук. деп. в ВИНИТИ, N 270-83).

14. Базелян Э. М., Горин Б. В., Левитов В. И. Физические и инженерные основы молниезащиты. Л.: Гидрометиоиздат. - 1978. - 223с.

15. Бару Н. В., Кононов И. И., Соломоник М. Е. Радиопеленгаторы-дальномеры ближних гроз. Л.: Гидрометиоиздат. - 1976. - 143 с.

16. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. -- М.: Наука. Глав. ред. физ.-мат. лит. 1984. - 329 с.

17. Гловер Ф., Клингман Д. Последние достижения в технике реализации сетевых потоковых алгоритмов. // Экономико-оптимизационные задачи большой размерности. Труды Советско-американского семинара. США, 1980. М.: ЦЭМИ. - 1983. - С. 180-209.

18. Глушков В.М., Капитонова Ю.В, Каспшицкая М.Ф., Сергиенко И.В. Алгоритмическое обеспечение пакета программ ВЕКТОР-1, предназназначенное для решения одного класса задач проектирования ЭВМ. // Кибернетика. 1978. - N0 4. - С. 1-5.

19. Голъштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов. радио. - 1966. - 524 с.

20. Грозопеленгатор-дальномер "Очаг-2П". Л: Гидрометеоиздат. -1988. - 30 с.

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

22. Дударева В. И., Панюков А. В., Пелъцвергер Б. В. Решение задачи Вебера на графе для древовидной связывающей сети. Библиотека программных модулей. Рег. N0 50870001420. Инф. бюллетень "Алгоритмы и программы". М.: ВНТИЦ. - 1988. - N0 6. - С.4.

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

24. Ерзин А. И. Асимптотический подход к решению задачи Штейнера с вогнутой функцией стоимости потока: Препринт No 4. Новосибирск: Ин-т математики СО АН СССР. - 1983. - 12 с.

25. Ерзин А. И., Мордвинова Т. Б. Одна задача построения оптимального дерева. // Управляемые системы. 1983. - Вып. 23. - С. 44-54.

26. Жак C.B., Зинченко A.B. Комбинаторные методы решения задачи размещения помещений в производственном здании. // Автоматизация архитектурно-строительного проектирования промышленных предприятий. Ростов-на-Дону: РИСИ. - 1979. - С. 56-57.

27. Жак C.B., Зинченко A.B. Решение некоторых задач геометрического размещения модифицированным методом ветвей и границ. // Математическое обеспечение АСУП: Тезисы докладов второго Всесоюзного семинара. М,: Ин-т пробл. упр. - 1975. - С. 27-28.

28. Жак C.B., Мермельштейн Г.Г., Рафалович И.И. Общая схема имитадионной модели процесса архитектурно-строительного проектирования промышленных предприятий. // Имитационное моделирование.- М.: Наука. 1977. - С. 19-20.

29. Журавлев Ю. И. Алгебры над множествами некорректных (эвристических) алгоритмов. // Докл. АН СССР. 1977. - 235. - No 4. -С. 761-763.

30. Забудский Г. Г. Алгоритм решения одной задачи оптимального линейного упорядочения. // Известия Вузов. Математика. 1997. -N0 12. - С. 73-78.

31. Замбицкий Д. К., Лозовану Д. Д. Алгоритмы решения оптимизационных задач на сетях. Кишинев: Штиница. - 1983. - 122с.

32. Зинченко А.Б. Об одной задаче оптимального геометрического размещения. // Численные методы нелинейного программирования. Тез. докл. Ш Всесоюзного семинара. Харьков. 1979. С. 15-16.

33. Зинченко А.Б. Локальный алгоритм для задачи размещения. // Автоматизация архитектурно-строительного проектирования промышленных предприятий. Ростов н/Д: РИСИ. - 1986. - С. 136-141.

34. Злотов А. В. Об одном комбинаторном алгоритме построения сети с разрывной функцией стоимости на ребрах. // Экономика и математические методы. 1978. - Т. 14. - Тщ 7. - С. 783-787.

35. Злотов А. В., Хачатуров В. Р. Применение аппроксимационно-комбинаторного метода для решения задач построения оптимальных сетей с нелинейными функциями стоимости ребер: Сообщения по прикладной математике. М.: ВЦ АН СССР. - 1984. - 41 с.

36. Иорданский М. А. Минимальные нумерации вершин деревьев. // Проблемы кибернетики. 1976. - Вып. 31. - С. 109-132.

37. Йенсен П., Барнес Д. Потоковое программирование. М.: Радио и связь. 1984. - 391 с.

38. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. М.: Изд. АН СССР. - 1960. - 231 с.

39. Кашппровский В. Е. Определение местоположения гроз радиотехническими методами. М.: Наука. - 1966. - 220 с.

40. Коглер В., Штиглиц К. Перечислительные и итеративные алгоритмы. // Теория расписаний и вычислительные машины. М.: Наука.- 1984. С. 249-317.

41. Кононов И. И. Границы применимости дипольных представлений молниевых разрядов // Труды ГГО. 1975. - Вып. 358. - С. 61-68.

42. Кононов И. И., Петренко И. А. Современное состояние пассивных методов местоопределения гроз (обзор). // Рдиотехника и электроника. 1992. - Т. 37. - N0 7. - С. 1153.

43. Кононов И. И., Семикрас Ю. В, Электромагнитное излучение молниевых разрядов // Труды ГГО. 1975. - Вып. 358. - С. 48-60.

44. Кононов И. И., Петренко И. А., Снегуров В. С. Радиотехнические методы местоопределения грозовых очагов. Л.: Гидрометеоиздат.- 1986. 222 с.

45. Кононов И. И., Штенников Ю. В. Экспериментальное исследование дипольных моментов молниевых разрядов // Атмосферное электричество. Труды I Всесоюзного симпозиума по атмосферному электричеству. JL: Гидрометиоиздат. - 1976. - С. 231-237.

46. Корбут А.А., Сигал И.Х. Финкелынтейн Ю.Ю. Метод ветвей и границ (Обзор теории, алгоритмов, программ и приложений). // Math. Operat. Statist,, Ser. Optimization. 1980. - V. 8, No 2. - P. 253-280.

47. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука. - 1969. - 368 с.

48. Литвинов В.Н., Новиков И.Д., Стоян Ю.Г. Компоновка генпланов с помощью математических методов и ЭВМ. // Изв. АН СССР. Техн. кибернетика. 1979. - No 4. - С. 96-102.

49. Лотарев Д. Т. Задача Штейнера для транспортной сети на поверхности, заданной цифровой моделью. // Автоматика и телемеханика. 1980. - No 10. - С. 104-115.

50. Магас С.Л. Определение и свойства структур линейных неравенств. // Автоматизация проектирования в машиностроении. Вып. 3. -С. 5-11.

51. Математическая модель процесса построения оптимального варианта объемно-планировочного решения одноэтажного промздания.-М.: ЦНИПИАСС. 1974. - 112 с.

52. Михалевич В. С., Трубин В. А., Шор Н. 3. Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы. М.: Наука. - 1986. - 264с.

53. Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. М: Наука. - 1979. - 384с.

54. Панюков A.B. Алгоритм локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети. // Изв. АН СССР. Техническая кибернетика. 1981. -С. 180-184.

55. Панюков А. В. Алгоритмы размещения прямоугольных объектов. // Декомпозиция и координация в сложных системах. Материалы Всес. конференции. Челябинск: ЧПИ. - 1987. - С. 80-97.

56. Панюков A.B. Декомпозиция задачи размещения прямоугольных объектов. // Декомпозиция и координация в сложных системах. Тез. докл. Всес. конф. Часть 1. Челябинск: ЧПИ. - 1986. - С. 99-100.

57. Панюков А. В. Задача определения параметров электрического диполя. // XVI Всесоюзная школа по теории операторов в функциональных пространствах. Тезисы докладов. Нижний Новгород, 1991.- Нижний Новгород: Нижегородский гос. ун-т. 1991. - С.173.

58. Панюков А. В. Комбинаторный алгоритм размещения разногабаритных прямоугольных объектов // Информационные и робототех-нические системы. Тем. сб. научн. трудов. Челябинск: ЧПИ. 1985.- С.7-9.

59. Панюков А. В. Локально оптимальное размещение прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль. Per. No 5080001644. // Инф. бюллетень "Алгоритмы и программы". М.: ВНТИЦ. - 1988. - No 7. - С. 8.

60. Панюков А. В. Оптимальная совокупность остовов нестационарной сети с двумя возможными состояниями коммуникаций // Информационный бюллетень Ассоциации математического программирования. Вып. 7. Екатеринбург: УрО РАН. - 1997. - С. 174-175.

61. Панюков А. В. Оптимальное размещение прямоугольных объектов с минимальной длиной связывающей их сети. Программный модуль. Per. No 5080001647. // Инф. бюллетень "Алгоритмы и программы". М.: ВНТИЦ. - 1988. - No 8. - С. 11.

62. Панюков А. В. Оптимизация размещения узлов управления сложных развивающихся систем // Методы синтеза и планирования развития структур крупномасштабных систем. III Всес. семинар. Звенигород, 1985. Тез. докл. и сообщ. М: ИПУ. - 1985. - С.47.

63. Панюков А. В. Повышение эффективности прямых алгоритмов построения потока минимальной стоимости в насыщенной сети //

64. Системы программного обеспечения задач оптимального планиро «■#вания. УШ Всес. симп. Тезисы докл. Нарва-Иыесуу, апрель, 1984. -М.:ЦЭМИ. 1984. - С. 153-154.

65. Панюков А. В. Построение плана с максимальной дисконтированной суммой доходов // Современные технологии в социально-экономических системах: Сборник научных трудов / Отв. Редактор А. В. Панюков. Челябинск: Издательство ЧГТУ. - 1995. - С.62-67

66. Панюков A.B. Построение локально оптимальных решений задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети. // Алгоритмы и программы. Информационный бюллетень. М.: ВНТИЦ. - 1984. - No 1. - С. 53.

67. Панюков А. В. Размещение прямоугольных объектов. // Декомпозиция и координация в сложных системах: Материалы Всесоюзной конференции / Ред. кол. П. С. Краснощеков и др. Челябинск: ЧПИ.- 1987. С. 80-89.

68. Панюков А. В. Упорядоченное изучение базисного дерева в прямых алгоритмах для транспортной задачи // Международная Сибирская конференция по исследованию операций. Материалы конференции.- Новосибирск: Изд-во Института Математики СО РАН. 1998. -С. 44.

69. Панюков А. В. Численное и аналитическое решение неатомических задач размещения с конечным числом классов К-эквивалентности // Проблемы вычислительной математики и автоматизации научных исследований: Тез. докл. II республиканской конференции (Алма

70. Ата, 2-6 октября 1988 г.). Том 2. Теория управления и численные методы экстремальных задач. Автоматизированные системы управления и проектирования. Алма-Ата: Наука. - 1988. - С. 78.

71. Панюков А. В., Захаров Е. Л., Королев М. С. Комплекс программ для системы местоопределения грозовых очагов в ближней зоне ("Гроза "). Свидетельство РосАПО об официальной регистрации программы для ЭВМ 970109 от 17.03.1997.

72. Панюков А. В., Пелъцвергер Б. В. Оптимальная совокупность остовов нестационарной сети / / Инф. бюллетень Ассоциации математического программирования. Вып. 5. Екатеринбург: УрО РАН. -1995. С. 160-161.

73. Панюков А. В., Пелъцвергер Б. В. Оптимальное размещение дерева в конечном множестве / / Журнал вычислительной математики и математической физики. Том 28. - 1988. - С. 618-620.

74. Панюков А. В., Пелъцвергер Б. В., Шафир А. Ю. Алгоритмы решения задачи Штейнера с потоками на графе. // Челябинск: ЧПИ. -1983. 15с. (Деп. в ВИНИТИ 1664-84 Деп., 0.7 п. л.)

75. Панюков А. В., Пелъцвергер Б. В., Шафир А. Ю. Локальные алгоритмы перебора топологий в задаче Штейнера на графах. // Методы математического программирования и программное обеспечение.

76. Тез. докл. научной конференции (Свердловск, 25 февраля 5 марта 1989 г.). - Свердловск: УрО АН СССР. - 1991. - С. 168-169.

77. Панюков А. В., Пелъцвергер Б. В., Шафир А. Ю. Оптимальное проектирование и управление развитием нефтегазодобыающих систем //IX Всесоюзное совещание по проблемам управления. М.: ИПУ АН СССР. - 1983. - С.424-425.

78. Панюков А. В., Пелъцвергер Б. В., Шафир А. Ю. Оптимальное размещение точек ветвления транспортной сети на цифровой модели местности // Автоматика и телемеханика. N0 9. - 1990. -С.153-162.

79. Панюков А. В., Петренко С. А. Формирование конкурентоспособных вариантов схемы компоновки генерального плана предприятия на ЭВМ // Известия ВУЗов. Строительство и архитектура. No 8. -1987. С. 119-121.

80. Панюков А. В., Семагин Б. ВФайзулин Н. А. Однопунктовые системы местоопределения гроз в ближней зоне. //II Областная научно-техническая конференция НТО РЭС им. А. С. Попова. Тез. докладов. Челябинск: НТО РЭС им. A.C. Попова. - 1984. - С.15-17.

81. Панюков А. В., Штраус В. А. Неатомические задачи размещения протяженных объектов // Автоматика и телемеханика. 1985. - No 11. - С.54-61.

82. Панюков А. В., Штраус В. А. Неатомические задачи размещения протяженных объектов с конечным числом классов К-эквивалентности. // Кибернетика и системный анализю No 2. -1992. - С. 165-170.

83. Панюков А. В., Штраус В. А. Оптимальное размещения континуума объектов //IX школа по теории операторов в функциональных пространствах. Тезисы докладов. Тернополь: Збруч. - 1984. -С. 107-108.

84. Панюков А. В., Штраус В. А. О решении неатомических задач размещения с конечным числом классов К-эквивалентности. //XI школа по теории операторов в функциональных пространствах. Часть III. Тезисы докладов Челябинск: ЧПИ. - 1986. - С. 90.

85. Плужников JI.H. Математическое обеспечение некоторых задач размещения и компоновки. // Автоматизация проектирования как комплексная проблема совершенствования проектного дела в стране. -М.: ЦДНТП. 1973. - С. 201-207.

86. Плужников Л.Н., Рачинский B.C. Математическое обеспечение АСП коммуникаций и генерального плана промышленного узла. // Автоматизированные системы проектирования. М.:МДЦТП. -1975. - С. 185-190.

87. Применение математических методов и ЭВМ при проектировании автомобильных дорог на неоднородной территории / Э. А. Ахпателов, А. В. Панюкое, и др. Под ред. Цыганкова В. А. Челябинск: ЧПИ. - 1984. Часть 2. - 50 с.

88. Разработка и анализ алгоритмов дискретной оптимизации. Учебное пособие. / А. В. Панюкое, Б. В. Пелъцвергер, И. X. Сигал, и др. -Челябинск: ЧПИ. 1987. - 74 с.

89. Разработка и анализ алгоритмов дискретной оптимизации. Учебное пособие. Часть 2. / А. В. Панюкое, Б. В. Пелъцвергер, И. X. Сигал, и др. Челябинск: ЧПИ. - 1988. - 48 с.

90. Растригин Л.А. Современные принципы управления сложным объектами. М.: Сов. радио. - 1980. - 232 с.

91. Рваче в В.Л. Об аналитическом описании некоторых геометрических объектов. // ДАН СССР. 1963. - 153. - No 4. - С. 765-767.

92. Рощин Г. В. Алгоритм построения кратчайшей связывающей сети на графе. // Вычислительная техника: Сб. статей. Каунас. - 1974.- С. 107-110.

93. Селютин В.А. Автоматизация проектирования топологии БИС. -М.: Радио и связь. 1983. - 112 с.

94. Родендорф Ю.К., Тиверский В.И. Проблемы автоматизированного проектирования генерального плана и транспорта завода. // Промышленный транспорт. 1972. No 1. - С. 9-16.

95. Селютин В.А. Машинное проектирование электронных устройств.- М.: Сов. радио. 1977. - 384 с.

96. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка. - 1985. - 384 с.

97. Сергиенко И.В., Каспшицкаж М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка. -1981. - 288 с.

98. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка. -1980. - 276 с.

99. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наукова думка. - 1977. - 247 с.

100. Стоян Ю.Г., Соколовский В.З. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. Киев: Наукова думка. - 1979. - 206 с.

101. Трубин В. А., Гндоян А.К. Алгоритм и свойства задачи синтеза сетей с одним источником. // Теория оптимальных решений. Киев: Наукова думка. - 1980. - С. 81-87.

102. Трубин В. А. О методе решения задач целочисленного линейного программирования специального вида // ДАН СССР. 1969. - N 5.

103. Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. 1978. - N 6. - С. 67-70.

104. Файзулин Н. А., Семагин Б. В., Панюков А. В. К построению од-нопунктных систем местоопределения гроз в ближней зоне, учитывающих поляризационные ошибки // Вопросы радиоэлектроники. Серия: Общие вопросы радиоэлектроники. Вып. 7. - 1987. - С. 60-64.

105. Форд JI., Фалкерсон Д. Потоки в сетях. М.: Мир. 1962. - 276 с.

106. Хачиян JI. Г. Полиномиальные алгоритмы в линейном программировании. // Журнал вычислительной математики и математической физики. 1980. - No 1. - С. 51-69.

107. Чернышев А.В. Технология монтажа, обработки, испытаний и контроля бортовых систем летательных аппаратов. М.: Машиностроение. - 1977. - 375 с.

108. Эйдес А.А. Современные методы размещения в системах автоматизированного проектирования радиоэлектронной аппаратуры (САПР РЭА). // Измерения, контроль, автоматизация. ЦНИИТЭИ приборостроения. Вып. 351. - 1984. - С. 69-84.

109. Ahrens J.H. Finke G. Primal Transportation and Transshipment Algorithms. // Z. Oper. Res. 1980. V.24. - No 1. - P. 1-32.

110. Arcangeli R. Pseudosolution de l'equation Ax = y. C.r. Acad. Sci. -Paris. - 1966. ^

111. Armstrong R. D., Klingman D., Whitman D. Implementation and Analisis of a Variant of Dual Method for the Capacitated transshipment Problem // European J. Oper. Res. 1980. - V. 4. - No 6. - P. 403-420.

112. Balas E., Padberg M. On the set-covering problem. // Oper. Res. 1972.- V. 20. No 6. - P. 1153-161.

113. Balas E., Padberg M. (1975) On the set-covering problem. An Algorithm for set partitioning. // Oper. Res. 1975. - V. 23. - No 1. - P. 74-90.

114. Barr RGlover F., Klingman D. Enhancements of Spanning Tree Labeling Procedures for Network Optimization. // INFOR. 1979. -V. 17. - No 1. - P. 16-34.

115. Benders J.F. Partitioning Procedures for solving Mixed Variables Programming Problems. // Numeriche Mathematik. 1962. - No 4.- P. 139-151.

116. Ben-Israel A., Charnes A. On some Problems of Diophantine Programming. / / Cahiers du Centre d'Etudes de Recherche Operationelle. 1962. - No 4. - P. 121-135.

117. Bom, M., E. Wolf. Principles of Optics. Electromagnetic Theory of Propagation, Interference and Diffraction of Light, pp., Pergamon Press, Oxford London - New York - Paris - Frankfurt, 1968.

118. Bradley G. H., Brown G. G., Graves G. W. Design and Implemetation of Large Scale Primal Transshipment Algorithms. // Manage. Sei. -1977. Vol. 24. - No 1. - P. 1-34.

119. Christofides N. Graph theory. An algorithmic approach. Academic Press Inc. (London)Ltd. 1977.

120. Dantzig G. Application of the Simplex Method to a Transportation Problem. // Activity Analysis of Production and Allocation. 1951.- P. 196-218.

121. Dantzig G. Linear Programming and Extensions. Princeton: University. - 1963. - 215 p.

122. Dreyfus S. E., Wagner R. A. Steiner problem in graphs. // Networks.- 1972. V. 2. - P. 195-207.

123. Fleischner H. Eulerian graphs and related topics. Vol. 1-2. Amsterdam. Noth. Holl. - 1991.

124. Francis R. L., White J. A. Facilities Layout and Location: an Analitical Approach. 1974. - Prentice-Hall, Englewood Cliffs. NJ.

125. Fulkerson D. An Out-of-Kilter Method for Minimal-Cost Flow Problems. // SI AM Journal of Applied Mathematics. 1961. - V. 9.- No 1. P. 1-18.

126. Galil Z., Tardos E. An 0(n2(m-\-nloogn) logn) min-cost flow algorithm. // 27th Annu. Symp. Found. Comput. Sei., Toronto, Oct. 27-29, 1986.- P. 1-9.

127. Gilbert E. N., Pollack H. 0. Steiner minimal trees. // J. of SIAM (Appl. Math.). 16. - P. 1-17.

128. Glickman S., Jonson J., Eselson L. Coding.in Transportation Problem. // Naval Research Logistics Quar. 1960. - V. 7. - No 2. - P. 169.

129. Glover F., Karney D., Klingman D. Implementation and Computational Comparisions of Primal, Dual and Primal-Dual Computer Codes for Minimum Cost Network Flow Problems. // Networks. 1974. - V. 4. -No 3. - P. 191-212.

130. Glover F., Karney D., Klingman D., Napier A. A Computational Study on start procedures basis change criteria, and solution algorithms for transportation problems. // Manage. Sci. 1974. - Vol. 20. - No 5. -P. 793-813.

131. Goldberg A. V., Plotkin S. A., Tardos E. Combinatorial algorithms for the generalized circulation problem. // Math. Oper. Res. 1991. - Vol. 16. -No.2. -P. 351-381.

132. Grotschel M., Lovasz L., Schrijver A., 1981. The Ellisoid Method and Its Consequeces in Combinatorial Optimization. // Combinatorica. -1981. No 2. - P. 169-197.

133. Hakimi S. L. Steiner's problem in graphs and its applications. // Networks. 1971. - V. 1. - P. 113-133.

134. The Steiner tree problem. / Hwang, R. Frank, et all. North Holland. - 1992. - 432 p.

135. Heller J. (1957) On linear systems with integer valued solutions. // Pacif. J. Math. 1957. - V. 7. - No 3.

136. Hutson V.C.L., Pym J.S. Application of Functional Analysis and Operator Teory. Academic Press. 1990.

137. Jonson J. Networks and Basic Solutions. // Operations. Res. 1966. -V. 14. - P. 619-623.

138. Kleinschmidt P., Schannath H. A Strongly Polynomial Algorithm for the Transportation Problem. // Mathematical Programming. 1995. -Vol. 68. - No 1. - P. 1-13.

139. Kononov I. I., Petrenko I. A., Richard P., Lojou J.-Y. Polarization errors of magnetic direction finders // Proceedings of 24th International Conference on Lightning Protection. Birmingham, United Kingdom, September, 14-18, 1998. Vol. 1. P. 221-226.

140. Konovalov, M. V., A. A. Romanchenko, A., V. Snegurov, V. S. Snegurov. One Station Thunderstorm Range and Direction Finding. -Proc. 9-th Int. Conf. on Atmospheric Electricity. Vol. 1. - 1992. -P. 287-291.

141. Krider, E.P., R. C. Noggle and M. A. Uman. A gated wideband magnetic direction finder for lightning return strokesio J. Appl. Meteorol. - 61. - 1980. - P.980-986.

142. Master, M. J., M. A. Uman, Y. T. Lin and R. B. Standler. Calculation of lightning return stroke electric and magnetic fields above ground // J. Geophis. Res. 86. - 1981 - P. 12,127-12,132.

143. Neumann J. Mathematical Foundations of Quantum Mechanics. Princeton Univ. Press, Princeton, New Jersey. 1955.

144. Orlin J. В., Plotkin S. A., Tardos E. Polynomial dual network simplex algorithms. // Math. Program. 1993. - Vol. - 60A. - No.3. -P. 255-276.

145. Panyukov A. V. Estimation of the location of an arbitrarily oriented dipole under single-point direction finding // Journal of geophysical research. June 27, 1996. - Vol. 101. - No D10. - P. 14,977-14,982. (USA)

146. Panyukov; A. V. The Optimization Algorithm for Electromagnetic Method of Lightning Location// Proc. 9-th Int. Conf. on Atmospheric Electricity. 1992. - Vol. 1. - P. 296-299.

147. Panyukov A. V. Lightning detection and mapping algorithms. // Proceedings of 24th International Conference on Lightning Protection. Birmingham, United Kingdom, September, 14-18, 1998. Vol. 1. -P. 227-231.

148. Panyukov A. V. The study of basis tree for primal transhipment algorithm // Combinatorial Optimization 94: Program & Abstracts of International Conference (Amsterdam, The Netherlands, April 5-8, 1994) .

149. Panyukov A. V., Pelzwerger B. V. Polynomial algorithms to finite Weber problem for a tree network // Journal of Computational and Applied Mathematics. Vol. 35. - 1991. - P. 291-296. (North-Holland)

150. Panyukov A. V., Strauss V. A. None-atomic problems on location of extended objects with a finite number of K-equivalence classes // Cybernetics and system analysis. 1992. - Vol. 28. - P. 303-308. (USA)

151. Petrenko, I. A., I. I. Kononov. Methods of Lightning Location. // Proc. 9-th Int. Conf. on Atmospheric Electricity. 1. - 1992. - P. 292-295.

152. Picard J., Queyranne M. On the One-Dimensional Allocation Problem. // Operat. Res. 1981. - V. 29, N 2. - P. 371-391.

153. Preas B.T., van Cleemput W.M. Placement Algorithms for Arbitrargily Shaped Bloks. // Proc. of the 16-th DAC. 1979. - P. 474-480.

154. Quinn N.R., Breuer M.A. Forced Directed Component Placement Procedure for PCB. // IEE Trans, on Circuits and Systems. 1979. - V. CAS-26. - No 6. - P. 377-388.249 —

155. Ruhnke, L. H. Distance to lightning strokes as determined from electrostatic field strength measurements. //J. Appl. Meteorol. No 1. -1962. P. 544-547.

156. Uman, M.A., Y. T. Lin and E. P. Krider. Errors in magnetic direction finding due to non-vertical lightning channel. // Radio Sci. 15. - 1980.- P. 35-39.

157. Winter P. Steiner problem in Halin networks. // Discrete Appl. Math.- 1987. V. 17. - No 3. - P. 281-294.