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

Автор работы: Пользователь скрыл имя, 03 Февраля 2014 в 14:52, курсовая работа

Краткое описание

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

Содержание

1. ВВЕДЕНИЕ 3
2. ПОСТАНОВКА ЗАДАЧИ И МЕТОД РЕШЕНИЯ 4
2.1 Общая постановка задачи о максимальном потоке 4
2.2 Математическая модель 4
2.3 Алгоритм Форда-Фалкерсона нахождения максимального потока 4
3. ПРАКТИЧЕСКАЯ ЧАСТЬ 6
4. ЗАКЛЮЧЕНИЕ 14
5. СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 15

Скачать в ZIP архиве (317.57 Кб) Сколько стоит заказать работу?

Вложенные файлы: 1 файл

КУРСОВАЯ И.О..docx

— 325.08 Кб (Скачать файл)

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

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

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

Итерация 5:

100

160

100

Рисунок 6

Назначаем а₁=∞, и помечаем узел 1 меткой [∞,−]. Полагаем i=1.
S₁={2,3,4} ≠{Ø}
k=4, c₁₂=max{c₁₂,c₁₃,c₁₄}=max{20,20,40}=40. Назначаем а₄=c₁₄=40 и помечаем узел 4 меткой [40,1]. Полагаем i=4 и возвращаемся к шагу 2.
S₂={6,8} ≠{Ø}
k=6, c₄₇=max{c_46, c₄₈}=max{30,20}=30. Назначаем а₆=c₄₆=30 и помечаем узел 6 меткой [30,4]. Полагаем i=6 и возвращаемся к шагу 2.
S₃={Ø} => откат к узлу 4
S₄={8} ≠{Ø}
k=8, c₄₇=max{c₄₈}=max{20}=20. Назначаем а₈=c₄₈=20 и помечаем узел 8 меткой [20,4]. Полагаем i=8 и возвращаемся к шагу 2.
S₅={Ø} => откат к узлу 1
S₆={2,3} ≠{Ø}
k=2, c₁₂=max{c₁₂,c₁₃}=max{20,20}=20. Назначаем а₂=c₁₂=20 и помечаем узел 2 меткой [20,1]. Полагаем i=4 и возвращаемся к шагу 2.
S₇={5,6,8} ≠{Ø}
k=8, c₂₈=max{c₂₅,c_26, c₂₈}=max{30,5,40}=40. Назначаем а₈=c₂₈=40 и помечаем узел 8 меткой [40,2]. Полагаем i=8 и возвращаемся к шагу 2.
S₈={Ø} => откат к узлу 2
S₉={5,6} ≠{Ø}
k=5, c₂₅=max{c₂₅,c₂₆}=max{30,5}=30. Назначаем а₅=c₂₅=30 и помечаем узел 5 меткой [30,2]. Полагаем i=5 и возвращаемся к шагу 2.
S₁₀={9} ≠{Ø}
k=9, c₅₉=max{c₅₉}=max{100}=100. Назначаем а₅=c₅₉=100 и помечаем узел 9 меткой [100,5]. Полагаем i=9 и переходим к шагу 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:

160

100

120

100

Рисунок 7

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

160

100

120

100

Рисунок 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

ЗАКЛЮЧЕНИЕ

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

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

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

Информация о работе Задача о максимальном потоке