Тип работы:
Предмет:
Язык работы:


РАЗРАБОТКА МЕТОДА МАКСИМАЛЬНОГО СЕТЕВОГО ПОТОКА ПРИ ПЛАНИРОВАНИИ ДОБЫЧИ РУД В КАРЬЕРАХ НА ОСНОВЕ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Работа №71687

Тип работы

Дипломные работы, ВКР

Предмет

математика

Объем работы84
Год сдачи2017
Стоимость4260 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
338
Не подходит работа?

Узнай цену на написание


ВВЕДЕНИЕ 2
ГЛАВА 1. ОБЗОР И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1. Задача поиска предельных границ рудных месторождений 6
1.2. Модели карьера, задача определения границ 9
1.3. Условия оптимизации границ 11
1.4. Методы оптимизации 15
1.5. Метод вариантов 18
1.6. Плавающий конус 19
1.7. Методы теории графов: алгоритм Лерча-Гроссмана 22
1.8. Методы теории графов: алгоритм максимизации псевдопотока 24
1.9. Среды разработки программного обеспечения 27
1.10. Методики разработки параллельных программ 32
ГЛАВА 2. РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ ОПТИМИЗАЦИИ ГРАНИЦ КАРЬЕРОВ ПРИ ПОМОЩИ АЛГОРИТМА ПСЕВДОПОТОКА .. 36
2.1. Математическая постановка задачи 36
2.2. Модификация алгоритма псевдопотока для структуры данных в виде
октодерева 40
ГЛАВА 3. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ
РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ ГРАНИЦ КАРЬЕРОВ 43
3.1. Разработка интерфейсов ввода-вывода 43
3.2 Реализация алгоритма псевдопотока 47
ГЛАВА 4. ТЕСТИРОВАНИЕ ПРОГРАММЫ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ ГРАНИЦ КАРЬЕРОВ 50
4.1. Проведение тестирования работы программы 50
ЗАКЛЮЧЕНИЕ 52
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 53
ПРИЛОЖЕНИЕ


В настоящее время высокие информационные технологии играют важную роль не только в научной сфере, но и в повседневной жизни людей, так как они значительно упрощают и ускоряют любые процессы. Оптимизация алгоритмов является весьма актуальной задачей, поскольку позволяет выполнять расчеты быстрее и точнее, тем самым экономя рабочее время и ресурсы.
Целью научно-исследовательской работы является применение алгоритмов оптимизации границ карьеров по добыче руд для блочных моделей, а также наглядного представления (визуализации) данного процесса.
Основной задачей работы является реализация алгоритма максимального псевдопотока с использованием блочных моделей со структурой октодерева, что существенно сокращает время выполнения расчетов на сложных и сверхбольших блочных моделях. Разбиение исходной полигональной модели с помощью пирамидально-рекурсивного алгоритма, имитирует процесс сокращения крупности блоков и позволяет вычислять спектры распределения блоков каждого уровня по крупности и качеству. В данном исследовании:
- предлагается подход к моделированию карьеров по добыче руд на основе блочных моделей;
- производится приведение структуры блочной модели к структуре «ориентированный граф»;
- разрабатываются методы распараллеливания алгоритмов оптимизации, основанных на нахождении максимальных потоков в ориентированном графе блочной модели месторождения;
- создаётся программный продукт для тестирования имеющихся и оптимизированных методов распараллеливания;
Объект исследования — блочные модели карьеров по добыче руд в системах недропользования.
Предмет исследования — применение алгоритмов оптимизации границ карьеров, применяемых в программном обеспечении открытой разработки рудного сырья.
Данная выпускная квалификационная работа состоит из четырех глав.
В первой главе «Обзор и анализ предметной области» выполняется сбор необходимой информации и анализ современных методов оптимизации границ карьеров по добыче руд и их сопоставление по вычислительной сложности, особенности их применения и использования, возможность распараллеливания алгоритмов оптимизации. Также рассматриваются различные среды программирования и методы паралелльной разработки.
Во второй главе «Разработка теоретических основ оптимизации границ карьеров при помощи алгоритма псевдопотока» производится математическая постановка задачи и приводится описание алгоритма максимизации псевдопотока.
В третьей главе «Разработка программного обеспечения для решения задачи оптимизации границ карьеров» приводятся основные этапы реализации разработанного алгоритма.
Четвертая глава посвящена исследованию эффективности разработанных методов, в ней приводится описание тестовых наборов данных, использовавшихся в ходе тестирования.
Данная выпускная квалификационная работа выполнена на 84 страницах, содержит 16 рисунков, 1 приложение и 40 использованных литературных источников.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!


При выполнении научно-исследовательской работы были выполнены следующие задачи:
1) было сформулировано определение открытого способа разработки месторождения;
2) описан процесс проектирования открытого карьера по добыче сырья;
3) рассмотрена задача определения границ предельного карьера;
4) исследованы различные алгоритмы оптимизации границ
открытого карьера;
5) выбранный алгоритм максимального псевдопотока был
модифицирован для использования с блочными моделями;
6) было разработано и реализовано ПО, вычисляющее контур предельного карьера блочной модели на основе выбранного метода.
7) Произведена оценка эффективности разработанной системы.
Алгоритм нахождения максимального псевдопотока найден наиболее быстрым из представленных, вследствие чего поставленные задачи по проекту заключаются в том, чтобы найти способ каким-либо образом уменьшить время выполнения данного алгоритма для крупных моделей. В качестве основного способа ускорения используется применение параллельного программирования (библиотек PPL в составе среды разработки Embarcadero RAD Studio) и доработка имеющихся алгоритмов с применением данных средств.



1. Lerchs H., Grossman I.F. Optimum design of open pit mines/H. Lerchs // Canadian Mining and Metallurgical Bulletin. 1965. - Vol.58. - № 633. - P. 47 - 56
2. Бобровский А.Н. Qt4.7+. Практическое программирование на C++. - СПб.: БХВ-Петербург, 2012. - 496 с.
3. Гергель В.П. Современные языки и технологии параллельного прогаммирования. - Издательство Московского Университета, 2012. -408 с.
4. Гладков Л.А., Курейчик В.В., Курейчик В.М. - Генетические алгоритмы- 2-е изд., исправл. и доп. - М.: ФИЗМАТЛИТ, 2010. - 310 с.
5. Капутин Ю.Е. Информационные технологии планирования горных работ - СПб., 2004.-334 с.
6. Малышкин В.Э., Корнеев В.Д. Параллельное программирование мультикомпьютеров. Изд-во НГТУ, 2011.
7. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем, БХВ-Петербург, 2002, 400 стр.
8. Рейзлин В.И. Численные методы оптимизации: учебное пособие - Томск: Изд-во Томского политехнического университета, 2011. - 105 с.
9. Рутковская Д., Пилиньский М., Рутковский Л. - Нейронные сети, генетические алгоритмы и нечеткие системы, 452, Горячая Линия - Телеком, 2007.
10. Сандерс Дж., Кэндрот Э. Технология CUDA в примерах: введение в програмирование графических процессоров: Перевод с английского Сликина А.А., научный редактор Боресков А.В. - М.: ДМК Пресс, 2011. -232 с.
11. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации: Учебное пособие. - 2-е издание. - М.:ФИЗМАЛИТ, 2005. - 368 с.
12. Intel® Parallel Studio - инструмент для создания параллельных приложений / [Электронный ресурс] / Режим доступа: https://software.intel.com/ru-ru/articles/intel-parallel-studio-parallelism-toolkit
13. Steps3D - Графика, ООП / [Электронный ресурс] / Режим доступа: http: //steps3d.narod.ru/tutorials/cuda-tutorial .html
14. Википедия — свободная энциклопедия / [Электронный ресурс] / Режим доступа: https://ru.wikipedia.org/wiki/Microsoft_Visual_Studio
15. Википедия — свободная энциклопедия/ [Электронный ресурс] / Режим доступа: https://ru.wikipedia.org/wiki/OpenCL
16. Национальный открытый университет «Интуит» / [Электронный
ресурс] / Режим доступа:
http://www. intuit.ru/studies/courses/3735/977/lecture/14689?page=5
17. Параллельные вычисления CUDA / [Электронный ресурс] / Режим доступа: http://www.nvidia.ru/object/cuda-parallel-computing-ru.html
18. Сибирский суперкомпьютерный центр СО РАН / [Электронный
ресурс] / Режим доступа: http://www2.sscc.ru/SORAN-
INTEL/paper/2012/Open%20ACC.PDF
19. Факультет информационных технологий и прикладной
математики / [Электронный ресурс] / Режим доступа:
http: //knit.bsu. edu.ru/knit/resources/docs. php?ID=000
20. Хабрахабр - интересные публикации / [Электронный ресурс] / Режим доступа: http://habrahabr.ru/post/72650/
21. Minelib 2011: A library of open pit production scheduling problems. Espinoza D, Goycoolea M, Moreno E, Newman A. 206(l), 2013, Ann. Oper. Res., pp. 93-114.
22. Ху T. Целочисленное программирование и потоки в сетях. Москва : Мир, 1974
23. The Pseudoflow Algorithm: A New Algorithm for the Maximum¬Flow Problem. Hochbamn D.S. 56, 2008, Oparations Research, Vol. 4, pp. 992¬1009.
24. Астафьев Ю.П., Зеленский A.C., Горлов Н.И. и др. Компьютеры и системы управления в горном деле за рубежом. М.: Недра, 1989. стр. 264.
25. Система многоуровневых октарных моделей горно¬геологических объектов. Васильев П.В. 2012 г., Материалы XII
Международной конференции Информатика. (XII International Conference "Informatics", 20-22 February 2012) 20-22 February 2012) в 2т, стр. 28-32
26. Петров Д.В. Применение методов глобальной оптимизации для поиска предельных границ рудных месторождений. Научные ведомости БелГУ. Серия Экономика. Информатика, 2015. №7 (204) Выпуск 34/1
27. Михелев B.M., Васильев П.В., Петров Д.В. «Суперкомпьютеры, как средства моделирования граничных контуров карьеров рудных месторождений», Вопросы радиоэлектроники. Серия "Электронная вычислительная техника (ЭВТ)" Выпуск 1, Москва 2013., с. 5-10
28. Muir D.C.W. 2008. Pseudoflow, New Life for Lerchs-Grossmann Pit Optimisation. Spectrum Series, Orebody Modelling and Strategic Mine Planning, 14: 97-104.
29. Ахо А.И., Хопкрофт Д., Ульман Д.Д. 2003. Структуры данных и алгоритмы.: Перв. с англ., М., Издательский дом "Вильямс", 384 (Alfred V. Aho, John E. Hopkroft, Jeffrey D. Ullman 2000. Data Structures and Algorithms, Addison-Wesley publishing company, London: 386)
30. Черепанов, Е.В., Макаров, И.В. Фисенко, А.И. Оценка экономической эффективности вовлечения в разработку площадей с прогнозными ресурсами категории Р1, с применением горно-геологических информационных систем [Электронный ресурс] / Сибирский федеральный университет. - Режим доступа: conf.sfu-kras.ru/sites/mn2010/pdf/4/80.pdf.
31. Валуев, А.М. О моделях и методах оптимизации в задачах проектирования разработки месторождений открытым способом
[Электронный ресурс] / Горный информационно-аналитический бюллетень. - Режим доступа: http://www.giab-online.ru/files/Data/2015/02/29_197-
206_Valuev.pdf.
32. Элкингтон, Т., Дурхэм, Р. Объединение задач определения размера приконтурных блоков и оптимизации производственной мощности карьера [Текст] / Т. Элкингтон, Р. Дурхэм // Физико-технические проблемы разработки полезных ископаемых. - 2011. - № 2. - С. 41-56.
33. Solving ultimate pit limit problem through graph closure (L-G Algorithm) and the fundamental tree algorithm [Электронный ресурс] / SpotiDoc. - Режим доступа: http://www.spotidoc.com/doc/725786
34. Ческидов, В.И., Саканцев, Г.Г., Саканцев, М.Г. Комплексное обоснование границ карьеров и способов вскрытия глубоких горизонтов при разработке крутопадающих пластообразных залежей [Текст] / В.И. Ческидов, Г.Г. Саканцев, М.Г. Саканцев // Известия высших учебных заведений. Горный журнал. - 2015. - № 2. - С. 17-23.
35. Шариф, Д.А. Регулярная проверка конечного контура рабочей зоны карьера на основе алгоритма скользящего конуса [Текст] / Шариф Д.А. // Горный информационно-аналитический бюллетень (научно-технический журнал). - 2007. - № 6. - С. 352-356.
36. Петров Д.В., Михелев В.М. Высокопроизводительные алгоритмы решения задачи поиска предельных границ открытых карьеров [Текст] / Д.В. Петров, В.М. Михелев // В сборнике: Актуальные проблемы вычислительной и прикладной математики труды Международной конференции, посвященной 90-летию со дня рождения академика Г. И. Марчука. - 2015. С. 580-584.
37. Петров Д.В., Михелев В.М. Моделирование карьеров рудных месторождений на высокопроизводительных гибридных вычислительных системах [Текст] / Д.В. Петров, В.М. Михелев // В сборнике: Параллельные вычислительные технологии (ПАВТ'2014) Труды международной научной конференции. Ответственные за выпуск: Л.Б. Соколинский, К.С. Пан. - 2014. С. 299-302.
38. Васильев П.В., Михелев В.М., Петров Д.В. Параллельные алгоритмы оптимизации границ карьеров по методу псевдопотока на модели данных со структурой октодерева [Текст] / П.В. Васильев, В.М. Михелев, Д.В. Петров // Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика. - 2016. том. 38. - № 9 (230). С. 123-128.
39. Петров, Д.В., Дроник, В.И., Михелев, В.М. Реализация алгоритма Лерча-Гроссмана для поиска предельных границ карьеров рудных месторождений [Текст] / Д.В. Петров, В.И. Дроник, В.М. Михелев // Информатика: проблемы, методология, технологиим сборник материалов XVII международной научно-методической конференции: в 5 т. Секция 6. - 2017. - С. 68-72.
40. Петров Д.В., Михелев В.М. Решение задачи оптимизации блочных моделей при проектировании открытых горных работ с использованием гибридных вычислительных систем [Текст] / Д.В. Петров, В.М. Михелев // Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика. том. 35. - № 13-1 (210). - 2015. - С. 93-98.


Работу высылаем на протяжении 30 минут после оплаты.




©2024 Cервис помощи студентам в выполнении работ