Знаходження критичного шляху табличним методом
Мережевий графік - необхідний елемент складного виробництва, що складається з декількох пов'язаних і залежать один від одного етапів. Виявлення критичного шляху і тимчасових резервів виробництва - основне завдання, яке вирішується побудовою мережевого графіка. Такі завдання можуть бути представлені у вигляді графа і у вигляді відображає його таблиці. Для знаходження критичного шляху (послідовності етапів роботи, що визначають тривалість всього проекту і не мають резерву за часом) застосовуються обчислювальні методи. Одним з таких методів є табличний метод і застосовується для даних, представлених у вигляді таблиці.
Проблема автоматизації розрахунку мережного графіка є досить актуальною і важливою. Обчислення критичного шляху за допомогою ЕОМ допоможе в кілька разів прискорити цей процес, а при великих графіках - у багато разів. Тому автоматизація розрахунку мережного графіка може мати велику практичну користь.
Ми розглядаємо задачу, яка представлена у вигляді графа.
Вершини графа - етапи робіт.
Ребра графа - виконання роботи. Ребра мають довжину, що позначає тривалість роботи і напрям, що позначає послідовність виконання роботи.
Потрібно знайти такий шлях на графі, який би мав максимальну довжину в порівнянні з усіма можливими шляхами для даного графа.
Дані завдання також можуть бути представлені у вигляді таблиці
Метою рішення також є:
Обчислення часу раннього початку робіт кожного виду - мінімального терміну початку роботи, рахуючи від початку проекту.
Обчислення часу раннього завершення робіт кожного виду - мінімального терміну завершення роботи, рахуючи від початку проекту.
Обчислення часу пізнього початку робіт кожного виду - максимального терміну початку роботи, рахуючи від початку проекту.
Обчислення часу пізнього завершення робіт кожного виду - максимального терміну завершення роботи, рахуючи від початку проекту.
Обчислення повного резерву робіт кожного виду - максимального запасу часу на яке можна відстрочити початок роботи.
Для написання програми була вибрана мова VBA з наступних причин:
1. VisualBasicforApplications дозволяє зручно працювати з великими таблицями, зчитуючи з них дані, виробляючи над ними перетворення і будуючи нові.
2. Використання VBA під оболонкою Excel дозволяє використовувати функції даної оболонки, що полегшують введення даних і роботу з ними.
3. Ця мова дозволяє автоматизувати деякі етапи написання програми засобами макрорекордер.
4. Я добре знайомий з цією мовою і мені зручніше за все буде писати програму саме за допомогою VBA.
5. Простота в освоєнні мови і доступність вихідних кодів програми дозволить наступним користувачам вдосконалити її, або змінити під свої вимоги.
1. При запуску вікна введення початкових даних користувачеві пропонується ввести кількість етапів робіт:
А) Виконується перевірка на правильність введення. Кількість виражається числом, воно повинно бути цілим (якщо число дробове, то відбувається усічення дробової частини) і не повинно перевищувати 254.
Б) Якщо умови введення виконані, то відбувається перевірка на наявність інформації в листі, про що виводиться повідомлення.
В) Будується таблиця вихідних даних
2. Після промальовування таблиці користувач повинен заповнити її значеннями:
А) після підтвердження користувачем заповнення таблиці:
3. Користувач переходить до іншого робочого вікна, де він має можливість активувати розрахунок критичного шляху і мережевого графіка, або перевести одиниці часу з одних в інші (наприклад, дні в години), якщо в таблиці є дробові числа, оскільки в конкретному завданні під оболонкою VBA обчислення з використанням дробових чисел дають похибку.
А) Якщо користувач вибрав переклад одиниць часу, то числа в таблиці вихідних даних перетворюються за обраною схемою.
Б) Якщо користувач вибрав побудова мережевого графіка, то будується таблиця, що має дані про час раннього і пізнього початку роботи, раннього і пізнього завершення роботи, а також резерв по часу для кожного етапу і послідовність етапів критичного шляху.
4. Натиснувши кнопку розрахунку мережного графіка, користувач запускає алгоритм пошуку критичного шляху і супутніх даних, який працює в такий спосіб:
4.1. У таблицю рішення заноситься інформація з таблиці вихідних даних і підраховується кількість записів (число видів робіт).
4.2. Визначаються початкові етапи. Якщо в таблиці вихідних даних стовпець не містить дані тривалості, значить, цим етапом не закінчується жоден вид робіт, тобто він початковий.
4.3. Для всіх початкових етапів, знайдених по вихідній таблиці заносяться значення раннього початку робіт рівні 0 і час раннього закінчення робіт 0 + тривалість виду робіт.
4.4. Для кожної заповненої таким чином рядка визначається етап закінчення виду робіт і його позначення запам'ятовується. З усіх видів робіт, що закінчуються на такий етап, виявляється вид, що має максимальне значення часу раннього закінчення роботи. Це значення також запам'ятовується. Далі в таблиці відшукуються види робіт, що починаються на раніше запомненний етап і для всіх записів, які відповідають умові в графу час раннього початку заноситься запомненное максимальне значення часу раннього закінчення роботи. Алгоритм повторюється, поки не залишиться ні за одну повну висоту.
4.5. У таблиці результатів, де для кожного виду робіт визначено час раннього початку і завершення, визначається максимальне значення часу раннього закінчення роботи, яке є тривалістю всього проекту.
4.6. Визначаються кінцеві етапи. Якщо в таблиці вихідних даних рядок не містить дані тривалості, значить, цим етапом починається не жоден вид робіт, тобто він кінцевий.
4.7. Для всіх кінцевих етапів, знайдених по вихідній таблиці заносяться значення пізнього завершення робіт рівні тривалості проекту і час пізнього початку робіт, однакову різниці тривалості проекту та тривалості виду робіт. Обчислюється повний резерв дорівнює різниці між пізнім і раннім часом закінчення (початку) робіт.
4.8. Для кожної заповненої таким чином рядка визначається етап початку виду робіт і його позначення запам'ятовується. З усіх видів робіт, що починаються на такий етап, виявляється вид, що має мінімальне значення часу пізнього початку роботи. Це значення також запам'ятовується. Далі в таблиці відшукуються види робіт, що закінчуються на раніше запомненний етап і для всіх записів, які відповідають умові в графу доби пізнього завершення заноситься запомненное мінімальне значення часу пізнього початку роботи. Обчислюється повний резерв. Алгоритм повторюється, поки не залишиться ні за одну повну висоту.
4.9. Виділяються записи, що мають значення повного резерву рівне 0. Такі види робіт входять в критичний шлях.
4.10. Для відшукання критичного шляху з першої зустрілася записи з повним резервом рівним нулю беруться значення початку і завершення виду робіт. Для всіх наступних записів береться тільки позначення етапу завершення виду робіт. Працездатність таким алгоритмом забезпечує структура розрахункової таблиці, де види робіт впорядковані по етапах їх початку. Однак якщо користувач пронумерує етапи в зворотному порядку, може трапитися так, що який-небудь етап зустрінеться в критичному шляху два рази, а інший ні разу. Для цього передбачений алгоритм пошуку повторюваних значень в критичному шляху. Якщо повторення виявлені, то програма будує критичний шлях в зворотному порядку. З останньої зустрілася записи з повним резервом рівним нулю беруться значення завершення і початку виду робіт. Для всіх наступних записів береться тільки позначення етапу початку виду робіт.
5. Результати обчислень виводяться на екран. Користувач може перевести одиниці часу в зворотному порядку (п. 3).
Визначимо критичний шлях на основі даних про зв'язки між етапами робіт і тривалості виконання робіт.
Нехай заданий граф.
Спочатку вводиться число етапів робіт (в даному прикладі 10)
Виходячи з даних таблиці заповнюється електронна таблиця вихідних даних, де номер рядка - етап початку роботи, а номер стовпця - етап завершення роботи.
Після натискання на кнопку «ОК» відкриється меню рішення
У конкретному прикладі переклад одиниць часу не потрібно, але для наочності можна здійснити переклад. Припустимо є дані про тривалість в днях, але є необхідність представити їх в годиннику.
Провівши розрахунок отримаємо підсумкову таблицю:
Можна здійснити зворотний переклад одиниць часу.
Це завдання було вирішене раніше без використання ЕОМ і мала рішення:
Час раннього початку
Час раннього кінця
Час пізній початок
Час пізнього кінця
При запуску Excel файлу з'являється стартове вікно. на якому розташовуються 2 кнопки:
«Почати роботу» при натисканні на цю кнопку викликається вікно введення початкових даних.
«Вихід» при натисканні на цю кнопку відбувається закриття програми і Excel.
У вікні введення початкових даних користувач задає число етапів робіт (число повинне бути цілим в діапазоні від 3 до 254)
У формі знаходяться 4 кнопки і прапорець
· «ОК» - формування таблиці вихідних даних і включення режиму заповнення таблиці.
· «Скасування» - закриття форми
· «Довідка» - виклик довідки про програму
· «Пропустити» - перехід до форми рішення
· «Включити підказки» - включення пояснювальних вікон.
Після заповнення таблиці користувач переходить до вікна рішення
На якому розташовуються 3 кнопки:
· «Визначення критичного шляху» - розрахунок критичного шляху і супутніх даних і виведення результатів на екран.
· «Повернення до введення початкових даних» - відкриття вікна введення початкових даних і листа введення.
· «Переклад одиниць часу» - відкриття вікна перекладу одиниць часу в якому потрібно вибрати поточні одиниці часу і натиснути кнопку «ОК», потім вибрати необхідні одиниці часу і натиснути кнопку «ОК».
В результаті виконання роботи був вивчений алгоритм знаходження критичного шляху і складання таблиці мережевого графіка. На основі алгоритму реалізована програма, що забезпечує графічний інтерфейс користувача, табличний введення даних і табличний висновок отриманих результатів.
1. Бєляєв С.П. Курс лекцій з «Дослідженню операцій».
ФормаAbout (довідка про програму)
Private Sub UserForm_Terminate ()
ФормаHelpForm1 (допомога в заповненні таблиці)
ФормаInsForm (введення кількості етапів робіт, перевірка формату листа, перевірка правильності введення, виклик довідки, вихід з програми, перехід до розрахункової формі)
'Перевірка правильності введення
Dim Answer As String
If iget.Value = "" Then
MsgBox "Введітеколічествоетапов", vbCritical + vbOKOnly, "Ошібкаввода"
If Not (IsNumeric (iget.Value)) Then
MsgBox "Кількість етапів роботи повинно бути числом", vbCritical + vbOKOnly, "Помилка введення"
If iget.Value <3 Then
MsgBox "Кількість етапів роботи повинно бути не менше 3", vbCritical + vbOKOnly, "Помилка введення"
If iget.Value> 254 Then
MsgBox "Кількість етапів роботи повинно бути не більше 222", vbCritical + vbOKOnly, "Помилка введення"
'Перевірка листа на наявність інформації
For i = 1 To 254
For j = 1 To 254
If Not ActiveSheet.Cells (i, j) .Value = "" Then
Answer = MsgBox ( "Лист містить інформацію! Якщо не перерветься вона буде знищена! Продовжити?", VbCritical + vbOKCancel, "Попередження")
If Answer = vbCancel Then
If Answer = vbOK Then