автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Модели и методы группировки объектов для геолого-экономического районирования

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

ПОНОМАРЕВ Андрей Васильевич

МОДЕЛИ И МЕТОДЫ ГРУППИРОВКИ ОБЪЕКТОВ ДЛЯ ГЕОЛОГО-ЭКОНОМИЧЕСКОГО РАЙОНИРОВАНИЯ

Специальность 05.13.01 - Системный анализ, управление и обработка информации

(технические системы)

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

- 7 и ЮН 2012

Санкт-Петербург 2012

005045457

Работа выполнена в Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской академии наук (СПИИРАН).

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

доцент Мустафпн Николай Габдрахманович

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

зав. лабораторией СПИИРАН

кандидат технических наук, доцент,

Балтийский государственный технический университет «ВОЕНМЕХ» им. Д.Ф.Устипова

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

Александров Виктор Васильевич

Королев Сергей Николаевич

Санкт-Петербургский государственный университет водных коммуникаций

Защита состоится * LtfOMji— 2012 г. в часов на заседании диссерта-

ционного совета Д.002.199.01 при Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской академии наук по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Санкт-Петербургского института информатики и автоматизации Российской академии наук.

/siaSb-

Автореферат разослан *__»_/ /¿с _2012 г.

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

диссертационного совета Д.002.199.01 капдидат технических наук

Ф.Г. Нестерук

Общая характеристика работы Актуальность темы диссертации.

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

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

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

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

1) проведен обзор классических оптимизационных задач, связанных с группировкой объектов;

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

3) проведена классификация видов задачи группировки и для распространенных подклассов задачи группировки сформулированы эквивалентные задачи математического программирования;

4) для ряда разновидностей задачи группировки объектов разработаны новые или адаптированы существующие алгоритмы решения и произведена оценка эффективности разработанных алгоритмов на синтетических наборах данных;

5) показана связь некоторых видов абстрактных задач группировки с предложенными моделями формирования промышленно-сырьевых узлов;

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

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

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

2. Методы решения вариантов задачи группировки объектов, возникающих при использовании предлагаемых моделей формирования промышленно-сырьевых узлов.

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

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

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

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

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

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

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

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

данными.

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

Реализация результатов работы. Исследования, отраженные в диссертации, поддержаны грантом РФФИ №09-07-00436-а «Онтолого-ориентированпое управление гибкими сетевыми организациями» и проектом Президиума РАН №2.13 «Разработка теоретических основ и интеллектуальных моделей для поддержки принятия решений при управлении гибкими сетевыми организациями», 2009-2011.

Апробация полученных в диссертации результатов подтверждена актами об использовании результатов диссертационной работы в процессе обучения студентов в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» и в научно-исследовательской работе по государственному контракту ЖАЛ-04-06/9 «Разработка программно-технологического комплекса, обеспечивающего построение, мониторинг и функционирование ГИС-ориентированной системы для составления геолого-экономических карт федеральных округов России» совместно с Всероссийским научно-исследовательским геологическим институтом (ВСЕГЕИ) им. А.П. Карпинского.

Апробация результатов работы. Основные положения и результаты диссертации представлялись на следующих конференциях: «Информационные технологии в экономике, образовании и бизнесе» (Саратов, 2011), «Наука и техника XXI века» (Новосибирск, 2011), «Наука и современность — 2011» (Новосибирск, 2011), «Проблемы подготовки кадров в сфере инфокоммуникационных технологий» (Санкт-Петербург, 2011), а также на городском семинаре «Информатика и компьютерные технологии» (СПИИРАН, Санкт-Петербург, 2012).

Публикации. Материалы диссертации опубликованы в 8 печатных работах, в том числе в 3 рецензируемых изданиях из списка ВАК.

Структура и объем работы. Диссертация объемом 123 страницу содержит введение, четыре главы, заключение, список литературы (81 наименование), 22 рисунка, 10 таблиц.

Содержание работы

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

В первой главе, с одной стороны, произведен обзор классических задач, связанных с группировкой объектов, а с другой стороны, описана одна из практических задач группировки — задача геолого-экономического районирования.

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

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

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

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

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

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

Под промышленно-сырьевым узлом (ПСУ) понимается пространственно обособленная группа сближенных минерально-сырьевых объектов, обладающих одинаковым набором полезных ископаемых, локализация которых связана с месторождениями определенного геолого-промышленного типа и, как следствие этого, с единой технологией получения первого товарного продукта на существующих или проектируемых горно-обогатительных предприятиях (ГОП).

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

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

На этом этапе возможны различные установки, так или иначе учитывающие цели и стратегию недропользования в регионе. Данная работа основывается на экономической интерпретации задачи формирования ПСУ, изложенной в работах Куклиной Е.А., где варианты формирования ПСУ оцениваются по рентабельности (или интегральному доходу), получаемой при реализации соответствующего варианта. Дополнительно может ставиться задача полного распределения всех объектов минерально-сырьевой базы по ПСУ для вовлечения их в активное хозяйствование.

Прибыль от функционирования ПСУ определенного состава вычисляется как разница между суммарной потенциальной стоимостью запасов и ресурсов (СП) по всем минерально-сырьевым объектам, входящим в состав данного узла, и затратной частью (30), формируемой на основе цепочки преобразований, которым подвергается добываемое минеральное сырье: добыча -» транспорт —> обогащение. Затраты, возникающие на каждом из этапов, делятся на капитальные и эксплуатационные. Таким образом, в затратной части оказывается 6 показателей, сведенных в таблицу 1.

Таблица 1. Основные затратные показатели

Добыча Обогащение Транспорт

Капитальные Кд Кп Кт

Эксплуатационные Сд Сп Ст

Суммарные затраты на формирование ПСУ символически можно записать следующим образом:

30 = (Кп + Сп)+^(Кд + Сд + Кт + Ст). (1)

мсо

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

Следует заметить, что данное выражение представляет собой упрощенную символическую запись, на практике Кп и Сп, обычно, зависят от точки размещения горно-обогатительного предприятия (ГОП) и состава узла, Кд и Сд зависят от параметров месторождения (в первую очередь, объема запасов), Кт и Ст —от взаимного расположения месторождения и горно-обогатительного предприятия и объема запасов месторождения. Знак суммирования по «МСО» следует понимать как суммирование по всем месторождениям (минерально-сырьевым объектам), входящим в состав узла.

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

30 = £кп СП 4- Ас СП + ^ (КД + Сд + Кт + Ст) = мсо мсо мсо

= + + Кд + Сд + Кт + Ст). (2)

мсо

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

• на основе данных о сети дорог;

1 Лобанов Н. Я. Экономика природопользования при разведке, добыче и обогащении полезных ископаемых. Экономическая оценка минеральных ресурсов. СПб.: Изд-во СПбГГИ, 2009, 99 с.

• на основе эмпирических показателей развития транспортной инфраструктуры;

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

Другим особым случаем является создание ПСУ на базе эксплуатируемого горнообогатительного предприятия. Такое предприятие должно быть учтено при расчете капитальных затрат на создание ПСУ (Кп). В работе предлагается несколько стратегий для его учета:

• не учитывать;

• линейное уменьшение Кп узла;

• уменьшение Кп узла без псевдоприбыли.

Структура базовой модели формирования ПСУ с различными стратегиями отображена на рисунке 1.

Рис. 1. Структура базовой модели формирования ПСУ

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

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

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

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

Исходными данными для группировки является семейство исходных множеств б = Здесь к — количество типов исходных объектов; например, в задаче формирования промышленно-сырьевых узлов к равно 2 и семейство б образовано двумя множествами: горно-обогатительных предприятий и месторождений.

В работе вводится понятие базовой группы. Базовой группой С, заданной на семействе исходных множеств & называется набор множеств

С = (0»>,0®.....О«)

таких, что

иа называются компонентами группы.

