Статистичне моделювання сітьового графіка побудови судна (стр. 5 из 8)
Щоб встановити при необхідності найдорожчі шляхи, можна в алгоритмі Флойда ввести ще одну матрицю 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 Описання теоретичної суті методу
Системи сітьового планування і керування в загальному випадку застосовуються для комплексів робіт, тривалість більшості яких не має нормативів.
У суднобудівній промисловості до них відносяться різні роботи на передпроектній і проектній стадіях, науково-дослідницькі, дослідно-конструкторські й експериментальні роботи, а також роботи з виготовлення та іспиту нових експериментальних зразків.
Невизначеність оцінок тривалості багатьох робот у суднобудуванні обумовлює імовірнісний характер виробничих сітей у галузі. У цих умовах застосовуються наступні ймовірносні способи оцінки тривалості кожної роботи:
1. по однієї і тієї ж роботи оцінки даються декількома експертами;
2. для робіт, що часто повторюються чи типових, установлюються найбільш імовірна tн.і. чи нормативна тривалість tнорм, що у розрахунках сітьового графіка приймається за очікувану тривалість роботи tоч;
3. даються дві оцінки тривалості роботи:
· мінімальна tmin, тобто при найбільш сприятливому збігу обставин;
· максимальна tmax, тобто при несприятливому збігу обставин, який характеризується значно більшою, ніж звичайно, кількістю труднощів і затримок, що можуть виникати в процесі виконання цієї роботи;
4. даються три оцінки тривалості:
· мінімальна;
· найбільш імовірна;
· максимальна.
Машинна обробка інформації про ймовірносні параметри сітьові моделі зводиться до обчислення:
· математичного сподівання і дисперсії тривалості всього комплексу операцій (Lкр), що описується даною сітьовою моделлю;
· довірчих інтервалів, що утримують значення тривалості комплексу операцій при заданих значеннях надійності;
· довірчої імовірності закінчення комплексу робіт зі створення об'єкта в директивний термін при заданих значеннях довжини довірчих інтервалів;
· математичних сподівань і дисперсій ранніх і пізніх термінів здійснення подій сітьової моделі;
· довірчих інтервалів, що утримують значення ранніх і пізніх термінів здійснення подій сітьової моделі при заданих значеннях надійності;
· довірчих імовірностей здійснення подій сітьової моделі в запланований термін при заданих значеннях довжини довірчих інтервалів;
У наш час розв’язання перелічених задач здійснюється такими способами:
I. зведенням імовірнісної моделі до детермінованого СГ, у якому математичні сподівання тривалості робіт приймаються за їхні детерміновані тривалості;
II. дослідженням імовірнісної моделі методом статистичних іспитів (метод Монте-Карло).
У випадку зведення імовірнісної моделі до детермінованого СГ приймаються наступні допущення:
· критичний шлях і максимальні шляхи, що передують кожній події і виходять з неї, є єдиними;
· тривалість критичного шляху і максимальних шляхів, що передують кожній події і виходять з неї, відповідно до граничної теореми Ляпунова припускаються наближено нормальними випадковими величинами.
Допущення існування в моделі єдиного критичного шляху і по одному максимальному шляху, що передують чи виходять з кожної події, не є точним. Побудова прикладів СГ, виключаючих це допущення, становить досить тривіальну задачу.
Внаслідок цього перше допущення не має теоретико-ймовірносного обґрунтування. При моделюванні за методом Монте-Карло створюється послідовність реалізацій СГ з випадковими тривалостями робіт. При цьому змінюється довжина критичного шляху та іноді список вершин, через які він проходить.
При моделюванні сітьового графіка методом статистичних випробувань (м. Монте-Карло) тривалості робіт реалізації СГ дорівнюють фіксованим значенням, отриманим з використанням статистичного моделювання по початковим даним.
Статистичне моделювання систем на ЕОМ є фактично сукупністю формальних процедур, засобами яких відтворюється на ЕОМ будь-які випадкові фактори (випадкові величини, випадкові події, випадкові функції з будь-яким розподілом). Вперше такі методи почали застосовувати для досліджень у галузі ядерної енергетики та військовій сфері наприкінці 40-х рр. XX ст.
Під час випробування вага
кожної дуги, що знаходиться у межах 
, розраховується за допомогою числа з нормальним розподілом 
за формулою 
. Для отримання випадкових чисел можна використовувати один з наступних методів:1) апаратний - найбільш складний, бо заснований на фізичному явищі;
2) табличний - потребує додаткової пам`яті, бо заздалегідь будуються таблиці випадкових чисел;
3) програмний - за допомогою спеціальних алгоритмів.
Останні два методи на відміну відпершого генерують псевдовипадкові числа.
Існує програмний метод конгруентних генераторів, що дозволяє отримати числа з рівномірним законом розподілу. У ньому застосовується наступна формула:
де коефіцієнти a, b, c не можуть бути довільними.В цій роботі a=97, b=1113, c=131072.
Повний період циклу цього генератора буде отриманий в тому разі, якщо коефіцієнти будуть обиратися наступним чином:
C = 2B, B- розрядність використовуємого комп’ютера. Повний період буде 2B;
a - вибирається за формулою a = 1+4×k, де k - ціле число;
b - просте число відносно с (найбільший спільний дільник буде 1).
 |
Рисунок 3 - Метод вилучення
Метод вилучення (рис. 3) дозволяє отримати випадкове число, якщо ми знаємо щільність розподілу f(x) випадкової величини Х. Його суть полягає в наступних діях:
· спочатку генерується випадкове число x з рівномірним розподілом на сегменті
;· потім ще одне - число Y, але на сегменті
;· ці два числа беруться як координати точки, якщо вона підпадає під криву f(x) (тобто в межах кривої щільності імовірності) , то перше число X і є випадковим числом з шуканим розподілом, якщо ні - знову генеруємо пари чисел.
Моделювання сітьового графіка методом статистичних випробувань дає достовірні результати, коли кількість реалізацій перевищує сотню. Треба враховувати, що така велика кількість розрахунків доцільна лише для розріджених графів (не з великою кількістю робіт). Це головний недолік цього методу.
Як вже згадувалося вище при моделюванні тривалість критичного шляху Lкр, ранні і пізні терміни здійснення подій є випадковими величинами, імовірності характеристики яких треба з’ясувати.
3.2 Знаходження характеристик вибіркового розподілу