трусики женские украина

На головну

 Раціональні методики пошуку оптимальних шляхів мережевих графіків і їх автоматизація на ЕОМ - Економіко-математичне моделювання

Реферат

Курсовий проект 43 с., 5 рис., 6 блок-схем, 1 таблиця, 1 джерело.

СЕТЕВОЙ ГРАФІК, АНАЛІЗ ОПТЕМАЛЬНОСТІ мережевий графік, раціональної методики ПОШУКУ ОСОБЛИВИХ ШЛЯХІВ мережевий графік, АВТОМАТИЗАЦІЯ АНАЛІЗУ мережевий графік НА ЕОМ.

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

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

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

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

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

Зміст

Введення 4

1 Постановка завдання 6

2 Теоретичні основи мережевого планування 9

3 Обгрунтування раціональних методик пошуку особливих шляхів мережевих графіків 15

4 Автоматизація аналізу оптимальності мережевих графіків на ЕОМ 22

4.1 Подання мережного графіка в машинної формі 22

4.2 Автоматизація розрахунку параметрів мережного графіка 27

4.3 Автоматизація процесу пошуку особливих шляхів мережного графіка 40

Висновок 42

Список використаних джерел 43

Введення

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

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

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

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

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

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

Інакше йде справа з завданням аналізу оптимальності вже готового мережного графіка. Треба сказати, що з цим завданням економіст-проектувальник стикається систематично при оптимізації мережного графіка по тривалості, коли кожне чергове прийняте рішення про перерозподіл трудових ресурсів вимагає перевірки на досягнення оптимального варіанту. Очевидно, що якщо автоматизувати процес вирішення розглянутої задачі, то це істотно знизить тривалість розробки мережевого графіка, а значить і витрати на мережеве планування в цілому. Так ось, завдання аналізу оптимальності мережного графіка математично формализуема і, з деякими труднощами, вирішувана на ЕОМ. В даному курсовому проекті, якраз і будуть запропоновані й обґрунтовані раціональні методики рішення задачі аналізу оптимальності мережевих графіків, легко автоматизує на ЕВМ.1Постановка завдання

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

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

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

, (1.1)

- Коефіцієнт напруженості найкоротшого шляху;

- Тривалість найкоротшого шляху ,;

- Тривалість критичного шляху ,.

З критерію (1.1) випливає, що деякий аналізований мережевий графік приймається оптимальним, якщо відношення тривалості його найкоротшого шляху до тривалості його критичного шляху не менше 0.7, або, що теж саме, якщо тривалість найкоротшого шляху відрізняється від тривалості критичного шляху не більше ніж на 30 %.

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

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

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

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

Отже, мережевий графік - є математична модель упорядкування проектних робіт типу "Сигнальний граф" (див. Приклад на ріс.Error: Reference source not found). Будь сигнальний граф складається тільки з двох елементів: дуг і вершин. У контексті мережевого планування, дугами є окремі роботи, зображувані на мережевому графіку у вигляді стрілок так, що почала стрілок, відповідає засадам виконання робіт, кінці стрілок - їх завершення. Вершинами сигнального графа є так звані події, які зображуються на мережному графіці як гуртків, з порядковими номерами в нижніх квадрантах. Якраз події мережного графіка і служать для цілей упорядкування проектних робіт, яке полягає в тому, що виходить із деякого події робота не може початися, поки не завершаться всі вхідні в нього роботи.

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

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

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

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

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

р

анніе та пізні терміни настання подій;

ранні та пізні терміни початку і закінчення робіт;

резерви часу робіт і подій.

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

, (2.1)

- Ранній термін настання аналізованого події ,;

- Номер аналізованого події;

- Номери попередніх подій, з'єднаних з даним роботами;

- Ранній термін настання-го попереднього події ,;

- Тривалість роботи, що з'єднує-е попереднє подія з даним ,.

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

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

, (2.2)

- Пізній термін настання аналізованого події ,;

