BARISAN PANGKAT TERURUT MATRIKS PADA ALJABAR MAX PLUS
Nurwan1 Jurusan Matematika FMIPA Universitas Negeri Gorontalo
1
E-mail:
[email protected]
Abstrak n ×n ⊗ k +c A ∈ Rmax yang memenuhi A = λ ⊗c ⊗ A ⊗k . Matriks A adalah taktereduksi jika grap dari matriks A adalah strongly connected. λ adalah nilai eigen dari matriks A
Diberikan matriks
dan c adalah kesiklikan dari matriks A. Dalam tulisan ini dibahas kecenderungan akhir dan kesiklikan dari barisan pangkat terurut matriks pada aljabar max plus. Dari barisan pangkat terurut matriks kemudian dihitung nilai eigen dan kesiklikan. Hasil pembahasan diperoleh nilai eigen berkaitan dengan barisan pangkat terurut matriks pada aljabar max plus dan kecenderungan akhir dari barisan pangkat terurut matriks adalah siklik. Kata kunci : Aljabar Max Plus, Matriks Taktereduksi, Barisan Matriks, Nilai Eigen
1. Pendahuluan Aljabar max plus merupakan salah satu klas dalam sistem event diskrit yang memiliki banyak aplikasi. Aljabar max plus mendeskribsikan suatu sistem secara linear. Pendekatan aljabar max plus dapat menganalisis suatu sistem dengan waktu invarian max-linear. Pembahasan lebih mendalam tentang aljabar max plus dan aplikasinya dapat dilihat pada [1]. Banyak hal yang dapat dikaji dalam aljabar max plus, terutama yang berkaitan dengan model matematika dari suatu sistem event diskrit. Beberapa masalah sistem event diskrit yang telah dilakukan kajian menggunakan aljabar max plus diantaranya sistem manufaktur, jaringan telekomonikasi, sistem transportasi, sistem logistik dan lain sebagainya. Dalam tulisan ini dikaji tentang perilaku pangkat terurut matriks dalam aljabar max plus. Sistematika dari tulisan ini adalah diawali dengan kajian tentang penerapan aljabar max plus. Pada bagian kedua dari tulisan ini membahas tentang notasi dan definisi yang berkaitan dengan aljabar max plus serta pengemabangan aljabar max plus dalam bentuk matriks dan grap. Kemudian pada bagian ketiga dibahas lebih mendalam tentang koneksi matriks taktereduksi dengan grap. Pada bagian keempat dibahas barisan dalam aljabar max plus disertai dengan beberapa contoh untuk lebih
memahaminya. Pada bagian akhir dibahas perilaku pengkat terurut matriks dalam aljabar max plus disertai dengan kesimpulan.
2. Aljabar Max Plus Pada bagian ini dibahas definisi dan operasi dasar aljabar max plus yang akan digunakan dalam pembahasan pada tulisan ini. Operasi dasar aljabar max plus adalah maksimum yang direpresentasikan oleh ⊕ dan penjumlahan yang direpresentasikan oleh ⊗ . Didefinisikan ε = −∞ dan e = 0 dan notasi Rmax adalah himpunan R ∪ {ε } dengan R adalah himpunan bilangan real. Dua operasi tersebut didefinisikan sebagai berikut: x ⊕ y = max(x , y )
x ⊗y = x +y
(1)
dengan x , y ∈ R ∪ {−∞} , ε = −∞ dan R max = R ∪ {ε } . max(x , −∞ ) = max(−∞, x ) = x
x ∈ Rmax diperoleh
dan
x + (−∞ ) = (−∞ ) + x = −∞ ,
untuk
setiap
x ⊕ ε = ε ⊕ x = x dan x ⊗ ε = ε ⊗ x = ε (2) Simbol ⊕ dan ⊗ dalam aljabar max plus memiliki kesamaan dengan operasi dalam aljabar biasa. Untuk n ∈ N dan x ∈ Rmax maka didefinisikan pangkat dalam aljabar max plus sebagai berikut: x ⊗n = x ⊗ x ⊗ ... ⊗ x
(3)
n
Menyelesaikan Persamaan (3) sama halnya dengan aljabar biasa,
x ⊗n = x + x + ... + x n
(4)
=n ×x n ×n Diberikan matriks A ∈ Rmax , maka pangkat matriks dalam aljabar max plus didefinisikan sebagai berikut:
A ⊗ = En 0
A⊗ = A ⊗ A⊗ , k = 1,2,3... Pembahasan mendalam tentang pangkat matriks dalam aljabar max plus dapat dilihat pada [1, 2, 5 ]. k
Contoh 1 5⊗3 = 3 × 5 = 15
8
⊗
1 2
=
1 ×8 = 4 2
k −1
m ×n Operasi ⊕ dan ⊗ dapat diperluas dalam bentuk matriks. Jika A, B ∈ R max dan n×p C ∈ R max maka didapat
(A ⊕ B )ij = a ij ⊕ bij p
(A ⊗ C )ij = ⊕aik ⊗ c kj
(5)
k =1
untuk semua i,j. Matriks nol dengan ukuran m × n dalam aljabar max plus didefinisikan oleh (ξ m ×n )ij = ε , untuk semua i,j. Matriks En adalah matriks identitas dengan ukuran
n × n dalam aljabar max plus yang didefinisikan oleh (En )ij = 0 untuk semua i,j dan (En )ij = ε untuk semua i,j dan i ≠ j .
Perkalian dua matriks dalam aljabar max plus memiliki persamaan dengan perkalian dua matriks dalam aljabar biasa yaitu, perkalian dua matriks dalam aljabar biasa menggunakan operasi x dan + sedangkan perkalian dua matriks dalam aljabar max plus menggunakan operasi ⊕ dan ⊗ . Pembahasan lebih mendalam dapat dilihat pada [1,3] Contoh 2
2 3 3 5 Diberikan matriks A = dan B = , maka e 4 −1 4 2 3 3 5 3 5 A⊕B = B ⊕A = ⊕ = e 4 −1 4 e 4 max((2 + 3),(3 − 1)) max((2 + 5),(3 + 4)) 5 7 A ⊗B = = , dengan cara max((e + 3),(4 − 1)) max((e + 5),(4 + 4)) 3 8 5 9 yang sama diperoleh B ⊗ A = . Seperti halnya dalam aljabar biasa, perkalian 4 8 matriks dalam aljabar max plus juga tidak komutatif, sehingga A ⊗ B = B ⊗ A .
n n Elemen-elemen dari Rmax disebut vektor. Elemen ke-j dari sebuah vektor x ∈ Rmax n dinotasikan dengan xj. Vektor di Rmax dengan semua elemennya sama dengan ε
n disebut vektor unit dan dinotasikan dengan u. Untuk sebarang a ∈ R max , perkalian
a ⊗ u menghasilkan vektor dengan semua elemennya sama dengan a .
3. Grap dalam Aljabar Max Plus ×n Pada bagian ini dibahas suatu grap berarah dari suatu matriks A ∈ R nmax . Suatu grap berarah dari matriks A dinotasikan oleh G( A) = ( E, V ) . Grap G ( A) mempunyai n
titik, himpunan semua titik dari G ( A) dinyatakan oleh V . Himpunan semua garis dari suatu grap dinotasikan oleh dengan E. Bobot dari garis ( j, i ) adalah nilai dari ai , j . Bila a i , j = ε , maka garis ( j, i ) , tidak ada. Himpunan barisan garis
(i1 , i2 ), (i2 , i3 ), , (il −1 , il )
dari suatu grap dinamakan suatu path. Suatu path dikatakan
elementer bila tidak ada titik terjadi dua kali dalam path tersebut. Bobot rata-ratanya adalah bobot dari p dibagi oleh banyaknya garis dalam p , yaitu
(a
i2 ,i1
)
+ ai3 ,i2 + + ail ,il −1 l − 1 .
Sirkuit mean adalah bobot rata-rata dari suatu sirkuit. Sebarang sirkuit dengan sirkuit mean maksimum dinamakan sirkuit kritis. Suatu grap dikatakan strongly connected bila suatu path ada untuk setiap titik i ke setiap titik j . Dalam hal yang demikian matriks yang terkait dengan grap G ( A) ini dinamakan matriks taktereduksi. [5,7] Contoh 3 Diberikan matriks
ε 15 ε A= ε ε 14 10 ε 12 Grap dari matriks A pada Contoh 3 dapat dilihat pada Gambar 1
Gambar 1. Grap G(A) [1] Grap yang ada pada Gambar 1 terdiri dari tiga titik yaitu N (A ) = {1,2,3} , himpunan
{(1,3),(3,2),(2,1),(3,3)} ρ = ((1,3),(3,2),(2,1)) dan θ = (3,3) .
art
adalah
dan
mempunyai
dua
sirkuit
yaitu
4. Barisan Aljabar Max Plus Pada bagian ini dibahas konsep barisan dalam aljabar max plus yaitu barisan ultimately geometric dan ultimately periodic. Definisi 1 [4] Suatu barisan {gk }k =0 adalah ultimately geometric jika ∞
∃K ∈ N , ∃c ∈ N 0 , ∃λ ∈ Rmax
sedemikian
sehingga
∀k ≥ K
maka
berlaku
gk +c = λ ⊗ ⊗ gk c
Jika g adalah barisan ultimately geometric maka bilangan terkecil c pada Definisi (1) adalah periode dari g. Bilangan terkecil λ adalah rata-rata dari g. Definisi 2 [4]
Suatu barisan {gk }k =0 adalah ultimately periodic jika ∞
∃K ∈ N , ∃c ∈ N 0 , ∃λ0 ,..., λc −1 ∈ Rmax sedemikian sehingga gkc +c +s = λs ⊗ ⊗ gkc +s c
untuk semua ∀k ≥ K dan untuk s = 0,1,2..., c − 1 .
Jika barisan g adalah barisan ultimately periodic maka bilangan terkecil c pada definisi disebut periode, dan bilangan terkecil λs adalah rata-rata dari g. Secara umum penjumlahan barisan ultimately geometric dalam aljabar max plus adalah ultimately periodic. Untuk memahami definisi tersebut maka diberikan contoh. Contoh 4
Barisan g = {gk }k =0 = 0,0,0,2, ε ,0,8, ε ,6,14, ε ,12,20, ε ,18,... ∞
Perhatikan barisan tersebut, pada suku ke-6, ke-9, ke-12, ke-15 mempunyai rasio yang sama yaitu 6, dan suku ke-7, ke-10, ke-13 juga mempunyai suku yang sama yaitu 6. g6 = 6 ⊗ g 3 = 6 + g 3 = 6 + 0 = 6
g7 = 6 ⊗ g 4 = 6 + g 4 = 6 + 2 = 8
g8 = 6 ⊗ g5 = 6 + g5 = 6 + ε = ε
g9 = 6 ⊗ g6 = 6 + g6 = 6 + 0 = 6
gk +3 = 2⊗ ⊗ gk = 6 ⊗ gk = 6 + gk untuk semua k ≥ 3 3
g = {gk }k =0 = 0,0,0,2, ε ,0,8, ε ,6,14, ε ,12,20, ε ,18,... pada Contoh 4 disebut ∞
barisan ultimately geometric, dengan periode 3 dan laju adalah 1 untuk k ≥ 3 .
5. Barisan Matriks Aljabar Max Plus Pada bagian ini dibahas barisan matriks dalam aljabar max plus, kemudian melihat perilaku atau kecenderungan akhir dari barisan tersebut. Matriks yang akan dibahas pada bagian ini adalah matriks taktereduksi. Definisi 3 Sebuah matriks A disebut siklik jika ada c dan k sedemikian sehingga A k +c = A k untuk setiap k ≥ K . Bilangan terkecil c disebut kesiklikan dari matriks A dan A disebut c-siklik. Teorema n ×n Jika A ∈ Rmax adalah matriks taktereduksi, maka terdapat λ ∈ R max , k0 ∈ N , c ∈ N 0 sedemikian sehingga A ⊗
k +c
= λ⊗ ⊗ A⊗ c
k
λ adalah nilai eigen dari matriks A dan bersesuain dengan rata-rata maksimum dari semua sirkuit dari grap A ( G(A)) , c adalah kesiklikan dari matriks A. Contoh 5
−1 2 ε Diberikan matriks A = 2 1 2 ε 1 3
A
⊗2
A⊗
2
A
⊗3
−1 2 ε −1 2 ε max(−2,4, ε ) max(1,3, ε ) max(ε ,4, ε ) = 2 1 2 ⊗ 2 1 2 = max(1,3, ε ) max(4,2,3) max(ε ,3,5) ε 1 3 ε 1 3 max(ε ,3, ε ) max(ε ,4,4) max(ε ,3,6) 4 3 4 = 3 4 5 3 4 6 = A⊗A
⊗2
−1 2 ε 4 3 4 5 6 7 = 2 1 2 ⊗ 3 4 5 = 6 6 8 ε 1 3 3 4 6 6 7 9
−1 2 ε 5 6 7 8 8 10 A = A ⊗ A = 2 1 2 ⊗ 6 6 8 = 8 5 11 ε 1 3 6 7 9 9 10 12 Dengan cara yang sama diperoleh ⊗4
⊗3
10 11 13 = 11 12 14 12 13 15
A
⊗5
= A⊗A
⊗4
A
⊗6
= A⊗A
⊗5
A
⊗7
= A⊗A
⊗6
A
⊗8
= A⊗A
13 14 15 = 14 15 17 15 16 18
16 17 18 = 17 18 20 18 19 21
19 20 21 = 20 21 23 21 22 24
⊗7
Dari
perhitungan
barisan
pangkat
matriks
aljabar
A, A , A , A , A , A , A ,... diperoleh bentuk ⊗2
A⊗
k +1
⊗3
⊗4
⊗5
⊗6
⊗7
= 3 ⊗ A ⊗ untuk k = 5,6,7,... k
Dengan demikian diperoleh λ = 3 dan c = 1 . Contoh 6
3 ε 2 Diberikan matriks B = 3 −2 2 ε 4 ε B
⊗2
3 ε 2 3 ε 2 6 6 5 = B ⊗ B = 3 − 2 2 ⊗ 3 −2 2 = 5 6 5 ε 4 ε ε 4 ε 7 2 6
B
⊗3
= B ⊗B
⊗2
B
⊗4
= B ⊗B
⊗3
3 ε 2 6 6 5 9 9 8 = 3 −2 2 ⊗ 5 6 5 = 9 9 8 ε 4 ε 7 2 6 9 10 9
3 ε 2 9 9 8 12 12 11 = 3 −2 2 ⊗ 9 9 8 = 12 12 11 ε 4 ε 9 10 9 13 13 12
max
plus
B
⊗5
= B ⊗B
⊗4
B
⊗6
= B ⊗B
⊗5
B
⊗7
= B ⊗B
⊗6
B
⊗8
= B ⊗B
⊗7
Dari
3 ε 2 12 12 11 15 15 14 = 3 −2 2 ⊗ 12 12 11 = 15 15 14 ε 4 ε 13 13 12 16 16 15
3 ε 2 15 15 14 18 18 17 = 3 −2 2 ⊗ 15 15 14 = 18 18 17 ε 4 ε 16 16 15 19 19 18
3 ε 2 18 18 17 21 21 20 = 3 −2 2 ⊗ 18 18 17 = 21 21 20 ε 4 ε 19 19 18 22 22 21
3 ε 2 21 21 20 24 24 23 = 3 −2 2 ⊗ 21 21 20 = 24 24 23 ε 4 ε 22 22 21 25 25 24
perhitungan
barisan
pangkat
matriks
aljabar
max
plus
B , B , B , B , B , B , B ,... diperoleh bentuk ⊗2
B⊗
k +1
⊗3
⊗4
⊗5
⊗6
⊗7
= 3 ⊗ B ⊗ untuk k = 4,5,6,... k
Dengan demikian diperoleh λ = 3 dan c = 1 . 6. Penutup Dari hasil pembahasan diperoleh kesimpulan bahwa perilaku atau kecenderungan akhir dari barisan pangkat terurut matrik aljabar max plus memenuhi
A⊗
k +c
n ×n = λ ⊗ ⊗ A ⊗ dengan A ∈ Rmax . Kecenderungan akhir dari matriks pangkat c
k
terurut pada aljabar max plus adalah siklik. Nilai eigen berkaitan dengan barisan pangkat terurut matriks pada aljabar max plus. Untuk selanjutnya dapat dikaji perilaku akhir pangkat terurut matriks aljabar max plus untuk matriks tereduksi
7. Daftar Pustaka [1] B. Heidergott, G.J. olsder, and J. van der Woude, (2006). Max Plus at Work, Modell ing and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications, Princeton University Press. [2] Butkovic, P., R.A. Cuninghame-Green (2007), On Matrix Powers in MaxAlgebra, Linear Algebra and Its Application, 421(2007)370-381 [3] F. Baccelli, G. Cohen, G.J. olsder, and J.-P. Quadrat, (1992). Synchronization and linearity: an algebra for discrete event systems, Wiley. [4] Schutter D. B. (2000), On the Ultimate Behavior of the Sequence of Consecutive powers of a Matrix in the Max Plus Algebra, Linear Algebra and Its Application 307(2000)103-117
[5] Subiono (2000) On Classes of Min-Max-Plus System and Their Application, Trail Thesis, Delft University Press [6] Subiono (2000) Power Algorithms for (max,+)-and bipartite (min,max,+)systems, Discrete Event Dynamic Systems: Theory and Applications, 10(4):369389. [7] Subiono (2010), The existence of eigenvalues for reducible matrices in MaxPlus Algebra, Seminar Nasional Matematika UMM Malang
