11.3. Die Matrix-Methode zur Entwicklung von Strategien Entwicklung der Vision einer Organisation Die unterschiedlichen Zustände des externen und internen Umfelds von Organisationen erklären die Vielfalt der Organisationen selbst und ihren Ist-Zustand Die Multifaktorizität der Parameter, die die jeweilige Position bestimmen

Übung 1

Berechnen Sie die Summe der Matrizen kA+mB, wenn

Die Elemente der Summenmatrix werden durch die Formel bestimmt:

cij=kaij+mbij.

Berechnen Sie die Elemente der ersten Zeile der Summenmatrix:

C11=-4*2+5*3=7

C12=-4 * (-1)+5 * 7=39

C13=-4*4+5*(-2)=-26

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

C22=-4*3+5*1=-7

C23=-4*0+5*6=30

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

C32=-4*5+5*8=20

C33=-4*9+5*5=-11

Somit nimmt die Summenmatrix die Form an:

Aufgabe 2

Berechne die inverse Matrix und überprüfe.

Wir verwenden den Algorithmus zum Finden der inversen Matrix:

• 1. Die Matrix ist quadratisch (die Anzahl der Zeilen ist gleich der Anzahl der Spalten), daher existiert die dazu inverse Matrix.
• 2. Finden Sie die Determinante der ursprünglichen Matrix:

• ?A=-3 * 3 * 3+1 * (-5) * 1+0 * (-4) * 3-1 * 3 * 3-(-4) * 1 * 3-0 * (-5) * (-3)=-29 ? 0
• 3. Finden Sie eine Matrix, die aus algebraischen Komplementen von Elementen der ursprünglichen Matrix besteht:

A11=(-1) 2*3*3-0*(-5)=-9

A12=(-1) 3 * -4 * 3-1 * (-5)=7

A13 = (-1) 4 * -4 * 0-1 * 3 = -3

A21=(-1) 3*1*3-0*3=-3

A22=(-1) 4*-3*3-1*3=-12

A23=(-1) 5 * -3 * 0-1 * 1=1

A31=(-1) 4*1*(-5)-3*3=-14

A32 = (-1) 5 * -3 * (-5)-(-4) * 3 = -27

A33=(-1) 6 * -3 * 3-(-4) * 1=-5

Damit erhalten wir die Matrix:

4. Transponieren Sie die resultierende Matrix:

5. Wir dividieren die letzte Matrix durch die Determinante der ursprünglichen Matrix und erhalten die inverse Matrix:

6. Wir überprüfen das Ergebnis. Dazu finden wir das Produkt der resultierenden Matrix mit der ursprünglichen:

A -1 .* A=A * A -1 =*= ==

Als Ergebnis haben wir also die Identitätsmatrix erhalten. Damit ist die inverse Matrix gefunden, richtig.

Aufgabe 3

Lösen Sie ein lineares Gleichungssystem mit der Cramer-Gauß-Methode.

Lösung:

1) Lösen Sie das System nach Cramers Methode.

Wir stellen die Matrix des Systems zusammen:

Wir berechnen die Determinante dieser Matrix:

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

Determinanten finden? 1 , ?2, ?3, erhalten aus der ursprünglichen Determinante durch Ersetzen der ersten, zweiten bzw. dritten Spalte durch eine Spalte mit freien Elementen:

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

Jetzt mit Cramers Formeln

x1=, x2=, x3= ,

Finden Sie die Lösung des Systems:

X1==,=0,79 x2==,=0,11 x3===0,18

2) Wir lösen das System mit der Gauß-Methode.

Wir stellen die erweiterte Matrix des Systems zusammen, die Koeffizienten für Variablen und freie Terme enthält:

Multiplizieren Sie die 2. Reihe mit (5). Multiplizieren Sie die 3. Reihe mit (7). Fügen wir die 3. Zeile zur 2. hinzu:

Multiplizieren Sie die 1. Reihe mit (26). Multiplizieren Sie die 2. Reihe mit (3). Fügen wir die 2. Zeile zur 1. hinzu:

Ab der 1. Zeile drücken wir x 3 aus

Ab der 2. Zeile drücken wir x 2 aus

26x 2 \u003d - + 4 \u003d 0,11

Ab der 3. Zeile drücken wir x 1 aus

5x 1 \u003d -2 * 0,11- - 3 \u003d 0,79

Aufgabe 4

Matrixdeterminante linear Cramer Gauß

Berechnen Sie die Determinante 4. Ordnung

Wir schreiben die Erweiterung der Determinante in die vierte Zeile:

A \u003d\u003d 0 * A 41 +3 * A 42 +0 * A 43 +1 * A 44

wobei Aij das algebraische Komplement des Elements ij a ist.

Suchen wir algebraische Additionen nach der Formel A ij =(-1) i+j , wobei m ij der Minor des Elements ij a ist, der aus der ursprünglichen Determinante durch Streichen der Zeile und Spalte an deren Schnittpunkt dies erhalten wird Element steht.

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

A 44 \u003d (-1) 4 + 4 * m 44 \u003d (-1) 8 * \u003d 4 * (-3) * (-1) + 0 * 7 * 0 + 1 * 1 * 7-7 * (-3 ) * 0-0 * 1 * (-1)-4 * 7 * 1=-9

Wir setzen die erhaltenen Werte in die Erweiterung der Determinante ein:

3 * A 42 + A 44 \u003d 3 * (-217) + (-9) \u003d -660

Aufgabe 5

inverse Determinantenmatrix linear Cramer Gauß

Eigenständig, analog zum Beispiel, ein Problem mit wirtschaftlichem Inhalt erstellen, ein mathematisches Modell des Wirtschaftsprozesses erstellen und das Problem lösen.

Aufgabe.

Die Kosten von drei Rohstoffarten A, B, C für die Herstellung einer Einheit jeder der drei Produktarten I, II, III und die Reserven jeder Rohstoffart sind in der Tabelle (Tabelle 1) angegeben. :

Tabelle 1

Es ist erforderlich, einen Produktionsplan festzulegen, der die Verwendung aller Rohstoffe sicherstellt.

Lassen Sie uns ein System linearer Gleichungen schreiben, indem wir die in der Tabelle angegebenen Daten verwenden:

wo - das Volumen der Ausgabe jedes Typs.

Zur Lösung verwenden wir die Gauß-Methode. Schreiben wir die erweiterte Matrix des Systems:

Wir schreiben das System in Form einer erweiterten Matrix:

Multiplizieren Sie die 2. Zeile mit (-2). Fügen wir die 2. Zeile zur 1. hinzu:

Multiplizieren Sie die 2. Reihe mit (3). Multiplizieren Sie die 3. Zeile mit (-1). Fügen wir die 3. Zeile zur 2. hinzu:

Multiplizieren Sie die 1. Reihe mit (2). Fügen wir die 2. Zeile zur 1. hinzu:

Nun kann das ursprüngliche System geschrieben werden als:

x2 = /2

x 1 = /3

Ab der 1. Zeile drücken wir x 3 aus

Ab der 2. Zeile drücken wir x 2 aus

Ab der 3. Zeile drücken wir x 1 aus

Vorlesungsreihe zur Disziplin

"Matrixanalyse"

für Studenten im 2

Spezialgebiet der Fakultät für Mathematik

"Ökonomische Kybernetik"

(Dozent Dmitruk Maria Alexandrowna)

1. Funktionsdefinition.

Df. Lassen

Die Lösung dieses Problems ist bekannt, wenn f(x) ein Polynom ist:

Definition von f(A) im allgemeinen Fall.

Sei m(x) das Minimalpolynom A und habe die kanonische Zerlegung

Sei g(A)=h(A) (1), dann ist das Polynom d(x)=g(x)-h(x) das Vernichtungspolynom für A, da d(A)=0, also d(x ) ist durch ein lineares Polynom teilbar, d.h d(x)=m(x)*q(x) (2).

Vereinbaren wir m Zahlen für f(x) wie z

Wenn die Menge f(Sp A) für f(x) definiert ist, dann ist die Funktion auf dem Spektrum der Matrix A definiert.

Aus (3) folgt, dass die Polynome h(x) und g(x) im Spektrum der Matrix A die gleichen Werte haben.

Unsere Argumentation ist umkehrbar, d.h. von (3) → (3) → (1). Wenn also die Matrix A gegeben ist, wird der Wert des Polynoms f(x) vollständig durch die Werte dieses Polynoms im Spektrum der Matrix A bestimmt, d.h. alle Polynome g i (x), die im Spektrum der Matrix die gleichen Werte annehmen, haben die gleichen Matrixwerte g i (A). Wir fordern, dass die Definition des Werts von f(A) im allgemeinen Fall dem gleichen Prinzip folgt.

Die Werte der Funktion f(x) auf dem Spektrum der Matrix A müssen f(A) vollständig bestimmen, d.h. Funktionen mit gleichen Werten im Spektrum müssen den gleichen Matrixwert f(A) haben. Offensichtlich reicht es zur Bestimmung von f(A) im allgemeinen Fall aus, ein Polynom g(x) zu finden, das auf dem Spektrum A dieselben Werte annehmen würde wie die Funktion f(A)=g(A).

Df. Wenn f(x) im Spektrum der Matrix A definiert ist, dann ist f(A)=g(A), wobei g(A) ein Polynom ist, das im Spektrum dieselben Werte annimmt wie f(A),

Df.Der Wert der Funktion aus der Matrix A wir nennen den Wert des Polynoms in dieser Matrix for

Unter den Polynomen von С[x], die die gleichen Werte im Spektrum der Matrix A annehmen, wie f(x), mit einem Grad nicht höher als (m-1), der die gleichen Werte im Spektrum annimmt Spektrum A, da f(x) der Rest der Division eines beliebigen Polynoms g(x) mit den gleichen Werten im Spektrum der Matrix A wie f(x) zum Minimalpolynom m(x)=g(x) ist )=m(x)*g(x)+r(x) ​​.

Dieses Polynom r(x) heißt Lagrange-Sylvester-Interpolationspolynom für die Funktion f(x) auf dem Spektrum der Matrix A.

Kommentar. Wenn das Minimalpolynom m(x) der Matrix A keine Mehrfachwurzeln hat, d.h.

Beispiel:

Finden Sie r(x) für beliebige f(x) wenn die Matrix

. Konstruieren wir f(H 1). Finden Sie das minimale Polynom H 1 - der letzte invariante Faktor:

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

m x \u003d f n (x) \u003d d n (x) / d n-1 (x) \u003d x nÞ 0 – n-fache Wurzel von m(x), d.h. n-fache Eigenwerte von H 1 .

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

2. Eigenschaften von Funktionen aus Matrizen.

Eigentum Nr. 1. Wenn die Matrix

Nachweisen:

Das charakteristische Polynom der Matrix A habe die Form:

Nehmen wir eine Änderung in der Gleichheit vor:

Gleichheit (*) gilt für jede Menge f(x), also ersetzen wir das Polynom f(x) durch

Links haben wir das charakteristische Polynom für die Matrix f(A) erhalten, rechts in lineare Faktoren zerlegt, was das impliziert

CHTD.

Eigentum Nr. 2. Lassen Sie die Matrix

Nachweisen:

Denn Funktion f(x) auf dem Spektrum der Matrix A definiert ist, dann gibt es ein Interpolationspolynom der Matrix r(x), so dass

Der zweite Ansatz zur Analyse von Petri-Netzen basiert auf der Matrixdarstellung von Petri-Netzen. Eine Alternative zur Definition des Petrinetzes in der Form (P, T, I, O) ist die Definition zweier Matrizen D - und D + , die die Eingangs- und Ausgangsfunktionen darstellen. Jede Matrix hat m Zeilen (eine pro Übergang) und n Spalten (eine pro Position). Definiere D – = #(p i , I(t j)) und D + = #(p i , O(t j)). D - definiert Übergangseingänge, D + - Ausgänge.

