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


  • Дата конвертації27.03.2017
    Розмір55.22 Kb.
    Типреферат

    Скачати 55.22 Kb.

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

    реферат

    Курсовий проект 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 Теоретичні основи мережевого планування

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

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

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

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

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

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

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

    -


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

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

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

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

    , (2.1)

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

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

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

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

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

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

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

    , (2.2)

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

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

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

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

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

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

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

    , (2.3)

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

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

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

    ; (2.4)

    , (2.5)

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

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

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

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

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

    ; (2.6)

    , (2.7)

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

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

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

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

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

    , (2.8)

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

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

    , (2.9)

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


    Нехай для роботи, входящеё на незабутню подію 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 залишається інша можлива ситуація - хоча б одна з них має також нульовий повний резерв часу. Теорема доведена.

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

    -


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

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

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

    -


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

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

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

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

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



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

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

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

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

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

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



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


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

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

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

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

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

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

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

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


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




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

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

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

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

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

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

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


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




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

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


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

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

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

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

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

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


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

    висновок

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

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

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

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

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


    Головна сторінка


        Головна сторінка



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

    Скачати 55.22 Kb.