Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
ISSN : 2085-9902
Nilai Eigen dan Vektor Eigen Universal Matriks Interval Atas Aljabar Max-Plus Fitri Aryani1, Tri Novita Sari2 Jurusan Matematika Fakultas Sains dan Teknologi UIN Suska Riau e-mail:
[email protected]
Abstrak Pembahasan mengenai nilai eigen dan vektor eigen pada suatu matriks telah banyak dilakukan. Entri-entri matriks dapat berupa rill, kompleks, fuzzy, dan interval. Penelitian ini membahas mengenai nilai eigen dan vektor eigen pada matriks interval atas aljabar max-plus. Matriks interval mempunyai nilai eigen dan vektor eigen universal. Nilai eigen universal dari matriks interval adalah nilai eigen untuk setiap .Vektor eigen universal dapat dicari dengan menyelesaikan sistem persamaan dua-sisi. Untuk nilai eigen sama dengan 0 dapat menggunakan sistem dua-sisi dengan dan untuk semua . Sedangkan untuk nilai eigen tidak sama dengan nol dapat menggunakan sistem dua-sisi dengan dan untuk semua . Kata kunci: Aljabar max-plus, matriks interval, nilai eigen dan vektor eigen, nilai eigen dan vektor eigen universal.
Abstract Discussion of eigenvalue dan eigenvector of a matrix has much to do. Matrix entries can be the real, complex, fuzzy, and interval. This paper discusses the eigenvelue and eigenvector of interval matrix over max-plus algebra. An interval matriks has universal eigenvalue and eigenvector. Universal eigenvalue of an interval matrix is the eigenvalue of each The universal eigenvector can be found by solving two-sided systems. For the eigenvalue is equal to 0 can use two-sided system with and for all While the eigenvalue not equal to 0 can use two-sided system with and for all .
Keywords: eigenvalue and eigenvector, eigenvalue and universal eigenvector, interval matrix, Max-plus algebra.
1. Pendahuluan Matriks yang elemen-elemen di dalamnya berupa interval tertutup dengan matriks batas bawah dan matriks batas atas sebagai penyusunnya disebut matriks interval. Matriks interval sama dengan matriks biasa yang mempunyai nilai eigen dan vektor eigen. Matriks interval juga mempunyai nilai eigen yang mungkin dan nilai eigen universal serta vektor eigen yang mungkin dan vektor eigen universal. Aljabar max-plus adalah aljabar atas bilangan rill yang dilengkapi dengan operasi maksimum yang dinotasikan dengan dan penjumlahan yang dinotasikan dengan , yangdidefinisikan sebagai berikut: dan . Operasi-operasi yang berlaku dalam aljabar max-plus bersifat assosiatif, komutatif, dan distributif seperti pada aljabar biasa.jika adalah matriks graf berarah berbobot yang terhubung kuat maka mempunyai nilai eigen tunggal yaitu ( ), dengan maksimum dari bobot maksimum semua sirkuit dengan panjang dengan titik sebagai titik awal dan titik akhir dalam atas seluruh titik adalah dan rataratanya adalah .Selanjutnya, untuk jika maka kolom ke-i matriks merupakan vektor eigen yang bersesuaian dengan . Kolom-kolom ke-i
218
Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
ISSN : 2085-9902
matriks , merupakan vektor eigen yang bersesuaian dengan nilai eigen dengan vektor-vektor eigen fundamental yang bersesuaian dengan nilai eigen
dan disebut .
Suatu skalar dinamakan nilai eigen dan vektor dinamakan vektor eigen matriks jika . Penelitian yang diakukan [12], aljabar max-plus digunakan untuk membahas ketunggalan nilai eigen dan vektor eigen matriks atas aljabar maxplus interval. Aljabar max-plus juga digunakanuntuk memodelkan suatu permasalahan tentang sistem linear max-plus interval waktu invariant [10]. Kemudian [13] membahas tentang penerapan aljabar max‐plus interval pada jaringan antrian dengan waktu aktifitas interval. Penelitian selanjutnya [5] membahas tentang aplikasi aljabar max-plus pada pemodelan dan penjadwalan busway yang diintegrasikan dengan kereta api komuter. Aljabar max-plus juga digunakan dalam penyelesaian sistem dua sisi menggunakan iterasi seperti penelitian [9]. Penyelesaian sistem dua sisi dalam aljabar max-plus banyak dibahas oleh peneliti, seperti: ⨂ ⨂ dan ⨂ ⨂ yang diselesaikan [3] dengan menggunakan metode ⨂ ⨂ ⨂ ⨂ alternatif. dengan matriks dibahas pada [1] tentang program linear dengan fungsi kendala. Sistem persamaan linear tersebut diselesaikan dengan menggunakan metode alternating, kemudian dicari solusi optimal dari permasalahan program linear tersebut. Penyelesaian sistem persamaan dua sisi dapat digunakan untuk mencari vektor eigen universal untuk yang telah diselesaikan [8]. Pada penelitian ini akan membahas mengenai nilai eigen dan vektor eigen universal matriks interval atas aljabar max-plus untuk dengan menggunakan sistem persamaan dua sisi. 2. Bahan dan Metode Penelitian Penelitian ini menggunakan metode studi literatur. Berikut diberikan literatur-literatur yang diperlukan untuk menunjang hasil dan pembahasan. 2.1 Matriks Interval atas Aljabar Max-Plus Bagian ini membahas tentang teknik pengoperasian matriks interval atas aljabar maxplus. Pembahasan lebih lengkap dapat diliihat pada [8]. Diberikan matriks dan sedemikian sehingga dengan Matriks interval atas aljabar max-plus berordo didefinisikan dengan [ ] . Definisi operasi maksimum dan penjumlahan matriks interval atas aljabar max-plus sama halnya dengan definisi operasi maksimum dan penjumlahan pada matriks atas aljabar maxplus. Perbedaannya pada matriks interval yaitu, hanya mengikuti definisi operasi maksimum dan penjumlahan pada suatu interval. Berikut definisi operasi tentang matriks interval atas aljabar max-plus: a) Misalkan matriks , penjumlahan matriks , didefinisikan dengan ( b)
Misalkan matriks dan yaitu didefinisikan dengan
c)
Misalkan matriks didefinisikan dengan
) ( ) , pergandaan skalar
dan
dengan matriks
perkalian matriks (
)
(
)
[ { } { }] Penyelesaian Sistem Persamaan Dua-Sisi Penyelesaian sistem persamaan dua-sisi dapat digunakan dalam menentukan vektor eigen universal matriks interval atas aljabar max-plus. Pembahasan selengkapnya dapat di lihat pada [3]. Sistem persamaan linear dua-sisi atas aljabar max plus yang berbentuk dengan , (1) 2.2
219
Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
ISSN : 2085-9902
menotasikan himpunan indeks baris dan himpunan indeks kolom dari matriks dan . Ukuran matriks dan harus sama. Berikut ini akan diberikan lemma yang menyatakan syarat bahwa dua-sisi tidak mempunyai penyelesaian. Lemma 1. Jika ada sebuah baris i sehingga tidakmempunyai penyelesaian.
untuk setiap j, maka sistem dua sisi
Bukti: Akan dibuktikan dengan menggunakan kontradiksi. Anggap bahwa sebuah vektor adalah sebuah penyelesaian dari Persamaan (1). Nilai maksimum pada ruas kiri adalah } dan nilai maksimum pada ruas kanan adalah }. Maka didapatkan . Karena , berarti bahwa bukan merupakan penyelesaian dari Persamaan (1) sebab jika merupakan penyelesaian seharusnya . Dari Lemma 1 di atas, memberikan akibat sebagai berikut: Akibat 1.Untuk setiap Persamaan (1) yang mempunyai penyelesaian, ada untuk setiap barisi suatu indeks j sehingga . Bukti: Misalkan vektor adalah penyelesaian dari Persamaan (1), Sehingga nilai maksimum pada ruas kiri adalah }.Sedangkan nilai maksimum pada ruas kanan adalah }. Maka didapatkan . Hal ini berarti untuk tiap baris i ada l = j , sehingga dan didapatkan . 2.2
Nilai Eigen dan Vektor Eigen yang Mungkin dari Matriks Interval atas Aljabar MaxPlus Diasumsikan bahwa suatu matriks adalah matriks dari graf berarah berbobot yang terhubung kuat dengan semua entri penyusun adalah berhingga, sehingga masing-masing mempunyai nilai eigen tunggal. Pembahasan lebih lengkap dapat dilihat pada [3] dan [8]. Suatu skalar adalah nilai eigen yang mungkin dari suatu matriks interval , jika skalar tersebut adalah nilai eigen dari sedikitnya satu . Berikut diberikan teorema nilai eigen yang mungkin dari suatu matriks interval. Teorema 1. Suatu skalar dan hanya jika
adalah nilai eigen yang mungkin dari suatu matriks interval .
jika
Bukti : Diketahui adalah nilai eigen yang mungkin dari suatu matriks interval . Sehingga, adalah nilai eigen dari sedikitnya satu . Misalkan adalah nilai eigen dari [ ]. suatu matriks Karena adalah matriks graf berarah berbobot yang terhubung kuat, maka (
( [
untuk setiap matriks dan
], berlaku
. Karena sifat kekonsistenan operasi
pada matriks terhadap urutan “ , sehingga berlaku (
(
) )
) )
”, maka berlaku (
(
) )
untuk (
(
) )
atau ( ) hal ini menunjukkan bahwa
( ) . 220
Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
ISSN : 2085-9902
[ ( ) ( )] Akan dibuktikan adalah nilai eigen yang mungkin dari matriks Diketahui interval , yang artinya adalah nilai eigen dari sedikitnya satu . Diambil matriks dari graf berarah berbobot yang terhubung kuat dengan nilai eigen (
(
) )
untuk setiap matriks , mempunyai 1. Nilai eigen matriks batas bawah , yaitu ( )
(
(
) )
(
(
) )
2. Nilai eigen matriks batas bawah , yaitu ( ) [
akan di tunjukan bahwa matriks ( )
]. jika
[ ( ) ( )] berarti bahwa ( )
sehingga berlaku (
(
) )
(
(
untuk , dan untuk setiap matriks [ ], dengan kata lain menunjukan bahwa matriks
) ) [
(
(
) )
], berlaku . Hal ini adalah nilai eigen dari sedikitnya satu
Suatu vektor adalah vektor eigen yang mungkin dari suatu matriks interval , jika terdapat sedemikian sehingga Vektor eigen dapat ditentukan dengan cara meningkatkan matriks batas bawah dalam setiap koordinat sedemikian sehingga tidak melebihi matriks batas atas , tetapi untuk setiap koordinat dari dipastikan nilainya sekurang-kurangnya yang dapat dirumuskan dengan { } dan maka dan mungkin dari matriks interval .
, sehingga
adalah vektor eigen yang
3. Hasil dan Pembahasan 3.1 Nilai Eigen dan Vektor Eigen Universal dari Matriks Interval atas Aljabar Max-Plus Diasumsikan bahwa suatu matriks adalah matriks dari graf berarah berbobot yang terhubung kuat dengan semua entri penyusun adalah berhingga, sehingga masing-masing mempunyai nilai eigen tunggal. Pembahasan selengkapnya dapat dilihat pada [3], [8], dan [12]. Suatu skalar dinamakan nilai eigen universal dari suatu matriks interval , jika skalar tersebut adalah nilai eigen dari setiap . Berikut diberikan teorema tentang matriks interval atas aljabar max-plus. Teorema
2.
Diberikan , dengan . Skalar interval , merupakan suatu nilai eigen max-plus interval matriks interval A. Vektor interval di mana dan berturut-turut adalah vektor eigen max-plus yang bersesuaian dengan nilai eigen dan , sedemikan hingga , merupakan vektor eigen max-plus interval matriks yang bersesuaian dengan .
221
Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
ISSN : 2085-9902
Bukti: Untuk setiap matriks
, berlaku
. Karena sifat kekonsistenan
dan pada matriks terhadap urutan “ , sehingga berlaku
operasi
(
(
) )
(
”, maka berlaku (
) )
untuk (
(
) )
atau ( ) ( ) jadi adalah suatu interval. ( ) Kemudian ambil , selanjutnya untuk , jika , maka kolom ke matriks merupakan vektor eigen yang bersesuaian dengan nilai eigen , demikian juga analog dengan . Ambil dan dimana berturut-turut adalah vektor eigen yang bersesuaian dengan nilai eigen dan , sedemikian sehingga , jika diperlukan dapat dibentuk kombinasi linier vektor-vektor eigen fundamental yang terkait, [ ] sehingga diperoleh . Ambil vektor interval maka [ ] [ ] ( ) ( ) [ ] yang berarti juga bahwa . Jadi, skalar interval , merupakan nilai eigen max plus matriks interval. Selanjutnya, dalam pembahasan vektor eigen universal akan dibahas nilai eigen ( ) ( ) universal untuk ( ) dan ( ) . Vektor eigen universal dibatasi pada kasus nilai eigen universal sama dengan 0. Vektor eigen universal merupakan kombinasi linier atas aljabar max-plus dari himpunan vektor eigen fundamental matriks interval batas bawah maupun matriks interval batas atas . Berikut diberikan teorema vektor eigen universal matriks interval . ( ) Teorema 3. Apabila suatu matriks interval mempunyai ( ) dan { adalah himpunan vektor eigen fundamental dari maka terdapat vektor eigen universal dari jika dan hanya jika sistem dua sisi dengan dan untuk semua mempunyai penyelesaian. Bukti: ( ) Diketahui suatu matriks interval dengan ( ) dan misalkan { adalah vektor eigen fundamental dari Akan dibuktikan sistem dua sisi mempunyai penyelesaian. Misalkan vektor eigen universal dari adalah , maka untuk setiap berlaku Karena vektor eigen universal merupakan kombinasi linier atas aljabar max-plus dari himpunan m vektor eigen fundametal matriks , maka ⨂ sehingga untuk dengan ( ) , berlaku ⨂ ⨂ ⨂ ⨂ ⨂ ⨂ ⨂ ⨂
jadi,
[
] adalah penyelesaian dari
.
( ) Diketahui suatu matriks interval dengan ( ) dan misalkan { adalah himpunan vektor eigen fundamental dari . Akan dibuktikan terdapat adalah suatu vektor eigen universal dari .
,
222
Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
[
Misalkan
ISSN : 2085-9902
] adalah penyelesaian dari sistem persamaan dua sisi
sehingga ⨂
⨂ ⨂ ⨂
⨂ Terlihat bahwa dengan ( ) , ⨂ adalah vektor eigen matriks batas dan , maka yang berarti adalah vektor eigen universal dari .
⨂ ⨂ ⨂ adalah vektor eigen matriks . Karena adalah vektor eigen semua matriks ,
Dalam pembahasan vektor eigen universal dibatasi pada kasus nilai eigen universal tidak sama dengan 0. Berikut diberikan teorema vektor eigen universal matriks interval . ( ) Teorema 4. Apabila suatu matriks interval mempunyai ( ) dan { adalah himpunan vektor eigen fundamental dari maka terdapat vektor eigen universal dari jika dan hanya jika sistem dua sisi dengan dan untuk semua mempunyai penyelesaian. Bukti: ( ) Diketahui suatu matriks interval dengan ( ) dan misalkan { adalah vektor eigen fundamental dari Akan dibuktikan sistem dua sisi mempunyai penyelesaian. Misalkan vektor eigen universal dari adalah , maka untuk setiap berlaku Karena vektor eigen universal merupakan kombinasi linier atas aljabar max-plus dari himpunan m vektor eigen fundametal matriks , maka ⨂ Sehingga untuk dengan ( ) , berlaku ⨂ ⨂ ⨂ ⨂ ⨂ ⨂ ⨂ ⨂ ⨂ ⨂ (2) jadi,
[
] adalah penyelesaian dari Persamaan (2)
( ) Diketahui suatu matriks interval dengan ( ) dan misalkan { adalah himpunan vektor eigen fundamental dari . Akan dibuktikan terdapat adalah suatu vektor eigen universal dari . Misalkan
[
,
] adalah penyelesaian dari sistem persamaan dua sisi
sehingga ⨂ ⨂ ⨂
⨂
⨂ ⨂ ⨂ ⨂ ⨂ ⨂ ( ) Terlihat bahwa dengan , ⨂ adalah vektor eigen matriks . Karena adalah vektor eigen matriks batas dan , maka adalah vektor eigen semua matriks , yang berarti adalah vektor eigen universal dari .
223
Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
ISSN : 2085-9902
3.2
Contoh Penyelesaian Untuk lebih jelasnya berikut diberikan contoh matriks yang mempunyai vektor eigen universal yang bersesuaian dengan nilai eigen tidak sama dengan 0. Contoh . Diberikan matriks interval [
]
( ) Dimana ( ) . Himpunan vektor eigen fundamental dari matriks . Kemudian dibentuk matriks
[
]
[
]
yaitu
[
dan
]
Dan matriks ( ) [
]
[
]
Salah satu penyelesaian dari sitem persamaan dua sisi [ Adalah
*
]
[
]
+, sehingga vektor eigen universal dari matriks adalah (
[
])
(
[
])
[
]
[
]
4. Kesimpulan Berdasarkan uraian di atas dapat diperoleh beberapa kesimpulan seperti berikut: a. Matriks interval mempunyai nilai eigen yang mungkin yang berada pada interval tertutup nilai eigen matriks batasnya. Yang dapat ditulis seperti berikut: [ ( ) ( )] Jika nilai eigen matriks batasnya sama, yaitu ( ) ( ), maka matriks mempunyai nilai eigen universal. b. Vektor eigen yang mungkin dari matriks dapat ditentukan dengan dengan cara meningkatkan matriks batas bawah dalam setiap koordinat sedemikian sehingga tidak melebihi matriks batas atas . c. Vektor eigen universal matriks interval dapat ditentukan seperti berikut: ( ) 1. Untuk ( ) maka vektor eigen universal ⨂ dari matriks interval , dapat di selesaikan dengan menyelesaikan sistem persamaan dua-sisi dengan matriks dan matriks . ( ) 2. Untuk ( ) maka vektor eigen universal ⨂ dari matriks interval , dapat di selesaikan dengan menyelesaikan sistem persamaan dua-sisi ( ) dengan matriks dan matriks . Ucapan Terimakasih
Penulis mengucapkan terimakasih kepada kolega dan reviewer yang telah memberikan masukan dalam peningkatan kualitas makalah ini.
224
Seminar Nasional Teknologi Informasi, Komunikasi dan Industri (SNTIKI) 8 Pekanbaru, 9 November 2016
ISSN : 2085-9902
Referensi [1] Aminu, Abdulhadi, Butkovic, P.”Introduction to Max-Linear Programing”. 2009. [2] Baccelli, Francois., dkk. ”Synchronization and Linearity, An Algebra for Discrete Even Systems”. Second edition. Wiley, Chichester. 2001. [3] Cechlarova, K.”Eigenvektors of Interval Matrices over Max-plus Algebra”. Journal of Discrete Applied Mathematics. Vol.150,hal. 2-15, 2005. [4] Cunninghame-Green, R. A., Butkovic, P. “The Equation over (max, +)”, Journal of Theoretical Computer Science, vol. 293, hal. 3–12, 2003. [5] Fahim, Kistosil, dkk.”Aplikasi Aljabar Max-plus pada Pemodelan dan Penjadwalan Busway yang Diintegrasikan dengan Kereta Api Komuter”. Jurnal Teknik Pomits, Jurusan Matematika Institut Teknologi Sepuluh November. Surabaya. 2013. [6] Farlow, Kasie. “Max-Plus Algebra”. Master’s Thesis submitted to the Faculty of the Virginia Polytechnic an State University. Blacksburg, Virginia. 2009. [7] Gioia, Federica dan Carlo N. Lauro.”Principal Component Analysis on Interval Data”.Universita degli Studi di Napoli. Vol.21, No.2, Hal.3-5. 2006. [8] Maharani, D.S., dan Suryoto.”Nilai dan Vektor Eigen Matriks Interval Atas Aljabar Max-plus”.Jurnal Matematika dan Komputer, Universitas Diponegoro. 2009. [9] Novitasari, Ratna dan Subiono.”Penyelesaian Sistem Dua Sisi dalam Aljabar Max-Plus”.Jurusan Matematika FMIPA Institud Teknologi Sepuluh November.2010. [10] Rudhito, M.A.” Sistem Linear Max-Plus Waktu-Invariant”. Master’s Thesis. UGM. 2003. [11] Rudhito, M.A., dkk.” Sistem Linear Max-Plus Interval Waktu Invariant”. Prosiding Seminar Nasional Mahasiswa S3 Matematika, UGM. 2008. [12] Rudhito, M.A., dkk.” Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Max-plus Interval”,Prosiding Seminar Nasional Mahasiswa S3 Matematika, UGM. 2008. [13] Rudhito, M.A., dkk.” Penerapan Aljabar Max-plus Interval pada Jaringan Antrian dengan waktu aktivitas Interval”, Prosiding Seminar Nasional Mahasiswa S3 Matematika, UGM. 2009. [14] Rudhito, M.A., dkk.” Matriks atas Aljabar Max-Plus Interval”. Jurnal Natur Indonesia. Vol. 13, No. 2, Hal. 94-99. 2011.
225