- Номер аналізованого події;

- Номери наступних подій, сполучених з даним роботами;

- Пізній термін настання-го подальшого події ,;

- Тривалість роботи, що з'єднує-е наступне подія з даним ,.

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

Знаючи ранній і пізній терміни настання події, можна визначити резерв часу події:

, (2.3)

- Резерв часу аналізованого події ,.

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

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

; (2.4)

, (2.5)

- Ранній термін початку роботи, яка з-го події та що входить в-е подія ,;

- Ранній термін закінчення даної роботи ,;

- Тривалість цієї роботи ,;

- Ранній початок події, з якого виходить розглянута робота ,;

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

; (2.6)

, (2.7)

- Пізній термін закінчення роботи, яка з-го події та що входить в-е подія ,;

- Пізній термін початку даної роботи ,;

- Тривалість цієї роботи ,;

- Пізніше закінчення події, в яке входить розглянута робота ,.

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

, (2.8)

- Повний резерв часу роботи, яка з-го події та що входить в-е подія ,.

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

, (2.9)

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

Як приклад, який буде потрібно і надалі, основні розглянуті параметри мережного графіка розраховані для випадку, представленого на малюнку Error: Reference source not found. Тут, тривалості робіт, що є вихідними даними для розрахунку, обрані довільним чином. Параметри робіт позначені відповідними символами біля стрілок. Параметри подій відображені в трьох квадрантах відповідних гуртків. У лівих квадрантах відбиті значення ранніх термінів звершення подій. У правих - значення пізніх термінів звершення подій. У верхніх - значення резервів часу подій.

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

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

Почнемо з докази методики пошуку критичного шляху мережного графіка. Для цього розглянемо ряд допоміжних теорем.

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

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

Доведемо це твердження методом від протилежного.

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

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

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

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

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

Для доказу даної теореми розглянемо узагальнений приклад на малюнку Error: Reference source not found, де, з метою зручності, подій присвоєні умовні номери.

Доведемо теорему методом від протилежного.

П

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

Для початку знайдемо, чому дорівнює пізній термін звершення події 2. Він, відповідно до формули (2.2), визначається як мінімальний час пізнього початку роботи серед всіх робіт, що виходять з аналізованого події. Нехай пізній термін звершення події 2 дорівнює пізнього початку роботи, що входить, наприклад, в подія 4:

,

або, у відповідності з виразом (2.8) для повного резерву часу,

. (3.1)

Тепер розглянемо, яке може мати значення повний резерв часу роботи, яка з події 1 і що входить у подія 2. Відповідно до формули (2.8):

. (3.2)

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

,

або, виходячи з формули (3.1):

. (3.3)

Оскільки ми припустили від протилежного, що серед усіх виходять з події 2 робіт немає робіт із нульовим повним резервом часу, то звідси відразу випливає, що і робота, яка виходить із події 1 і що входить у подія 2, також не може мати нульовий повний резерв часу, вже якщо його мінімальне значення завідомо нерівно нулю, відповідно до отриманим рівністю (3.3). Останнє суперечить умові теореми. З цієї суперечності випливає те, що неможлива ситуація, коли при нульовому резерві часу роботи, що входить в подія 2, всі вихідні з цієї події роботи мали б ненульові резерви часу. Якби це мало місце, то відповідно до приведеним доказом, робота, входить у подія 2 також б мала ненульовий повний резерв часу. Але ж це не так за умовою теореми. Тоді для робіт, що виходять з події 2 залишається інша можлива ситуація - хоча б одна з них має також нульової повний резерв часу. Теорема доведена.

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

Раціональна методика пошуку критичного шляху мережного графіка:

Перегляд мережного графіка ведеться від його початкового події до кінцевого;

При розгляді початкового події мережного графіка, як роботи, що лежить на критичному шляху, вибирається та, яка має нульовий повний резерв часу. Відповідно до теореми 3.1 (затвердження-необхідність), така робота обов'язково буде існувати;

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

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

Реалізація зазначених правил дає шлях, що складається тільки з робіт з нульовими повними резервами часу. Тоді, на підставі теореми 3.1 (затвердження-достатність), цей шлях і буде критичним.

З метою перевірки, доведена методика застосована для мережевого графіка, представленого на малюнку Error: Reference source not found. Тут, знайдені критичні шляху, виділено жирними стрілками. Як видно, таких шляхів два, завдяки тому, що серед робіт, що виходять з події 0, є дві роботи з нульовими повними резервами часу. Перевірити те, що знайдені шляхи є критичними легко, підсумувавши тривалості належних їм робіт. Суми виявляться: по-перше, рівними між собою, а по-друге, найбільшими серед аналогічних сум інших можливих шляхів.

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

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

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

Для перевірки доведеною теореми, параметри мережного графіка малюнку Error: Reference source not foundпересчітани заново, при негативних значеннях тривалостей робіт, і представлені на малюнку Error: Reference source not found. Як видно, мережевий графік на малюнку Error: Reference source not foundсодержіт шлях, роботи якого мають тільки нульові повні резерви часу. Даний шлях виділений масними стрілками. Цей шлях, будучи критичним для мережного графіка малюнку Error: Reference source not found, в теж час є найліпшим шляхом для мережного графіка малюнку Error: Reference source not found. Останнє можна перевірити простим підсумовуванням тривалостей його робіт. Отримана сума повинна бути найменшою за абсолютним значенням, серед аналогічних сум інших шляхів мережного графіка малюнку Error: Reference source not found.

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

Н

еобходимо сказати, що можна поставити і вирішити спільне завдання пошуку шляху заданої тривалості. Але дана задача принципової важливості, при аналізі мережевого графіка, не несе. Для аналізу оптимальності мережного графіка і здійснення його оптимізації, досить знати лише, як проходять особливі шляху, і яка їхня тривалість. Відповіді на ці питання і дають раціональні методики пошуку особливих шляхів, доведені в цьому разделе.4Автоматізація аналізу оптимальності мережевих графіків на ЕОМ 4.1Представленіе мережевого графіка в машинної формі

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

Найбільш зручний спосіб представлення структури мережевого графіка в машинної формі, заснований на понятті матриці смежностей. Приклад даної матриці для структури мережного графіка малюнку Error: Reference source not foundпредставлен на малюнку Error: Reference source not found.

Матриця смежностей квадратна і має розмірність, де- число подій мережевого графіка. Номери рядків матриці задаються номерами подій, з яких роботи мережного графіка виходять, номери шпальт матриці задаються номерами подій, в які роботи мережевого графіка входять. На перетині рядка і стовпця, в матриці смежностей, може бути тільки одне з двох значень: 0 або 1. Якщо, то це означає, що на мережевому графіку існує робота, яка виходить із події з номеромі входить у подія з номером. Якщо, то такої роботи на мережевому графіку немає.

Матриця смежностей буде вірно відображати структуру мережевого графіка, якщо мережевий графік побудований за всім, узаконеним стандартом правилам. Тут, найбільш важливі наступні:

С

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

Дві події мережного графіка може з'єднувати лише одна робота. Якщо все ж має місце факт з'єднання двох подій кількома роботами, то, для виконання зазначеного правила, необхідно ввести додаткові події, що розривають зайві роботи і доповнюють їх фіктивними роботами з нульовою тривалістю (див. Приклад на рис. Error: Reference source not found). Додаткові події також повинні мати свої унікальні, в мережевому графіку, номери, присвоєні їм відповідно до першим правилом.

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

Е

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

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

Якщо деякий собитіеуказивает одиницями у відповідній рядку матриці смежностей на з'єднані з ним події, то номери цих собитіймогут бути тільки більше номери, що зрозуміло з правила присвоєння номерів подіям мережевого графіка. З цієї властивості випливає, що матриця смежностей носить діагональний характер, тобто, одиниці в матриці смежностей можуть бути присутніми тільки у верхній діагональної частини матриці (див. Рис. Error: Reference source not found).

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

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

Б

лок-схема 4. - Алгоритм тестування матриці смежностей

4.2Автоматізація розрахунку параметрів мережного графіка

Аналіз оптимальності мережного графіка можливо провести, тільки після розрахунку всіх, властивих йому параметрів. Вихідними даними для розрахунку є тривалості всіх, що входять в мережевий графік робіт. Результатами розрахунку є значення, описаних у розділі 2, параметрів. І перше і друге, можна об'єднати в одній таблиці вихідних даних і результатів Error: Reference source not found.

Дана таблиця - є двовимірна матриця з пронумерованими рядками і стовпцями. Номери рядків змінюються від 0 до (див. Таб. Error: Reference source not found), де- число робіт в мережевому графіку, яке можна знайти, підрахувавши всі одиниці в матриці смежностей. Номери стовпців змінюються від 0 до 13, де кожен номер відповідає своєму параметру мережного графіка. Нумерація рядків і стовпців необхідна для подання таблиці вихідних даних і результатів в машинної формі.

Стовпці під номерами 0,1 і 2 визначають частина таблиці Error: Reference source not found, відведену під зберігання вихідних даних, до яких відносяться коди робіт і тривалості робіт. Як видно, коди робіт задаються осередками двох стовпців під номерами 0 і 1. Тут індекс (стовпець 0) визначає номер події, з яких робота виходить, а індекс (стовпець 1) визначає номер події, в якому вона входить. Знайти всі можливі коди робіт мережного графіка легко по матриці смежностей, якщо, переглядаючи її рядки, номери яких відповідають індексу, вибирати в якості індексаномера тих стовпців, для яких будуть відшукувати одиниці.

Алгоритм заповнення таблиці Error: Reference source not foundісходнимі даними представлений у вигляді блок-схеми 4., де осередки самої таблиці позначені символом. Для даного позначення: - номер рядка таблиці вихідних даних і результатів, - номер стовпчика тієї ж таблиці. Алгоритм передбачає, що таблиця вихідних даних і результатовуже зарезервована і має розмірність, - число робіт в мережевому графіку.

Блок-схема 4. - Алгоритм заповнення вихідними даними таблиці вихідних даних і результатів

Після заповнення таблиці Error: Reference source not foundісходнимі для розрахунку, йде наступна стадія, - безпосередньо, сам розрахунок параметрів мережного графіка. Дана стадія виконується в три етапи. На першому етапі здійснюється розрахунок мережного графіка в порядку - від початкового події до завершального, і визначаються ранні терміни звершення подій, ранні початку і закінчення робіт. На другому етапі здійснюється розрахунок мережного графіка в зворотному порядку - від завершального події до початкового, і визначаються пізні терміни звершення подій, пізні початку і закінчення робіт. На третьому етапі здійснюється розрахунок резервів часу подій та робіт, в довільному порядку.

Розглянемо розрахунок параметрів мережного графіка на першому етапі.

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

Теорема 4.1 - Якщо події мережного графіка пронумеровані так, що будь-яка його робота виходить з події з меншим номером і входить в подія з великим номером, то розрахунок ранніх термінів звершення подій у порядку: 0-е подія, 1-е, 2-е, і так далі, до завершального події, у безвихідь зайти не може, за умови, що розраховуючи ранній термін звершення чергового події, відразу ж визначаються ранні закінчення всіх, що виходять з нього робіт.

Доведемо цю теорему методом математичної індукції.

