Теория графов 3

Введение

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

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

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

Сформулированная цель предопределила следующую совокупность решаемых задач:

1. исследовать эффективность стандартных алгоритмов решения задач оптимизации;

2. разработать и реализовать алгоритмы, позволяющие автоматизировать решение задач оптимизации;

3. реализовать разработанную процедуру в виде программного продукта, соответствующего современным требованиям;

4. провести исследование эффективности разработанной процедуры на представительном множестве тестовых задач;

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

6. провести апробацию разработанного подхода на реальных практических задачах.

Объект исследования - графовые методы в теории информации.

Предмет исследования - модели структур и сложность решения задач оптимизации.

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

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

Научная новизна и теоретическая значимость исследования состоит в том, что в нем:

1. выявлены структурные элементы решения задачи;

2. выявлены отношения, связывающие эти структурные элементы;

3. построены семантические графы первого порядка сложности, моделирующие эти отношения;

4. дана количественная характеристика сложности решения задач;

5. выявлены и систематизированы структуры решений задач оптимизации по числовой характеристике - сложности решения;

6. разработана технология организации работы с программными средствами при решении задач с применением графовых моделей.

1. Элементы теории графов

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

Граф-совокупность вершин и ребер универсальное средство наглядного представления достаточно разнообразных задач (рис.1).

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

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

Каждую вершину сети нумеруют порядковым номером. Начальную 1 вершину в описании движения потоков называют источником, конечную – стоком.

Дугу (Рис.5) обозначают двойной индексацией 1-2; 3-4; и т.д. в общем случае дугу обозначают i-j, где i-номер вершины, из которой исходит дуга. Каждая дуга имеет свою характеристику: t_ij -продолжительность движения по

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать