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

Завдання 1

Обчислити суму матриць kA+mB, якщо

Елементи матриці суми визначаються за такою формулою:

cij=kaij+mbij.

Обчислимо елементи першого рядка матриці суми:

С11=-4*2+5*3=7

С12 = -4 * (-1) +5 * 7 = 39

С13 = -4 * 4 +5 * (-2) = -26

С21=-4*6+5*9=21

С22=-4*3+5*1=-7

С23=-4*0+5*6=30

С31=-4*(-7)+5*(-4)=8

С32=-4*5+5*8=20

С33=-4*9+5*5=-11

Таким чином, матриця суми набуде вигляду:

Завдання 2

Обчислити зворотну матрицю та зробити перевірку.

Використовуємо алгоритм знаходження зворотної матриці:

• 1. Матриця квадратна (число рядків дорівнює кількості стовпців), отже, зворотна до неї матриця існує.
• 2. Знаходимо визначник вихідної матриці:

• ?А=-3 * 3 * 3+1 * (-5) * 1+0 * (-4) * 3-1 * 3 * 3-(-4) * 1 * 3-0 * (-5) * (-3) = -29? 0
• 3. Знаходимо матрицю, що складається з додатків алгебри елементів вихідної матриці:

А11 = (-1) 2 * 3 * 3-0 * (-5) = -9

А12 = (-1) 3 * -4 * 3-1 * (-5) = 7

А13 = (-1) 4 * -4 * 0-1 * 3 = -3

А21 = (-1) 3 * 1 * 3-0 * 3 = -3

А22 = (-1) 4 * -3 * 3-1 * 3 = -12

А23 = (-1) 5 * -3 * 0-1 * 1 = 1

А31 = (-1) 4 * 1 * (-5) -3 * 3 = -14

А32 = (-1) 5 * -3 * (-5) - (-4) * 3 = -27

А33 = (-1) 6 * -3 * 3- (-4) * 1 = -5

Таким чином, отримуємо матрицю:

4. Отриману матрицю транспонуємо:

5. Останню матрицю ділимо на визначник вихідної матриці та отримуємо зворотну матрицю:

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

А -1. * А = А * А -1 = * = ==

Таким чином, отримали в результаті поодиноку матрицю. Отже, зворотну матрицю було знайдено, вірно.

Завдання 3

Розв'язати систему лінійних рівнянь методом Крамера, Гауса.

Рішення:

1) Вирішити систему шляхом Крамера.

Складаємо матрицю системи:

Обчислюємо визначник цієї матриці:

0 * (-8) * 4+3 * 2 * (-5)+7 * 2 * 9-9 * (-8) * (-5)-3 * 7 * 4-0 * 2 * 2=-348?0

Чи знаходимо визначники? 1 , ?2, ?3, що виходять з вихідного визначника заміною відповідно першого, другого та третього стовпців стовпцем вільних членів:

1==2 * (-8) * 4+3 * 2 * (-3)+9 * 5 * 2-9 * (-8) * (-3)-3 * 5 * 4-2 * 2 * 2=-276

2==0 * 5 * 4+2 * 2 * (-5)+9 * 7 * (-3)-9 * 5 * (-5)-2 * 7 * 2-0 * 2 * (-3)=- 40

3==0 * (-8) * (-3)+3 * 5 * (-5)+2 * 7 * 2-2 * (-8) * (-5)-3 * 7 * (-3)-0 * 5 * 2=- 64

Тепер використовуючи формули Крамера

х1 =, х2 =, х3 =,

знаходимо рішення системи:

Х1==,=0,79 х2==,=0,11 х3===0,18

2) Вирішимо систему методом Гауса.

Складаємо розширену матрицю системи, в яку входять коефіцієнти при змінних та вільні члени:

Помножимо 2-й рядок на (5). Помножимо 3-й рядок на (7). Додамо 3-й рядок до 2-го:

Помножимо 1-ий рядок на (26). Помножимо 2-й рядок на (3). Додамо 2-ий рядок до 1-го:

З першого рядка виражаємо x 3

З 2-го рядка виражаємо x 2

26х2 = - +4 = 0,11

З 3-го рядка виражаємо х 1

5х 1 = -2 * 0,11 - - 3 = 0,79

Завдання 4

матриця визначник лінійний крамер гаус

Обчислити визначник 4-го порядку

Запишемо розкладання визначника по четвертому рядку:

А = = 0 * А 41 +3 * А 42 +0 * А 43 +1 * А 44

де Aij - додаток алгебри елемент ij a .

Знайдемо додатки алгебри за формулою А ij =(-1) i+j , де m ij - мінор елемента ij a, який виходить з вихідного визначника викреслюванням рядка і стовпця, на перетині яких стоїть даний елемент.

А 42 =(-1) 4+2 * m 42 =(-1) 6 * =4 * 7 * (-9)+7 * (-7) * 0+1 * (-1) * 0 - 0 * 7 * 0 - 7 * 1 * (-9) - 4 * (-7) * (-1) =-217

А 44 =(-1) 4+4 * m 44 =(-1) 8 * =4 * (-3) * (-1)+0 * 7 * 0+1 * 1 * 7-7 * (-3 ) * 0-0 * 1 * (-1)-4 * 7 * 1=-9

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

3 * А 42 + А 44 = 3 * (-217) + (-9) = -660

Завдання 5

матриця зворотний визначник лінійний крамер гаус

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

Завдання.

Витрати трьох видів сировини А, B, C виробництва одиниці кожного з трьох типів продукції I, II, III і запаси кожного виду сировини задані в таблиці (Таблиця 1):

Таблиця 1

Потрібно визначити план виробництва, який би використання всієї сировини.

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

де - обсяги продукції кожного виду.

Для вирішення скористаємося методом Гауса. Запишемо розширену матрицю системи:

Запишемо систему у вигляді розширеної матриці:

Помножимо 2-й рядок на (-2). Додамо 2-ий рядок до 1-го:

Помножимо 2-й рядок на (3). Помножимо 3-й рядок на (-1). Додамо 3-й рядок до 2-го:

Помножимо 1-ий рядок на (2). Додамо 2-ий рядок до 1-го:

Тепер вихідну систему можна записати як:

x 2 = /2

x 1 = /3

З першого рядка виражаємо x 3

З 2-го рядка виражаємо x 2

З 3-го рядка виражаємо х 1

Курс лекцій з дисципліни

«Матричний аналіз»

для студентів II курсу

математичного факультету спеціальності

"Економічна кібернетика"

(Лектор Дмитрук Марія Олександрівна)

1. Визначення функції.

Df.Нехай

Розв'язання цього завдання відомо, коли f(x) – багаточлен:

Визначення f(A) у випадку.

Нехай m(x) – мінімальний многочлен А і має таке канонічне розкладання

Нехай g(A)=h(A) (1), тоді многочлен d(x)=g(x)-h(x) – анулюючий многочлен для А, оскільки d(A)=0, отже, d(x ) ділиться на лінійний многочлен, тобто. d(x)=m(x)*q(x) (2).

Умовимося m чисел для f(x) таких

Якщо безліч f(Sp A) визначено для f(x), то функція визначена спектрі матриці А.

З (3) випливає, що багаточлени h(x) та g(x) мають однакові значення на спектрі матриці А.

Наші міркування оборотні, тобто. із (3) Þ (3) Þ (1). Отже, якщо задана матриця А, значення многочлена f(x) цілком визначається значеннями цього многочлена на спектрі матриці А, тобто. всі многочлени g i (x), що приймають однакові значення на спектрі матриці, мають однакові матричні значення g i (A). Вимагаємо, щоб визначення значення f(A) у загальному випадку підпорядковувалося такому самому принципу.

