Course of lectures on discipline

"Matrix Analysis"

for 2nd year students

Faculty of Mathematics specialty

"Economic cybernetics"

(lecturer Dmitruk Maria Alexandrovna)

Chapter 3. Matrix Functions.

1. Function definition.

Df. Let is a scalar argument function. It is required to define what is meant by f(A), i.e. we need to extend the function f(x) to the matrix value of the argument.

The solution to this problem is known when f(x) is a polynomial: , then .

Definition of f(A) in the general case.

Let m(x) be the minimal polynomial A and it has such a canonical decomposition , , are the eigenvalues ​​of A. Let the polynomials g(x) and h(x) take the same values.

Let g(A)=h(A) (1), then the polynomial d(x)=g(x)-h(x) is the annihilating polynomial for A, since d(A)=0, hence d(x ) is divisible by a linear polynomial, i.e. d(x)=m(x)*q(x) (2).

Then , i.e. (3) , , .

We will agree to call m numbers for f(x) such values ​​of the function f(x) on the spectrum of the matrix A, and the set of these values ​​will be denoted by .

If the set f(Sp A) is defined for f(x), then the function is defined on the spectrum of the matrix A.

It follows from (3) that the polynomials h(x) and g(x) have the same values ​​on the spectrum of the matrix A.

Our reasoning is reversible, i.e. from (3) Þ (3) Þ (1). Thus, if the matrix A is given, then the value of the polynomial f(x) is completely determined by the values ​​of this polynomial on the spectrum of the matrix A, i.e. all polynomials g i (x) that take the same values ​​on the spectrum of the matrix have the same matrix values ​​g i (A). We require that the definition of the value of f(A) in the general case obey the same principle.

The values ​​of the function f(x) on the spectrum of the matrix A must fully determine f(A), i.e. functions having the same values ​​on the spectrum must have the same matrix value f(A). Obviously, to determine f(A) in the general case, it suffices to find a polynomial g(x) that would take the same values ​​on the spectrum A as the function f(A)=g(A).

Df. If f(x) is defined on the spectrum of the matrix A, then f(A)=g(A), where g(A) is a polynomial that takes the same values ​​on the spectrum as f(A),

Df. The value of the function from the matrix A is the value of the polynomial from this matrix for .

Among the polynomials from С[x], which take the same values ​​on the spectrum of the matrix A, as f(x), of degree not higher than (m-1), which takes the same values ​​on the spectrum A, as f(x) is the remainder of the division any polynomial g(x) having the same values ​​on the spectrum of the matrix A as f(x) to the minimal polynomial m(x)=g(x)=m(x)*g(x)+r(x) .

This polynomial r(x) is called the Lagrange-Sylvester interpolation polynomial for the function f(x) on the spectrum of the matrix A.

Comment. If the minimal polynomial m(x) of matrix A has no multiple roots, i.e. , then the value of the function on the spectrum .

Find r(x) for arbitrary f(x) if the matrix

. Let us construct f(H 1). Find the minimal polynomial H 1 - the last invariant factor :

, 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-fold root m(x), i.e. n-fold eigenvalues ​​of H 1 .

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

Three of a kind is the solution to the game<=>, when is a solution to the game, where a is any real number, k>0 CHAPTER 2. Zero-sum games in pure strategies 2.1 Calculation of optimal strategies on the example of problem solving Using the minimax theorem, we can state that each antagonistic game has optimal strategies. Theorem: let A be a matrix game and the rows of the given...

A picture that does not match it is a candidate for exclusion from the scope of the corporation. 5. Developing a corporate strategy The previous analysis has set the stage for developing strategic steps to improve the performance of a diversified company. The main conclusion about what to do depends on the conclusions regarding the entire set of activities in the economic ...

It makes it possible to determine the optimal sequence for studying the subjects included in the curriculum. Each subject in the curriculum has its own number.

Let the curriculum include 19 subjects. We build a square matrix with a base, which is equal to the number of subjects in the curriculum (19).

The method of expert assessment by experienced teachers determines the most significant relationships between academic subjects. The columns of the matrix are considered consumers, and the rows are considered information carriers. For example, for column 10, lines 7, 9, 11 are important information carriers, that is, knowledge on subjects with these numbers. These rows in the column are reflected by ones (1), the absence of a cash connection - by zeros (0). As a result of the analysis, a matrix of the nineteenth order was formed. The analysis of the matrix consists in the sequential removal of columns and rows. Columns filled with zeros do not receive information from other subjects, that is, their study is not based on a logical relationship with other subjects, although they, in turn, can be carriers of primary information. This means that subjects that have numbers in these columns can be studied first. Lines filled with zeros are not considered information carriers and will not be the basis for studying other subjects, which means they can be studied last.

First, columns 7,8, 9,18 and their corresponding rows are crossed out. We get the first reduced matrix of the fifteenth order, which in turn has zero columns 4, 16, 17. Getting rid of them, we get the second reduced matrix. Having thus carried out all subsequent reductions, we obtain a matrix in which there are no columns without ones, but there are zero rows, which are also crossed out along with their corresponding columns. Having successively performed similar actions, we arrive at a matrix of this form, as shown in the diagram.

The formed matrix corresponds to the graph shown in Figure 3.2. This graph contains three closed double contours (13-15), (5-6), (11-10). With some approximation, we can assume that the subjects that entered these circuits should be studied in parallel, and first subjects with numbers 13 and 15 are studied, and only then subjects 5, 6, 10, 11.

As a result of the conducted matrix analysis, it becomes possible to create a schematic (block) model of the study of subjects in the curriculum:

The diagram shows a combined system for connecting educational subjects. The cells contain the numbers of subjects with parallel study. An educated connection system should be understood not as a mandatory sequence of connecting one group of subjects only after the end of the previous one, but only as a need to get ahead in their study. It only indicates a general trend in the connection of objects.

Matrix Analysis Program

Allows you to evaluate the logical sequence of the location educational material within the subject and improve it accordingly.

Let the subject include 6 topics. Matrix A! compiled according to the thematic plan of this academic subject. The numbers of topics that, when compiling the matrix, are considered in terms of their use in the study of other topics are arranged vertically, the numbers located horizontally correspond to the topics considered in terms of their use of information from other topics.

To identify closed loops, the presence of which indicates the impossibility of establishing the passage of the sequence of passage of individual topics, we carry out transformations (shortening) of the matrix Au. We delete row 5, consisting of zeros, and the column corresponding to it, as well as the zero column 3 with the corresponding row. Matrix A2 is formed.

The matrix A2 has missing rows and columns consisting of only zeros. To establish closed contours, we present the graph corresponding to the matrix A2 (see Fig. 3.3, a).

From the study of the graph, it follows that the presence of closed contours is caused by the relationship between the content of the educational material of topics 1 and 6, as well as topics 4 and 6. The reason for the noted relationship is the unsuccessful redistribution of the content of the educational material between these topics. After reviewing the content of these topics, it becomes possible to eliminate the existing closed contours of the graph. Thus, a new graph is formed (Fig. 3.3, b) and the corresponding matrix A3.

Reducing this matrix gives a new matrix A4.

After removing the arcs (6, 4), (6, 1) and (1, 6), we obtain a new initial matrix B1, the graph of which has no closed contours.

Now that the loops are broken, let's start adjusting the order of the topics. To do this, we will sequentially delete columns consisting of zeros and rows of the same name with them. Topics in these columns do not use information from other topics and can therefore be explored first.

In the matrix! columns 1 and 3 are null. Thus, topic 1 can take its place in the thematic plan. When examining the reasons for putting Topic 3 before Topic 2, it turns out that some of the information on Topic 2 takes place in Topic 3. However, it is more logical and more useful to leave them in Topic 3.

After rearranging the educational material, instead of the arc (3, 2) we get the arc (2, 3); delete column 1 - we get the matrix B2.

We assign the former number 2 to topic 2. Delete column 2 row 2. We get matrix B3.

Themes 3 and 4 remain with the same numbers. Delete columns 3, 4 with the corresponding rows; we get the matrix B4

Topic 6 is assigned number 5, and topic 5 is number 6.

We compose matrix C1 according to the new distribution of topics.

Let's carry out transformations of the matrix, sequentially deleting zero rows and columns with the same name. We move the topics corresponding to them to the end of the row, because the information of these topics is not used in the study of other topics. Topic 5 is assigned the number 6.

Delete row and column 6. Assign topic 6 number 5.

We delete lines 4 and 3 and the topics that answer them, assign the former numbers 4 and 3.

For topics 1 and 2, the same numbers remain in the thematic plan. As a result of the matrix processing, the following final arrangement of topics in the structure of the subject is obtained:

From the above sequence it can be seen that after the matrix processing the structures of the thematic plan, topics 5 and 6 were swapped. In addition, it became necessary to move the educational material on topic 5 to topic 1, as well as from topic 2 to topic 3.

As can be seen from the above example, the matrix analysis of the structure of the educational material makes it possible to streamline and improve it to a certain extent. mutual arrangement curriculum topics.

It should be taken into account that the matrix analysis of curricula and programs requires a lot of practical experience and in-depth knowledge of the content of the training. First of all, this refers to the compilation of the initial matrix, more precisely, to the definition of links between academic subjects or educational topics within the subject. There are many connections between such large elements as program topics, but matrix analysis performers must be able to "read between the lines" (find hidden but really existing connections), determine the significance various connections in relation to the goals of matrix analysis, and sometimes critically about the content of the topics of educational subjects.

UDK 681.51.011

MATRIX ANALYSIS IN THE ENTERPRISE MANAGEMENT SYSTEM

© 2006 A.V. Volgin1, G.E. Belashevsky2

LLC "Samara - AviaGaz"

Samara State Aerospace University

The paper analyzes various ways of using matrices in enterprise management. The relationship (connection) between the elements of two or more sets can be represented in matrix form. The composition of relations allows you to simplify the analysis of relationships between elements of sets. An example of the use of priority matrices in the enterprise management system is given.

Matrices, as an analysis tool, have long been used in the enterprise management system. Suffice it to name such quality tools as matrix charts, priority matrices, matrix analysis in Quality Function Deployment.

1. The use of matrices in management is due to the fact that almost any enterprise is characterized by a large set of objects (various equipment, divisions, suppliers, consumers), and it is difficult to describe the relationships between them with dependencies like y \u003d f (x) . Real connections are multidimensional and implicit. Matrices, on the other hand, make it possible to identify such relationships in a fairly visual form and analyze them. In the task of forming the production structure of an enterprise, a matrix of relationships between groups of parts B = ], where ^ is the number of units, can be used.

the main equipment used in the processing of the 1st and] -th parts, the technical level matrix u = \u^] is used in marketing research, where

and y - technical level of the 1st enterprise in the ] -th market and the price matrix.

From the standpoint of mathematics, the assignment of a matrix can be interpreted as a specification of a relationship (connection) between the objects of two sets. The matrix element in this case can mean both the connection of objects (such as "yes" or "no"), and the strength of the connection, expressed as a number. In the case of three or more sets, one can build multidimensional relations and, accordingly, multidimensional matrices. However, this approach loses clarity and ease of interpretation. The complexity of the analysis of multidimensional relations

ions can be overcome with the help of relationship composition.

2. Let's assume that the company has suppliers P1 P2, ... P5, which supply materials (parts, assemblies, components) Mі, M2, M3. From these materials, the enterprise manufactures products Ib I2, ... I, for customers (consumers) Zi, Z2, ... Z5. For these sets, you can compose matrices of connections. Suppose, for example, links are established between suppliers and the materials they supply (table 1), products and necessary materials (table 2), customers and products (table 3). The sign "x" denotes the connection of objects of two sets.

Table 1. Supplier Relationship Matrix

and supplied materials (PM)

PM Pі P2 Pz P4 P5

Table 2. Matrix of relations between products and materials (IM)

IM Mі M2 Mz

Table 3. Matrix of relationships between customers and products (PI)

ZI II I2 From From

Using the composition of the ratios given by the matrices PM, MI, and ZI, it is not difficult to compose a matrix of the ratio of PP. The PZ matrix (Table 4) shows the links established by the enterprise between suppliers P and customers Z^ So, for example, the interaction of the customer Z3 with the enterprise takes place on the product I3, which requires materials M! and M3 supplied by Pn P3 and P5.

Table 4. Relationship matrix between supplier-

Detailed scheduling of technological processes (product lines) with the help of relationship matrices simplifies the determination of added value for the customer, the profit of the enterprise and its losses.

3. The construction of an enterprise quality management system is associated with the allocation of a network of processes. The distribution of processes by business units, the implementation of the requirements of the standard, for example, ISO 9001-2000, can be carried out using matrices. Let's say the processes are highlighted: contracting, QMS documentation management, internal audit, procurement, manufacturing, monitoring customer satisfaction, and the company has divisions: marketing department, purchasing department, chief designer department, chief technologist department, production, warranty support department. Based on the results of discussion with representatives of departments, a PP matrix can be compiled (Table 5). On the other hand, dedicated processes should cover the requirements of a standard, such as ISO 9001-2000. Linking processes to ISO 9001-2000 results in a TP matrix (Table 6).

Using the composition of relations, we obtain the ISO matrix (Table 7).

us and customers (PP)

ПЗ Зі 32 Зз 34 35

Table 5. Matrix of links between processes and departments (SP)

PP matrix Marketing department Procurement department Chief designer department Chief technologist department Production Warranty support department

Contracting X X

Internal audit X

Procurement X

Manufacturing X

Table 6. Relationship of processes to ISO 9001-2000

TP matrix Quality management systems Management responsibility Resource management Processes life cycle products Measure, analyze and improve

Contracting X

QMS documentation management X X

Internal audit X X

Procurement X

Production X X X

Customer Satisfaction Monitoring X

ISO Matrix Marketing Department Purchasing Department Chap. designer department chap. technologist Production Warranty Support Department

Quality management systems X X

Management responsibility X X X

Resource management X

Product Life Cycle Processes X X X

Measurement, analysis and improvement X X

Obviously, with such a distribution of ISO requirements, inconsistencies can be expected in section 5 "Management responsibility", since the quality policy is the responsibility of top management.

4. Expanding each element of the relationship matrix, for example, "Management Responsibility - Marketing Department" can be using the priority matrix underlying the hierarchy analysis method. The requirements of the ISO 9000-2000 series establish the scope and depth of the regulatory and technical documentation necessary for the functioning of the enterprise's QMS. One of the obligatory documents of the QMS of the enterprise is the policy and goals in the field of quality. The goals of the enterprise are formulated in various areas: finance, market, competition

(benchmarking), customer satisfaction, improvement of product and process performance. The goals of the entire organization should be projected (deployed, decomposed) into its divisions, so that the staff is aware of their involvement and responsibility for achieving a particular goal of the entire organization.

Planning, choosing goals, optimizing behavior in a competitive environment always require a decision at a certain stage. It became practically obvious that social processes, in particular, management processes, are poorly formalized within the classical framework.

topics. In this case, the method of analyzing hierarchies can be quite effective.

The method of analysis of hierarchies is based on the so-called priority matrix. Assume that the task is to compare the factors influencing the selected object. As a rule, the number of influencing factors is quite large, the exact dependencies are unknown, and it is practically impossible to perform the mathematical formalization of the problem. The expert also experiences difficulties in assessing the influence of factors on the object. Surprisingly, the problem is solved more easily if a pairwise comparison of the influence of factors on the object is carried out. (The bottom line is that it is difficult to answer the question how much A weighs, it is much easier to decide which is heavier: A or B)

For analytical planning of the development of an enterprise, it is necessary to describe the initial state (the “as is” position), the target state (goals) and the means to link these states. Below is an example of applying the hierarchy analysis method, as an object, the goal from the quality policy “Sustainable growth in enterprise profits” is selected and some factors influencing the goal are highlighted (Table 8).

Specialists - experts of the enterprise compiled priority matrices according to the selected criteria (an example is given in table 9).

Management Logistics

Planning, Procurement,

Investments, supplier relationships,

Advertising, entrance control,

Selling prices, control of resources.

Marketing strategy. Personnel and Development

production qualification,

Compliance with deadlines, staff training,

Technology, staff motivation,

Quality, creativity,

Organization of production, cost control. planning new developments

Table 9. Example of the matrix "Production"

Production Compliance with the terms of delivery of products Technology Quality Organization of production Cost control

Compliance with product delivery dates 1 5 1 3 3

Technology 1/5 1 3 1 3

Quality 1 1/3 1 3 1

Organization of production 1/3 1 1/3 1 1

Cost control 1/3 1/3 1 1 1

Scale of relationships and filling in tables 1 - equivalence of factors, 3 - dominance of one factor over another factor,

5 - strong dominance of one factor over another factor, 2.4 - possible intermediate values.

Mathematical processing of matrices consisted in finding the priority vector as an eigenvector corresponding to the maximum eigenvalue. As an example, below are the results of processing the estimates of expert N (table 10). The columns indicate the components of the vector of priorities by various factors, for example, by the criterion "Management"

Priority is given to investment.

On fig. 1. The results of calculating the priorities of experts according to the above criteria are given. Goal achievement is associated with investment, quality,

planning new developments and controlling resources.

Table 10. Results of processing the estimates of expert N

Goal - Sustainable growth of the company's profit

Management Production Mat - technical supply Personnel and development

0,1084 0,3268 0,3072 0,1625

0,4198 0,1280 0,2059 0,0773

0,1084 0,2829 0,1552 0,1007

0,2356 0,1002 0,3316 0,2080

0,1279 0,1621 0,4516

Management

Production

S&I^TO o i_CO

Personnel and Development

Rice. 1. Results of calculating the priorities of experts

Knowing the distribution of priorities according to the selected criteria allows the top management of the enterprise to pursue a reasonable policy to achieve the goal.

Bibliography

1. Gludkin O.P., Gorbunov NM., Gurov A.I., Zorin Yu.V. Total Quality Management. - M.: Radio and communication, 1999.

2. Kuzin B., Yuriev V., Shakhdinarov G. Methods and models of firm management. - St. Petersburg: Peter, 2001.

3. Faure R., Kofman A., Denis-Papin M. Modern mathematics. - M.: Mir, 1966.

4. Saati T. Decision making. Hierarchy analysis method. / per. from English. - M.: Radio and communication, 1993.

MATRIX ANALYSIS IN ENTERPRISE EXECUTIVE SYSTEM

© 2006 A.V. Volgin1, G.E. Belachewskij2

\cSamara - Aviagas»

Samara State Aerospace University

In work various ways of matrixes application in business operation are analyzed. The relation (connection) between elements of two and more sets can be submitted in the matrix form. The composition of relations allows to simplify the analysis of connections between elements of sets. The example of use of priorities matrixes in a control system of the enterprise is the result.

The second approach to the analysis of Petri nets is based on the matrix representation of Petri nets. An alternative to the definition of the Petri net in the form (P, T, I, O) is the definition of two matrices D - and D + , representing the input and output functions. Each matrix has m rows (one per transition) and n columns (one per position). Define D - = #(p i , I(t j)), and D + = #(p i , O(t j)). D - defines transition inputs, D + - outputs.

The matrix form of the definition of the Petri net (P, T, D - , D +) is equivalent to the standard form used by us, but allows definitions in terms of vectors and matrices. Let e[j] be an m-vector containing zeros everywhere except j-th component equal to one. The transition t j is represented by an m-row vector e[j].

Now the transition t j in the marking µ is allowed if µ > e[j] D - , and the result of running the transition t j in the marking µ is written as:

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

where D = D + - D - is a composite change matrix.

Then for the transition trigger sequence σ = t j ​​1 , t j 2 , … , t jk we have:

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

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

The vector f(σ) = e + e + ... + e is called the launch vector of the sequence σ = t j ​​1 , t j 2 , … , t jk , f(σ) j p is the number of runs of the transition t p in the sequence t j 1 , t j 2 , … , t jk . The trigger vector f(σ) is therefore a vector with non-negative integer components. (The vector f(σ) is the Parikh mapping of the sequence σ = t j ​​1 , t j 2 , … , t jk).

In order to show the usefulness of such a matrix approach to Petri nets, consider, for example, the conservation problem: is a given labeled Petri net preserving? In order to show conservation, it is necessary to find a (non-zero) weighting vector for which the weighted sum over all reachable markings is constant.

Let w = (w 1 ,w 2 , … , w n) be a column vector. Then, if µ is the initial marking and µ" is an arbitrary reachable marking, i.e. µ" belongs to R(C,µ), it is necessary that µ w = µ" w. Now, since µ" is reachable, there is a sequence of runs transitions σ = t j ​​1 , t j 2 , … , t jk , which takes the network from µ to µ". Therefore

µ" = µ + f(σ) D

Hence,

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

Since this must be true for all f(σ) , we have D w = 0.

Thus, a Petri net is preserving if and only if there exists a positive vector w such that D w = 0.

This provides a simple persistence check algorithm and also allows a weighting vector w to be obtained.

The developed matrix theory of Petri nets is a tool for solving the reachability problem. Assume that the marking µ" is reachable from the marking µ. Then there is a sequence (possibly empty) of transition starts σ that leads from µ to µ". This means that f(σ) is a non-negative integer solution of the following matrix equation for x:

µ" = µ + xD

Therefore, if µ" is reachable from µ, then given equation has a solution in non-negative integers; if the given equation has no solution, then µ" is unreachable from µ.

Consider, for example, the labeled Petri net shown in Figure 1:

Rice. 1. Petri net illustrating an analysis method based on matrix equations

The matrices D - and D + have the 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

p 3 1 0 1 p 3 0 1 0

p 4 0 1 0 p 4 0 0 1

and matrix D:

In the initial marking µ = (1, 0, 1, 0) the transition t 3 is allowed and leads to the marking µ" = (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).

The sequence σ = t 3 , t 2 , t 3 , t 2 , t 1 is represented by the launch vector f(σ) = (1, 2, 2) and is labeled µ":

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

To determine if the label (1, 8, 0, 1) is reachable from the label (1,0, 1, 0), we have the equation:

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

which has a solution x =(0, 4, 5). This corresponds to the sequence σ = 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

has no solution.

The matrix approach to the analysis of Petri nets is very promising, but it also has some difficulties. First of all, we note that the matrix D by itself does not fully reflect the structure of the Petri net. Transitions that have both inputs and outputs from the same position (loops) are represented by the corresponding matrix elements D+ and D - , but then cancel each other out in the matrix D = D + - D - . This is reflected in the previous example by the position p 4 , and the transition t3.

Another problem is the lack of sequence information in the launch vector. Consider the Petri net in fig. 2. Suppose we want to determine if the marking (0, 0, 0, 0, 1) is reachable from (1, 0, 0, 0, 0). Then we have the equation

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

Rice. 2. Another Petri net to illustrate matrix analysis

This equation does not have a unique solution, but reduces to a set of solutions (a\f(o) =(1, x 2, x 6 - 1, 2x 6, x e - 1, x 6)). It defines the relationship between transition triggers. If we put x 6= 1 and x 2= 1, then /(o) = (1, 1, 0, 2, 0, 1), but this trigger vector corresponds to both the sequence 44444. and the n0-sequence 44444. launch is unknown.

Another difficulty is that solving the equation is necessary for attainability but not sufficient. Consider the simple Petri net shown in Fig. 3. If we want to determine if (0, 0, 0, 1) is reachable from (1, 0, 0, 0), we need to solve the equation

Rice. 3. Petri net showing that the solution of the matrix equation is a necessary but not sufficient condition for solving the reachability problem

This equation has a solution f(a) = (1, 1) corresponding to two sequences: tit 2 and /3/t. But neither of these two transition sequences is possible, since in (1,0, 0, 0) neither t it neither 4 are allowed. Thus, solving the equation is not enough to prove reachability.

Control questions and tasks

1. Build a Petri net graph for the following Petri net:

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. Build a Petri net graph for the following Petri net:

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. For the Petri net from exercise 1 for marking m=(5,4,0,0) indicate the allowed transitions.

4. For the Petri net from exercise 2, for marking m=(7,12,2,1), indicate the allowed transitions.

5. Show that ÈR(C,m)=N n , where mнN n .

6. Prove that if m‘н R(C,m), then R(C,m‘)н R(C,m).

7. Prove that m‘н R(C,m) if and only if R(C,m‘)н R(C,m).

8. Build the reachability set for the Petri net from Exercise 1.

9. Construct the reachable set for the Petri net from Exercise 2.

10. Petri nets with their chips and launch rules are in many ways reminiscent of games that have a playing field: checkers, backgammon, him, go, etc. You can come up with a game for one or four people, consisting of a playing field (a Petri net is used as a field) and a set of chips. The tokens are distributed over the positions of the Petri net, and the players take turns choosing the allowed transitions and launching them. Define the rules of the game, providing for the following:

a How is the initial position of the tiles determined? (For example, each player starts the game with one chip in the house, or each player receives n tiles on the entire field at will, etc.).

b What is the purpose of the game? (Capture your opponent's chips; get the most chips; get rid of your chips as soon as possible, etc.).

c Is it necessary to color the pieces for different players? (Determine the rules for triggering transitions accordingly.)

d Shouldn't we assign points to different transitions? (Then the player's score is determined by the sum of the transitions he fired).

Based on this, describe the game, give an example of the game.

11. Develop a program that implements the game from exercise 10, where your opponent is a computer for a given Petri net.

12. Build a simulation system to perform a Petri net. The start of allowed transitions is set by the user of the simulation system.

13. Wise men sit at a large round table, which has a lot of Chinese dishes. Between the neighbors lies one chopstick. However, two chopsticks are needed to eat Chinese food, so every sage should take chopsticks from the right and left. The problem is that if all the sages take the sticks on the left side and then wait for the sticks on the right side to be released, they will wait forever and starve to death (dead end state). It is necessary to build such a Petri net that sets the strategy for holding a dinner and has no dead ends.

14.Build a Petri net representing a finite automaton that calculates the two's complement of a binary number.

15.Build a Petri net representing a finite state machine for determining the parity of the input binary number.

16.Build a Petri net representing a finite state machine that defines a trigger with a counting input.

17.Build a Petri net representing a state machine that defines a trigger with separate inputs.

18.Develop an algorithm for modeling flowcharts with a Petri net.

19.PERT-diagram is a graphical representation of the relationships between the various stages that make up the project. The project is a collection a large number jobs, where jobs must be completed before others can start. In addition, each job takes a certain amount of time to complete. Works are graphically represented by vertices, and arcs are used to show cause and effect relationships between them. The PETR diagram is a directed graph with weighted edges. The task is to determine the minimum time to complete the project. Develop an algorithm for modeling PERT diagrams using Petri nets.

20. Develop a model based on Petri nets to simulate chemical reactions.

21. Consider building not a tree, but a reachability graph. If a vertex x generates a subsequent vertex z with m[z]=m[y] for some non-boundary vertex y, an appropriately labeled arc from x to y is introduced. Describe the algorithm for constructing a reachability graph.

22. Show that the reachability graph construction algorithm converges and examine its properties by comparing it with the reachability tree construction algorithm.

23. A reachability tree cannot be used to solve a reachability problem, because information is lost in connection with the introduction of the concept of the symbol w. It is introduced when we arrive at the marking m‘ and on the path from the root to m‘ there is a marking m such that m‘>m. In this case, all markings of the form m+n(m‘-m) can be obtained. Explore the possibility of using the expression a+bn i instead of w to represent component values. If you can define a reachability tree in which all label vectors are expressions, then the solution to the reachability problem is determined simply by solving the system of equations.

24. Generalize the definition of conservation by allowing negative weights. What would be a reasonable interpretation of a negative weight? Is the problem of determining the persistence of a Petri net solvable if negative weights are allowed?

25. Develop an algorithm for determining the boundedness of a Petri net using a matrix approach to analysis.

26.Develop an algorithm for solving the problem of equality of two Petri nets. Petri net C 1 =(P 1 ,T 1 ,I 1 ,O 1) labeled m 1 is equal to Petri net C 2 =(P 2 ,T 2 ,I 2 ,O 2) labeled m 2 if R(C 1 ,m 1)= R(C 2 ,m 2).

27.Develop an algorithm for solving the problem of a subset of two Petri nets. Petri net C 1 =(P 2 ,T 2 ,I 2 ,O 2) labeled m 2 is a subset of Petri net C 1 =(P 1 ,T 1 ,I 1 ,O 1) labeled m 1 if R( C 1 ,m 1)Н R(C 2 ,m 2).

28.Develop an algorithm for solving the reachability problem. In a Petri net C=(P,T,I,O) with marking m, marking m‘ is reachable from m if m‘ ОR(C,m).

29.Develop an algorithm for the subtagging reachability problem. Given a subset P’ Н P and a marking m‘, does there exist m‘’ ОR(C,m) such that m‘’(p i)=m‘(p i) for all p i ОP’?.

30.Develop an algorithm for the zero reachability problem. Does m‘нR(C,m), where m‘(p i)=0, hold for all p i нP?

31.Develop an algorithm for the task of reaching zero in one position. For a given position p i ОP, does m‘ОR(C,m) exist with m‘(p i)=0?

32.Develop an algorithm for solving the Petri net activity problem. Are all transitions t j ОT active?

33.Develop an algorithm for solving the problem of the activity of one transition. Is this transition t j ОT active?

34. A Petri net is called reversible if for each transition t j ОT there is a transition t k ОT such that

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

those. for each transition there is another transition with reverse inputs and outputs. Develop an algorithm for solving the reachability problem for reversible Petri nets.

35. Develop an algorithm for solving the equality problem for reversible Petri nets.

36. The task of smokers. Each of the three smokers continuously makes a cigarette and smokes it. To make a cigarette, you need tobacco, paper and matches. One of the smokers always has paper, another always has matches, the third always has tobacco. The agent has an endless supply of paper, matches and tobacco. The agent puts the two components on the table. A smoker with a third missing ingredient can make and smoke a cigarette, signaling this to the agent. The agent then places the other two of the three ingredients and the cycle repeats. Propose an active Petri net that models the problem of smokers.

37. An automaton Petri net is a Petri net in which each transition can have exactly one output and one input, i.e. for all t j ОT ½I(t j)1=1 and ½O(t j)1=1. Develop an algorithm for constructing a finite automaton that is equivalent to a given automaton Petri net.

38. A labeled graph is a Petri net in which each position is an input for exactly one transition and an output for exactly one transition, i.e. for each transition p i ОP ½I(p i)1=1 and ½O(p i)1=1. Develop an algorithm for solving the reachability problem for labeled graphs.

39. Consider the class of Petri nets that are both labeled graphs and automaton Petri nets.

40.Build a Petri net that simulates the systems described in Appendix 8. Describe the events that occur in the system and the conditions that describe the system. Construct a reachable tree for the constructed Petri net. Describe the states that the system can be in.

Matrix analysis or the matrix method has become widespread in the comparative evaluation of various economic systems (enterprises, individual divisions of enterprises, etc.). The matrix method allows you to determine the integral assessment of each enterprise for several indicators. This assessment is called the rating of the enterprise. Consider the application of the matrix method in stages using a specific example.

1. Selection of evaluation indicators and formation of a matrix of initial data a ij, that is, tables, where the numbers of systems (enterprises) are reflected in rows, and the numbers of indicators (i = 1,2 ... .n) - systems are reflected in columns; (j=1,2…..n) - indicators. The selected indicators should have the same focus (the more, the better).

2. Compilation of a matrix of standardized coefficients. In each column, the maximum element is determined, and then all elements of this column are divided by the maximum element. Based on the results of the calculation, a matrix of standardized coefficients is created.

We select the maximum element in each column.