Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах
В статье показан алгоритм поиска кратчайшего пути между двумя выделенными вершинами на примере сети отредактированного в необходимом формате компонента несвязного исходного графа выбора рациональных цепочек разработки угольных пластов мощностью от 0.8 до 2.2 м....
Збережено в:
| Дата: | 2013 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут фізики гірничих процесів НАН України
2013
|
| Назва видання: | Физико-технические проблемы горного производства |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/108277 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах / В.Г. Гринев, П.П. Николаев // Физико-технические проблемы горного производства: Сб. научн. тр. — 2013. — Вип. 16. — С. 162-168. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-108277 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1082772016-11-02T03:02:56Z Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах Гринев, В.Г. Николаев, П.П. Технико-экономические проблемы горного производства В статье показан алгоритм поиска кратчайшего пути между двумя выделенными вершинами на примере сети отредактированного в необходимом формате компонента несвязного исходного графа выбора рациональных цепочек разработки угольных пластов мощностью от 0.8 до 2.2 м. У статті показано алгоритм пошуку найкоротшого шляху між двома виділеними вершинами на прикладі мережі відредагованого в необхідному форматі компонента незв'язного початкового графа вибору раціональних ланцюжків розробки вугільних пластів потужністю від 0.8 до 2.2 м. In the article on the example of network of edited in a necessary format component of incoherent initial count of choice of rational chainlets of development of coal layers by power from 0.8 to 2.2 m is shown algorithm of search of short cut between two selected tops. 2013 Article Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах / В.Г. Гринев, П.П. Николаев // Физико-технические проблемы горного производства: Сб. научн. тр. — 2013. — Вип. 16. — С. 162-168. — Бібліогр.: 12 назв. — рос. XXXX-0016 http://dspace.nbuv.gov.ua/handle/123456789/108277 622: 33.003.55: 681.3 ru Физико-технические проблемы горного производства Інститут фізики гірничих процесів НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Технико-экономические проблемы горного производства Технико-экономические проблемы горного производства |
| spellingShingle |
Технико-экономические проблемы горного производства Технико-экономические проблемы горного производства Гринев, В.Г. Николаев, П.П. Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах Физико-технические проблемы горного производства |
| description |
В статье показан алгоритм поиска кратчайшего пути между двумя выделенными вершинами на примере сети отредактированного в необходимом формате компонента несвязного исходного графа выбора рациональных цепочек разработки угольных пластов мощностью от 0.8 до 2.2 м. |
| format |
Article |
| author |
Гринев, В.Г. Николаев, П.П. |
| author_facet |
Гринев, В.Г. Николаев, П.П. |
| author_sort |
Гринев, В.Г. |
| title |
Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах |
| title_short |
Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах |
| title_full |
Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах |
| title_fullStr |
Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах |
| title_full_unstemmed |
Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах |
| title_sort |
исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах |
| publisher |
Інститут фізики гірничих процесів НАН України |
| publishDate |
2013 |
| topic_facet |
Технико-экономические проблемы горного производства |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/108277 |
| citation_txt |
Исследование взаимосвязи типов очистного оборудования по алгоритмам оптимизации на сетях и графах / В.Г. Гринев, П.П. Николаев // Физико-технические проблемы горного производства: Сб. научн. тр. — 2013. — Вип. 16. — С. 162-168. — Бібліогр.: 12 назв. — рос. |
| series |
Физико-технические проблемы горного производства |
| work_keys_str_mv |
AT grinevvg issledovanievzaimosvâzitipovočistnogooborudovaniâpoalgoritmamoptimizaciinasetâhigrafah AT nikolaevpp issledovanievzaimosvâzitipovočistnogooborudovaniâpoalgoritmamoptimizaciinasetâhigrafah |
| first_indexed |
2025-07-07T21:14:03Z |
| last_indexed |
2025-07-07T21:14:03Z |
| _version_ |
1837024248437145600 |
| fulltext |
Физико-технические проблемы горного производства 2013, вып. 16
162
Раздел 4. Технико-экономические проблемы горного производства
УДК 622: 33.003.55: 681.3
В.Г. Гринев1, П.П. Николаев2
ИССЛЕДОВАНИЕ ВЗАИМОСВЯЗИ ТИПОВ ОЧИСТНОГО
ОБОРУДОВАНИЯ ПО АЛГОРИТМАМ ОПТИМИЗАЦИИ
НА СЕТЯХ И ГРАФАХ
1ИФГП НАН Украины
2Донецкая облгосадминистрация
В статье показан алгоритм поиска кратчайшего пути между двумя выделенными
вершинами на примере сети отредактированного в необходимом формате компо-
нента несвязного исходного графа выбора рациональных цепочек разработки
угольных пластов мощностью от 0.8 до 2.2 м.
Ключевые слова: граф, сетевая модель, алгоритм оптимизации, взаимосвязь, рацио-
нальная эксплуатация.
Современный уровень угледобычи предъявляет высокие требования к
инженерному обеспечению подземных горных работ и обоснованности при-
нимаемых инженерных решений. Если по определению параметр – это ве-
личина, характеризующая какое-либо свойство процесса, явления или си-
стемы, машины, прибора, то технологических параметров, имеющих отно-
шение к добыче угля, насчитывается не менее двух десятков.
Область, которая определяется всеми проектными параметрами, – это
пространство проектирования. Оно не так велико, как может показаться, по-
скольку обычно ограничено рядом условий, связанных с физической сущно-
стью задачи. Ограничения могут быть такими значительными, что задача не
будет иметь ни одного удовлетворительного решения.
Для горных задач еще в 90-е годы прошлого столетия введено понятие
области рационального проектирования [1]. Как пример деятельности вне
области рационального проектирования можно назвать результаты оснаще-
ния шахт новыми комплексами с техническими характеристиками по суточ-
ной нагрузке до 1500 т. Предполагалось, что создание техники позволит
обеспечить стабильно высокие нагрузки в сложных горно-геологических
условиях. Однако, несмотря на явный прогресс в нашей стране в создании
такой техники, наблюдается падение добычи угля [2].
Изучение области фактического применения комплексов на шахтах Донбас-
са показывает, что задача выбора области рациональной эксплуатации горно-
file://////современный
Физико-технические проблемы горного производства 2013, вып. 16
163
шахтного оборудования характеризуется линейной целевой функцией и линей-
ными ограничениями. Для решения таких задач успешно могли бы применять-
ся известные методы линейного программирования. Однако характерной осо-
бенностью задач выбора горно-шахтного оборудования для конкретных усло-
вий является большая размерность, обусловливающая необходимость поиска
более эффективных алгоритмов оптимизации. О значительном количестве ва-
риантов выбора оборудования в настоящее время говорит факт существования
в Украине большого разнообразия типов очистного оборудования [3].
Общеизвестно, что основополагающими конструкционными принципами
увязки механизированного очистного комплекса являются параметрические,
функциональные и конструктивные связи составных частей комплекса – кре-
пи, комбайна, конвейера, которые должны учитывать конкретные горно-
геологические условия и требования безопасности. Фактические данные сов-
местной работы разных типов очистного оборудования показывают, что ко-
нечный результат в виде безопасной нагрузки на очистной забой в значитель-
ной степени зависит от взаимной обусловленности типов такого оборудова-
ния друг другом (философская категория – взаимосвязь) [4]. Если рассматри-
вать проблему рациональной эксплуатации оборудования при добыче угля
под углом зрения решения задач комбинаторики, то плодотворной основой
для построения вычислительных алгоритмов выбора рациональной эксплуа-
тации оборудования может служить их представление на сетях и графах. Этот
раздел математики имеет широкое практическое приложение, поскольку до-
вольно хорошо разработаны алгоритмы оптимизации на сетях и графах [5–7].
Сложная прикладная задача выбора технологической цепочки горного
очистного оборудования для конкретных горно-геологических и горно-
технических условий, которая не решается традиционными методами, может
быть сформулирована как задача теории графов. Для этого необходимо про-
двигаться от физического смысла задачи к алгоритмическим построениям.
В результате графоаналитической экспертной оценки области рациональ-
ной эксплуатации отечественного очистного оборудования был построен граф
выбора рациональных технологических цепочек (рис. 1), на котором пред-
ставлены варианты эффективной разработки угольных пластов для диапазона
мощности пласта от 0.8 до 2.2 м с разбивкой на 7 отдельных областей.
Данный граф G является не связным, поскольку число его компонент
связности равно c(G) = 7. Вершина диапазона мощности m2 = (1.01–1.2) м
имеет наибольшую степень δ(m2) = 6. Для вершины m1 = (0.81–1.0) м δ(m1) = 5,
а для m4 = (1,41–1.6) м δ(m4) = 4. Для m5 = (1.61–1.8) м имеется только две
альтернативы, а для остальных трех областей диапазона мощности угольно-
го пласта соответствующие вершины имеют единичную степень.
Несвязный ориентированный граф G с семью компонентами, в которых
начальная и конечная вершины связаны между собой отношением достижи-
мости, имеет в каждом подграфе (компоненте) цепь: <m1,g1>; <m2,g2>;
<m3,g3>; <m4,g4>; <m5,g5>; <m6,g6>; <m7,g7>.
Физико-технические проблемы горного производства 2013, вып. 16
164
Рис. 1. Граф выбора рациональных технологических цепочек разработки угольных
пластов мощностью от 0,8 до 2,2 м
Физико-технические проблемы горного производства 2013, вып. 16
165
Поиск минимальных затрат в цепях заключается в определении радиуса
или наименьшего расстояния между вершинами. Для выяснения макси-
мального результата по добыче угля необходимо рассчитать диаметр цепи
или наибольшее расстояния между начальной и конечной вершинами
маршрута.
Для каждой области эксплуатации построен свой компонент исходного
графа [8]. Проведенная экспертная оценка области рациональной эксплуата-
ции очистного оборудования показала, что для мощностей пласта 1,21–1,4,
1,81–2,0 и 2,01–2,2 м существует только по одному варианту цепочки крепь-
комбайн-конвейер, которые показывают максимальный вариант. В рассмат-
риваемых условиях Донбасса конкурентов среди отечественных механизи-
рованных крепей нет. В остальных компонентах графа присутствует до-
вольно много альтернатив для выбора комплектов оборудования. Компонент
исходного графа для мощности 0,8–1,0 м и его сетевая модель подробно
описаны в [8].
В настоящей работе на примере этой сети показан алгоритм оптимизации
модели выбора очистного оборудования путем поиска кратчайшего пути
между двумя выделенными вершинами.
Прежде чем представлять алгоритм, необходимо ввести некоторые обо-
значения и произвести правки. Вершины графа выбора рациональных тех-
нологических цепочек (см. рис. 1), которые имеют отношение к мощности
угольного пласта mi и длине лавы li, относятся к параметрам, определяющим
выбор рабочего компонента исходного графа G, и не принимают участия в
алгоритме оптимизации.
Вершины vi, которые фиксируют конечный результат эксплуатации ком-
плекса оборудования по достигаемой суточной нагрузке очистного забоя,
также не участвуют в алгоритме поиска кратчайшего пути, поскольку они
участвуют в выборе варианта технологической цепочки по критерию мак-
симальной добычи графо-аналитическим способом.
В качестве исходного графа продолжаем исследовать первый компо-
нент c1(G) исходного графа G [8]. На рис. 2 представлена сеть отредакти-
рованного в необходимом формате первого компонента несвязного ис-
ходного графа.
Каждой дуге (x, y) сети исходного графа G поставим в соответствие чис-
ло a(x, y). Если в сети отсутствует некоторая дуга (x, y), положим a(x, y) = ∞.
Будем называть число a(x, y) длиной дуги (x, y) и интерпретировать его
как соответствующие затраты при добыче угля. Определим длину пути
как сумму длин отдельных дуг, составляющих этот путь. Для любых двух
вершин s и t сети графа G могут существовать несколько путей, соединя-
ющих вершину s с вершиной t. Рассмотрим алгоритм, который определя-
ет такой путь, ведущий от вершины s к вершине t и имеющий минималь-
но возможную длину. Этот путь называется кратчайшим путем между
вершинами s и t.
Физико-технические проблемы горного производства 2013, вып. 16
166
Описываемый в работе [9] алгоритм позволяет находить в сети кратчай-
ший путь между двумя выделенными вершинами и при положительных
длинах дуг. Данный алгоритм, предложенный в 1959 г. Дейкстрой [10], счи-
тается одним из наиболее эффективных алгоритмов решения задачи.
Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста.
Предположим, что нам известны m вершин, ближайших к вершине s (бли-
зость любой вершины x к вершине s определяется длиной кратчайшего пути,
ведущего от s к x). Пусть также известны сами кратчайшие пути, соединяю-
щие вершину s с выделенными m вершинами (длина пути, не содержащего
дуги, принимается равной нулю).
Покажем теперь, как может быть определена (m + 1)-я ближайшая к s
вершина. Окрасим вершину s и m ближайших к ней вершин (в данном алго-
ритме необходимо выделять вершины и дуги только одной категории, по-
этому цвета окраски не указываются). Построим для каждой неокрашенной
вершины y пути, непосредственно соединяющие с помощью дуг (x, y) каж-
дую окрашенную вершину x с y. Выберем из этих путей кратчайший и будем
считать его условно кратчайшим путем от вершины s к вершине y.
Какая же из неокрашенных вершин является (m + 1)-й ближайшей к s
вершиной? Та, для которой условно кратчайший путь имеет наименьшую дли-
ну. Это обусловливается тем, что кратчайший путь от вершины s к (m + 1)-й
ближайшей вершине при положительном значении длин всех дуг должен
содержать в качестве промежуточных лишь окрашенные вершины, т.е. вер-
шины, входящие в число m вершин, ближайших к вершине s.
Итак, если известны m ближайших к s вершин, то (m + 1)-я ближайшая к s
вершина может быть найдена так, как это описано выше. Начиная с m = 0,
описанная процедура может повторяться до тех пор, пока не будет получен
кратчайший путь, ведущий от s-вершины к вершине t. Формально алгоритм
Дейкстры описан в работе [11].
Рис. 2. Отредактированная модель вы-
бора очистного оборудования для диа-
пазона мощности 0,8–1,0 м в условиях
шахт Донбасса
Физико-технические проблемы горного производства 2013, вып. 16
167
Таким образом, впервые для рационального выбора очистного оборудо-
вания на угольных шахтах Донбасса построены сетевые модели и обосно-
ваны классические алгоритмы оптимизации графов: для нахождения крат-
чайшего пути между двумя выделенными вершинами – алгоритм
Дейкстры, а для кратчайшего пути между каждой парой вершин – алго-
ритм Флойда [12].
Направление, связанное с приложением теории графов к решению горных
проблем, может иметь большую перспективу для решения фундаментальной
проблемы высвобождения метана из угольного массива. Идея представления
углегазовой структуры в виде графа может оказаться результативной, так как в
свое время значительный скачок в развитии теории графов был связан именно с
распространением представления о молекулярном строении вещества.
1. Гринев В.Г. Решение горных задач на ЭВМ при освоении рудных месторожде-
ний / В.Г. Гринев, В.П. Зубков, В.Ю. Изаксон, С.П. Шкулев. – Новосибирск:
Наука. Сибирская издательская фирма РАН, 1999. – С. 215.
2. Николаев П.П. Исследование области рациональной эксплуатации очистного
оборудования на шахтах Донбасса с помощью теории графов и программы
STATISTICA / П.П. Николаев // Материалы Межд. конф. «Форум горняков
2012». – Днепропетровск, 2012. – С. 56.
3. Гринев В.Г. Обоснование технологических параметров выемки угля на углега-
зовых месторождениях / В.Г. Гринев, Г.П. Стариков, С.Е. Дегтярь, П.П. Нико-
лаев // Материалы ІІ Межд. конф. «Подземные катастрофы: модели, прогноз,
предупреждение». – Днепропетровск: НГУ. – 2011. – С. 24–30.
4. Советский энциклопедический словарь / М.: Советская энциклопедия, 1998. –
Изд. 4-е. – 1599 с.
5. Аляев Ю.А. Дискретная математика и математическая логика: учебник / Ю.А. Аля-
ев, С.Ф. Тюрин. – М.: Финансы и статистика, 2006. – 368 с.
6. Алексеев В.Б. Дискретная математика / Московский государственный универси-
тет им. Ломоносова. – М., 2002. – 44 с.
7. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж.
Хопкроф. – М.: Мир, 1979. – 536 с.
8. Гринев В.Г. Приложение теории графов для эффективного выбора очистного
оборудования на шахтах Донбасса / В.Г. Гринев, П.П. Николаев // Физико-
технические проблемы горного производства. – 2011. – №14. – С. 166–172.
9. Майника Э. Алгоритмы оптимизации на сетях и графах / Э. Майника: Пер. с
англ. – М.: Мир, 1981. – 323 с.
10. Dijksatra E.W. A note on two problems in connexion with graphs / E.W. Dijksatra //
Numer Math. – 1959. – V. 1. – P. 269–271.
11. Гринев В.Г. Алгоритмы оптимизации сетевых моделей для выбора рациональ-
ных технологических цепочек очистного оборудования / В.Г. Гринев, П.П. Ни-
колаев // Материалы 3-й Межд. науч.-техн. конф. «Техногенные катастрофы:
модели, прогноз, предупреждение». – Днепропетровск: НГУ, 2013. – C. 90–95.
12. Floyd R.Z. Algorithm 97, Shortest Path, Comm. ACM, 5, p. 345, 1962.
Физико-технические проблемы горного производства 2013, вып. 16
168
В.Г. Гріньов, П.П. Ніколаєв
ДОСЛІДЖЕННЯ ВЗАЄМОЗВ'ЯЗКУ ТИПІВ ОЧИСНОГО ОБЛАДНАННЯ
ПО АЛГОРИТМАХ ОПТИМІЗАЦІЇ НА МЕРЕЖАХ І ГРАФАХ
У статті показано алгоритм пошуку найкоротшого шляху між двома виділеними
вершинами на прикладі мережі відредагованого в необхідному форматі компонента
незв'язного початкового графа вибору раціональних ланцюжків розробки вугільних
пластів потужністю від 0.8 до 2.2 м.
Ключовi слова: граф, мережева модель, алгоритм оптимізації, взаємозв‘язок, раціо-
нальна експлуатація
V. Grinyov, P. Nikolaev
RESEARCH OF INTERCOMMUNICATION OF TYPES OF CLEANSING
EQUIPMENT ON ALGORITHMS OF OPTIMIZATION ON NETWORKS
AND COLUMNS
In the article on the example of network of edited in a necessary format component of
incoherent initial count of choice of rational chainlets of development of coal layers by
power from 0.8 to 2.2 m is shown algorithm of search of short cut between two selected
tops.
Keywords: graph, the network model, an algorithm optimization, interaction, rational
exploitation
|