Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Задача про максимальний потік в мережі та її змістовні інтерпретації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Інформаційні системи та мережі
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Детерміновані моделі дослідження операцій та оптимізації інформаційних систем
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра “Інформаційні системи та мережі”
К У Р С О В А Р О Б О Т А
з дисципліни “Детерміновані моделі дослідження операцій та оптимізації інформаційних систем”
на тему:
“Задача про максимальний потік в мережі та її змістовні інтерпретації”
ЛЬВІВ – 2011
Текст індивідуального завдання: На міську станцію очищення води приходять забруднені води з 10-ти насосних підстанцій. В результаті будівництва нових районів в мережу буде надходити додаткова кількість забрудненої води, в зв'язку з чим необхідно визначити чи достатня пропускна спромож ність існуючої системи (для водопровідних труб вказані залишки пропускної здатності).
Календарний план, дати отримання завдання та здавання роботи.
Керівник видає студентові тему курсової роботи та індивідуальне завдання протягом 1-го тижня семестру. На ґрунті індивідуального завдання студент здійснює формулювання проблеми, визначає мету дослідження та перелік можливих критеріїв оцінки якості операції. Особливу увагу слід звернути на формулювання мети дослідження та можливі альтернативні шляхи її реалізації. Із сформульованого переліку критеріїв шляхом консультацій з керівником синтезується глобальний критерій або вибирається найважливіший.
22.08
На основі індивідуального завдання та результатів попереднього етапу студент будує формальну модель операції, розв’язуючи спочатку пряму задачу дослідження операцій — визначаючи формальний вигляд критерію якості операції, й далі, виділяючи параметри, змінні та формулюючи обмеження, здійснює формальну постановку задачі. Визначається клас задач дослідження операцій, до якого належить отримана постановка, та на основі аналізу літературних джерел - її можливі сфери застосування.
26.09
Проводиться аналіз існуючих методів отримання оптимальних розв’язків на формальній моделі операції з використанням літературних джерел. Обґрунтовується вибір конкретного методу порівнянням його характеристик з іншими. У випадку синтезу оригінального методу обґрунтовуються очікувані значення характеристик роботи алгоритму.
12.10
Розробка плану створення програмного забезпечення здійснюється паралельно з структуризацією програми методами структурного або об’єктного проектування. Для кожного з модулів (класів) програми визначається його функція і поведінка та повністю описується інтерфейс. Тестові приклади складаються таким чином, щоб перевірити правильність функціонування програми в умовах, наближених до реальних умов експлуатації.
14.11
Отримане згідно до індивідуального завдання розв’язання реальної задачі дослідження операцій служить для проведення наступного його аналізу на несуперечливість та чутливість. За результатами виконаної курсової роботи оформляється пояснювальна записка та формулюються висновки.
25.11
Завдання прийнято до виконання:
29.08
Керівник роботи:
/Камінський Р. М./
Зміст пояснювальної записки
Вступ - 5 -
1. Змістовна постановка задачі операційного дослідження - 7 -
2. Формальна постановка задачі - 8 -
3. Аналіз методів та алгоритмів розв'язування задачі - 12 -
4. Опис програмного забезпечення задачі - 14 -
5. Аналіз та інтерпретація отриманих результатів - 16 -
Висновки - 17 -
Список літератури - 18 -
Вступ
Дослідження операцій як наукова дисципліна виникло перед Другою світовою війною, виходячи з військових потреб, і надалі знайшло широке застосування до розв’язання практичних задач в економіці та інших галузях. Діяльність вчених-операціоністів в той час не обмежувалася лише елементами технічних рішень, а включала й застосування відповідних знань при плануванні тактичних військових операцій та опрацюванні їх стратегії. Звідси і бере початок назва дисципліни - «Дослідження операцій». Найважливішим в цьому для майбутнього було те, що багато хто з фахівців побачив у військових розробках зародження нової науки про функціональні системи, а також можливості застосування отриманих знань в мирний час.
Починаючи з 50-х років ХХ-го століття, дослідження операцій отримало визнання як самостійний предмет, що читається для студентів та аспірантів у багатьох вищих закладах освіти світу і є важливим для майбутніх фахівців як в галузі комп’ютингу, так і для фахівців галузі організаційного управління та економістів.
Дослідження операцій (ДО) - це теорія математичних моделей та методів отримання оптимальних розв’язків, що спрямована на обгрунтування доцільності вибору тієї чи іншої альтернативи з множини можливих в області цілеспрямованої діяльності людини. ДО служить для кількісного обгрунтування рішень, що приймаються в організаціях, і виходить з того, що якість рішення можна кількісно оцінити за допомогою одного чи декількох критеріїв якості.
Розвиток методів лінійного програмування в роботах Л. В. Канторовича та Дж. Данціга поклав початок практичному застосуванню методів дослідження операцій, а теоретичні результати Г. Куна та А. Такера заклали грунт для наступних досліджень в області нелінійного програмування. В наступних роботах багатьох вчених-операціоністів були розвинуті методи розв’язання як спеціальних задач квадратичного нелінійного програмування, так і градієнтні методи пошуку оптимальних рішень для загальних задач нелінійного програмування.
Широко відомими в світі є роботи українських вчених О.Г. Івахненка, який запропонував та розробив метод групового врахування аргументів, що знайшов застосування в прогнозуванні економічних процесів, великим є вклад В.М. Глушкова в розроблення та впровадження оптимізаційних задач в АСУ, B.C. Михалевича та І.В. Сергієнка в області дискретної оптимізації та багатьох інших.
У багатьох задачах лінійного і нелінійного програмування процес залежить від часу - реалізується в декількох періодах. При розв’язанні таких багатокрокових задач необхідно враховувати поетапний розвиток процесу. Метод розв’язання задач такого типу складає сутність динамічного програмування. Великий внесок у його розвиток вніс американський математик Річард Белман, який сформулював основоположний принцип оптимальності.
Задачі планування та керування на мережах є моделями процесів планування та управління складними проектами, що включають до свого складу множину напіввпорядкованих робіт, для виконання яких необхідно використати певні об’єми ресурсів різних типів. На основі методів СРМ та PERT розроблене і широко застосовується програмне забезпечення для планування та управління множиною проектів (як лінійка продуктів фірми Primavera чи Microsoft Project фірми Microsoft). Важливі практичні застосування знайшли задачі управління запасами, ремонту та заміни обладнання та задачі масового обслуговування.
Задачі з активною протидією полягають у визначенні розумної стратегії поведінки за умови конфлікту інтересів. В задачах цього типу інтереси учасників можуть бути або антагоністичними, або (що відповідає ситуаціям, поширеним в економіці) частково збіжними, а частково протилежними.
Задачі транспортування продуктів є задачами вибору маршрутів, які найчастіше зустрічаються при дослідженні різноманітних процесів на транспорті та в комп’ютерних мережах (транспортування інформації). Розв’язання задач цього типу зводиться до визначення деякого маршруту (чи множини маршрутів)з числа можливих, які є найекономічнішими з точки зору критерія якості (наприклад, найменша вартість чи найкоротший шлях).
Змістовна постановка задачі операційного дослідження
Задачі потокового типу дуже часто виникають на практиці - в багатьох випадках потрібно визначити множину найкоротших шляхів, мінімізувати мережу, розрахувати пропускну спроможність водогінної системи та «вузьке місце» в ній. Задачі потокового типу можуть бути сформульовані як задачі ЛП та розв’язані за допомогою симплекс- методу, але ця можливість є лише принциповою, тому що розмірність відповідних задач ЛП буде надзвичайно великою, і матриці коефіцієнтів обмежень дуже розрідженими. Водночас спеціальна структура окремих класів потокових задач дозволяє побудувати ефективні алгоритми їх розв’язування. Теоретичним фундаментом для потокових задач є теорема Форда-Фалкерсона, а також властивість унімодулярності матриці коефіцієнтів обмежень, що дозволяє з одного боку, побудувати ефективний алгоритм пошуку макси мального потоку та мінімального розрізу - власне того «вузького місця» в мережі, а також забезпечити цілочисельність розв’язку за умови цілочисельності значень параметрів задачі. Загальна постановка задачі потокового типу дозволяє краще зрозуміти основні типи потокових задач та взаємні зв’язки між ними. Знання теоретичних основ та володіння потоковими алгоритмами дозволяє ефективно розв'язувати різноманітні практичні задачі.
Формальна постановка задачі
Ця задача, як і задача про найкоротший шлях, є частинним випадком задачі про оптимальний потік. Із задачею про максимальний потік тісно пов'язана задача про мінімальний розріз мережі. Наведемо формулювання цих задач.
Розглянемо мережу, що визначається графом g , яка має єдине джерело s , єдиний стік t та означену на множині U функцію пропускної спроможності /. Нехай інтенсивність джерела /. За теоремою існування потоку на мережі інтенсивність стоку має бути рівною /. Допустимий потік для розглядуваної мережі визначається співвідношеннями:
/
Задача про максимальний потік полягає у знаходженні максимального значення інтенсивності d , при якому в розглядуваній мережі існує потік. Потік /, що відповідає максимальному значенню d * інтенсивності, називається максимальним потоком, a d * — величиною цього потоку.
Розглянемо описану вище мережу. Розрізом мережі, що відокремлює s від t , називається множина дуг /, де С — деяка множина вершин /мережі, така, що /.
Нагадаємо, що пропускна спроможність цього розрізу визначається звичайним чином:
/
Зрозуміло, що для кожної конкретної мережі вибір множини С повністю визначає пропускну спроможність розрізу. Розріз, що має найменшу пропускну спроможність, називається мінімальним. Задача пошуку такого розрізу називається задачею про мінімальний розріз.
Виявляється, що сформульовані задачі є двоїстими і, як слід чекати, їх розв'язки тісно пов'язані між собою.
Теорема 3.3 (Форда-Фалкерсона). Величина максимального потоку із s в t дорівнює пропускній спроможності мінімального розрізу, що відокремлює s від t .
Зауважимо, що теорема тривіальна, якщо мережа складається з вершин та дуг, що утворюють єдиний шлях від s до t.
У наведеному прикладі мінімальний розріз здійснює дуга (2,3). її пропускна спроможність /визначає максимальну інтенсивність d *=2 допустимого для мережі потоку.
Доведення . Нехай /— максимальний потік на мережі, що визначається графом g , d * — величина максимального потоку. Нехай U ( C ) — довільний розріз мережі, що відокремлює s від t , r (С) — його пропускна спроможність. За теоремою існування потоку /. Нам необхідно показати, що існує така множина С*, що
/
Множина С*, що визначає мінімальний розріз, будується на основі потоку х * таким чином :
/
Спочатку покажемо, що /. Від супротивного: нехай /. Із означення множини С* випливає, що будь-які дві її вершини можна з'єднати ланцюгом. З'єднаємо вершини /та /:
/.
Для цього ланцюга умови можна переписати так:
якщо для ребра /
якщо для ребра /
Нехай
/
/
Покладемо
/
Нехай
/
Зрозуміло, що /. Змінимо потік вздовж ланцюга С , збільшуючи його на /уздовж ребер множини /і зменшуючи його на /уздовж ребер множини /. У результаті одержимо допустимий потік величини /, що суперечить припущенню про максимальність потоку х *. Отже /.
Покажемо, що /. Із означення множини С* випливає, що
/
Запишемо співвідношення при х = х * для /
/
Підсумовуючи останні рівності по /, маємо
/
Розглядаючи випадки /та /, з останньої рівності маємо:
/
Другий та третій доданки у цій рівності взаємно знищуються і, приймаючи до уваги , одержуємо
/
або /
Наслідок . Якщо дуга ( i , j ) входить до мінімального розрізу, то величина максимального потоку по цій дузі дорівнює її пропускній спроможності /. При цьому кажуть, що потік насичує дугу.
Для розв'язування задачі про максимальний потік Фордом та Фалкерсоном був розроблений метод, що носить їх ім'я.
Згідно теореми про максимальний потік та мінімальний розріз за відомим максимальним потоком /легко побудувати мінімальний розріз U ( C *) (див. співвідношення (3.9)). Крім того, якщо потік не є максимальним, то можливе його збільшення шляхом зміни потоку вздовж певного ланцюга. Ці факти лежать в основі методу Форда-Фалкерсона, що являє собою рекурентну процедуру, на кожному кроці якої позначаються вершини або будується потік більшої величини.
Аналіз методів та алгоритмів розв'язування задачі
Алгоритм Форда-Фалкерсона розпочинає роботу з будь-якого допустимого потоку /(зокрема нульового) величини /. Згідно для цього потоку визначається множина /. Якщо /, то потік /є максимальним, в іншому випадку можна знайти /та новий потік /величини /. Для нового потоку цей цикл операцій повторюється і т. д.
Процеси визначення /та /об'єднуються в один процес "розставлення позначок" вершин. Позначка /довільної вершини i складається з двох чисел /та /. Ці числа означають, що вздовж деякого ланцюга, останнім ребром якого є /, можна додатково доставити /, одиниць потоку з вершини s до вершини i .
Дамо детальний виклад алгоритму, вважаючи, що відомий допустимий потік х (зокрема нульовий).
Алгоритм Форда-Фалкерсона
Крок 1 (процес розставлення позначок). На цьому кроці кожна з вершин належить до одного з трьох типів:
непозначена,
позначена і непроглянута,
позначена і протянута.
Спочатку всі вершини непозначені.
Позначимо вершину s позначкою /, що означає: можна послати потік з вершини s у саму себе необмеженої величини.
Тепер вершина s позначена і непроглянута.
Взагалі, нехай j — позначена і непроглянута вершина, /або /— її позначка. Розглядаємо ще непозначені вершини /k : і /. Кожній з таких вершин приписуємо позначку /, де /. Розглядаємо ще непозначені вершини /, і /. Кожна з таких вершин одержує позначку /, де /.
Всі вершини k , які одержали позначки, тепер позначені і непроглянуті, а вершина j — позначена і протянута.
Продовжуємо приписувати позначки непозначеним вершинам до тих пір, поки або вершина t виявиться позначеною, або не можна буде позначити жодної вершини і вершина t виявиться непозначеною.
У другому випадку існуючий потік х — максимальний, а множина позначених вершин С * визначає мінімальний розріз мережі.
У першому випадку існуючий потік х на кроці 2 можна збільшити.
Крок 2 ( збільшення потоку). Нехай /, або /— позначка вершини t . Це означає, що існуючий потік з s в t можна збільшити на величину /. Для цього в першому випадку замінюємо /на /, у другому — /замінюємо на/.
Переходимо до вершини k і виконуємо аналогічні операції, змінюючи величину потоку на ту ж величину /. Продовжуємо ці дії, поки не досягнемо вершини s . Після цього ліквідовуємо позначки всіх вершин і переходимо до кроку 1.
Опис програмного забезпечення задачі
Для виконання відкомпільованої програми потрібен ПК із встановленою програмою .NET Framework 4.0. Якщо ж наявний лише текст програми, то потрібно мати ще середовище програмування C#. У програмі використовуються принципи ООП.
Текст програми:
using System;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
int n;
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
dataGridView1.Visible=false;
}
private void textBox1_TextChanged(object sender, EventArgs e)
{
}
private void label2_Click(object sender, EventArgs e)
{
}
private void dataGridView1_CellContentClick(object sender, DataGridViewCellEventArgs e)
{
}
private void button1_Click(object sender, EventArgs e)
{
n = int.Parse(textBox1.Text);
dataGridView1.RowCount = n;
dataGridView1.ColumnCount =n;
dataGridView1.Visible = true;
}
int findPath(int[,] cap, bool[] vis, int u, int t, int f)
{
if (u == t)
return f;
vis[u] = true;
for (int v = 0; v < vis.Length; v++)
if (!vis[v] && cap[u,v] > 0)
{
int df = findPath(cap, vis, v, t, Math.Min(f, cap[u,v]));
if (df > 0)
{
cap[u,v] -= df;
cap[v,u] += df;
return df;
}
}
return 0;
}
int maxFlow(int[,] cap, int s, int t)
{
for (int flow = 0; ; )
{
int df = findPath(cap, new bool[(int)Math.Sqrt(cap.Length)], s, t, int.MaxValue);
if (df == 0)
return flow;
flow += df;
}
}
private void button2_Click(object sender, EventArgs e)
{
int x, y;
x=int.Parse(textBox2.Text);
x--;
y = int.Parse(textBox4.Text);
y--;
int[,] capacity = new int[n,n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
capacity[i,j]=int.Parse(dataGridView1[j,i].Value.ToString());
textBox3.Text=maxFlow(capacity, x, y).ToString();
}
}
}
Аналіз та інтерпретація отриманих результатів
Інтерфейс програми текстовий. В результаті програма виводить величину потоку. Програма реалізує алгоритм Форда -Фалкерсона
/
Таким чином максимальний потік у мережі становить 13 одиниць.
Висновки
Виконавши курсову роботу, я навчився розвязувати задау знаходження максимального потоку в мережі. Написана програма дозволяє за введеними даними у двовимірному масиві розвязати задачу. Програма виводить значення максимального потоку на екран. Ця програма може використовуватись для вирішення різноманітних задач з постачання ресурсів. Метод дозволяє обчислювати для прикладу пропускну здатність системи водопостачання, газопостачання чи інших ресурсів, визначати вузькі місця у системі. Також, використовуючи такий алгоритм, можна збільшити кількості поставок без значних затрат, визначивши слабкі місця.
Цей метод має велике значення у густозаселених районих для вирішення життєвонеобхідних завдань.
Список літератури
Катренко А. В. Дослідження операцій. Львів, “Магнолія - 2006”, 2009.
ru.wikipedia.org/wiki/Поток_в_графе
Зайченко Ю. П. Исследование операций, Київ, “Вища школа”, 1988.
http://sites.google.com/site/indy256/algo/preflow
15.05.2013 17:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора