<<
>>

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

Наглядность геометрии широко используют при анализе больших технических и организационных систем.

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

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

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

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

Рис. 8.8. Двойная индексация дуги сети

Дугу сети обозначают двойной индексацией 1-2; 3-4 (рис. 8.8) и т. д. (по номерам вершин, на которые дуга опирается). В общем случае дугу обозначают «г-/», где { — номер вершины, из которой исходит дуга; / — номер вершины, в которую входит дуга. Каждая дуга имеет свои характеристики (рис. 8.9); ^ — продолжительность движения по дуге г-/; с/ — стоимость перемещения; di? — пропускная способность дуги и т. д.

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

0 с“'КТ)

Рис. 8.9. Характеристики дуги сети

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

Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает последовательность работ и продолжительность выполнения каждой работы (табл. 8.13).

Таблица 8.13

Исходные данные для составления сетевого графика Работа Содержание Следует после работ Продолжи

тельность Обозначение а1 Закупка и доставка оборудования - 1 1-2 а2 Разработка технологии - 2 1-3 а3 Монтаж и наладка оборудования а1 4 2-3 а4 Обучение рабочих-операторов а1 3 2-4 а5 Пуск линии в эксплуатацию а2, а4 6 3-4 Два события отметим особо: начальное — состояние, с которого начинается весь комплекс работ; конечное — состояние, которым завершается комплекс работ.

По исходным данным строится сетевой график (рис.

8.10).

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

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

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

Перейдем к формализации. В нашем примере время наступления каждого события может быть найдено по зависимостям

Т = 0; Т2 = Т, + ?12 = 0 + 1 = 1.

Рис. 8.10. Сетевой график

Так как третье событие может наступить после выполнения работ 2-3 и 1-3, запишем:

значит, Т3 = 5.

Аналогично найдем время наступления последнего события:

значит, Т4 = 11.

Окончательно время наступления событий будет равно:

Т1 = 0; Т2 = 1; Т3 = 5; Т4 = 11.

Резерв работы 1-3 будем обозначать А13 = 5 - 2 = 3. Значит, работа 1-3 может быть начата не в начальный момент времени, а спустя 3 ед. времени или продолжаться на 3 ед. больше, чем первоначально предполагалось, т. е. может длиться 2

+ 3 = 5 ед. без увеличения момента наступления конечного события 4 (рис. 8.11).

Рис. 8.11. Временной резерв работы 1-3

4 ) Г4 = 11

г, = о

Аналогично Д24 = Т4 - (Т2 + ?24) = 11 - (1 + 3) = 7, т. е. продолжительность работы 2 - 4 может быть увеличена на 7 ед. Очевидно, что для работ критического пути резерв времени равен 0, т. е. Д12 = Д23 = Д34 = 0.

Для третьего события можно записать Т3 = Т1 + ?13 + Д13.

Отсюда (Т3 - Т4) - Д13 = ?13. Выражение (Т3 - Т4) записано в скобках, чтобы было наглядно видно, что это интервал времени между двумя последовательными событиями.

И этот интервал за вычетом резерва Д13 равен продолжительности работы 1-3. В этой зависимости нам задана продолжительность работы ?13 = 2 (правая часть уравнения), остальные величины — искомые переменные. Если их обозначить

то можно записать

и получить линейное уравнение с тремя неизвестными.

Если записать аналогичные зависимости для всех событий и работ, входящих в нашу сеть, то получим систему:

(T2 - T1) -Л12 = ?12; (73 - T1) -Л13 = ?13; <

(T3 - T2)-Л 23 = ?23; (T4 - T2) -Л24 = ?24;

(T4 - T3) — Л34 = ?34.

Эта система описывает топологию (структуру) нашей сети.

Если вместо ^ подставить их известные (заданные) значения, получим:

(T2 - T1) -Л12 = 1; (T3 - T1) - Л13 = 2; <

(T3 - T2) -Л23 = 4; (T4 - T2) -Л24 = 3;

(T4 - T3) -Л34 = 6.

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

При этом возможны две постановки задач оптимизации.

Первая постановка: задаемся временем начала работ, т. е. значением Т1, например Т1 = 0, и стремимся закончить комплекс работ как можно раньше:

L = T4 ^ min; 71 = 0.

Вторая постановка: задан срок завершения всех работ, например Т4 = 15, и мы заинтересованы в как можно более позднем начале работы, но с соблюдением намеченного срока:

|L2 = T1 ^ max; [T4 = 15.

В общем виде топология сети запишется:

(*)

(Tj - T) - д.. = tj(для всех i, j).

Если обозначить 5 — число событий, Я — число работ, то, как видно из (*), система, описывающая сеть, будет включать п переменных, где п = 5 + Я, так как каждому г-му событию соответствует неизвестная Т, а каждой г, ]-й работе — неизвестная Л^.. А число ограничений т = Я, т. е. каждой работе соответствует ограничение.

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

Тогда общие постановки запишутся:

где Т , Тп пл — заданные плановые сроки начала и окончания работ сети. Например, для графика из 11 событий и 20 работ (рис. 8.12) первая постановка при Т1 = 0 будет иметь вид:

Li = Тц —— ^rin;

<(Tj - Т)-Aj- = tj (i = 1... 10; j = 2... 11);

T1 = 0.

T2 = 2

Рис. 8.12. График 11 событий и 20 работ

<< | >>
Источник: Глухов В. В.. Менеджмент: Учебник для вузов. 3-е изд. — СПб.: Питер. — 608 с.. 2008

Еще по теме 8.12. Теория графов:

  1. 37. КАК ФЛОРЕНТИЙЦЫ ПОТЕРПЕЛИ ПОРАЖЕНИЕ ОТ ГРАФОВ ГВИДИ ПРИ МОНТЕДИКРОЧЕ
  2. Вопрос 44 ЧТО ТАКОЕ «ТЕОРИЯ X» И «ТЕОРИЯ У» Д. МАК-ГРЕГОРА?
  3. СИСТЕМНАЯ ТЕОРИЯ И ТЕОРИЯ РАЦИОНАЛЬНОГО ВЫБОРА
  4. 6.6. Теория ожиданий и теория справедливости
  5. ЧАСТЬ II ОБЩАЯ ТЕОРИЯ ГОСУДАРСТВА И ПРАВА Раздел III ТЕОРИЯ ГОСУДАРСТВА
  6. Глава IX Искусство как катарсис Теория эмоций и фантазии. Принципы экономии сил. Теория эмоционального тона и вчувствования. Закон "двойного выражения эмоций" и закон «реальности эмоции». Центральный и периферический разряд эмоций. Аффективное противоречие и начало антитезы. Катарсис. Уничтожение содержания формой.
  7. 6. Теория обмена
  8. Количественная теория денег
  9. ТЕОРИЯ И ЭКСПЕРИМЕНТ
  10. Теория души
  11. 2.2. «Школа», «теория», «парадигма», «ориентация»
  12. Теория занятости
  13. Теория справедливого обогащения
  14. Врум и теория ожиданий
  15. Теория полных издержек