Рациональные методики пошуку оптимальних шляхів мережевих графіків та його автоматизація на ЭВМ

РефератДопомога в написанніДізнатися вартістьмоєї роботи

Рациональные методики пошуку оптимальних шляхів мережевих графіків та його автоматизація на ЭВМ (реферат, курсова, диплом, контрольна)

Реферат.

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

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

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

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

Постановка задачи.

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

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

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

[pic], (1.1) [pic] - коефіцієнт напруженості найкоротшого шляху; [pic] - тривалість найкоротшого шляху, [pic]; [pic] - тривалість критичного шляху, [pic].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[pic], (2.3) [pic] - резерв часу аналізованого події, [pic]. Резерв часу події показує наскільки можна відстрочити наступ події проти його раннім терміном наступу без зміни загальної тривалості всього проекта.

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

[pic]; (2.4).

[pic], (2.5) [pic] - ранній термін початку, яка з [pic]-го події та яка входить в [pic]-е подія, [pic]; [pic] - ранній термін закінчення даної роботи, [pic]; [pic] - тривалість цієї роботи, [pic]; [pic] - раннє початок події, із якого виходить розглянута робота, [pic];

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

[pic]; (2.6).

[pic], (2.7) [pic] - пізніший строк закінчення роботи, яка з [pic]-го події та що входить у [pic]-е подія, [pic]; [pic] - пізніший строк початку даної роботи, [pic]; [pic] - тривалість цієї роботи, [pic]; [pic] - пізніше закінчення події, до якого входить розглянута робота, [pic].

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

[pic], (2.8) [pic] - повний резерв часу роботи, яка з [pic]-го події та що входить у [pic]-е подія, [pic].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай до роботи, входящеё на незабутню подію 2, повний резерв часу [pic]. Припустимо гидке — серед усіх робіт, що виходять з події 2, немає праці із нульовим повним резервом времени.

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

[pic], чи, відповідно до вираженням (2.8) до повного резерву времени,.

[pic]. (3.1).

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

[pic]. (3.2).

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

[pic], чи, з формули (3.1):

[pic]. (3.3).

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

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

Раціональна методика пошуку критичного шляху мережного графіка: Перегляд мережного графіка ведеться з його початкового події до кінцевого; Зблизька початкового події мережного графіка, як роботи, лежачої на критичному шляху, вибирається та, має нульової повний резерв часу. Відповідно до теоремою 3.1 (утверждение-необходимость), така обов’язково існуватиме; Зблизька робіт, що виходять з події, якого прищепила роботу з нульовим повним резервом часу, вибирається робота, вона має нульової повний резерв часу. Відповідно до теоремою 3.2, така існує; Якщо, серед що виходять з деякого події робіт, кілька робіт з нульовими повними резервами часу, то вибирається будь-яка. У цьому, відповідно до теоремі 3.2, процес побудови критичного шляху до глухий кут зайти неспроможна, і рано чи пізно сягне завершального події мережного графика.

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

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

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

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

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

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

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

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

Автоматизація аналізу оптимальності мережевих графіків на ЭВМ.

1 Уявлення мережного графіка в машинної форме.

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

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

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

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

Правильно побудована матриця смежностей має поруч корисних властивостей: Якщо задатися деяким номером події [pic], то одиниці у відповідній рядку вкажуть на номери подій [pic], із якими подія [pic] з'єднане, що виходять із нього роботами. Це властивість випливає з правила побудови матриці смежностей. Якщо задатися деяким номером події [pic], то одиниці у відповідній стовпці вкажуть на номери подій [pic], із якими подія [pic] з'єднане, які входять у нього роботами. Це властивість, слід з правила побудови матриці смежностей. Якщо деяке подія [pic] вказує одиницями у відповідній рядку матриці смежностей на сполучені з нею події [pic], то номери цих подій [pic] може лише більше номери [pic], зрозуміло з правила присвоєння номерів подій мережного графіка. На цьому властивості слід, що матриця смежностей носить діагональний характер, тобто, одиниці в матриці смежностей можуть бути присутні тільки у верхній діагональної частини матриці (див. рис. 4.1).

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

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

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

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

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

Ця таблиця — є двовимірна матриця з пронумерованими рядками і стовпчиками. Номери рядків змінюються від 0 до [pic] (див. таб. 4.1), де [pic] - число робіт у мережному графіці, що можна знайти, підрахувавши все одиниці в матриці смежностей. Номери шпальт змінюються від 0 до 13, де кожен номер відповідає своєму параметру мережного графіка. Нумерація рядків і шпальт необхідна до подання таблиці вихідних даних, і результатів в машинної форме.

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

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

Блок-схема 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, в таблиці вихідних даних, і результатів [pic] вже сьогодні перебувають коди робіт мережного графіку й їх тривалості. Блок-схема 4.3 — Алгоритм розрахунку ранніх термінів звершення подій мережного графика.

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

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

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

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

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

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

