Dom

Kurs predavanja iz discipline

"Matrična analiza"

za studente 2. godine

Matematički fakultet specijalnost

"Ekonomska kibernetika"

(predavač Dmitruk Marija Aleksandrovna)

Poglavlje 3. Funkcije matrica.

1. Definicija funkcije. Df. Neka

– funkcija skalarnog argumenta. Potrebno je utvrditi šta se podrazumijeva pod f(A), tj. trebate proširiti funkciju f(x) na matričnu vrijednost argumenta.

Rješenje ovog problema je poznato kada je f(x) polinom: , tada .

Definicija f(A) u općem slučaju. Neka je m(x) minimalni polinom A i ima sljedeću kanoničku ekspanziju:

, su sopstvene vrijednosti A. Neka polinomi g(x) i h(x) imaju iste vrijednosti.

Neka je g(A)=h(A) (1), tada je polinom d(x)=g(x)-h(x) poništavajući polinom za A, pošto je d(A)=0, dakle d(x) ) je podijeljen linearnim polinomom, tj. d(x)=m(x)*q(x) (2). , , .

Zatim, tj. (3),

Dogovorimo se da m brojeva za f(x) nazovemo vrijednostima funkcije f(x) na spektru matrice A, a skup ovih vrijednosti će biti označen sa .

Ako je skup f(Sp A) definiran za f(x), tada je funkcija definirana na spektru matrice A.

Iz (3) proizilazi da polinomi h(x) i g(x) imaju iste vrijednosti na spektru matrice A.

Naše rezonovanje je reverzibilno, tj. od (3) Þ (3) Þ (1). Dakle, ako je data matrica A, tada je vrijednost polinoma f(x) u potpunosti određena vrijednostima ovog polinoma na spektru matrice A, tj. svi polinomi g i (x) koji imaju iste vrijednosti na spektru matrice imaju iste vrijednosti matrice g i (A). Zahtevamo da se određivanje vrednosti f(A) u opštem slučaju pridržava istog principa.

Vrijednosti funkcije f(x) na spektru matrice A moraju u potpunosti odrediti f(A), tj. funkcije koje imaju iste vrijednosti na spektru moraju imati istu vrijednost matrice f(A). Očigledno, za određivanje f(A) u opštem slučaju, dovoljno je pronaći polinom g(x) koji bi na spektru A poprimio iste vrijednosti kao funkcija f(A)=g(A).

Df. Ako je f(x) definiran na spektru matrice A, tada je f(A)=g(A), gdje je g(A) polinom koji na spektru uzima iste vrijednosti kao i f(A), .

Među polinomima iz C[x], koji uzimaju iste vrijednosti na spektru matrice A, kao f(x), stepen nije veći od (m-1), uzimajući iste vrijednosti na spektru A, kao f(x) - ovo je ostatak dijeljenja bilo kojeg polinoma g(x) koji ima iste vrijednosti na spektru matrice A kao f(x), do minimalnog polinoma m(x)=g( x)=m(x)*g(x)+r(x) ​​.

Ovaj polinom r(x) se zove interpolacijski polinom Lagrange-Sylvester za funkciju f(x) na spektru matrice A.

Komentar. Ako minimalni polinom m(x) matrice A nema višestruke korijene, tj. , zatim vrijednost funkcije na spektru.

Naći r(x) za proizvoljni f(x), ako je matrica

. Konstruirajmo f(H 1). Nađimo minimalni polinom H 1 - posljednji invarijantni faktor:

, 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-struki korijen od m(x), tj. n-struke vlastite vrijednosti H 1 .

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

Tri je rješenje za igru<=>, kada je rješenje igre, gdje je a bilo koji realan broj, k>0 POGLAVLJE 2. Igre sa nultom sumom u čistim strategijama 2.1 Izračunavanje optimalnih strategija na primjeru rješavanja problema Koristeći teoremu o minimaksu, možemo reći da je svaki igra sa nultom sumom ima optimalne strategije. Teorema: neka je A matrična igra i redovi datog...

Slike koje mu ne odgovaraju kandidati su za isključenje iz djelokruga korporacije. 5. Razvijanje korporativne strategije Prethodna analiza je postavila teren za razvoj strateških koraka za poboljšanje učinka diversifikovane kompanije. Glavni zaključak o tome šta učiniti zavisi od zaključaka koji se odnose na čitav niz aktivnosti u poslovanju...

Omogućava određivanje optimalnog slijeda izučavanja akademskih predmeta uključenih u nastavni plan i program. Svaki predmet u nastavnom planu i programu ima svoj broj.

Neka nastavni plan i program obuhvata 19 predmeta. Gradimo kvadratnu matricu sa osnovom koja je jednaka broju predmeta u nastavnom planu i programu (19).

Metodom stručne provjere iskusni nastavnici utvrđuju najznačajnije odnose između nastavnih predmeta. Stupci matrice smatraju se potrošačima, a redovi su nosioci informacija. Na primjer, za kolonu 10 važni nosioci informacija su redovi 7, 9, 11, odnosno znanja iz predmeta sa ovim brojevima. Ove linije u koloni se odražavaju jedinicama (1), odsustvo veze je predstavljeno nulama (0). Kao rezultat analize formirana je matrica devetnaestog reda. Matrična analiza se sastoji od uzastopnog uklanjanja kolona i redova. Kolone popunjene nulama ne primaju informacije od drugih subjekata, odnosno njihovo proučavanje nije zasnovano na logičkom odnosu sa drugim subjektima, iako oni zauzvrat mogu biti nosioci primarnih informacija. To znači da se prvo mogu proučavati predmeti koji imaju brojeve ovih kolona. Linije ispunjene nulama ne smatraju se nosiocima informacija i neće biti osnova za izučavanje drugih predmeta, što znači da se mogu izučavati posljednji.

Prvo se precrtavaju kolone 7, 8, 9, 18 i njihovi odgovarajući redovi. Dobijamo prvu redukovanu matricu petnaestog reda, koja zauzvrat ima nula stupaca 4, 16, 17. Nakon što smo ih se riješili, dobili smo drugu redukovanu matricu. Nakon što smo izvršili sve naknadne redukcije, dobijamo matricu u kojoj nema stupaca bez jedinica, ali ima nula redova, koji su također precrtani zajedno sa svojim odgovarajućim stupcima. Nakon dosljednog izvođenja sličnih radnji, dolazimo do matrice oblika prikazanog na dijagramu.

Rezultirajuća matrica odgovara grafikonu prikazanom na slici 3.2. Ovaj graf sadrži tri zatvorene dvostruke konture (13-15), (5-6), (11-10). Uz neku aproksimaciju, možemo pretpostaviti da se predmeti koji su uključeni u ove konture treba izučavati paralelno, a prvo se izučavaju predmeti pod brojem 13 i 15, a tek onda predmeti 5, 6, 10, 11.

Kao rezultat matrične analize, postaje moguće kreirati šematski (blok) model izučavanja predmeta u nastavnom planu i programu:

Na dijagramu je prikazan kombinovani sistem za povezivanje obrazovnih predmeta. Ćelije sadrže brojeve subjekata sa paralelnim proučavanjem. Formirani sistem povezivanja ne treba shvatiti kao obavezni niz povezivanja jedne grupe predmeta tek nakon završetka prethodne, već samo kao potrebu napredovanja u njihovom proučavanju. To samo ukazuje na opšti trend u povezivanju objekata.

Matrična analiza programa

Omogućava vam da procijenite logički slijed rasporeda edukativni materijal unutar predmeta i u skladu s tim ga poboljšati.

Neka akademski predmet sadrži 6 tema. Matrix A! sastavljen prema tematskom planu ovog nastavnog predmeta. Brojevi koji se razmatraju u smislu njihove upotrebe u proučavanju drugih tema pri sastavljanju matrice nalaze se okomito, brojevi smješteni horizontalno odgovaraju temama koje se razmatraju u smislu njihove upotrebe informacija iz drugih tema.

Da bismo identifikovali zatvorene konture, čije prisustvo ukazuje na nemogućnost uspostavljanja redosleda prolaska pojedinih tema, vršimo transformacije (skraćenje) matrice Au. Brišemo red 5, koji se sastoji od nula, i kolonu koja mu odgovara, kao i nultu kolonu 3 sa odgovarajućim redom. Formira se matrica A2.

U matrici A2 nedostaju redovi i stupci koji se sastoje samo od nula. Da bismo uspostavili zatvorene konture, predstavljamo graf koji odgovara matrici A2 (vidi sliku 3.3, a).

Na osnovu proučavanja grafa proizilazi da je prisustvo zatvorenih kontura uzrokovano odnosom sadržaja nastavnog materijala 1. i 6., kao i tema 4. i 6. Razlog navedenog odnosa je neuspješna preraspodjela sadržaja nastavnog materijala između ovih tema. Pregledom sadržaja ovih tema postaje moguće eliminisati postojeće zatvorene petlje grafa. Na taj način se formira novi graf (slika 3.3, b) i odgovarajuća matrica A3.

Smanjenje ove matrice daje novu matricu A4.

Nakon uklanjanja lukova (6, 4), (6, 1) i (1, 6), dobijamo novu početnu matricu B1 čiji graf nema zatvorene konture.

Sada kada su zatvorene petlje prekinute, počnimo s prilagođavanjem redoslijeda tema. Da bismo to učinili, redom ćemo izbrisati kolone koje se sastoje od nula i redova istog imena. Prilikom proučavanja tema koje odgovaraju ovim stupcima ne koriste se informacije iz drugih tema, pa se one mogu prvo proučiti.

U matrici! kolone 1 i 3 su nula. Dakle, tema 1 može zauzeti svoje mjesto u tematskom planu. Kada se ispitaju razlozi za postavljanje teme 3 ispred teme 2, ispada da se neke informacije o temi 2 nalaze u temi 3. Međutim, logičnije je i korisnije ostaviti ih u temi 3.

Nakon preuređivanja nastavnog materijala, umjesto luka (3, 2) dobijamo luk (2, 3); uklonimo kolonu 1 - dobijamo matricu B2.

Prijašnji broj 2 dodjeljujemo temi 2. Izbrišemo kolonu 2, red 2. Dobijamo matricu B3.

Teme 3 i 4 ostaju sa istim brojevima. Brišemo kolone 3, 4 sa odgovarajućim redovima; dobijamo matricu B4

Temi 6 je dodijeljen broj 5, a temi 5 broj 6.

Sastavljamo matricu C1 prema novoj distribuciji tema.

Hajde da transformišemo matricu uzastopnim uklanjanjem nula redova i kolona istog imena. Teme koje odgovaraju njima premještamo na kraj reda, jer se informacije iz ovih tema ne koriste prilikom proučavanja drugih tema. Temi 5 je dodijeljen broj 6.

Izbrišite red i kolonu 6. Dodijelite temu 6 broj 5.

Brišemo redove 4 i 3 i dodjeljujemo prethodne brojeve 4 i 3 temama koje na njih odgovaraju.

Teme 1 i 2 ostaju tematski iste. Kao rezultat obrade matrice dobija se sljedeći konačni raspored tema u strukturi predmeta:

Iz gornje sekvence jasno je da nakon matrične obrade strukture tematski plan Teme 5 i 6 su zamijenjene, potrebno je premjestiti edukativni materijal o temi 5 u temu 1, kao i iz teme 2 u temu 3.

Kao što se može vidjeti iz gornjeg primjera, matrična analiza strukture nastavnog materijala omogućava da se on u određenoj mjeri pojednostavi i poboljša. relativnu poziciju teme nastavnog plana i programa.

Treba imati u vidu da je za matričnu analizu nastavnih planova i programa potrebno mnogo praktično iskustvo i duboko poznavanje sadržaja obuke. Prije svega, to se odnosi na sastavljanje početne matrice, tačnije na utvrđivanje veza između akademskih predmeta ili obrazovne teme unutar objekta. Postoje mnoge veze između tako velikih elemenata kao što su programske teme, ali izvođači matrične analize moraju biti u stanju da "čitaju između redova" (pronađu skrivene, ali stvarno postojeće veze) i odrede značaj razne veze u odnosu na svrhe matrične analize, a ponekad i da bude kritičan prema sadržaju tema u obrazovnim predmetima.

UDC 681.51.011

MATRIČNA ANALIZA U SISTEMU UPRAVLJANJA PREDUZEĆEM

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

DOO "Samara - AviaGaz"

Samara State Aerospace University

U radu se analiziraju različiti načini upotrebe matrica u upravljanju preduzećima. Odnos (veza) između elemenata dva ili više skupova može se predstaviti u matričnom obliku. Kompozicija relacija omogućava da se pojednostavi analiza veza između elemenata skupova. Dat je primjer upotrebe matrica prioriteta u sistemu upravljanja preduzećem.

Matrice, kao alat za analizu, dugo se koriste u sistemima upravljanja preduzećima. Dovoljno je navesti takve alate kvaliteta kao što su matrični dijagrami, matrice prioriteta, matrična analiza u implementaciji funkcije kvaliteta.

1. Upotreba matrica u menadžmentu je zbog činjenice da gotovo svako preduzeće karakteriše veliki skup objekata (razna oprema, odjeli, dobavljači, potrošači), a veze između njih teško je opisati ovisnostima poput y = f (x). Prave veze su višedimenzionalne i implicitne. Matrice omogućavaju da se takve veze identifikuju u prilično jasnom obliku i da se izvrši njihova analiza. U zadatku formiranja proizvodne strukture preduzeća može se koristiti matrica odnosa između grupa delova B = ], gde je ^ broj

opšte opreme koja se koristi u obradi 1. i ]-tog dela, u marketinškom istraživanju se koristi matrica tehničkog nivoa i = \u^], gde je

i y - tehnički nivo 1. preduzeća na ]-tom tržištu i matrica cijena.

Sa matematičke tačke gledišta, specificiranje matrice može se tumačiti kao specificiranje odnosa (veze) između objekata dva skupa. Element matrice u ovom slučaju može značiti i vezu između objekata (kao što je „da“ ili „ne“), i snagu veze, izraženu brojem. U slučaju tri ili više skupova, moguće je graditi višedimenzionalne odnose i, shodno tome, višedimenzionalne matrice. Međutim, ovaj pristup gubi jasnoću i lakoću tumačenja. Složenost analize multivarijantnih odnosa

cije se mogu prevazići uz pomoć relacione kompozicije.

2. Pretpostavimo da preduzeće ima dobavljače Pn P2,...P5, koji isporučuju materijale (delove, sklopove, komponente) Mí, M2, M3. Od ovih materijala preduzeće proizvodi proizvode Ib I2,...I, za kupce (potrošače) Zi, Z2,...Z5. Za ove skupove moguće je kreirati matrice povezivanja. Neka, na primjer, uspostavimo veze između dobavljača i materijala koje isporučuju (Tabela 1), proizvoda i potrebnih materijala (Tabela 2), kupaca i proizvoda (Tabela 3). Znak “x” označava vezu objekata dva skupa.

Tabela 1. Matrica veza između dobavljača

i isporučeni materijal (P M)

PM Pi P2 Pz P4 P5

Tabela 2. Matrica veza između proizvoda i materijala (IM)

IM Mi M2 Mz

Tabela 3. Matrica veza između kupaca i proizvoda (ZI)

ZI II I2 Od Od

Koristeći kompoziciju relacija specificiranih matricama PM, IM i ZI, nije teško konstruisati matricu relacija PP. PZ matrica (Tabela 4) prikazuje veze koje je uspostavilo preduzeće između dobavljača P i kupaca Z^ Tako, na primer, interakcija kupca Z3 sa preduzećem se dešava na proizvodu I3, za koji su potrebni materijali M! i M3, isporučuje Pp P3 i P5.

Tabela 4. Matrica veza između dobavljača-

Detaljan opis tehnoloških procesa (proizvodnih linija) korišćenjem matrica odnosa pojednostavljuje određivanje dodane vrednosti za kupca, dobit i gubitke preduzeća.

