Оптимизация сетевого графика методом время - стоимость

Стоимости c(i,j) остальных работ:
с(0,1)=50 с(0,3)=45 с(1,2)=82 c(3,4)=55 с(3,5)=72 с(5,6)=30 с(6,7)=26 с (6,9)=75 с (6,8)=42 с(9,10)=35 с(10,11)= 10
Стоимость первоначального варианта сетевого графика:
C = 694 + 50 + 45 + ... + 35 + 10 = 1216 (д.е.)
С – ΔС = 1216 – 293 = 923 (д.е.)
Уменьшение стоимости:
Стоимость нового плана:

Появились новые критические пути длиной tкр= 61 (всего 28):
0→1→3→4→7→10→11;
0→3→5→8→9→11;
0→1→3→4→6→7→10→11;
0→3→5→6→8→9→11 и т.д.

Построение графика зависимости
стоимости проекта от времени выполнения

L1: 0→1→3→5→6→7→8 20+7+13+25+13+11=89
L2: 0→1→3→4→6→7→8 20+7+26+22+13+11=99
L3: 0→1→2→7→8 20+12+7+11=50
L4: 0→2→7→8 32+7+11=50

1. Сокращаем работу (3,4) на 8 дней
∆С1 = 2∙8 = 16 С1 = С0 + ∆С1 = 300 + 16 = 316
С = 300 + 2∙(99 - t) = 498 - 2 t, 91 ≤ t ≤ 99
(3,4)

С=498-2t

2. Сокращаем работу (4,6) на 2 дня
∆С2 = 4∙2 = 8 С2 = С1 + ∆С2 = 316 + 8 = 324
С = 316 + 4∙(91 - t)= 680 - 4t, 89 ≤ t ≤ 91
(4,6)

С=498-2t
С=680-4t

(6,7)
3. Сокращаем работу (6,7) на 5 дней
∆С3 = 5∙5 = 25 С3 = С2 + ∆С3 = 324 + 25 = 349
С = 324 + 5∙(89 - t)= 769 - 5t, 84 ≤ t ≤ 89

С=498-2t
С=680-4t
С=769-5t

(0,1)
4. Сокращаем работу (0,1) на 10 дней
∆С4 = 6∙10 = 60 С4 = С3 + ∆С4 = 349 + 60 = 409
С = 349 + 10∙(84 - t)= 853 - 6t, 74 ≤ t ≤ 84

С=498-2t
С=680-4t
С=769-5t
С=753-6t

(1,3)
5. Сокращаем работу (1,3) на 5 дней
∆С5 = 8∙5 = 40 С5 = С4 + ∆С5 = 409 + 40 = 449
С = 409 + 8∙(74 - t)= 1001 - 8t, 69 ≤ t ≤ 74

С=498-2t
С=680-4t
С=769-5t
С=853-6t
С=1001-8t

(7,8)
6. Сокращаем работу (7,8) на 5 дней
∆С6 = 9∙5 = 45 С6 = С5 + ∆С6 = 449 + 45 = 494
С = 449 + 9∙(69 - t)= 1070 - 9t, 64 ≤ t ≤ 69

С=498-2t
С=680-4t
С=769-5t
С=853-6t
С=1001-8t
С=1070-9t

(4,6)
(5,6)
7. Сокращаем работы (5,6) и (4,6) на 5 дней
∆С7 = (4 + 4)∙5 = 40
С7 = С6 + ∆С7 = 494 + 40 = 534
С = 494 + (4 + 4) ∙(64 - t)= 1006 - 8t, 59 ≤ t ≤ 64

С=498-2t
С=680-4t
С=769-5t
С=853-6t
С=1001-8t
С=1070-9t
С=1006-8t

(4,6)
(3,5)
8. Сокращаем работы (3,5) и (4,6) на 3 дня
∆С8 = (6 + 4)∙3 = 30
С8 = С7 + ∆С8 = 534 + 30 = 564
С = 534 + (6 + 4) ∙(59 - t)= 1124 - 10t, 56 ≤ t ≤ 59