Оптимизация сетевого графика

Задача коммивояжера

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

Транспортных объектах.

Методы и модели теории графов и сетевого моделирования на

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

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

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

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

Каждую вершину сети нумеруют порядковым номером. Начальную 1 вершину в описании движения потоков называют источником, конечную – стоком. В общем случае дугу обозначают i-j, где i – номер вершины, из которой исходит дуга; j – номер вершины, в которую входит дуга. Каждая дуга имеет свою характеристику: t_ij – продолжительность движения по дуге i-j; c_ij – стоимость перемещения; d_ij – пропускная способность дуги и т.д.

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

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

Рисунок 1.

Таблица 1.

Из пункта i	В пункт j

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

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

1, если из пункта i торговец переедет в пункт j

= 0, если не поедет.

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

, или ,

или для произвольного i-ого пункта

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

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

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

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

,

,

, (*)

= [0;1] .

В результате решения системы (*) получим (рис.2) следующие значения , остальные ; min L = 10+8+10+20+14=62.

Рисунок 2.

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

,

,

, (*)

= [0;1] .

Система методов сетевого планирования и управления (СПУ) - система методов планирования и управления разработкой больших народнохозяйственных комплексов, научными исследованиями, конструкторской и технологической подготовкой производства, новых видов изделий, строительством и реконструкцией, капитальным ремонтом основных фондов путем применения сетевых графиков.

Первые методы СПУ: метод оценки и проверки планов (PERT) и метод критического пути (CPM) были разработаны в 1950-х гг. для управления сложными проектами. CPM появился в 1957 г. для организации строительства и ремонта химических заводов Дюпона. PERT разрабатывался независимо для нужд военно-морского флота и появился в 1958 г. В дальнейшем сетевые методы стали широко применяться и во всех отраслях экономики.

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

Система СПУ позволяет:

· формировать календарный план реализации некоторого комплекса работ;

· выявлять и мобилизовать резервы времени, трудовых, материальных и финансовых ресурсов;

· осуществлять управление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ;

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

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

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

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

Сетевая модель и ее основные элементы

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

Главными элементами сетевой модели являются события и работы.

Термин «работа» используется в СПУ в широком смысле. Во-первых, это действительная работа - протяженный во времени процесс, который требует затрат ресурсов (например, сборка изделия, испытание прибора и т.п.). Каждая действительная работа должна быть конкретной, четко описанной и иметь ответственного исполнителя.

Во-вторых, это ожидание - протяженный во времени процесс, который не требует затрат труда (например, процесс высыхания после окрашивания, старение металла, твердение бетона).

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

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

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

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

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

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

Продолжительность пути - сумма продолжительности работ, которые этот путь составляют.

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

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

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

Основные временные параметры сетевых графиков представлены в табл.2.