Інтеграл та його застосування
Київський столичний університет імені Бориса Грінченка
Факультет інформаційних технологій та математики
Кафедра математики і фізики
З В І Т
з практичної роботи № 11
з дисципліни ‟ Методи оптимізації та дослідження операцій”
Тема: Знаходження максимального потоку у мережі з використанням
табличного редактора Microsoft Excel та за алгоритмом Форда-Фалкерсона
Варіант № 6
Виконав(ла): студент(ка) групи Маб-1-23-4.0д
Прізвище І.Б. Тимошек Катерина Андріївна
Дата здачі/захисту 20.05.2025
Перевірив__________________________
Оцінка_____________________________
2025 Виконання роботи
Завдання 1. Для мережі, заданої матрицею С пропускних спроможностей дуг:
1) сформулювати задачу про максимальний потік у вигляді ЗЛП;
2) розв’язати задачу про максимальний потік з використанням надбудови “Розв’язувач” табличного редактора Microsoft Excel.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
11 |
|
9 |
10 |
|
|
2 |
|
|
5 |
6 |
7 |
4 |
|
3 |
|
|
|
8 |
|
9 |
|
4 |
|
|
|
|
2 |
10 |
|
5 |
|
|
|
|
|
17 |
|
6 |
|
|
|
|
|
|
Розв’язання. Намалюємо для наочності геометричне зображення мережі:
Нехай джерело – вузол 1, а стік – вузол 6.
1) Побудуємо математичну модель даної задачі про максимальний потік.
Змінними математичної моделі даної задачі про максимальний потік в мережі є 12 змінних: x12, x14, x15, x23, x24, x25, x26, x34, x36, x45, x46, x56. Кожна з цих змінних xij може приймати невід'ємне цілочисельне значення, що не перевищує пропускної спроможності дуги сij. Тоді математична постановка даної задачі про максимальний потік в мережі може бути записана в наступному вигляді:
де множина припустимих значень Х формується наступною системою обмежень типу рівностей і нерівностей:
2) Створимо файл Microsoft Excel з назвою ПР 10 Макс. потік ПІБ.xlsx. Створимо аркуш Microsoft Excel з назвою «Макс. потік».
1. Введемо умову задачі.
Створимо екранну форму для введення умови задачі і введемо залежності з математичної моделі в екранну форму.
1) Внесемо необхідні написи в клітинки А1: F1.
2) В клітинки А2:А13 введемо індекси початкових вузлів, в клітинки В2:В13 – індекси кінцевих вузлів всіх наявних дуг мережі
3) В клітинки С2:С13 введемо значення пропускних спроможностей відповідних дуг мережі. (Рис. 1).
Рис. 1
4) В клітинку F2, в якій буде відображатися значення ЦФ, введемо формулу, за якою це значення буде розраховано.
5) В клітинки Е2–Е5 введемо формули, які являють собою ліві частини обмежень.
Зовнішній вигляд робочого листа в режимі формул з вихідними даними для розв’язування задачі про максимальний потік в мережі має такий вигляд (рис 2).
Рис. 2
2. У вікні “Параметри розв’язувача” (“Дані”“Аналіз”“Розв’язувач”)
1) Задамо ЦФ – клітинка $F2$, напрям її оптимізації «Максимум», та клітинки змінних $D$2:$D$13.
2) Задамо перші 5 обмежень задачі. З цією метою виконати наступні дії:
- для задання цих обмежень в вихідному діалоговому вікні “Розв’язувача” натиснемо кнопку з написом “Додати”;
- в додатковому вікні, яке з'явиться, виберемо діапазон клітинок $E$2:$E$13, який повинен відобразитися в полі з ім'ям “Посилання на клітинку”;
- як знак обмеження зі списку виберемо рівність «=»;
- як значення правої частини обмеження ввести з клавіатури значення 0;
- для додавання обмежень в додатковому вікні натиснемо кнопку з написом “Додати”.
3) Задати обмеження на пропускні спроможності дуг. З цією метою виконати наступні дії:
- для задання першого з цих обмежень в вихідному діалоговому вікні “Розв’язувача” натиснемо кнопку з написом “Додати”;
- в додатковому вікні, яке з'явиться, виберемо діапазон клітинок $D$2:$D$13, який повинен відобразитися в полі з ім'ям “Посилання на клітинку”;
- як знак обмеження з випадаючого списку виберемо нестрогу нерівність «<=».
- як значення правої частини обмеження в додатковому вікні виберемо діапазон клітинок клітинку $C$2:$C$13.$C$2, який повинен відобразитися в полі з ім'ям “Посилання на клітинку”;
- щоб додати обмеження в додатковому вікні натиснемо кнопку з написом “Додати”.
4) Задати обмеження на цілочисельні значення змінних. З цією метою виконати наступні дії:
- у вихідному діалоговому вікні “Розв’язувача” натиснемо кнопку з написом “Додати”;
- у додатковому вікні, яке з'явиться, виберемо діапазон клітинок $D$2:$D$13, який повинен відобразитися в полі з ім'ям “Посилання на клітинку”;
- як знак обмеження із списку виберемо рядок «ціле»;
- як значення правої частини обмеження в поле з ім'ям “Обмеження”: залишимо без зміни вставлене програмою значення «ціле»;
- щоб додати обмеження в додатковому вікні натиснемо кнопку з написом “Додати”.
5) У вікні додаткових параметрів “Розв’язувача” виберемо позначки «За симплекс-методом» і «Зробити необмежені змінні невід’ємними».
Загальний вигляд діалогового вікна специфікації параметрів “Розв’язувача” показаний на рис. 3.
Рис. 3
6) Запустимо надбудову “Розв’язувач” на виконання. Екранна форма після отримання розв’язку показана на рис.4.
Рис. 4.
Результатом розв’язування задачі про максимальний потік в мережі є знайдені оптимальні значення змінних: x12, x14, x15, x23, x24, x25, x26, x34, x36, x45, x46, x56. Знайденому оптимальному розв’язку відповідає значення цільової функції: v=30.
Тим самим знайдений оптимальний план транспортування продукту від джерела до стоку (рис 5).
Рис. 5
Відповідь: v=35.
Завдання 2. Для мережі, заданої матрицею С пропускних спроможностей дуг, знайти:
1) максимальний потік від вершини s=1 до вершини t=6 за алгоритмом Форда-Фалкерсона;
2) мінімальний розріз.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
11 |
|
9 |
10 |
|
|
2 |
|
|
5 |
6 |
7 |
4 |
|
3 |
|
|
|
2 |
|
10 |
|
4 |
|
|
|
|
2 |
10 |
|
5 |
|
|
|
|
|
17 |
|
6 |
|
|
|
|
|
|
Розв’язання.
Ітерація 1.
Крок 1. Знайдемо ланцюг, який сполучає s=1 з t=6: 1→4→5→6.
Крок 2. Знайдемо θ = min{9, 2, 17}=2. Змінимо матрицю пропускних спроможностей, віднявши θ з пропускних спроможностей дуг ланцюга 1→4→5→6:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
11 |
|
7 |
10 |
|
|
2 |
|
|
5 |
6 |
7 |
4 |
|
3 |
|
|
|
2 |
|
10 |
|
4 |
|
|
|
|
0 |
10 |
|
5 |
|
|
|
|
|
15 |
|
6 |
|
|
|
|
|
|
Ітерація 2.
Крок 1. Знайдемо ланцюг, який сполучає s=1 з t=6: 1→4→6.
Крок 2. Знайдемо θ = min{7, 10}=7. Змінимо матрицю пропускних спроможностей, віднявши θ з пропускних спроможностей дуг ланцюга 1→4→6:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
11 |
|
0 |
10 |
|
|
2 |
|
|
5 |
6 |
7 |
4 |
|
3 |
|
|
|
2 |
|
10 |
|
4 |
|
|
|
|
0 |
3 |
|
5 |
|
|
|
|
|
15 |
|
6 |
|
|
|
|
|
|
Ітерація 3.
Крок 1. Знайдемо ланцюг, який сполучає s=1 з t=6: 1→2→4→6.
Крок 2. Знайдемо θ = min{11, 6, 3}=3. Не міняємо матрицю пропускних спроможностей:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
8 |
|
0 |
10 |
|
|
2 |
|
|
5 |
3 |
7 |
4 |
|
3 |
|
|
|
2 |
|
10 |
|
4 |
|
|
|
|
0 |
0 |
|
5 |
|
|
|
|
|
15 |
|
6 |
|
|
|
|
|
|
Ітерація 4.
Крок 1. Знайдемо ланцюг, який сполучає s=1 з t=6: 1→2→3→6.
Крок 2. Знайдемо θ = min{8, 5, 10}=5. Змінимо матрицю пропускних спроможностей
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
3 |
|
0 |
10 |
|
|
2 |
|
|
0 |
3 |
7 |
4 |
|
3 |
|
|
|
2 |
|
5 |
|
4 |
|
|
|
|
0 |
0 |
|
5 |
|
|
|
|
|
15 |
|
6 |
|
|
|
|
|
|
Ітерація 5.
Крок 1. Знайдемо ланцюг, який сполучає s=1 з t=6: 1→2→5→6.
Крок 2. Знайдемо θ = min{3, 7, 15}=3. Змінимо матрицю пропускних спроможностей:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
0 |
|
0 |
10 |
|
|
2 |
|
|
0 |
3 |
4 |
4 |
|
3 |
|
|
|
2 |
|
5 |
|
4 |
|
|
|
|
0 |
0 |
|
5 |
|
|
|
|
|
12 |
|
6 |
|
|
|
|
|
|
Ітерація 6.
Крок 1. Знайдемо ланцюг, який сполучає s=1 з t=6: 1→5→6.
Крок 2. Знайдемо θ = min{10, 12}=10. Змінимо матрицю пропускних спроможностей:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
0 |
|
0 |
0 |
|
|
2 |
|
|
0 |
3 |
4 |
4 |
|
3 |
|
|
|
2 |
|
5 |
|
4 |
|
|
|
|
0 |
0 |
|
5 |
|
|
|
|
|
2 |
|
6 |
|
|
|
|
|
|
Не існує більше ланцюгів, які сполучають s=1 з t=6.
Крок 3. Знайдемо максимальний потік в мережі. Для цього від елементів початкової матриці пропускних спроможностей віднімемо елементи модифікованої матриці пропускних спроможностей з останньої ітерації:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
11 |
|
9 |
10 |
|
|
2 |
|
|
5 |
3 |
3 |
0 |
|
3 |
|
|
|
0 |
|
5 |
|
4 |
|
|
|
|
2 |
10 |
|
5 |
|
|
|
|
|
15 |
|
6 |
|
|
|
|
|
|
Максимальний потік з s=1 в t=6 дорівнює
v=∑xsi=11+9+10=30, v=∑xjt=5+10+15=30
.
Відповідь: v=30.
Значення потоку збігається із знайденим з використанням надбудови “Розв’язувач” табличного редактора Microsoft Excel.
2) В даній мережі мінімальний розріз – множина дуг { (1, 2), (1, 4), (1, 5)}, (показаний червоним), пропускна спроможність розрізу 11+9+10=30 дорівнює величині максимального s-t-потоку при s=1, t=6.
Контрольні питання
1.Що називається потоком у мережі? Потоком на мережі 
називається дійсна функція, яка кожній дузі (i,j) ставить у відповідність число хij так, що виконуються умови:
1. Обмеженість: для кожної дуги (i,j)∈E виконується 0 ≤ хij ≤ cij, тобто потік через дугу є невід’ємним та не перебільшує пропускну спроможність дуги. 2. Збереженість: для кожного вузла i∈V окрім джерела s та стоку t виконується умова збереження потоку: 
тобто сумарний потік, що заходить в будь-який вузол мережі (крім джерела та стоку), дорівнює сумарному потоку, що виходить з цього вузла.
2. У чому зміст задачі про максимальний потік? Задача про максимальний потік полягає у знаходженні такого потоку за транспортною мережею, щоб сума потоків з витоку, або, що означає те ж саме, сума потоків до стоку була максимальна.
3. Наведіть математичне формулювання задачі про максимальний потік. Математична модель задачі про максимальний потік:
Тут А(i) – підмножина множини V, що включає вузли j, які є кінцями дуг з початком у вузлі i; В(i) – підмножина множини V, що включає вузли j, які є початком дуг, що входять у вузол i (рис.1).
При цьому обмеження (2) - (4) вимагають виконання наступних умов: - величина потоку, що виходить з вершини s (джерела), повинна дорівнювати величині потоку, що входить в вершину t (стік); - будь-який частковий потік, що входить в кожну проміжну вершину графа, має дорівнювати потоку, який виходить з цієї вершини; - величина потоку, що протікає по дузі (i,j) ∈ E, повинна бути невід’ємною і не повинна перевищувати пропускної спроможності цієї дуги сij; - всі змінні набувають тільки невід'ємні цілочисельні значення. Загальна кількість обмежень (2) дорівнює n-1.
4. До якого типу задач лінійного програмування зводиться задача про максимальний потік? Задачу про максимальний потік можна сформулювати як задачу цілочисельного лінійного програмування. Слід, однак, підкреслити, що розв’язування мережевих задач симплекс-методом недоцільно. З іншого боку, вивчення формулювань мережевих задач лінійного програмування допомагає ідентифікувати моделі лінійного програмування, які на перший погляд не є мережевими, але які або безпосередньо, або з деякими модифікаціями можна звести до мережевих. Розв’язування двоїстої ЗЛП для задачі про максимальний потік забезпечує знаходження мінімального розрізу. 5. Наведіть порядок дій при розв’язуванні задачі про максимальний потік в середовищі MS Excel. Порядок повністю описаний в Завданні 1 6. Що називається розрізом у мережі? Розрізом (U,
) мережі називається множина дуг {(i, j) ∈ E}, для яких: i∈ U, j∈
або i ∈ 
, j∈ U. 7. У чому зміст задачі про мінімальний розріз? Розріз називається мінімальним, якщо він має найменшу пропускну спроможність. 8. Як пов’язані між собою максимальний потік і мінімальний розріз? Знаходження мінімального розрізу є одною з основних задач аналізу транспортних мереж. Мінімальний розріз можна відшукати, розв’язуючи двоїсту задачу про максимальний потік у мережі. 9. Сформулюйте теорему Форда-Фалкерсона. Теорема (Форда-Фалкерсона): У будь-якій мережі величина максимального s-t-потоку дорівнює пропускній спроможності мінімального s-t-розрізу. 10. У чому полягає процедура пошуку максимального потоку за алгоритмом Форда-Фалкерсона? Алгоритм Форда–Фалкерсона Крок 1. Знайти ланцюг, який сполучає s з t, по якому потік приймає додатне значення у напрямі s→t. Перейти до кроку 2. Крок 2. Нехай сij- (сij+) – пропускні спроможності дуг ланцюга (s,t) у напрямі s→t (t←s) і θ = min{сij-}>0. Матрицю пропускних спроможностей {cij} змінити таким чином: (а) відняти θ зі всіх сij- ; (б) додати θ до всіх сij- . Замінити поточну матрицю C = {cij} на знов отриману і перейти до кроку 1. Операція (а) дає можливість використовувати залишки пропускних спроможностей дуг вибраного ланцюга у напрямі s→t. Операція (б) відновлює початкові пропускні спроможності мережі, оскільки зменшення пропускної спроможності дуги в одному напрямі можна розглядати як збільшення її пропускної спроможності в протилежному напрямі. Кроки 1 і 2 повторюються доти, поки можна знайти ланцюг, який сполучає s з t. Якщо такого ланцюгу не існує, перейти до кроку 3. Крок 3. Знайти максимальний потік в мережі. Нехай C = {cij} – початкова матриця пропускних спроможностей, і C* = {cij} – остання матриця, що вийшла в результаті модифікації початкової матриці (кроки 1 і 2). Оптимальний потік Х={xij} у дугах задається як 
Максимальний потік з s в t дорівнює 
При цьому v є сумою всіх додатних θ, визначених на кроці 2. Таким чином, можна пояснити, чому використовуються додатні елементи матриці С–С* для визначення результуючого потоку у напрямі s→t.
про публікацію авторської розробки
Додати розробку