3. Izgradnja sistema upravljanja kvalitetom preduzeća povezana je sa identifikacijom mreže procesa. Distribucija procesa među odjelima poduzeća, ispunjavanje zahtjeva standarda, na primjer, ISO 9001 -2000, može se izvršiti pomoću matrica. Recimo da su istaknuti sljedeći procesi: ugovaranje, upravljanje QMS dokumentacijom, interna revizija, nabavka, proizvodnja, praćenje zadovoljstva kupaca, a preduzeće ima odjele: odjel marketinga, odjel nabave, odjel glavnog projektanta, odjel glavnog tehnologa, proizvodnja, odjel za garancijsku podršku . Na osnovu rezultata razgovora sa predstavnicima odeljenja može se sastaviti PP matrica (tabela 5). S druge strane, namjenski procesi moraju pokrivati ​​zahtjeve standarda, na primjer ISO 9001-2000. Povezivanje procesa sa ISO 9001-2000 dovodi do TP matrice (tablica 6).

Koristeći kompoziciju relacija, dobijamo ISO matricu (tabela 7).

mi i kupci (PZ)

PZ Zi 32 Zz 34 35

Tabela 5. Matrica veza između procesa i odjela (PP)

PP matrica Odeljenje marketinga Odeljenje nabavke Odeljenje glavnog projektanta Odeljenje glavnog tehnologa Odeljenje za podršku u proizvodnji i garanciji

Zaključivanje ugovora X X

Interna revizija X

Kupovina X

Pravljenje X

Tabela 6. Odnos između procesa i ISO 9001-2000

TP Matrix Sistemi upravljanja kvalitetom Odgovornosti upravljanja Upravljanje resursima Procesi životni ciklus Mjerenje, analiza i poboljšanje proizvoda

Zaključivanje ugovora X

QMS Upravljanje dokumentima X X

Interna revizija X X

Kupovina X

Proizvodnja X X X

Praćenje zadovoljstva kupaca X

ISO Matrix Marketing Department Odeljenje nabavke Ch. Dizajnerski odjel Ch. tehnolog Odjel za podršku za proizvodnu garanciju

Sistemi upravljanja kvalitetom X X

Odgovornosti menadžmenta X X X

Upravljanje resursima X

Procesi životnog ciklusa proizvoda X X X

Mjerenje, analiza i poboljšanje X X

Očigledno, sa ovakvom raspodjelom ISO zahtjeva, nedosljednosti se mogu očekivati ​​u dijelu 5 „Odgovornost menadžmenta“, budući da je politika kvaliteta odgovornost najvišeg menadžmenta.

4. Proširivanje svakog elementa komunikacijske matrice, na primjer, “Odgovornost menadžmenta – odjel marketinga” može biti korištenjem matrice prioriteta koja je u osnovi metode analize hijerarhije. Zahtevi standarda serije ISO 9000-2000 utvrđuju obim i dubinu regulatorne i tehničke dokumentacije neophodne za funkcionisanje QMS-a preduzeća. Jedan od obaveznih dokumenata QMS-a preduzeća je politika i ciljevi kvaliteta. Ciljevi preduzeća su formulisani u različitim oblastima: finansije, tržište, konkurencija

(benchmarking), zadovoljstvo kupaca, poboljšanje performansi proizvoda i procesa. Ciljevi cijele organizacije moraju se projektovati (proširiti, dekomponovati) na njene odjele, tako da osoblje bude svjesno svoje uključenosti i odgovornosti za postizanje određenog cilja cijele organizacije.

Planiranje, odabir ciljeva, optimizacija ponašanja u konkurentskom okruženju uvijek zahtijevaju donošenje odluka u određenoj fazi. Postalo je gotovo očigledno da su društveni procesi, posebno procesi upravljanja, slabo formalizirani u okviru klasične matematike.

teme. U ovom slučaju, metoda analize i-r arhija može se pokazati prilično efikasnom.

Metoda analize hijerarhije zasniva se na takozvanoj matrici prioriteta. Pretpostavimo da je zadatak uporediti faktore koji utiču na odabrani objekat. Po pravilu, broj faktora koji utiču na to je prilično velik, tačne zavisnosti su nepoznate i gotovo je nemoguće izvršiti matematičku formalizaciju problema. Veštak takođe ima poteškoća u proceni uticaja faktora na objekat. Začudo, problem se lakše rješava ako se izvrši parno poređenje utjecaja faktora na objekt. (Poenta je da je teško odgovoriti na pitanje koliko je A težak; mnogo je lakše odlučiti šta je teže: A ili B)

Za analitičko planiranje razvoja preduzeća potrebno je opisati početno stanje (pozicija „kao što jeste“), ciljno stanje (ciljevi) i način povezivanja ovih stanja. U nastavku je dat primjer primjene metode analize hijerarhije kao cilj odabran je cilj iz politike kvaliteta „Održivi rast profita preduzeća“ i istaknuti neki faktori koji utiču na postizanje cilja (Tabela 8).

Stručnjaci i stručnjaci preduzeća sastavili su matrice prioriteta na osnovu odabranih kriterijuma (primer je dat u tabeli 9).

Upravljanje Materijalno-tehničko snabdevanje

Planiranje, nabavka,

Investicije, odnosi sa dobavljačima,

Oglašavanje, kontrola ulaza,

Prodajne cijene, kontrola resursa.

Marketing strategija. Kadrovi i razvoj

kvalifikacija za proizvodnju,

Ispoštovanje rokova, obuka osoblja,

Tehnologija, motivacija osoblja,

Kvalitet, kreativni potencijal,

Organizacija proizvodnje, kontrola troškova. planiranje novih razvoja

Tabela 9. Primjer matrice “Proizvodnja”.

Proizvodnja Usklađenost sa rokovima isporuke proizvoda Tehnologija Kvalitet Organizacija proizvodnje Kontrola troškova

Poštivanje rokova isporuke proizvoda 1 5 1 3 3

Tehnologija 1/5 1 3 1 3

Kvalitet 1 1/3 1 3 1

Organizacija proizvodnje 1/3 1 1/3 1 1

Kontrola troškova 1/3 1/3 1 1 1

Skala odnosa i popunjavanje tabela 1 - ekvivalencija faktora, 3 - dominacija jednog faktora nad drugim faktorom,

5 - jaka dominacija jednog faktora nad drugim faktorom, 2,4 - moguće međuvrijednosti.

Matematička obrada matrica sastojala se od pronalaženja vektora prioriteta kao svojstvenog vektora koji odgovara maksimalnoj svojstvenoj vrijednosti. Kao primjer, u nastavku su dati rezultati obrade procjena stručnjaka N (Tabela 10). Kolone označavaju komponente vektora prioriteta za različite faktore, na primjer, prema kriteriju "Upravljanje"

prioritet je dat investicijama.

Na sl. 1. Prikazani su rezultati proračuna prioriteta eksperata prema gore navedenim kriterijumima. Ostvarenje cilja povezano je sa ulaganjem, kvalitetom,

planiranje novih razvoja i kontrola resursa.

Tabela 10. Rezultati obrade stručnih N ocjena

Cilj - Održiv rast profita preduzeća

Menadžment Proizvodnja Mat - tehničko snabdevanje Kadrovi i razvoj

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

Menadžment

Proizvodnja

S & I ^ TO o i_ CO

Kadrovi i razvoj

Rice. 1. Rezultati proračuna prioriteta stručnjaka

Poznavanje raspodele prioriteta prema odabranim kriterijumima omogućava najvišem menadžmentu preduzeća da vodi zdravu politiku za postizanje postavljenog cilja.

Reference

1. Gludkin O.P., Gorbunov N.M., Gurov A.I., Zorin Yu.V. Totalno upravljanje kvalitetom. - M.: Radio i komunikacija, 1999.

2. Kuzin B., Yuryev V., Shakhdinarov G. Metode i modeli upravljanja kompanijom. -SPb: Petar, 2001.

3. Faure R., Kofman A., Denis-Papin M. Moderna matematika. - M.: Mir, 1966.

4. Saati T. Donošenje odluka. Metoda analize hijerarhije. / lane sa engleskog - M.: Radio i komunikacija, 1993.

MATRIČNA ANALIZA U IZVRŠNOM SISTEMU PREDUZEĆA

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

\cSamara - Aviagas"

Samara State Aerospace University

U radu se analiziraju različiti načini primjene matrica u poslovanju. Relacija (veza) između elemenata dva i više skupova može se prikazati u matričnom obliku. Kompozicija relacija omogućava da se pojednostavi analiza veza između elemenata skupova. Rezultat je primjer upotrebe matrica prioriteta u kontrolnom sistemu preduzeća.

Drugi pristup analizi Petrijevih mreža zasniva se na matričnom predstavljanju Petrijevih mreža. Alternativa definiranju Petrijeve mreže u obliku (P, T, I, O) je definiranje dvije matrice D - i D + koje predstavljaju ulazne i izlazne funkcije. Svaka matrica ima m redaka (jedan po prijelazu) i n stupaca (jedan po poziciji). Definirajmo D - = #(p i , I(t j)), i D + = #(p i , O(t j)). D - definira ulaze u prijelaze, D + - izlaze.

Matrični oblik Definicije Petrijeve mreže (P, T, D - , D +) su ekvivalentne standardnom obliku koji koristimo, ali dozvoljava definicije u terminima vektora i matrica. Neka je e[j] m-vektor koji sadrži nule svuda osim j-te komponente, jednako jedan. Prijelaz t j je predstavljen vektorom m reda e[j].

Sada je prijelaz t j u oznaci µ dozvoljen ako je µ > e[j] D - , a rezultat pokretanja prijelaza t j u oznaci µ je zapisan kao:

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

gdje je D = D + - D - kompozitna matrica promjena.

Tada za sekvencu pokretanja tranzicije σ = t j ​​1 , t j 2 , … , t jk imamo:

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

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

Vektor f(σ) = e + e + ... + e naziva se vektor početaka niza σ = t j ​​1 , t j 2 , ... , t jk , f(σ) j p je broj prijelaza počinje t p u nizu t j 1 , t j 2 , … , t jk . Vektor startova f(σ) je stoga vektor sa nenegativnim celobrojnim komponentama. (Vektor f(σ) je Parihovo preslikavanje niza σ = t j ​​1 , t j 2 , … , t jk).

Da bismo pokazali korisnost ovog matričnog pristupa Petrijevim mrežama, razmotrimo, na primjer, problem očuvanja: da li je dato označeno očuvanje Petrijeve mreže? Da bi se pokazalo očuvanje, potrebno je pronaći vektor pondera (koji nije nula) za koji je ponderisani zbir svih dostupnih oznaka konstantan.

Neka je w = (w 1 ,w 2 , … , w n) vektor stupac. Zatim, ako je µ početna oznaka, a µ" proizvoljno dostupna oznaka, tj. µ" pripada R(C,µ), potrebno je da µ w = µ" w. Sada, pošto je µ" dostupno, postoji niz pokretanih tranzicija σ = t j ​​1 , t j 2 , … , t jk , koji prenosi mrežu od µ do µ".

µ" = µ + f(σ) D

dakle,

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

Pošto ovo mora biti tačno za sve f(σ), imamo D w = 0.

Dakle, Petrijeva mreža je očuvana ako i samo ako postoji pozitivan vektor w takav da je D w = 0.

Ovo obezbjeđuje jednostavan algoritam za provjeru očuvanja i također omogućava da se dobije težinski vektor w.

Razvijena matrična teorija Petrijevih mreža je alat za rješavanje problema dosegljivosti. Pretpostavimo da je oznaka µ" dostupna od oznake µ. Tada postoji niz (moguće prazan) prijelaznih početaka σ koji vodi od µ do µ". To znači da je f(σ) nenegativno cjelobrojno rješenje sljedeće matrične jednadžbe za x:

µ" = µ + x D

Stoga, ako je µ" dosegljivo iz µ, onda zadata jednačina ima rješenje u nenegativnim cijelim brojevima; ako data jednadžba nema rješenja, tada je µ" nedostižno iz µ.

Razmotrimo, na primjer, označenu Petrijevu mrežu prikazanu na slici 1:

Rice. 1. Petrijeva mreža koja ilustruje metodu analize zasnovanu na matričnim jednačinama

Matrice D - i D + imaju oblik:

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

i matrica D:

U početnom označavanju µ = (1, 0, 1, 0), t 3 prelaz je omogućen i rezultira označavanjem µ" = (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).

Niz σ = t 3 , t 2 , t 3 , t 2 , t 1 je predstavljen vektorom lansiranja f(σ) = (1, 2, 2) i označen je µ":

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

Da bismo utvrdili da li je oznaka (1, 8, 0, 1) dostupna iz oznake (1,0, 1, 0), imamo jednačinu:

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

koja ima rešenje x =(0, 4, 5). Ovo odgovara nizu σ = 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

nema rješenje.

Matrični pristup analizi Petrijevih mreža je vrlo obećavajući, ali ima i određenih poteškoća. Prije svega imajte na umu da je matrica D samo po sebi ne odražava u potpunosti strukturu Petrijeve mreže. Prijelazi koji imaju i ulaze i izlaze sa iste pozicije (petlje) predstavljeni su odgovarajućim elementima matrice D+ i D - , ali se onda međusobno poništavaju u matrici D = D + - D - . Ovo se u prethodnom primjeru odražava na poziciji p 4 i prijelazu t 3.

Drugi problem je nedostatak informacija o sekvenci u vektoru lansiranja. Razmotrimo Petrijevu mrežu na sl. 2. Pretpostavimo da želimo da utvrdimo da li je oznaka (0, 0, 0, 0, 1) dostupna iz (1, 0, 0, 0, 0). Tada imamo jednačinu

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

Rice. 2. Još jedna Petrijeva mreža korištena za ilustraciju matrične analize

Ova jednadžba nema jedinstveno rješenje, ali se može svesti na mnoga rješenja (a\f(o) =(1, x 2, x 6 - 1, 2x 6, x e - 1, x 6)). Definira odnos između okidača tranzicije. Ako stavimo x 6= 1 i x 2= 1, tada /(o) = (1, 1, 0, 2, 0, 1), ali ovaj pokretački vektor odgovara i sekvenci 44444 i nizu 44444. Prema tome, iako je poznat broj okidača tranzicije, njihov narudžba lansiranja nepoznata.

Druga poteškoća je u tome što je rješavanje jednadžbe neophodno za dostižnost, ali nije dovoljno. Razmotrimo jednostavnu Petrijevu mrežu prikazanu na Sl. 3. Ako želimo da utvrdimo da li je (0, 0, 0, 1) dostupno iz (1, 0, 0, 0), moramo da rešimo jednačinu

Rice. 3. Petrijeva mreža koja pokazuje da je rješavanje matrične jednadžbe neophodan, ali ne i dovoljan uslov za rješavanje problema dosegljivosti

Ova jednadžba ima rješenje /(a) = (1, 1), koje odgovara dva niza: sisa 2 i /3/t. Ali nijedna od ove dvije prijelazne sekvence nije moguća, jer u (1,0, 0, 0) nijedna t it nije dozvoljeno ni 4. Dakle, rješavanje jednadžbe nije dovoljno za dokazivanje dosegljivosti.

Sigurnosna pitanja i zadatke

1. Konstruirajte graf Petrijeve mreže za sljedeću Petrijevu mrežu:

P=(p 1,p2,p3,p4), T=(t1,t2,t3,t4,t5),

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

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

I(t 3)=(p 2,p2,p4), O(t3)=(p1,p3),

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

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

2. Konstruirajte graf Petrijeve mreže za sljedeću Petrijevu mrežu:

P=(p 1,p2,p3,p4), T=(t1,t2,t3,t4),

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,p1,p1,p1,p1,p1), O(t3)=(p2,p2p2,p2p4,p4),

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

3. Za Petrijevu mrežu iz vježbe 1, za označavanje m=(5,4,0,0) označiti dozvoljene prijelaze.

4. Za Petrijevu mrežu iz vježbe 2, za označavanje m=(7,12,2,1) označiti dozvoljene prijelaze.

5. Pokazati da je ÈR(C,m)=N n, gdje je mÎN n.

6. Dokazati da ako je m‘O R(C,m), onda R(C,m‘)O R(C,m).

7. Dokažite da je m‘O R(C,m) ako i samo ako je R(C,m‘)O R(C,m).

8. Konstruirajte skup dosegljivosti za Petrijevu mrežu iz vježbe 1.

9. Konstruirajte skup dosegljivosti za Petrijevu mrežu iz vježbe 2.

10. Petrijeve mreže sa svojim čipovima i pravilima pokretanja po mnogo čemu podsjećaju na igre koje imaju teren za igru: dame, backgammon, nim, go, itd. Možete smisliti igru ​​za jednu do četiri osobe koja se sastoji od igranja polje (kao polje se koristi Petrijeva mreža) i set čipova. Čipovi se raspoređuju po pozicijama Petrijeve mreže, a igrači naizmjenično biraju dozvoljene prelaze i pokreću ih. Odredite pravila igre koja uključuju sljedeće:

a Kako se određuje početna lokacija čipova? (Na primjer, svaki igrač počinje igru ​​s jednim komadom u kućici, ili svaki igrač dobije n komada na cijelom polju po želji, itd.).

b Šta je cilj igre? (Uhvatite protivnikove žetone; uzmite najviše žetona; riješite se svojih žetona što je prije moguće, itd.).

c Zar figure ne bi trebale biti obojene za različite igrače? (Definirajte pravila za pokretanje prijelaza u skladu s tim).

d Zar ne bismo trebali dodijeliti bodove različitim prijelazima? (Tada su poeni igrača određeni zbirom tranzicija koje je on pokrenuo).

Na osnovu toga opišite igru, navedite primjer igre.

11. Razvijte program koji implementira igru ​​iz vježbe 10, gdje je vaš protivnik kompjuter za datu Petrijevu mrežu.

12. Izgradite simulacijski sistem za izvođenje Petrijeve mreže. Pokretanje dozvoljenih prelaza određuje korisnik simulacionog sistema.

13. Mudraci sjede kod velikih okrugli sto, koji ima puno kineskih jela. Između susjeda je jedan štapić. Međutim, za jelo kineske hrane potrebna su dva štapića, pa bi svaki mudrac trebao uzeti štapiće s desne i lijeve strane. Problem je u tome što će, ako svi mudraci uzmu štapove s lijeve strane, a zatim čekaju da se štapovi s desne strane oslobode, čekati zauvijek i umrijeti od gladi (stanje mrtve tačke). Potrebno je izgraditi Petrijevu mrežu koja postavlja strategiju za ručak i koja nema slijepe ulice.

14. Izgradite Petrijevu mrežu koja predstavlja konačnu mašinu koja izračunava komplement dva binarnog broja.

15. Izgradite Petrijevu mrežu koja predstavlja konačnu mašinu za određivanje parnosti ulaznog binarnog broja.

16. Izgradite Petrijevu mrežu koja predstavlja konačnu mašinu koja definiše okidač sa ulazom za brojanje.

17. Izgradite Petrijevu mrežu koja predstavlja konačnu mašinu koja definiše okidač sa odvojenim ulazima.

18. Razviti algoritam za modeliranje blok dijagrama koristeći Petrijevu mrežu.

19.PERT dijagram je grafički prikaz odnosa između različitih faza koje čine projekat. Projekat je zbirka veliki broj posao, a posao mora biti završen prije nego što drugi počnu. Osim toga, svaki posao zahtijeva određeno vrijeme za završetak. Radovi su grafički predstavljeni vrhovima, a lukovi se koriste da pokažu uzročno-posledične veze između njih. PETR dijagram je usmjereni graf s ponderiranim lukovima. Zadatak je odrediti minimalno vrijeme za završetak projekta. Razviti algoritam za modeliranje PERT dijagrama koristeći Petrijeve mreže.

20. Razviti model zasnovan na Petrijevim mrežama za simulaciju hemijskih reakcija.

21. Razmislite o izgradnji ne stabla, već grafa dosegljivosti. Ako vrh x generiše sledeći vrh z sa m[z]=m[y] za neki negranični vrh y, uvodi se odgovarajuće označeni luk od x do y. Opišite algoritam za izgradnju grafa dosegljivosti.

22.Pokažite da se algoritam za konstruisanje grafa dosegljivosti konvergira i istražite njegova svojstva upoređujući ga sa algoritmom za konstruisanje stabla dohvatljivosti.

23. Stablo dostupnosti se ne može koristiti za rješavanje problema dostupnosti, jer informacije se gube zbog uvođenja koncepta simbola w. Uvodi se kada dođemo do oznake m‘ i na putu od korijena do m‘ nalazi se oznaka m takva da je m‘>m. U ovom slučaju možete dobiti sve oznake oblika m+n(m’-m). Istražite mogućnost korištenja izraza a+bn i umjesto w za predstavljanje vrijednosti komponenti. Ako možete definirati stablo dosegljivosti u kojem su svi vektori označavanja predstavljeni izrazima, tada se rješenje problema dosegljivosti jednostavno određuje rješavanjem sistema jednačina.

