Задача о максимальном потоке

(с₁₄,с₄₁)=(70-30,130+30)=(40,160)

(с₄₇,с₇₄)=(30-30,0+30)=(0,30)

(с₇₉,с₉₇)=(60-30,0+30)=(30,30) 

 Итерация 5:

1

2

3

4

5

6

7

8

9

20

20

40

30

5

40

5

90

0

30

0

20

100

0

30

0

0

0

160

0

100

0

10

0

30

0

0

20

100

10

 1

0

0

0

100

0

0

0

0

0

0

0

100

0

100

0

0

20

60

10

100

40

30

40

0

90

5

40

5

30

100

20

20

9

8

7

6

5

4

3

0

20

30

        Рисунок 6

1. Назначаем а₁=∞, и помечаем узел 1 меткой [∞,−]. Полагаем i=1.
2. S₁={2,3,4} ≠{Ø}
3. k=4, c₁₂=max{c₁₂,c₁₃,c₁₄}=max{20,20,40}=40. Назначаем а₄=c₁₄=40  и помечаем узел 4 меткой [40,1]. Полагаем i=4 и возвращаемся к     шагу 2.
4. S₂={6,8} ≠{Ø}
5. k=6, c₄₇=max{c_46, c₄₈}=max{30,20}=30. Назначаем а₆=c₄₆=30  и помечаем узел 6 меткой [30,4]. Полагаем i=6 и возвращаемся к        шагу 2.
6. S₃={Ø} => откат к узлу 4
7. S₄={8} ≠{Ø}
8. k=8, c₄₇=max{c₄₈}=max{20}=20. Назначаем а₈=c₄₈=20  и помечаем узел 8 меткой [20,4]. Полагаем i=8 и возвращаемся к шагу 2.
9. S₅={Ø} => откат к узлу 1
10. S₆={2,3} ≠{Ø}
11. k=2, c₁₂=max{c₁₂,c₁₃}=max{20,20}=20. Назначаем а₂=c₁₂=20  и помечаем узел 2 меткой [20,1]. Полагаем i=4 и возвращаемся к        шагу 2.
12. S₇={5,6,8} ≠{Ø}
13. k=8, c₂₈=max{c₂₅,c_26, c₂₈}=max{30,5,40}=40. Назначаем а₈=c₂₈=40 и помечаем узел 8 меткой [40,2]. Полагаем i=8 и возвращаемся к        шагу 2.
14. S₈={Ø} => откат к узлу 2
15. S₉={5,6} ≠{Ø}
16. k=5, c₂₅=max{c₂₅,c₂₆}=max{30,5}=30. Назначаем а₅=c₂₅=30  и помечаем узел 5 меткой [30,2]. Полагаем i=5 и возвращаемся к     шагу 2.
17. S₁₀={9} ≠{Ø}
18. k=9, c₅₉=max{c₅₉}=max{100}=100. Назначаем а₅=c₅₉=100  и помечаем узел 9 меткой [100,5]. Полагаем i=9 и переходим к шагу 19.
19. N₁={а₁,а₂,а_5, а₉} f₁ = min{∞, 20, 30, 100} = 20

(с₁₂,с₂₁)=(20-20,0+20)=(0,20)(с₂₅,с₅₂)=(30-20,0+20)=(10,20)               (с₅₉,с₉₅)=(100-20,100+20)=(80,120)

Итерация 6:

1

2

3

4

5

6

7

8

9

0

20

40

10

5

40

5

90

0

30

0

20

80

0

30

0

20

0

160

20

100

0

10

0

30

0

0

20

120

10

 1

0

0

0

100

0

0

0

0

0

0

0

100

0

100

0

0

20

60

10

100

40

30

40

0

90

5

40

5

30

100

20

20

9

8

7

6

5

4

3

0

20

30

        Рисунок 7

1. Назначаем а₁=∞, и помечаем узел 1 меткой [∞,−]. Полагаем i=1.
2. S₁={3} ≠{Ø}
3. k=3, c₁₄=max{c₁₃}=max{20}=20. Назначаем а₁=c₁₃=20  и помечаем узел 3 меткой [20,1]. Полагаем i=3 и возвращаемся к     шагу 2.
4. S₂={7,8} ≠{Ø}
5. k=8, c₃₈=max{c_37, c₃₈}=max{5,90}=90. Назначаем а₈=c₃₈=90  и помечаем узел 8 меткой [90,3]. Полагаем i=8 и возвращаемся к        шагу 2.
6. S₃={Ø} => откат к узлу 3
7. S₄={7} ≠{Ø}
8. k=7, c₃₇=max{c₃₇}=max{5}=5. Назначаем а₇=c₃₇=5 и помечаем узел 7 меткой [5,3]. Полагаем i=7 и возвращаемся к шагу 2.
9. k=9, c₇₉=max{c₇₉}=max{30}=30. Назначаем а₇=c₇₉=30  и помечаем узел 9 меткой [30,7]. Полагаем i=9 и переходим к шагу 7.
10. N₁={а₁,а₃,а_7, а₉} f₁ = min{∞, 20, 5, 30} = 5

(с₁₃,с₃₁)=(20-5,0+5)=(15,5)

(с₃₇,с₇₃)=(5-5,0+5)=(0,5)         (с₇₉,с₉₇)=(30-5,30+5)=(25,35) 

Итерация 7:

1

2

3

4

5

6

7

8

9

0

15

40

10

5

40

0

90

0

30

0

20

80

0

25

0

20

5

160

20

100

0

10

5

30

0

0

20

120

10

 1

0

0

0

100

0

0

0

0

0

0

0

100

0

100

0

0

20

60

10

100

40

30

40

0

90

5

40

5

30

100

20

20

9

8

7

6

5

4

3

0

20

35

          Рисунок 8

Из каждого зернохранилища в  фермы поступит следующее количество зерна:

З1 → Ф1 = 20

З2 → Ф3 = 5

З3 → Ф1 = 100

З3 → Ф2 = 10

З3 → Ф3 = 30

З3 → Ф4 = 20

 

В итоге всего фермы получат зерна:

Ф1 = 120

Ф2 = 10

Ф3 = 35

Ф4 = 20

- что не является достаточным,  чтобы удовлетворить спрос ферм.

Вывод:

Спрос ферм не будет удовлетворен.

Решение:

F= f₁+f₂+f₃+f₄+f₅+f₆ = 20+5+100+10+30+20 = 185

4. ЗАКЛЮЧЕНИЕ

Представленный  алгоритм является оптимальным для  решения данной задачи. В ходе решения  найдена  максимально эффективная схема поставок зерна от зернохранилищ фермам, максимально обеспечивающая их спрос.

 

5. СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Таха Х. Введение в исследование операций, 7-е издание.: Пер. с англ. – М.: Изд. дом «Вильямс», 2005. – 912 с.