Мережеві методи у плануванні

[pic].

Кафедра прикладної математики.

Курсова робота з курсу:

«Дискретна математика».

по теме:

«Мережні методи в планировании».

Група: ДІ 102.

Студент: Шеломанов Р.Б.

Керівник: Алфьорова З.В.

Москва 1998.

Содеражание.

Запровадження 3.

Частина 1 Теоретична частина до курсовому проекту 4.

Глава 1 Теорія графів 4.

Глава 2 Календарне планування мережними методами 8.

Частина 2 Практична реалізація курсового проекту 13.

Завдання 13.

Рішення 14.

Укладання 20.

Список літератури 21.

Для ілюстрацій умов і рішень багатьох завдань люди користуються графіками. За своєю суттю графіки є набором з багатьох крапок і відрізків прямих що з'єднують ці точки. Постає питання: підпорядковуються чи графіки будь-яким законам й володіють вони якимись властивостями? Це запитання поставлений Д. Кенігом, що об'єднав все схематичні зображення, які з сукупності крапок і ліній, загальним терміном «граф» і розглянув граф як математичний об'єкт. Теорія графів набула свого використання у рішенні цілого ряду економічних завдань. Цю область докладання теорії графів може бути: «Календарне планування програм мережними методами». Вивчення цієї області є основним метою мого курсового проекту. Програма визначає сукупність взаємозалежних операцій які необхідні у порядку, аби досягти поставленої у програмі мети. Операції логічно упорядковані тому, що навколо лише операції не можна розпочати, як ні завершено інші. Операція програми зазвичай сприймається як робота, до виконання якої потрібні витрати часу й ресурсів. Зазвичай, сукупність операцій програми не повторюється. До появи мережевих методів календарне планування програм (т. е. планування у часі) здійснювалося у невеликий обсяг. Найбільш знаним засобом такого планування був стрічковий (лінійний) графік Ганта, задававший терміни початку будівництва і закінчення кожну операцію на горизонтальній шкалою часу. Його недолік полягає у цьому, що не дозволяв відновити залежності між різними операціями (що визначають значною мірою темпи реалізацію програми). У зв’язки Польщі з підвищенням складності сучасних програм знадобилася розробка більш чітких і найефективніших методів планування, які забезпечують оптимізацію всього процесу здійснення програми. У цьому ефективність інтерпретується як мінімізація тривалості виконання програми з урахуванням економічних чинників використання наявних. Організаційне управління програмами стало новою сферою теоретичних і прикладних досліджень завдяки розробці двох аналітичних методів структурного і календарного планування, і навіть оперативно керувати програмами. Ці методи, розроблені майже одночасно у 1957;1958 рр. двома різноманітними групами, отримали назви метод критичного шляху (МКП) і метод оцінки й перегляду програм (ПЕРТ). Метод критичного шляху було запропоновано фірмою Є. I. du Роnt de Nemours & Company керувати програмами будівництва, та був було розвинено до узагальнено фірмою Маuсhlу Associates. Метод ПЕРТ розроблений консультативної фірмою на замовлення військово-морського міністерства США для календарного планування проведення науково-дослідницьких і дослідно-конструкторських робіт програми створення ракет «Поларіс». У методах ПЕРТ і МКП основну увагу приділяється тимчасовому аспекту планів тому, що обидві методу зрештою визначають календарний план програми. Хоча ці методи розробили незалежно, вони різняться разючою подібністю. Мабуть, найістотнішим відмінностями спочатку було те, що у методі МКП оцінки тривалості операцій передбачалися детермінованими величинами, а метод ПЕРТ — випадковими. Нині обидва методу складаю єдиний метод мережного планування і управління (СПУ) программами.

Частина 1.

Теоретична частина до курсовому проекту.

Глава1.

Теорія графов.

Поняття графа.

Графом G (X, U) називається сукупність двох об'єктів деякого безлічі X і відображення цього безлічі у собі Г.

