Реферати українською » Экономико-математическое моделирование » Знаходження критичного шляху табличним методом


Реферат Знаходження критичного шляху табличним методом

Страница 1 из 2 | Следующая страница

Зміст

 

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

>1.Постановка завдання. 3

>2.Метод рішення. 4

>3.Язик програмування. 11

>4.Описание алгоритму. 12

>5.Контрольний приклад. 15

>6.Описание інтерфейсу з користувачем. 19

Укладання. 20

Література. 21

>Листинг програми.. 22


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

 

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

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


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

 

Ми розглядаємо завдання, подану як графа.

>Рис. 1

Вершини графа – етапи робіт.

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

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

Дані завдання також можуть бути як таблиці

Види робіт Тривалість
1-2 2
1-4 1
1-5 4
2-3 3
4-3 5
4-6 3
4-7 1
4-9 3
5-6 2
6-10 5
7-8 6
7-9 2

Метою рішення є також:

·Вичисление часу раннього початку робіт кожного виду – мінімального терміну початку, починаючи з початку проекту.

·Вичисление часу раннього завершення робіт кожного виду – мінімального терміну роботи, починаючи з початку проекту.

·Вичисление часу пізнього початку робіт кожного виду – максимального терміну початку, починаючи з початку проекту.

·Вичисление часу пізнього завершення робіт кожного виду – максимального терміну роботи, починаючи з початку проекту.

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

 

>3.Язик програмування

 

Для написання програми, був обраний мовуVBA з таких причин:

1.VisualBasicforApplications дозволяє зручно працювати з більшими на таблицями, зчитуючи їх дані, виробляючи з них перетворення та строю нові.

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

3. Її дозволяє автоматизувати деякі етапи написання програми засобамимакрорекордера.

4. Я добре з цю мову і мені найзручніше писатиме програму саме з допомогоюVBA.

5. Простота лідера в освоєнні мови та доступність вихідних кодів програми дозволить наступним користувачам вдосконалити її, або змінити під свої основні вимоги.


>4.Описание алгоритму

 

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).

>5.Пример виконання завдання на ЕОМ

>Определим критичний шлях з урахуванням даних зв'язки між етапами робіт і тривалості виконання.

Нехай заданий граф.

За підсумками даних графа будується таблиця

Види робіт

>Продол-

житель-

>ность

Час раннього початку Час раннього кінця Час пізнього початку Час пізнього кінця Повний резерв
1-2 2
1-4 1
1-5 4
2-3 3
4-3 5
4-6 3
4-7 1
4-9 3
5-6 2
6-10 5
7-8 6
7-9 2

Спочатку вводиться число етапів робіт (у цьому прикладі 10)

З даних таблиці заповнюється електронна таблиця вихідних даних, де номер рядки – етап початку, а номер шпальти – етап роботи.

Після натискання на кнопку «ОК» відкриється меню рішення

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


Провівши розрахунок одержимо підсумкову таблицю:

Можна здійснити зворотний переклад одиниць часу.

Це було вирішена раніше без використання ЕОМ й мала рішення:

Види робіт

>Продол-

житель-

>ность

Час раннього початку Час раннього кінця Час пізнього початку Час пізнього кінця Повний резерв
1-2 2 0 2 6 8 6
1-4 1 0 1 1 3 2
1-5 4 0 4 0 4 0
2-3 3 2 5 8 11 6
4-3 5 1 6 6 11 4
4-6 3 1 4 3 6 2
4-7 1 1 2 4 5 3
4-9 3 1 4 8 11 7
5-6 2 4 6 4 6 0
6-10 5 6 11 6 11 0
7-8 6 2 8 5 11 3
7-9 2 2 4 9 11 7

Критичний шлях: 1-5-6-10

Результати обчислень вручну, і на ЕОМ збігаються.

>5.Описание інтерфейсу і керівництво користувача

Після запуску Excel файла з'являється стартове вікно, у якому розташовуються 2 кнопки:

«Почати роботу» при натисканні з цього кнопку викликається вікно введення початкових даних.

«Вихід» при натисканні з цього кнопку відбувається закриття програми розвитку й Excel.

У вікні введення початкових даних користувач задає число етапів робіт (число має бути цілим буде в діапазоні від 3 до 254)

У формі перебувають 4 кнопки і прапорець

· «ОК» - формування таблиці вихідних даних, і включення режиму заповнення таблиці.

· «Скасування» - закриття форми

· «Довідка» - виклик довідки про програму

· «Пропустити» - перехід до форми рішення

· «Включити підказки» - включення пояснюючих вікон.

Після заповнення таблиці користувач переходить до вікна рішення

На якому розташовуються 3 кнопки:

· «Визначення критичного шляху» - розрахунок критичного шляху й супутніх даних, і висновок результатів на екран.

· «Повернення ввести в дію початкових даних» - відкриття вікна введення початкових даних, і аркуша введення.

· «Переклад одиниць часу» - відкриття вікна перекладу одиниць часу у якому потрібно вибрати поточні одиниці часу й натиснути кнопку «ОК», потім вибрати необхідні одиниці часу й натиснути кнопку «ОК».


Укладання

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


Література

 

1. Бєляєв С.П. Курс лекцій з «Дослідженню операцій».

2.Кузменко В. Г, Програмування на MicrosoftVisualBasicforApplications 2003 /Москва вид.Бином; 2004 р. – 880 з.: мул.


>Листинг програми

 

Форма >About (довідка про програму)

>PrivateSubUserForm_Terminate()

>Hide

>InsForm.Show

EndSub

Форма >HelpForm1 (допомогу у заповненні таблиці)

 

>PrivateSubCommandButton1_Click()

>Hide

>OKForm.StartUpPosition = 0

>OKForm.Top = 450

>OKForm.Left = 580

>OKForm.Show

EndSub

>PrivateSubCommandButton2_Click()

>Hide

>InsForm.Show

EndSub

>PrivateSubUserForm_Terminate()

>Hide

>InsForm.Show

EndSub

Форма >HelpForm2 (допомогу у розумінні результатів обчислень)

 

>PrivateSubCommandButton1_Click()

>check =True

>Hide

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>SolForm.Show

EndSub

>PrivateSubCommandButton2_Click()

>check =False

>Hide

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>SolForm.Show

EndSub

Форма >HelpForm3 (допомогу у перекладі одиниць часу)

>PrivateSubCommandButton1_Click()

>check =True

>Hide

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>SolForm.Show

EndSub

>PrivateSubCommandButton2_Click()

>check =False

>Hide

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>SolForm.Show

EndSub

Форма >InsForm (введення кількості етапів робіт, перевірка формату аркуша, перевірка правильності введення, виклик довідки, вихід із програми, перехід дорасчетной формі)

 

'Перевірка правильності введення

>PrivateSubCommandButton1_Click()

>DimAnswerAsString

>Application.ScreenUpdating =False

>Ifiget.Value = ""Then

>MsgBox "Запровадьте кількість етапів",vbCritical +vbOKOnly, "Помилка введення"

>ExitSub

EndIf

>IfNot (>IsNumeric(iget.Value))Then

>MsgBox "Кількість етапів роботи має бути числом",vbCritical +vbOKOnly, "Помилка введення"

>ExitSub

EndIf

>Ifiget.Value < 3Then

>MsgBox "Кількість етапів роботи має не меншим 3",vbCritical +vbOKOnly, "Помилка введення"

>ExitSub

EndIf

>Ifiget.Value > 254Then

>MsgBox "Кількість етапів роботи має не більше 222",vbCritical +vbOKOnly, "Помилка введення"

>ExitSub

EndIf

n =Fix(iget.Value)

'Перевірка аркуша на наявність інформації

>For і = 1To 254

>For j = 1To 254

>IfNotActiveSheet.Cells(i,j).Value = ""Then

>Answer =MsgBox("Лист містить інформацію! Якщо не перерветься вона знищена! Продовжити?",vbCritical +vbOKCancel, "Попередження")

EndIf

>IfAnswer =vbCancelThen

і = 254

j = 254

>ExitSub

EndIf

>IfAnswer =vbOKThen

і = 254

j = 254

EndIf

Next j

Next і

'Побудова таблиці введення і до неї

>Range("A1:IV254").Select

>Selection.Clear

>InsData

>Application.ScreenUpdating =True

>Hide

>Ifhelp.Value =TrueThen

>hlp =True

>HelpForm1.Show

>Else

>hlp =False

>OKForm.StartUpPosition = 0

>OKForm.Top = 450

>OKForm.Left = 580

>OKForm.Show

EndIf

EndSub

>PrivateSubCommandButton2_Click()

>Hide

>STF.Show

EndSub

>PrivateSubCommandButton3_Click()

>Hide

>About.Show

EndSub

PublicSubStart()

>iget.Value = n

EndSub

>PrivateSubCommandButton4_Click()

>DimflagAsBoolean

>Hide

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>SolForm.Show

>flag =True

n = 1

>IfNotActiveSheet.Cells(1,1).Value = "№"Then

>MsgBox "Ліст не відформатований для розрахунку, скористайтеся вікном введення даних",vbCritical +vbOKOnly, "Помилка"

>Hide

>InsForm.Show

>ExitSub

EndIf

>DoWhileflag

n = n + 1

>IfActiveSheet.Cells(n,1).Value = ""Then

>flag =False

EndIf

>IfActiveSheet.Cells(n,1).Value = n - 1Then

>flag =True

>Else:flag =False

EndIf

>Loop

n = n - 2

>For і = 2To n

>IfNotActiveSheet.Cells(1,i).Value = і - 1Then

>MsgBox "Ліст не відформатований для розрахунку, скористайтеся вікном введення даних",vbCritical +vbOKOnly, "Помилка"

>Hide

>InsForm.Show

>ExitSub

EndIf

Next і

EndSub

>PrivateSubSpinButton1_SpinUp()

>Ifiget.Value <= 222Then

>iget.Value =iget.Value + 1

>Else

>ExitSub

EndIf

EndSub

>PrivateSubSpinButton1_SpinDown()

>Ifiget.Value >= 4Then

>iget.Value =iget.Value - 1

>Else

>ExitSub

EndIf

EndSub

>PrivateSubUserForm_Initialize()

>iget.Value = 10

>Sheets("Data").Select

EndSub

>PrivateSubUserForm_Terminate()

>Hide

>STF.Show

EndSub

Форма >OKForm (підтвердження закінчення введення початкових даних)

>PrivateSubCommandButton1_Click()

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>Hide

>SolForm.Show

EndSub

>PrivateSubUserForm_Terminate()

>Hide

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>SolForm.Show

EndSub

Форма >Perevod1 (запам'ятовування поточних одиниць часу)

 

'>Запоминание поточних одиниць часу

>PrivateSubCommandButton1_Click()

>IfMinutes.Value =TrueThen

>edin = 1

EndIf

>IfChas.Value =TrueThen

>edin = 2

EndIf

>IfSutki.Value =TrueThen

>edin = 3

EndIf

>IfNedeli.Value =TrueThen

>edin = 4

EndIf

>IfMes.Value =TrueThen

>edin = 5

EndIf

>IfGodi.Value =TrueThen

>edin = 6

EndIf

>Hide

>Perevod2.Show

EndSub

>PrivateSubUserForm_Terminate()

>Hide

>SolForm.StartUpPosition = 0

>SolForm.Top = 350

>SolForm.Left = 480

>SolForm.Show

EndSub

Форма >Perevod2 (переклад одиниць часу, повернення дорасчетной формі)

 

'Переклад одиниць часу

>PrivateSubCommandButton1_Click()

>Hide

>SolForm.Show

>IfActiveSheet.Cells(1,1).Value = "№"Then

>Ifedin = 1Then

>IfMinutes.Value =TrueThen

>ExitSub

EndIf

>IfChas.Value =TrueThen

>For і = 2To n + 1

>For j = 2To n + 1

>IfNotActiveSheet.Cells(i,j).Value = ""Then

>ActiveSheet.Cells(i,j).Value =ActiveSheet.Cells(i,j).Value / 60

EndIf

Next j

Next і

EndIf

>IfSutki.Value =TrueThen

>For і = 2To n + 1

>For j = 2To n + 1

>IfNotActiveSheet.Cells(i,j).Value = ""Then

>ActiveSheet.Cells(i,j).Value =ActiveSheet.Cells(i,j).Value / 1440

EndIf

Next j

Next і

EndIf

>IfNedeli.Value =TrueThen

>For і = 2To n + 1

>For j = 2To n + 1

>IfNotActiveSheet.Cells(i,j).Value

Страница 1 из 2 | Следующая страница

Схожі реферати:

Навігація