PROSIDING
ISBN : 978-979-16353-8-7
A-12 NILAI EIGEN DAN VEKTOR EIGEN MATRIKS TERREDUKSI REGULER DALAM ALJABAR MAX-PLUS INTERVAL Siswanto1, Ari Suparwanto2, M. Andy Rudhito3 1
Mahasiswa S3 Matematika FMIPA UGM dan Staff Pengajar FMIPA UNS Surakarta, 2 Jurusan Matematika FMIPA Universitas Gadjah Mada Yogyakarta 3 FKIP, Universitas Sanata Dharma Yogyakarta 1 e-mail :
[email protected],
[email protected],
[email protected] Abstrak Misalkan himpunan bilangan real. Aljabar Max-Plus adalah himpunan max dilengkapi dengan operasi maksimum " " dan plus " " . Dibentuk himpunan I ()max yaitu himpunan yang anggotanya merupakan interval-interval tertutup dalam max . Himpunan I ()max dilengkapi dengan operasi " " dan " " disebut aljabar Max-Plus interval. Selanjutnya, dapat dibentuk himpunan matriks berukuran n n yang elemen-elemennya merupakan anggota himpunan I ()max
n n ditulis I ()nmax . Misalkan A I ()nmax dan
n [A, A] I (nmax )b dengan A [A,A] , matriks interval A dikatakan tak terreduksi
jika untuk setiap matriks A [A,A] tak terreduksi. Jika tidak demikian matriks interval A dikatakan terreduksi. Dalam penelitian ini akan dibahas tentang nilai eigen dan vektor eigen suatu matriks interval terreduksi reguler. Kata kunci : Aljabar Max-Plus interval, nilai eigen, vektor eigen, matriks terreduksi reguler.
PENDAHULUAN Aljabar Max-Plus adalah himpunan max , dilengkapi dengan operasi maksimum " " dan plus " " merupakan semiring idempoten yang komutatif. Aljabar Max-Plus telah digunakan untuk memodelkan dan menganalisis secara aljabar masalah perencanaan, komunikasi, produksi, sistem antrian dengan kapasitas berhingga, komputasi parallel, dan lalu lintas. (Baccelli, et.al [1]). Untuk menyelesaikan masalah jaringan dengan waktu aktifitas bilangan kabur seperti penjadwalan kabur dan sistem antrian kabur, aljabar Max-Plus telah digeneralisasi menjadi aljabar Max-Plus interval dan aljabar Max-Plus bilangan kabur. Aljabar Max-Plus interval yaitu himpunan I ()max dilengkapi dengan operasi " " dan " " , sedangkan aljabar Max-Plus " dan " " bilangan kabur yaitu himpunan F () dilengkapi dengan operasi " max
(Rudhito [6]). Dari himpunan max dapat dibentuk himpunan matriks berukuran n n yang n elemen-elemennya merupakan elemen max , dinotasikan dengan nmax . Himpunan ini Makalah dipresentasikan dalam Seminar Nasional Matematika dan Pendidikan Matematika dengan tema ” Kontribusi Pendidikan Matematika dan Matematika dalam Membangun Karakter Guru dan Siswa" pada tanggal 10 November 2012 di Jurusan Pendidikan Matematika FMIPA UNY
PROSIDING
ISBN : 978-979-16353-8-7
dilengkapi dengan operasi maksimum " " dan plus " " merupakan semiring yang n idempoten (Akian, et. al, [1], Butkovic [3], Konigsberg [5]). Demikian juga, m max yaitu himpunan matriks berukuran m n dalam aljabar Max-Plus. Khusus untuk n = 1,
diperoleh himpunan vektor dalam aljabar Max-Plus ditulis m max (Farlow [4]). n Misalkan A nmax , graf komunikasi dari A ditulis G(A). Jika G(A) terhubung kuat maka matriks A dikatakan tak terreduksi. Sebaliknya, jika G(A) tak terhubung kuat maka matriks A dikatakan terreduksi (Farlow [4], Konigsberg [5]). Farlow [4] dan Tam K. P [10] telah membahas di dalam aljabar Max-Plus beserta tafsirannya dalam teori graf, bahwa nilai eigen dan vektor eigen dari suatu matriks masing-masing adalah periode dan barisan dari suatu waktu aktifitas. Farlow [4] membahas khusus untuk matriks tak terreduksi, sedangkan Konigsberg [5] dan Schutter [7] selain membahas matriks tak terreduksi juga matriks terreduksi. Berkaitan dengan nilai eigen dan vektor eigen, Siswanto [8] dan Subiono [9] telah membahas tentang algoritma untuk menentukan nilai eigen dan vektor eigen suatu matriks dalam aljabar Max-Plus. Sejalan pada aljabar Max-Plus, muncul pula matriks dalam aljabar Max-Plus interval n mn yaitu I ()m max dan matriks dalam aljabar Max-Plus bilangan kabur yaitu F () max , serta nilai eigen dan vektor eigen matriks dalam aljabar Max-Plus interval dan aljabar Max-Plus bilangan kabur. Rudhito [6] telah membahas tentang nilai eigen dan vektor eigen matriks atas aljabar Max-Plus interval khusus untuk matriks tak terreduksi. Dalam makalah ini akan dibahas tentang nilai eigen dan vektor eigen matriks terreduksi dalam aljabar Max-Plus interval. Sebelum dibahas hasil utama dari makalah ini, terlebih dahulu akan ditinjau beberapa konsep dasar dan hasil-hasil yang mendukung pembahasan.
Definisi 1.1. Diberikan barisan x(k ) k yang dibangkitkan oleh sistem persamaan n linear x(k 1) A x(k ) dengan A nmax
dan x(0) n sebagai nilai awal.
Misalkan x(k ) ( x1 (k ), x2 (k ), ..., xn (k )) nmax sehingga untuk j 1, 2, ..., n , x j (k ) j lim ada. Vektor (1, 2 , ..., n ) disebut vektor waktu sikel. Jika semua k k i sama maka nilai ini disebut laju pertumbuhan asimtotik barisan x(k ) . Definisi 1.2. Suatu matriks dikatakan regular jika memuat paling sedikit satu unsur yang tidak sama dengan dalam setiap baris.
max vi . Definisi 1.3. Norma l untuk vektor v n didefinisikan oleh v i 1, 2, ..., n m n Lema 1.4. [4] Jika A m max matriks regular dan u, v maka
( A u ) ( A v) u v .
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 100
PROSIDING
ISBN : 978-979-16353-8-7
n Teorema 1.5. [4] Diberikan sistem x(k 1) A x(k ) untuk k 0 , A nmax reguler x(k , x(0)) dan nilai awal x(0) . Jika x(0) nilai awal sehingga lim ada maka nilai limit k k
ini sama untuk sebarang nilai awal y(0) n . n Lema 1.6. [4] Diberikan sistem x(k 1) A x(k ) untuk k 0 , A nmax tak
terreduksi dengan v vektor eigen yang bersesuaian dengan nilai eigen
maka
lim
x j (k , x(0))
k
k
untuk semua j 1, 2, ..., n dan x(0) n .
Teorema 1.7. [8,9] Jika untuk sebarang nilai awal x(0) ( , , ..., ) sistem x(k 1) A x(k ) memenuhi x(m) c x(n) untuk bilangan bulat m n 0 dan
x(k ) c . Selanjutnya, ( , , ..., ) dengan mn k k
bilangan real c maka lim
adalah suatu nilai eigen dari matriks A dengan vektor eigen diberikan oleh mn
v ( (m n 1) x(m i 1) . i 1
Selanjutnya, dibicarakan konsep aljabar Max-Plus interval dan matriks di dalamnya [6]. Interval tertutup x dalam max adalah suatu himpunan bagian dari max yang berbentuk x = [x,x] = { x max x m x m x} . Interval x dalam max disebut interval Max-Plus. Suatu bilangan x max dapat dinyatakan sebagai interval [x,x].
Definisi 1.8. Dibentuk I ()max {x = [ x, x ] x, x , m x m x } { ε } , dengan ε = [ , ] . Pada himpunan I ()max didefinisikan operasi " " dan " " dengan
x y [ x y, x y] dan x y [ x y, x y] untuk setiap x, y I ()max . Himpunan I ()max dilengkapi dengan operasi dan merupakan semiring idempoten komutatif dengan elemen netral ε [ , ] dan elemen satuan 0 [0, 0] . Selanjutnya
disebut
aljabar
Max-Plus
interval
dan
dinotasikan
dengan
I ()max I ()max ; , .
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 101
PROSIDING
ISBN : 978-979-16353-8-7
Definisi 1.10. Himpunan matriks berukuran m n dengan elemen-elemen dalam n I ()max dinotasikan dengan I ()m max yaitu
n I ()m max A = [Aij ] Aij I ()max ; i = 1, 2, ..., m, j = 1, 2, ..., n . Matriks anggota
n I ()m max disebut matriks interval Max-Plus. Selanjutnya matriks interval Max-Plus
cukup disebut dengan matriks interval. n Definisi 1.11. Struktur aljabar dari I ()nmax yang dilengkapi dengan operasi dan
n n I ()nmax ; , dinotasikan dengan I ()nmax
merupakan dioid (semiring yang
n idempoten), sedangkan I ()m max merupakan semimodul atas I ()max .
n m n Definisi 1.12. Untuk A I ()m max didefinisikan matriks A = [Aij ] max
dan
n A = [Aij ] m max masing-masing disebut matriks batas bawah dan matriks batas atas dari
matriks interval A. n Definisi 1.13. Diberikan matriks interval A I ()m max , dengan A dan A
masing-masing adalah matriks batas bawah dan matriks batas atas dari matriks A. n Didefinisikan interval matriks dari A yaitu [A, A] { A m A m A m A } dan max n I (m max ) b = { [A, A]
n A I ()m max } .
Definisi 1.14. n 1. Untuk α I ()max , [A, A], [B, B] I (m max ) b didefinisikan
i.
α [A, A] = [α A, α A]
ii.
[A, A] [B, B] = [A B, A B]
k k n 2. Untuk [A, A] I (m max )b , [B, B] I (max )b didefinisikan
[A, A] [B, B] = [A B, A B] .
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 102
PROSIDING
ISBN : 978-979-16353-8-7
n Teorema 1.15. [9] Struktur aljabar dari I (nmax )b yang dilengkapi dengan operasi
nn
n )b ; , merupakan dioid (semiring dan dinotasikan dengan I (max )b I (nmax n yang idempoten), sedangkan I (m max )b merupakan semimodul atas I ()max .
Semiring
nn
n n I ()nmax I ()nmax ; ,
n I (max )b I (nmax )b ; ,
dengan
isomorfis
pemetaan
dengan
n f : I ()nmax
semiring n * I (nmax )
n n . Sedangkan semimodul I ()m f (A) = [ A , A ], A I ()nmax max atas I ()max n isomorfis dengan semimodul I (m max )b atas I ()max . Dengan demikian untuk setiap
matriks interval A selalu dapat ditentukan interval matriks [ A, A ] dan sebaliknya untuk n n dapat ditentukan setiap interval matriks [ A, A ] I (nmax )b dengan A, A nmax n matriks interval A I ()nmax dimana [ Aij , Aij ] I ()max untuk setiap i dan j. n Dengan demikian matriks interval A I ()m max dapat dipandang sebagai interval n nn matriks [A, A] I (m max ) b . Interval matriks [A, A] I (max ) b disebut interval n matriks yang bersesuaian dengan matriks interval A I ()nmax dan dilambangkan
dengan A [A, A] . Akibat isomorfisme di atas maka berlaku
α A [α A, α A] , A B [A B, A B] dan A B [A B, A B] .
Definisi 1.16. Didefinisikan
I ()nmax x = [x1 , x 2 , ..., x n ] T xi I ()max ; i = 1, 2, ..., n . Himpunan I ()nmax 1 dapat dipandang sebagai I ()nmax . Unsur-unsur dalam I ()nmax disebut vektor interval
atas I ()max . Vektor interval x bersesuaian dengan interval vektor yaitu x [x , x] . n Definisi 1.17. Diberikan A I ()nmax . Skalar interval λ I ()max disebut nilai eigen
Max-Plus interval matriks interval A jika terdapat suatu vektor interval v I ()nmax dengan v ε n 1 sehingga A v =λ v . Vektor v disebut vektor eigen Max-Plus interval matriks interval A yang bersesuaian dengan λ . Berikut diberikan suatu teorema yang memberikan eksistensi nilai eigen interval Max-Plus suatu matriks interval.
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 103
PROSIDING
ISBN : 978-979-16353-8-7
n Teorema 1.18. [9] Diberikan A I ()nmax dengan A [ A, A ] . Skalar interval max (A) = [ max (A), max (A) ] , merupakan suatu nilai eigen Max-Plus interval matriks interval A, dimana max (A) dan max (A) berturut-turut adalah bobot rata-rata
maksimum sirkuit elementer dalam G(A) dan G(A) . n Definisi 1.19. Suatu matriks interval A I ()nmax dengan A [ A, A ] , dikatakan tak
terreduksi jika setiap matriks A [ A, A ] tak terreduksi. n Teorema 1.20. [9] Suatu matriks interval A I ()nmax , dengan A [ A, A ] , tak n terreduksi jika dan hanya A nmax tak terreduksi.
n Akibat 1.21. [9] Diberikan A I ()nmax , dengan A [ A, A ] . Jika matriks interval A
tak terreduksi maka max (A) = [max (A), max (A) ] merupakan nilai eigen interval Max-Plus tunggal matriks interval A. PEMBAHASAN Misalkan x(k 1) A x(k ) yaitu sistem persamaan dalam aljabar Max-Plus interval. Akan dibahas hasil penelitian yaitu tentang nilai eigen dan vektor eigen matriks interval terreduksi reguler. Pembahasan ini berkaitan dengan perilaku periodik dari suatu sistem persamaan dalam aljabar Max-Plus interval, sedangkan perilaku periodik dari suatu sistem persamaan berkaitan dengan vektor interval waktu sikel.
Definisi 2.1. Diberikan barisan x(k) = [x1 (k ), x 2 (k ), ..., x n (k )]T I ()nmax k ,
himpunan bilangan asli yaitu barisan yang dibangkitkan oleh x(k 1) A x(k ) x j (k ) x j x j sehingga untuk x j (k ) [ x j , x j ] , j 1, 2, ..., n , , dan bahwa k k k x j (k ) τ j lim ada. Vektor τ [τ1, τ 2 , ..., τ n ]T disebut vektor interval waktu sikel. k k Jika semua τ i sama maka interval ini disebut laju pertumbuhan asimtotik barisan vektor interval x(k ) . Misalkan
x(k) I ()nmax
k
barisan yang dibangkitkan oleh sistem
n dan x(0) I ()n sebagai nilai awal. x(k 1) A x(k ) , dengan A I ()nmax
Barisan x(k ) dapat ditulis x(k ) A k x(0) . Jika A matriks interval tak terreduksi, laju pertumbuhan asimtotik sebarang x j ( k ) , j 1, 2, ..., n merupakan nilai eigen n interval yang tunggal dari A. Selanjutnya, untuk A I ()nmax tak terreduksi dengan
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 104
PROSIDING
ISBN : 978-979-16353-8-7
nilai eigen interval λ dan vektor eigen interval v, maka nilai eigen interval dari A k adalah λ k dan vektor eigen intervalnya adalah v. Ini dinyatakan dalam lema berikut. n Lema 2.2. Jika v eigen vektor interval dari matriks tak terreduksi A I ()nmax dengan
nilai eigen interval λ maka A k v λ k v untuk semua k 0 . Bukti : Diperhatikan bahwa untuk n 0 berlaku : A (λ n v) (A λ n ) v (λ n A) v λ n (A v) λ n (λ v) λ ( n 1) v . Selanjutnya, bukti lema dilakukan dengan induksi matematika. i.
Untuk k = 1, A1 v λ 1 v A v λ v
ii.
Dianggap benar untuk k = n – 1, yaitu A ( n 1) v λ ( n 1) v
iii. Untuk k = n, A (λ ( n 1) v) λ n v A (A ( n 1) v) λ n v
(A A ( n 1) ) v λ n v A n v λ n v
Dari i, ii dan iii terbukti, A k v λ k v untuk semua k 0 . ■ Dari lema 2.2, yaitu A k v λ k v dan dari x(k ) A k x (0) , jika x (0)
dipilih
v
suatu
vektor
eigen
interval
maka
x (k ) A k x(0)
x(k ) A k v x(k ) λ k v . Dengan menggunakan operasi di dalam aljabar
konvensional bahwa, jika λ [λ, λ, ..., λ]T maka x(k ) k λ v x(k ) v k λ x j (k ) v j lim x(k ) v [kλ, kλ, ..., kλ]T sehingga berlaku λ atau k k k x j (k ) lim λ untuk j 1, 2, ..., n . Oleh karena itu, jika x(0) = v yang merupakan k k vektor eigen interval maka laju pertumbuhan asimtotik dari x(k) adalah nilai eigen interval yang bersesuaian dengan vektor eigen interval v dari matriks interval A. Selanjutnya, bagaimana jika barisan x(k) diberikan nilai awal selain vektor eigen interval dari A. Untuk pembicaraan ini, diperlukan norma l yang dimodifikasi untuk vektor interval v I ()n dan beberapa lema. Definisi 2.3. Untuk n = 1, berarti v = [v, v] I () . Didefinisikan v v - v , untuk v v . v untuk v = v = v
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 105
PROSIDING
ISBN : 978-979-16353-8-7
Lema 2.4. Misalkan v = [v, v] I () maka v yang didefinisikan pada definisi 2.3 merupakan norma dari v I () . Bukti : Ambil v = [v, v], w = [w, w] I () dan . i. a. Jika v = [v, v] dengan v v maka
v
= [ v, v]
v v (v v) [v, v]
v .
b. Jika v = [v, v] dengan v = v = v maka
v
= [ v, v]
v v v .
Jadi v = v . ii. a. Jika v = [v, v], w = [w, w] I () dengan v v dan w w maka v+w = [v, v] [w, w] [v w, v w] v w (v w) (v v) (w w)
v + w . b. Jika v = [v, v], w = [w, w] I () dengan v = v v dan w = w w maka v+w = [v, v] [w, w] [v w, v w] v+w v w v + w .
c. Jika v = [v, v], w = [w, w] I () dengan v v dan w = w w maka v+w = [v, v] [w, w] [v w, v w] v w (v w)
vv
v v+ w Jadi, v+w v + w . iii. v 0 , v I () dan v 0 v = 0 = [0,0].
Selanjutnya untuk n 2 , disajikan definisi dan lema berikut.
Definisi 2.5. Untuk setiap vektor interval v I ()n , v = [v1, v 2 , ..., v n ]T dengan
vi = [vi , vi ], i = 1, 2, ..., n didefinisikan max vi vi , jika i 1, 2, ..., n vi vi i 1, 2, ..., n v . vi , jika i 1, 2, ..., n vi = vi i 1,max 2, ..., n Lema 2.6. Misalkan vektor interval v I ()n , v = [v1, v 2 , ..., v n ]T
dengan
vi = [vi , vi ], i = 1, 2, ..., n maka v yang didefinisikan pada definisi 2.5 merupakan norma dari v I ()n .
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 106
PROSIDING
ISBN : 978-979-16353-8-7
Bukti : Ambil v, w I ()n dan dengan v = [ [v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T dan w = [ [w1, w1 ], [w2 , w2 ], ...,[wn , wn ] ]T i. a. Untuk v = [ [v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T dimana i {1, 2, ..., n} vi vi . Berarti,
v = [[v1, v1 ], [v2 , v 2 ], ..., [v n , v n ] ]T = [ [ v1, v1 ], [ v 2 , v 2 ], ...,[ v n , v n ] ]T sehingga, v = max vi vi max vi vi i1,2,..., n i1,2,..., n
max
i1,2,..., n
vi vi v .
b. Untuk v = [ [v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T dimana i {1, 2, ..., n} vi vi . Berarti,
v = [[v1, v1 ], [v2 , v 2 ], ..., [v n , v n ] ]T = [ [ v1, v1 ], [ v 2 , v 2 ], ...,[ v n , v n ] ]T sehingga, v = max vi max vi max vi v . i1,2,..., n i1,2,..., n i1,2,..., n Jadi v = v . ii. a. Untuk v = [ [v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T dimana i {1, 2, ..., n} vi vi dan dan w = [ [w1, w1 ], [w2 , w2 ], ...,[wn , wn ] ]T dimana i {1, 2, ..., n} wi wi .
v + w = [[v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T
Berarti,
+ [[ w1, w1 ], [ w2 , w2 ], ...,[ wn , wn ]]T = [[v1 w1, v1 w1 ], [v 2 w2 , v 2 w2 ], ...,[v n wn , v n wn ]]T sehingga, v+w = max ( vi wi ) ( vi wi ) i1,2,..., n
=
max
(vi vi ) ( wi wi )
max
vi vi +
i1,2,..., n
i1,2,..., n
max
i1,2,..., n
wi wi v + w .
b. Untuk v = [ [v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T dimana i {1, 2, ..., n} vi vi dan dan w = [ [w1, w1 ], [w2 , w2 ], ...,[wn , wn ] ]T dimana i {1, 2, ..., n} wi wi .
v + w = [[v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T
Berarti,
+ [[ w1, w1 ], [ w2 , w2 ], ...,[ wn , wn ]]T = [[v1 w1, v1 w1 ], [v 2 w2 , v 2 w2 ], ...,[v n wn , v n wn ]]T sehingga, v+w = max vi wi i1,2,..., n
max
i1,2,..., n
vi
max
i1,2,..., n
wi v v + w
c. Untuk v = [ [v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T dimana i {1, 2, ..., n} vi vi dan Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 107
PROSIDING
ISBN : 978-979-16353-8-7
dan w = [ [w1, w1 ], [w2 , w2 ], ...,[wn , wn ] ]T dimana i {1, 2, ..., n} wi wi .
v + w = [[v1, v1 ], [v 2 , v 2 ], ...,[v n , v n ] ]T
Berarti,
+ [[ w1, w1 ], [ w2 , w2 ], ...,[ wn , wn ]]T = [[v1 w1, v1 w1 ], [v 2 w2 , v 2 w2 ], ...,[v n wn , v n wn ]]T sehingga, v+w = max ( vi wi ) ( vi wi ) i1,2,..., n
=
max
(vi vi ) ( wi wi )
max
vi vi v v + w
i1,2,..., n
i1,2,..., n
Jadi, v+w v + w . iii. v 0 , v I ()n dan v 0 v = [ [0,0],[0,0], ..., [0,0]]T Oleh karena itu, v yang didefinisikan pada definisi 2.3 dan definisi 2.5 merupakan norma dari v I ()n . n Definisi 2.7. Suatu matriks interval A I ()nmax dengan A [ A, A ] , dikatakan
regular jika untuk setiap matriks A [A, A] regular. n Lema 2.8. Matriks interval A I ()nmax dengan A [A, A] dikatakan regular jika n dan hanya jika A nmax regular.
Bukti : ( ) Menurut definisi 2.7, karena A [A, A] maka A regular. ( ) Diketahui A regular, berarti memuat paling sedikit satu unsur yang tidak sama dengan dalam setiap baris. Ambil A [ A, A ] sebarang. berarti A m A . Oleh karena itu, A memuat paling sedikit satu unsur yang tidak sama dengan dalam setiap baris. Dengan kata lain A reguler. Karena A sebarang maka setiap matriks A [ A, A ] regular. m n Lema 2.9. Jika A I ()m max matriks regular dan u, v I () dengan A [A, A] ,
u [u, u] dan v [v, v] maka (A u) (A v)
u v .
Bukti : Misalkan A u dan A v vektor interval berhingga dalam I ()m dengan
A u [A u, A u] dan A v [A v, A v] . Bukti diberikan untuk kasus jika i {1, 2,..., n} (A u)i (A u)i dan (A v )i (A v )i , sedangkan untuk kasus jika i {1, 2,..., n} (A u)i (A u)i dan (A v )i (A v )i sejalan bukti Teorema 1.4. didefinisikan β = (A u) (A v)
. Berarti bahwa, ada i0
1, 2, ..., m sehingga β (A u) (A v ) (A u) (A v ) i . Oleh i0 0 Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 108
PROSIDING
karena
ISBN : 978-979-16353-8-7
itu,
adalah
i0
indeks
dari
elemen
dalam
(A u) (A v) (A u) (A v) dengan nilai mutlak maksimum. i0 i0 Tanpa kehilangan keumuman misalkan bahwa β (A u) (A v ) (A u) (A v )i 0 . Menurut perkalian matrik i0 0
dalam aljabar Max-Plus, berarti β max ((ai0 j u j ) (ai0 j v j )) j1, 2, ..., n
max
(( ai j u j ) ( ai j v j )) . 0 0
l1, 2, ..., n
Oleh karena itu, ada suatu j0 1, 2, ..., n sehingga, β = ((ai0 j 0 u j0 ) (ai0 j0 v j0 ))
((ai j u j ) (ai j v j )) 0 0
max
l1, 2, ..., n
((ai0 j 0 u j0 ) (ai0 j0 v j0 )) ((ai j u j ) (ai j v j )) 0 0 0 0 0 0 (u j0 v j0 ) (u j v j ) 0
0
Ini mengakibatkan bahwa, β (u j0 v j0 ) (u j v j ) 0
max
j1, 2, ..., n
0
(u j v j ) (u j v j )
Terbukti, (A u) (A v)
(u j v j ) (u j v j )
max
j1, 2, ..., n
uv .
u v . ■ Dalam teorema berikutnya, dipandang x(0) tidak perlu merupakan vektor eigen interval dari A. Notasi x(k , x(0)) menyatakan vektor interval x(k ) dimulai dengan x(0) .
n Lema 2.10. Diberikan sistem x(k 1) A x(k ) untuk k 0 , A I ()nmax reguler x(k , x(0)) dan nilai awal x(0) . Jika x(0) mengakibatkan lim ada maka nilai limit ini k k
sama untuk sebarang nilai awal y(0) I ()n . x( k , x(0)) τ dengan τ I ()n . k k
Bukti : Misalkan bahwa, x(0) I ()n dan lim
Oleh karena itu, untuk sebarang y(0) I ()n diperoleh, x(k , y(0)) x( k , x(0)) 1 1 0 (A k y(0)) (A k x(0)) y(0) x(0) k k k k x(k , y(0)) x(k , x(0)) 1 0 . Untuk k maka y(0) x(0) 0 dan k k k x( k , y(0)) Akibatnya lim τ. ■ k k Menurut teorema ini, untuk suatu matriks interval regular jika vektor waktu sikel ada maka vektor ini tidak tergantung dari nilai awal. Selanjutnya, untuk suatu matriks tak terreduksi A, lema berikut menjamin eksistensi vektor waktu sikelnya. Menurut lema
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 109
PROSIDING
ISBN : 978-979-16353-8-7
2.10 dan lema 2.2, bahwa semua komponen vektor waktu sikelnya adalah λ untuk sebarang nilai awal. n Lema 2.11. Diberikan sistem x(k 1) A x(k ) untuk k 0 , A I ()nmax tak terreduksi dengan v vektor eigen interval yang bersesuaian dengan nilai eigen λ I () x j ( k , x(0)) maka lim λ untuk semua j 1, 2, ..., n dan x(0) I ()n . k k Bukti : Misalkan v suatu vektor eigen dari matriks interval A. Jika dipilih x j ( k , x(0)) λ untuk semua j. Karena A tak x(0) v I ()n diperoleh lim k k terreduksi maka A reguler dan v berhingga. Menurut lema 2.10, vektor waktu sikel ada dan tidak tergantung dari x(0). Dengan kata lain semua komponen vektor waktu sikelnya adalah λ untuk sebarang nilai awal. ■ Berdasarkan uraian sebelumnya, eksistensi nilai eigen interval dan vektor eigen interval untuk matriks interval terreduksi diberikan oleh teorema berikut :
Teorema
2.12.
Jika
untuk
sebarang
nilai
awal
x(0) [ε, ε, ..., ε]T sistem
x(k 1) A x(k ) memenuhi x(m) c x(n) untuk bilangan bulat m n 0 dan
x(k ) c . Selanjutnya, λ adalah [λ, λ, ..., λ]T dengan λ mn k k
interval c maka lim
suatu nilai eigen interval dari matriks A dengan vektor eigen diberikan oleh mn
v (λ ( m n 1) x(n i 1)) . i 1
Bukti : Diketahui bahwa untuk sebarang nilai awal x(0) [ε, ε, ..., ε]T sistem x(k 1) A x(k ) memenuhi x(m) c x(n) untuk bilangan bulat m n 0 dan
interval c. Misalkan l = m – n, sehingga x(k ) x(n il ) lim k k i n il lim
c i x(n ) n il i
lim
c i x( n) lim lim i n il i n il
ci x( n) c c c lim maka 0 . Jadi jika λ lim 0 mn mn i n il i n il l x(k ) [λ, λ, ..., λ]T . k k
vektor waktu sikelnya adalah lim
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 110
PROSIDING
ISBN : 978-979-16353-8-7
mn
Selanjutnya, jika v (λ ( m n 1) x( n i 1)) maka i 1
mn A v A (λ ( m n 1) x( n i 1) i 1 mn
(A (λ ( m n 1) x(n i 1))) i 1
mn
(λ ( m n 1) (A x( n i 1))) i 1
mn
(λ ( m n 1) (x(n i )) i 1
m n 1
(λ ( m n i 1) x(n i 1))
i 2
m n 1 λ (λ ( m n i ) x( n i 1)) i 2 mn λ (λ ( m n i ) x( n i 1)) λ v . ■ i 1 Berdasarkan teorema ini, berikut adalah langkah-langkah yang digunakan untuk n menentukan nilai eigen dan vektor eigen dari matriks A I ()nmax dilakukan secara berulang dari sistem x(k 1) A x(k ) sebagai berikut : Ambil sebarang vektor x(0) [ε, ε, ..., ε]T . i. Lakukan iterasi sistem x(k 1) A x(k ) sampai terdapat bilangan bulat m > n 0 dan interval sehingga perilaku periodik terjadi yaitu x(m) c x(n) . c ii. Hitung nilai eigen λ . mn mn
iii. Vektor eigen v (λ ( m n 1) x(n i 1)) . i 1
KESIMPULAN Dari hasil pembahasan dapat disimpulkan bahwa :
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 111
PROSIDING
ISBN : 978-979-16353-8-7
a. Matriks interval terreduksi regular A mempunyai nilai eigen interval dan vektor eigen interval jika vektor interval waktu sikelnya merupakan laju pertumbuhan asimtotik barisan x(k ) dari sistem persamaan linear x(k 1) A x(k ) . b. Batas bawah dan batas atas nilai eigen interval tersebut berturut-turut adalah nilai eigen Max-Plus matriks batas bawah dan nilai eigen Max-Plus matriks batas atas dari matriks intervalnya. c. Batas bawah dan batas atas vektor eigen interval tersebut berturut-turut adalah vektor eigen matriks batas bawah dan vektor eigen matriks batas atas dari matriks intervalnya. DAFTAR PUSTAKA [1]
Akian, M., Cohen, G., Gaubert, S., Quadrat, J. P., and Viot, M. 1994. Max-Plus Algebra and Applications to System Theory and Optimal Control. Proceedings of the International Congress of Mathematicians. Zurich, Switzerland. [2] Bacelli, F., Cohen, G., Olsder, G. J., Quadrat, J. P. 2001. Synchronization and Linearity, New York : John Wiley & Sons. [3] Butkovic, P., Tam K. P., 2009. On Some Properties of The Image of a Max Linear Mapping. Contemporary Mathematics. Volume 495. [4] Farlow, K. G. 2009. Max-Plus Algebra. Master's Thesis submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Masters in Mathematics. [5] Konigsberg Z. R. 2009. A Generalized Eigenmode Algorithm for Reducible Regular Matrices over the Max-Plus Algebra. International Mathematical Forum, 4. 24. 1157 – 1171. [6] Rudhito, Andy. 2011. Aljabar Max-Plus Bilangan Kabur dan Penerapannya pada Masalah Penjadwalan dan Jaringan Antrian. Disertasi : Program Studi S3 Matematika FMIPA UGM. Yogyakarta. [7] Schutter, B. D. 1996. Max Algebraic System Theory for Discrete Event Systems. Ph.D Thesis, Katholike Universiteit Leuven, Departement Elektrotechniek. [8] Siswanto. 2012. Nilai Eigen dan Vektor Eigen suatu Matriks Terreduksi dalam Aljabar Max-Plus. Prosiding Seminar Nasional Aljabar 2012 Jurusan Matematika UNDIP. 152 – 161. [9] Subiono. 2000. On Classes of Min-Max-Plus Systems and Their Applications, Published by Delf University Press. [10] Tam. K. P. 2010. Optimizing and Approximating Eigenvectors In Max-Algebra. A thesis Submitted to the University of Birmingham for The Degree of Doctor of Philosophy (PHD).
Seminar Nasional Matematika dan Pendidikan Matematika FMIPA UNY Yogyakarta, 10 November 2012
MA - 112