Мережеве подання програми (мережева модель)

Хмельницький 2008

Дослідження операцій. Методичні вказівки до курсової роботи для студентів напряму навчання “Економічна кібернетика” / П.М. Григорук, О.В. Манталюк. – Хмельницький: ХНУ, 2008. – 41 с.

ЗМІСТ

ВСТУП

1. ТЕОРЕТИЧНІ ВІДОМОСТІ ПРО КАЛЕНДАРНЕ ПЛАНУВАННЯ
2. ПОБУДОВА МОДЕЛІ ТА РОЗРАХУНОК ЇЇ ПАРАМЕТРІВ.
3. ЗАВДАННЯ КУРСОВОЇ РОБОТИ.

ВСТУП

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

Організаційне управління програмами стало новою областю теоре­тичних і прикладних досліджень завдяки розробці двох аналітичних методів структурного і календарного планування, а також оперативного управління програмами. Ці методи, розроблені майже одночасно в 1956–1958 рр. двома різним групами, одержали назви “Метод критичного шляху” (МКШ) і “Ме­тод оцінки і перегляду програм” (ПЕРТ).

Метод критичного шляху був запропонований фірмою Е.I. du Ропt dе Nemours & Соmраny для управління програмами будівництва, а потім був розвинутий і узагальнений фірмою Маuсhlу Аssосіаtеs. Метод ПЕРТ розроб­лений консультативною фірмою за замовленням військово-морського мініс­терства США для календарного планування науково-дослідних і дослідно-конструкторських робіт програми створення ракет “Поларис”.

Обидва методи в кінцевому рахунку визначають календарний план виконання програми. Хоча ці методи були розроблені незалежно, вони вра­жаюче подібні один до одного. Найістотнішою відмінністю спочатку було те, що в методі МКШ оцінки тривалості операцій передбачалися детермінова­ни­ми величинами, а в методі ПЕРТ – випадковими. В даний час обидва методи складають єдиний метод планування і управління мережами (ПУМ).

ТЕОРЕТИЧНІ ВІДОМОСТІ ПРО КАЛЕНДАРНЕ ПЛАНУВАННЯ

1.1. Загальні відомості про методи календарного планування

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

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

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

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

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

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

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

Планування і управління мережами включає три основних етапи: структурне планування, календарне планування й оперативне управління.

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

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

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

Мережеве подання програми (мережева модель)

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

Мережева модель відображає взаємозв’язки між операціями і поря­док їх виконання (відношення упорядкування або наступності). Як правило, для представлення операції використовується стрілка (орієнтована дуга), напрямок якої відповідає процесу реалізації програми в часі. Відношення упорядкування між операціями задається за допомогою подій. Подія визна­чається як момент часу, коли завершуються одні операції і починаються інші. Початкова і кінцева точки будь-якої операції описуються, таким чином, па­рою подій, що зазвичай називають початковою подією і кінцевою подією. Операції, що виходять з деякої події, не можуть початися, поки не будуть до­вершені всі операції, що входять у цю подію. За прийнятою термінологією, кожна операція відображається орієнтованою дугою, а кожна подія – вузлом (вершиною). Довжина дуги ніяким чином не пов’язана з тривалістю операції, а графічне зображення дуг необов’язково має являти собою прямолінійний відрізок.

а)

б)

Рис. 1.1

На рис. 1.1, а) наведений типовий приклад графічного зображення операції i, j з початковою подією i та кінцевою подією j. На рис. 1.1, б) показаний інший приклад, з якого видно, що для можливості початку опе­рації (3, 4) потрібне завершення операцій (1, 3) і (2, 3). Протікання операцій у часі задається шляхом нумерації подій, причому номер початкової події завжди менший за номер кінцевої. Такий спосіб нумерації є особливо зруч­ним при виконанні обчислень на ЕОМ.

Побудова математичних моделей розв’язання вказаних задач плану­вання та управління мережами ґрунтується на дослідженні попарних (бінар­них) зв’язків між об’єктами, які утворюють систему дослідження. Графічне зображення множини досліджуваних об’єктів і зв’язків між ними називається графом. Граф доцільно зображати у вигляді діаграми. На діаграмі об’єкти зображуються пронумерованими точками або кружками, які називаються вершинами, зв’язки між об’єктами-відрізками ліній, які з’єднують відповідні об’єкти. Якщо зв’язок між двома об’єктами А та В однобічний, тобто від А до В є зв’язок, а зворотний зв’язок відсутній, то це зображується орієнто­ваним відрізком, стрілка якого відповідає напрямку зв’язку. Такий одноріч­ний орієнтований відрізок називається дугою. Графічне зображення неорієн­тованих попарних зв’язків між об’єктами називається ребрами. У подаль­шому ми не будемо в термінології відрізняти поняття графу та його діаграми. Граф, вершини якого мають лише однобічний зв’язки, називається орієнто­ваним або орграфом.

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

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

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

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

Шляхом називається орієнтований ланцюг. Отже, поняття “шлях” стосується лише орієнтованих графів.

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

Основними елементами графіка мережі є поняття роботи та події. Термін роботавикористовується в системі ПУМ у широкому розумінні.

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

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

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

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

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