Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Max-Plus Interval 1
M. Andy Rudhito, 2Sri Wahyuni, 3Ari Suparwanto, and 4F. Susilo
1
Mahasiswa S3 Matematika FMIPA UGM dan Staff Pengajar FKIP Universitas Sanata Dharma Paingan Maguwoharjo Yogyakarta 2,3
Jurusan Matematika FMIPA Universitas Gadjah Mada Sekip Utara Yogyakarta
4
Jurusan Matematika FST , Universitas Sanata Dharma Paingan Maguwoharjo Yogyakarta
e-mail :
[email protected],
[email protected],
[email protected],
[email protected]
Abstrak. Makalah ini membahas eksistensi dan ketunggalan nilai eigen dan vektor eigen matriks atas aljabar max-plus interval. Hasil pembahasan menunjukkan bahwa setiap matriks atas aljabar max-plus interval mempunyai nilai eigen, yaitu nilai eigen interval max-plus maksimum, dan vektor eigen interval max-plus yang bersesuaian dengan nilai eigen tersebut. Batas bawah dan batas atas nilai eigen interval max-plus maksimum tersebut berturut-turut adalah nilai eigen max-plus maksimum matriks batas bawah dan nilai eigen max-plus maximum matriks batas atas dari matriks intervalnya. Jika matriks atas aljabar max-plus interval tersebut irredusibel maka nilai eigennya tunggal.
Kata-kata kunci: aljabar max-plus, interval, nilai eigen dan vektor eigen.
1. Pendahuluan Dalam masalah pemodelan dan analisa suatu jaringan, kadang-kadang waktu aktifitasnya belum diketahui. Hal ini misalkan karena jaringan masih pada tahap perancangan, data-data mengenai waktu aktifitas belum diketahui secara pasti maupun distribusinya. Waktu aktifitas ini dapat diperkirakan berdasarkan pengalaman maupun pendapat dari para ahli maupun operator jaringan tersebut. Untuk itu waktu aktifitas jaringan dimodelkan dalam suatu bilangan kabur (fuzzy number). Akhir-akhir ini telah berkembang pemodelan jaringan yang melibatkan bilangan kabur. Untuk masalah penjadwalan yang melibatkan bilangan kabur dapat dilihat pada Chanas, S., Zielinski, P. (2001). Sedangkan untuk masalah model jaringan antrian yang melibatkan bilangan kabur dapat dilihat pada Lüthi, J., Haring, G. (1997). Pemodelan dan analisa sifat periodik sistem jaringan yang melibatkan bilangan kabur, sejauh penulis ketahui, belum ada yang menggunakan pendekatan aljabar maxplus. Dalam pemodelan suatu sistem jaringan dengan pendekatan aljabar max-plus, graf untuk jaringan tersebut dinyatakan dengan menggunakan matriks, dengan unsurunsurnya menyatakan waktu aktifitas antar titik pada jaringan tersebut. Selanjutnya sifat
Semnas Matematika dan Pendidikan Matematika 2008
1-8
Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Max-Plus Interval
periodik sistem dapat dianalisis melalui nilai eigen dan vektor eigen matriks atas aljabar max-plus (selanjutnya cukup disebut nilai eigen dan vektor eigen max-plus) seperti dalam Baccelli et.al (1992), Rudhito A (2003). Pemodelan waktu aktifitas jaringan dengan menggunakan bilangan kabur dengan pendekatan aljabar max-plus akan terkait dengan matriks yang unsur-unsurnya berupa bilangan kabur. Dengan mengikuti pola pemodelan dan analisa jaringan dengan menggunakan aljabar max-plus, maka konsep dasar yang akan terkait dengan analisa sifat periodik sistem adalah nilai eigen dan vektor eigen matriks atas aljabar max-plus bilangan kabur dari matriks dalam model tersebut. Operasi-operasi pada bilangan kabur dapat dilakukan menggunakan Teorema Dekomposisi, yaitu melalui potonganpotongan-α-nya yang berupa interval-interval (Susilo, F. 2006). Dengan demikian penentuan nilai eigen dan vektor eigen matriks atas aljabar max-plus bilangan kabur melalui Teorema Dekomposisi akan memerlukan hasil-hasil pembahasan nilai eigen dan vektor eigen matriks atas aljabar max-plus interval . Untuk itu dalam makalah ini akan dibahas tentang nilai eigen dan vektor eigen matriks atas aljabar max-plus interval (selanjutnya cukup disebut nilai eigen dan vektor eigen max-plus interval). Sebelum dibahas hasil utama makalah ini pada bagian 4, terlebih dahulu pada bagian 2 dan 3 akan ditinjau beberapa konsep dasar dan hasil-hasil yang mendukung pembahasan. 2. Aljabar Max-Plus, Nilai Eigen dan Vektor Eigen Max-Plus Dalam bagian ini dibahas konsep dasar aljabar max-plus dan kaitannya dengan teori graf, serta eksistensi dan ketunggalan nilai eigen dan vektor eigen max-plus. Pembahasan selengkapnya dapat dilihat pada Baccelli et.al (1992), Rudhito A (2003). Diberikan Rε := R ∪{ε } dengan R adalah himpunan semua bilangan real dan ε : = −∞. Pada R ε didefinisikan operasi berikut: ∀a,b ∈ R ε, a ⊕ b := max(a, b) dan a ⊗ b : = a + b. Dapat ditunjukkan bahwa (Rε, ⊕, ⊗) merupakan semiring komutatif idempoten dengan elemen netral
ε = −∞ dan elemen satuan e = 0. Lebih lanjut (Rε, ⊕, ⊗) merupakan
semifield, yaitu bahwa (Rε, ⊕, ⊗) merupakan semiring komutatif di mana untuk setiap a ∈ R terdapat −a sehingga berlaku a ⊗ (−a) = 0. Kemudian
(Rε, ⊕, ⊗) disebut
dengan aljabar max-plus, yang selanjutnya cukup dituliskan dengan Rmax. 1 - 9
Aljabar max-pus Rmax tidak memuat pembagi nol yaitu ∀ x, y ∈ Rε berlaku: jika x ⊗ y = ε maka x = ε atau y = ε. Relasi “ π m ” yang didefinisikan pada Rmax dengan x π m y ⇔ x ⊕ y = y merupakan urutan parsial pada Rmax. Lebih lanjut relasi ini merupakan urutan total pada Rmax. Dalam Rmax, operasi ⊕ dan ⊗ konsisten terhadap urutan π m , yaitu ∀a, b, c ∈ Rmax , jika a π m b , maka a ⊕ c π m b ⊕ c, dan a ⊗ c π m b ⊗ c. Pangkat k
0
k dari elemen x ∈ R dilambangkan dengan x ⊗ didefinisikan sebagai berikut: x ⊗ := 0 k
dan x ⊗ := x ⊗ x ⊗
k −1
k
0
, dan didefinisikan pula ε ⊗ : = 0 dan ε ⊗ : = ε, untuk k = 1, 2, ... .
Operasi ⊕ dan ⊗ pada Rmax dapat diperluas untuk operasi-operasi matriks dalam m× n : = {A = (Aij)⏐Aij ∈ Rmax, untuk i = 1, 2, ..., m dan j = 1, 2, ..., n}. Untuk α ∈ Rmax, R max
n dan A, B ∈ R m× max didefinisikan α ⊗ A, dengan (α ⊗ A)ij = α ⊗ Aij dan A ⊕ B, dengan (A m× p p× n ⊕ B)ij = Aij ⊕ Bij untuk i = 1, 2, ..., m dan j = 1, 2, ..., n. Untuk A ∈ R max , B ∈ R max B
didefinisikan A ⊗ B, dengan (A ⊗ B)ij =
p
Aik ⊗ Bkj . ⊕ k =1
⎧0 , jika i = j m× n (E )ij := ⎨ dan matriks ε ∈ R max , ⎩ ε , jika i ≠ j
n Didefinisikan matriks E ∈ R n× max ,
(ε )ij := ε untuk setiap i dan j . Dapat
n ditunjukkan bahwa ( R n× max , ⊕, ⊗) merupakan semiring idempoten dengan elemen netral
matriks
n ε dan elemen satuan matriks E. Sedangkan R m× max merupakan semimodul atas
Rmax. Pangkat k dari matriks A ∈ R nxn max dalam aljabar max-plus didefinisikan dengan: k
0
A⊗ = En dan A⊗ = A ⊗ A⊗ m× n pada R max dengan
Perhatikan bahwa
A A
k −1
untuk k = 1, 2, ... . Relasi “ π m ” yang didefinisikan
m× n π m B ⇔ A ⊕ B = B merupakan urutan parsial pada R max .
π m B ⇔ A ⊕ B = B ⇔ Aij ⊕ Bij = Bij ⇔ Aij π m Bij untuk B
B
B
n setiap i dan j. Dalam ( R m× max , ⊕, ⊗), operasi ⊕ dan ⊗ konsisten terhadap urutan n yaitu ∀A, B, C ∈ R n× max , jika A
πm ,
π m B , maka A ⊕ C π m B ⊕ C, dan A ⊗ C π m B ⊗ C .
Didefinisikan R nmax := { x = [ x1, x2, ... , xn]T | xi ∈ R
max,
i = 1, 2, ... , n}.
×1 Perhatikan bahwa R nmax dapat dipandang sebagai R nmax , sehingga R nmax merupakan
semimodul atas Rmax. Unsur-unsur dalam R nmax disebur vektor atas Rmax.
Semnas Matematika dan Pendidikan Matematika 2008
1 - 10
Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Max-Plus Interval
Suatu graf berarah G didefinisikan sebagai suatu pasangan G = (V, A) dengan V adalah suatu himpunan berhingga tak kosong yang anggotanya disebut titik dan A adalah suatu himpunan pasangan terurut titik-titik. Anggota A disebut busur. Suatu lintasan dalam graf berarah G adalah suatu barisan berhingga busur (i1, i2), (i2, i3), ... , (il−1, il) dengan (ik, ik+1) ∈ A untuk suatu l ∈ N (= himpunan semua bilangan asli), dan k = 1, 2, ... , l − 1. Suatu lintasan disebut sirkuit jika titik awal dan titik akhirnya sama. Sirkuit elementer adalah sirkuit yang titik-titiknya muncul tidak lebih dari sekali, kecuali titik awal yang muncul tepat dua kali. Suatu graf berarah G = (V, A) dengan V = {1, 2, , ... , n} dikatakan terhubung kuat jika untuk setiap i, j ∈ V , i ≠ j , terdapat suatu lintasan dari i ke j. Diberikan graf berarah G = (V, A) dengan V = {1, 2, ... , p}. Graf berarah G dikatakan berbobot jika setiap busur (j, i) ∈ A dikawankan dengan suatu bilangan real Aij. Bilangan real Aij disebut bobot busur (j, i), dilambangkan dengan w(j, i). Graf n preseden dari matriks A ∈ R n× max adalah graf berarah berbobot G(A) = (V, A) dengan V
= {1, 2, ... , n}, A = {(j, i)|w(i, j) = Aij ≠ ε }. Bobot suatu lintasan didefinisikan sebagai jumlahan bobot busur-busur yang menyusun tersebut . Suatu rumus bobot rata-rata maksimum sirkuit elementer dalam G(A), dilambangkan dengan λmax(A)), n
λmax(A) =
⊕ ( 1 ⊕(A k =1
n
k
i =1
⊗k
adalah
)ii ).
n Suatu matriks A ∈ R n× max dikatakan semi-definit jika semua sirkuit dalam G(A)
mempunyai bobot takpositif dan
dikatakan definit jika semua sirkuit dalam G(A)
n mempunyai bobot negatif. Diberikan A ∈ R n× max . Dapat ditunjukkan bahwa jika A semi-
definit, maka ∀p ≥ n, A⊗
p
π m E ⊕ A ⊕ ... ⊕ A⊗ n −1 . Diberikan matriks semi-definit n
* ⊗ n A ∈ R n× ⊕ A⊗ max . Didefinisikan A : = E ⊕ A ⊕ ... ⊕ A
n +1
⊕ ... . Suatu matriks A ∈
n R n× max dikatakan irredusibel jika graf presedennya terhubung kuat. Dapat ditunjukkan
2
⊗ n bahwa matriks A ∈ R n× ⊕ ... ⊕ A⊗ max irredusibel jika dan hanya jika (A ⊕ A
n −1
)ij ≠ ε ,
untuk setiap i, j dengan i ≠ j. n Diberikan A ∈ R n× max . Skalar λ ∈ Rmax disebut nilai eigen max-plus matriks A
jika terdapat suatu vektor v ∈ R nmax dengan v ≠ εn×1 sehingga A ⊗ v = λ ⊗ v. Vektor v 1 - 11
tersebut
disebut
vektor eigen
max-plus matriks A yang bersesuaian dengan λ.
n Diberikan A ∈ R n× max . Dapat ditunjukkan bahwa skalar λmax(A), yaitu bobot rata-rata
maksimum sirkuit elementer dalam G(A), merupakan suatu nilai eigen max-plus matriks A. Lebih lanjut untuk B = −λmax(A) ⊗ A, jika Bii+ = 0, maka kolom ke-i matriks B* merupakan vektor eigen yang bersesuaian dengan nilai eigen λmax(A). Kolom-kolom kei matriks B* di atas, yang merupakan vektor eigen yang bersesuaian dengan nilai eigen
λmax(A), disebut vektor-vektor eigen fundamental yang bersesuaian dengan nilai eigen λmax(A). Dapat ditunjukkan bahwa kombinasi linear max-plus vektor-vektor eigen fundamental matriks A juga merupakan vektor eigen yang berseuaian dengan λmax(A). Jika skalar λ ∈ Rmax, merupakan nilai eigen max-plus matriks A, maka λ merupakan bobot rata-rata suatu sirkuit dalam G(A), sehingga λmax(A) merupakan nilai eigen maxn plus maksimum matriks A. Dapat ditunjukkan bahwa jika matriks irredusibel A ∈ R n× max
mempunyai nilai eigen max-plus λ dengan x sebagai vektor eigen max-plus yang bersesuaian dengan λ, maka xi ≠ ε untuk setiap i ∈ {1, 2, ..., n}. Dapat ditunjukkan n bahwa jika matriks A ∈ R n× max irredusibel, maka A mempunyai nilai eigen max-plus
tunggal, yaitu λmax(A). 3. Aljabar Max-Plus Interval dan Matriks atas Aljabar Max-Plus Interval Bagian ini membahas konsep dasar dan teknik pengoperasian matriks atas aljabar max-plus interval. Pembahasan lebih lengkap dapat dilihat pada Rudhito, A. dkk (2008a, 2008b). Interval (tertutup) x dalam Rmax adalah suatu himpunan bagian dari Rmax yang berbentuk
x = [ x , x ] = {x ∈ Rmax | x π m x π m x }. Interval x dalam Rmax di atas
disebut interval max-plus, yang selanjutnya akan cukup disebut interval. Suatu bilangan x ∈ Rmax dapat dinyatakan sebagai interval [x, x ]. Didefinisikan I(R)ε := { x = [ x , x ] |
x , x ∈ R , ε π m x π m x } ∪ { ε }, dengan ε := [ε, ε ]. Pada I(R)ε didefinisikan operasi ⊕ dan ⊗ dengan: x ⊕ y = [ x ⊕ y , x ⊕ y ] dan x ⊗ y = [ x ⊗ y , x ⊗ y ] , ∀ x, y ∈ I(Rε). Dapat ditunjukkan bahwa (I(R)ε, ⊕ , ⊗ )
merupakan semiring idempoten komutatif dengan elemen netral ε = [ε, ε] dan elemen
Semnas Matematika dan Pendidikan Matematika 2008
1 - 12
Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Max-Plus Interval
satuan 0 = [0, 0]. Semiring idempoten komutatif (I(R)ε , ⊕ , ⊗ ) selanjutnya disebut dengan aljabar max-plus interval yang dilambangkan dengan I(R)max. Didefinisikan I(R) mmax×n := {A = (Aij)⏐Aij ∈ I(Rmax), untuk i = 1, 2, ..., m dan j = 1, 2, ..., n}. Matriks anggota I(R) mmax× n disebut matriks interval max-plus. Selanjutnya matriks interval max-plus cukup disebut dengan matriks interval. Untuk α ∈ I(R)max, ×n A, B ∈ I(R) mmax , didefinisikan α ⊗ A, dengan (α ⊗ A)ij = α ⊗ Aij dan A ⊕ B, dengan p (A ⊕ B)ij = Aij ⊕ Bij untuk i = 1, 2, ..., m dan j = 1, 2, ..., n . Untuk A ∈ I(R) m× max , B p ×n ∈ I(R) max , didefinisikan A ⊗ B dengan (A ⊗ B)ij =
p
⊕A
ik
⊗ Bkj untuk i = 1, 2, ...,
k =1
n ×n m dan j = 1, 2, ..., n. (I(R) max , ⊕ , ⊗ ) merupakan semiring idempoten dengan
elemen netral matriks ε dengan (ε )ij := ε untuk setiap i , j dan elemen satuan adalah ⎧0 , jika i = j matriks E, dengan (E )ij : = ⎨ . Sedangkan I(R) mmax× n merupakan semimodul ε , jika i ≠ j ⎩ atas I(R)max, Untuk A ∈ I(R) mmax× n didefinisikan matriks A = ( A ij) ∈ R mmax× n dan A = ( A ij) ∈ m ×n yang berturut-turut disebut matriks batas bawah dan matriks batas atas dari R max
m× n matriks interval A. Diberikan matriks interval A ∈ I(R) max , dengan A dan A berturut-
turut adalah matriks batas bawah dan matriks batas atasnya. Didefinisikan interval m× n matriks dari A, yaitu [ A , A ] = { A ∈ R max ⎜A
πm A πm
m× n * A } dan I( R max ) = {
m× n * n [ A , A ] | A ∈ I(R) m× max }. Untuk α ∈ I(R)max, [ A , A ], [ B , B ]∈ I( R max ) , didefinisikan
α ⊗ [ A , A ] = [ α ⊗ A , α ⊗ A ] dan [ A , A ] ⊕ [ B , B ] = [ A ⊕ B , A ⊕ B ]. Untuk p * p× n * [ A , A ]∈ I( R m× max ) , [ B , B ] ∈ I( R max ) , didefinisikan [ A , A ] ⊗ [ B , B ]= [ A ⊗ B , A ⊗ xn * B ]. (I( R nmax ) , ⊕ , ⊗ ) merupakan semiring idempoten dengan elemen netral adalah
interval matriks [ε, ε] dan elemen satuan adalah interval matriks [E, E]. Sedangkan m× n * I( R max ) merupakan semimodul atas I(R)max.
n ×n xn * Semiring (I(R) max , ⊕ , ⊗ ) isomorfis dengan semiring (I( R nmax ) , ⊕ , ⊗ ), n ×n n ×n xn * dengan pemetaan f : I(R) max → I( R nmax ) , f (A) = [ A , A ], ∀A ∈ I(R) max . Sedangkan
1 - 13
×n m× n * semimodul I(R) mmax atas I(R)max isomorfis dengan semimodul I( R max ) atas I(R)max
Dengan demikan untuk setiap matriks interval A selalu dapat ditentukan interval xn * matriks [ A , A ] dan sebaliknya untuk setiap interval matriks [ A , A ] ∈ I( R nmax ) , maka
n ×n xn A , A ∈ R nmax , sehingga dapat ditentukan matriks interval A ∈ I(R) max , di mana [ A ij , ×n A ij ] ∈ I(R)max , ∀i dan j. Dengan demikian matriks interval A ∈ I(R) mmax dapat m× n * dipandang sebagai interval matriks [ A , A ] ∈ I( R max ) . Interval matriks [ A , A ] ∈ xn * I( R nmax ) disebut interval matriks yang bersesuaian dengan matriks interval A ∈
n ×n I(R) max dan dilambangkan dengan A ≈ [ A , A ]. Akibat isomorfisma di atas, maka
berlaku α ⊗ A ≈ [ α ⊗ A , α ⊗ A ], A ⊕ B ≈ [ A ⊕ B , A ⊕ B ] dan A ⊗ B ≈ [A ⊗ B, A ⊗ B] . Didefinisikan I(R) nmax := {x = [x1, x2, ... , xn ]T| xi ∈ I(R)max, i = 1, 2, ... , n }. Himpunan I(R)
n max
dapat dipandang sebagai I(R)
n ×1 max
. Unsur-unsur dalam I(R)
n max
disebut vektor interval atas I(R)max. Vektor interval x bersesuaian dengan interval vektor [ x , x ], yaitu x ≈ [ x , x ]. 4. Nilai Eigen dan Vektor Eigen Max-Plus Interval Definisi 4.1 n×n Diberikan A ∈ I(R) max . Skalar interval λ ∈ I(R)max disebut nilai eigen max-plus
interval matriks interval A jika terdapat suatu vektor interval v ∈ I(R) nmax dengan v ≠ εn×1 sehingga A ⊗ v = λ ⊗ v. Vektor v tersebut 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. Teorema 4.1 ×n Diberikan A ∈ I(R) nmax , dengan A ≈ [ A , A ]. Skalar interval λmax(A) = [λmax( A ),
λmax( A )], merupakan suatu nilai eigen max-plus interval matriks interval A. Vektor
Semnas Matematika dan Pendidikan Matematika 2008
1 - 14
Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Max-Plus Interval
interval v ≈ [ v , v ], di mana v dan v berturut-turut adalah vektor eigen max-plus yang bersesuaian dengan nilai eigen λmax( A ) dan λmax( A ), sedemikan hingga v π Im v , merupakan vektor eigen max-plus interval matriks A yang bersesuaian dengan λmax(A). Bukti: A ∈ [ A , A ], berlaku A
Untuk setiap matriks
π m Aij π m A . Karena sifat
kekonsistenan operasi ⊕ dan ⊗ pada matriks terhadap urutan “ π m ”, maka berlaku n
A
⊗k
πm A
⊗k
n
1 πm ⊕ ( k =1 k
πm A
⊗k
, untuk k = 1, 2, ... , sehingga berlaku n
n
⊕(A i =1
⊗k
)ii ) π m
⊕ ( 1 ⊕ (A k =1
n
k
i =1
⊗k
⊕ ( 1 ⊕ (A k k =1
n
i =1
⊗k
) ii )
) ii ), atau λmax( A ) π m λmax(A) π m λmax( A ).
Jadi [λmax( A ), λmax( A )] adalah suatu interval. Ambil λmax(A) = [λmax( A ), λmax( A )]. Menurut hasil pada bagian 2 di atas, untuk B = +
−λmax( A ) ⊗ A , jika Bii = 0, maka kolom ke-i matriks B merupakan vektor eigen yang *
bersesuaian dengan nilai eigen λmax( A ), demikian juga analog untuk B . Ambil v dan v , di mana berturut-turut adalah vektor eigen yang bersesuaian dengan nilai eigen
λmax( A ) dan λmax( A ), sedemikan hingga v π m v , jika diperlukan dapat dibentuk kombinasi linear vektor-vektor eigen fundamental yang terkait, sehingga diperoleh v
π m v . Ambil vektor interval v ≈ [ v , v ], maka [ A , A ] ⊗ [ v , v ] = [λmax( A ),
λmax( A )] ⊗ [ v , v ], yang berarti juga bahwa A ⊗ v = λ ⊗ v. Jadi skalar interval λmax(A) = [λmax( A ), λmax( A )], merupakan suatu nilai eigen max-plus interval matriks interval A.
■
Berikut diberikan suatu teorema yang memberikan ketunggalan nilai eigen interval max-plus suatu matriks interval. Sebelumnya akan diberikan definisi dan syarat cukup dan perlu irredusibilitas suatu matriks interval. Definisi 4.2 ×n Suatu matriks interval A ∈ I(R) nmax , dengan A ≈ [ A , A ], dikatakan irredusibel jika
setiap matriks A ∈ [ A , A ] irredusibel.
1 - 15
Teorema berikut memberikan syarat perlu dan cukup suatu matriks interval irredusibel. Teorema 4.2 ×n Suatu matriks interval A ∈ I(R) nmax , dengan A ≈ [ A , A ], irredusibel jika dan hanya n jika A ∈ R n× max irredusibel.
Bukti: (⇒): Jelas berlaku menurut Definisi 4.2 di atas. (⇐): Untuk setiap matriks A ∈ [ A , A ], berlaku A
π m A π m A . Karena sifat
kekonsistenan operasi ⊕ dan ⊗ pada matriks terhadap urutan “ π m ”, maka berlaku (A⊕A
⊗2
⊕ ... ⊕ A
⊗ n −1
)
π m (A ⊕ A⊗ 2 ⊕ ... ⊕ A⊗ n−1 ) π m ( A ⊕ A ⊗ 2 ⊕ ... ⊕ A ⊗ n−1 ), yang berarti berlaku juga
(A⊕A
⊗2
⊕ ... ⊕ A
⊗ n −1
)ij
π m (A ⊕ A⊗ 2 ⊕ ... ⊕ A⊗ n−1 )ij π m ( A ⊕ A ⊗ 2 ⊕ ... ⊕ A ⊗ n−1 )ij
untuk setiap i dan j. Karena A irredusibel, maka menurut hasil pada bagian 2 di atas, (A⊕A
⊗2
⊕ ... ⊕ A
⊗ n −1
)ij ≠ ε untuk setiap i, j dengan i ≠ j . Dengan demikan untuk 2
setiap matriks A ∈ [ A , A ] juga berlaku bahwa (A ⊕ A⊗ ⊕ ... ⊕ A⊗
n −1
)ij ≠ ε untuk
setiap i, j dengan i ≠ j, sehingga menurut menurut hasil pada bagian 2 di atas A irredusibel. Jadi terbukti bahwa matriks interval A ∈ I(R) mmax× n irredusibel. ■ Akibat 4.3 ×n Diberikan A ∈ I(R) nmax , dengan A ≈ [ A , A ]. Jika matriks interval A irredusibel, maka
λmax(A) = [λmax( A ), λmax( A )] merupakan nilai eigen interval max-plus tunggal matriks interval A. Bukti:
Semnas Matematika dan Pendidikan Matematika 2008
1 - 16
Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Max-Plus Interval
Jika matriks interval A iredusibel, maka ∀A ∈ [ A , A ] irredusibel, sehingga menurut hasil pada bagian 2, λmax(A) merupakan nilai eigen max-plus tunggal matriks A. Dengan cara yang analog dengan pembuktian Teorema 4.1 di atas dapat disimpulkan bahwa
λmax(A) = [λmax( A ), λmax( A )], merupakan nilai eigen max-plus interval tunggal matriks interval A. ■ Contoh 4.1 Akan ditentukan nilai eigen dan vektor eigen max-plus interval dari matriks
⎡[−2, − 1] [3, 4] [1, 2] ⎤ ⎡− 2 3 1 ⎤ ⎥ ⎢ [1,1] [ε , ε ] ⎥ . Perhatikan bahwa A = ⎢⎢ 1 1 ε ⎥⎥ dan A = A= ⎢ [1, 2] ⎢⎣ [ε , ε ] [2, 4] [−1,1]⎥⎦ ⎢⎣ ε 2 − 1⎥⎦
⎡− 1 4 2⎤ ⎢ 2 1 ε ⎥ . Untuk A diperoleh bahwa λ ( A ) = 2 dengan vektor-vektor eigen max ⎥ ⎢ ⎢⎣ ε 4 1 ⎥⎦ fundamentalnya adalah [0, −1, −1]T dan [1, 0, 0]T . Untuk A diperoleh bahwa λmax( A ) = 3 dengan vektor-vektor eigen fundamentalnya adalah [0, 1, 0]T dan
[1, 0, 1]T .
Vektor interval v = [[0, 0], [ −1,1], [ −1,0]]T , merupakan vektor eigen interval maxplus matriks interval A yang bersesuaian dengan λmax(A) = [2, 3]T. Perhatikan bahwa A irredusibel sehingga vektor eigen interval max-plus yang diperoleh adalah tunggal. 5. Kesimpulan
Dapat disimpilkan bahwa setiap matriks interval persegi, yaitu matriks persegi dengan unsur-unsurnya berupa interval, mempunyai nilai eigen interval max-plus, yaitu nilai eigen interval max-plus maksimum, dan vektor eigen interval max-plus. Batas bawah dan batas atas nilai eigen interval max-plus maksimum tersebut berturut-turut adalah nilai eigen max-plus matriks batas bawah dan nilai eigen max-plus matriks batas atas dari matriks intervalnya. Jika matriks tersebut irredusibel maka nilai eigen interval tersebut tunggal. Kepustakaan
Bacelli, F., et al. 2001. Synchronization and Linearity. New York: John Wiley & Sons.
1 - 17
Chanas, S., Zielinski, P. 2001. Critical path analysis in the network with fuzzy activity times. Fuzzy Sets and Systems. 122 (2001) 195–204. Lüthi, J., Haring, G. 1997. Fuzzy Queueing Network Models of Computing Systems. Proceedings of the 13th UK Performance Engineering Workshop, Ilkley, UK,
Edinburgh University Press, July 1997. Rudhito, Andy. 2003. Sistem Linear Max-Plus Waktu-Invariant. Tesis: Program Pascasarjana Universitas Gadjah Mada. Yogyakarta. Rudhito, Andy, dkk. 2008a. “Aljabar Max-Plus Interval”. Prosiding Seminar Nasional Matematika S3 UGM. Yogyakarta. 31 Mei 2008. Rudhito, Andy, dkk. 2008b. “Matriks atas Aljabar Max-Plus Interval”. Prosiding Seminar Nasional Matematika S3 UGM. Yogyakarta. 31 Mei 2008. Susilo, F. 2006. Himpunan dan Logika Kabur serta Aplikasinya edisi kedua. Graha Ilmu, Yogyakarta.
Semnas Matematika dan Pendidikan Matematika 2008
1 - 18