Задамося нульовим терміном звершення 0-го події, і розрахуємо ранні закінчення всіх, що виходять з нього робіт. Далі. Розглянемо 1-е подія. У нього можуть входити тільки роботи, які виходять з подій з меншими номерами - в даному випадку тільки з 0-го події, при цьому ранні закінчення цих робіт вже відомі. Тоді можна розрахувати ранній термін звершення 1-го події. Розрахувавши ранній термін звершення 1-го події, відразу ж розрахуємо ранні закінчення всіх, що виходять з нього робіт. Далі. Розглянемо 2-е подія. У нього можуть входити роботи, тільки з 0-го і 1-го події, і ранні закінчення яких вже відомі. Тоді можемо розрахувати ранній термін звершення 2-го події. Розрахувавши ранній термін звершення 2-го події, відразу ж розрахуємо ранні закінчення всіх, що виходять з нього робіт. Далі. Розглянемо третє подія. У нього можуть входити роботи, тільки з 0-го, 1-го і 2-го події, і ранні закінчення яких вже відомі. Тоді можемо розрахувати ранній термін звершення 3-го події ....

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

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

Блок-схема 4. - Алгоритм розрахунку ранніх термінів звершення подій мережевого графіка

Розглянемо розрахунок параметрів мережного графіка на другому етапі.

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

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

Доведемо цю теорему методом математичної індукції.

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

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

З даної теореми, безпосередньо, слід алгоритм розрахунку параметрів мережного графіка на другому етапі. Даний алгоритм представлений у вигляді блок-схеми 4., і заснований на тому, що після виконання алгоритму 4., в таблиці вихідних даних і результатовуже розраховані всі ранні терміни звершення подій.

Блок-схема 4. - Алгоритм розрахунку пізніх термінів звершення подій мережевого графіка

Розглянемо розрахунок параметрів мережного графіка на третьому етапі.

Якщо, спочатку виконати алгоритм розрахунку ранніх термінів звершення подій 4., а потім алгоритм розрахунку пізніх термінів звершення 4., то в таблиці вихідних даних і результатів залишаться незаповненими тільки три останніх шпальти, з номерами: 11, 12 і 13. Дані стовпці, як видно з таблиці Error: Reference source not found, відведені під розрахунок резервів часу мережного графіка. Розрахунок резервів часу мережного графіка можна здійснити в будь-якому порядку рядків таблиці вихідних даних і результатів, наприклад, поспіль - з 0-й рядки по останню. Такий порядок розрахунку представлений нижче, у вигляді блок-схеми 4.. Даний алгоритм є завершальним для процесу розрахунку параметрів мережного графіка, після виконання якого, всі елементи таблиці вихідних даних і результатів Error: Reference source not found, будуть заповнені значеннями відповідних параметрів.

Блок-схема 4. - Алгоритм розрахунку резервів часу мережного графіка

4.3Автоматізація процесу пошуку особливих шляхів мережного графіка

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

З розділу 3 ясно, що для пошуку, і критичного шляху і найліпшого, можливо використовувати одну й ту ж саму методику. Дана методика полягає в послідовному виборі, від 0-го події до завершального, тих робіт, які мають нульові повні резерви часу. У випадку, якщо параметри мережного графіка розраховувалися для позитивних тривалостей, назв робіт, то зазначена методика дає критичний шлях мережного графіка. Якщо ж параметри розраховувалися при негативних длительностях робіт, то методика дасть найкоротший шлях мережного графіка.

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

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

Блок-схема 4. - Алгоритм пошуку особливого шляху мережного графіка

Висновок

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

Крім того, в курсовому проекті були розглянуті питання автоматизації на ЕОМ раціональних методик пошуку особливих шляхів мережного графіка. В результаті - розроблені блок схеми алгоритмів розрахунку параметрів мережевих графіків і пошуку їх особливих шляхів, які передбачається використовувати при створенні конкретної програми аналізу оптимальності мережевих графіків на будь-якому з відомих мовах програмування.

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

Список використаних джерел

Техніко-економічне обґрунтування дипломних проектів проектів: Учеб. Посібник для втузів / Л. А. Астреіна, В. В. Балдесов, В. К. Беклешов та ін .; Під ред. В. К. Беклешова. - М .: Вища. Шк., 1991. - 176 c .: іл.

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка