1.4 Змістовна постановка задачі

На основі проведеного аналізу предметної області можна зрозуміти, що в ході курсової роботи для досягнення поставленої мети потрібно виконати три наступні підзадачі:

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

1. Розробити програмні структури для обраного представлення сітьового графа (СГ).

2. Розробити програмне забезпечення для топологічного аналізу СГ на наявність обривів та контурів.

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

4. Результати розрахунків представити у виді таблиці.

5. Розробити програмне забезпечення для графічного представлення СГ у вигляді діаграми Ганта.

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

1. Описати теоретичну суть та послідовність розрахунків імовірнісних характеристик параметрів проекту.

2. Навести алгоритми основної програми, структуру вхідних і вихідних даних.

III. Основні висновки по роботі та аналіз досягнутих результатів.

2 РОЗРОБКА ДЕТЕРМІНОВАНОЇ МОДЕЛІ СІТЬОВОГО ГРАФІКА І ПРОВЕДЕННЯ МОДЕЛЮВАННЯ

2.1 Розробка програмного забезпечення для моделювання детермінованої моделі

Розробка програмних структур для СГ

Маємо орієнтований граф G =(V, E), кожній дузі vаw цього графа відповідає невід'ємна ціна С [v, w]. Загальна задача знаходження найдовших шляхів полягає в знаходженні для кожної вершини впорядкованої пари вершин (v, w) любого шляху від вершини v до вершини w, довжина якого максимальна серед усіх можливих шляхів від v до w.

Існує прямий спосіб розв'язання цієї задачі, використовуючий алгоритм Флойда (R. W. Floyd). Для визначеності установимо, що вершини графа послідовно пронумеровани від 1 до n. Алгоритм Флойда використовує матрицю А розміру nхn, в якій обчислюються довжини найдовших шляхів. На початку А[i, j]=C[i, j] для усіх i?j. Якщо дуга iа j відсутня, то C[i, j]=-?. Кожний діагональний елемент матриці А дорівнює 0.

Над матрицею А виконується n ітерацій. Після k-тої ітерації A[i, j] містить значення шляхів найменшої довжини з вершини i в вершину j, які не проходять через вершини з номером, більшим за k. Іншими словами, між кінцевими вершинами шляху i и j можуть знаходитися вершини, номера яких менше чи рівні k.

На k-тій ітерації для обчислення матриці А застосовується наступна формула:

Ak[i, j] = min(Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j]).

Нижній індекс k позначає значення матриці А після k-тої ітерації, однак це означає, що існує n різних матриць, цей індекс використовується для скорочення запису.

Для обчислення Ak[i, j] проводиться порівняння вершини Ak-1[i, j] (тобто ціна от шляху від вершини i до вершини j без участі вершини k чи іншої вершини з більш високим номером) з величиною Ak-1[i, k] + Ak-1[k, j] (ціна шляху від вершини i до вершини k плюс шляху від вершини k до вершини j). Якщо шлях через вершину k дорожче, ніж Ak-1[i, j], то величина Ak[i, j] змінюється.

Рівності Ak[i, k] = Ak-1[i, k] и Ak[k, j] = Ak-1[k, j] означають, що на k-тій ітерації елементи матриці А, що стоять в k-тій строці и в k-м стовпці, не змінюються. Усі обчислення можливо проводити лише з однією копією матриці А.

Щоб встановити при необхідності найдорожчі шляхи, можна в алгоритмі Флойда ввести ще одну матрицю P, в якій елемент P[i, j] містить вершину k, отриману при знаходженні найбільшого значення A[i, j]. Якщо P[i, j] = 0, то найдовший шлях з вершини i в вершину j складається з однієї дуги iа j.

Модифікована версія алгоритму Флойда, що дозволяє відновити найдовші шляхи:

private void AlgorithmFloyda(double [,]C, int [,]P)

{

int i,j,k;

int nn = (int)Math.Sqrt(C.Length)-1;

double [,]A = new double[nn+1,nn+1];

for(i=1; i<=nn; i++)

for(j=1; j<=nn; j++)

{

A[i,j] = C[i,j];

P[i,j] = 0;

}

for(i=1; i<=nn; i++)

A[i,i] = 0;

for(k=1; k<=nn; k++)

for(i=1; i<=nn; i++)

for(j=1; j<=nn; j++)

if(A[i,k] + A[k,j] >A[i,j])

{

A[i,j]=A[i,k]+A[k,j];

P[i,j]=k;

}

}

Програма повинна виконувати топологічний аналіз СГ на існування обривів та контурів. Якщо у СГ існує i-та вершина, з якої не виходить жодна дуга-робота (тобто i-й рядок матриці містить лише від'ємні числа), то знайден обрив. Тоді вершина, що висить, видаляється з графа шляхом заміни i-го стовпця матриці числами, що символізують -Ґ. Повідомлення про відповідні дії будуть записуватися у вихідний файл. Аналіз на існування контурів буде проводиться під час знаходження максимального шляху між вершинами: СГ є топологічно відсортованим, тому виявлення зворотної дуги vаw (v>w) свідчить про наявність контуру. У цьому разі для попередження зациклювання виконання програми буде припинятися.

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

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

Розрахунок критичного шляху, визначення ранніх і пізніх термінів настання подій, ранніх і пізніх термінів початку і завершення робіт, повних и вільних резервів часу виконання робіт буде виконуватися на базі інформації, отриманої алгоритмом Флойда, за формулами, що наведенні в I розділі.

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

Також програма буде формувати графічне представлення СГ - діаграму Ганта. На діаграмі кожній роботі буде відповідати два часових параметра: безпосередньо тривалість роботи та її повний резерв.

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

i j Назва роботи C_min C_max.

3 МОДЕЛЮВАННЯ СІТЬОВОГО ГРАФІКА МЕТОДОМ СТАТИСТИЧНИХ ВИПРОБУВАНЬ

3.1 Описання теоретичної суті методу

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

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

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

по однієї і тієї ж роботи оцінки даються декількома експертами;

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

даються дві оцінки тривалості роботи:

мінімальна tmin, тобто при найбільш сприятливому збігу обставин;

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

даються три оцінки тривалості:

мінімальна;

найбільш імовірна;

максимальна.

Машинна обробка інформації про ймовірносні параметри сітьові моделі зводиться до обчислення:

математичного сподівання і дисперсії тривалості всього комплексу операцій (Lкр), що описується даною сітьовою моделлю;

довірчих інтервалів, що утримують значення тривалості комплексу операцій при заданих значеннях надійності;

довірчої імовірності закінчення комплексу робіт зі створення об'єкта в директивний термін при заданих значеннях довжини довірчих інтервалів;

математичних сподівань і дисперсій ранніх і пізніх термінів здійснення подій сітьової моделі;

довірчих інтервалів, що утримують значення ранніх і пізніх термінів здійснення подій сітьової моделі при заданих значеннях надійності;

довірчих імовірностей здійснення подій сітьової моделі в запланований термін при заданих значеннях довжини довірчих інтервалів;

У наш час розв'язання перелічених задач здійснюється такими способами:

зведенням імовірнісної моделі до детермінованого СГ, у якому математичні сподівання тривалості робіт приймаються за їхні детерміновані тривалості;

Страницы: 1, 2, 3, 4, 5, 6