Значення функції f(x) на спектрі матриці повинні повносильно визначити f(A), тобто. функції, що мають одні й ті самі значення на спектрі повинні мати те саме матричне значення f(A). Вочевидь, що з визначення f(A) у випадку, досить знайти многочлен g(x), який приймав самі значення на спектрі А, як і функція f(A)=g(A).

Df.Якщо f(x) визначено на спектрі матриці А, то f(A)=g(A), де g(A) – багаточлен, який приймає на спектрі ті ж значення, що й f(A),

Df.Значення функції від матриці А назвемо значення багаточлена від цієї матриці при

Серед многочленів із С[x], що приймають однакові значення на спектрі матриці А, що і f(x), ступеня не вище (m-1), що приймає однакові значення на спектрі А, що і f(x) – це залишок від розподілу будь-якого многочлена g(x), що має ті ж значення на спектрі матриці А, що і f(x), мінімальний многочлен m(x)=g(x)=m(x)*g(x)+r(x) .

Цей багаточлен r(x) називають інтерполяційним багаточленом Лагранжа-Сільвестру для функції f(x) на спектрі матриці А.

Зауваження. Якщо мінімальний многочлен m(x) матриці А немає кратних коренів, тобто.

Приклад:

Знайти r(x) для довільної f(x), якщо матриця

. Побудуємо f(H1). Знайдемо мінімальний многочлен H 1 - останній інваріантний множник:

, d n-1 = x 2; d n-1 = 1;

m x = f n (x) = d n (x) / d n-1 (x) = x nÞ 0 – n –кратний корінь m(x), тобто. n-кратні власні значення H1.

, r(0)=f(0), r'(0)=f'(0),…,r (n-1) (0)=f (n-1) (0)Þ .

2. Властивості функцій від матриць.

Властивість №1. Якщо матриця

Доказ:

Нехай характеристичний багаточлен матриці має вигляд:

Зробимо заміну в рівності:

Рівність (*) справедлива для будь-якої множини f(x), тому замінимо багаточлен f(x) на

Зліва ми отримали характеристичний багаточлен для матриці f(A), розкладений праворуч на лінійні множники, звідки слід, що

ЧТД.

Властивість №2. Нехай матриця

Доказ:

Т.к. функція f(x) визначена на спектрі матриці А, існує інтерполяційний багаточлен матриці r(x) такий, що

Другий підхід до аналізу мереж Петрі ґрунтується на матричному поданні мереж Петрі. Альтернативним по відношенню до визначення мережі Петрі у вигляді (Р, Т, I, О) є визначення двох матриць D - і D +, що представляють вхідну та вихідну функції. Кожна матриця має m рядків (по одному на перехід) та n стовпців (по одному на позицію). Визначимо D - = # (p i, I (t j)), a D + = # (p i, O (t j)). D – визначає входи в переходи, D+ – виходи.

Матрична форма визначення мережі Петрі (Р, Т, D - , D +) еквівалентна стандартній формі, що використовується нами, але дозволяє дати визначення термінах векторів і матриць. Нехай e[j] - m-вектор, що містить нулі скрізь, за винятком j-ї компоненти, що дорівнює одиниці. Перехід t j представляється m-вектором-рядком е[j].

Тепер перехід t j у маркуванні µ дозволений, якщо µ > e[j] D - , а результат запуску переходу t j у маркуванні µ, записується як:

δ(t j) = µ - e[j] D - + e[j] D + = µ + e[j] D

де D = D + - D - складова матриця змін.

Тоді для послідовності запуску переходів σ = t j ​​1 , t j 2 , … , t jk маємо:

δ(σ) = µ + e D + e D + … + e D =

= µ + (e + e + … + e)D = µ + f(σ) D

