Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 20

хi

     шаг   итерации  pi=i

1

2

3

4

5

6

х0

0

0

0

0

0

0

х1

+0

+0

+0

-3

-

-

х2

+0;+3

+0;+3

+0

+0

+0

-

х3

+0;+1

+0;+1

+0;+1

+0

-

-

хk

+1;+2;+3

+1;+2

+1;+2

+1;+2

+2

-

При увеличении потока на единицу по данному маршруту оказалась насыщенной дуга (х3k). В результате расстановки меток на втором шаге итерации возможны маршруты: n0k={(хk, х1, х0); (хk, х2, х0); (хk, х2, х3, х0); (хk, х2, х3, х1, х0)}, из множества которых выбран маршрут n0k=(хk, х2, х3, х1, х0). При увеличении потока на единицу по данному маршруту оказалась насыщенной дуга (х32). В результате расстановки меток на третьем шаге итерации возможны маршруты: n0k={(хk, х1, х0); (хk, х2, х0)}, из которых выбрали маршрут nok=(хk, х1, х0). При увеличении потока по этому маршруту оказалась насыщенной дуга (х01). Следует отметить, что на этом шаге итерации не использовали метку у вершины х3. В результате расстановки меток на четвертом этапе вершина х3 помечена +0, а вершина х1 не может быть помечена “+0”, т.к. дуга (х01) -насыщена. Табл. а) показывает возможность для вершины х1 поставить метку -3, что приведет к перераспределению потоков в дугах графа, но общему увеличению. Итак, на четвертом шаге итерации имеем возможные маршруты: n0k={(хk, х1, -х3, х0); (хk, х2, х0)}, из которых выбран маршрут  n0k=(хk, х1, -х3, х0).                                                                                                     табл. b).

i, хj)

  Сij

    шаг итерации pi=i

1

2

3

4

5

6

0, х1)

2

0

0

1

2

2

2

0, х2)

1

0

0

0

0

0

1

0, х3)

3

1

2

2

2

3

3

1, х3)

4

0

0

1

0

0

1, хk)

3

0

0

0

1

2

2

2, хk)

2

0

0

1

1

2

3, х2)

1

0

0

1

1

1

1

3, хk)

2

1

2

2

2

2

2

При перераспределении потоков (уменьшение потока в дуге (х13), насыщении дуги (х03)) удалось увеличить поток еще на одну единицу. При расстановке меток на пятом шаге итерации многообразие маршрутов сведено к одному - n0k=(хk10). На шестом шаге итерации невозможно поставить метку у вершины хk, дуги (х01), (х02), (х03), (х2k), (х32), (х3k) - насыщены. Следовательно, нельзя проложить маршрут n0k.

3.4.5 Поиск критического пути в управлении проектами

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

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

Для управления проектом разработан метод сетевого планирования и управления (СПУ), в основу которого положен метод критического пути (МКП).

Этот метод позволяет:

1) планировать работы проекта и предвидеть возможные задержки в исполнении каждой работы и проекта в целом;