Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Аналіз та оптимізація сіткового графіка

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

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

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

У загальному вигляді задача зводиться до визначення імовірності Р потрапляння неперервної випадкової величини х в інтервал (а, 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

Дерева і остови визначаються як для орієнтованих, так і для неорієнтованих графів.

На рис. 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. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...