Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Аналіз та оптимізація сіткового графікаРозрахований критичний шлях, що характеризує час виконання всіх робіт, які входять у сітковий графік, порівнюється із заданим директивним терміном виконання всіх робіт. Для детермінованого сіткового графіка достатньо, щоб критичний шлях за тривалістю був меншим від директивного терміну. Для стохастичного (імовірнісного) сіткового графіка внаслідок наявності дисперсії оцінок виконання робіт, з яких складається критичний шлях, навіть якщо критичний шлях менший від директивного, необхідно розрахувати Імовірність успіху, тобто імовірність того, що відбудеться саме так, як це запроектовано. У загальному вигляді задача зводиться до визначення імовірності Р потрапляння неперервної випадкової величини х в інтервал (а, b). Випадковою величиною є термін здійснення завершальної події Тk. Розподіл величини Тk виявляється близьким до нормального за такого припущення. Тривалість робіт, що лежать на критичному шляху, є незалежними випадковими величинами. У теорії ймовірностей встановлюється, що нормальний закон є граничним для суми таких складових. Для нормального закону розподілу диференціальна функція розподілу має вигляд
де а — математичне сподівання неперервної випадкової величини (для даного випадку а =Тk розрахункове); а —Тк середньоквадратичне відхилення, оскільки дисперсія суми випадкових величин дорівнює сумі дисперсій складових, для критичного шляху , а загальна дисперсія дорівнює сумі дисперсій робіт критичного шляху. Тоді
Або
Згідно з припущенням про нормальний закон розподілу величини Тk можна розрахувати межі а і (3 зміни очікуваного терміну здійснення завершальної події за «правилом трьох сігм». Оскільки центром розсіяння в даному випадку є Тk то межі зміни очікуваного терміну завершення робіт дорівнюють (Тk — 3σ) і (Тk + 3σ); при Тq< Тk — 3σ імовірність завершення події в заданий термін дорівнює нулю, а при Тq> Тk — 3σ ця імовірність дорівнює одиниці. Отже, має сенс розглядати задачу лише при
Отже, задачу можна сформулювати в такому вигляді: яка імовірність того, що час здійснення завершальної події, то є випадковою величиною а; лежить у межах , тоді
Згідно з даними таблиці значень функції Лапласа одержуємо:
Якщо критичний шлях перевищує заданий директивний термін (для детерміністичних графіків) або мала імовірність успіху (для стохастичних графіків), необхідно коригувати сітковий графік з метою зведення його параметрів згідно із заданими термінами. Процес коригування сіткового графіка іноді називають оптимізацією, вважаючи під цим. послідовне поліпшення сітки з метою досягнення заданого терміну виконання робіт. Існує кілька способів приведення сіткового графіка у відповідність із заданими термінами: зміна часу виконання робіт за рахунок перерозподілу ресурсів, як часових, так і матеріальних; зміна часу виконання робіт за рахунок інтенсифікації виконання робіт критичного шляху (додаткова кількість виконавців, обладнання, матеріальне стимулювання тощо); розподіл робіт та їх сумісність у часі; конструктивна зміна комплексу робіт, зміна графічного зображення внаслідок перегляду технології виконання робіт. Загальний термін виконання робіт слід скорочувати насамперед завдяки зміні тривалості робіт критичного шляху. Це один із найпоширеніших прийомів, оскільки не пов'язаний зі зміною графічного зображення (топології) сітки. Зменшення часових оцінок за критичними роботами забезпечується насамперед за рахунок перекидання відповідних ресурсів (людей, механізмів тощо) з робіт, що мають великі резерви часу. Унаслідок перерозподілу ресурсів тривалість одних робіт зменшується, а інших — збільшується; отже, необхідно знову розрахувати часові параметри сіткового графіка. Якщо внутрішніх ресурсів недостатньо, слід ставити питання про залучення їх зовні. Наприклад, увести другу та третю зміну тощо. Третій спосіб скорочення тривалості виконання робіт — паралельне їх виконання, що досягається розподілом робіт більшої тривалості. У ряді випадків для цього також потрібні додаткові ресурси, наприклад додаткова бригада для паралельного виконання однорідних робіт. Якщо не вдається повною мірою зменшити термін виконання розробки за рахунок формування робіт, то звертаються до зміни графічного зображення (топології) сітки. Це можливо завдяки тому, що окремі роботи можна виконувати різними методами. Багатоваріантна технологія дає змогу відшукати нову послідовність виконання робіт і нові взаємозв'язки. При цьому необхідно повністю виконати всі роботи, пов'язані з побудовою та розрахунком сіткового графіка. Якщо після всіх вжитих заходів щодо скорочення тривалості виконання робіт директивного терміну не досягнуто, цс свідчить про його нереальність і перед вищестоящою організацією ставиться питання про зміну директивного терміну. Визначення можливого терміну виконання всіх робіт, якого можна досягти з імовірністю Р, у цьому разі розглядають як задачу, протилежну тій, що розглянуто раніше. Задаючись бажаною імовірністю Р із рівняння (7.1) можна визначити значення функції і, знаючи Тq і а , підібрати Тk. Раніше вже було коротко розглянуто оптимізацію графіка за часом. Можливі також інші критерії оптимізації: «за вартістю, «час — вартість», «надійність», «завантаженість персоналу» та ін. Таким в загальному вигляді виявляється СПК. Підбиваючи підсумки, слід зупинитися на перевагах і недоліках СПК. Переваги СПК: Наочність зображення. Багато авторів стверджують: якщо з усіх переваг СПК використати лише принцип зображення процесу в вигляді сітки, то й тоді матимемо великий ефект. Можливе використання сітки з будь-яким бажаним ступенем деталізації (у керівника укрупнена сітка, чим нижчий рівень, тим більший ступінь деталізації). Спочатку увага керівників зосереджується на найважливіших ділянках (роботи, що перебувають на критичному шляху), другорядні та мало важливі роботи вилучаються з фокуса уваги керівника. Високий ступінь концентрації управлінських зусиль забезпечує ефективність застосовуваних заходів. Можливість визначення імовірності успіху. 5.Можливість оптимізації робіт, висока динамічність методу. Порівнюючи звичайні методи управління Із сітковим, спеціалісти проводять аналогію з артилерійським снарядом і керованою ракетою. Після вильоту снаряда з дула гармати керувати траєкторією його польоту неможливо. Керована ж ракета може змінювати напрям залежно від змінюваних умов польоту, виявлених помилок прицілювання або переміщення цілі. Такою самою є відмінність між звичайними методами управління та сітковим. Діапазон використання цього методу дуже широкий — будівництво, реконструкція, капітальні ремонти, створення об'єктів нової техніки, організація дослідницьких робіт та ін. Найповніше переваги методу виявляються тоді, коли створюється щось нове, невипробуване, що погребує розв'язання багатьох задач, пов'язаних як одна з одною, так і із загальною метою. Недоліки методу: 1.Складність графічного зображення. Велика кількість кружечків і стрілок може призвести до втрати наочності, тобто однієї з найголовніших переваг методу. 2.Застосування сіткового графіка порушує встановлені організаційні зв'язки (традиції), що склалися па підприємствах чи в організаціях. З.Графік координує і кооперує зусилля всупереч налагодженим стосункам І часто бажанням окремих керівників. 4. Застосування сіткового графіка неможливе без встановлення строгої дисципліни на всіх ділянках запланованого процесу (зменшення ступенів свободи). Найменше відхилення від встановлених правил може призвести до дискредитації цього дуже прогресивного способу планування та управління складними процесами. Саме такими є загальні положення СПК.
ДОДАТОК А СТРУКТУРА МЕРЕЖІ ЗВ'ЯЗКУ Основні поняття теорії графів Теорія графів є розділом математики, що має широкі практичні додатки. Багато проблем, що виникають в таких вельми різних областях знань, як психологія, управління, планування, хімія, електроніка, торгівля, освіта і ін., можуть бути сформульовані як задачі теорії графів. Зважаючи на це теорія графів цікава не тільки сама по собі, але також і тим, що представляє загальну основу, на якій результати, одержані в різних областях знань, можуть бути зібрані, узагальнені і поширені. На відміну від інших наукових дисциплін, теорія графів має цілком певну дату народження. Перша робота по теорії графів, написана математиком Леонардом Ейлером, була опублікована в 1736 р. в працях Академії наук в Санкт-Петербурзі. Ним була сформульована і розв’язана задача про Кенігсбергські мости [3]. До 50-х років нашого століття в теорії графів склалися два цілком різних напрями: алгебраїчний і оптимізаційний. Останній одержав широкий розвиток завдяки появі ЕОМ і у зв'язку з розробкою методів лінійного програмування. У даному навчальному посібнику розглядатимемо оптимізаційний напрям теорії графів. Граф G задається безліччю точок або вершин х1, х2, ..., хn (які позначимо X) і безліччю ліній або ребер (гілок) а1, а2, ...,аm (які позначимо А), об’єднуючих між собою всі або частину цих точок. Таким чином, граф G повністю задається парою (X, А), тобто G =(X, А) [4]. Замість позначень X і А можна використовувати і інші. Якщо ребра з множини А орієнтовані, що звичайно показується стрілкою, то граф називається орієнтованим графом, або орграфом. Ребра орграфа звичайно називають дугами. Орграф приведений на рис. 1.1. Якщо ребра не мають орієнтації, то граф називається неорієнтованим (рисунок 1.2). Граф, що має як орієнтовані так і неорієнтовані ребра, називається змішаним (рис. 1.3). Якщо в графі між двома якими-небудь вершинами є декілька ребер, то такий граф називається мультиграфом (рис. 1.4).
Рисунок 1.1 – Зображення орграфа
Рисунок 1.2 – Зображення неорієнтованого графа
Рисунок 1.3 – Зображення змішаного графа
Рисунок 1.4 – Зображення мультиграфа
Зазвичай вершинам графа приписуються номери (або позначення xi, xj ) щоб розрізняти їх і мати нагоду ними оперувати в процесі аналізу. Ребра графа позначаються звичайно а = (xi, xj), де xi, xj - початкова і кінцева вершини, зв'язані даним ребром. Окрім цього позначення, застосовують також a(xi, xj), або а(i, j), або а i j. Іноді ребро (дугу) позначають (i, j). У використовуваних позначеннях i, j - номери вершин. Крім того, ребра можна позначати аi, де i - номер ребра. Шляхом µ i j графа називається послідовність ребер, що починається у вершині i, закінчується увершині j, у якій кінцева вершина кожного ребра, відмінного від останнього, є початковою вершиною наступного. Так, на рис. 1.5 послідовності дуг а6, а5, а9, а8, а4; а1, а6, а5, а9 є шляхами. Ці послідовності можна також записати у формі:
а(х2, х5), а(х5, x4), а(х4, х3), а(x3, х5), а(х5, х6); а(х1, х2), а(х2, х5), а{х5, х4), а(х4, х3). Більш простішою є наступна форма запису:
а25, а54, а43, а35, а56; а12, а25, а54, а43.
Шлях називається простим, або само непересічним, якщо в ньому не повторюються ні вершини, ні ребра. У розглянутому прикладі другий шлях є простим. Цикл - це шлях, початкова і кінцева вершини якого співпадають. Граф називається зв'язковим, якщо для будь-яких різних вершин існує, принаймні, один сполучаючий їх шлях. У орграфе шлях називають також ланцюгом. Нагадаємо, що граф - це безліч вершин і ребер, позначається G = (X, А). Будь-яка підмножина множини G називається підграфом, позначається =( , ). Дерево графа визначається як зв'язна підмножина , що не містить циклів. Отже, для будь-яких двох вершин графа в дереві існує єдиний шлях, що сполучає їх. У графі, що містить n вершин, підграф із k вершин (k ≤ n) є деревом, якщо виконані будь-які дві з наступних умов: 1) підграф є зв'язковим, 2) підграф не має циклів, 3) число ребер в підграфі рівне k - 1.
Рисунок 1.5 – Зображення послідовності дуг а6, а5, а9, а8, а4; а1, а6, а5, а9 , що є шляхами
Рисунок 1.6 – Зображення графа Остовним деревом, або остовом, називається дерево, що містить всі вершини графа. Отже, якщо граф містить n вершин, то дерево з n вершинами і n - 1 ребром є остовом. Дерево для графа (рис. 1.6) представлене на рис. 1.7, остовне дерево - на рис. 1.8. Тут для спрощення вершини графа позначені номерами, гілки ж не позначені. Їх позначатимемо при необхідності. Помітно, що для графа можна побудувати декілька остовних дерев. Надалі для спрощення, якщо це не обумовлено особо, остовне дерево називатимемо просто деревом.
Рисунок 1.7 – Зображення дерева графа для графа (рис. 1.6)
Рисунок 1.8 – Зображення остовного дерева для графа (рис.1.6)
Якщо для вказівки деяких звичайних обмежень, що накладаються на ребра (дуги) графа, зіставити останнім числа, які називаються вагами ребер, або їх кількісними характеристиками, відповідними, наприклад, відстані, вартості, часу або іншим адитивним величинам, то можна ввести поняття мінімального (або максимального ) дерева. Вага дерева визначається як сума вагів його ребер (звідси і вимога до адитивності характеристик ребер графа). Найкоротшим (максимальним) деревом називається дерево з мінімальною (максимальною) вагою. Іноді таке дерево називають деревом мінімальної (максимальної) вартості.
Дерева і остови визначаються як для орієнтованих, так і для неорієнтованих графів. На рис. 1.9 зображено дерево графа рис. 1.5, на рисунку 1.10 - остов графа рис. 1.5. Січенням (розрізом) графа називається сукупність ребер, при видаленні яких граф розпадається на два незв'язні підграфи. Перетин σst, що розділяє вершини s і t, є безліч ребер (А, ), де s є А , t є . Число С (А, ) називається пропускною спроможністю (величиною) січення. Пропускна спроможність січення визначається як сума пропускних спроможностей ребер, утворюючих січення. На графах січення звичайно позначається лініями, що пересікають ребра, утворюючих січення.
Рисунок 1.11 – Розподіл графа на підграфи січеннями σ1, σ2, σ3
На рис. 1.11 січення σ1 включає ребра (1, 2), (1, 6) і розділяє граф на два підграфи, в одному з яких вершина 1, в іншому - вся решта вершин і ребер. Січення σ2 (ребра (2, 3), (6, 3), (6, 5)) розділяє граф на два підграфи, в одному з яких вершини 1, 2, 6 і ребра (1, 2), (1, 6), в іншому - вершини 3, 4, 5 і ребра (3, 4), (3, 5) і (4, 5). Січення σ3 розділяє граф на два підграфи, в одному з яких вершини 1, 2, 5, 6 і ребра (1, 2), (1, 6),(6, 5), в іншому - вершини 3 і 4 і ребро (3, 4). Модель мережі зв'язку Структура мережі зв'язку, її топологія - це сукупність пунктів (вузлів, станцій і т. д.) і сполучаючих їх ліній (каналів). Для математичного опису структури мережі зв'язку зручно користуватися мережевою моделлю. В якості моделі використовується граф G = (X, А), де X = {хі} - сукупність вершин графа, які ставляться у відповідність пунктам мережі,а А = {аіj} - сукупність ребер графа, які виставляються відповідно лініям зв'язку. Оскільки канали мережі можуть бути односторонніми і двосторонніми, ребра графа можуть бути орієнтованими і неорієнтованими. Таким чином, як модель мережі зв'язку можуть бути використані орієнтовані, неорієнтовані, змішані графи, а також мультиграфи. Мережеві моделі широко використовуються на практиці при проектуванні систем електрозв'язку, систем космічного і радіозв'язку, телетрансляційних мереж, транспортних мереж і т.д. Мережевий аналіз грає все зростаючу роль, оскільки за допомогою мереж (графів) можна досить просто побудувати модель системи. Розширення області використовування мереж пов'язане з тим, що методи мережевого аналізу дозволяють [1]: 1) побудувати модель складної системи як сукупність простих; 2) скласти формальні процедури для визначення якісних і кількісних характеристик системи; 3) вказати механізм взаємодії компонентів системи з метою опису останньої в термінах її основних характеристик; 4) визначити, які дані необхідні для дослідження системи. Основна перевага мережевого підходу полягає у тому, що він може бути успішно застосований до рішення практично будь-якої задачі, коли дослідник володіє необхідними знаннями і здатністю точно побудувати мережеву модель. Матричні представлення графів Для алгебраїчного задання графів зручно користуватися топологічними матрицями і матрицями характеристик ребер графа (гілок мережі). 1.3.1. Топологічні матриці Матриця суміжності. Матриця суміжності (зв'язності) графа G - квадратна матриця А = {аіj} розміру n (n - число вершин графа). Визначається таким чином:
Рисунок 1.12 – Зображення графа матриці суміжності табл. 1.1 Елементи головної діагоналі матриці А звичайно приймаються рівними нулю (аіj = 0), за винятком випадків, коли в деяких вершинах є петлі. Матрицю суміжності графа, зображеного на рис 1.12, має вигляд табл. 1.1. У вершинах 2 і 6 є «петлі», тому відповідні елементи головної діагоналі а22 = 1 і а66=1. Надалі розглядатимемо графи, що не містять «петель» у вершинах.
Таблиця 1.1 – Матриця суміжності графа, зображеного на рис. 1.12
А =
Відзначимо, що матриця А для орієнтованого графа несиметрична щодо головної діагоналі, симетричною вона буде для неорієнтованого графа. Структурна матриця. Для спрощення запису структури і мережі ребрам графа привласнюються позначення, наприклад, а,b, c, ... Ці позначення використовуються як елементи структурної матриці. Структурна матриця графа G - квадратна матриця В = [b іj] розміру n. Визначається таким чином:
Тут х – позначення ребра на графі.
Рисунок 1.13 – Зображення графа структурної матриці В табл. 1.2
Для графа,изображенного на рис 1.13,структурна матриця В представлена в табл. 1.2
Таблиця 1.2–Структурна матриця графа, зображеного на рис. 1.13
В = Крім розглянутих топологічних матриць, можуть бути використані матриці інциденцій «вершини-дуги», «дуги-дуги» [1,4, 5].
1.3.2. Матриці кількісних характеристик ребер графа Для різних кількісних оцінок кожному ребру графа приписується деяка вага - число, що характеризує яку-небудь властивість даного ребра, наприклад, довжину, вартість, пропускну здатність, канальну ємність, час передачі інформації, надійність і т.п. Вказані характеристики ребер графа представляються у формі відповідних квадратних матриць розміру n - довжин, вартостей і т.д. Для побудови, наприклад, матриці довжин L = [l іj] користуються правилом:
Вважаючи, що числа, зображені біля ребер графа рис 1.13, є довжини ребер, матрицю довжин L представимо в табл. 1.3
Таблиця 1.3 – Матриця довжин L 1 2 3 4 5 L =
Таблиця 1.4 – Матриця канальних ємностей С 1 2 3 4 5 С =
Матрицю канальних ємностей ребер С=[с іj] одержують за правилом:
Вважаючи, що числа, вказані біля ребер графа рис. 1.13 є число каналів ребер, відповідну матрицю канальних ємностей С представимо в табл. 1.4. Аналогічно виходять і інші матриці характеристик ребер графа. Якщо G - неорієнтований граф, то всі матриці симетричні щодо головної діагоналі, тобто їх елементи х іj = хji.
|
||||||||
Последнее изменение этой страницы: 2016-06-10 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |