Алгоритм Дейкстри та його застосування

Размещено на http://www.allbest.ru/

На даний момент одним з домінуючих різновидів теорії ігор, які застосовуються на практиці є багатокрокові ігри. Завдяки багатокроковим іграми набагато спростилися математичні та графічні методи розв'язування складних задач в різних галузях, зокрема в найпоширенішій галузі її застосування - економіці.

В даній роботі описується алгоритм Дейкстри та їх застосування, які дозволяють визначити оптимальне рішення задачі за допомогою як математичних, так і графічних методів, що дозволить вирішувати широке коло економічних, технічних та іншого роду задач.

Метою курсової роботи є дослідження видів багатокрокових ігор, а також створення конкретної математичної моделі позиційної гри, однієї з різновидів алгоритмів.

Мета курсової роботи конкретизується в таких завданнях:

– проаналізувати позиційні, диференціальні, стохастичні ігри, та ігри на виживання, їх складність, відмінності між собою та можливе застосування;

– розробити конкретну економічну задачу, рішення якої базується на позиційній грі;

– знайти оптимальне рішення задачі шляхом складання матриці та відповідного дерева гри;

– створити користувацьку базу даних на основі вхідних даних і одержаних результатів.

– Виконання бази даних на основі вхідних і вихідних даних розділу №2 виконуємо засобами ПЗ Ms Access 2010. База даних буде складатись з 5 таблиць та 1 запиту.

Об'єктом дослідження даної роботи є алгоритм Дейкстри, основні характеристики, та поверхневе їх дослідження.



Розділ №1

Сіткове моделювання: алгоритм Дейкстри

1. Суть алгоритму Дейкстри та приклад його застосування.

Задано орієнтований граф. Кожній дузі, що з'єднує вершину u_i з вершиною u_j (u_i > u_j), відповідає невід'ємне число c_ij > 0. Це число називаємо вагою дуги [1].

Питання, що тут виникають:

1 Яка довжина найкоротшого шляху між будь-якими двома вершинами графа?

2 Які довжини найкоротших шляхів між виділеною вершиною та іншими вершинами?

3. Які довжини шляхів між усіма парами вершин, що це за шляхи?

Один із методів розв'язання таких задач - це алгоритм Дейкстри (розв'язок одержано у 1960р., автор - Дейкстра).

При роботі цього алгоритма будемо користуватись такими правилами:

1) позначаємо вершини значеннями їх відстаней від виділеної вершини;

2) до остаточної позначки вершині присвоюється тимчасова позначка; ця тимчасова позначка дає відстань від виділеної вершини, коли множина шляхів складається не з усіх можливих;

3) алгоритм припиняє роботу тоді, коли позначка кінцевої вершини не змінюється;

4) у кожний момент роботи алгоритма деякі вершини мають остаточні позначки, а решта не мають [1].

Алгоритм Дейкстри -- алгоритм, що дозволяє знайти найкоротший шлях в зваженому графі між будь-якими двома вершинами. Граф називається зваженим, коли всі його ребра мають вагу. Вагою ребра часто називають його довжину.[12]

Алгоритм Дейкстри можна сформулювати наступним чином:

1) Вибирається початкова вершина графа та присвоюється їй нульову відстань (оскільки ми з неї починаємо) [12]. Тобто, початковій вершині присвоюється остаточна позначка «0», а іншим вершинам - тимчасова позначка «?». Після цього будь-яким методом запускаємо від неї обхід всіх інших вершин графа[1].

2) Для кожної вершини перебираємо всіх її сусідів (сусідами вважаються такі вершини, які з'єднані ребром) і кожному з них присвоюємо відстань, утворену шляхом додавання ваги відповідного ребра до відстані до поточної вершини [13]. Тобто кожній вершині х, яка не має остаточної позначки, присвоюється нова тимчасова позначка за правилом :

min(d_x, d_y+c_yx) (1)

, де d_x - стара тимчасова позначка вершини х; у - вершина, яка одержала остаточну позначку на попередньому кроці; c_yx - вага дуги (у,х) [1].

Отже, Знаходимо найменшу з усіх тимчасових позначок і оголошуємо її остаточною позначкою відповідної вершини. Ця вершина грає роль вершини у для наступного кроку [1].

3) При цьому, якщо сусідній вершині вже присвоєно якесь значення, то залишається те, яке є меншим. В результаті цієї операції ми для кожної вершини отримаємо певне число, яке рівне мінімальній відстані від початкової вершини до даної [12].

