WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


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

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

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

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

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

Научный консультант:

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

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

доктор технических наук, профессор, зав. лабораторией СПИИРАН Александров Виктор Васильевич кандидат технических наук, доцент, Балтийский государственный технический университет «ВОЕНМЕХ» им. Д.Ф.Устинова Королев Сергей Николаевич

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

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

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

Автореферат разослан « » 2012 г.

Ученый секретарь диссертационного совета Д.002.199.кандидат технических наук Ф.Г. Нестерук

Общая характеристика работы

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

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

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

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

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

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

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 рисунка, таблиц.

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1. Основные затратные показатели Добыча Обогащение Транспорт Капитальные КД КП КТ Эксплуатационные СД СП СТ Суммарные затраты на формирование ПСУ символически можно записать следую­ щим образом:

ЗО = (КП + СП) + (КД + СД + КТ + СТ). (1) МСО Это выражение является ядром предлагаемой базовой модели формирования ПСУ. Мо­ дель названа базовой, поскольку она задает общую идею поиска, но она не может быть применена непосредственно без уточнения того, как именно вычисляются параметры, в нее входящие — для некоторых параметров могут применяться существенно различные стратегии.

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

Знак суммирования по «МСО» следует понимать как суммирование по всем месторожде­ ниям (минерально-сырьевым объектам), входящим в состав узла.

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

ЗО = kкп СП + kсп СП + (КД + СД + КТ + СТ) = МСО МСО МСО = (kкпСП + kспСП + КД + СД + КТ + СТ). (2) МСО В таком виде выражение все еще не может быть использовано, поскольку в нем не раскрыт способ вычисления КД, СД, КТ и СТ. Для вычисления первых двух величин в работе так­ же используется метод корреляционных зависимостей, последняя же пара, обозначающая полные затраты на транспортировку руды от места добычи к месту обогащения, может оцениваться различными способами, в зависимости от имеющейся информации, и зада­ ет одну из стратегий расширения базовой модели. В работе рассматриваются следующие реализации этой стратегии:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В работе вводится понятие базовой группы. Базовой группой G, заданной на семей­ стве исходных множеств O называется набор множеств (1) (2) (k) G = (OG, OG,..., OG ) таких, что (i) OG O(i), i {1,..., k}.

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

Группировку G на семействе исходных множеств O определим как множество попарно не пересекающихся базовых групп на этом семействе. То есть, G = {G}, (3) (G1, G2)|G1, G2 G G1 G2 = (4) Группировка G называется полной по O(i) тогда и только тогда, когда O(i)(G) = O(i).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Централизованная группировка предполагает, что семейство исходных множеств O состоит из двух множеств: множества первичных объектов O(1) и множества потенциаль­ ных центров групп O(2), относительно которых происходит объединение первичных объ­ ектов. При рассмотрении этого вида группировок будем пользоваться альтернативным обозначением этих множеств S и C соответственно.

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

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

Простейшая система показателей. Предполагается, что задано одно отображение D : S C R. Оценка группы вычисляется по формуле:

val(G) = d(s, C(G)).

sS(G) Система показателей со стоимостью активации. Здесь, помимо D, задано отобра­ жение P : C R. Оценка группы вычисляется по формуле:

val(G) = -p(C(G)) + d(s, C(G)).

sS(G) Система показателей с линейной стоимостью и бесплатным порогом. Помимо D, заданы отображения R: S R, L: C R и A: C R, а оценка группы вычисляет­ ся так:

val(G) = d(s, C(G)) + a(C(G)) · min(0, l(C(G)) - r(s)). (5) sG(S) sS(G) Смысл параметров определяется прикладной задачей, сводимой к данной задаче группировки.

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

n m Максимизировать z = xijd(si, cj) (6) i=1 j=при ограничениях m xij 1 i {1,..., n} (7-а) j=xij yj i {1,..., n}, j {1,..., m} (7-б) xij, yj {0, 1} i {1,..., n}, j {1,..., m}.

Здесь переменные вида xij — признак вхождения объекта si в группу с центром в cj, а yj — признак образования группы с центром в cj. Если не указано иное, то n здесь и далее обозначает |S|, а m обозначает |C|.

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

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

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

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

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

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

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

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

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

dij = СП(si) - (kкпСП(si) + kспСП(si) + КД(si) + СД(si) + КТ(si, cj) + СТ(si, cj)), pj = VГОП, под VГОП здесь понимается балансовая стоимость действующего горно-обогатительного предприятия. Для вычисления КД и СД может применяться метод корреляционных за­ висимостей, а способ вычисления транспортных затрат КТ и СТ определяется доступной информацией (о сетях транспорта).

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

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

G G : max q(s) - min q(s) q.

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

1, если |q(x) - q(y)| > q;

q R (x, y) = 0, в противном случае.

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

q xi,j + xi,j 1 j {1,..., m}, i1, i2 {1,..., n}, R (si, si ) = 1.

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

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

Метод решения задачи полной централизованной группировки с простейшей систе­ мой показателей основывается на том, что в графовой интерпретации эта задача известна как m n задача о назначениях и может быть сведена к поиску потока минимальной стоимости2 в специальным образом построенной сети M(V, E, a, f). Принцип построения inf inf s t inf m-n inf q Рис. 2. Вид сети для представления задачи полной группировки как задачи о потоке минимальной стоимости сети M(V, E, a, f) следующий. Пусть множество вершин V = C S {s} {t} {q}. То есть, в множестве вершин графа есть по одной вершине для каждого из элементов множе­ ства C S, вершина–источник s, вершина–сток t и дополнительная фиктивная вершина q. Обозначение множества вершин V мы будем употреблять также и в функциональном контексте в качестве обозначения отображения между множествами исходных объектов и множеством вершин графа. При этом запись V (si) следует интерпретировать как «верши­ на графа, соответствующая объекту si». Множество дуг E, вместе с отображениями a и f, задающими пропускные способности дуг и стоимости использования единицы пропускной способности, является объединением следующих множеств:

множество дуг вида V (cj), V (si), где si S, cj C. Для таких дуг принимается a(V (cj), V (si)) = , f(V (cj), V (si)) = -d(si, cj);

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

множество дуг вида V (si), t, где si S. Для таких дуг принимается a(V (si), t) = 1, f(V (si), t) = 0;

дуга s, q, для которой принимается a(s, q) = |S| - |C|, f(s, q) = 0;

множество дуг вида s, V (cj), где cj C. Для таких дуг принимается a(s, V (cj)) = , f(s, V (cj)) = 0.

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

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

Полная по C централизованная группировка с простейшей системой показателей мо­ жет быть решена с помощью обобщения предыдущей задачи. Сеть для решения строится аналогичным образом, но иначе задается пропускная способность дуги (s, q) - в случае Bertsekas D. Linear Network Optimization: Algorithms and Codes. The MIT Press, 19задачи полной группировки пропускная способность этой дуги была m - n, здесь же пред­ лагается рассмотреть сети с любой целочисленной пропускной способностью соответству­ ющей дуги, попадающей в определенный интервал 3. Фактически, речь идет о семействе сетей M, элементами которого являются сети M[x], построенные по изложенным выше правилам и имеющие пропускную способность дуги c(s, q) = x.

inf inf s t inf X inf q Рис. 3. Вид сети M[x] В работе доказывается, что решение задачи централизованной группировки с про­ стейшей системой показателей является максимальным потоком минимальной стоимости в одной из сетей семейства M[x]|0 x m-n.

Таким образом, предлагаемый метод полной по C централизованной группировки с простейшей системой показателей заключается в последовательном рассмотрении сетей M[0], M[1],..., M[m - n] и нахождении в них максимальных потоков минимальной стои­ мости. Результат группировки получается выбором одного из решений m-n+1 подзадач, обладающего наименьшим значением стоимости.

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

Суть алгоритма заключается в том, что все пары si, cj упорядочиваются по убыва­ нию значения отображения d(si, cj) и далее анализируются последовательно. Если si из пары si, cj, рассматриваемой на очередном шаге, еще не входит в группу, то он включа­ ется в группу с центром в cj.

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

Сложность этих алгоритмов оценивается как O(mn log(mn)).

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

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

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

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

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

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

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

m n m Максимизировать z = a(cj)qj + xijd(si, cj) (8) j=1 i=1 j=при ограничениях qj 0 j {1,..., m} n qj yjl(cj) - xijr(si). j {1,..., m} i=m xij 1 i {1,..., n} j=xij yj i {1,..., n}, j {1,..., m} xij, yj {0, 1} i {1,..., n}, j {1,..., m}.

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

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

А именно, принимаются следующие допущения:

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

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

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

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

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

Данная задача относится к задачам частично-целочисленного программирования.

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

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

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

плотность набора, выражающая соотношение между бесплатными границами и суммарным объемом ресурса всех сателлитов. Плотность вычисляется по формуле l(c)/ r(s);

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

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

r–d отношение, вычисляемое как r(s)/ d(s, c).

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

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

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

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

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

начало 2012 года Кочетов Ю. А. Методы локального поиска для дискретных задач размещения. Дисс. на соискание степени доктора ф.-м. наук, Новосибирск, 20 Время, с 160 1 1 1 Плотность, % Отношение, % 1Рис. 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. Оценки средней погрешности для метода «Лидер группы» Количество Вероятность выбора (p) итераций 0, 25 0, 5 0, 100 2, 8% 3, 2% 3, 6% В четвертой главе описан набор программных модулей, предназначенных для ре­ шения различных видов задачи группировки, и осуществляется решение задачи геолого­ экономического районирования месторождений Дальневосточного федерального округа (ДВФО) с помощью разработанных модулей. Источником данных о месторождениях яв­ ляется Государственный кадастр месторождений и проявлений полезных ископаемых.

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

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

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

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

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

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

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

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

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

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

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

В этой модели затраты на формирование узла вычисляются по формуле:

ЗО = -VГОП + (kкпСП + kспСП + КД + СД + КТ + СТ), МСО где VГОП — балансовая стоимость ГОП.

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

dij = СП(si) - (kкпСП(si) + kспСП(si) + КД(si) + СД(si) + КТ(si, cj) + СТ(si, cj)), а отображение P :

pj = VГОП.

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

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

ОСНОВНЫЕ НАУЧНЫЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ В настоящей диссертационной работе решена важная актуальная задача обеспечения модельно-алгоритмической поддержки геолого-экономического районирования, имеющая большое значение для осуществления эффективной государственной политики в области экономики природопользования. В ходе решения данной задачи были получены следую­ щие результаты:

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

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

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Опубликовано в рецензируемых изданиях из списка ВАК:

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

СПб: Наука, 2012. Вып. 1(20). С. 208–22. Пономарев А. В. Методы и алгоритмы группировки геологических объектов / Мустафин Н. Г., Пономарев А. В., Савосин С. В. // Информационно-измерительные и управляющие системы. 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.







© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.