Кога се използват стохастичните модели? Основи на стохастиката. стохастични модели. Важен вид знаково моделиране е математическото моделиране, основано на факта, че различни обекти и явления, които се изучават, могат да имат еднакви

МАТЕМАТИЧЕСКИ МОДЕЛИ

2.1. Формулиране на проблема

Детерминистични моделиописват процесите в детерминистиченсистеми.

Детерминирани системисе характеризират с едно към едно съответствие (съотношение) между входните и изходните сигнали (процеси).

Ако входният сигнал на такава система е даден, неговата характеристика y \u003d F (x), както и състоянието му в началния момент, са известни, тогава стойността на сигнала на изхода на системата по всяко време е еднозначно определени (фиг. 2.1).

Съществува два подходакъм изучаването на физически системи: детерминистичен и стохастичен.

Детерминистичен подходсе основава на прилагането на детерминистичен математически модел на физическа система.

Стохастичен подходпредполага използването на стохастичен математически модел на физическа система.

Стохастичен математически моделнай-адекватно (достоверно) отразява физическите процеси в една реална система, функционираща под въздействието на външни и вътрешни случайни фактори (шум).

2.2. Случайни фактори (шум)

Вътрешни фактори −

1) температурна и времева нестабилност на електронните компоненти;

2) нестабилност на захранващото напрежение;

3) шум от квантуване в цифрови системи;

4) шум в полупроводникови устройства в резултат на неравномерните процеси на генериране и рекомбинация на основните носители на заряд;

5) топлинен шум в проводниците поради термично хаотично движение на носители на заряд;

6) ударен шум в полупроводници, дължащ се на случайния характер на процеса на преодоляване на потенциалната бариера от носители;

7) трептене - шум, причинен от бавни произволни колебания във физичното и химичното състояние на отделни участъци от материали на електронни устройства и др.

Външен фактори –

1) външни електрически и магнитни полета;

2) електромагнитни бури;

3) смущения, свързани с работата на промишлеността и транспорта;

4) вибрации;

5) влияние на космическите лъчи, топлинното излъчване на околните обекти;

6) колебания в температурата, налягането, влажността на въздуха;

7) запрашен въздух и др.

Влиянието (наличието) на случайни фактори води до една от ситуациите, показани на фиг. 2.2:

ОТ Следователно предположението за детерминистичния характер на една физическа система и нейното описание чрез детерминистичен математически модел е идеализиране на реалната система.Всъщност имаме ситуацията, изобразена на фиг. 2.3.

Допуска се детерминистичен моделв следните случаи:

1) влиянието на случайните фактори е толкова незначително, че пренебрегването им няма да доведе до забележимо изкривяване на резултатите от симулацията.

2) детерминистичният математически модел отразява реални физически процеси в осреднен смисъл.

При тези задачи, при които не се изисква висока точност на резултатите от симулацията, предпочитание се дава на детерминиран модел. Това се обяснява с факта, че прилагането и анализът на детерминистичен математически модел е много по-прост от стохастичния.

Детерминиран модел неприемливов следните ситуации: случайните процеси ω(t) са съизмерими с детерминираните x(t). Резултатите, получени с помощта на детерминистичен математически модел, ще бъдат неадекватни на реалните процеси. Това се отнася за радарни системи, системи за насочване и контрол. самолет, комуникационни системи, телевизия, навигационни системи, всякакви системи, които работят със слаби сигнали, в електронни управляващи устройства, в прецизни измервателни уреди и др.

В математическото моделиране случаен процесчесто се разглежда като случайна функция на времето, чиито моментни стойности са случайни променливи.

2.3. Същността на стохастичния модел

Набори от стохастични математически модели вероятностни връзки между входа и изхода на системата. Този модел дава възможност за статистически заключения за някои вероятностни характеристики на изследвания процес y(t):

1) очаквана стойност (означава):

2) дисперсия(мярка за дисперсия на стойностите на произволен процес y(t) спрямо средната му стойност):

3) стандартно отклонение:

(2.3)

4) корелационна функция(характеризира степента на зависимост - корелация - между стойностите на процеса y(t), разделени една от друга с време τ):

5) спектрална плътностслучаен процес y(t) описва своите честотни свойства:

(2.5)

Преобразуване на Фурие.

Стохастичният модел се формира въз основа на стохастичен диференциалили стохастично диференциално уравнение.

Разграничете три вида стохастични диференциални уравнения: със случайни параметри, със случайни начални условия, със случаен входен процес (случайна дясна страна). Нека дадем пример за стохастик диференциално уравнениетрети тип:

, (2.6)

където
– добавкаслучаен процес - входен шум.

В нелинейните системи има мултипликативни шумове.

Анализът на стохастичните модели изисква използването на доста сложен математически апарат, особено за нелинейни системи.

2.4. Концепцията за типичен модел на случаен процес.Нормален (Гаус) случаен процес

При разработването на стохастичен модел е важно да се определи естеството на случаен процес
. Случайният процес може да бъде описан чрез набор (последователност) от функции на разпределение - едномерни, двумерни, ..., n-мерни или съответните плътности на разпределение на вероятностите. В повечето практически задачи те се ограничават до дефинирането на едномерни и двумерни закони за разпределение.

В някои проблеми естеството на разпределението
априори известно.

В повечето случаи, когато произволен процес
е резултат от въздействието върху физическата система на комбинация от значителен брой независими случайни фактори, се смята, че
има свойства нормален (гаус) закон на разпределение. В този случай казваме, че процесът е случаен
се заменя с него тип моделе случаен процес по Гаус. едноизмеренплътност на разпространениевероятностинормален (гаусов) случаен процес е показан на фиг. 2.4.

Нормалното (гаусово) разпределение на случаен процес има следните свойства .

1. Значителен брой случайни процеси в природата се подчиняват на нормалния (Гаус) закон за разпределение.

2. Възможност за определяне (доказване) на нормалния характер на случаен процес доста строго.

3. Когато една физическа система е изложена на комбинация от случайни фактори с различни закони на тяхното разпределение нетен ефектсе подчинява на нормалния закон за разпределение ( централна гранична теорема).

4. При преминаване през линейна система нормалният процес запазва свойствата си, за разлика от други случайни процеси.

5. Стохастичен процес на Гаус може да бъде напълно описан с две характеристики − математическо очакванеи дисперсия.

AT по време на процеса на моделиране често възниква проблемът - определят характера на разпределениетонякаква случайна променлива x според резултатите от множеството й измервания (наблюдения)
. За това правят хистограма– стъпкова графика, която позволява въз основа на резултатите от измерването на случайна променлива да се оцени нейната плътност на разпределение на вероятностите.

При конструиране на хистограма диапазонът от стойности на случайна променлива
се разделят на определен брой интервали и след това се изчислява честотата (процентът) на данните, попадащи във всеки интервал. По този начин хистограмата показва честотата на удряне на стойностите на случайна променлива във всеки от интервалите. Ако конструираната хистограма се апроксимира чрез непрекъсната аналитична функция, тогава тази функция може да се разглежда като статистическа оценка на неизвестна теоретична плътност на разпределение на вероятностите.

При формиране непрекъснати стохастични моделиизползва се концепция "случаен процес".Разработчици различни стохастични моделиоперират с концепцията "случайна последователност".

Специална роля в теорията на стохастичното моделиране играе Марков случайни последователности.За тях е валидна следната връзка за условната плътност на вероятността:

От това следва, че вероятностният закон, описващ поведението на процеса в даден момент , зависи само от предишното състояние на процеса в момента
и абсолютно не зависи от поведението му в миналото (т.е. в моменти от времето
).

Вътрешните и външните случайни фактори (шум), изброени по-горе, са случайни процеси от различни класове. Други примери за случайни процеси са турбулентни потоци на течности и газове, промяна в натоварването на енергийна система, която захранва голям брой потребители, разпространение на радиовълни при наличие на случайно затихване на радиосигнали, промяна в координатите на частица в брауново движение, процеси на повреда на оборудването, получаване на заявки за поддръжка, разпределение на броя на частиците в малък обем колоиден разтвор, което определя влиянието в системите за радарно проследяване, процеса на термоемисия от металната повърхност и др. .

Стохастично диференциално уравнение(SDE) - диференциално уравнение, в което един или повече термини са със стохастичен характер, тоест представляват стохастичен процес (друго име е случаен процес). Така решенията на уравнението също се оказват стохастични процеси. Най-известният и често използван пример за SDE е уравнение с член, описващ бял шум (който може да се разглежда като пример за производна на процес на Винер). Съществуват обаче и други видове случайни колебания, като например процес на скок.

История

В литературата първото използване на SDE традиционно се свързва с работата по описанието на Брауновото движение, направена независимо от Мариан Смолуховски (ж.) и Алберт Айнщайн (ж.). SDE обаче са използвани малко по-рано (г.) от френския математик Луи Бушелие в неговата докторска дисертация „Теория на предположенията“. Въз основа на идеите на тази работа френският физик Пол Ланжевен започва да прилага SDE в своята работа по физика. По-късно той и руският физик Руслан Стратонович разработват по-строга математическа обосновка за SDE.

Терминология

Във физиката SDE традиционно се записват под формата на уравнението на Langevin. И често, не съвсем точно, се нарича самото уравнение на Ланжевен, въпреки че SDE може да бъде написано по много други начини. SDE под формата на уравнението на Langevin се състои от обикновено нестохастично диференциално уравнение и допълнителна част, описваща бял шум. Втората често срещана форма е уравнението на Фокер-Планк, което е частично диференциално уравнение и описва еволюцията на плътността на вероятността във времето. Третата форма на SDE е по-често използвана в математиката и финансовата математика, тя наподобява уравненията на Langevin, но се записва с помощта на стохастични диференциали (вижте подробностите по-долу).

Стохастично смятане

Позволявам T > 0 (\displaystyle T>0), остави

μ: R n × [0, T] → R n; (\displaystyle \mu:\mathbb (R) ^(n)\times \to \mathbb (R) ^(n);) σ: R n × [0, T] → R n × m; (\displaystyle \sigma:\mathbb (R) ^(n)\times \to \mathbb (R) ^(n\times m);) E[ | Z | 2]< + ∞ . {\displaystyle \mathbb {E} {\big [}|Z|^{2}{\big ]}<+\infty .}

След това стохастичното диференциално уравнение за дадени начални условия

d X t = μ (X t , t) d t + σ (X t , t) d B t (\displaystyle \mathrm (d) X_(t)=\mu (X_(t),t)\,\mathrm (d) t+\sigma (X_(t),t)\,\mathrm (d) B_(t))за t ∈ [0, T]; (\displaystyle t\in ;) X t \u003d Z; (\displaystyle X_(t)=Z;)

има уникален (в смисъл на "почти вероятно") и t (\displaystyle t)- непрекъснато решение (t , ω) ∣ → X t (ω) (\displaystyle (t,\omega)\shortmid \!\до X_(t)(\omega)), така че X (\displaystyle X)- адаптиран процес за филтриране F t Z (\displaystyle F_(t)^(Z)), генериран Z (\displaystyle Z)и B s (\displaystyle B_(s)), s ≤ t (\displaystyle s\leq t), и

E [ ∫ 0 T | X t | 2dt]< + ∞ . {\displaystyle \mathbb {E} \left[\int \limits _{0}^{T}|X_{t}|^{2}\,\mathrm {d} t\right]<+\infty .}

Приложение на стохастичните уравнения

Физика

Във физиката SDE често се записват под формата на уравнението на Langevin. Например SDE система от първи ред може да бъде написана като:

x ˙ i = d x i d t = f i (x) + ∑ m = 1 n g i m (x) η m (t) , (\displaystyle (\dot (x))_(i)=(\frac (dx_(i))( dt))=f_(i)(\mathbf (x))+\sum _(m=1)^(n)g_(i)^(m)(\mathbf (x))\eta _(m)( T))

където x = ( x i | 1 ≤ i ≤ k ) (\displaystyle \mathbf (x) =\(x_(i)|1\leq i\leq k\))- набор от неизвестни, f i (\displaystyle f_(i))и са произволни функции, и η m (\displaystyle \eta _(m))са случайни функции на времето, които често се наричат шумови термини. Тази нотация се използва, защото има стандартна техника за преобразуване на уравнение с по-високи производни в система от уравнения от първи ред чрез въвеждане на нови неизвестни. Ако g i (\displaystyle g_(i))са константи, казваме, че системата е обект на адитивен шум. Ние също така разглеждаме системи с мултипликативен шум, когато g (x) ∝ x (\displaystyle g(x)\propto x). От двата разглеждани случая адитивният шум е по-простият. Решението за система с адитивен шум често може да бъде намерено само с помощта на методите на стандартното смятане. По-специално може да се използва обичайният метод за съставяне на неизвестни функции. Въпреки това, в случай на мултипликативен шум, уравнението на Ланжевен е слабо дефинирано в смисъла на обикновения математически анализ и трябва да се тълкува от гледна точка на смятането на Ито или смятането на Стратонович.

Във физиката основният метод за решаване на SDE е да се намери решение под формата на вероятностна плътност и да се трансформира оригиналното уравнение в уравнението на Фокер-Планк. Уравнението на Фокер-Планк е частично диференциално уравнение без стохастични членове. То определя еволюцията във времето на плътността на вероятността, точно както уравнението на Шрьодингер определя зависимостта от времето на вълновата функция на система в квантовата механика или уравнението на дифузията определя еволюцията във времето на химическата концентрация. Решенията могат да се търсят и числено, например чрез метода Монте Карло. Други техники за намиране на решения използват интеграла по пътя, тази техника се основава на аналогията между статистическата физика и квантовата механика (например уравнението на Фокер-Планк може да се трансформира в уравнението на Шрьодингер с помощта на някаква трансформация на променливи) или решението на обикновени диференциални уравнения за моменти на плътност на вероятността.

Връзки

Стохастичен свят - просто въведение в стохастичните диференциални уравнения

Литература

Адомиан, Джордж.Стохастични системи (неопр.) . - Орландо, Флорида: Academic Press Inc., 1983. - (Математика в науката и инженерството (169)).
Адомиан, Джордж.Нелинейни стохастични операторни уравнения (неопр.) . - Орландо, Флорида: Academic Press Inc., 1986.
Адомиан, Джордж.Теория на нелинейните стохастични системи и приложения във физиката. - Dordrecht: Kluwer Academic Publishers Group, 1989. - (Математиката и нейните приложения (46)). (Английски)

Математически схеми за описание на технически системи

Обща класификация на системните модели

Нарича се всичко, към което е насочена човешката дейност обект . Определяйки ролята на теорията на моделирането в процеса на изучаване на обекти и следователно на техните модели, е необходимо да се абстрахираме от тяхното разнообразие и да подчертаем общите черти, които са присъщи на модели на обекти, които са различни по природа. Този подход доведе до появата на обща класификация на системните модели.

Създадените системни модели се класифицират:

· по време

* динамични модели: непрекъснати, които се описват с диференциални уравнения; дискретно-непрекъснати (разностни), описват се с диференциални уравнения; вероятностни, изградени върху събития - модели на теорията на масовото обслужване;

* дискретни модели - автомати;

· по избор:

* детерминистични - модели, отразяващи процеси, в които няма случайни въздействия;

* стохастични - модели отразяващи вероятностни процеси и събития;

· по уговорка:

· по вид на обработваната информация:

* информация: - справочно-информационна;

Информация и консултиране;

Експерт;

Автоматично;

* физически модели: - естествени (плазма);

Полу-естествени (аеродинамични тунели);

* симулационни модели;

* интелигентни модели;

* семантични (логически) модели;

Нека да преминем към разглеждането на основните типове математически схеми.

1.3.1. Непрекъснато детерминирани модели (D - схеми)

Математическите схеми от този вид отразяват динамикапроцеси, протичащи във времето в системата. Затова се наричат D-схеми. Специален случай на динамичните системи са автоматични системи за управление.

Линейна автоматична система се описва с линейно диференциално уравнение от вида

където x(t)- настройка на действие или входна променлива на системата; y(t)- състояние на системата или изходна променлива; - коефициенти; T- време.

Фигура 1 показва увеличена функционална схема на системата за автоматично управление, където е сигналът за грешка; - контролно действие; f(t)- смущаващо влияние. Тази система се основава на принципа на отрицателната обратна връзка, тъй като за намаляване на изходната променлива y(t)спрямо зададената му стойност се използва информация за отклонението между тях. Съгласно него е възможно да се разработи блокова диаграма и математически модел под формата на предавателна функция или под формата на диференциално уравнение (1.1), в което за простота се приема, че точките на приложение на смущаващите влияния съвпадат с входа на системата.

Фиг.1.1. Структура на системата за автоматично управление

Непрекъснато детерминирани вериги (D-вериги) се изпълняват на аналогови компютри (ACM).

1.3.2. Дискретно-детерминирани модели (F - схеми)

Основният тип дискретно-детерминирани модели е крайна машина.

държавна машинанаречен дискретен преобразувател на информация, способен да преминава от едно състояние в друго под въздействието на входни сигнали и да генерира сигнали на изхода. Това е автоматик с памет. Да организира паметта, автоматизираното време и концепцията състояние на машината.

Концепцията за " състояние"автомат означава, че изходният сигнал на автомата зависи не само от входните сигнали в даден момент, но също така взема предвид входните сигнали, идващи по-рано. Това позволява времето да бъде елиминирано като изрична променлива и изходите да бъдат изразени като функция на състояния и входове.

Всеки преход на автомата от едно състояние в друго е възможен не по-рано от дискретен интервал от време. Освен това, самият преход се счита за мигновен, т.е. преходните процеси в реалните вериги не се вземат предвид.

Има два начина за въвеждане на автоматното време, според които автоматите се делят на синхронени асинхронен.

AT синхроненВ автоматите моментите от време, в които се записват промените в състоянията на автомата, се задават от специално устройство - генератор на часовников сигнал. Освен това сигналите пристигат на равни интервали от време - . Честотата на тактовия генератор е избрана така, че всеки елемент на автомата да има време да завърши работата си, преди да се появи следващият импулс.

AT асинхроненВ автомата моментите на преход на автомата от едно състояние в друго не са предварително определени и зависят от конкретни събития. В такива автомати интервалът на дискретност е променлив.

Също така има детерминистичени вероятностенавтомати.

AT детерминистиченавтомати, поведението и структурата на автомата във всеки момент от времето се определят еднозначно от текущата входна информация и състоянието на автомата.

AT вероятностенавтомати, те зависят от произволен избор.

Абстрактно един краен автомат може да бъде представен като математическа схема (F - схема), която се характеризира с шест вида променливи и функции:

1) крайно множество x(t)входни сигнали (входна азбука);

2) крайно множество y(t)изходни сигнали (изходна азбука);

3) крайно множество z(t)вътрешни състояния (азбука на състоянията);

4) начално състояние на автомата z0 , ;

5) функцията на автоматичните преходи от едно състояние в друго;

6) функцията на изходите на машината.

Абстрактен краен автомат има един вход и един изход. Във всеки отделен момент от време t=0,1,2,... F– машината е в определено състояние z(t)от много З– състояния на автомата, и в началния момент от времето t=0винаги е в първоначалното си състояние z(0)=z0. В момента T, е в състояние z(t), автоматът е в състояние да възприеме сигнала на входния канал и да издаде сигнала на изходния канал, преминавайки в състояние

Абстрактен краен автомат реализира някакво картографиране на набора от думи във входната азбука хв набор от думи в изходната азбука Y, т.е. ако входът на крайната машина е зададен в първоначалното състояние z0, дайте в някаква последователност буквите от входната азбука, които съставят входната дума, тогава на изхода на автомата последователно ще се появят буквите от изходната азбука, образуващи изходната дума.

Следователно работата на крайния автомат се извършва по следната схема: на всеки T– ти цикъл към входа на автомата, който е в състояние z(t), се дава някакъв сигнал x(t), на което автоматът реагира с превключване към (t+1)–ом такт към ново състояние z(t+1)и дава някакъв изходен сигнал.

В зависимост от това как е дефиниран изходният сигнал, синхронните абстрактни крайни автомати се разделят на два типа:

F е автомат от първи вид, наричан още Мили машина :

F - автомат от втори вид:

Автомат от втори вид, за който

Наречен Машина на Мур – функцията на изходите не зависи от входната променлива x(t).

За да се зададе краен F-автомат, е необходимо да се опишат всички елементи на множеството.

Има няколко начина за настройка на работата на F - автоматите, сред които най-широко използваните са табличен, графичен и матричен.

1.3.3. Дискретно-непрекъснати модели

Процесите в линейни импулсни и цифрови автоматични системи за управление се описват с дискретно-разностни уравнения от вида:

където x(n)е решетъчната функция на входния сигнал; y(n)е решетъчната функция на изходния сигнал, която се определя от решението на уравнение (1.2); b kса постоянни коефициенти; - разлика да се-та поръчка; t=nT, където nt – н-ти момент във времето Tе дискретният период (в израз (1.2) условно се приема за единица).

Уравнение (1.2) може да бъде представено в друга форма:

Уравнение (1.3) е рекурсивна връзка, която ви позволява да изчислите всяко (i+1)-тият член на редицата по стойностите на предишните й членове аз, аз-1,...и смисъл x(i+1).

Основният математически инструмент за моделиране на цифрови автоматични системи е Z-преобразуването, което се основава на дискретното преобразуване на Лаплас. За да направите това, е необходимо да намерите функцията за предаване на импулси на системата, да зададете входната променлива и чрез промяна на параметрите на системата можете да намерите най-добрата версия на проектираната система.

1.3.4. Дискретно - стохастични модели (P - схеми)

Дискретно-стохастичният модел включва вероятностен автомат. Най-общо вероятностният автомат е дискретен поетапен преобразувател на информация с памет, чието функциониране на всяка стъпка зависи само от състоянието на паметта в него и може да бъде описано статистически. Поведението на автомата зависи от произволния избор.

Използването на схеми на вероятностни автомати е важно за проектирането на дискретни системи, в които се проявява статистически редовно случайно поведение.

За P-автоматът се въвежда подобна математическа концепция, както за F-автомат. Да разгледаме множество G, чиито елементи са всички възможни двойки (x i,z s), където x iи z sелементи на входно подмножество хи подмножества от състояния Зсъответно. Ако има две такива функции и тази карта и се изпълняват с тяхна помощ, тогава се казва, че дефинира автомат от детерминиран тип.

Преходната функция на вероятностен автомат определя не едно конкретно състояние, а разпределението на вероятността върху набор от състояния

(автомат със случайни преходи). Изходната функция също е вероятностно разпределение на множеството изходни сигнали (автомат със случайни изходи).

За да опишем вероятностен автомат, въвеждаме по-обща математическа схема. Нека Φ е множеството от всички възможни двойки на формата (z k,y j), където y jе елемент от изходното подмножество Y. След това изискваме всеки елемент от набора Жиндуциран върху множеството Φ някакъв закон на разпределение от следния вид:

елементи от е...

къде са вероятностите за преминаване на автомата в състояние з ки появата на сигнал на изхода y jако можеше z sи в този момент на входа му е получен сигнал x i.

Броят на такива разпределения, представени под формата на таблици, е равен на броя на елементите на множеството G. Ако означим това множество от таблици с B, тогава четирите елемента се наричат вероятностен автомат (P - автоматичен). При което .

Специален случай на P-автомат, дефиниран като автомати, в които или преходът към ново състояние, или изходният сигнал се определят детерминистично ( Z е детерминиран вероятностен автомат, Y е детерминиран вероятностен автоматсъответно).

Очевидно, от гледна точка на математическия апарат, задаването на Y - детерминиран P - автомат е еквивалентно на задаването на някаква верига на Марков с краен набор от състояния. В тази връзка апаратът на веригите на Марков е основният при използване на P-схеми за аналитични изчисления. Подобни P-автомати използват генератори на последователности на Марков, когато конструират процесите на функциониране на системи или влияния на околната среда.

Марковски последователности, съгласно теоремата на Марков, е последователност от случайни променливи, за които изразът

където N е броят на независимите тестове; Д--дисперсия.