Із даної теореми, безпосередньо, слід алгоритм розрахунку параметрів мережного графіка другого етапу. Цей алгоритм представлено вигляді блок-схемы 4.4, і грунтується у тому, що дозволить після виконання алгоритму 4.3, в таблиці вихідних даних, і результатів [pic] вже розраховані все ранні терміни звершення событий.

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

Список використаних источников.

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

———————————;

[pic].

. 2.1 — Приклад мережного графика.

. 3.1 — Поясняющий малюнок до Теоремі 3.2.

[pic].

— 3.

— 4.

— 6.

— 9.

— 7.

— 5.

— 6.

— 1.

— 3.

[pic].

. 3.2 — Приклад мережного графіка при негативних длительностях работ.

С0.

С1.

С2.

С3.

С4.

С5.

С6.

С7.

С0.

С1.

С2.

С3.

С4.

С5.

С6.

С7.

. 4.1 — Матриця смежностей мережного графика.

Ci.

Cj.

Фіктивна работа.

. 4.2 — Приклад розриву паралельних работ.

Верно.

Неверно.

Начало.

Матриця смежностей вже задана.

i:=0 j:=0.

Mi j 0.

Помилка у структурі графика.

Err:=1.

Err=1 — Помилка у структурі; Err=0 -Помилок нет.

Да.

Нет.

j:=j+1.

j > i.

Да.

Нет.

j:=0 i:=i+1.

і < p.

Нет.

Err:=0.

p — Кількість подій не графике.

У структурі помилок нет.

Конец.

Да.

Таблиця 4.1 — Таблиця вихідних даних, і результатов.

| |Код |Параметри робіт і подій | | |робіт| | | |и | | | |і |j |[pi|[pic|[pi|[pic|[pic|[pic|[pic|[pic|[pic|[pi|[pi|[p| | | | |з] |] |з] |] |] |] |] |] |] |з] |з] |ic| | | | | | | | | | | | | | | |] | | |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |12 |13| |0 | | | | | | | | | | | | | | | |1 | | | | | | | | | | | | | | |.

|k-1 | | | | | | | | | | | | | | |.

N строки.

N Столбца.

Начало.

і := 0 j := 1 p. s := 0.

Mi j = 1.

Нет.

Да.

As 0 := i.

As 1 := j.

As 2 := ti j.

ti j.

Ввод оператором тривалості роботи з кодом i-j.

p.s := s+1.

j:= j+1.

j? p.

Нет.

Да.

і:= i+1 j:=i+1.

і < p-1.

Нет.

Да.

Конец.

p — Кількість подій не графике.

Да.

Нет.

з > 0.

з:= c-1.

p.s:= 0.

max:= As 9.

Да.

Нет.

max.

Цикл пошуку максимального з ранніх закінчень робіт, які входять у i-е событие.

Да.

Нет.

As 1= i.

-? — Мінімально можливе машинне число з — Лічильник двох циклів заповнення осередків A p. s 5 табл. вихідних даних, і результатов.

max:= -? з:= 2.

p -Кількість событий.

Да.

Нет.

і < p.

і:= i+1.

k — Кількість рядків таблиці вихідних даних, і результатов.

Да.

Нет.

p.s < k.

p.s := s+1.

As 3:= max.

As 7:= max.

As 9:= max+As 2.

Цикл розрахунку ранніх закінчень робіт, що виходять з i-го события.

Да.

Нет.

As 0 = i.

s:=0.

max — Зберігає ранній термін звершення поточного события.

max:= 0 і:= 0.

Начало.

Да.

Нет.

p.s < k.

p.s := s+1.

As 5:= max.

Конец.

Цикл пошуку мінімального з пізніх почав робіт, що виходять з j-го события.

min:= As 8.

Да.

Нет.

min > As 8.

Да.

Нет.

As 0 = j.

p.s:= s-1.

p.s:= k.

+? — Максимально можливе машинне число з — Лічильник двох циклів заповнення осередків As 4 табл. вихідних даних, і результатов.

min:= +? з:= 2.

Конец.

Да.

Нет.

j < 0.

j:= j-1.

Да.

Нет.

p.s > 0.

As 6:= min.

As 10:= min.

As 8:= min-As 2.

Да Цикл розрахунку пізніх почав робіт, які входять у j-е событие.

Нет.

As 1 = j.

p.s:= p. s -1.

s:=k.

min — Зберігає пізніший строк звершення поточного события.

min:= Ak-1, 5 j:= p-1.

Начало.

k — Кількість рядків таблиці вихідних даних, і результатов.

As 4:= min.

Да.

Нет.

p.s > 0.

Да.

Нет.

з > 0.

з:= c-1.

s:=0.

Начало.

As 11:= As 10 — As 9.

As 12:= As 5 — As 9.

As 13:= As 4 — As 3.

p.s:= p. s +1.

Да.

Нет.

p.s < k.

Конец.

і:= 0.

Начало.

p.s:= 0.

Да.

Нет.

і < p — 1.

Да.

Нет.

As 0 = i.

Да.

Нет.

As 11 = 0.

Висновок коду роботи особливого пути:

< і, As 1 >

і:= As 1.

p.s:= s+1.

Конец.

Показати весь текст

Заповнити форму поточною роботою