При геометричному поданні графа елементи безлічі Х зображуються точками площини і називаються вершинами графа. Лінії, що з'єднують будь-які пари точок x і y, у тому числі у є відображенням x, називаються дугами графа. Дуги графа мають напрям, позначуване стрілкою, спрямованої вістрям від елемента x для її відображенню у.

Вершини і лінії графа.

Дві вершини Проте й У є граничними вершинами дуги, якщо Апочаток дуги, а У його конец.

Суміжними називаються різні дуги, мають загальну граничную точку. Дві вершини x і в суміжні, якщо вони різняться існує дуга, що йде від, а такою в іншу .

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

Якщо дуга U виходить із вершини x чи заходить в x, то дуга U називається инцидентной вершині x, а вершини x инцидентной дузі U. Загальна кількість дуг, инцидентной вершині x, є ступенем вершини x Р (х). Вершини, ступінь яких Р (х)>2, називаються вузлом, а зі ступенем Р (х)= 0. Розмір L (j)-E (i)-d ij називається повним резервом часу операції (і, j). Яке якомога більше часу можуть дати до виконання операції (і, j) без запровадження додаткових тимчасових обмежень на наступні операції? Для дотримання його запровадження операція (і, j) має бути закінчена на момент часу Є (j). Оскільки операція (і, j) може початися вже не раніше E (і), їхньому виконання без запровадження додаткових обмежень на наступні операції можна виділяти трохи більше E (j)-E (i) одиниць часу. Розмір E (j) -E (і) — d ij Називається вільним резервом часу операції (і, j). Вільний резерв часу дорівнює максимальної затримки здійснення операції (і, j), не впливає виконання наступних операцій. Яке якомога більше часу можуть дати до виконання операції (i, j) без запровадження додаткових тимчасових обмежень кожну операцію проекту? Для виконання цієї умови операція (i, j) повинна початися в останній момент часу L (i) і закінчитися на момент часу E (j), cледовательно, виконання операції (i, j) у разі можна назвати трохи більше Є (J) -L (i) одиниць часу. Величина Є(j) — L (і)-d ij називається незалежним резервом Часу операції (і, j). Незалежний резерв часу дорівнює максимальної затримки, що можна допустити і під час операції (і, j) без запровадження додаткових тимчасових обмежень кожну іншу операцію проекту. Негативне значення незалежного резерву означає, будь-яка затримка з виконанням операції призведе до додатковим обмеженням виконання інших операций.

Побудова календарного графіку й розподіл ресурсов.

Кінцевим результатом виконуваних на мережевий моделі розрахунків є календарний графік (план). Цей графік легко перетворюється на реальну шкалу часу, зручну для реалізації процесу виконання програми. При побудові календарного графіка необхідно враховувати наявність ресурсів, оскільки одночасне (паралельне) виконання деяких операцій через обмеження, що з робочої силою, обладнанням і інші види ресурсів, може бути неможливим. Саме у цьому відношенні представляють цінність резерви часу некритичних операцій. Зсуваючи некритичну операцію у цьому чи іншому напряму, але у межах її повного резерву часу, можна домогтися зниження максимальної потреби у ресурсах. Однак навіть за відсутності обмежень на ресурси повні резерви часу зазвичай йдуть на вырабатывания потреб у ресурсах на протязі всього терміну реалізацію програми. Фактично, це, що програму вдається виконати більш-менш постійним складом робочої сили порівняно з випадком, коли у робітничій силі (та інших. ресурсах) різко змінюються під час переходу від однієї інтервалу часу до іншому. Для побудови календарного графіка передусім визначаються календарні терміни виконання критичних операцій. Далі розглядаються некритичні операція і вказуються їх ранні терміни початку Є. і пізні терміни закінчення L. Критичні операції зображуються суцільними лініями. Відтинки часу, в межах яких можуть виконуватися некритичні операції, наносяться пунктирними лініями, які показують, що календарні терміни операцій можна вибрати у межах за умови збереження відносин прямування. Фіктивна операція не вимагає витрат часу й тому змальовується на графіці вертикальним відрізком. Числа, проставлені над некритическими операціями, відповідають продолжительностям.

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

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

Частина 2.

Практична реалізація курсового проекта.

Задание.

Варіант № 24.

Побудувати мережну модель і календарний графік за зазначеними у таблиці данным.

|Номера |Яким |Продолжи-тел|Потребность в | |робіт |роботам |ьность работ|трудресурсах | |(опера-|предше-ству| | | |ций) |ет | | | |1 |2 |9 |2 | |2 |3, 4, 5 |8 |1 | |3 |6 |8 |9 | |4 |8 |9 |5 | |5 |7 |13 |1 | |6 |7 |12 |4 | |7 |10, 12 |14 |4 | |8 |9, 10 |12 |3 | |9 |10, 12 |14 |8 | |10 |11 |6 |4 | |11 |14 |9 |1 | |12 |13, 17 |11 |3 | |13 |15 |16 |6 | |14 |15 |5 |1 | |15 |16 |7 |5 | |16 |18 |9 |1 | |17 |18 |13 |2 | |18 | |9 |3 |.

Решение.

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

[pic].

Рис 4.1.

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

Алгоритм розрахунку найперших можливих термінів наступу подій. Крок 1. Покласти Е/0/ = 0 Шaг 2. Для j = 1,2,…, n вычислить.

E (j)=max {E (і) + d ij }, і: (ij) е, А где максимум з всіх операціях, завершальним, в jm вузлі і які виходять із будь-якого попереднього іго вузла. Означимо тепер через L (і) найбільш пізніший строк наступу іго події, не впливає тимчасово завершення всього проекту. Починаючи з завершального події рухаємося у напрямі через кожне попереднє подія. Обчислення здійснюються у цьому випадку по наступному алгоритму.

Алгоритм розрахунку найбільш пізніх допустимих термінів наступу подій. Крок 1. Покласти L (n) =Є(n). Крок 2. Для і = n-1,n-2,…, 0 вычислить.

L (i)=min {L (j-dij)}, j:(ij)эA.

де мінімум з всіх операціях начинающимся в ім вузлі і які входять у будь-який j-й вузол. Діючи описаним вище способом, розрахуємо найбільш ранні можливі терміни наступу подій і найбільш пізні допустимі строки наступу подій (рис 4.2). Найбільш ранні максимально можливі строки наступу подій відбито в квадратиках поруч із самим подією, над квадратиками розташовані найбільш пізні допустимі строки наступу подій. На основі прямого й протилежного проходів виділяємо на графіці критичні операції з яких складається критичний шлях. Критичний шлях становлять операції: 1,2,4,8,9,(из 6 до 8 події фіктивна операция), 12,13,15,16,18 — ці опреации виділено іншим кольором на граффике (рис 4.2). Критичний час проекту — 104.

[pic]Рис 4.2 Тепер обчислимо резерви часу для некритичних операцій. Розраховані резерви часу внесемо в таблицю 1.

Таблиця 1.

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

Таблиця 2.

[pic].

За підсумками отриманої таблиці будуємо календарний графік реалізації проекту (рис 4.3) і двоє графіка ресурсних профілів проекту — у першому, виберемо в ролі моментів початку некритичних операцій їх ранні максимально можливі строки, одержимо ранній календарний план реалізації проекту (рис 4.5), тоді як у другому виберемо як моментів початку некритичних операцій їх пізні допустимі строки, одержимо пізній календарний план реалізації проекту (рис 4.6).

[pic]. Рис 4.5.

[pic]Рис 4.6.

Заключение

.

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

Список використаної литературы.

Таха Х. «Введення у дослідження операцій» т.1,2.

М. Світ 1989 Ковальова Л. Ф. «Математична і теорія графів» МЭСИ 1977.