Вектор f(σ) = e + e + ... + e називається вектором запусків послідовності σ = tj 1 , tj 2 , … , t jk , f(σ) jp - це число запусків переходу tp у послідовності tj 1 , tj 2 , …, t jk. Вектор запусків f(σ), отже, є вектором з цілими негативними компонентами. (Вектор f(σ) - це відображення Паріха послідовності σ = t j ​​1 , t j 2 , … , t jk).

Щоб показати корисність такого матричного підходу до мереж Петрі, розглянемо, наприклад, завдання збереження: чи є ця маркована мережа Петрі зберігає? Для того, щоб показати збереження, необхідно знайти (ненульовий) вектор зважування, для якого зважена сума по всіх досяжних маркування постійна.

Нехай w = (w 1, w 2, …, w n) - Вектор-стовпець. Тоді, якщо µ - початкове маркування, а µ" - довільне досяжне маркування, тобто µ" належить R(C,µ), необхідно, щоб µ w = µ" w. Тепер, оскільки µ" досяжна, існує послідовність запусків переходів σ = tj 1 , tj 2 , … , t jk , яка переводить мережу з µ в µ". Тому

µ" = µ + f(σ) D

Отже,

µ w = µ" w = (µ + f(σ) D w = µ w + f(σ) D w, тому f(σ) D w = 0.

Оскільки це має бути правильним для всіх f(σ) , маємо D w = 0.

Таким чином, мережа Петрі є такою, що зберігає тоді і тільки тоді, коли існує такий позитивний вектор w, що D w = 0.

Це забезпечує простий алгоритм перевірки збереження, а також дає змогу отримувати вектор зважування w.

Розвинена матрична теорія мереж Петрі є інструментом вирішення проблеми досяжності. Припустимо, що маркування µ" можна досягти з маркування µ. Тоді існує послідовність (можливо, порожня) запусків переходів σ, яка призводить з µ до µ". Це означає, що f(σ) є невід'ємним рішенням наступного матричного рівняння для х:

µ" = µ + x D

Отже, якщо µ" досяжна з µ, тоді дане рівняння має рішення в невід'ємних цілих; якщо дане рівняння не має рішення, тоді µ" недосяжна з µ.

Розглянемо, наприклад, марковану мережу Петрі, зображену на рис.1:

Рис. 1. Мережа Петрі, що ілюструє метод аналізу, заснований на матричних рівняннях

Матриці D- та D+ мають вигляд:

t 1 t 2 t 3 t 1 t 2 t 3

p 1 1 0 0 p 1 1 0 0

D - = p 2 1 0 0 D + = p 2 0 2 0

p 3 1 0 1 p 3 0 1 0

p 4 0 1 0 p 4 0 0 1

а матриця D:

У початковому маркуванні µ = (1, 0, 1, 0) перехід t 3 дозволений і призводить до маркування µ" = (1, 0, 0,1).

µ" = µ + e D = (1, 0, 1, 0) + (0, 0, 1) D =

= (1, 0, 1, 0) + (0, 0, -1, 1) = (1, 0, 0, 1).

Послідовність σ = t 3 , t 2 , t 3 , t 2 , t 1 представляється вектором запусків f(σ) = (1, 2, 2) і отримує маркування µ":

µ" = (1, 0, 1, 0) + (1, 2, 2) D = (1, 0, 1, 0) + (0, 3, -1, 0) = (1, 3, 0, 0)

Для визначення того, чи є маркування (1, 8, 0, 1) з маркування (1,0, 1, 0), маємо рівняння:

(1, 8, 0, 1) = (1, 0, 1,0)+ x D

яке має рішення х =(0, 4, 5). Це відповідає послідовності σ = t 3 , t 2 , t 3 , t 2 , t 3 , t 2 , t 3 , t 2 , t 3

(1, 7,0, 1)=(1, 0, 1, 0) + x D

немає рішення.

Матричний підхід до аналізу мереж Петрі дуже перспективний, але має деякі труднощі. Зауважимо насамперед, що матриця Dяк така в повному обсязі відбиває структуру мережі Петрі. Переходи, що мають як входи, так і виходи з однієї позиції (петлі), є відповідними елементами матриць D+і D - але потім взаємно знищуються в матриці D = D + - D -.Це відображено в попередньому прикладі позицією p 4 і переходом t 3 .