Такива P-автомати (P-схеми) могат да се използват за оценка на различни характеристики на изследваните системи както за аналитични модели, така и за симулационни модели, като се използват методи за статистическо моделиране.

Y - детерминираният P-автомат може да бъде определен от две таблици: преходи (Таблица 1.1) и изходи (Таблица 1.2).

Таблица 1.1

Където P ij е вероятността за преминаване на P-автомата от състояние z i в състояние z j , докато .

Таблица 1.1 може да бъде представена като квадратна матрица с размерност . Ще наречем такава маса матрица на вероятността за преходили просто преходна матрица на P-автомат, което може да бъде представено в компактна форма:

За да се опише Y-детерминираният P-автомат, е необходимо да се зададе първоначалното вероятностно разпределение на формата:

З...	z1	z2	...	z k-1	з к
Д...	d1	d2	...	dk-1	dk

където d k е вероятността в началото на работата P-автоматът да е в състояние z k , докато .

И така, преди началото на работа, P-автоматът е в състояние z 0 и в началната (нулева) времева стъпка променя състоянието в съответствие с разпределението D. След това промяната в състоянията на автомата се определя от преходната матрица P. Като се има предвид z 0, размерността на матрицата Р р трябва да се увеличи до , докато първият ред на матрицата ще бъде (d 0,d 1,d 2,...,dk), а първата колона ще бъде нула.

Пример. Y-детерминираният P-автомат е даден от таблицата на прехода:

Таблица 1.3

и изходна таблица

Таблица 1.4

З	z0	z1	z2	z3	z4
Y

Като се има предвид таблица 1.3, графиката на преходите на вероятностен автомат е показана на фиг. 1.2.

Изисква се да се оценят общите крайни вероятности този автомат да бъде в състояние z 2 и z 3 , т.е. когато на изхода на машината се появят единици.

Ориз. 1.2. Графика на прехода

С аналитичен подход могат да се използват известни отношения от теорията на веригите на Марков и да се получи система от уравнения за определяне на крайните вероятности. Освен това първоначалното състояние може да бъде игнорирано, тъй като първоначалното разпределение не влияе на стойностите на крайните вероятности. Тогава таблица 1.3 ще приеме формата:

където е крайната вероятност Y-детерминираният P-автомат да е в състояние з к.

В резултат на това получаваме система от уравнения:

Към тази система трябва да се добави условието за нормализиране:

Сега, решавайки системата от уравнения (1.4) заедно с (1.5), получаваме:

Така при безкрайна работа на даден автомат на изхода му ще се формира двоична последователност с вероятност за поява единица, равна на: .

В допълнение към аналитичните модели под формата на P-схеми могат да се използват и симулационни модели, реализирани например чрез метода на статистическото моделиране.

1.3.5. Непрекъснати стохастични модели (Q-схеми)

Ще разгледаме такива модели, като използваме примера за използване на системи за масово обслужване като типични математически схеми, които се наричат Q– схеми . Такива Q-схеми се използват при формализирането на процесите на функциониране на системите, които по същество са процеси обслужване.

Да се обслужващи процесимогат да бъдат приписани: потоци от доставки на продукти до определено предприятие, потоци от части и компоненти на поточната линия на цех, приложения за обработка на компютърна информация от отдалечени терминали на компютърна мрежа. Характерна особеност за функционирането на такива системи или мрежи е случайното появяване на заявки за услуги. Освен това във всеки елементарен сервизен акт могат да се разграничат два основни компонента: очакването на услугата и всъщност процесът на обслужване на самото приложение. Нека го представим под формата на някое i-то сервизно устройство P i (фиг. 1.3), състоящо се от акумулатор на заявки Н i , в който могат да има едновременно приложения; K i – канал за обслужване на приложението.

Всеки елемент на устройството P i получава потоци от събития, поток от заявки влиза в акумулатора H i , а поток от услуга AND i влиза в канала K i .

Фиг.1.3. Устройство за поддръжка

Потоците от събития могат да бъдат хомогенен, ако се характеризира само с последователността на пристигането на тези събития (), или разнородни, ако се характеризира с набор от атрибути на събитието, например такъв набор от атрибути: източник на заявки, наличие на приоритет, възможност за обслужване на един или друг тип канал и др.

Обикновено, когато се моделират различни системи по отношение на канала K i, може да се приеме, че потокът от заявки на входа K i образува подмножество от неконтролирани променливи, а потокът на услугата AND i образува подмножество от контролирани променливи.

Тези заявки, които по различни причини не се обслужват от канала Ki, формират изходящия поток Y i.

Тези модели могат да бъдат класифицирани като оптимални стохастични модели.

В много случаи при изграждането на модел не всички условия са известни предварително. Ефективността на намирането на модел тук ще зависи от три фактора:

Поставете условия x 1 , x 2 ,..., x n;

неизвестни условия y 1 ,y 2 ,...,yk;

Фактори под наш контрол и 1, и 2,...,и m,да бъде намерен.

Индикаторът за ефективност за решаване на такъв проблем има формата:

Наличие на неизвестни фактори y iтрансформира оптимизационния проблем в проблем за избор на решение при несигурност. Задачата става изключително трудна.

Задачата е особено сложна за случаите, когато количествата y iнямат статистическа стабилност, тоест неизвестни фактори y iне могат да бъдат изследвани със статистически методи. Техните закони за разпределение или не могат да бъдат получени, или изобщо не съществуват.

В тези случаи комбинациите от възможни стойности на Y се разглеждат по такъв начин, че да се получат както "най-добрите", така и "най-лошите" комбинации от променливи стойности. y i.

След това се разглежда като критерий за оптимизация.

Стохастичните модели описват случайни процеси или ситуации, като се разбира, че случайността на определени явления се изразява чрез вероятност. Точно като детерминистичните модели, стохастичните модели могат да бъдат дискретни и непрекъснати.

Непрекъснати стохастични модели

Основната схема на формализирано описание на системи, които се характеризират с

1) непрекъснатият характер на промяната във времето и

2) наличието на случайност в поведението,

служи като апарат на системите за масово обслужване. Тоест, това е план от математически схеми, предназначени да формализират процесите на функциониране на системите, които са обслужващи процеси. Именно за такива системи стохастичният характер на работа (случайна поява на заявки за услуга), завършване на услугата в произволни моменти, наличие на входен и изходящ поток от заявки, наличие на сервизни устройства, поток от събития, съществуване на опашка за обслужване, определяне на определен ред на обслужване и др.

Както се вижда от описанието на модели от този вид, непрекъснато-стохастичните модели не ни подхождат.

Дискретни стохастични модели

Този тип модел е подходящ за тези обекти, които имат следните характеристики:

времето в тях е дискретно

те показват статично редовно произволно поведение.

Съгласно тази дефиниция, нашият модел напълно отговаря на описанието на дискретните стохастични модели: по условието нашето време е дискретно и заключихме, че има случайност в модела. Модели на системи от този вид могат да бъдат изградени на базата на две формализирани схеми за описание:

Уравнения с крайни разлики, сред променливите на които са функции, които определят случайни процеси

Вероятностни автомати

„Вероятностният автомат е дискретен преобразувател на информация, който има повече от едно състояние, чието функциониране във всеки цикъл зависи само от състоянието на паметта в него и може да бъде описано статично“ 3

Задаването на вероятностни автомати се извършва в таблици или с помощта на графики, но използването им на практика е възможно само чрез внедряване на симулационен модел на компютър (с изключение на малки и прости модели, в които са възможни и аналитични изчисления).

Нека проверим възможността за прилагане на вероятностни автомати към нашия модел:

В нашия модел има случайност, но възможно ли е да се изчисли законът за разпределение?

1.В случай на случайна цена?

Да, това е равномерно разпределение и вероятностите за всички състояния са равни при определяне на цената.

При произволно разпределение на непродадени продукти?

Това отново е равномерно разпределение и вероятностите могат да бъдат намерени.

Да видим какви входни състояния може да приеме системата... Оказва се, че има безкрайно много такива състояния, следователно е невъзможно да се изгради вероятностен автомат. Ами ако има ограничения за обема на продукцията? Това множество ще бъде ограничено и може да бъде построен вероятностен автомат, но полученият модел, както в случая с предположението, че системата е детерминистична, ще отразява лошо реалността. Следователно ще се откажем от конструирането на вероятностен автомат.

В случай на дискретно-стохастична схема на формализирано описание най-удобното решение е решението на проблема с помощта на уравнения с крайни разлики.

Досега разглеждахме модели с детерминирана мрежова топология. Когато се моделира сложен проект, мрежовите модели със стохастична структура често са най-гъвкави и полезни. Стохастичната мрежа се дефинира като мрежа, съдържаща алтернативни възли (състояния), докато дъгите (работите) се характеризират не само с вероятностното разпределение на продължителността, но и с вероятността за тяхното изпълнение.

Стохастичният мрежов модел с много възможни резултати, като по-нататъшно развитие на традиционните мрежи, дава възможност за по-пълно отразяване на процеса на разработване и създаване на сложен проект. Математическият апарат, използван за анализ на стохастични мрежови модели, позволява да се изчислят вероятностите за различни алтернативни резултати и да се оцени времето за тяхното възможно реализиране.

Стохастичният мрежов модел е краен граф G=(W,A), където W е набор от детерминистични и алтернативни върхове, идентифицирани със събития, а технологичната матрица A=(p ij ) дефинира набора от ориентирани дъги, идентифицирани със задачи ( или връзки). За стохастични мрежи 0 £ p ij £ 1 и p ij =1 дефинира работата (i,j) подобно на определенията, приети в традиционните мрежи, и

0 < p ij < 1 соответствует альтернативному событию i, из которого с вероятностью p ij «выходит» работа (i,j). Другими словами p ij – вероятность того, что работа (i,j) будет выполнена при условии, что узел i выполнен.

Нека j(t ij) е плътността на разпределението на времето за изпълнение на работата (i,j). M[x] е математическото очакване на случайна променлива x.

Условната генерираща функция на моментите на случайната величина t ij се въвежда като М ij (s)=М[е st ij ], т.е.

M ij (s)= ò e st ij j(t ij)dt ij (за непрекъсната случайна променлива),

е st ij j(t ij) (за дискретна случайна променлива).

По-специално, М ij (s)=М[е sа ] = e sа при t ij =а=const, М ij (0)=1.

За всяка дъга (i,j) Y-функцията се дефинира като

Y ij (s) = p ij М ij (s).

Оригиналната мрежа се преобразува в еквивалентна мрежа с помощта на три основни трансформации:

последователни дъги,

Успоредни дъги

За последователни дъги (фиг. 7)

Y ik (s) = Y ij (s) Y jk (s).

За успоредни дъги (фиг. 8)

Y ij (s) = Y a (s) + Y b (s).

За контури за изглед (фиг. 9)

Y ij (s) = Y b (s)/.

Чрез комбиниране на основни трансформации всяка мрежа може да се трансформира в еквивалентна мрежа, състояща се от една дъга (E-дъга).

Целта на анализа на времето на стохастична мрежа е да се изчисли математическото очакване и дисперсията на времето за изпълнение на мрежата (или някой от нейните фрагменти) и вероятността за изпълнение на крайното (или всяко друго събитие) на мрежата.

Тук се използва теорията на затворените графики на потока, където Y-функцията, въведена по-горе, се интерпретира като съответния коефициент на пропускливост на дъгата. За да се приложат резултатите от тази теория към отворена мрежа с желания параметър Y E (s), се въвежда допълнителна дъга с параметър Y A (s), свързваща крайното събитие (мивка) с първоначалното (източник).

Тогава се използва топологичното уравнение за затворени графи, известно като правилото на Мейсън, със следната форма:

1 – åT(L 1) + åT(L 2) – åT(L 3) +…+ (-1) m åT(L m) + … =0, (10)

където åT(L m) е сумата от еквивалентните коефициенти на пропускливост за всички възможни вериги от m-ти ред.

Еквивалентният коефициент на пропускане за цикъла от m-ти ред е равен на произведението на коефициентите на пропускане m несвързанибримки от първи ред, т.е.

T(L m)=Õ m k=1 T k .

От правилото на Мейсън следва директно, че 1–Y A (s)Y E (s)=0 или Y A (s)=1/Y E (s). Използвайки този резултат, в топологичното уравнение (10) Y A (s) се заменя с 1/Y E (s) и след това се решава по отношение на Y E (s), като по този начин се получава еквивалентна Y-функция за оригиналната стохастична мрежа.

Тъй като Y E (s) \u003d p E M E (s) и M E (0) \u003d 1, тогава p E \u003d Y E (0), което означава, че

M E (s) = Y E (s)/p E = Y E (s) / Y E (0). (единадесет)

След получаване на аналитичен израз за M E (s), изчислете първата и втората частни производни по отношение на s на функцията M E (s) в точката s=0, т.е.

m 1E =¶/¶s[M E (s)] s=0 (12)

m 2E =¶ 2 /¶s 2 [M E (s)] s=0 (13)

Първият момент m 1E спрямо началото е математическото очакване на времето за изпълнение на мрежата (трансформирано в неговата еквивалентна E-дъга), а дисперсията на времето за изпълнение на мрежата е равна на разликата между втория момент m 2E и квадрата от първото, т.е.

s 2 \u003d m 2E - (m 1E) 2. (четиринадесет)

По този начин описаното по-горе устройство позволява да се изчислят времевите параметри на всякакви събития от стохастична мрежа, които представляват интерес за потребителя, както и да се определи вероятността за тяхното възникване.

Използвайки получената информация, използвайки неравенството на Чебишев, е възможно да се оцени вероятността от всякакви доверителни интервали за завършване на проекта за произволни закони за разпределение за изпълнение на отделни операции. Ако времето за изпълнение на всяка операция е нормално разпределено, тогава полученото време също е нормално разпределено. В този случай е възможно да се получат вероятностни оценки на времето за изпълнение на проекта, като се използва интегралната теорема на Moivre-Laplace. В допълнение, при достатъчно голям брой работни места в мрежата и изпълнението на определени условия (по-специално независимостта на работните места), можем да използваме граничната теорема на Ляпунов и да разгледаме полученото време за изпълнение на проекта като нормално разпределена случайна променлива с характеристики, изчислени по гореописания метод.

Така стохастичният мрежов модел включва всички случайни отклонения и несигурност, които възникват директно по време на изпълнението на всяка отделна работа.

3.4. Формализация на общата постановка на задачата за планиране на работата в управлението на проекти и описание на универсалния мрежов модел и задачите на времевия анализ, решени на негова основа

В резултат на анализа и синтеза на горните модели е предложен универсален математически модел, а класическите, обобщените и стохастичните мрежови модели са негови частни случаи.

Този модел (наз цикличен стохастичен мрежов модел - CSSM) е по-гъвкав и адекватен инструмент за описание на процеса на управление на развитието на сложен проект.

CSSM е краен, ориентиран, цикличен граф G(W,A), състоящ се от набор от събития W и дъги (i,j)(събития i, jOW), определени от матрицата на съседство A=(p ij). 0Ј p ij Ј1 и p ij =1 дефинира детерминирана дъга (i,j) и 0< p ij <1 определяет альтернативное событие i, которое с вероятностью p ij связано дугой с событием j. Множество дуг подразделяется на дуги-работы и дуги-связи. Первые реализуют определенный объем производственной деятельности во времени, второй тип дуг отражает исключительно логические связи между последними. Событиями могут быть как начала и окончания выполняемых работ, так некоторые их промежуточные состояния.

Означаваме с T i времето на завършване на i-тото събитие, тогава съотношението между времето за завършване на събитията, свързани с дъгата (i, j), се дава от неравенството:

Т j – Т i і y ij , (15)

където y ij обикновено е случайна променлива, разпределена по някакъв закон в диапазона от –Ґ до 0 или от 0 до +Ґ.

Освен това са възможни абсолютни ограничения по време на изпълнение на събитието i:

l i Ј Т i ЈL i . (16)

Релациите (15)-(16) са обобщение на съответните неравенства при описанието на обобщени мрежови модели, където параметърът y ij и матрицата на съседство A са детерминирани.

Разгледайте семантичното натоварване на връзката (15) с вероятностния характер на параметъра y ij .

Ако (i,j) е дъгова работа (или част от нея), тогава положително разпределена случайна променлива y ij определя разпределението на минималната продължителност на тази работа (свързана с максималната й наситеност с определящия ресурс). Хартията показва, че разпределението на стойността y ij е унимодално и асиметрично и бета разпределението удовлетворява тези изисквания, по този начин, минимално време на работае случайна променлива y ij =t min (i,j), разпределена според закона за бета разпределение на сегмента [a, b] с плътност

j(t)=С(t – a) p-1 (b – t) q-1 , (17)

където C се определя от условието

Ако случайната променлива y ij в (15), съответстваща на дъговата работа (i,j), е разпределена в интервала от –Ґ до 0, тогава –y ij =t max (j,i) задава разпределението на дължината на максималния интервал от време, през който работата (i, j) трябва да започне и завърши, дори ако е минимално наситена с определящия ресурс. За това количество получихме разпределението му в подобна форма (17). Познавайки разпределението на случайната променлива y ij за всяка работа (i, j), нейното математическо очакване и дисперсия се изчисляват с помощта на подходящите формули.

Въвеждането на отрицателно разпределени стойности y ij за дъгови задачи (i,j) в (15) значително разширява възможностите за описание на времевите характеристики на работните места, което прави широко използвания вероятностен модел само един от специалните случаи.

За дъгови връзки (i,j) стойността y ij определя разпределението на времевата зависимост между събития i и j, а положително разпределената стойност y ij определя връзката от типа „не по-рано“ (събитието j не може да се случи по-рано от y ij дни след завършването на събитие i), а отрицателно разпределената стойност y ij определя връзката от типа „не по-късно от“ (събитие i може да се случи не по-късно от –y ij дни след събитието j). В последния случай такива връзки се наричат "обратни".

Така тук получихме обобщение на тези връзки, като вземем предвид техния евентуален вероятностен характер.

Тъй като времето за завършване на събития Т i се определя от сумата от продължителностите на работите, които технологично ги предшестват, тогава с достатъчно голям брой такива работи, в съответствие с централната гранична теорема, разпределението на случайната променлива Т i клони към нормата с параметрите - очакване МТ i и дисперсия DТ i . Нормалното разпределение също има параметър y ij, съответстващ на "обратните" дъги, което също се потвърждава от статистически анализ.

Абсолютните ограничения за времето на събитията, дадени с (16), отразяват съответните директивни, организационни и технологични ограничения за времето за изпълнение на работа или части от нея, дадени в "абсолютна" (реална или условна) времева скала. Абсолютните ограничения също се характеризират с типа "не по-рано" или "не по-късно" и приемат формата: T i - T 0 і l i , T 0 - T i і -L i . По този начин абсолютните ограничения на формата (16) са частен случай на ограничения на формата (15) за определени дъги-връзки.

Въвеждането на стохастична матрица на съседство A в комбинация с обобщени връзки предоставя допълнителни възможности за описание на процеса на създаване на сложен проект.

Нека L(i,j) е някакъв път, свързващ събития i и j:

L(i,j)=(i=i 0 ®i 1 ®i 2 ®…®i v =j). (осемнадесет)

Това детерминиран път, ако pi k-1 i k =1 е валиден за всички kО, и стохастичен, в противен случай. По този начин стохастичният път съдържа поне една дъга, чиято вероятност за "изпълнение" е строго по-малка от 1.

По подобен начин се определя детерминистична и стохастична веригаК(i)=(i=i 0 ®i 1 ®i 2 ®…®i v =i). (такива събития i се наричат "контур").

Ако събития i и j са свързани с път L(i,j), тогава вероятността събитие j да се случи, при условие че събитие i се е случило P(j/i), е произведението на коефициентите на матрицата на съседство A съответстващи на дъгите на свързващия път:

P(j/i)=X v k=1 p i k-1 i k. (19)

Ако събития i и j са свързани по няколко начина, тогава еквивалентната GERT трансформация на този мрежов фрагмент се извършва в съответствие с формулите, дадени в работата, изчислява се генериращата функция Y ij (s) на трансформирания фрагмент и вероятността на събитие j, при условие че събитие i се е случило P (j/i)= Y ij (0).

Първата производна на функцията Y ij (s)/ Y ij (0) по отношение на s в точката s=0 (първият момент m 1 (j/i)) определя очакването M(j/i) на време на събитието j по отношение на времето на събитието i. Второто производно на функцията Y ij (s)/ Y ij (0) по отношение на s в точката s=0 (вторият момент m 2 (j/i)) ни позволява да изчислим дисперсията на времето на събитие j по отношение на времето на събитие i по формулата

s 2 (j / i) \u003d m 2 (j / i) - (m 1 (j / i)) 2. (двадесет)

Дължината на пътя L(i,j) е случайна променлива, чието математическо очакване ML(i,j) е сумата от математическите очаквания на дължините на всички дъги, които изграждат този път, и дисперсията DL (i,j) е равно на сумата от дисперсиите.

При тези условия дължината на пътя (контурата) може да отнеме отрицателенстойности, което се тълкува по следния начин:

ако L(i,j)<0 и дуга (j,i) имеет отрицательно распределенный параметр y ji , то событие j должно свершиться не по-късноот -y ji дни след настъпването на събитие i. Параметърът y ji е с вероятностен характер, което дава възможност за по-гъвкаво (по отношение на цикличните мрежови модели) описание на логико-времевите връзки между събитията.

Като параметър на дъгата y ij може също да се разглежда всеки характерен параметър, който има адитивност по дъгите на който и да е път (например цената на работа), докато използваме еквивалентната GERT трансформация, получаваме математическото очакване и дисперсията на цената на мрежов фрагмент или проект като цяло.

Задачи на времеви анализ на CSSM (и алгоритми за тяхното решаване)както и времевият анализ на класически, обобщени или стохастични мрежови модели са в основата на решаването на всички проблеми на планирането и управлението на проекти. Те са от независимо значение при решаването на проблеми с управлението на проекти, без да се вземат предвид ограниченията на ресурсите.

Задачите на временния анализ също са необходими за генериране на различни варианти на план за определени стойности на вектора на ресурсната наличност с цел тяхното последващо сравнение, оценка на качеството на опциите на плана и избор на посока за неговото по-нататъшно подобряване.

При решаване на задачи за оптимално планиране на работата в управлението на проекти, алгоритмите за анализ на времето CSSM се използват като инструмент за изчисляване на необходимите параметри, използвани в съответните алгоритми за оптимизация, за да се гарантира изпълнението на технологичните ограничения.

Задачата на времевия анализ на CSSM се свежда до намиране на случаен вектор T=(T 0 ,T 1 ,…,T n), където T i е времето на i-тото събитие, чиито координати удовлетворяват неравенствата ( 15), (16) и превръщаме в екстремум някаква целева функция f(T).

Подчертано три класа задачи за времеви анализ:

· класически, в който за изчисляване (T i) се използват математическите очаквания на продължителността на всички дъги;

· вероятностенв който на базата на теоремата за границата на Ляпунов или други аналитични средства се изчисляват математическите очаквания за момента на завършване на i-тото събитие - (MT i ), които са аргументи на целевата функция f(T). ;

· статистически, при което за дадено ниво на надеждност p, съгласно метода, описан в статията, се определят p-квантилни оценки на емпиричните разпределения както за времето на i-тото събитие - (W p (T i)), така и за тяхното производни, включително стойности на целевата функция f(W p (T)), където W p (T)=(W p (T 0),W p (T 1),…,W p (T n)) .

Въвежда се концепцията за последователност на CSSM.

Моделът на циклична стохастична мрежа се нарича последователенако има поне един допустим план, изчислен за съответния клас задачи за времеви анализ (класически, вероятностни или статистически), който удовлетворява системата от неравенства (15), (16).

Нека да разгледаме тези три концепции.

Класическа консистенция на модела.

Изчисляват се математическите очаквания на продължителността на всички дъги, след което се формира мрежа с постоянни дължини на дъгите. Като се има предвид стохастичният характер на разглеждания модел и наличието на обобщени връзки, след горните изчисления в CSSM могат да се появят стохастични и детерминистични контури. Доказва се следната теорема:

Теорема 1 . За да може цикличният стохастичен модел, в който продължителностите на дъгите се изчисляват по класическата схема, да бъде съвместим с дадена вероятност a, е необходимо и достатъчно дължините на всички детерминистични контури да не са положителни.

Съгласуваност на вероятностния модел.

Математическото очакване на MT i и дисперсията s 2 T i на синхронизирането на събитията се изчисляват аналитично. Така изчислените параметри се различават с 15-20% по големина от тези, изчислени по класическия начин (според математическите очаквания за времетраене на дъгата).

Нека поговорим за вероятностна последователност на модела средно, ако така полученото множество удовлетворява неравенства (15)-(16), където математическото му очакване се приема като стойност на y ij. Доказана е валидността на следната теорема:

Теорема 2 . За да бъде един цикличен стохастичен модел вероятностно последователен средно, е необходимо и достатъчно математическите очаквания на дължините на всички детерминистични контури да не са положителни.

Приемайки, че Т i имат нормално разпределение с параметри: математическо очакване - МТ i и дисперсия - s 2 Т i , въвеждаме по-широко понятие за e- вероятностна последователност на модела.

Ще кажем, че CSSM е е-вероятностно последователен, ако съществува e > 0, така че за всички T i, удовлетворяващи неравенството

|T i –MT i |< e, справедливы соотношения (15)-(16). В работе доказано следующее:

Теорема 3 . За да бъде цикличният алтернативен модел е-вероятностно непротиворечив, е необходимо и достатъчно математическите очаквания на дължините на всички детерминистични контури да удовлетворяват отношението МL(K(i)) Ј –4e.

Вероятностната последователност на модела, като цяло, е специален случай на е-вероятностна последователност при e=0.

Статистическа последователност на модела.

Със статистическия метод за изчисляване на параметрите на мрежовия модел имаме работа с техните p-квантилни оценки на стойности, които са вероятностни аналози на съответните показатели. Казва се, че цикличният стохастичен модел статистически в съответствие с вероятността p, ако за всяко събитие i има p-квантилни оценки на времето на завършване на събитията W p (T i), удовлетворяващи неравенствата:

W p (Т j) – W p (Т i)і W p (y ij), (21)

l i JW p (Т i)JL i . (22)

Тук отношенията (21)-(22) са вероятностни аналози на (15)-(16), W p (y ij) е оценката на p-квантила на дължината на дъгата (i,j). Доказано е следното:

Теорема 4 . За да бъде цикличният алтернативен модел статистически съвместим с вероятността p, е необходимо и достатъчно p-квантилните оценки на дължините на всички детерминистични контури да удовлетворяват отношението W p (L(K(i))) Ј 0.

Алгоритми за изчисляване на времевите параметри на CSSM.

Ранни и късни планове.

За изчисляване на ранните и късните дати за завършване на събитията се предлага модифициран алгоритъм "Махало". Идеята на модификацията е да синтезира статистическия метод за изчисляване на параметри, използван за вероятностни мрежи и алгоритъма "Махало", използван в обобщени мрежи, и след това да го приложи към CSSM.

Фиг.10. Принципна блокова схема на алгоритъма за изчисление

р-квантилни оценки ранни датиосъществяване на събития

Блок 1. Въвеждане на изходни данни (коефициенти на матрица А, параметри на разпределение y ij , ниво на достоверност p).

Блок 2. Изчисляване на необходимия брой "тегления" N за осигуряване на зададената точност на резултатите. Направените изчисления показаха, че при p=0,95, e=0,05 получаваме N»270.

Блок 3. v:=v+1 (v е числото на "тегленето").

Блок 4. Изчертаване на v-тия вариант на случайни променливи y ij , всяка в съответствие със своя закон на разпределение, получаване на константи y ij (v) - дължината на дъгата (i, j) на v-тия чертеж.

Блок 5. Начертайте за всеки алтернативен връх i на прехода към съседен връх j (възпроизвежда се дискретна случайна променлива p ij, представена от i-тия ред на матрицата на съседство A, 0< р ij <1 и е j р ij =1). Выбранная дуга помечается, остальные из графа исключаются. Если в полученном графе образовался контур К(i), содержащий хотя бы одну помеченную дугу, это есть стохастический контур, вычисляем его длину L (v) K(i) и опять для вершины i разыгрываем дискретную случайную величину р ij . В соответствие с доказанной в работе лема 1 същият стохастичен контур при дадено ниво на достоверност p може да се формира не повече от k пъти, където k се оценява по съответната формула. Добавяме k-кратната дължина на контура към дължината на дъгата, която „разиграхме“ на (k + 1)-та стъпка и пристъпваме към анализа на друг стохастичен контур (ако има такъв). В този случай могат да се появят противоречия в мрежата (положителни детерминистични контури), след което в съответствие с формулите, дадени в работата, добавяме d-кратната дължина на контура, като по този начин оценяваме средното време за завършване на „ изход” събитие от контура.

Блок 6. Получената детерминирана обобщена мрежа G (v) е разделена на две мрежи G 1 (v) и G 2 (v), така че нито G 1 (v), нито G 2 (v) съдържат контури. Върховете в мрежата G 1 (v) са подредени по рангове и в съответствие с тях задаваме „правилната“ номерация. Прехвърляме това номериране към мрежата G 2 (v) и към оригинала G (v) .

Блок 7. За всички върхове i на мрежата G 1 (v) изчисляваме ранните дати на завършване

T i 0(v) :=max j (T i 0(v) , T j 0(v) + y ij (v) ).

Блок 8. Извършваме процедури, подобни на блок 7 за върховете на мрежата G 2 (v) .

Блок 9. Ако резултатите от блокове 7 и 8 не съвпадат поне по един индикатор, тогава се връщаме към блок 7 (няма повече такива връщания от броя на обратните дъги в G 2 (v)), в противен случай блок 10.

Блок 10. Ако тегленето е vJN, отидете на блок 4, в противен случай отидете на блок 11.

Блок 11. От получения набор (T i 0(v)) за всеки връх i изграждаме вариационна серия. Фиксираме такава стойност на Т i 0(x), че N x /N=р, където N x е броят на членовете на вариационната серия по-малък от Т i 0(x) . Стойността Т i 0(x) е необходимият p-квантил на ранния срок на i-тото събитие – W p (Т i 0). По подобен начин, използвайки вариационната серия (y ij (v) ) изграждаме p-квантилни оценки на дължините на дъгата – W p (y ij).

Входът на блок 6 получава v-та версия на обобщения мрежов модел G (v) и всъщност блокове 6 - 9 са увеличена блокова диаграма на алгоритъма "Махало" за изчисляване на ранното време на събитията в OSM. Прилагане на подходящ алгоритъм за изчисляване късни датизавършване на събития в блокове 7 и 8, получаваме T i 1(v) - късни дати за завършване на събития за v-тата версия на обобщения мрежов модел, докато блок 11 ни дава W p (T i 1) - р-квантилни оценки късни датизавършване на събития.

Планове с минимална продължителност.

Продължителността L(T (v)) на всеки изпълним план T (v) =(T i (v) ) на v-тата версия на мрежата G (v) се определя по формулата:

L(Т (v))=max ij |Т i (v) – Т j (v) |. (23)

Замествайки в блоковата схема на фиг. 10 блока 6 - 9 на блока за намиране на минимума на функцията (23), получаваме плана на минималната продължителност за мрежата G (v) (или "компресиран" план). Стойност

L(T* (v))=min max ij |T i (v) – T j (v) | (24)

е критичното време на мрежата G (v) .

Използвайки в блокове 6-9 метода за намиране на компресиран план за OCM и преминаване на получените планове през блок 11, получаваме вероятностни p-квантилни оценки на компресираните планове.

Времевите резерви за работа (i, j) съответстват на техните р-квантилни двойници, изчислени по формулите:

R p p (i, j) \u003d W p (T j 1) - W p (T i 0) - W p (y ij) за пълен резерв, (25)