Die Matrixform der Definition des Petrinetzes (P, T, D - , D +) entspricht der von uns verwendeten Standardform, erlaubt aber Definitionen in Form von Vektoren und Matrizen. Sei e[j] ein m-Vektor, der überall Nullen enthält, mit Ausnahme der j-ten Komponente, die gleich eins ist. Der Übergang t j wird durch einen m-Zeilen-Vektor e[j] dargestellt.

Nun ist der Übergang t j in der Markierung µ erlaubt, wenn µ > e[j] D - , und das Ergebnis der Ausführung des Übergangs t j in der Markierung µ wird wie folgt geschrieben:

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

wobei D = D + - D - eine zusammengesetzte Änderungsmatrix ist.

Dann gilt für die Übergangstriggersequenz σ = t j ​​​​1 , t j 2 , … , t jk :

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

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

Der Vektor f(σ) = e + e + ... + e heißt Startvektor der Folge σ = tj 1 , tj 2 , … , t jk , f(σ) jp ist die Anzahl der Transitionsläufe tp in der Folge tj 1 , tj 2 , … , t jk . Der Triggervektor f(σ) ist also ein Vektor mit nicht negativen ganzzahligen Komponenten. (Der Vektor f(σ) ist die Parikh-Abbildung der Folge σ = t j ​​​​1 , t j 2 , … , t jk).

Um die Nützlichkeit eines solchen Matrix-Ansatzes für Petri-Netze zu zeigen, betrachten Sie beispielsweise das Erhaltungsproblem: Ist ein gegebenes markiertes Petri-Netz erhaltend? Um die Erhaltung zu zeigen, ist es notwendig, einen (von Null verschiedenen) Gewichtungsvektor zu finden, für den die gewichtete Summe über alle erreichbaren Markierungen konstant ist.

Sei w = (w 1 ,w 2 , … , w n) ein Spaltenvektor. Wenn µ die Anfangsmarkierung ist und µ" eine beliebige erreichbare Markierung ist, dh µ" zu R(C,µ) gehört, ist es notwendig, dass µ w = µ" w. Nun, da µ" erreichbar ist, gibt es eine Folge von Übergängen σ = tj 1 , tj 2 , … , t jk , die das Netzwerk von µ nach µ bringt

µ" = µ + f(σ) D

Somit,

µ w = µ" w = (µ + f(σ) D) w = µ w + f(σ) D w, also f(σ) D w = 0.

Da dies für alle f(σ) gelten muss, ist D w = 0.

Somit ist ein Petri-Netz genau dann erhaltend, wenn es einen positiven Vektor w gibt, so dass D w = 0 ist.

Dies stellt einen einfachen Persistenzprüfalgorithmus bereit und ermöglicht auch, dass ein Gewichtungsvektor w erhalten wird.

Die entwickelte Matrixtheorie der Petrinetze ist ein Werkzeug zur Lösung des Erreichbarkeitsproblems. Angenommen, die Markierung µ" ist von der Markierung µ aus erreichbar. Dann gibt es eine (möglicherweise leere) Folge von Übergangsstarts σ, die von µ nach µ" führt. Das bedeutet, dass f(σ) eine nicht negative ganzzahlige Lösung der folgenden Matrixgleichung für x ist:

µ" = µ + xD

Wenn also µ" von µ aus erreichbar ist, dann hat die gegebene Gleichung eine Lösung in nicht-negativen ganzen Zahlen; wenn die gegebene Gleichung keine Lösung hat, dann ist µ" von µ aus nicht erreichbar.

Betrachten Sie zum Beispiel das in Abbildung 1 gezeigte beschriftete Petri-Netz:

Reis. 1. Petri-Netz zur Veranschaulichung einer auf Matrixgleichungen basierenden Analysemethode

Die Matrizen D - und D + haben die Form:

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

Seite 3 1 0 1 Seite 3 0 1 0

Seite 4 0 1 0 Seite 4 0 0 1

und Matrix D:

In der Anfangsmarkierung µ = (1, 0, 1, 0) ist der Übergang t 3 erlaubt und führt zur Markierung µ" = (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).

Die Folge σ = t 3 , t 2 , t 3 , t 2 , t 1 wird durch den Startvektor f(σ) = (1, 2, 2) dargestellt und mit µ bezeichnet:

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

Um zu bestimmen, ob das Label (1, 8, 0, 1) vom Label (1, 0, 1, 0) aus erreichbar ist, haben wir die Gleichung:

(1, 8, 0, 1) = (1, 0, 1,0) + xD

was eine Lösung hat x=(0, 4, 5). Dies entspricht der Folge σ = 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

hat keine Lösung.

Der Matrix-Ansatz zur Analyse von Petri-Netzen ist sehr vielversprechend, hat aber auch einige Schwierigkeiten. Zunächst stellen wir fest, dass die Matrix D allein spiegelt die Struktur des Petrinetzes nicht vollständig wider. Transitionen, die sowohl Eingänge als auch Ausgänge von derselben Position haben (Schleifen), werden durch die entsprechenden Matrixelemente dargestellt D+ und D - , heben sich dann aber in der Matrix gegenseitig auf D = D + - D - . Dies spiegelt sich im vorherigen Beispiel durch die Position p 4 und den Übergang wieder t3.

Ein weiteres Problem ist das Fehlen von Sequenzinformationen im Startvektor. Betrachten Sie das Petri-Netz in Abb. 2. Angenommen, wir wollen feststellen, ob die Markierung (0, 0, 0, 0, 1) von (1, 0, 0, 0, 0) aus erreichbar ist. Dann haben wir die Gleichung

(1, 0, 0, 0, 0)=(0, 0, 0, 0, 1) + xD

Reis. 2. Ein weiteres Petri-Netz zur Veranschaulichung der Matrixanalyse

Diese Gleichung hat keine eindeutige Lösung, sondern reduziert sich auf eine Menge von Lösungen (a\f(o) =(1, x 2, x 6 - 1, 2x 6, x e - 1, x 6)). Es definiert die Beziehung zwischen Übergangstriggern. Wenn wir setzen x 6= 1 und x 2= 1, dann /(o) = (1, 1, 0, 2, 0, 1), aber dieser Triggervektor entspricht sowohl der Sequenz 44444. Start ist unbekannt.

Eine weitere Schwierigkeit besteht darin, dass das Lösen der Gleichung für die Erreichbarkeit notwendig, aber nicht ausreichend ist. Betrachten Sie das einfache Petri-Netz in Abb. 3. Wenn wir feststellen wollen, ob (0, 0, 0, 1) von (1, 0, 0, 0) aus erreichbar ist, müssen wir die Gleichung lösen

Reis. 3. Petrinetz, das zeigt, dass die Lösung der Matrixgleichung eine notwendige, aber nicht hinreichende Bedingung für die Lösung des Erreichbarkeitsproblems ist

Diese Gleichung hat eine Lösung f(a) = (1, 1), die zwei Folgen entspricht: Titte 2 und /3/t. Aber keine dieser beiden Übergangsfolgen ist möglich, da in (1,0, 0, 0) keine es keine 4 sind erlaubt. Daher reicht das Lösen der Gleichung nicht aus, um die Erreichbarkeit zu beweisen.

Kontrollfragen und Aufgaben

1. Erstellen Sie einen Petrinetzgraphen für das folgende Petrinetz:

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. Erstellen Sie einen Petrinetzgraphen für das folgende Petrinetz:

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 p4 ,p 4 ),

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

3. Geben Sie für das Petrinetz aus Aufgabe 1 zur Markierung m=(5,4,0,0) die erlaubten Übergänge an.

4. Geben Sie für das Petrinetz aus Aufgabe 2 für die Markierung m=(7,12,2,1) die erlaubten Übergänge an.

5. Zeigen Sie, dass ÈR(C,m)=N n , wobei míN n .

6. Beweisen Sie: Wenn m‘í R(C,m), dann R(C,m‘)î R(C,m).

7. Beweisen Sie, dass m‘í R(C,m) genau dann gilt, wenn R(C,m‘)î R(C,m).

8. Bauen Sie den Erreichbarkeitssatz für das Petrinetz aus Aufgabe 1 auf.

9. Konstruieren Sie die erreichbare Menge für das Petrinetz aus Aufgabe 2.

10. Petrinetze mit ihren Chips und Startregeln erinnern in vielerlei Hinsicht an Spiele, die ein Spielfeld haben: Dame, Backgammon, Him, Go usw. Sie können sich ein Spiel für eine oder vier Personen ausdenken, das aus einem Spiel besteht Feld (als Feld wird ein Petri-Netz verwendet) und ein Satz Chips. Die Token werden über die Positionen des Petri-Netzes verteilt, und die Spieler wählen abwechselnd die erlaubten Übergänge aus und starten sie. Definieren Sie die Spielregeln, indem Sie Folgendes vorsehen:

a Wie wird die Anfangsposition der Kacheln bestimmt? (Zum Beispiel beginnt jeder Spieler das Spiel mit einem Chip im Haus, oder jeder Spieler erhält nach Belieben n Plättchen auf dem gesamten Feld usw.).

b Was ist der Zweck des Spiels? (Erobern Sie die Chips Ihres Gegners; holen Sie sich die meisten Chips; werden Sie Ihre Chips so schnell wie möglich los usw.).

c Ist es notwendig, die Figuren für verschiedene Spieler anzumalen? (Legen Sie die Regeln zum Auslösen von Übergängen entsprechend fest.)

d Sollten wir nicht verschiedenen Übergängen Punkte zuweisen? (Dann wird die Punktzahl des Spielers durch die Summe der von ihm gefeuerten Übergänge bestimmt).

Beschreiben Sie auf dieser Grundlage das Spiel, geben Sie ein Beispiel für das Spiel.

11. Entwickeln Sie ein Programm, das das Spiel aus Übung 10 implementiert, wo Ihr Gegner ein Computer für ein gegebenes Petri-Netz ist.

12. Bauen Sie ein Simulationssystem, um ein Petri-Netz zu erstellen. Der Beginn erlaubter Übergänge wird durch den Benutzer des Simulationssystems eingestellt.

13. Weise Männer sitzen an einem großen runden Tisch, auf dem viele Gerichte der chinesischen Küche stehen. Zwischen den Nachbarn liegt ein Stäbchen. Allerdings werden zwei Essstäbchen benötigt, um chinesisches Essen zu essen, also sollte jeder Weise Essstäbchen von rechts und links nehmen. Das Problem ist, dass, wenn alle Weisen die Stöcke auf der linken Seite nehmen und dann darauf warten, dass die Stöcke auf der rechten Seite losgelassen werden, sie ewig warten und verhungern werden (Sackgassenzustand). Es ist notwendig, ein solches Petri-Netz zu bauen, das die Strategie für das Abhalten eines Abendessens vorgibt und keine Sackgassen hat.

14. Bauen Sie ein Petri-Netz auf, das einen endlichen Automaten darstellt, der das Zweierkomplement einer Binärzahl berechnet.

15. Erstellen Sie ein Petri-Netz, das einen endlichen Zustandsautomaten darstellt, um die Parität der eingegebenen Binärzahl zu bestimmen.

16. Erstellen Sie ein Petri-Netz, das einen endlichen Zustandsautomaten darstellt, der einen Trigger mit einem Zähleingang definiert.

17. Erstellen Sie ein Petri-Netz, das eine Zustandsmaschine darstellt, die einen Trigger mit separaten Eingängen definiert.

18. Entwickeln Sie einen Algorithmus zur Modellierung von Flussdiagrammen mit einem Petri-Netz.

