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

 

Введение 

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

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

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

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

   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). Требуется найти такой маршрут, начинающийся в данном пункте, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы его продолжительность была наименьшей. 
 
 
 
 

     

     

     Решение. Для решения этой задачи необходимо составить математическую модель. введем обозначения: 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).

     Эти зависимости обеспечивают выполнение условия, что из каждого пункта выезда производится только один раз и только в одном направлении.

     Условие въезда в пункт 1 аналогично условию въезда из пункта 1 (Рис.7). Требование минимальной продолжительности маршрута запишется в виде целевой функции:

     min L= t_{11 11}+ t_{12 12}+ t_{13 13}+ t_{14 14}+ t_{15 15}+ t_{21 21}+ t_{22 22}+…+ t_{55 55} ,

где t_ij берутся  из исходной таблица, а _ij  - искомые переменные.

      Тогда всю задачу можно сформулировать:

min L = tij ij,

(*)

     В результате решения системы (*) получим (Рис.8) следующие значения остальные =0;  

     min L = 10+8+10+20+14=62

переходя  от частной к общей постановке, задачу коммивояжера можно сформулировать как:

      min L =  tij ij,

        

     1.3. Транспортная задача

     Транспортная  задача – это задача о выборе плана перевозок однородного  продукта из пунктов производства в пункты потребления. Пусть имеется m продуктов отправления и n пунктов назначения. Запасы продукта в пунктах отправления обозначим через a_i , потребность в продукте в пункте потребления – b_{j .}  Расходы на доставку единицы продукта из i-го пункта отправления в j-й пункт назначения равняются C_ij.

Балансовое  условие производства и потребления  имеет вид 

 

     Требуется определить x_ij – количество продукта, доставляемого от i-го пункта отправления к j-му пункту потребления. При этом обязательными условиями являются: необходимость удовлетворения всех потребителей, оптимальный план доставки продукта должен обеспечить минимум общей суммы затрат на доставку. Экономико-математическая модель задачи:

min L =

      В рассмотренной ЭММ предполагается, что суммарные запасы равны суммарным  потребностям. Такая модель называется закрытой. Если это условие не выполняется, то модель называется открытой. Для  сведенья открытой модели к закрытой вводится или фиктивный пункт отправления, или фиктивный пункт назначения.