ALGORITMA MENENTUKAN HIMPUNAN TERBESAR DARI SUATU MATRIKS INTERVAL DALAM ALJABAR MAX-PLUS Ratna Novitasari Program Studi Matematika FMIPA UNDIP Jl.Prof.Soedarto, S.H Semarang 50275 Abstract. This research discussed about how to obtained largest set from an interval matrix if given a possible eigen vector. For obtained the largest set, we would doing some iteration and then determined the best algorithm. Keywords: Eigen Vectors, Interval Matrix, Largest set, Maxplus Algebra
1. PENDAHULUAN Pada beberapa permasalahan, matriks digunakan untuk memodelkan suatu sistem dan sistem tersebut diselesaikan sehingga didapatkan solusinya. Untuk mendapatkan penyelesaian analitis dari sistem ini adakalanya menemui kesulitan dan lebih mudah menggunakan komputasi. Tetapi nilai komputasi dari matriks tersebut tidak tepat seperti keadaan yang sebenarnya. Hal ini menyebabkan adanya interval nilai dari sebuah matriks dalam komputasi dibandingkan dengan matriks dengan nilai sesuai keadaan yang sebenarnya. Sebuah matriks yang mempunyai interval data seperti ini dinamakan matriks interval. Pentingnya masalah matriks interval ini telah diketahui dan dipelajari dalam Aljabar biasa dan dicari penyelesaiannya [2]. Aljabar Max-Plus pertama kali dikenalkan oleh [1] dan terus dikembangkan hingga saat ini. Aljabar max-plus sering digunakan untuk memodelkan suatu permasalahan seperti transportasi, manufakturing, penjadwalan, sistem antrian, lalu lintas dan lain sebagainya [3]. Seperti halnya pada aljabar biasa, untuk menyelesaikan model tersebut muncul permasalahan adanya interval nilai yang menyebabkan adanya matriks interval. Karena itu, diperlukan analisis mengenai matriks interval untuk mendapatkan penyelesaiannya. Pada penelitian sebelumnya [4] telah dibahas mengenai
132
generator-generator dari possible eigenvector. Beberapa possible eigenvector inilah yang akan digunakan untuk mendapatkan himpunan terbesar dari matriks interval dalam Aljabar Max-Plus. Untuk memudahkan perhitungan, digunakan toolbox Aljabar Max-Plus dengan program Scilab–4.1.2. 2. MATRIKS INTERVAL DALAM ALJABAR MAX-PLUS Untuk setiap a, b ∈ Rmaks, didefinisikan operasi ⊕ dan ⊗ adalah def
def
a ⊕ b = maks( a, b ) dan a ⊗ b = a + b . Sehingga
untuk setiap a ∈ Rmaks dan ε , didapatkan a ⊕ ε = ε ⊕ a = a dan a ⊗ε = ε ⊗ a = ε . Himpunan Rmaks dengan operasi ⊕ dan ⊗ disebut Aljabar Max-Plus dan dinyatakan R = (Rmaks, ⊕ , ⊗ , ε , e). Matriks interval adalah himpunan semua matriks yang mempunyai interval nilai dan ditulis dalam bentuk A = A, A , n× n dimana A, A ∈ R mak s dan A≤ A . Matriks interval seperti dalam matriks biasa juga mempunyai eigenvalue dan eigenvector. Matriks A* merupakan matriks yang terletak diantara matriks interval bawah dan matriks interval atas. Jika memenuhi persamaan A ⊗ x ≤ A * ⊗ x ≤ A ⊗ x maka x disebut dengan possible eigenvector. Diberikan definisi mengenai eigenvalue pada matriks interval adalah sebagai berikut: Definisi 2.1 [2] Suatu bilangan riil λ adalah sebuah possible eigenvalue dari sebuah matriks interval A jika λ
Jurnal Matematika Vol. 14, No. 3, Desember 2011 :132 - 136
merupakan eigenvalue dari minimal satu matriks A ∈ A. Suatu bilangan riil λ adalah sebuah universal eigenvalue dari sebuah matriks interval A jika λ merupakan eigenvalue dari tiap matriks A ∈ A. Sedangkan pengertian eigenvector pada matriks interval didefinisikan sebagai berikut: Definisi 2.2 [2] Suatu vektor x ∈ R nmak s adalah sebuah possible eigenvector dari sebuah matriks interval A jika ada A ∈ A sehingga A ⊗ x = λ ( A) ⊗ x . Suatu vektor n x ∈ R mak s adalah sebuah universal eigenvector dari sebuah matriks interval A jika A ⊗ x = λ ( A) ⊗ x untuk setiap matriks A ∈ A. Contoh 2.3 Diberikan matriks interval 2, 4 6,9 3,8 4, 6 A= 3,5 −∞ . − ∞,5 2,8 3,7 Dengan menggunakan algoritma maxalgol, matriks A mempunyai eigenvalue λ ( A) = 4 dan matriks A mempunyai eigenvalue λ ( A )= 8 . Karena λ ( A ) ≠ λ ( A ) , berarti matriks interval A tidak mempunyai universal eigenvalue hanya mempunyai possible eigenvalue yaitu 4 ≤ λ ≤ 8 . 1 Jika di ambil suatu vektor x = 2 , 3 9 maka diperoleh A ⊗ x = 5 dengan nilai 6 Selanjutnya λ = maks ( A ⊗ x − x ) i = 8 . i
9 didapatkan nilai dari A * ⊗ x = λ ⊗ x = 10 11 12 dan A ⊗ x = 7 . Terlihat bahwa pada 10 baris kedua dan ketiga, nilai A* ⊗ x > A ⊗ x padahal seharusnya A ⊗ x ≤ A * ⊗ x ≤ A ⊗ x .
1 Jadi, x = 2 bukan merupakan possible 3 eigenvector untuk matriks interval A. 2 Jika di ambil suatu vektor x = 2 , 0 6 maka dengan nilai A⊗x = 6 4 Selanjutnya λ = maks ( A ⊗ x − x ) i = 4 . i
6 didapatkan nilai dari A ⊗ x = λ ⊗ x = 6 4 10 dan A ⊗ x = 8 . Terlihat bahwa pada 10 setiap baris memenuhi A ⊗ x ≤ A * ⊗ x ≤ A ⊗ x . Adapun nilai dari A* diberikan oleh * a ij = min{a ij , λ ( x ) + x i − x j }. *
4 4 6 sehingga didapatkan A = 4 4 − ∞ . 2 2 4 Karena A ≤ A * ≤ A dan A* ⊗ x = 4 ⊗ x , maka *
2 x = 2 adalah possible eigenvector untuk 0 matriks interval A dengan λ = 4 . Contoh 2.4 Diberikan matriks interval A ={A( c ); c∈ − 4, −3 } , dimana
−∞ c −∞ A(c ) = − ∞ − ∞ 1 . Dengan − ∞ −1 − ∞ menggunakan algoritma maxalgol, didapatkan eigenvalue dari A(c ) dan A(c ) adalah sama dengan nol. Jadi, matriks A mempunyai universal eigenvalue λ ( A(c )) = 0 untuk semua c∈ − 4, −3 . Dan
c eigenvector dari A(c) adalah 0 . Dimana −1 133
Ratna Novitasari (Algoritma Menentukan Himpunan Terbesar dari suatu Matriks Interval dalam Aljabar …)
−4 eigenvector dari matriks A(c ) adalah 0 −1 sedangkan eigenvector dari matriks A(c ) −3 adalah 0 . Jadi, matriks interval A(c) −1 tidak mempunyai universal eigenvector. Diberikan matriks interval B ={B( c ); c∈ − 4, −3 } , dimana 0 −∞ c A(c ) = − ∞ − ∞ 1 − ∞ −1 − ∞
dengan
matriks
−∞ − 4 0 interval bawah A(c ) = − ∞ − ∞ 1 dan − ∞ −1 − ∞ −∞ −3 0 matriks interval atas A(c ) = − ∞ − ∞ 1 . − ∞ −1 − ∞ Didapatkan eigenvalue dari B (c ) dan B (c ) adalah sama dengan nol. Jadi, matriks B mempunyai universal eigenvalue c∈ − 4, −3 . untuk semua λ ( B (c )) = 0 Sedangkan eigenvector dari B(c) adalah −1 0 . Dimana eigenvector dari matriks −1 A( c ) dan eigenvector dari matriks A( c )
−1 adalah 0 . Jadi, matriks interval B(c) −1 mempunyai universal eigenvector. Untuk proses perhitungan besarnya nilai eigenvalue dan eigenvector digunakan Algoritma Power [5] dalam bentuk program Scilab 4.1.2 [6]. 3. ALGORITMA MENENTUKAN HIMPUNAN TERBESAR DARI MATRIKS INTERVAL Untuk mendapatkan himpunan terbesar di suatu matriks interval apabila diberikan suatu possible eigenvector akan dilakukan dengan cara iterasi. Matriks A* pasti terletak di antara matriks A dan A . 134
Kemudian matriks A digantikan oleh matriks A* dan seterusnya hingga nilai dari matriks A semakin naik hingga mencapai nilai terbesarnya dan berhenti. Matriks ∗ merupakan matriks yang terletak antara matriks interval bawah dan matriks interval atas pada iterasi ke-n. Contoh 3.1 Matriks interval diberikan pada Contoh 2.3. Dari keempat macam A* yang telah didapatkan, diambil A* dengan nilai terbesar, yaitu jika diberikan vektor yang merupakan eigenvector dari c, yaitu 6 4 8 * A = 4 5 − ∞ . Dengan menggunakan 4 6 6 algoritma maxalgol, didapatkan matriks A* 2 mempunyai λ = 6 dan v = 0 . Kemudian 0 di ambil A* sebagai A1 , sehingga matriks interval berubah menjadi 4 8,9 6,8 4, 6 5 − ∞ . Jika diberikan x 4,5 6,8 6,7 2 adalah eigenvector dari A1 yaitu x = 0 , 0 6 4 8 maka didapatkan A12* = 4 5 − ∞ yang 4 6 6 sama dengan A* = A1 . Jika diberikan x
2 adalah eigenvector dari A yaitu x = 0 , 0 6 4 8 maka didapatkan A22* = 4 5 − ∞ . Jika 4 6 6 diberikan x adalah nilai maksimum dari 8.5 rata-rata matriks interval, yaitu x = 5 , 7 maka didapatkan bahwa x bukan merupakan possible eigenvector. Jadi, himpunan terbesar dari matriks interval A jika diberikan keempat macam
Jurnal Matematika Vol. 14, No. 3, Desember 2011 :132 - 136
possible eigenvector kemudian di ambil nilai A* yang terbesar dan dilakukan secara 6 4 8 iterasi adalah 4 5 − ∞ . 4 6 6 Adapun algoritma untuk menentukan himpunan terbesar dalam suatu matriks interval adalah Input : matriks interval A = A, A dan vektor x Output : himpunan terbesar dari matriks interval A A*=maks { A × x, A × x, Amaks× x} While A* maksimum (A* ≤ A ) A = A* A*= A × x end Berikut ini diberikan contoh untuk matriks interval dengan ukuran 2 × 2. Contoh 3.2 Diberikan matriks interval seperti pada Contoh 3.1 dan akan di tentukan himpunan terbesarnya. Matriks 1,3 2,5 . Jika di ambil interval A = 3 , 4 4 possible eigenvector yang memberikan nilai A# yang maksimum, yaitu eigenvector 5 dari matriks A yaitu x = , maka 4.5 3 4.5 didapatkan yang A # = 3.5 4 4.5 mempunyai λ = 4 dan v = . 4 Kemudian A# di ambil sebagai A , sehingga matriks interval menjadi 3 4.5,5 . A 1 = 3 . 5 , 4 4 1
1
Jika diberikan eigenvector dari A , yaitu 4.5 maka didapatkan x = 4 3 4.5 A11# = 3.5 4
Jika diberikan eigenvector dari A yaitu 5 maka didapatkan x = 4.5 • 3 4 . 5 . A21# = 3.5 4 1
Jika di ambil rata-rata eigenvector dari A 4.75 maka didapatkan dan A yaitu x = 4 . 25 3 4 . 5 . A31# = 3 . 5 4 Jika di ambil maksimum dari rata-rata 4.75 maka matriks interval, yaitu x = 4 3 5 . didapatkan Possible A41# = 3.5 4 eigenvector ini juga merupakan possible eigenvector pada matriks interval A. 3 5 di ambil sebagai Kemudian A41# = 3.5 4 2
A , sehingga matriks interval menjadi 5 3 . A 2 = 3.5,4 4 2 Jika diberikan eigenvector dari A , yaitu 9.25 maka didapatkan x = 8.5 3 5 . A12# = 3.5 4 Jika diberikan eigenvector dari A yaitu 5 maka didapatkan x = 4.5
3 5 . A22# = 4 4 Jika di ambil rata-rata eigenvector yaitu 7.125 ternyata tidak memberikan x = 6.5 nilai A#. Jika di ambil maksimum dari rata-rata 2.5 matriks interval, yaitu x = ternyata 2 # tidak memberikan nilai A . 135
Ratna Novitasari (Algoritma Menentukan Himpunan Terbesar dari suatu Matriks Interval dalam Aljabar …)
Jadi, didapatkan himpunan maksimum jika diberikan suatu possible eigenvector 3 5 yang sama dengan adalah A22# = 4 4 besarnya matriks interval atas. 4.
KESIMPULAN Himpunan terbesar suatu matriks interval A apabila diberikan suatu possible eigenvector didapatkan dengan cara iterasi. Matriks A* pasti terletak di antara matriks A dan A . Kemudian matriks A digantikan oleh matriks A* dan seterusnya hingga nilai dari matriks A semakin naik hingga mencapai nilai terbesarnya dan berhenti. 5. DAFTAR PUSTAKA [1] Baccelli, F., Cohen, G., Olsder, G.J. dan Quadrat, J.P., (1992), Synchronization and Linearity An Algebra for Discrete Event Systems, John Wiley & Sons, New York.
136
[2]
Cechlarova, K., (2005), Eigenvectors of Interval Matrices over Max-Plus Algebra, Journal of Discrete Applied Mathematics, vol. 150, hal. 2– 15. • [3] Heidergott, B., Olsder, G.J. dan Woude, J. van der, (2006), Max Plus at Work, Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications, Princeton University Press, New Jersey. [4] Novitasari, R., Subiono, (2009), Analisis Masalah Generator dari Possible dan Universal Eigenvector pada Matriks Interval dalam Aljabar Max Plus, Jurusan Matematika Institut Teknologi Sepuluh Nopember, Surabaya. [5] Subiono, Woude, J. van der, (2000), Power Algorithm for (max, +) and Bipartite (min, max, +) Systems, Journal of Discrete Event Dynamic Systems, vol. 10, hal. 369-389. [6] Subiono, (2007), Max-plus Algebra Toolbox, ver. 1.0, Jurusan Matematika Institut Teknologi Sepuluh Nopember, Surabaya.