Группировку (5 на семействе исходных множеств 6 определим как множество попарно не пересекающихся базовых групп на этом семействе. То есть,

® = {С}, (3)

У(С1,С2)|С1,С2 6 ® -+С1Г\О2 = 0 (4)

Группировка 0 называется полной гю 0й тогда и только тогда, когда и 0м (С) =

0«.

Группировка 10 называется полной тогда и только тогда, когда она полная по каждому из множеств в.

Группировка 0 называется частично полной тогда и только тогда, когда она не является полной, но в С существует хотя бы одно множество 0('>, по которому данная группировка является полной.

Группировка,

не являющаяся ни полной, ни частично полной, называется неполной.

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

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

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

• семейство исходных множеств;

• класс ограниченной группы — набор ограничений на структурные отношения объектов разных типов внутри группы;

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

полная, неполная;

• систему показателей.

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

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

• одноранговую группировку;

• централизованную группировку;

Задача группировки будет являться одноранговой в том случае, когда выделяемые группы являются однородными и состоят из объектов, одинаковых по своей роли в группе. Для этого вида группировок характерно наличие одного исходного множества (семейство в представлено только одним множеством О'1', класс ОГ либо эквивалентен классу базовых групп, либо содержит простейшие ограничения на размер группы, а система показателей базируется на попарных отношениях между объектами. К этой разновидности относятся большинство вариантов задачи кластеризации.

Централизованная группировка предполагает, что семейство исходных множеств & состоит из двух множеств: множества первичных объектов О'1' и множества потенциальных центров групп относительно которых происходит объединение первичных объектов. При рассмотрении этого вида группировок будем пользоваться альтернативным обозначением этих множеств 5 и С соответственно.

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

В рамках данной работы производится анализ, в первую очередь, именно централизованной группировки, причем рассматриваются три системы показателей; это связано с тем, что именно к таким задачам группировки сводятся задачи формирования промыш-ленно-сырьевых узлов при предлагаемых стратегиях учета ГОП. Во всех рассматриваемых системах показателей оценка группировки задается как сумма оценок групп, а оценки групп, в свою очередь, формируются следующим образом (здесь С {О) — центр группы О, а 5((3) —множество сателлитов этой группы):

• Простейшая система показателей. Предполагается, что задано одно отображение Б: 5 х С К. Оценка группы вычисляется по формуле:

• Систелш показателей со стоимостью активации. Здесь, помимо £>, задано отображение Р: С ь4 К. Оценка группы вычисляется по формуле:

ш/(С) = -р(С(С)) + <1{з,С(С)).

• Система показателей с линейной стоимостью и бесплатным порогом. Помимо £), заданы отображения Л: 5 и Е, Ь: С Н Е и Л: С и Е, а оценка группы вычисляется так:

уа1(в)= С(б)) + а(С(С)) ■ тт(0,1(С(С)) — ^ К«))- (5)

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

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

n m

Максимизировать г = ^ ^ Xijd(si, с,) (6)

i=l j=l

при ограничениях

m

Х^У^1 ге{1,...,п} (7-а)

j=i

Xij^Vj г е {l,...,n}, j е {l,...,m} (7-6)

Xij,yje{0,1} ie{l,...,n}, j 6 {i,...,m}.

Здесь переменные вида Жу — признак вхождения объекта Sj в группу с центром в cjt а уj — признак образования группы с центром в Су Если не указано иное, то п здесь и далее обозначает |5|, am обозначает |С|.

Ограничения вида 7-6 пазовем ограничениями целостности, поскольку они выражают требование внутренней согласованности и непротиворечивости значений переменных Xij и yj.

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

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

1) полные, частично полные и неполные задачи группировки;

2) группировки со стоимостью активации потенциальных центров;

3) группировки с некоторыми видами ресурсных ограничений;

4) группировки с ограничением на одновременное вхождение;

5) группировки с ограничением на структуру группы.

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

d« = Cn(Si) - (fcKnCn(sj) + fccnCn(si) + Кд(5<) + Сд(*0 + KT(si, Cj) + CT(si, cj)),

Vi = ^roni

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

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

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

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

Ограничения подобного вида предлагается представлять в виде дополнительных ограничений к рассмотренной выше базовой постановке задачи группировки как задачи математического программирования, сведя их к логическим функциям, задающим запрет на одновременное вхождение объектов в группу. Введем на множестве 5x5 логическую функцию 11д», определяемую следующим образом:

Тогда для учета ограничения на разброс параметра к списку ограничений базовой постановки задачи группировки как задачи математического программирования необходимо добавить ограничения вида:

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

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

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

6 ® : тахд(б) - ттдЫ < Д„.

1, если |д(:г) - q(y)\ > Д„; О, в противном случае.

Xi1j+Xi <1 ] 6 {1,...,ш}, ¿1, »2 6 {1,. ..,п}, 11а'(З{1,З<2) = 1.

стоимости2 в специальным образом построенной сети M'(V, Е,а, /). Принцип построения

