Нагруженные графы

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

В качестве примера рассмотрим транспортную задачу (Рисунок 2.1‑4), в которой объекту находящемуся в вершине v1 требуется за минимальное время достичь вершины v6.

Рисунок 2.1‑4. Пример нагруженного графа

Задачу невозможно решить не зная время, за которое объект в состоянии преодолевать каждое из ребер графа. Доопределим исходные данные и зададим в качестве веса время преодоления ребра. На графе назначенные веса приведены рядом с каждым из ребер через символ “/”, так e3/5 означает что ребро e3 преодолевается за 5, предположим, минут. Теперь, после некоторого размышления, перебрав все четыре возможные пути из v1 в v6, можно сказать что кратчайшим (по времени) способом передвижения из v1 в v6 является путь Pmin(v1,v6)={e1,e3,e4,e5}.

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

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

2.1.4 Лепим пельмени – строим граф

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

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

ü в целях упрощения будем считать наши ресурсы (руки, финансы и оборудование) неограниченными,

ü объем проекта (количество результирующих пельменей) фиксирован.

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

ü из каких частей (подпроектов, фаз, работ) состоит проект,

ü какова продолжительность каждой из частей,

ü какие технологические ограничения наложены на последовательность исполнения работ.

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

Выделим отдельные работы, которые необходимо выполнить в рамках проекта (этот процесс называется декомпозицией целей). Итак, для того чтобы “приготовить домашние пельмени ” необходимо:

A. Купить говядину, свинину, муку, соль, перец, масло, молоко, лук, чеснок.

B. Просеять муку.

C. Замесить тесто и дать ему отстояться.

D. Помыть мясо.

E. Почистить лук и чеснок.

F. Пропустить через мясорубку мясо с чесноком, луком.

G. Добавить к фаршу перец, соль и молоко.

H. Вымешать фарш.

I. Нарезать тесто на куски.

J. Раскатать лепешки.

K. Лепить пельмени.

L. Варить.

Отложим до раздела??? вопрос почему именно эти работы выделены (т.е. почему именно так проведена декомпозиция целей) и займемся оценкой длительности работ. Будем теперь использовать для обозначения работ уже сформированный в предыдущем списке индекс работы в виде заглавного латинского символа. Итак: A – 45 (минут), B – 5, C – 45, D – 4, E – 5, F – 10, G – 2, H – 4, I – 10, J – 15, K – 40, L – 12. И здесь оставим на дальнейшее рассмотрение вопросы типа “Почему лепка пельменей занимает 40 минут, хотя количество рабочих рук неограниченно?”.

Приступим теперь к ответу на третий вопрос “Какие технологические ограничения наложены на последовательность исполнения работ?”. И что такое вообще технологические ограничения? Прежде всего это ограничения на последовательность любой пары работ. Например, нельзя начать возводить стены здания не построив фундамент. Можно и посложнее - нельзя начать возводить стены здания прежде чем не пройдет три дня с момента заливки бетона в фундамент (три дня бетон должен “схватываться”). В нашем проекте эти ограничения последовательностей выглядят следующим образом:

ü не выполнив работу A (закупка продуктов) нельзя начать ни одну из остальных работ,

ü работу C (месить тесто) можно начать только после окончании работы B (просеивание муки),

ü работа F (мясорубка) может быть начата только после работ D (мытье мясо) и E (чистка овощей).

ü работу G (добавление специй к фаршу) можно начать только после окончании работы F (мясорубка) и лишь закончив работу G можно начать Н (месить фарш),

ü работы I (разрезка теста) и J (раскатка теста) будем выполнять последовательно и I можно выполнять лишь после того как тесто будет готово (работа С),

ü лепить пельмени (работа K) начнем лишь после того как готов фарш (работа Н) и лепешки раскатаны (J), а варить (работа L) – после того как пельмени слеплены (K).

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

Заметим здесь, что еще не все условия приведены выше. Например, не перечислено вполне логичное условие: “Работа I (разрезка теста) не может быть начата до окончания работы B (просеивание муки)”. Объясняется это обстоятельство тем, что оно является лишним при наличии двух выше сформулированных условий: “ C после B ” и “ I после С ”. Принимая это замечание во внимание, переформулируем теперь первое из выше перечисленных условий предшествования “не выполнив работу A (закупка продуктов) нельзя начать ни одну из остальных работ” как ряд условий: “ B после A ”, “ C после A ”,“ D после A ”, и т.д. и из этого ряда выбросим лишние, оставив только три: “ B после A ”, “ D после A ”, “ E после A ”.

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

Итак, представим модель проекта по приготовлению пельменей в виде графа. Граф есть пара множеств: вершины и ребра. Что же для модели проекта является вершиной и что ребром? Исторически, с методов перечисленных в начале этого раздела, было принято в качестве ребер графа брать работы, а в качестве вершин – события, заключающиеся в начале или окончании одной или нескольких работ (альтернативный подход рассмотрен в следующем подразделе). Попробуем построить такой граф, начав с одной работы A.

Рисунок 2.1‑5. Представление единичной работы на графе проекта.

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

Добавим к вышеприведенному графу работы B, С и D, которые по сформулированным нами ограничениям предшествования могут начаться после окончания работы A. Это даст нам возможность посмотреть как ограничения предшествования находят отражение на графе.

Рисунок 2.1‑6. Отражение зависимостей предшествования на графе проекта.

Переформулируем отношение “работа T2 может начаться только после окончания работы T1 ” в терминах графов. Получим: ребра T2 и T1 смежны, при этом для их общей вершины ребро T1 является входящим, а ребро T2 – исходящим. Отсюда и полученное изображение графа (Рисунок 2.1‑6).

Построим теперь весь граф, отражающий модель проекта изготовления пельменей.

Рисунок 2.1‑7. Полный граф проекта изготовления пельменей.

Оставим на время открытым вопрос о том сколько времени займет изготовление пельменей и перейдем к моделям использующимся в управлении проектом.

Дата добавления: 2015-07-20