ch6SolverMinCostCapacitatedNetwork.xls). Матрица пропускных способностей записана в диапазоне N6:W15.6 Незаполненные ячейки матрицы пропускных способностей показывают, что соответствующие дуги имеют бесконечную пропускную способность. Нулевые значения пропускных способностей вводятся для несуществующих дуг. Матрица удельных стоимостей записана в диапазоне В6:К15. Здесь также нулевые значения вводятся для несуществующих дуг.

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

В диалоговом окне средства Поиск решения целевая ячейки, изменяемые ячейки и ограничения уже заданы. На рис. 6.49 видно, что изменяемые ячейки составляют диапазон В20:В39, а ограничения задаются как F19:F23=G19:G23 (баланс потоков для всех узлов) и В20:В39<=С20:С39 (ограничения пропускных способностей дуг).

Решение N1-N2 = 5, N1-N4 = 35, N2-N3 = 25, N2-N5 = 30, N3-N5 = 25 и N4-N5 = 5, показанное на рис. 6.49, дает общую стоимость потока, равную 490 долл.

УПРАЖНЕНИЯ 6.5.4

1. Решите следующие задачи с помощью средства Поиск решения.

a) Задача из упражнения 6.5.3.3.

b) Задача из упражнения 6.5.3.4.

c) Задача из упражнения 6.5.3.7.

d) Задача из упражнения 6.5.3.8.

На основе сетевых моделей разработано множество методов планирования, составления временных расписаний и управления проектами. Наиболее известные - метод критического пути (Critical Path Method - СРМ), а также система планирования и руководства программами разработок (Program Evaluation and Review Technique - PERT). В этих методах проекты рассматриваются как совокупность некоторых взаимосвязанных процессов (видов деятельности, этапов или фаз выполнения проекта), каждый из которых требует определенных временных и других ресурсов. В методах JCPM и PERT проводится анализ проектов для составления временных графиков распределения фаз проектов. На рис. 6.50 в обобщенной форме показаны основные этапы реализации этих методов. На первом этапе определяются отдельные процессы, составляющие проект, их отношения последовательности (т.е. какой процесс должен предшествовать другому) и длительность. Далее проект представляется в виде сети, показывающей последовательность процессов, составляющих проект. На третьем этапе на основе построенной сети выполняются вычисления, в результате которых составляется временной график реализации проекта.

6.6. МЕТОДЫ СЕТЕВОГО ПЛАНИРОВАНИЯ

Сеть

Временной график

]- п Вычисления

Время

н, I-I

Рис. 6.50. Основные этапы выполнения методов СРМ и PERT

На рис. 6.49 строки от 11 до 15 и столбец К скрыты для экономии места.

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

6.6.1. Построение сети проекта

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

Построение сети проекта основано на следующих правилах.

Правило 1. Каждый процесс в проекте представляется одной и только одной дугой.

Правило 2. Каждый процесс идентифицируется двумя концевыми узлами.

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

Рис. 6.51. Представление двух параллельных процессов с помощью фиктивного процесса

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

1. Какой процесс непосредственно предшествует текущему?

2. Какой процесс должен выполняться после завершения текущего процесса?

3. Какой процесс конкурирует (выполняется параллельно) с текущим?

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

1. Процесс С должен начаться сразу после завершения процессов А и В.

2. Процесс Е должен начаться непосредственно после завершения процесса В.

На рис. 6.52, а показано неправильное представление наших процессов, так как из него следует, что процесс Е должен начаться после завершения как процесса В, так и А. На рис. 6.52, б показано, как с помощью фиктивного процесса D разрешить эту коллизию.

а) б)

Рис. 6.52. Использование фиктивного процесса для правильного отображения последовательного выполнения процессов

Пример 6.6.1

Издатель имеет контракт с автором на издание его книги. Ниже представлена последовательность (упрощенная) процессов, приводящая к реализации проекта издания книги. Необходимо разработать сеть для этого проекта.

Процесс Предшествующий Длительность

процесс (недели)

На рис. 6.53 показана сеть, представляющая взаимосвязь процессов данного проекта. Фиктивный процесс (2, 3) введен для того, чтобы развести конкурирующие процессы А и В. Номера узлов сети возрастают в направлении выполнения проектов.

Рис. 6.53. Сеть проекта для примера 6.6.1