• TORA D:\Work\ToraFII«tch6Tor*CPM[<6 6 3 t*l
Рис. 6.59. Результаты вычислений для задачи из примера 6.6.2
Рис. 6.60. Временной график проекта из примера 6.6.2
УПРАЖНЕНИЯ 6.6.3
1. Дан процесс (i, j) длительностью £>,., самый ранний срок его начала - Ц и самый поздний срок его завершения - Д. Определите самый ранний срок завершения этого процесса и самый поздний срок его начала.
2. Чему равны общий и свободный запасы времени критических процессов?
3. Для следующих процессов определите максимальный сдвиг начала их выполнения (относительно самого раннего срока начала выполнения), который не нарушает никаких отношений следования с другими процессами.
a) TF= 10, FF= 10, D = 4.
b) TF=10,FF=5,D = 4.
c) TF = 10,FF = 0, £> = 4.
4. В задаче из примера 6.6.4 на основе значений запасов времени ответьте на следующие вопросы.
a) Пусть процесс В начался в 1-й день от начала выполнения всего проекта, а процесс С - в 5-й день (см. рис. 6.57). Каков самый ранний срок начала процессов Е и F?
b) Пусть процесс В начался на 3-й день от начала выполнения проекта, а процесс С - на 7-й. Каков самый ранний срок начала процессов Е и F?
c) Может ли процесс В начаться после 6-го дня от начала выполнения проекта?
5. Пусть в проекте из примера 6.6.2 (рис. 6.54) длительность процессов В и F возросла до 20 и 25 дней соответственно.
a) Определите критический путь.
b) Найдите общие и свободные запасы времени для некритических процессов и пометьте при необходимости их "красными флажками".
c) Пусть процесс А начался на 5-й день от начала выполнения всего проекта. Определите по возможности самые ранние сроки начала процессов С, D, Е и Н.
d) Предположим, для выполнения процессов F, G и Н необходимо одно и то же оборудование. Определите минимально необходимое количество этого оборудования.
6. Вычислите запасы времени и расставьте "красные флажки" процессам проектов, показанных на рис. 6.56. Затем постройте временные графики при соблюдении следующих условий.
Проект А
1. Процесс (1, 5) не может начаться раньше 14-го момента времени.
2. Процессы (5, 6) и (5, 7) используют одинаковое оборудование, которое в любой момент времени может использоваться только в одном процессе.
3. Все другие процессы начинаются так рано, как только возможно. Проект Б
1. Процесс (1, 3) должен начаться так рано, как только возможно, с учетом того, что процессы (1, 2), (1, 3) и (1, 6) используют одинаковое оборудование, которое в любой момент времени может использоваться только в одном процессе.
2. Все другие процессы начинаются так рано, как только возможно.
6.6.4. Формализация задачи поиска критического пути как задачи ЛП
Задача определения критического пути в сети проектов, решаемая методом СРМ, противоположна задаче вычисления кратчайшего пути (раздел 6.3) в том смысле, что здесь ищется самый длинный путь от начального узла до конечного. Можно применить формализацию задачи поиска кратчайшего пути из раздела 6.3.3 к задачам нахождения критического пути, решаемых метом СРМ (для краткости будем называть такие задачи задачами СРМ), следующим образом. Предположим, что в сеть в начальном узле поступает одна единица потока, которая покидает сеть в конечном узле. Обозначим
хц - величина потока, проходящего по дуге (£, j), соответствующей процессу (г, j), Dtj - длительность процесса (i, ;). В этих обозначениях целевая функция задачи линейного программирования запишется как
максимизировать г =
но всем процессам
(Сравните с формализацией задачи вычисления кратчайшего пути, где целевая функция минимизируется.) Для каждого узла (проекта) определяется только одно ограничение, задающее баланс потока, проходящего через данный узел:
общий входной поток = общий выходной поток.
Очевидно, что все переменные xtj неотрицательны. Отметим, что одно из ограничений избыточно.
Опять, как и в задачах поиска кратчайшего пути, для решения задачи СРМ можно применить двойственную задачу ЛП. В следующем примере покажем две формализации задачи СРМ.
Пример 6.6.5
Ниже дана формулировка задачи из примера 6.6.2 (см. рис. 6.54) в терминах сетевых моделей линейного программирования. Отметим, что узлы 1 и 6 являются соответственно начальным и конечным узлами.
| | | | | | | Фиктивный | | | |
| | | | | | | | | | |
Максимизировать z | | | | | | | | | | |
Узел 1 | | | | | | | | | | = -1 |
Узел 2 | | | | | | | | | | |
Узел 3 | | | | | | | | | | |
Узел 4 | | | | | | | | | | |
Узел 5 | | | | | | | | | | |
Узел 6 | | | | | | | | | | |
С помощью программы TORA было получено следующее оптимальное решение: 2 = 25, х12(А)= 1, x2i(D) = 1, х45(Фиктивный) = 1, x66(G) = 1, все другие переменные равны 0. Решение определяет следующий критический путь: А -> D -> Фиктивный -» G, при этом длительность проекта равна 25 дней.