WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Дослідження операцій. Задачі упорядкування та координації. Сітьове планування та керування - Реферат

Дослідження операцій. Задачі упорядкування та координації. Сітьове планування та керування - Реферат

3 Рис.2. Припустимо, пройдений n-1 етап і визначено вершини (n-1)-го рангу. Викреслимо всі дуги, які виходять з вершин (n-1)-го рангу. Розглянемо всі вершини, в яких закінчуються викрес-лені на цьому етапі дуги. Вершини, в які заходять лише дуги, визначені на (n-1)-му етапі, утворюють множину вершин n-го рангу. Пронумеруємо їх у довільному порядку, використовуючи неперервно числа натурального ряду, починаючи з найменшого, яке не було використане для нумерації вершин (п-1)-го рангу. Алгоритм завершується по досягненні кінцевої вершини. Для нашого прикладу (рис. 2) це вершина "56"( V56), де індекс 5 означає ранг кінцевої вершини, а індекс 6 - її порядковий номер. Виконавши правильно нумерацію вершин графу, в подальшому індекс рангу вершини можна не вказувати. Алгоритм правильної нумерації вершин графу може бути представлений по-іншому . Алгоритм пошуку найкоротшого шляху мережі (графу) Виконавши правильну нумерацію графу мережі, можна ефективно реалізувати алгоритм пошуку найкоротшого шляху між заданими вершинами. Реалізацію алгоритму приведено до побудови послідовності шляхів з однієї дуги, двох дуг, трьох дуг і т. д., які з'єднують верши-ни певного рангу з кінцевою вершиною. При цьому перегляд вершин виконується в послідовності зменшення їх номерів. На кожному етапі алгоритму відбувається перехід від вершини більш високого рангу до вершини меншого рангу за умови, що із множини всіх шляхів, які починаються в одній і тій же вершині, необхідно залишити для наступного кроку реалізації алгоритму лише найкоротший шлях від цієї вершини до завершальної. За правильної нумерації вершин такий упорядкований перехід у послідовності зменшення рангів відбувається автоматично, навіть за умови, коли нумерацію рангів вершин опущено. Розглянемо реалізацію алгоритму на прикладі графу, зображеного на рис. 2. Згідно з алгори-тмом будемо рухатися від кінцевої вершини V56 до початкової V00, крокуючи послідовно від вершин більш високого рангу до вершин меншого рангу. У кружках, які зображають верши-ни графу, будемо записувати найкоротшу віддаль від вершини (n-l)-ro рангу до кінцевої ве-ршини. Одночасно найкоротший шлях від кожної вершини до кінцевої будемо відмічати подвійною стрілкою. У кружку останньої кінцевої вершини V56 записуємо "0", бо звідси виконуємо відлік віддалі. Потім переходимо до вершини 4-го рангу - в прикладі це вершина V45. Від цієї вершини в кінцеву маємо лише один шлях: (V45, V56) , його довжина дорівнює двом одиницям виміру, її і запишемо у вершині V45, а відповідну дугу позначимо на графові подвійною стрілкою. Переходимо до вершини 3-го рангу V34. З цієї вершини в кінцеву маємо два шляхи: (V34 , V56) та (V34 , V45 ,V56). Найкоротшим є останній. Його одержуємо, додаючи дугу (V34, V45) до вже побудованого шляху (V45, V56 ) та відмічаючи шлях (V34, V45 ) подвійною стрілкою. Довжина шляху (V34 , V45 ,V56) дорівнює 1+2=3 , записуємо це число у вершині V34 . Шлях (V34 , V56 ) при наступних пошуках не використовуємо, тому що з вершини 3-го рангу вже знайдено найкоротший шлях до кінцевої вершини. Переходимо до вершин 2-го рангу: V22 , V23. Розглянемо шляхи, якими можна перейти від цих вершин до вершин вищого рангу. З вершини V22 до вершини вищого рангу можна потрапити лише по дузі (V22, V34). її відмічаємо подвійною лінією та записуємо в V22 число 3+3=6 - найкоротша віддаль від V22 до V56 , враховуючи, що найкоротша віддаль від V34 до V56 уже визначена. З вершини V23 можна потрапити в вершини вищого рангу або по дузі (V23, V34), або по дузі (V23, V45 ). Обчислюємо шлях від V23 до V56 за умов руху із V23 по названим дугам. Шлях (V23 ,V45, V56) має довжину 2+2=4 , шлях (V23, V34, V56) 2+3=5 . Порівнявши названі величини, приходимо до висновку, що найкоротшим шляхом від V23 до V56 буде шлях (V23, V45, V56), отже дугу (V23 , V45) позначаємо подвійною лінією, а в вершині V23 ставимо "4". Розглянувши всі вершини 2-го рангу, переходимо до вершин 1-го рангу. У наведеному прикладі це лише V11 , з якої виходять дуги (V11 , V22 ), (V11, V23) та (V11 , V45). Розглядаємо й оцінюємо шляхи, які починаються цими дугами та закінчуються в V56 : (V11, V45 , V56 ), (V45, V23 , V45 , V56 ) та (V11 , V22 , V34 , V45 , V56 ). Решту шляхів, що починаються цими дугами й закінчуються в V56 , не розглядаємо, бо вони мають дуги, які не позначені подвійною стрілкою (шляхи з непозначеними подвійною стрілкою дугами не можуть бути найкоротшими до кінцевої вершини). Обчислюємо довжину кожного з трьох названих шляхів та вибираємо найкоротший: (V11,V45 ,V56 ). Довжину цього шляху 4+2=6 записуємо в V11 , позначивши подвійною лінією дугу (V11 ,V45). Отже, найкоротші шляхи як від V11 , так і від V22 до V56 мають однакову довжину - шість одиниць. Перейдемо до розгляду вершини V00. З неї виходять дві дуги - (V00 , V11 ) та (V00 ,V22), корис-туючись якими, можна дістатися до вершин вищого, ніж нульовий, рангу. З двох названих дуг меншу довжину має дуга (V00 , V22). Тому найкоротший шлях від початкової вершини V00 до кінцевої V56 буде (V00 , V22 , V34 , V45 , V56), його довжина - сім одиниць. Складові дуги шляху всі позначені подвійною лінією. Якщо завантаження графу рис. 2 тлумачити не як відстані, а як тарифи перевезень вантажу, то ми знайшли шлях найменшої вартості перевезення з вершини V00 до V56 . Зауваження 1. Використання описаного алгоритму дає можливість визначити найкоротший шлях та найменшу відстань від довільної вершини графу до кінцевої: найменша відстань записується в кружках, які зображають вершини, а найкоротший шлях відмічається на гра-фові подвійною лінією. Наприклад (рис. 2): найкоротший шлях з вершини V11 до V56 має до-вжину шість одиниць і проходить через вершини (V11 , V45 , V56), з вершини V22 - теж шість одиниць і проходить через вершини (V22 , V34 , V45 , V56). Зауваження 2. Описаний алгоритм побудований на так званому "принципі оптимальності": якщо найкоротший шлях від початкової вершини до кінцевої проходитьчерез деяку вершину Vi , то відрізок цього шляху від вершини Vi , до кінцевої вершини є найкоротшим серед усіх шляхів, які з'єднують вершину Vi , та кінцеву. Так, у розглянутому прикладі найкоротший шлях від V00 до V56 (V00 ,V22 ,V34 ,V45 ,V56 ) як свої складові має найкоротші шляхи до кінцевої вершини від усіх вершин, через які він проходить. Побудова графу планування та управління мережею (ПУМ) Розглянемо методи планування та управління при реалізації проектів створення складних систем, якими можуть бути як виробничі, так і науково-дослідні системи. Щоб скласти план виконання робіт за такими проектами, необхідно зобразити його деякою математичною мо-деллю, яка називається моделлю мережі і є відображенням певних послідовностей виконання робіт і взаємозв'язків між ними з урахуванням необхідних матеріальних ресурсів. Отже, під моделлю мережі будемо розуміти план виконання комплексу взаємопов'язаних робіт, представлений у специфічній формі графу, який називається графіком мережі. Основними елементами графіка мережі є поняття події та роботи. Термін робота використовується в системі планування та управління мереж (ПУМ) у широ-кому розумінні. По-перше, це певна реальна робота, яка потребує затрат матеріальних ресурсів та відповід-ного терміну виконання. Кожна така робота має бути чітко визначеною, конкретною та сто-суватися відповідального виконавця, без наявності якого марно говорити про планування. По-друге, до поняття роботи відносять чекання - процес у часі, який не потребує ніяких ма-теріальних затрат (наприклад, затвердіння бетону після виконання відповідних робіт, виси-хання фарби тощо). По-третє,
Loading...

 
 

Цікаве