Інша проблема – це відсутність інформації про послідовність у векторі запуску. Розглянемо мережу Петрі на мал. 2. Припустимо, ми хочемо визначити, чи є маркування (0, 0, 0, 0, 1) досяжним (1, 0, 0, 0, 0). Тоді маємо рівняння

(1, 0, 0, 0, 0)=(0, 0, 0, 0, 1) + x D

Рис. 2. Інша мережа Петрі, що служить для ілюстрації матричного аналізу

Це рівняння немає однозначного рішення, але зводиться до безлічі рішень (a f (o) =(1, х 2, х 6 - 1, 2х 6 , х е - 1, х 6)).Воно визначає взаємозв'язок між запусками переходів. Якщо покладемо х 6= 1 та х 2= 1, то /(о) = (1, 1, 0, 2, 0, 1), але цьому вектору запуску відповідають як послідовність 44444. так і п0- послідовність 44444- Отже, хоча і відомо число запусків переходів, порядок їх запуску невідомий.

Ще одна проблема полягає в тому, що рішення рівняння є необхідним для досяжності, але недостатнім. Розглянемо просту мережу Петрі, наведену на рис. 3. Якщо ми хочемо визначити, чи є (0, 0, 0, 1) досяжним із (1, 0, 0, 0), необхідно вирішити рівняння

Рис. 3. Мережа Петрі, що показує, що розв'язання матричного рівняння-необхідна, але недостатня умова для вирішення задачі досяжності

Це рівняння має розв'язок /(а) = (1, 1), що відповідає двом послідовностям: tit 2і /3/t. Але жодна з цих двох послідовностей переходів неможлива, оскільки в (1,0, 0, 0) t itні 4 не дозволені. Отже, рішення рівняння замало доказу досяжності.

Контрольні питання та завдання

1. Побудуйте граф мережі Петрі для наступної мережі Петрі:

P=(p 1 ,p 2 ,p 3 ,p 4 ), T=(t 1 ,t 2 ,t 3 ,t 4 ,t 5 ),

I(t 1)=(), O(t 1)=(p 1 ),

I(t 2)=(p 1 ), O(t 2)=(p 2 ),

I(t 3)=(p 2 ,p 2 ,p 4 ), O(t 3)=(p 1 ,p 3 ),

I(t 4)=(), O(t 4)=(p 3 ),

I(t 5)=(p 3 ), O(t 5)=(p 4 ,p 4 ).

2. Побудуйте граф мережі Петрі для наступної мережі Петрі:

P=(p 1 ,p 2 ,p 3 ,p 4 ), T=(t 1 ,t 2 ,t 3 ,t 4 ),

I(t 1)=(), O(t 1)=(p 1 ,p 1 ,p 1 ,p 1 ,p 2 ),

I(t 2)=(p 2 ), O(t 2)=( p 1 ,p 1 p 1 ,p 1 ,p 1 ,p 1 ,p 3 ),

I(t 3)=(p 1 ,p 1 ,p 1 ,p 1 ,p 1 ,p 1 ), O(t 3)=( p 2 ,p 2 p 2 ,p 2 p 4 ,p 4 ),

I(t 4)=( p 2 ,p 3 p 4 ,p 4 ), O(t 4)=(p 3 ).

3. Для мережі Петрі із упр.1 для маркування m=(5,4,0,0) вказати дозволені переходи.

4. Для мережі Петрі з упр.2 для маркування m = (7, 12, 2, 1) вказати дозволені переходи.

5. Покажіть, що ER(C,m)=N n де mÎN n .

6. Доведіть, що якщо m'Î R(C,m), то R(C,m')Í R(C,m).

7. Доведіть, що m'Î R(C,m) тоді і лише тоді, коли R(C,m')Í R(C,m).

8. Побудуйте безліч можливостей для мережі Петрі з упр.1.

9. Побудуйте безліч можливостей для мережі Петрі з упр.2.

10. Мережі Петрі зі своїми фішками і правилами запусків багато в чому нагадують ігри, що мають ігрове поле: шашки, нарди, ним, го та ін. та набору фішок. Фішки розподілені за позиціями мережі Петрі, і гравці по черзі вибирають дозволені переходи та запускають їх. Визначте правила гри, що передбачають:

a Як визначено початкове розташування фішок? (Наприклад, кожен гравець починає гру, маючи одну фішку в будиночку або кожен гравець отримує n фішок по всьому полі за бажанням і т.д.).

b Якою є мета гри? (Захопити фішки свого супротивника; отримати найбільшу кількість фішок; якнайшвидше позбутися своїх фішок і т.д.).

c Чи не потрібно розфарбувати фішки для різних гравців? (Відповідно до цього визначте правила запуску переходів).

d Чи не варто присвоїти окуляри різним переходам? (Тоді очки гравця визначаються сумою переходів, запущених ним).

На основі цього опишіть гру, наведіть приклад гри.

11. Розробте програму, яка реалізує гру з упр.10, де як вашого супротивника виступає комп'ютер для заданої мережі Петрі.

12. Побудуйте систему моделювання для виконання мережі Петрі. Запуск дозволених переходів визначається користувачем системи моделювання.

13.Мудреці сидять за великим круглим столом, на якому багато страв китайської кухні. Між сусідами лежить одна паличка для їжі. Однак для прийому китайської їжі необхідні дві палички, отже, кожен мудрець має взяти палички праворуч та ліворуч. Проблема полягає в тому, що якщо всі мудреці візьмуть палички зліва і потім чекатимуть, коли звільняться палички з правого боку, то вони чекатимуть вічно і помруть з голоду (стан глухого кута). Необхідно побудувати таку мережу Петрі, яка ставить стратегію проведення обіду і не має глухих кутів.

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

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

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

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

18. Розробити алгоритм моделювання блок-схем мережею Петрі.

19.PERT-діаграма є графічним уявленням взаємозв'язків між різними етапами, що становлять проект. Проект є сукупністю великої кількості робіт, у своїй роботи мають завершитися перш, ніж почнуть виконуватися інші. Крім того, на виконання кожної роботи потрібна певна кількість часу. Роботи графічно представляються вершинами, а дуги застосовуються для відображення причинно-наслідкових зв'язків з-поміж них. PETR - діаграма є спрямований граф із завислими дугами. Завдання у тому, щоб визначити мінімальний час виконання проекту. Розробити алгоритм моделювання PERT-діаграм за допомогою мереж Петрі.

20. Розробте модель, засновану на мережах Петрі, для моделювання хімічних реакцій.

21. Розгляньте побудову не дерева, а графа досяжності. Якщо вершина x породжує наступну вершину z з m[z]=m[y] для деякої неграничної вершини y, вводиться позначена дуга від x до y. Опишіть алгоритм побудови графа досяжності.

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

23.Дерево досяжності не можна використовуватиме вирішення проблеми досяжності, т.к. втрачається інформація у зв'язку із запровадженням поняття символу w. Він вводиться, коли приходимо до маркування m' і по дорозі від кореня до m' є така маркування m, що m'>m. В цьому випадку можна отримати всі маркування виду m+n(m'-m). Досліджуйте можливість використання виразу a+bn i замість w, щоб представити значення компонент. Якщо ви зможете визначити дерево досяжності, в якому всі вектори маркувань є виразами, тоді вирішення задачі досяжності визначається просто рішенням системи рівнянь.

24. Узагальнюйте визначення збереження, дозволяючи негативні ваги. Що можна було б вважати розумною інтерпретацією негативної ваги? Чи є вирішеним завдання визначення збереження мережі Петрі, якщо дозволено негативну вагу?

25. Розробте за допомогою матричного підходу до аналізу алгоритм визначення обмеженості мережі Петрі.

26. Розробте алгоритм розв'язання задачі рівності двох мереж Петрі. Мережа Петрі C ​​1 =(P 1 ,T 1 ,I 1 ,O 1) з маркуванням m 1 дорівнює мережі Петрі C ​​2 =(P 2 ,T 2 ,I 2 ,O 2) з маркуванням m 2 , якщо R(C 1, m 1) = R (C 2, m 2).

27. Розробте алгоритм розв'язання задачі підмножини двох мереж Петрі. Мережа Петрі C ​​1 =(P 2 ,T 2 ,I 2 ,O 2) з маркуванням m 2 є підмножина мережі Петрі C ​​1 =(P 1 ,T 1 ,I 1 ,O 1) з маркуванням m 1 , якщо R( C 1 ,m 1) R (C 2 ,m 2).

28. Розробте алгоритм розв'язання задачі досяжності. У мережі Петрі C=(P,T,I,O) з маркуванням m маркування m досягається з m, якщо mÎR(C,m).

29. Розробте алгоритм завдання досяжності підмаркування. Для підмножини P' Í P і маркування m' чи існує m''ÎR(C,m), така, що m''(p i)=m'(p i) для всіх p i ÎP'?.

30. Розробте алгоритм завдання досяжності нуля. Чи виконується m'ÎR(C,m), де m'(p i)=0 для всіх p i ÎP?

31. Розробте алгоритм задачі досяжності нуля в одній позиції. Для цієї позиції p i ÎP чи існує m'ÎR(C,m) з m'(p i)=0?

32. Розробте алгоритм розв'язання задачі активності мережі Петрі. Чи активні всі переходи t j ÎT?

33. Розробте алгоритм розв'язання задачі активності одного переходу. Чи активний цей перехід t j ÎT?

34. Мережа Петрі називається оборотною, якщо для кожного переходу t j ÎT знайдеться перехід t k ÎT, такий, що

#(p i ,I(t j))=#(p i ,O(t k)), #(p i ,O(t j))=#(p i ,I(t k)),

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

35. Розробте алгоритм розв'язання задачі рівності для оборотних мереж Петрі.

36. Завдання про курців. Кожен із трьох курців безперервно виготовляє сигарету та палить її. Щоб зробити сигарету, необхідні тютюн, папір та сірники. Один із курців завжди має папір, інший – сірники, третій – тютюн. Агент має нескінченні запаси паперу, сірників і тютюну. Агент кладе дві складові на стіл. Курець, що має третій відсутній інгредієнт, може зробити і закурити сигарету, сигналізуючи про це агенту. Тоді агент містить інші два з трьох інгредієнтів, і цикл повторюється. Запропонуйте активну мережу Петрі, яка моделює завдання курців.

37. Автоматна мережа Петрі - це мережа Петрі, у якій кожен перехід може мати точно один вихід і один вхід, тобто. для всіх t j ÎT ½I(t j)½=1 та ½O(t j)½=1. Розробте алгоритм побудови кінцевого автомата, який еквівалентний заданій автоматній мережі Петрі.

38. Маркований граф є мережа Петрі, у якій кожна позиція є входом точно одного переходу і виходом точно одного переходу, тобто. для кожного переходу p i ÎP ½I(p i)½=1 та ½O(p i)½=1. Розробте алгоритм розв'язання задач досяжності для маркованих графів.

39. Розгляньте клас мереж Петрі, які є і маркованими графами, і автоматними мережами Петрі.

40. Побудуйте мережу Петрі, яка моделює системи, описані в додатку 8. Опишіть події, що відбуваються в системі, та умови, що описують систему. Побудуйте дерево досяжності збудованої мережі Петрі. Опишіть стан, у якому може бути система.