R с p (i, j) \u003d W p (T j 0) - W p (T i 0) - W p (y ij) за свободен резерв. (26)

Съгласно съответните формули се изчисляват p-квантилите коефициенти на напрежениеработи W p (k n (i, j)), след това p-квантилът критична зона, p-квантил резервна зонаи р-квантил междинна зона.

Като параметър на дъгата разгледахме времето за изпълнение на операцията (работата). Може също така да се разгледа всеки характерен параметър, който има адитивност по дъгите на всеки път. Това може да бъде цената на работата, размерът на необходимия натрупан ресурс и др.

Трябва да се отбележи, че досега само методите за детерминистично мрежово моделиране, някои евристични методи за оптимално разпределение на ресурсите и параметрични методи за оценка на разходите (главно в областта на въздушните и космически полети) са намерили широко практическо приложение. Въпреки че теоретично е намерено точното решение на проблемите с разходите за планиране, базирано на класически мрежови модели (описано в), практическото му използване е свързано с трудността да се получат действителни данни за зависимостите време-цена.

Всеки от разгледаните по-горе модели има своя собствена предметна област, по свой начин (повече или по-малко пълно) изпълнява основните функции на управлението на проекти и само синтезът на анализираните модели и методи ви позволява да изградите модел, който адекватно отразява процес на изпълнение на сложен проект в условия на несигурност и в същото време да се получи приемливо решение на формулирания проблем.

Тема 4. ОПТИМИЗАЦИЯ НА ПОТРЕБЛЕНИЕТО НА РЕСУРСИ НА БАЗА НА МРЕЖОВИ МОДЕЛИ

Общи понятия.

По-горе бяха разгледани мрежови модели, без да се вземат предвид ограничените ресурси, т.е. проблемът за най-доброто разпределение на ресурсите като такъв не беше поставен. В разгледаните от нас методи за използване на мрежови модели основното внимание беше обърнато на времето за изпълнение на отделните работи и идентифицирането на най-важните (критични и подкритични) вериги на работа, на които навременното завършване на проекта ( въвеждане в експлоатация на съоръжението) зависи. По този начин характерна особеност на тези методи е класифицирането на информацията според степента на нейната важност от гледна точка на завършване на цялата гама работа в рамките на установения срок.

Количествена мярка за важността на информацията е резервът от работно време или коефициенти на напрежение

K ij \u003d 1 - R p ij / (T n 0 - T cr (i, j)), (25)

където R p ij е общият резерв на работа (i, j), T n 0 е критичното време за проекта, T kr (i, j) е продължителността на сегмента от максималния път, който съвпада с критичния път , съдържаща работа (i, j). 0 £ K ij £ 1 и колкото по-близо е K ij до 1, толкова по-малък е резервът в запаса от работа (i, j), следователно, толкова по-висок е рискът той да не бъде завършен в рамките на определеното време. Например за работа (2.5) (фиг. 5) T cr (2.5) = 5, R p 25 = 3, откъдето K 25 = 1 -3 / (22 - 5) = 0.82, а за работа ( 5.8) T cr (5.8) \u003d 0, R p 58 \u003d 12, откъдето K 58 \u003d 1 -12 / (22 - 0) = 0.45. Работите могат да имат същите пълни резерви, но степента на напрежение във времето на тяхното изпълнение може да бъде различна. Обратно, различни общи резерви могат да съответстват на едни и същи коефициенти на напрежение. С информация, класифицирана по този начин, ръководителят на проекта във всеки един момент може да определи в коя област трябва да се съсредоточи вниманието (и ресурсите), за да се елиминират възникващите отклонения от дадената дата на завършване на цялата работа.

Преди да очертаем допълнителни начини за подобряване на методите за планиране и управление на мрежата, нека се спрем по-подробно на някои от основните недостатъци, присъщи на методите, разгледани по-горе.

Давайки времева оценка на продължителността на всяка работа, ние приехме използването на определени ресурси с определена интензивност за извършване на тази работа (интензивността на потреблението на ресурси е количеството ресурс, консумиран за единица време).

Към момента на определяне на времева оценка не е известно кога ще трябва да се извърши тази работа, какви други дейности по проекта, които консумират същия вид ресурс, ще се извършват по същото време. Освен това, като правило, едни и същи ресурси могат да бъдат необходими едновременно за различни проекти. Следователно е възможно общата нужда от определен ресурс в определени моменти от време да надхвърли наличното им ниво. В тези случаи ще е необходимо или да се намали интензивността на потреблението на ресурси на отделни работни места, или да се отложи изпълнението на редица работни места за по-късна дата, често извън пълния резерв на тези работни места. Това води в хода на проекта до чести корекции на първоначалния план, с други думи, до нестабилност на плана.

Очевидно е, че ако ограниченията на ресурсите се вземат предвид предварително при планирането на процеса на изпълнение на проекта, тогава може да се получи много по-надежден план.

Нивото на наличните ресурси и възможното време за завършване на проекта са взаимосвързани. Времето за завършване на целия проект ще зависи от това кога и колко ресурси ще бъдат разпределени за всяка дейност и това до голяма степен се определя от очакваната им наличност във всеки един момент.

По този начин възниква проблемът с разпределението на ресурсите в мрежова среда.

Най-общо казано, всеки процес на планиране на производството не е нищо повече от решение на проблема с ефективното използване на ресурсите.

Критериите за ефективност могат да бъдат различни, ние ще се спрем на този важен момент от планирането (избор и обосновка на критерия) малко по-ниско, когато разглеждаме конкретни задачи.

Нека въведем някои понятия и определения.

· работна програманека назовем определен набор от операции (работи), които трябва да бъдат изпълнени за постигане на една или повече цели, а изпълнението на работата на програмата е подчинено на един ръководен център. Можем да говорим за работна програма за пусков комплекс, работна програма за обект, строителна организация, проектантски институт и т.н.

· Работна програма с една темаще наречем програма, състояща се от един комплекс от технологично взаимосвързани произведения, насочени към постигане на една (едноцелева тема) или няколко цели (многоцелева тема).

· Многотематична работна програмаще наречем програма, състояща се от няколко комплекса от произведения, технологично свързани във всеки комплекс. Всеки работен пакет може да има една или повече крайни цели. Произведенията, принадлежащи към различни комплекси, не са технологично свързани помежду си. Принадлежността на темите към една многотематична програма се определя от единството на контролния център и общността на резервоара от ресурси.

Нека първо разгледаме различни формулировки на проблеми с разпределението на ресурсите за програма с една тема и една цел.

Въз основа на двете възможни целеви настройки за управление на проекти, описани от мрежовия модел, има два основни типа настройка на задачи. Първият тип е фокусиран върху стриктното спазване на ограниченията на ресурсите, докато вторият тип включва стриктно спазване на датите за завършване на проекта.

Формулиране на първия тип постановка на проблема („калибриране“).

При зададени ограничения на потреблението на ресурси, намерете такова разпределение на тях, като вземете предвид технологичната последователност на работа, определена от топологията на мрежовата диаграма, която осигурява изпълнението на цялата програма за минимално време.

Формулиране на втория тип постановка на проблема („изглаждане“).

При спазване на определената продължителност на изпълнение на програмата е необходимо да се разпределят ресурсите между отделните работни места по такъв начин, че тяхното потребление да бъде оптимално. Въпросът за избора на критерий за оптималност за тази настройка ще бъде разгледан от нас отделно.

Поради различния механизъм за задоволяване на потребността от ресурси, те обикновено се разделят на две групи: акумулирани (съхраняеми) и неакумулативни (несъхраняеми). Втората група ресурси често се нарича "ресурси от тип капацитет".

Първата група включва ресурси, които по своята същност позволяват натрупване с възможност за последващо използване, например пари, различни материали и конструкции и др. Ресурсните ограничения в този случай могат да бъдат зададени чрез интегрална ненамаляваща функция, показваща във всеки момент общата стойност на предлагането на ресурс за целия предходен период.

Втората група включва ресурси, чието натрупване за последващо използване е невъзможно. Например ресурсите на работното и машинното време. Престоят на работници и механизми е невъзвратима загуба. Ресурсните ограничения за тази група се дават от функцията за наличност на ресурси във всеки момент от време.