24. Uopštiti definiciju očuvanja dozvoljavanjem negativnih težina. Šta bi se smatralo razumnim tumačenjem negativne težine? Da li je problem određivanja očuvanja Petrijeve mreže rješiv ako su dopuštene negativne težine?

25. Koristeći matrični pristup analizi, razviti algoritam za određivanje ograničenosti Petrijeve mreže.

26.Razviti algoritam za rješavanje problema jednakosti dvije Petrijeve mreže. Petrijeva mreža C 1 =(P 1 ,T 1 ,I 1 ,O 1) označena m 1 jednaka je Petrijevoj mreži C 2 =(P 2 ,T 2 ,I 2 ,O 2) označena m 2 ako je R(C 1 ,m 1)= R(C 2 ,m 2).

27.Razviti algoritam za rješavanje problema podskupa dvije Petrijeve mreže. Petrijeva mreža C 1 =(P 2 ,T 2 ,I 2 ,O 2) označena m 2 je podskup Petrijeve mreže C 1 =(P 1 ,T 1 ,I 1 ,O 1) označena sa m 1 ako je R( C 1 ,m 1)R R(C 2 ,m 2).

28. Razviti algoritam za rješavanje problema dostupnosti. U Petrijevoj mreži C=(P,T,I,O) sa oznakom m, oznaka m' je dostupna iz m ako je m'ÎR(C,m).

29. Razviti algoritam za problem dostupnosti podoznake. Za podskup P' Í P i oznaku m', postoji li m''ÎR(C,m) tako da je m''(p i)=m'(p i) za sve p i ÎP'?.

30. Razviti algoritam za problem nulte dostupnosti. Da li je m‘ÎR(C,m), gdje je m‘(p i)=0 za sve p i ÎP?

31. Razviti algoritam za problem dostizanja nule u jednoj poziciji. Za datu poziciju p i OP, postoji li m‘OR(C,m) sa m‘(p i)=0?

32. Razviti algoritam za rješavanje problema Petrijeve mreže. Da li su svi prijelazi t j OT aktivni?

33. Razviti algoritam za rješavanje problema aktivnosti jedne tranzicije. Da li je ovaj prelaz t j OT aktivan?

34. Petrijeva mreža se naziva reverzibilnom ako za svaki prijelaz t j OT postoji prijelaz t k OT takav da

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

one. za svaki prelaz postoji još jedan prelaz sa obrnutim ulazima i izlazima. Razviti algoritam za rješavanje problema dosegljivosti za invertibilne Petrijeve mreže.

35. Razviti algoritam za rješavanje problema jednakosti za invertibilne Petrijeve mreže.

36. Problem sa pušačima. Svaki od tri pušača neprekidno pravi cigaretu i puši je. Da biste napravili cigaretu, potrebni su vam duhan, papir i šibice. Jedan od pušača uvijek ima papir, drugi ima šibice, a treći duvan. Agent ima beskrajne zalihe papira, šibica i duhana. Agent stavlja dvije komponente na sto. Pušač koji ima treći sastojak koji nedostaje može napraviti i zapaliti cigaretu, signalizirajući to agentu. Zatim agens stavlja druga dva od tri sastojka i ciklus se ponavlja. Predložite aktivnu Petrijevu mrežu koja modelira problem pušača.

37. Automatska Petrijeva mreža je Petrijeva mreža u kojoj svaki prelaz može imati tačno jedan izlaz i jedan ulaz, tj. za sve t j OT ½I(t j)½=1 i ½O(t j)½=1. Razviti algoritam za konstruisanje konačnog automata koji je ekvivalentan datoj automatskoj Petrijevoj mreži.

38. Označeni graf je Petrijeva mreža u kojoj je svaka pozicija ulaz za tačno jedan prijelaz i izlaz tačno jednog prijelaza, tj. za svaki prelaz p i OP ½I(p i)½=1 i ½O(p i)½=1. Razviti algoritam za rješavanje problema dosegljivosti za označene grafove.

39. Razmotrimo klasu Petrijevih mreža koje su i označene grafove i automatske Petrijeve mreže.

40. Konstruirajte Petrijevu mrežu koja modelira sisteme opisane u Dodatku 8. Opišite događaje koji se dešavaju u sistemu i uslove koji opisuju sistem. Konstruirajte stablo dosegljivosti za izgrađenu Petrijevu mrežu. Opišite stanja u kojima sistem može biti.

Matrična analiza ili matrična metoda našla je široku upotrebu u komparativnoj procjeni različitih ekonomskih sistema (preduzeća, pojedinačne podjele preduzeća, itd.). Matrična metoda vam omogućava da odredite integralnu procjenu svakog preduzeća prema nekoliko indikatora. Ova procjena se naziva rejting preduzeća. Hajde da razmotrimo aplikaciju matrična metoda korak po korak koristeći konkretan primjer.

1. Izbor indikatora evaluacije i formiranje matrice početnih podataka a ij, odnosno tabele u kojima redovi odražavaju brojeve sistema (preduzeća), a kolone broj indikatora (i=1,2....n) - sistema; (j=1,2…..n) - indikatori. Odabrani indikatori moraju imati isti fokus (što više, to bolje).

2. Izrada matrice standardizovanih koeficijenata. U svakoj koloni se određuje maksimalni element, a zatim se svi elementi u toj koloni dijele sa maksimalnim elementom. Na osnovu rezultata proračuna kreira se matrica standardizovanih koeficijenata.

Odaberite maksimalan element u svakoj koloni.