Звариант. Зависимость (2,3) не выполняется, а зависимость (6,3) выполняется. Это дает следующее значение 13=12+12+18=42. 4 вариант. Зависимость (6,3) не выполняется, а зависимость (2,3) выполняется. Тогда Тз=12+27+16=55. Новый индекс вершины 3 А ,, = тт(40,39,42,55)=39. Индекс вершины 4 определяется из условия, что в нее входит всего одна дуга. Поэтому Х4= тт(12+13,12 +39) 25. Рассматриваем вершину 5. В эту вершину входит три дуги: (2, 5), (4, 5), (6, 5). Это приводит к необходимости рассматривать восемь возможных вариантов выполнения рекомендательных зависимостей. 1 вариант. Все зависимости не выполняются. Тогда В=17+17+15+14=63. 2 вариант. Все зависимости выполняются. В этом случае 15=17+тах(27,25, 18)=44. 3 вариант. Зависимость (2,5) выполняется, а остальные нет. Тогда В= 17+27+15+14=73. 4 вариант. Зависимость (4,5) выполняется, а остальные нет. Тогда В=17+17+25+14=73. 5 вариант. Зависимость (6,5) выполняется, а остальные нет. В этом случае имеем: 15=17+17+15+18=67. 6 вариант. Зависимости (2,5) и (4,5) выполняются, а остальные нет. Тогда 15=17+тах(27, 25)+14=58. 7 вариан т. Зависимости (2,5) и (6,5) выполняются, а остальные нет. В этом случае получим: 15=17+шах(27,18)+15=59. 8 вариант. Зависимости (4,5) и (6,5) выполняются, а остальные нет. Это дает: 15=17+тах(25, 18)+17=59. В итоге новый индекс вершины 5 будет определяться соотношением: ?,5= тт(бЗ,44,73,73,67,58,59,59) = 44. Аналогично находим индексы вершин 6 и 7. Х6 =18 Я,, = т т ( 1 5 + 27,15+ 27+ 14,15+ 13+ 18,15+ 13+ 14)= 42,. 101 |
2 вариант. Все зависимости выполняются. В этом случае получаем t3=12+max(27,18)=39. 3 вариант. Зависимость (2,3) не выполняется, а зависимость (6,3) выполняется. Это дает следующее значение t3=12+12+18=42. 4 вариант. Зависимость (6,3) не выполняется, а зависимость (2,3) выполняется. Тогда t3=12+27+16=55. Новый индекс вершины 3 Х3=min(40,39,42,55)=39. Индекс вершины 4 определяется из условия, что в нее входит всего одна дуга. Поэтому ?ч =min(l2+13,12+39)=25. Рассматриваем вершину 5. В эту вершину входит три дуги: (2, 5), (4, 5), (6, 5). Это приводит к необходимости рассматривать восемь возможных вариантов выполнения рекомендательных зависимостей. 1 вариант. Все зависимости не выполняются. Тогда t5=l 7+17+15+14=63. 2 вариант. Все зависимости выполняются. В этом случае tj=17+max(27, 2 5 ,18)=44. 3 вариант. Зависимость (2,5) выполняется, а остальные нет. Тогда t5= 17+27+15+14=73. 4 вариант. Зависимость (4,5) выполняется, а остальные нет. Тогда t3= 17+17+25+14=73. 5 вариант. Зависимость (6,5) выполняется, а остальные нет. В этом случае имеем: t5=17+17+15+18=67. 6 вариант. Зависимости (2,5) и (4,5) выполняются, а остальные нет. Тогда ts=17+max(27,25)+14=58. 7 вариант. Зависимости (2,5) и (6,5) выполняются, а остальные нет. В этом случае получим: t5=17+max(27,18)+15=59. 8 вариант. Зависимости (4,5) и (6,5) выполняются, а остальные нет. Это дает: t5=17+max(25, 18)+17=59. В итоге новый индекс вершины 5 будет определяться соотношением: Xs = min(63,44,73,73,67,58,59,59) = 44. Аналогично находим индексы вершин 6 и 7. *.6 =18 Х7 = min(l5 + 27,15 + 27 +14,15 +13 +18,15 +13 +14)= 42,. Производим корректировку индексов вершин сетевого графика в том же порядке, то есть делаем третий шаг. Третий шаг. Рассматриваем вершину 1.Новый индекс вершины Я., =11. В вершину 2 входит только одна работа. Поэтому индекс вершины определяется из соотношения Х2 = ш т (т , + а 12,т2+ Я .,)= тт(16 + 12,16 + 11) = 27 . Таким образом, индекс вершины не изменился. Определим индекс вершины 3. В эту вершину входит две дуги: (2,3) и (6,3). Это дает четыре возможных варианта 1 вариант. Все зависимости не выполняются. Тогда t3=12+12+16=40. 2 вариант. Все зависимости выполняются. В этом случае получаем t3=12+max(27, 18)=39. Звариант. Зависимость (2,3) не выполняется, а зависимость (6,3) выполняется. Это дает следующее значение t3= 12+12+18=42. 4 вариант. Зависимость (6,3) не выполняется, а зависимость (2,3) выполняется. Тогда t3= 12+27+16=55. Новый индекс вершины 3 Х3=min(40,39,42,55) =39. Индекс вершины 4 определяется из условия, что в нее входит всего одна дуга. Поэтому Х4 =min(l2 +13,12+39)=25. Рассматриваем вершину 5. В эту вершину входит три дуги: (2, 5), (4, 5), (6, 5). Это приводит к необходимости рассматривать восемь возможных вариантов выполнения рекомендательных зависимостей. 1 вариант. Все зависимости не выполняются. Тогда t5=17+17+15+14=63. 2 вариант. Все зависимости выполняются. В этом случае t5=17+max(27, 25, 18)=44. 3 вариант. Зависимость (2,5) выполняется, а остальные нет. Тогда ts= 17+27+15+14=73. 4 вариант. Зависимость (4,5) выполняется, а остальные нет. Тогда t5= 17+17+25-1-14=73. 5 вариант. Зависимость (6,5) выполняется, а остальные нет. В этом случае имеем: t3=17+17+l5+18=67. 6 вариант. Зависимости (2,5) и (4,5) выполняются, а остальные нет. Тогда t5=17+max(27,25)+14=58. 7 вариант. Зависимости (2,5) и (6,5) выполняются, а остальные нет. В этом случае получим: t5=l 7+max(27,18)+I5=59. 8 вариант. Зависимости (4,5) и (6,5) выполняются, а остальные нет. Это дает: t5=17+max(25, 18)+17=59. В итоге новый индекс вершины 5 будет определяться соотношением: Х5 = min(63,44,73,73,67,58,59,59)= 44. Аналогично находим индексы вершин 6 и 7. \ =18 Х7 = min(l5 + 27,15+ 27+ 14,15+ 13+ 18,15+ 13+ 14)= 42. Таким образом, индексы вершин, рассматриваемого сетевого графика не изменились, что свидетельствует о том, что итерационная процедура решения завершена. Убирая зависимости, которые нарушаются, получим сетевой график, представленный на рис. 7.1.2. |