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

АННОТАЦИЯ

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

ABSTRACT

When organizing the work of excavators and trucks, graph theory was used. Dijkstreet's algorithm was used to determine the minimum distance between them. Having determined the adjacency matrix and the weighted graph, we have obtained a weighted function with which we can determine the distance and fuel consumption, which means that ore mining will be optimized

Ключевые слова: Граф, алгоритм Дейкстрита, матрица смежности

Keywords: Graph, Dijkstra's Algorithm, adjacency Matrix

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

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

Раскраска графов и применение

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

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

Только в 1879 году данная задача была опубликована в первом томе «Трудов Королевского географического общества» известным английским математиком Артуром Кэли. Так она получила широкую известность.

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

В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».

Рисунок 1. Основные понятия теории графов

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

Рисунок 2. Пути и циклы в графе

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

Предположим, что A,B,C и J это есть экскаваторы и пункты назначения (например, обогатительные фабрики).

Таким образом, граф определяется как множество вершин V, связанных между собой множеством ребер Еи обозначается как G= (V, Е). Если V= {A,B,C ... J} — множество вершин и Е= {е₁, е₂. e₃.., е_n} — множество ребер.

Чтобы найти минимум расстояние от точки A до точки F, будем использовать алгоритмом Дейкстрита.

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

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

Рисунок 3. Значения параметров

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

Список литературы:

1. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика [Электронный ресурс ] - М.: ФИМА, МЦНМО, 2006. Vilenkin1969ru.pdf (ysn.ru)
2. Мельников О.И. Теория графов в занимательных задачах./ [Электронный ресурс ] Изд.3, испр. и доп. 2009 https://moodle.znu.edu.ua/pluginfile.php?file=/206369/mod_resource/content/1/Zanimatielnyie zadachi po tieorii ghrafov - Mielnikov O.I_.pdf
3. Фляйшнер Г. Эйлеровы графы и смежные вопросы. / [Электронный ресурс ] Пер. с англ. - М.:Мир, 2002
4. Фляйшнер Г. Эйлеровы графы и смежные вопросы (studmed.ru)