4) Знаючи мінімальну відстань до кожної вершини, ми можемо шляхом послідовного перебору її сусідів у зворотньому порядку дійти до початкової вершини. Таким чином ми знайдемо шлях.

Алгоритм можна модифікувати так, щоб він закінчував роботу після одержання усіма вершинами графа G постійних міток, тобто знаходяться найкоротші шляхи з s в усі вершини графа. Алгоритм визначить основне дерево D найкоротших шляхів з вершини s. Для будь-якої вершини v єдиний (s,v) - шлях у дереві D буде найкоротшим (s,v) - шляхом у графі G [10].

Будь-яка задача, що вимагає знаходження оптимальних маршрутів може бути виконана за допомогою алгоритму Дейкстри. Це стосується і мереж, і транспортних потоків, і обробки графів. Дуже часто використовується не сам алгоритм в чистому вигляді, а його модифікація [9].

Приклад застосування алгоритму:

Розглянемо виконання алгоритму на прикладі. Нехай потрібно знайти відстані від 1-ої вершини до всіх інших. Кружечками позначені вершини, лініями -- шляхи між ними («дуги»). Над дугами позначена їх «ціна» -- довжина шляху. Надписом над кружечком позначена поточна найкоротша відстань до вершини.

Зберігатимемо поточну мінімальну відстань до всіх вершин V (від даної вершини a) і на кожному кроці алгоритму намагатимемося зменшити цю відстань. Спочатку встановимо відстані до всіх вершин рівними нескінченості, а до вершини а -- нулю.

Крок 1. Ініціалізація. Відстань до всіх вершин графа V = . Відстань до а = 0. Жодна вершина графа ще не опрацьована.

d1=0, di=?, де i = 2,3,4,5,6.

Крок 2. Знаходимо таку вершину (із ще не оброблених), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуємо цей новий, коротший шлях як поточний найкоротший шлях до сусіда. Перший по порядку сусід 1-ї вершини -- 3-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 3-ю вершиною, тобто 0 + 2 = 2. Це менше поточного найкоротшого шляху до 3-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 2.

d₃ = min(?,0+2) = 2 .

Кроки 3, 4. Аналогічну операцію проробляємо з двома іншими сусідами 1-ї вершини -- 2-ю та 4-ю. d2 = min(4,2+?) = 4

Фактично, немає різниці який шлях вибрати від вершини 1 до вершини 4, оскільки сумарна відстані від шляхів 1-2 і 2-4 і відстань 1-4 одинакова і дорівнює 7.

d₄ = min(?,0+7) = 7, d₄ = min(7,4+3) = 7.

Крок 5. Знову відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 3 з поточною найкоротшою відстанню до неї = 2. Знаходимо найкоротшу відстань до вершини 5. d5 = min(5,4+2) = 5.

Крок 6. Знаходимо відстань до шуканої вершини 6. Причому слід вибрати його як мінімум серед двох альтернативних варіантів проходжень від 1-ої вершини до 6-ої вершини(шлях 1-2-4-6 і 1-3-5-6).

d6 = min(?,5+2) = 7.

d6 = min(7,7+2) = 7.

Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ої вершини до 2-ої становить 4, до 3-ої -- 2, до 4-ої -- 7, до 5-ої --5, до 6-ої -- 7 умовних одиниць.

Переваги й недоліки алгоритму, альтернативні алгоритми.

Переваги алгоритму Дейкстри

Нема необхідності будувати новий граф для кожного проходу.

Алгоритм Дейкстри має порядок n² так що це досить ефективно використовувати для відносно великих проблем, це свідчить про те, що він є порівняно швидший за інші алгоритми для пошуку критичного шляху [12].

Однією з головних переваг Алгоритм Дейкстри є те, що маршрутизатор обчислює маршрути самостійно з використанням тих же вихідних даних статусу, вони не залежать від обчислення проміжних машин. Таким чином, Дейкстра Алгоритми краще, ніж алгоритми вектора відстані [11].

Недоліки алгоритму Дейкстри

Основним недоліком алгоритму є те, що вона робить сліпий і непотрібний пошук, споживаючи багато часу і багато необхідних ресурсів.

Алгоритм Дейкстри не знаходить правильне рішення у випадку від'ємних ваг ребер (дуг) графа. Це призводить доациклічних графів і найчастіше не можуть отримати право найкоротшому шляху [12].

Недоліком майже всіх алгоритмів знаходження найкоротшого шляху в графі і в тому числі алгоритму Дейкстри є те, що вони мають квадратичну і кубічну складності. Кількість шляхів експотенціально зростає , що при великій кількості ребер або дуг робить їх дуже повільними [8].

Недоліком алгоритму Дейкстри є те, що не враховується важливість вузлів та ігноруються вузли, які знаходяться на значній відстані від цільової вершини. Для ліквідації цих недоліків необхідно якимось чином призначати пріоритети вузлам в залежності від відстані до цільової точки, щоб не кожній ітерації алгоритму ті вузли, які знаходяться далі від цілі, не розглядались [5].

Малювання n графів або використання n матриць у процесі розрахунку найкоротших шляхів. Початкове призначення нескінченності довжини шляхів від входу до всіх вершин з наступним корегуванням їх значень. Це сповільнює роботу і ефективність алгоритму [7].

Складність алгоритму Дейкстри

Складність алгоритму Дейкстри залежить від способу знаходження вершини V, а також способу зберігання безлічі невідвіданих вершин і способи оновлення міток. Позначимо через n кількість вершин, а через т - кількість ребер у графі G.

У найпростішому випадку, коли для пошуку вершини з мінімальним d [V] проглядається все безліч вершин, а для зберігання величин d - масив, час роботи алгоритму є O(n²+m). Основний цикл виконується порядку п раз, в кожному з них на знаходження мінімуму витрачається порядка n операцій, плюс кількість релаксацій (змін міток), яка не перевершує кількості ребер у вихідному графі.

Для розріджених графів (тобто таких, для яких т багато менше nІ) Невідвідані вершини можна зберігати в двійковій купі, а в якості ключа використовувати значення d[i], тоді час вилучення вершини з U стане , при тому, що час модифікації d[i] зросте до . Так як цикл виконується порядку п разів, а кількість релаксацій не більше т, швидкість роботи такої реалізації O(n+m).

Якщо для зберігання невідвіданих вершин використовувати фібоначчіеву купу, для якої видалення відбувається в середньому за O(), а зменшення значення в середньому за O(1), то час роботи алгоритму складе O( +m) [9].

Альтернативні алгоритми

Функціональність оригінального алгоритму Дейкстри може бути розширена різними модифікаціями. Наприклад, іноді бажано, щоб представити рішення, які математично менше, ніж оптимальне. Щоб отримати ранжируваний список менше, ніж оптимальне рішення, оптимальне рішення спочатку обчислити. Одне ребро, що входять в оптимальне рішення видалити з графіка, і розрахувати оптимальне рішення цього нового графіка. Кожне ребро оригінальне рішення пригнічується в свою чергу, і розраховується новий найкоротший шлях [10].

Алгоритм широко використовується в програмуванні і технологіях, наприклад, його використовує протокол OSPF для позбавлення від кільцевих маршрутів [9].

На відміну від алгоритму Дейкстри, Беллмана-Форда алгоритм може бути використаний на графах з негативними вагами ребер, поки граф не містить негативних досяжна цикл від джерела з вершини. (Наявність таких циклів означає, що немає найкоротшого шлях, так як загальна вага стає менше, кожен раз, коли цикл буде пройдений) [4].

У порівнянні з методом Дейкстри алгоритм Левіта, що як і алгоритм Дейкстри знаходить найкоротшу відстань від однієї з вершин графа до всіх інших і працює лише для графів без ребер негативного ваги програє в тому, що деякі вершини доводиться обробляти повторно, а виграє на більш простих алгоритмах включення і виключення вершин з множини М1. Експерименти показують, що для графів з «геометричним» походженням, тобто для графів, побудованих на основі транспортних мереж і реальних відстаней, метод Левіта виявляється найбільш швидким. Він виграє і за розміром програми [14].

Метод Левіта має ще й тим перевагою перед методом Дейкстри, що він застосовний у випадку негативних довжин дуг (адже «довжина дуги» - це просто назва, яка дає нам корисні асоціації з реальністю). Якщо вважати, що значення L (U) не обов'язково позитивні, рішення задачі про найкоротший шлях значно ускладнюється.

Перша складність в тому, що втрачається просте правило методу Дейкстри для визначення остаточності обчисленого відстані до конкретної дуги. Ця трудність, як ми побачимо далі, обходиться, хоча і з деякою втратою ефективності методу (доводиться перевіряти всі дуги, провідні в дану вершину).

Друга складність полягає в тому, що при негативних довжинах в графі можуть знайтися контури з від'ємною сумою довжин дуг (назвемо такі контури «негативними»). Додаток до шляху негативного контуру зменшує значення цільової функції, і чим більше обходів негативного контуру ми додамо, тим «краще». Позбавитись від нескінченного убування мінімуму просто так неможливо, але є два виходи з цього становища (звичайно ж, вибір виходу залежить не від нас, а від розв'язуваної практичної задачі).

Заборонити включення в шлях контурів, тобто розглядати тільки прості шляхи, але така заборона робить задачу дуже складною.

У разі негативних контурів вважати, що завдання рішення не має, і обмежиться рішенням задачі у випадках, коли негативних контурів немає. У цьому випадку метод Левіта дасть необхідне оптимальне рішення, а при деякій модифікації дозволить «відловлювати» негативні контури [14].

Алгоритм «кращий-перший». Це перший розглядуваний евристичний пошук, який бере до уваги знання про простір пошуку для направлення своїх зусиль. Він схожий на алгоритм Дейкстри, за винятком того, що вузли в списку Open оцінюються за приблизною відстанню, що залишилася до мети. Ця оцінка так само не вимагає наявності оновлень, на відміну від алгоритму Дейкстри [4].

Алгоритм A* - це алгоритм пошуку по першому найкращому співпадінні на графі, який знаходить маршрут з найменшою вартістю від однієї вершини (початкової) до іншої (цільової, кінцевої). Алгоритм поєднує в собі врахування довжини попереднього шляху з алгоритму Дейкстри з евристикою з алгоритму «кращий-перший» [4].

Порядок обходу вершин визначається евристичною функцією «відстань + вартість» (зазвичай позначається як f(x)). Ця функція - сума двох інших: функції вартості досягнення даної вершини (x) з початковою (зазвичай позначається як g(x) і може бути евристичною) і евристичною оцінкою відстані від розглянутої вершини до кінцевої (позначається як h(x)). Функція h(x) повинна бути допустимою евристичною оцінкою, тобто не повинна переоцінювати відстані до цільової вершини. Наприклад, для задачі маршрутизації h(x) може представляти собою відстань до мети по прямій лінії, тому що це фізично найменша можлива відстань між двома точками.

Алгоритм Прима - алгоритм побудови мінімального остовного дерева зваженого зв'язного неорієнтованого графа. Алгоритм Прима володіє тим властивістю, що ребра в безлічі А завжди утворюють єдине дерево. Дерево починається з довільною кореневої вершини г і росте до тих пір, поки не охопить всі вершини в V. На кожному кроці до дерева А додається легке ребро, що з'єднує дерево і окрему вершину з частини графа. Дане правило додає тільки безпечні для А ребра; отже, по завершенні алгоритму ребра в А утворюють мінімальне остовне дерево. Дана стратегія є жадібною, оскільки на кожному кроці до дерева додається ребро, яке вносить мінімально можливий внесок у загальну вагу.

В якості вхідних даних алгоритму передаються зв'язний граф G і корінь r мінімального остовного дерева. Всі вершини G, ще не потрапили в дерево, зберігаються в черзі з пріоритетом Q. Пріоритет вершини v визначається значенням key [v], яке дорівнює мінімальному вазі ребер, що з'єднують v з вершинами мінімального кістяка. Поле prev [v] для вершин дерева вказує на батька, а для вершин з черги, вказує на вершину дерева, в якою веде ребро з вагою key [v] (одне з таких ребер, якщо їх декілька).

Існує і безліч інших алгоритмів, що в основному є модифікацією вище розглянутих і спрямовані на те, що мінімізувати недоліки основних алгоритмів: зменшення витрат пам'яті, підвищення швидкодії алгоритму, вибір оптимальних параметрів для його реалізації. До таких алгоритмів належать алгоритм A* з ітеративним поглибленням (iterative deeping A*, IDA*), A* з обмеженням пам'яті (memory-bounded A*, MA*), спрощений MA* (simplified MA*, SMA*), рекурсивний пошук по першому найкращому збігу (recursive best-first search, RBFS), алгоритм Белмана-Форда, алгоритм Флойда-Уоршелла, алгоритм Джонсона тощо[4].

Розділ №2: Задача про пошук найкоротшого шляху. Реалізація задачі засобами ПЗ MS Excel

Схема маршрутів, витрати на перевезення товару і пропускна спроможність шляхів представлені в таблиці та на рисунку 1. Потрібно забезпечити перевезення 32 тонн вантажу із пункту A до пункту K щодня з мінімальними витратами.

Позначення шляху	Витрати на перевезення 1т товару (ум. од.)	Пропускна спроможність т/день
AB	50	10
AC	25	20
AD	30	15
AE	20	25
BF	35	30
CF	42	12
DG	56	15
EH	44	17
FI	26	24
GI	18	21
GJ	22	11
HJ	15	17
IK	38	22
JK	25	24

Таблиця 2.1. Схема маршрутів і витрати на перевезення товару

Розвязок задачі засобами ПЗ Ms Excel

Для початку будуємо орієнтований граф, в якому вагами дуг будуть витрати на перевезення 1т вантажу, а вершинами будуть пункти через які цей вантаж будуть провозити, і розвязуємо цей граф алгоритмом Дейкстри.

Риcунок. 2.1 Побудова графу за допомогою MS Excel

Отже, для початку всі вершини приймаємо нескінченість, а вершину дуги А приймаємо 0. Оскільки вершини B, C, D, E звязуються лише з А, то вагою вершини буде вага дуги + вага попередньої вершини, але A=0, тобто В=50, С=25, D=30, E=20.

Риcунок. 2.3 Знаходження найкоротшого шляху до вершин B,C,D,E на першому етапі ітерації

Оскільки до вершини F входять 2 дуги і відразу найкоротших шлях до неї знайти неможливо, то знаходимо його за допомогою внутрішньої функції мінімум в MS Excel.

Риcунок. 2.4 Знаходження найкоротшого шляху до вершини F на першому етапі ітерації

Найкоротший шлях від вершини A до вершин G і H як суми відповідних їм попередніх вершин і ваг дуг.

Риcунок. 2.5 Знаходження найкоротшого шляху до вершини G і Н на першому етапі ітерації

Оскільки до вершин I, J входять 2 дуги і відразу найкоротших шлях до них знайти неможливо, то найкоротший шлях до вершин знаходимо за допомогою внутрішньої функції мінімум в MS Excel. Для знаходження найкоротшого шляху до вершини I, записуємо МИН(Q15+R17;Q17+R18), де Q15+R17 - сума ваги вершини F і ваги дуги FI, а Q17+R18- сума ваги вершини G і ваги GI.

Риcунок. 2.6 Знаходження найкоротшого шляху до вершини I на першому етапі ітерації

Риcунок. 2.7 Знаходження найкоротшого шляху до вершини J

За аналогією (використовуючи функцію МИН в MS Excel) знаходимо найкоротший шлях від вершини А до шуканої вершини К.

Риcунок. 2.8 Знаходження найкоротшого шляху до вершини K

Найкоротший шлях від А до К = 104 од., критичний шлях A-E-H-J-K, отже по ньому ми будемо спочатку провозити вантаж. Для визначення кількості тон перевезення вантажу по даному критичному шляху нам необхідно знайти мінімальну пропускну спроможність серед дуг, що входять до критичного шляху за формулою в Excel : МИН(H10;H14;H18;H20), де H10 - пропускна спроможність шляху AE, H14 - EH, H18 - HJ, а для H20 - JK. Мінімальна пропускна спроможність складає 17 тон, отже по даному критичному шляху провозимо 17 тон. Залишається 15 тон нерозвезеного вантажу.

Риcунок. 2.9 Критичний шлях на першому етапі ітерації

Відкинувши непотрібні вершини, тобто вершини критичного шляху через які пропусна спроможність = 17 тон/день (це вершини E i H), оскільки по них ми вже перевезти вантаж не можемо, отримуємо новий граф, критичний шлях якого будемо шукати за алгоритмом Дейстри.

Риcунок. 2.10 Спрощений граф на другому етапі ітерації

Оскільки вершина А єдина, що входить в вершини B,C,D, то їх вагою буде вага дуги + вага попередньої вершини, але A=0, тобто В=50, С=25, D=30.

Оскільки до вершини F входять 2 дуги і відразу найкоротших шлях до них знайти неможливо, то найкоротший шлях до вершин знаходимо за допомогою внутрішньої функції мінімум в MS Excel. Для знаходження найкоротшого шляху до вершини F, записуємо МИН(R39+S40; R41+S41), де R39+S40 - сума ваги вершини B і ваги дуги BF, а R41+S41- сума ваги вершини C і ваги CF.

Риcунок. 2.11 Знаходження найкоротшого шляху до вершини B, C, D, F на другому етапі ітерації

Найкоротший шлях до вершини G, обчислюється як сума ваги вершини D і ваги дуги DG. Для знаходження найкоротшого шляху до вершини I, записуємо МИН(T40+U41; T42+U42), де R39+S40 - сума ваги вершини F і ваги дуги FI, а R41+S41- сума ваги вершини G і ваги GI.

Найкоротший шлях до вершини J, обчислюється як сума ваги вершини G і ваги дуги GJ. Для знаходження найкоротшого шляху до шуканої вершини K, записуємо МИН(V40+W41; V43+W43), де V40+W41- сума ваги вершини I і ваги дуги IK, а V43+W43- сума ваги вершини J і ваги JK.

Риcунок. 2.13 Знаходження найкоротшого шляху до вершин J, K на 2-ому етапі ітерації

Отже, найкоротший шлях від А до К = 131 од., критичний шлях A-С-F-I-K, отже по ньому ми будемо провозити вантаж. Для визначення кількості тон перевезення вантажу по даному критичному шляху нам необхідно знайти мінімальну пропускну спроможність серед дуг, що входять до критичного шляху за формулою в Excel : =МИН(H8;H12;H15;H19), де H8 - пропускна спроможність шляху AC, H12 - шляху CF, H15 - шляху FI, а для H19 - шляху IK. Мінімальна пропускна спроможність складає 12 тон, звідси по даному критичному шляху провозимо 12 тон. Залишилось 3 тони неперевезеного вантажу.

Риcунок. 2.14 Шуканий граф на другому етапі ітерації

Відкинувши непотрібні вершини, тобто вершини критичного шляху через які пропусна спроможність на попередньому етапі = 15 тон/день (це вершина С), оскільки по ній ми вже перевезти вантаж не можемо, отримуємо новий граф, критичний шлях якого знову будемо шукати за алгоритмом Дейстри.

Риcунок. 2.15 Спрощений граф на третьому етапі ітерації

Оскільки дуги вершини А єдині, що входить в вершини B, C, D, то їх вагою буде вага дуги + вага попередньої вершини, але A=0, тобто В=50, а D=30. Найкоротші шляхи до вершин F, G, J обчислюються як суми ваг вершин B і ваги дуги BF, D i DG, G i GJ відповідно. Для знаходження найкоротшого шляху до вершини I, записуємо МИН(T30+U31; T32+U32), де T30+U31- сума ваги вершини F і ваги дуги FI, а T32+U32 - сума ваги вершини G і ваги GI.

Риcунок. 2.16 Знаходження найкоротшого шляху до вершин B, D, F, G, J на третьому етапі ітерації

Для знаходження найкоротшого шляху до шуканої вершини K, записуємо МИН(V30+W31; V33+W33), де V30+W31- сума ваги вершини I і ваги дуги IK, а V33+W33 - сума ваги вершини J і ваги JK.

Риcунок. 2.17 Знаходження найкоротшого шляху до вершини K на третьому етапі ітерації

Отже, найкоротший шлях від А до К = 133 од., критичний шлях A-D-G-J-K, отже по ньому ми будемо провозити вантаж паралельно попереднім критичним шляхам. Перевозимо залишені 3 тони вантажу по даному критичному шляху, отже ми перевезли 32 тони вантажу від пункту А до пугкту К.

Риcунок. 2.18 Шуканий граф на третьому етапі ітерації

Суму щоденних витрат на перевезення 32 тон вантажу знаходимо як суму добутків перевезених тон на даному відрізку шляху та витрати на перевезення 1 т вантажу на цьому відрізку.

Реалізація в Excel:

=W21*(G10+G14+G18+G20)+W47*(G8+G12+G15+G19)+W37*(G9+G13+G17+G20), де W21, W47, W37 - кількість перевезених тон по 1-ому, 2-ому і 3-ому критичному шляху відповідно, а Gi - це витрати на перевезення 1 тони на і-тому відрізку шляху.

Розділ №3: Створення користувацької бази даних на основі отриманих результатів

гра матриця алгоритм дейкстра

Виконання бази даних на основі вхідних і вихідних даних розділу №2 виконуємо засобами ПЗ Ms Access 2010. База даних буде складатись з 4 таблиць і 1 запиту.

Створюємо в режимі конструктора першу таблицю з іменем «Перший етап», в якому будуть імена полів: Номер частини шляху з типом даних Лічильник, що створене з метою обліку всіх частин шляху графа, які входять до першого етапу;

Позначення шляху з типом даних Текстовий;

Витрати на перевезення 1 тони вантажу з типом Числовий;

Пропускна проможність т/день з типом Числовий;

Також було створено поле з іменем приналежність частини шляху до критичного шляху з типом даних Логічний, що визначає приналежність дуги графу до його критичного шляху. Оскільки тип даних Логічний набуває лише два значення, його зручно використовувати в подальшому для побудови запиту на основі відбору. До того ж, наочно видно яка з частин шляху належить до критичного шляху.



Рисунок.3.1. Побудова першої таблиці в режимі Конструктор.

Заповнюємо таблицю значеннями з умови задачі до розділу №3, та даних на основі опрацювання першого етапу (див. розділ №2)

Рисунок.3.2. Заповнення першої таблиці даними з умови задачі.

Аналогічно створюємо і заповнюємо табличку для другого і третього етапу, при цьому врахувавши що зменшується кількість вершин і дуг графу на кожному з етапів.

Рисунок.3.3. Заповнення другої таблиці даними з умови задачі.

Рисунок.3.4. Заповнення третьої таблиці даними з умови задачі.

Створюємо запит на вибірку на основі попередніх трьох таблиць, використовуючи поля Пропускна проможність т/день та приналежність частини шляху до критичного шляху з кожної з таблиць, при цьому поставивши в параметрах запиту під кожним полем з пропускною спроможністю операцію Min, при цьому встановивши умову відбору TRUE під кожним полем з приналежністю частини шляху до критичного шляху.

Рисунок.3.5. Побудова запиту на вибірку на основі попереднії трьох таблиць в режимі Конструктор.

Створюємо табличку Вихідні дані з полями:

Код етапу з титом даних Лічильник, для відображення порядкового номеру етапу;

Критичний шлях з типом даних Текстовий, для відображення шляху по якому рухатиметься вантаж;

Довжина критичного шляху з типом даних Числовий, для опису довжини критичного шляху графу, в якому дугами вершин були витрати на перевезення 1т вантажу;

Кількість вантажу перевезень з типом даних Числовий, що відображає шукану кількість вантажу, яку ми будемо перевозити по критичному шляху, будується на основі запиту.

Рисунок.3.6. Побудова четвертої таблиці Вихідні результати таблиці в режимі Конструктор.

Рисунок.3.7. Заповнення таблиці Вихідні дані на основі отриманих результатів з розділу №2

На основі вищезгаданих таблиць і запиту будуємо схему даних:



Рисунок.3.8. Схема взаємозв'язку таблиць і запитів БД



Висновок

Алгоритм Дейкстри дозволяє знайти найкоротший шлях в зваженому графі між будь-якими двома вершинами. Граф називається зваженим, коли всі його ребра мають вагу. Вагою ребра часто називають його довжину дозволяють розв'язати значне коло прикладних задач різної галузевої спрямованості, зокрема деякі з них є простими і ефективними. Також задачі значно спрощуються, якщо для розв'язку використовувати графічні методи їх вирішення такого типу, як диференціальні, ігри на розорення та стохастичні є складними в обрахунках, але за допомогою відповідних формул легко піддаються програмуванню.

В даній роботі розглянуто застосування алгоритму Дейкстри на прикладі задачі про дві фірми, які бажають встановити між собою ділові стосунки і вирішити питання про спільне використання парку транспортних засобів. Задача полягала у відшуканні оптимального рішення в даній ситуації, виходячи з альтернативи: розміщення паркінгу на території другої фірми чи задіяти на основі аутсорсингу. Результати відображено за допомогою побудови матриці гри та дерева гри, які відображали собою результати обирання певних стратегій та відповідних ходів. Для наочності було сформовано базу даних на основі вхідних даних, проміжних та отриманих результатів.



Перелік посилань

1. Боровик О.В. Дослідження операцій в економіці. Навч. пос. / О.В. Боровик, Л.В. Боровик - К. : ЦУЛ, 2007. - 424 с.

2. Вовк В.М. Основи системного аналізу. Навч. посібник / В.М. Вовк, З.Б. Дрогомирецька - Львів : ВЦ ЛНУ ім. Івана Франка, 2002. - 248 с.

3. Карбовник М.М. Методичні вказівки до виконання лабораторних робіт з курсу “Дослідження операцій” / М.М. Карбовник, М.В. Негрей - Львів : Видавничий центр ЛНУ ім. І. Франка, 2004.

4. Катренко А.В. Дослідження операцій в економіці: Підручник / А.В. Катренко - Львів : “Магнолія 2006”, 2007. - 480 с.

5. Наконечний С.І. Математичне програмування: Навч. посіб. / С.І. Наконечний, С.С. Савіна - К. : КНЕУ, 2003. - 452с.

6. Математичні методи дослідження операцій: [Навч. пос.] / В.П. Лавренчук, М.І. Букатар, Т.І. Готинчан, Г.С. Пасічник - Чернівці : Рута, 2005. - 360 с.

7. Малиш Н.А. Моделювання економічних процесів ринкової економіки: Навч. пос. / Н.А. Малиш - К. : МАУП, 2004. - 120 с.

8. Математичні моделі в менеджменті та маркетингу: Навч. посібник / [С.К. Рамазанов, Н.О. Рязанцева, Т.В. Ляшенко та ін.] - Луганськ : СПД Резніков В.С., 2010. - 311 с.

9. Сакович В.А. Исследование операций (детерминированные методы и модели): Справ. пособие / В.А. Сакович - Минск : Высшая школа, 1984. - 256 с.

10. Ульянченко О.В. Дослідження операцій в економіці. Підручник для студ. вузів / О.В. Ульянченко - Харків : Гриф, 2002. - 580 с.

11. Вітлінський В.В. Моделювання економіки: Навч. посіб. / В.В. Вітлінський - К. : КНЕУ, 2003. - 408 с.

Размещено на Allbest.ru

...