Конспект лекцій з дисципліни «Дослідження операцій»



Сторінка6/12
Дата конвертації11.05.2017
Розмір2.27 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   ...   12

Лекція 5 «Моделі мережевого планування та управління»


Анотація

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


    1. Призначення та сфера використання

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

  • складання календарного плану виконання певного комплексу робіт;

  • оцінку необхідних трудових, матеріальних та фінансових ресурсів, затрат часу;

  • контроль комплексу робіт з прогнозуванням і запобіганням можливих зривів при виконанні робіт;

  • ефективне управління при чіткому розподілі відповідальності між керівниками різних рівнів і виконавцями робіт;

  • оцінку дієздатності та якості системи стосовно певних критеріїв.

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

У цій галузі розглядаються дві задачі стосовно управління мережами: планування робіт з реалізації певного проекту та оцінка пропускної спроможності даної мережі.

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


    1. Основні поняття теорії графів

Побудова математичних моделей розв’язання вказаних задач планування та управління мережами ґрунтується на досліджені попарних (бінарних) зв’язків між об’єктами, які утворюють систему дослідження. Графічне зображення множини досліджуваних об’єктів і зв’язків між ними називається графом. На діаграмі об’єкти ображаються пронумерованими точками або кружками, які називаються вершинами. Однобічний орієнтований відрізок називається дугою, а графічне зображення неорієнтованих попарних зв’язків між об’єктами – ребрами. Граф, вершини якого мають лише однобічні зв’язки, називається орієнтованим, або орграфом.

Приклад графів.

На рис.5.1 зображено схему використання обладнання при запуску бензинового двигуна внутрішнього згоряння (а) та її граф (б).





Рисунок5.1 – Схема використання обладнання при запуску бензинового двигуна внутрішнього згоряння (а) та її граф (б)


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

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

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

Цикл – це ланцюг, початкова вершина якого співпадає з кінцевою.

Шляхом називається орієнтований ланцюг.


    1. Побудова правильної нумерації вершин графа

Правильна нумерація вершин виконується за так званим «алгоритмом викреслення дуг».

Алгоритм опишемо, посилаючись на граф (рис. 5.2), для якого у квадратах наводиться довільна нумерація вершин.


Рисунок5.2 – Алгоритм правильної нумерації вершин графу


Умовно виділимо всі дуги, які виходять з початкової вершини (V00 – вершина нульового рангу). Далі розглядаються вершини, в які не входять інші дуги, окрім викреслених. Такі вершини називають вершинами 1-го рангу та пронумеруємо їх у довільному порядку, дотримуючись неперервності в нумерації. Т.ч. кожній вершині надається два індекси: перший – ранг вершини, другий – її порядковий номер серед множини вершин однакового рангу. Повторюючи даний алгоритм, маємо одну вершину першого рангу (V11), дві вершини другого рангу (V22), та (V23), по одній – третього, четвертого і п’ятого рангу відповідно: (V34), (V45), (V56). Виконавши правильно нумерацію вершин графу, в подальшому індекс рангу вершини можна не вказувати.
5.4 Алгоритм пошуку найкоротшого шляху мережі (графу)

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

Розглянемо реалізацію цього алгоритму на прикладі графу, зображеного на рис.5.2. Згідно з алгоритмом рухаємося від кінцевої вершини V56 до початковоїV00. У кружках, що зображають вершини графу записуємо найкоротшу відстань від вершини (n-1)-го рангу до кінцевої вершини. Одночасно найкоротший шлях від кожної вершини до кінцевої будемо відмічати подвійною стрілкою. У кружку останньої кінцевої вершини 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-го рангу вже знайдено найкоротший шлях до кінцевої вершини. Алгоритм повторюється аж до вершини V00.

Якщо завантаження графу рис. 5.2 тлумачити не як відстань, а як тарифи перевезень вантажу, то ми знайшли шлях найменшої вартості перевезень з вершини V00 до V56.


    1. Побудова графу планування та управління мережею (ПУМ)

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

Основними елементами графіка мережі є поняття події та роботи.

Термін робота використовується у широкому розумінні:


  1. це певна реальна робота, яка потребує затрат матеріальних ресурсів та відповідного терміну виконання;

  2. чекання – процес у часі, який не потребує ніяких матеріальних затрат (затвердіння бетону, висихання фарби);

  3. фіктивна робота – це природний логічний взаємозв’язок між двома або кількома роботами чи їх завершенням, який не потребує затрат праці, матеріальних ресурсів або часу. Термін виконання фіктивної роботи

Подія – це фіксація моменту завершення певного етапу виконання проекту.

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

  2. Завершальна подія не може мати наступних подій та робіт.

  3. Подій, які не визначають термін виконання певної роботи, називають початковою та кінцевою.

Події на графі ПУМ зображають кружками (вершини графу), а роботи – орієнтованими дугами, які показують, які роботи потрібно виконати, щоб відбулася певна подія, та які роботи можна виконувати, якщо подія відбулася. Отже, будь яка робота на графі ПУМ позначається двома подіями, між якими вона знаходиться. Фіктивна робота на графі ПУМ позначається штриховою лінією без зазначення часу. На рис. 5.3 наведено граф, який узагальнено описує комплекс будівельних робіт при спорудженні виробничого комплексу.

І на початку, і по завершені реальної роботи повинна бути лише одна подія, бо роботи ідентифікуються за номерами подій, між якими виконуються, тому на графі введено фіктивні роботи (3; 4) та (5; 4).



Рисунок 5.3 – Граф, що узагальнено описує комплекс будівельних робіт при спорудженні виробничого комплексу


Використовують два принципи побудови графів ПУМ. При реалізації одного з них роботи зображуються дугами, а вершини – подіями, які означають завершення робіт. Це так званий граф «події – роботи». Але використовують й інші підходи до побудови графів ПУМ – без подій. За таким принципом роботи є вершинами графу, а дуги означають залежність між певними роботами в послідовності їх виконання. Побудовані за таким принципом графи ПУМ більш місткі та менш зручні для аналізу та реалізації в ЕОМ. Тому на практиці використовують перший спосіб.

Порядок та правила побудови графів ПУМ.

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

Вимого до побудови графів ПУМ:


  1. Граф ПУМ не повинен мати «глухих кутів», тобто подій, з яких не виходить жодної роботи, окрім завершальної події.



  1. На графові не може бути «хвостових» подій (окрім вихідної водії), тобто подій, яким не передує жодна робота.



  1. Граф не може мати замкнутих контурів і петель, тобто шляхів, які з’єднують певні події з ними ж.



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



  1. На графі ПУМ повинна бути лише одна вихідна і лише одна завершальна події. Якщо це не так (початок реалізації комплексу робіт можна розпочинати паралельно з декількох робіт), то необхідно ввести фіктивні події.

Фіктивні події та роботи можуть вводитися і через інші умови. Однією з таких умов є відображення залежності подій, не пов’язаних з реальними роботами. Наприклад, роботи А та В можуть виконуватись технологічно незалежно одна від одної, але в умовах конкретного виробництва В не може розпочатися раніше, ніж завершиться робота А. Тоді вводиться фіктивна робота С.



Другий випадок – неповна залежність робіт. Наприклад, робота С може бути розпочата лише по завершенні робіт А та В, але робота В – лише по завершенні роботи В і не залежить від роботи А. Тоді необхідно ввести фіктивну роботу F та фіктивну подію 3'.






    1. Упорядкування графу ПУМ, обчислення основних параметрів

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

У залежності від характеру та умов виробництва оцінки визначаються за допомогою методів:



  • з урахуванням продуктивності праці за умови, що такі роботи виконувались раніше за таких же або близьких обставин;

  • за діючими нормами, з урахуванням обсягу роботи, продуктивності праці одного виконавця, кількості працюючих у зміну, кількості змін , тощо;

  • методом експертних оцінок, з використанням оцінок, визначених кожним експертом. Наприклад, терміни виконання роботи обчислюється як середня арифметична термінів, названих кожним експертом;

  • терміни виконання робіт розглядаються як випадкові величини з деякими законами розподілу та відповідними числовими характеристиками: математичним сподіванням та дисперсією.

Найпростішим розподілом є так званий β-розподіл в математичній статистиці.

Для визначення математичного сподівання терміну виконання певної роботи від виконавців та експертів одержують таку інформацію:


Рис. 5.4 – Інформація, необхідна для визначення математичного сподівання терміну виконання певної роботи




  • оптимістичну оцінку tо, тобто термін виконання роботи за найсприятливіших умов;

  • песимістичну оцінку tп, тобто термін виконання роботи за найнесприятливіших умов;

  • найбільш ймовірну оцінку tно терміну виконання роботи