Рис. 2. Вид сети для представления задачи полной группировки как задачи о потоке минимальной стоимости

сети M'(V, Е, а, /) следующий. Пусть множество вершин V = С U S U {s} U {í} U {<?}. То есть, в множестве вершин графа есть по одной вершине для каждого из элементов множества С U S, вершина-источник s, вершина-сток í и дополнительная фиктивная вершина q. Обозначение множества вершин V мы будем употреблять также и в функциональном контексте в качестве обозначения отображения между множествами исходных объектов и множеством вершин графа. При этом запись V(s¡) следует интерпретировать как «вершина графа, соответствующая объекту ,s¡». Множество дуг Е, вместе с отображениями а и /, задающими пропускные способности дуг и стоимости использования единицы пропускной способности, является объединением следующих множеств:

• множество дуг вида (V(cj), V(.9¡)), где s¡ е 5,с,- 6 С. Для таких дуг принимается

a(V(Cj), V(«<)) = оо, f(V(Cj), V(s,)) = -d(sit cj);

• множество дуг вида (s,V(cj)), где c¡ € С. Для таких дуг принимается a(s, V(cj)) = 1, f(s,V(Cj))= 0;

• множество дуг вида ¿)> гДе s¡ € S- Для таких дуг принимается a{V(si),t) — 1,

• дуга (s,q), для которой принимается

a(.S,g) = |S|-|q,/(5,9) = 0;

• множество дуг вида {s,V(cj)), где Cj 6 С. Для таких дуг принимается a(s, ^(с,)) = с», f(S,V(Cj)) = 0.

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

Для решения задачи нахождения потока минимальной стоимости существует множество алгоритмов, как псевдополиномиальных, так и строго полиномиальных. Лучший из известных автору алгоритмов принадлежит J.B. Orlin и имеет сложность 0((тlog п)(т + nlogn)), где пат — количества вершин и дуг сети соответственно.

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

2 Bertsekas D. Linear Network Optimization: Algorithms and Codes. The MIT Press, 1991

задачи полной группировки пропускная способность этой дуги была т — п, здесь же предлагается рассмотреть сети с любой целочислепной пропускной способностью соответствующей дуги, попадающей в определенный интервал 3. Фактически, речь идет о семействе сетей М', элементами которого являются сети М'[х], построенные по изложенным выше правилам и имеющие пропускную способность дуги с(в, д) = х.

Рис. 3. Вид сети М'[х]

В работе доказывается, что решение задачи централизованной группировки с простейшей системой показателей является максимальным потоком минимальной стоимости в одной го сетей семейства М'[х]|0<1^т-„.

Таким образом, предлагаемый метод полной по С централизованной группировки с простейшей системой показателей заключается в последовательном рассмотрении сетей М'[0],Л/'[1],..., М'[тп — п] и нахождении в них максимальных потоков минимальной стоимости. Результат группировки получается выбором одного из решений т — п + 1 подзадач, обладающего наименьшим значением стоимости.

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

Суть алгоритма заключается в том, что все пары упорядочиваются по убыва-

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

ется в группу с центром в с,.

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

Сложность этих алгоритмов оценивается как 0(mnlog(mrг)).

В системе показателей со стоимостью активации определена стоимость образования группы на основе заданного объекта из С; эта стоимость задается отображением Р: С К.

В работе рассмотрены четыре варианта централизованной группировки с такой системой показателей.

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

Полная по S и неполная разновидности этой задачи не сводимы к потоку, но представляют собой хорошо изученную задачу дискретной оптимизации, известную под названием «простейшая задача размещения» (uncapacitated factory location problem). Эта задача является NP-трудной и для ее решения можно воспользоваться классическими методами точного решения задач ЦЛП или приближенными методами; в данной работе для решения практических задач формирования промышленно-сырьевых узлов, сводимых к данному виду задачи группировки, используется три способа: применение универсального решателя SCIP для получения точных решений и генетический алгоритм и разновидность метода локального поиска для получения приближенных.

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

Особенность системы показателей с линейной стоимостью и бесплатным порогом состоит в том, что в рамках нее каждый сателлит характеризуется некоторым количеством ресурса (R: S R), а для каждого центра указан порог (L: С R), до превышения которого штраф за образование группы с соответствующим центром отсутствует, а после превышения этот штраф растет пропорционально величине превышения с коэффициентом A: ChR.

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

m п m

Максимизировать г = ^ a{cj)Qi + сз) (8)

J=1 ¡=1 J=1

при ограничениях

9j<0 je {!,...,m}

П

Чз < Узl(Cj) - xiA3i)- J € {1,..., m}

¡=1

m

X^v^1 ie{i,...,n}

3=1

Хц «SVj г e {1,... ,n}, j e {1,... ,rn}

h e {0,i> i e {l,...,n}, j e {1,...,m}.

Переменная q здесь введена как способ избавиться от min в целевой функции (см. формулу 5).

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

• a(cj) полагается равным 1 для всех j;

• l(cj) считается неотрицательным для всех j\

• r(si) считается неотрицательным для всех »;

• речь идет только о неполной группировке.

Такой набор допущений связан с тем, что именно такая формальная постановка соответствует практической задаче формирования ПСУ, в том случае, если применяется стратегия учета существующих горно-обогатительных предприятий «без псевдоприбыли».

Данная задача относится к задачам частично-целочнсленного программирования. Для оценки применимости классических точных методов решения такого рода задач к задаче группировки с линейным порогом и бесплатной стоимостью в работе использован один из самых быстрых на данный момент3 коммерческих решателей задач линейного, целочисленного и квадратичного программирования — IBM ILOG CPLEX 12.4.

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

Выделены следующие характеристики:

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

Есе cKc)/E5esr(s);

• доля центров, у которых бесплатный порог больше 0;

• фаворитизм — неравномерность распределения значений в отображении D; эта характеристика применима, в основном, к синтетическим наборам, и может либо принимать значение «отсутствует», если для каждого сателлита значения отображения D формируются случайно в достаточно широких пределах или быть числом от 0 до 1, и тогда это число выражает для любого сателлита долю тех центров, значения отображения D для пары с которыми больше нуля, значения для остальных пар равны нулю;

• r-d отношение, вычисляемое как 22sesr(s)/ ¿Lcec d(s>с)-

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

Применение CPLEX к 840 наборам разных классов показало, что, с одной стороны, большинство наборов данных вплоть до достаточно больших размерностей (400-500) эффективно решаются этим инструментом, с другой стороны, выделен набор таких классов, решение которых представляет значительные трудности. Такими «трудными» классами оказались наборы исходных данных, обладающих плотностью 80-100%% и небольшой долей центров с бесплатным порогом (10-40%%). На таких наборах значительно медленнее происходит и поиск приближенных решений. В связи с этим, для быстрого получения приближенных решений, было разработано несколько вариантов алгоритмов решения задачи группировки с линейной стоимостью и бесплатным порогом, основанных на локальном поиске. А именно:

• локальный поиск со случайным стартом;

• метод «Лидер группы»4;

• вариант схемы GRASP (Greedy Randomized Adaptive Search — вероятностный жадный алгоритм поиска).

3 начало 2012 года

4 Кочетов Ю. А. Методы локального поиска для дискретных задач размещения. Дисс. на соискание степени доктора ф.-м. наук, Новосибирск, 2009

Рис. 4. Время работы CPLEX при поиске точного решения

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

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

Для всех методов средняя погрешность оказалась в пределах 5%, лучшие результаты получены применением локального поиска со случайным стартом и методом «Лидер группы» (см. таблицу 2 и таблицу 3).

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

Таблица 2. Оценки средней погрешности для локального поиска

Вариант алгоритма Количество итераций Средняя погрешность

Старт с пустой группировки 1 4,5%

Старт со случайной группировки 100 2,9%

200 2,8%

300 2,7%

400 2,6%

500 2,6%

Таблица 3. Оценки средней погрешности для метода «Лидер группы»

Количество итераций Вероятность выбора (р)

0,25 0,5 0,75

100 2,8% 3,2% 3,6%

В четвертой главе описан набор программных модулей, предназначенных для решения различных видов задачи группировки, и осуществляется решение задачи геолого-экономического районирования месторождений Дальневосточного федерального округа (ДВФО) с помощью разработанных модулей. Источником данных о месторождениях является Государственный кадастр месторождений и проявлений полезных ископаемых.

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

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

По отношению к применяемым методам, разработанные модули можно разбить на три группы:

• модули, использующие какой-либо универсальный решатель (SCIP или CPLEX);

• модули, реализующие специальные алгоритмы (жадный алгоритм, вариант поиска

потока максимальной стоимости, локальный поиск и т.д.);

• модули, реализующие генетический алгоритм решения (на основе библиотеки GAlib).

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

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

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

Два исходных множества задачи группировки определялись следующим образом: множество S — сателлитов — являлось множеством месторождений, множество С — потенциальных центров групп —также являлось множеством месторождений (точнее, точек, совпадающих в пространстве с месторождениями) исходя из того, что создание горнообогатительного предприятия (ГОП), расположенного вблизи источника сырья, является

широко распространенной практикой в геолого-экономическом хозяйствовании.

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

30 = -Угоп + (¿к„СП + А;спСП + Кд + Сд + Кт + Ст), мсо

где КГоп — балансовая стоимость ГОП.

Такая модель вычисления затрат на формирования ПСУ соответствует системе показателей со стоимостью активации. А именно, отображение Г> задается выражением:

¿у = СП(в4) - (£кПСП(*) + ЛьпСП(а4) + Кд(вО + Сд(84) + Кт(«4, с,-) + Ст(в4, с,)), а отображение Р:

Рз = ^гоп-

Относительно этих исходных данных ставилась задача оптимальной централизованной группировки с системой показателей со стоимостью активации.

Узлы О

Легенда

мсо

• Центры фут х Сателлиты (Ъязи в группах

Рис. 5. Моносырьевые группы ГПТ «Оловянные» на фрагменте карты ДВФО

Результаты, полученные с применением разработанных алгоритмов к сформулированной задаче группировки, показали хорошее соответствие (95-98%) с результатами геолого-экономического районирования ДВФО, выполненного экспертами в области недропользования. На рисунке 5 показан фрагмент карты ДВФО с выделенными моносырьевыми узлами геолого-промышленного типа «Оловянные».

ОСНОВНЫЕ НАУЧНЫЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

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

6. Разработаны программные модули для решения различных вариантов задачи группировки, вошедшие в ГИС-ориентированную систему «Геолого-экономическая карта региона» (ВСЕГЕИ им. А.П. Карпинского). Некоторые модули реализуют авторские алгоритмы, другие являются «оболочками» к пакетам решения задач целочисленного и частично целочисленного программирования SCIP и CPLEX.

7. Разработанные модели и программные модули использованы при решении задачи формирования промышленно-сырьевых узлов на месторождениях твердых полезных ископаемых Дальневосточного федерального округа. Результат на 95-98% совпал с результатом работы независимой экспертной группы.

Полученные результаты соответствуют п.4 «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации» и п.9 «Разработка проблемно-ориентированных систем управления, принятия решений и оптимизации технических систем» паспорта специальности 05.13.01 — «Системный анализ, управление и обработка информации».

20

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

Опубликовано в рецензируемых изданиях из списка ВАК:

1. Пономарев А. В. Метод оптимальной группировки векторных объектов относительно центров / Мустафин Н. Г., Пономарев А. В., Савосин С. В. // Труды СПИИРАН. СПб: Наука, 2012. Вып. 1(20). С. 208-220

2. Пономарев А. В. Методы и алгоритмы группировки геологических объектов / Мустафин Н. Г., Пономарев А. В., Савосин С. В. // Информационно-измерительные и управляющие системы. 2009. Т. 4. С. 71—74.

3. Пономарев А. В. Программно-технологический комплекс Единой информационно-аналитической системы «Минерально-сырьевые ресурсы России» / Дубенецкий В. А., Кра-соткин С. И., Мустафин Н. Г. и др. // Программные продукты и системы. 2005. Т. 1. С. 9-13.

Опубликовано в других изданиях:

4. Пономарев А. В. Алгоритмическая поддержка задачи геолого-экономического районирования // Информационные технологии в экономике, образовании и бизнесе: материалы международной научно-практической конференции / Под ред. А. Зарайский. Саратов: Издательство ЦПМ «Академия Бизнеса», 2011. С. 150—153.

5. Пономарев А. В. Модель группировки объектов, основанная на бинарных отношениях // «Наука и техника XXI века»: материалы международной заочной научно-практической конференции. Новосибирск: Изд. «Априори», 2011. С. 90—93.

6. Пономарев А. В. Применение генетических алгоритмов для группировки объектов // Наука и современность - 2011: сборник материалов XIII Международной научно-практической конференции. Часть 2 / Под ред. С. Чернов. Новосибирск: Издательство НГТУ, 2011. С. 238-242.

7. Пономарев А. В. Использование метода локального поиска для решения задачи группировки объектов // Проблемы подготовки кадров в сфере инфокоммуникационных технологий. СПб научно-практическая конференция. СПб: Сборник трудов конференции / СПОИСУ, 2011. С. 62-67.

8. Пономарев А. В. Модель данных для решения аналитических задач в ГИС-ори-ентированной системе «Геолого-экономическая карта региона» / Водяхо А. И., Мустафин Н. Г., Первицкий А. Ю. и др. // Труды СПИИРАН. СПб: Наука, 2007. Т. 4. С. 345-356.

61 12-5/3042

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

ПОНОМАРЕВ Андрей Васильевич

МОДЕЛИ И МЕТОДЫ ГРУППИРОВКИ ОБЪЕКТОВ ДЛЯ ГЕОЛОГО-ЭКОНОМИЧЕСКОГО РАЙОНИРОВАНИЯ

Специальность 05.13.01 - Системный анализ, управление и обработка информации

(технические системы)

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель к. т. н.. доцент Мустафин Н. Г.

С анкт- Петербург 2012

Содержание

Введение ......................................................................................4

Глава 1. Геолого-экономическое районирование и группировка объектов 8

1.1. Геолого-экономическое районирование............................................8

1.1.1. О задаче геолого-экономического районирования......................8

1.1.2. Элементы экономической оценки минерально-сырьевой базы .... 12

1.1.3. Задача формирования промышленно-сырьевых узлов..................16

1.1.4. Модели формирования промышленно-сырьевых узлов................19

1.2. Задача группировки объектов......................................................28

1.2.1. О группировке объектов....................................................28

1.2.2. Кластерный анализ ........................................................29

1.2.3. Группировка в дискретной оптимизации................................33

1.2.4. Известные обобщения задачи группировки..............................38

Выводы......................................................................................39

Глава 2. Модели централизованной группировки .............................41

2.1. Формальная модель задачи группировки ........................................41

2.1.1. Терминология задачи группировки ......................................41

2.1.2. Типология задач группировки............................................43

2.2. Простейшая задача централизованной группировки............................45

2.2.1. Описание задачи............................................................45

2.2.2. Постановка задачи математического программирования..............46

2.2.3. Постановка задачи в терминах теории графов..........................48

2.2.4. Задача формирования ПСУ как простейшая централизованная группировка ......................................................................49

2.3. Задача централизованной группировки со стоимостью активации............51

2.3.1. Описание задачи............................................................51

2.3.2. Постановка задачи математического программирования..............51

2.3.3. Задача формирования ПСУ как централизованная группировка со стоимостью активации......................................................52

2.4. Модификации........................................................................53

2.4.1. Группировка с ресурсными ограничениями..............................53

2.4.2. Запреты на одновременное вхождение....................................58

2.4.3. Количественные ограничения..............................................59

2.5. Группировка векторных объектов..................................................60

Выводы........................................... 63

Глава 3. Методы и алгоритмы решения задачи группировки........ 65

3.1. Простейшая задача централизованной группировки.............. 65

3.1.1. Полная группировка........................................................65

3.1.2. Полная по С ................................................................69

3.1.3. Полная по S ................................................................72

3.1.4. Неполная....................................................................74

3.2. Задача централизованной группировки со стоимостью активации............77

3.2.1. Простейшая задача размещения..................... 78

3.2.2. Анализ задачи............................... 79

•3.2.3. Подготовка исходных данных для эксперимента............ 82

3.2.4. Генетические алгоритмы ..................................................84

3.2.5. Метод локального поиска..................................................93

3.3. Группировка с линейной стоимостью и бесплатным порогом..................95

3.3.1. Наборы данных для экспериментального исследования методов решения ........................................................................97

■3.3.2. Решение с применением CPLEX..................... 98

3.3.3. Локальный поиск..............................100

3.3.4. Метод «Лидер группы»..........................101

3.3.5. Вероятностные жадные алгоритмы поиска (GRASP).........102

Выводы...........................................103

Глава 4. Практическое решение задачи геолого-экономического районирования ............................................106

4.1. Библиотека модулей группировки.........................106

4.1.1. Модули для решения простейшей задачи группировки........106

4.1.2. Модули для решения задачи группировки со стоимостью активации 106

4.2. Решение задачи геолого-экономического районирования для федерального округа ........................................111

4.2.1. Исходные данные..............................111

4.2.2. Результаты.................................113

Выводы...........................................113

Заключение .........................................116

Литература..........................................117

Введение

Актуальность темы диссертации.

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

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

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

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

Для достижения поставленных целей были решены следующие задачи:

1) проведен обзор классических оптимизационных задач, связанных с группировкой объектов;

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

3) проведена классификация видов задачи группировки и для распространенных подклассов задачи группировки сформулированы эквивалентные задачи математического программирования;

4) для ряда разновидностей задачи группировки объектов разработаны новые или адаптированы существующие алгоритмы решения и произведена' оценка эффективности разработанных алгоритмов на синтетических наборах данных;

5) показана связь некоторых видов абстрактных задач группировки с предложенными моделями формирования промышленно-сырьевых узлов;

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

Основные положения, выносимые на защиту:

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

2. Методы решения вариантов задачи группировки объектов, возникающих при использовании предлагаемых моделей формирования промышленно-сырьевых узлов.

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

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

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

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

зовать разработанные методы и алгоритмы при решении задач централизованной

группировки объектов.

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

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

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

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

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

Реализация результатов работы. Исследования, отраженные в диссертации, поддержаны грантом РФФИ №09-07-00436-а «Онтолого-ориентированное управление гибкими сетевыми организациями» и проектом Президиума РАН №2.13 «Разработка теоретических основ и интеллектуальных моделей для поддержки принятия решений при управлении гибкими сетевыми организациями», 2009-2011.

Апробация полученных в диссертации результатов подтверждена актами об использовании результатов диссертационной работы в процессе обучения студентов в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» и в научно-

исследовательской работе по государственному контракту №АЛ-04-06/9 «Разработка программно-технологического комплекса, обеспечивающего построение, мониторинг и функционирование ГИС-ориентированной системы для составления геолого-экономических карт федеральных округов России» совместно с Всероссийским научно-исследовательским геологическим институтом (ВСЕГЕИ) им. А.П. Карпинского.

Апробация результатов работы. Основные положения и результаты диссертации представлялись на следующих конференциях: «Информационные технологии в экономике, образовании и бизнесе» (Саратов, 2011), «Наука и техника XXI века» (Новосибирск, 2011), «Наука и современность — 2011» (Новосибирск, 2011), «Проблемы подготовки кадров в сфере инфокоммуникационных технологий» (Санкт-Петербург, 2011), а также на городском семинаре «Информатика и компьютерные технологии» (СПИИРАН, Санкт-Петербург, 2012).

Публикации. Материалы диссертации опубликованы в 8 печатных работах, в том числе в 3 рецензируемых изданиях из списка ВАК.

Структура и объем работы. Диссертация объемом 123 страницы содержит введение, четыре главы, заключение, список литературы (81 наименование), 22 рисунка, 10 таблиц.

Глава 1

Геолого-экономическое районирование и группировка

объектов

1.1. Геолого-экономическое районирование

1.1.1. О задаче геолого-экономического районирования

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

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

В современных работах, посвященных геолого-экономическому районированию и построению геолого-экономических карт [1-3], рассматривается следующий ряд объектов

геолого-экономического районирования:

1. промышленно-сырьевые объекты (ПСО);

2. промышленно-сырьевые узлы (ПСУ);

3. геолого-экономические районы (ГЭР);

4. горно-промышленные комплексы (ГПК).

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

Хивовчан

Охотничье

О

Бургачан

Южное

О

Лунное

Хрустальное О

Рис. 1.1. Пример районирования — исходные объекты

Бургачан

Рис. 1.2. Пример районирования — промышленно-сырьевые узлы

На рисунках 1.1, 1.2, 1.3 показан пример того, как происходит укрупнение объектов при переходе от одного уровня районирования к другому. Кругами обозначены место-

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

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

Важность рационального формирования промышленно-сырьевых узлов обусловлена следующими положениями:

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

• в [4, 5] при рассмотрении перспектив развития государственной политик