Модели и методы группировки объектов для геолого-экономического районирования

• Автор: Пономарев, Андрей Васильевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 123 с. : ил.

Содержание
Введение
Глава 1. Геолого-экономическое районирование и группировка объектов
1.1. Геолого-экономическое районирование
1.1.1. О задаче геолого-экономического районирования
1.1.2. Элементы экономической оценки минерально-сырьевой базы
1.1.3. Задача формирования промышленно-сырьевых узлов
1.1.4. Модели формирования промышленно-сырьевых узлов
1.2. Задача группировки объектов
1.2.1. О группировке объектов
1.2.2. Кластерный анализ
1.2.3. Группировка в дискретной оптимизации
1.2.4. Известные обобщения задачи группировки
Выводы
Глава 2. Модели централизованной группировки
2.1. Формальная модель задачи группировки
2.1.1. Терминология задачи группировки
2.1.2. Типология задач группировки
2.2. Простейшая задача централизованной группировки
2.2.1. Описание задачи
2.2.2. Постановка задачи математического программирования
2.2.3. Постановка задачи в терминах теории графов
2.2.4. Задача формирования ПСУ как простейшая централизованная группировка
2.3. Задача централизованной группировки со стоимостью активации
2.3.1. Описание задачи
2.3.2. Постановка задачи математического программирования
2.3.3. Задача формирования ПСУ как централизованная группировка со стоимостью активации
2.4. Модификации
2.4.1. Группировка с ресурсными ограничениями
2.4.2. Запреты на одновременное вхождение
2.4.3. Количественные ограничения
2.5. Группировка векторных объектов

Выводы

Глава 3. Методы и алгоритмы решения задачи группировки
3.1. Простейшая задача централизованной группировки
3.1.1. Полная группировка
3.1.2. Полная по С
3.1.3. Полная по
3.1.4. Неполная
3.2. Задача централизованной группировки со стоимостью активации
3.2.1. Простейшая задача размещения
3.2.2. Анализ задачи
3.2.3. Подготовка исходных данных для эксперимента
3.2.4. Генетические алгоритмы
3.2.5. Метод локального поиска
3.3. Группировка с линейной стоимостью и бесплатным порогом
3.3.1. Наборы данных для экспериментального исследования методов решения
3.3.2. Решение с применением CPLEX
3.3.3. Локальный поиск
3.3.4. Метод «Лидер группы»
3.3.5. Вероятностные жадные алгоритмы поиска (GRASP)
Выводы
Глава 4. Практическое решение задачи геолого-экономического районирования
4.1. Библиотека модулей группировки
4.1.1. Модули для решения простейшей задачи группировки
4.1.2. Модули для решения задачи группировки со стоимостью активации
4.2. Решение задачи геолого-экономического районирования для федерального округа
4.2.1. Исходные данные
4.2.2. Результаты
Выводы
Заключение
Литература

Введение
Актуальность темы диссертации.
Задача геолого-экономического районирования приобрела актуальность в связи с рассмотрением на государственном уровне перспектив развития политики в области недропользования, суть которых заключается в переходе от лицензирования отдельных объектов недропользования на лицензирование промышленно-сырьевых узлов и геолого-эко-номических районов, включающих месторождения разных полезных ископаемых. Целью этого перехода является повышение рентабельности освоения минерально-сырьевых ресурсов и полноты их вовлечения в хозяйственный оборот.
В общем случае, задача геолого-экономического районирования является комплексной системной задачей, решаемой экспертами в области экономики недропользования с учетом знаний о разведанных запасах минерально-сырьевых ресурсов, истории и перспективах развития минерально-сырьевого комплекса, данных об инфраструктуре и трудовых ресурсах исследуемого региона. Однако при решении этой задачи эксперту приходится обрабатывать значительные объемы фактической информации, что делает актуальной задачу компьютерной поддержки этого процёсса. Создание программных инструментов важно еще и потому, что способно повысить качество принимаемых экспертом решений, например, за счет обеспечения возможности быстрого анализа альтернативных вариантов районирования.
В то же время, значительное количество задач, возникающих в научной и практической деятельности человека, включая задачи геолого-экономического районирования, имеют в своей основе общую идею: образование групп из заданных объектов при определенных условиях. Многие из этих задач успешно решаются с применением различных методов и моделей - теории графов, кластерного анализа, математического программирования. Вместе с тем, почти нет работ, в которых бы предпринимались попытки осознать и описать внутреннее родство таких задач, выделить общие идеи, подходы и методы, которые можно было бы применять последовательно, при решении различных задач группировки объектов.
Цель диссертационной работы и задачи исследования. Цель диссертационной работы состоит в разработке моделей и методов группировки объектов для повышения качества геолого-экономического районирования и снижения затрат на его проведение.
Для достижения поставленных целей были решены следующие задачи:

при ограничениях
Ах 1 (1.12-а)
х 1 х G N.
Как видно, она отличается от задачи разбиения множества ослаблением одного ограничения ( 1.12-а против 1.10-а), то есть, элемент исходного множества М может попасть более, чем в одно результирующее множество. Ослабление этого ограничения делает задачу проще (не в смысле ее теоретической сложности, а, скорее, в практическом решении) - если для задачи разбиения множества даже поиск допустимого (не оптимального) решения является NP-сложной задачей, то для задачи покрытия тривиальное допустимое решение существует всегда: х = (1,1
К задаче о покрытии сводятся многие известные задачи дискретной оптимизации: задачи стандартизации, упаковки и разбиения множества [25], задача о наибольшей клике, задача минимизации полинома от булевых переменных и др. Известна и обратная сводимость задачи о покрытии к этим задачам.
На практике задачи о покрытии возникают при размещении пунктов обслуживания, в системах информационного поиска, при назначении экипажей на транспорте, проектировании интегральных схем и конвейерных линий [26].
Задачи о назначениях
Задачи о назначениях — это еще один класс задач комбинаторной оптимизации, в котором производится операция, схожая с группировкой объектов. В классической постановке задачи о назначениях рассматривается способ таким образом назначить каждый из п объектов одного типа одному из п объектов другого типа, при заданной попарной стоимости такого назначения, чтобы суммарная стоимость назначения была минимальна. Интерпретация этой задачи как задачи группировки весьма ограничена — группы получаются только размером 2 и только в количестве п для 2га исходных объектов.
Гораздо ближе к понятию группировки оказывается обобщенная задача о назначениях (generalized assignment problem - GAP), в которой рассматривается следующая ситуация: га задач должны быть выполнены т агентами, причем у агентов есть определенные ограничения, выраженные в виде ресурса, потребляемого при обработке задачи. Решением является такое назначение задач агентам, чтобы каждая задача была назначена ровно