Виходячи з гіпотези про β-розподіл величини терміну виконання певної роботи та використовуючи вказану інформацію, отриману від фахівців, математичне сподівання терміну виконання кожної роботи обчислюється за формулою:

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

    1. Параметри планування й управління мережі за критерієм часу

Шлях – це будь-яка послідовність робіт, якщо кінцева подія кожної роботи є початковою подією наступної роботи.

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

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



Максимальним шляхом між двома подіями «i»та «j» називається шлях від i-ої події до j-ої, який має максимальний термін, тобто сума термінів робіт, які складають такий шлях, є не меншою ніж відповідна сума для довільного шляху від i-ої події до j-ої.

Наприклад, для графу рис. 5.5 завершеними шляхами будуть L1=[2; 6; 7], L2=[4; 5; 7],L3=[3; 6; 7]і т.д.



Рисунок 5.5


Їх терміни: t(L1)=3+5+16=24; t(L2)=8+7+18=33;t(L3)=4+10+16=30. Критичний шлях слід визначати за алгоритмом, описаним у п. 5.2, використовуючи завантаження дуги не пропускною спроможністю, а терміном виконання роботи, що відповідає дузі. Критичний шлях для даного графу,Lкр=[1; 2; 4; 5; 7], а його термін t(Lкр)=3+9+7+18=37.

Критичними роботами будуть: (1; 2), (2; 4), (4; 5), (5; 7).

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

Основні параметри ПУМ за критерієм часу наведені в табл. 5.1.
Таблиця 5.1 – Основні параметри планування й управління мережі


Розглянемо формули обчислення параметрів, вказаних в табл. 5.1.

Результати обчислення параметрів записуються у таблиці на зразок табл.5.2. Якщо граф має велику кількість подій (до двох десятків), то результати можна записувати на графові за схемою, зображеною на рис. 5.6.



Рисунок 5.6 – Схема запису параметрів планування й управління мережі


Розглянемо параметри подій. Певна подія jне може відбутися раніше, ніж завершаться всі роботи, які їй передують. Отже ранній термін tp(j) можливого звершення j-ої події визначається терміном максимального шляху:
(5.1)
Lbj – будь-який шлях, який передує j-й подій, тобто шлях від вихідної до j-ої події).

Якщо подія має кілька шляхів, які їй передують, то ранній термін tp(j) звершення події j зручно обчислювати за формулою:


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

Пізній (або граничний) термін (строк) tn(і) звершення і-ої події обчислюється за формулою:


(5.3)
де Liз - будь-який шляхL віді-ої події до завершальної.

Якщо подія «і» має кілька наступних шляхів, пов’язана з кількома наступними подіями «j», то пізній строк завершення події «і» обчислюється за формулою:


. (5.4)
Резерв часу R(i-ої події обчислюється як різниця пізнього та раннього термінів звершення і-ої події:
. (5.5)
Резерв часу подій показує, на який допустимий термін можна затримати завершення події, не гальмуючи (не збільшуючи) при цьому термін виконання всього комплексу робіт мережі.

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

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

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

Приклад. Обчислити параметри часу подій та критичний шлях графу рис.5.5. Результати наведені в табл. 5.2.
Таблиця 5.2 – Результати розрахунків параметрів подій графу (рис.5.5)


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

Для вихідної вершини і=1 очевидно tp(i)=0. Для і=2 маємо tp(2)=3 бо існує лише одна робота, завершення якої відповідає події 2. З тієї ж причини tp(3)=4. Для обчислення tp(4) скористаємося формулою (5.2) та заданими величинами t(2; 4)=9 таt(1; 4)=8:



.





Отже, термін критичного шляху дорівнює 37 одиницям виміру часу.

При обчислені пізніх термінів здійснення подій tn(i)розглядаємо вершини графу в послідовності зменшення їх нумерації. Для завершальної події пізній термін її завершення дорівнює ранньому, тому tn(7)=37. Пізні терміни інших подій обчислюємо, користуючись формулою (5.4).

, бо для події 6 існує лише один наступний шлях (6; 7).

.

, бо для події 4 існує лише один наступний шлях, який починається з дуги (4; 5).

.

.

.

За формулою (5.5) обчислюємо резерв часу для кожної події: R(1)=0-0=0; R(2)=3-3=0; R(3)=11-4=7; R(4)=12-12=0; R(5)=19-19=0; R(6)=21-19=2; R(7)=37-37=0.

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

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

Наступним кроком буде розрахунок параметрів робіт.

Очевидно, що ранній термін tpn(i, j) початку роботи (i, j) співпадає з раннім терміном здійснення попередньої події і, тому:


. (5.6)
Таким чином, ранній термін tpn(i, j) завершення роботи (i, j) обчислюється так:

. (5.7)
Для того, щоб фактичний термін виконання певної роботи не збільшив час виконання комплексу робіт, повинна виконуватись вимога: кожну роботу слід завершувати не пізніше допустимого терміну її завершальної події j. За так5их умов пізній термін tпз(i, j) завершення роботи (i, j) визначається формулою:
. (5.8)
а пізній термін tnn(i, j) початку цієї роботи – формулою:
. (5.9)
Розглянемо резерви часу шляхів. Такі резерви мають всі некритичні шляхи. Резерв часу Rt(L) шляхуL визначається як різниця термінів критичного та даного шляхів:

. (5.10)
Величина Rt(L) показує на скільки можуть бути збільшені в сумі терміни всіх робіт, які складають шлях L.

Повний резерв Rn(i, j) часу роботи (i, j) обчислюється за формулою:
. (5.11)
На рис. 5.7 показано схему розрахунків параметрів часу стосовно робіт.

Рисунок5.7 – Схема розрахунків параметрів часу стосовно робіт


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

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

Частинним резервом першого виду R1 часу роботи (i, j)є та частина повного резерву часу цієї роботи, на яку можна збільшити термін роботи, не змінивши при цьому пізній термін її початкової події. Цим резервом можна скористатися при виконання певної роботи за умови, що її початкова та завершальні події відбудуться в свої пізні терміни (рис 5.7, б). Величина R(i, j) обчислюється за формулою:

. (5.12)

або


. (5.13)
Частинним резервом другого виду R2 часу роботи (i, j)є та частина повного резерву часу цієї роботи, на яку можна збільшити термін її виконання, не змінивши при цьому ранній термін її початкової події.

Цим резервом можна користуватись при виконанні певної роботи за умови, що початкова та завершальна події відбудуться в свої ранні терміни ( рис. 5.7, в). Величина R2(i, j) обчислюється за формулою:


. (5.14)

або


. (5.15)
Величина R2(i, j) показує, на скільки можна перенести початок або збільшити термін виконання роботи.

Незалежним резервом часу Rnроботи (i, j)є та частина повного резерву часу цієї роботи, яка визначається за умови, що попередні роботи завершуються в пізні терміни, а всі наступні розпочинаються в ранні терміни (рис. 5.7, г).

Величина Rnобчислюється за формулою:
. (5.16)

або


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

Висновки. Частковий резерв першого виду часу роботи може бути використаний на збільшення терміну виконання даної та наступної робіт. Частковий резерв другого виду часу роботи може бути використаний еа збільшення терміну виконання даної та попередніх робіт без зміни резерву часу наступних робіт. Незалежний резерв часу може бути використаний для збільшення терміну виконання лише даної роботи.

Роботи, які складають критичний шлях, та критичні події будь-яких резервів часу не мають. Якщо початкові події і роботи (i, j)належать критичному шляху, то повний резерв часу



. (5.18)
Якщо завершальна подія j роботи (i, j) належить критичному шляху, але сама робота не належить йому, то повний резерв часу визначається так:
. (5.19)
Якщо початкові події і та завершальна подія j належать критичному шляху, але сама робота не належить йому, то повний резерв часу визначається так:
. (5.20)
Формули (5.18) - (5.20) доцільно використовувати для контролю вірності розрахунків резервів темпів виконання окремих робіт.

Обчислимо часові параметри робіт графу ПУМ



Результати розрахунків представлені в табл.5.3


Таблиця 5.3 – Таблиця розрахунків термінів графу


Rn (3; 6) = -2 свідчить про те, що наступну роботу (6; 7) не можна виконати в ранній термін. Аналіз розрахунків показує, що виконання робіт (1; 4), (2; 6), (3; 5), (3; 6), (6; 7) та наступних за будь-якими шляхами може бути затримано на відповідну кількість часу без витрат термінів виконання попередніх робіт, бо величина R2для вказаних робіт більша за нуль.

.



Поділіться з Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   12


База даних захищена авторським правом ©divovo.in.ua 2017
звернутися до адміністрації

войти | регистрация
    Головна сторінка


загрузить материал