19.PERT-Diagramm ist eine grafische Darstellung der Beziehungen zwischen den verschiedenen Phasen, aus denen das Projekt besteht. Ein Projekt ist eine Sammlung einer großen Anzahl von Aktivitäten, und Aktivitäten müssen abgeschlossen sein, bevor andere beginnen können. Außerdem nimmt jede Aufgabe eine gewisse Zeit in Anspruch. Werke werden grafisch durch Scheitelpunkte dargestellt, und Bögen werden verwendet, um Ursache-Wirkungs-Beziehungen zwischen ihnen darzustellen. Das PETR-Diagramm ist ein gerichteter Graph mit gewichteten Kanten. Die Aufgabe besteht darin, die Mindestzeit für die Fertigstellung des Projekts zu bestimmen. Entwickeln Sie einen Algorithmus zur Modellierung von PERT-Diagrammen unter Verwendung von Petri-Netzen.

20. Entwicklung eines auf Petri-Netzen basierenden Modells zur Simulation chemischer Reaktionen.

21. Erwägen Sie, keinen Baum, sondern einen Erreichbarkeitsgraphen zu erstellen. Wenn ein Knoten x einen nachfolgenden Knoten z mit m[z]=m[y] für einen nicht-begrenzten Knoten y erzeugt, wird ein entsprechend gekennzeichneter Bogen von x nach y eingeführt. Beschreiben Sie den Algorithmus zum Erstellen eines Erreichbarkeitsgraphen.

22. Zeigen Sie, dass der Erreichbarkeitsgraph-Konstruktionsalgorithmus konvergiert und untersuchen Sie seine Eigenschaften, indem Sie ihn mit dem Erreichbarkeitsbaum-Konstruktionsalgorithmus vergleichen.

23. Ein Erreichbarkeitsbaum kann nicht zur Lösung eines Erreichbarkeitsproblems verwendet werden, weil Informationen gehen im Zusammenhang mit der Einführung des Konzepts des Symbols w verloren. Es wird eingeführt, wenn wir bei der Markierung m‘ ankommen und auf dem Weg von der Wurzel zu m‘ gibt es eine Markierung m, so dass m‘>m. In diesem Fall können alle Markierungen der Form m+n(m‘-m) erhalten werden. Untersuchen Sie die Möglichkeit, den Ausdruck a+bn i anstelle von w zu verwenden, um Komponentenwerte darzustellen. Wenn Sie einen Erreichbarkeitsbaum definieren können, in dem alle Label-Vektoren Ausdrücke sind, dann wird die Lösung des Erreichbarkeitsproblems einfach durch Lösen des Gleichungssystems bestimmt.

24. Verallgemeinern Sie die Definition von Erhaltung, indem Sie negative Gewichte zulassen Was wäre eine vernünftige Interpretation eines negativen Gewichts? Ist das Problem der Bestimmung der Persistenz eines Petrinetzes lösbar, wenn negative Gewichte erlaubt sind?

25. Entwickeln Sie einen Algorithmus zur Bestimmung der Begrenztheit eines Petri-Netzes unter Verwendung eines Matrixansatzes zur Analyse.

26.Entwickeln Sie einen Algorithmus zur Lösung des Gleichheitsproblems zweier Petrinetze. Das Petri-Netz C 1 =(P 1 ,T 1 ,I 1 ,O 1) mit der Bezeichnung m 1 ist gleich dem Petri-Netz C 2 =(P 2 ,T 2 ,I 2 ,O 2) mit der Bezeichnung m 2, wenn R(C 1). ,m 1)= R(C 2 ,m 2).

27. Entwickeln Sie einen Algorithmus zur Lösung des Problems einer Teilmenge von zwei Petri-Netzen. Das Petri-Netz C 1 = (P 2 , T 2 , I 2 , O 2) mit der Bezeichnung m 2 ist eine Teilmenge des Petri-Netzes C 1 = (P 1 , T 1 , I 1 , O 1) mit der Bezeichnung m 1, wenn R( C 1 ,m 1)Н R(C 2 ,m 2).

28. Entwickeln Sie einen Algorithmus zur Lösung des Erreichbarkeitsproblems. In einem Petrinetz C=(P,T,I,O) mit Markierung m ist Markierung m‘ von m aus erreichbar, wenn m‘ ОR(C,m).

29. Entwickeln Sie einen Algorithmus für das Subtagging-Erreichbarkeitsproblem. Existiert für eine gegebene Teilmenge P’ ½ P und eine Markierung m‘ ein m‘‘ ¾R(C,m) mit m‘‘(p i)=m‘(pi) für alle p i ¾P‘?

30. Entwickeln Sie einen Algorithmus für das Nullerreichbarkeitsproblem. Gilt m‘íR(C,m) mit m‘(pi)=0 für alle p i ñP?

31. Entwickeln Sie einen Algorithmus für die Aufgabe, in einer Position Null zu erreichen. Existiert für eine gegebene Position p i ¾P m‘¾R(C,m) mit m‘(pi)=0?

32.Entwickeln Sie einen Algorithmus zur Lösung des Petrinetz-Aktivitätsproblems. Sind alle Transitionen t j ОT aktiv?

33. Entwickeln Sie einen Algorithmus zur Lösung des Problems der Aktivität eines Übergangs. Ist diese Transition t j ОT aktiv?

34. Ein Petri-Netz heißt reversibel, wenn es zu jedem Übergang t j † T einen Übergang t k † T gibt, so dass

#(pi,I(tj))=#(pi,O(tk)), #(pi,O(tj))=#(pi,I(tk)),

jene. für jeden Übergang gibt es einen weiteren Übergang mit umgekehrten Ein- und Ausgängen. Entwickeln Sie einen Algorithmus zur Lösung des Erreichbarkeitsproblems für reversible Petrinetze.

35. Entwickeln Sie einen Algorithmus zur Lösung des Gleichheitsproblems für reversible Petrinetze.

36. Die Aufgabe der Raucher. Jeder der drei Raucher macht kontinuierlich eine Zigarette und raucht sie. Um eine Zigarette herzustellen, braucht man Tabak, Papier und Streichhölzer. Einer der Raucher hat immer Papier, ein anderer immer Streichhölzer, der dritte immer Tabak. Der Agent hat einen endlosen Vorrat an Papier, Streichhölzern und Tabak. Der Agent legt die beiden Komponenten auf den Tisch. Ein Raucher mit einer dritten fehlenden Zutat kann eine Zigarette herstellen und rauchen und dies dem Agenten signalisieren. Der Agent platziert dann die anderen zwei der drei Zutaten und der Zyklus wiederholt sich. Schlagen Sie ein aktives Petri-Netz vor, das das Raucherproblem modelliert.

37. Ein Automaten-Petrinetz ist ein Petrinetz, in dem jede Transition genau einen Ausgang und einen Eingang haben kann, d.h. für alle t j ÞT ½I(t j)1=1 und ½O(t j)1=1. Entwickeln Sie einen Algorithmus zum Konstruieren eines endlichen Automaten, der äquivalent zu einem gegebenen Automaten-Petri-Netz ist.

38. Ein beschrifteter Graph ist ein Petri-Netz, in dem jede Position eine Eingabe für genau einen Übergang und eine Ausgabe für genau einen Übergang ist, d.h. für jeden Übergang p i ОP ½I(p i)1=1 und ½O(p i)1=1. Entwickeln Sie einen Algorithmus zur Lösung des Erreichbarkeitsproblems für beschriftete Graphen.

39. Betrachten Sie die Klasse der Petri-Netze, die sowohl als Graphen als auch als Automaten-Petri-Netze bezeichnet werden.

40. Bauen Sie ein Petri-Netz, das die in Anhang 8 beschriebenen Systeme simuliert. Beschreiben Sie die Ereignisse, die in dem System auftreten, und die Bedingungen, die das System beschreiben. Konstruieren Sie einen erreichbaren Baum für das konstruierte Petri-Netz. Beschreiben Sie die Zustände, in denen sich das System befinden kann.