I этап. Условная оптимизация

1-й шаг: k = 1. На первом шаге с задаваемым сечением ,  из состояний и  возможен только один вариант перехода вконечное состояние . Поэтому в вершинах и  записываемсоответственно издержки 12 и 9. Ребра  и  обозначаемстрелкой, направленной в вершину - .

2-й шаг: k = 2. Второй шаг оптимизации задается сечением по вершинам . Из состояний  и , возможен единственный переход в вершины , и  соответственно, поэтому в вершинах  и  записываем суммарные издержки 25 и 19 на первых двух шагах перехода в конечное состояние .

Из вершины  возможны два варианта перехода: в вершинy  или вершину . При переходе сумма издержек составляет 12 + 10 = 22, на переходе  сумма составляет 13 + 9 = 22. Из двух вариантов суммарных издержек выбираем наименьшую (22) и обозначаем стрелкой условно оптимальный переход , .

3-й шаг: k = 3. На третьем шаге сечение проходит через вершины , , , . Из вершин  и  возможен единственный переход в вершины  соответственно. Суммарные издержки для состояния равны 19 + 11 = 30, для состояния  равны 25+11=36.  Из вершины  возможны два варианта перехода: в вершину издержки равны 25 + 11 = 36; в вершину  22 + 14 = 36.

Для вершины  возможен переход в вершину  (22 + 15 = 37) и в вершину  (19 + 19 = 38). Выбираем для вершин  и  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

4-й шаг: k = 4. На четвертом  шаге сечение проходит через вершины , , , ,  Из вершин  и  возможен единственный переход в вершины    соответственно. Суммарные издержки для состояния равны 30 + 19 = 49, для состояния  равны 36+9=45.  Из вершины  возможны два варианта перехода: в вершину издержки равны 36 + 12 = 48; в вершину  36 + 15 = 51.

Для вершины  возможен переход в вершину  (36 + 13 = 49) и в вершину  (37 + 18 = 55). Выбираем для вершин  и  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

Для вершины  возможен переход в вершину  (30 + 18 = 48) и в вершину  (37 + 14 = 51). Выбираем для вершины  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

5-й шаг: k = 5. На пятом  шаге сечение проходит через вершины , , , ,  Из вершины  возможен единственный переход в вершину . Суммарные издержки для состояния равны 45 + 8 = 53.  Из вершины  возможны два варианта перехода: в вершину издержки равны 45+13 = 58; в вершину  48 + 14 = 62.

Для вершины  возможен переход в вершину  (48 + 14 = 62) и в вершину  (49 + 21 = 70). Выбираем для вершин  и  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

Для вершины  возможен переход в вершину  (48+ 13 = 61) и в вершину  (49 + 12 = 61). Выбираем для вершины  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

Для вершины  возможен переход в вершину  (49 + 17 = 66) и в вершину  (48 + 16 = 64). Выбираем для вершины  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

6-й шаг: k = 6. На шестом  шаге сечение проходит через вершины , , , ,  Из вершины  возможен единственный переход в вершину . Суммарные издержки для состояния равны 53 + 10 = 63.  Из вершины  возможны два варианта перехода: в вершину издержки равны 53+14 = 67; в вершину  58 + 13 = 71.

Для вершины  возможен переход в вершину  (58 + 12 = 70) и в вершину  (62 + 20 = 82). Выбираем для вершин  и  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

Для вершины  возможен переход в вершину  (61+ 12 = 73) и в вершину  (62 + 11 = 73). Выбираем для вершины  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

Для вершины  возможен переход в вершину  (64 + 16 = 80) и в вершину  (61+ 13 = 74). Выбираем для вершины  наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

7-й шаг: k = 7. На седьмом шаге сечение проходит через вершины , , , . Из вершины   возможен переход в вершину  (63 + 15 = 78) и в вершину  (67 + 12 = 79).

Для вершины  возможен переход в вершину  (67 + 13 = 80) и в вершину  (70 + 19 = 89).

Для вершины  возможен переход в вершину  (70 + 13 = 83) и в вершину  (73 + 12 = 85).

Для вершины  возможен переход в вершину  (73 + 15 = 88) и в вершину  (74 + 14 = 88).

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

8-й шаг: k = 8. На восьмом шаге сечение проходит через вершины , , . Из вершины   возможен переход в вершину  (78 + 11 = 89) и в вершину  (80 + 18 = 98).

Для вершины  возможен переход в вершину  (80 + 10 = 90) и в вершину  (83 + 10 = 93).

Для вершины  возможен переход в вершину  (83 + 12 = 95) и в вершину  (88 + 10 = 98).

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

9-й шаг: k = 9. На девятом шаге сечение проходит через вершины , . Из вершины   возможен переход в вершину  (89 + 10 = 99) и в вершину  (90 + 10 = 100).

Для вершины  возможен переход в вершину  (90 + 10 = 100) и в вершину  (95 + 15 = 110).

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

10-й шаг: k = 10. На девятом шаге сечение проходит через точку . Из вершины  возможен переход в вершину  (99 + 9 = 108) и в вершину  (100 + 13 = 113).

Минимальные возможные суммарные издержки равны 108.

В результате получим граф условно оптимальных переходов, представленный на рис. 2.1.1.

Рис 2.1.1. Сетевая модель связи расходов операций