Методическое пособие для студентов экономических специальностей бнту/ Корзников А. Д., Матвеева Л. Д., Смирнов М. Б мн.: Бнту, 2006. - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
В. В. Примшиц стратегический менеджмент 25 1474.19kb.
Национальная экономика беларуси 1 156.56kb.
Учебно-методическое пособие Математическое моделирование в среде... 1 63.08kb.
Методическое пособие для студентов специальности 1  70 01 01 «Производство... 4 487.32kb.
Учебно-методическое пособие по английскому языку для студентов экономических... 15 1231.7kb.
Методическое пособие по курсу «Картография» для студентов специальностей... 4 405.66kb.
Учебное пособие по дисциплине «Структуры и алгоритмы обработки данных»... 12 1959.7kb.
Макроэкономика 5 941.34kb.
Учебно-методическое пособие для студентов неязыковых специальностей... 14 1613.09kb.
Методическое пособие для студентов заочного отделения технических... 17 1025.07kb.
Учебное пособие для студентов экономических специальностей Красноярск... 24 2429.74kb.
Методические указания и оборазцы выполнения контрольных заданий для... 1 145.26kb.
Направления изучения представлений о справедливости 1 202.17kb.

Методическое пособие для студентов экономических специальностей бнту/ Корзников А. - страница №7/8

Таблица 1





работы

1

2

3

4

5

6

7

8

9

Предшествующие работы

-

-

1

1, 2

1, 2

3, 4

3, 4

6

7, 5


Продолжительность работы

10

15

5

20

15

6

8

10

15


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

Рис. 3.
Предварительно следует упростить полученную сеть. Можно удалить некоторые дуги-связи, а начало и конец удаляемой дуги объединить в одну вер-шину. На рис. 2 изображена сеть, полученная после упрощения сети, изобра-женной на рис. 1.

Рис. 4.


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

После построения сетевого графика все его вершины нумеруются так, что нумерация является правильной.


Алгоритм правильной нумерации.
Шаг 1. Нумеруем начальную вершину номером 1. Переходим к шагу 2.

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

В результате правильной нумерации вершин сетевой график, приведен­ный на рис. 4 примет вид


Рис.5


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

Рассмотрим основные временные параметры сетевого графика. Пусть tijпродолжительность работы, для которой соответствующая дуга (i, j) в сетевом графике имеет в качестве начальной – вершину с номером i , а в качестве конечной – вершину с номером j.

Ранним сроком начала работы (i, j) называется наименьшее допустимое время tijPH , когда может быть начато ее выполнение.

Если работа начата в ранний срок, то время ее окончания tijP0 называется ранним сроком окончания



tij = tij-tij

Ранний срок начала всех работ, для которых вершина i – начальная, называется ранним сроком наступления события i и обозначается TiP.

Ранний срок наступления конечного события называется критическим временем и обозначается Ткр. Таким образом, критическое время – это мини­мальный срок, за который может быть выполнен весь комплекс работ.

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

Поздними сроками начала и окончания работы (i, j) называется наиболь­шее допустимое время начала (tijПН) и окончания (tijПO) этой работы без нарушения сроков выполнения всего комплекса работ. Очевидно:
tijПН = tijПО-tij.
Наиболее поздний из поздних сроков окончания работ, входящих в вершину j, называется поздним сроком наступления события j и обозначается ТjП.

Рассмотрим работу (i, j). Плановая продолжительность этой работы равна tij. Максимально допустимое время, на которое можно увеличить продолжительность работы (i, j) или задержать начало ее выполнения, при котором не изменится время выполнения всего проекта, называется полным резервом Rij времени этой работы. Он равен:


Rij = TjП - TiP – tij.
Резерв времени для работы (i, j), использование которого не изменит ранние сроки наступления всех событий (т.е. все работы смогут начать выполняться в минимально возможные сроки), называется свободным и может быть вычислен по формуле

rij = TjP - TiP – tij.
Очевидно, полный и свободный резерв времени любой работы, лежащей на критическом пути, равен нулю.

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


  1. Полагаем T1P = 0.

  2. Для j = 2, 3, . . . , n вычисляем TjP = (TkP + tkj)

Здесь I(j) – множество всех дуг, входящих в вершину j.

Критическое время Тkp = TnP.


Алгоритм нахождения поздних сроков наступления событий


  1. Полагаем ТnП = Т (как правило Т = Тkp.).

  2. Для i = n-1, n-2, . . . 1, вычисляем

TПi = .

Здесь 0 (i) – множество вершин, которые являются конечным для дуг, выходящих из вершины i.



Рассмотрим сетевой график, описанный в таблице 1. События (вершины) сетевого графика изображены следующим образом:
В верхней четверти записан номер события (вершины) в соответствии с правильной нумерацией. Номер вершины ki , при движении из которой получе­но значение TiP , заносится в нижнюю четверть. В левой четверти записывается ранний срок наступления события TiP, а в правой четверти – его поздний срок наступления TiП .

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

Полагаем T1P = 0, k1 = 0. Рассматриваем вершины в порядке возрастания их номеров.
T2P = T1P + t12 = 0 + 10 = 10, k2 = 1;

T3P = max (T1P + t13; T2P + t23) = max (0 + 15; 10 + 0) = T1P + t13 = 15, k3 = 1;

T4P = max (T2P + t24; T3P + t34) = max (10 + 5; 15 + 20) = T3P + t34 = 35, k4=3;

T5P = max (T3P + t35, T4P + t45) = max (15 + 15; 35 + 8) = T4P + t45 = 43, k5=4;

T6P = T4P+ t46 = 35 + 6 = 41, k6 = 4;

TkP = max (T5P + t57; T6P + t67) = max (43 + 15; 41 + 10) = T5P + t57 = 58, k7=5.
Построим критический путь, начиная с конечной вершины, двигаясь по номерам вершин ki,, стоящих в нижней четверти.

В результате получим 1 – 3 – 4 – 5 – 7. Найдем поздние сроки наступле­ния событий. Полагаем время окончания всего проекта T = T7П = Tkp. = 58. Поставим это значение в правую четверть конечной вершины 7.


T6П = T7П – t67 = 58 – 10 = 48;

T5П = T7П – t57 = 58 – 15 = 43;

П4П = min (T6П – t46; T5П – t45) = min (48 - 6; 43 - 8) = 35;

T3П = min (T5П - t35; T4П - t34) = min (43 - 15; 35 - 20) = 15;

T2П = min (T4П - t24; T3П – t23) = min (35 - 5; 15 - 0) = 15;

T1П = min (TП3 - t13; T2П – t1П ) = (15 – 15; 15 – 10) = 0.
В результате получаем следующую сетевую модель, содержащую под­робную информацию о ранних, поздних сроках наступления событий, крити­ческом времени и критическом пути. Критический путь отмечен двойными линиями.

Рис. 7

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 7. В приведенных ниже таблицах комплекс работ задан их порядковыми номерами, отношением предшествования. Указаны про­должительности работ. Необходимо составить сетевой график выполне­ния работ и посчитать все его числовые характеристики.




№ ра-бот



ва-рианта






1

2

3

4

5

6

7

8

9

10

1

Каким работам предшествует

4,10

10,5

5

8,10

9

8

9

-

-

6

Продолжитель-ности работ

10

2

6

3

12

8

4

1

15

7

2

Каким работам предшествует

4

10,6

5,10

8

10,9

8

9

-

-

4

Продолжитель­ности работ

12

6

1

12

5

7

9

10

4

2

3

Каким работам предшествует

4

10,4,7

5

8

9

8

9

-

-

5

Продолжитель­ности работ

7

11

12

6

2

10

1

8

10

9

4

Каким работам предшествует

4,9,5

9,8

5

8

10

8

10

-

10

-

Продолжитель-ности работ

7

3

10

12

4

5

9

4

8

11

5

Каким работам предшествует

4,9

9

5,9

8

10

8

0

-

6,7

-

Продолжитель-ности работ

10

13

2

8

15

1

6

2

9

7

6

Каким работам предшествует

3,4

5

5

8

9,7

10

6

5

10

-

Продолжитель-ности работ

10

1

15

6

7

4

12

3

10

2

7

Каким работам прешествует

3,4

5

5

8

7,9

10

6

7,9

10

-

Продолжитель-ности работ

10

1

8

2

6

8

12

3

5

3

8

Каким работам предшествует

3,4

5,8

7,9

5,8

6

10

6

7,9

10

-

Продолжитель-ности работ

9

3

4

12

6

5

7

10

7

4

9

Каким работам предшествует

3,4

7

6,8,9

4

7

5

10

10

-

-

Продолжитель-ности работ

9

5

12

8

7

6

6

4

3

8

10

Каким работам предшествует

3

5,7

8,9

10

4,6

8,9

10

10

-

-

Продолжитель-ности работ

5

10

6

7

9

12

10

8

9

7


VIII. ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ
Рассмотрим ориентированный граф G(V, U). Каждой дуге uij U по­ставлено в соответствие неотрицательное число lij , которое мы будем называть длиной дуги uij (если граф содержит неориентированную дугу, мы заменим ее парой противоположно ориентированных дуг, каждой из которых ставим в соответствие одно и то же число lij = lji). Рассмотрим некоторый ориен­тированный (s - t) путь, соединяющий вершину s с вершиной t, и обозначим множество дуг входящих в него через P(s, t).

Длиной пути P(s, t) называется сумма L[ P(s, t) ] = , длин всех дуг, входящих в путь P(s, t).

Теперь может быть сформулирована следующая задача [5, 6]: для выделенных вершин s и t сети G(V, U), среди всех путей их соединяющих, требуется найти путь P*(s, t) = L [P(s, t)], длина которого минимальна Если вершины сети трактовать как, например, города, а пути - как дороги между ними, протяженность которых известна, то задача состоит в на­хождении кратчайшего маршрута между выделенными городами.

Прежде чем описать алгоритм [6] нахождения кратчайших путей из вы­деленной вершины s V сети G(V, U) во все остальные ее вершины, введем следующие обозначения. Для каждой вершины j сети G(V, U), l*( j ) будет обо­значать длину кратчайшего (s - j) пути, а l( j ) - длину некоторого (не обяза­тельно кратчайшего) пути (s - j) пути, а v*(j) – номер предпоследней вершины кратчайшего пути, а v(j) – номер предпоследней вершины рассматриваемого пути. В процессе работы алгоритма, на каждой его итерации очередной верши­не j присваивается постоянная метка вида (l*(j), v*(j)), где v*(j) - номер пред­последней вершины в кратчайшем (s - j) пути. Эта вершина присоединяется к множеству вершин R, имеющих постоянную метку.

Обозначим через arg( l(j)) значение индекса j , при котором достигается минимальное значение величин l( j ), то есть



arg(l( j )) = i = l( i ) = l( j ).
Алгоритм построения кратчайших путей в сети
Начальный шаг. Полагаем l*( s ) : = 0, R : = { s }, l( j ) = lsj, если дуга (s, j) U и l( j ) = в противном случае. Для всех вершин v( j ) = s.

Общая итерация. Шаг 1. Пусть arg(l( j )) = i и вершина i имеет метку ( l(i), k). Если l( k ) = и R V - алгоритм заканчивает работу.

Если l( k ) <  полагаем R : =R {i} и l*( i)= l( i), v*( i )= k .

Если R = V - алгоритм заканчивает работу.

Если R V - переходим к шагу 2.



Шаг 2. Для всех j R, таких, что (k, j) U полагаем

l( j ) : = [l*( i ) + lij, l( j ) ].

Если l( i ) + lij < l( j ), то v( j ) : = i; в противном случае v( j ) не меняет­ся. Переходим к шагу 1 следующей итерации.

Рассмотрим итерацию, на которой алгоритм заканчивает работу. Это происходит на шаге 1, когда либо l( j ) = для всех j R и R V, либо R=V.

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

Во втором случае все вершины получили постоянную метку (l*(i), v*( i )), т.е. найдены кратчайшие расстояния от вершины S ко всем остальным верши­нам сети.

Заметим, что алгоритм явно не указывает кратчайший путь к вершине, а только его длину. Но воспользовавшись второй частью метки: v*( i ) - его легко восстановить. Действительно, v*(i) - номер предпоследней вершины в кратчайшем пути из S в i; пусть v*( i ) = i1.

Но v*( i1 ) = i2 - номер предпоследней вершины в кратчайшем пути из S в i1. Продолжая, мы найдем последовательность вершин S, ik , ik-1, ..., i2, i1, k, через которые проходит кратчайший путь.

Рассмотрим работу алгоритма на следующем примере.

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

Рис.7
На начальном плане вершина S получает постоянную метку (0*, S*),



R = {S}, соседние с ней вершины 1, 2, 3 получают временные метки (1, S), (10, S) и (6, S) соответственно, а остальные вершины получают временные метки (, S) (рис.8 ).

Рис. 8

Итерация 1.

1) Минимальное значение первой части меток всех вершин равно 1 для первой вершины, т.е. arg() = 1. Метка первой вершины становится постоянной. Полагаем R:= R{1} = {S, 1}, переходим к шагу 2.

2) Просматриваем все вершины, соседние с вершиной, получившей по­стоянную метку (вершиной 1).

Для вершины 5 имеем l*(1) + l15 =1 + 2 = 3 < l(5) = , поэтому полагаем l(5) = 3, V(5) = 1.



Для вершины 2 имеем min(l*(1) + l12 , l*(S) + l32 = min (1 + , 10) = 10. Так как l(2) = 10, то метка вершины 2 не меняется. Переходим ко второй итерации и т.д.

Заметим, что на каждой итерации алгоритма одна очередная вершина i присоединяется к множеству R и получает постоянную метку (l*( i ), v*( i ) ), которая в дальнейшем не меняется, а для остальных вершин j R пересмат­риваются текущие значения величин l ( j), некоторые из которых могут ме­няться и в дальнейшем. Результаты вычислений на начальном шаге (итерация 0) и на всех последующих итерациях удобно заносить в таблицу 2.1. Если пара чисел (l (i ), v( i )) помечается символом ( * ), это означает, что вершина i получила постоянную метку (l*( i ), v*( i )), которая в дальнейшем не меняется.


Таблица 2.1

Вершина
итерация

0

1

2

3

4

5

6

7

s

1

2

3

4

5

6

7

t

0*, s*

s

10, s

7, s

, s

, s

, s

, s

, s




1*, s*

10, s

7, s

, s



3, 1

, s

, s

, s





10, s

7, s

4, 5

3*, 1*

, s



11, 5

13, 5



10, s

6, 4

4*, 5*
, s

8, 4

13, 5



7, 3

6*, 4*

, s



8, 4

13, 5



7*, 3*

, s



8, 4

13, 5

, s



8*, 4*

13, 5

, s


13*, 5*

Алгоритм закончил работу на 7-й итерации случаем, когда R = s, 1, 2, 3, 4, 5, 7, t , 6  R и R V, а l(6) = . Это означает, что не существует пути, ведущего из вершины s в вершину 6. Для всех остальных вершин сети длины кратчайших путей найдены, а сами пути могут быть построены, как описано выше. Например, для вершины 2 имеем: ( l*(2), v*(2) ) = (7*, 3*); предыдущая вершина кратчайшего пути - 3. Для вершины 3 (l*(3), v*(3) ) = (6*, 4*); для вершины 4 - ((l*(4), v*(4) ) = (4*, 5*);для вершины 5 - ( (l*(5), v*(5) ) = (3*, 1*); а для вершины 1 - ( (l*(1), v*(1) ) = (1*, s*). Таким образом, кратчайший (s - 2) путь проходит через вершины s, 1, 5, 4, 3, 2 и его длина равна 7.

Все дуги сети, входящие в кратчайшие пути, изображены на рис.9. Пары чисел около вершин (рис.8, 9) - это найденные в результате работы алгоритма постоянные метки вершин, первая часть которых l*(i) - длина кратчайшего (s - i) пути P*(s, i), а вторая - предпоследняя вершина этого пути (последней является вершина i ).

Кратчайшие пути образуют дерево, но не остовное, так как вершина 6 не соединена ни с одной другой вершиной.



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

<< предыдущая страница   следующая страница >>



Работа не волк. Зато начальник — зверь. Виктор Коняхин
ещё >>