Теория графов 3 (стр. 1 из 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-продолжительность движения по дуге i-j; c_ij – стоимость перемещения; d_ij – пропускная способность дуги и т.д.

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

1.2. Задача коммивояжёра

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

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

Пример. Пусть имеются 5 пунктов, соединенных между собой дорогами так, что из любого пункта можно проехать в любой другой пункт (Рис.6).Известно время перевозки из пункта i в пункт j (табл.1). Требуется найти такой маршрут, начинающийся в данном пункте, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы его продолжительность была наименьшей.

Из пункта j	В пункт j
	1	2	3	4	5
1	0	10	25	25	10
2	1	0	10	15	2
3	8	9	0	20	10
4	14	10	24	0	15
5	10	8	25	27	0

Решение. Для решения этой задачи необходимо составить математическую модель. введем обозначения: i и j – номера пунктов выезда и въезда; t_ij – время переезда из пункта i в пункт j из таблицы 1 видно, что t_ij в общем случае может бы не равно времени переезда в обратном направлении t_ij

t_ji (например, когда один пункт на вершине горы, а другой – у ее подножия). Введем булевы переменные:

Составим модель (Рис.7). Из пункта 1 можно выехать в любой из пункта 2 или 5, или 3, или 4, или остаться в пункте 1. но при этом можно выехать только в одном единственном направлении. Это условие можно записать так:

₁₁+₁₂+₁₃+₁₄+₁₅ =1, или _1j=1, или для производительного i-го пункта _ij=1(i=1,…,5).