PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Karakterisasi Nilai Eigen, Vektor Eigen, dan Eigenmode dari Matriks Tak Tereduksi dan Tereduksi dalam Aljabar Max-Plus Himmatul Mursyidah (1213 201 001)
Dosen Pembimbing : Dr. Subiono, M.S. Program Magister Matematika Institut Teknologi Sepuluh Nopember Surabaya 2015 1 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Latar Belakang
2 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
3 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Perumusan Masalah
Permasalahan yang dibahas dalam penelitian ini adalah 1 Bagaimana karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tak tereduksi dalam aljabar max-plus? 2 Bagaimana karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tereduksi dalam aljabar max-plus? 3 Bagaimana contoh penerapan hasil karakterisasi yang diperoleh dalam masalah sistem transportasi dan antrian?
4 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Batasan Masalah
Batasan masalah dalam penelitian ini adalah 1 Karakter yang dibahas meliputi eksistensi, ketunggalan, dan nilai dari ketiga komponen. 2 Sistem transportasi dan sistem antrian yang digunakan sebagai contoh masing-masing memiliki matriks representasi berdimensi 3 × 3.
5 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Tujuan Penelitian Tujuan dari penelitian ini adalah 1 Mendapatkan hasil karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tak tereduksi dalam aljabar max-plus, berupa analisa karakter dari ketiga komponen yang diberikan dalam bentuk teori dan contoh. 2 Mendapatkan hasil karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tereduksi dalam aljabar max-plus, berupa analisa karakter dari ketiga komponen yang diberikan dalam bentuk teori dan contoh. 3 Memberikan contoh penerapan hasil karakterisasi yang diperoleh dalam masalah sistem transportasi dan antrian. 6 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Manfaat Penelitian Manfaat dari penelitian ini adalah 1 Sebagai penerapan ilmu dari mata kuliah aljabar max-plus. 2 Sebagai tambahan wawasan dan referensi dalam penerapan aljabar max-plus untuk menyelesaikan permasalahan, terutama yang berkaitan dengan masalah penjadwalan. 3 Sebagai referensi untuk penelitian selanjutnya mengenai nilai eigen, vektor eigen, dan eigenmode dalam aljabar max-plus.
7 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Kontribusi Hasil Penelitian
Kontribusi hasil penelitian ini terhadap pengembangan ilmu adalah sebagai referensi untuk penelitian lebih lanjut mengenai nilai eigen, vektor eigen, dan eigenmode dalam aljabar max-plus. Selain itu, hasil karakterisasi yang telah diperoleh dapat diterapkan dalam proses penjadwalan sistem menggunakan aljabar max-plus.
8 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Aljabar Max-Plus Definisi (2.1.1) Aljabar max-plus adalah suatu himpunan tidak kosong def Rε = R ∪ {ε} dengan R adalah himpunan bilangan real dan def ε = −∞, disertai dua operasi biner yang didefinisikan sebagai berikut: i. operasi biner ⊕, yaitu ∀x, y ∈ Rε berlaku def
x ⊕ y = max{x, y }, ii. operasi biner ⊗, yaitu ∀x, y ∈ Rε berlaku def
x ⊗ y = x + y. (Baccelli dkk, 2001)
9 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Suatu matriks A ∈ Rn×m max dinamakan reguler jika setiap baris A memuat setidaknya satu elemen tidak sama dengan ε. Matriks E(n, m) adalah matriks berukuran n × m dengan semua elemen sama dengan ε. Matriks E (n, m) yaitu matriks berukuran n × m dengan e untuk i = j, def [E (n, m)]i,j = ε untuk i 6= j, dengan e = 0. Jika m = n, maka E adalah matriks persegi dan dinamakan matriks identitas. Vektor di Rnmax dengan seluruh elemen sama dengan e disebut vektor satuan, dan dinotasikan dengan u. 10 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Graf dalam Aljabar Max-Plus Aplikasi aljabar max-plus erat kaitannya dengan graf berarah G = (N , D).
4 1
2
1 2 Gambar 2.1. Graf Komunikasi G(A)
Graf kritis dari G(A) dinotasikan G c (A) = (N c (A), Dc (A)) adalah graf yang terdiri dari himpunan titik dan arc yang berada pada sirkuit kritis dari graf G(A). 11 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Misal diberikan graf G = (N , D), untuk i, j ∈ N titik i dikatakan reachable dari titik j dinotasikan dengan jRi, jika terdapat suatu path dari j ke i, titik i dikatakan communicate dengan titik j dinotasikan dengan jCi, jika dan hanya jika i = j atau jRi dan iRj.
Relasi C adalah relasi ekivalen pada N . Dua jenis graf berdasarkan sifat keterhubungannya: Graf strongly connected apabila seluruh titik pada graf tersebut saling communicate. Matriks representasi dari graf strongly connected disebut matriks tak tereduksi. Graf tidak strongly connected apabila tidak semua titik pada graf saling communicate satu sama lain. Matriks representasi dari graf tidak strongly connected disebut matriks tereduksi. 12 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Nilai Eigen, Vektor Eigen, dan Eigenmode dalam Aljabar Max-Plus Definisi (2.3.1) Diberikan A ∈ Rn×n max suatu matriks persegi. Jika µ ∈ Rmax adalah suatu skalar dan v ∈ Rnmax adalah suatu vektor yang paling sedikit memuat satu elemen berhingga, sedemikian hingga A ⊗ v = µ ⊗ v, maka µ disebut nilai eigen dari A dan v adalah vektor eigen dari A yang bersesuaian dengan nilai eigen µ. (Heidergott dkk, 2006) 13 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Dalam menyelesaikan masalah penjadwalan erat kaitannya dengan upaya untuk mendapatkan barisan {x(k) : k ∈ N} dari model persamaan linear x(k + 1) = A ⊗ x(k),
(1)
n untuk k ≥ 0, dengan A ∈ Rn×n max dan x(0) = x0 ∈ Rmax adalah kondisi awal. Dengan induksi, Persamaan (1) menjadi
x(k) = A⊗k ⊗ x0 , untuk setiap k ≥ 0.
14 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Definisi (2.3.3) Suatu pasangan vektor (η, v) ∈ Rn × Rn disebut eigenmode tergeneralisasi dari matriks reguler A jika untuk setiap k ≥ 0 memenuhi A ⊗ (k × η + v) = (k + 1) × η + v. (Heidergott dkk, 2006)
15 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Algoritma untuk Menentukan Nilai Eigen, Vektor Eigen, dan Eigenmode dalam Aljabar Max-Plus Beberapa algoritma yang digunakan dalam proses penelitian adalah Algoritma Power digunakan untuk mencari nilai eigen sekaligus vektor eigen dari matriks tak tereduksi maupun matriks tereduksi. Algoritma Eigenmode Tergeneralisasi untuk Matriks Tereduksi Reguler.
16 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Tahapan Penelitian 1 2
3
4
5
Menguraikan dasar teori. Melakukan karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tak tereduksi dalam aljabar max-plus. Melakukan karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tereduksi dalam aljabar max-plus. Membuat contoh sistem dan menganalisa nilai eigen, vektor eigen, serta eigenmode dari sistem tersebut. Membuat kesimpulan.
17 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Karakterisasi Nilai Eigen, Vektor Eigen, dan Eigenmode dari Matriks Tak Tereduksi dalam Aljabar-Maxplus Eksistensi Nilai Eigen dari Matriks Tak Tereduksi Teorema (4.1.1) Jika A ∈ Rn×n max adalah matriks tak tereduksi, maka terdapat sirkuit rata-rata maksimum berhingga λ yang merupakan nilai eigen dari matriks A.
18 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Ketunggalan dan Nilai dari Nilai Eigen Matriks Tak Tereduksi Teorema (4.1.2) Untuk setiap matriks tak tereduksi A ∈ Rn×n max memiliki satu dan hanya satu nilai eigen. Nilai eigen tersebut dinotasikan dengan λ(A), merupakan suatu nilai berhingga dan sama dengan sirkuit rata-rata maksimum pada G(A), yaitu |γ|w . γ∈C(A) |γ|`
λ(A) = max
(Heidergott dkk, 2006)
19 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Eksistensi Vektor Eigen dari Matriks Tak Tereduksi Teorema (4.1.3) Jika A ∈ Rn×n max adalah matriks tak tereduksi dengan nilai eigen λ, maka vektor kolom [A∗λ ].,η untuk setiap titik η ∈ N c (A) merupakan vektor eigen dari matriks A yang bersesuaian dengan nilai eigen λ.
20 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Ketidaktunggalan Vektor Eigen dari Matriks Tak Tereduksi Teorema (4.1.4) Untuk setiap matriks tak tereduksi A ∈ Rn×n max memiliki vektor n eigen tidak tunggal, yaitu jika v ∈ Rmax adalah vektor eigen yang bersesuaian dengan nilai eigen λ, maka α ⊗ v juga merupakan vektor eigen yang bersesuaian dengan nilai eigen λ untuk sebarang α ∈ R. Ketidaktunggalan vektor eigen dari matriks tak tereduksi juga dapat diperoleh dari vektor-vektor eigen yang bukan merupakan hasil operasi ⊗ sebarang skalar elemen bilangan real dengan suatu vektor eigen.
21 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
1 1
2
3
3 2 Gambar 4.4. Graf G(B)
Contoh 4.1.3. Matriks representasi dari graf G(B) adalah 3 1 matriks tak tereduksi B = . Matriks B jelas 2 3 memiliki nilai eigen tunggal, yaitu: λ(B) =
2 M tr(B ⊗k ) k=1
k
tr(B) tr(B ⊗2 ) = ⊕ 1 2 3 6 = ⊕ = 3. 1 2
22 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Graf kritis dari G(B) adalah
1
2
3
3 Gambar 4.5.Graf G c (B)
Berikutnya, dihitung vektor eigen yang bersesuaian dengan nilai eigen λ(B) = 3. Pertama, dilakukan perhitungan Bλ sebagai berikut: Bλ = −λ ⊗ B 3 1 = −3 ⊗ 2 3 0 −2 = −1 0 23 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Selanjutnya, dihitung matriks Bλ+ Bλ+ =
2 M
Bλ⊗k
k=1
= =
0 −2 −1 0
0 −2 −1 0
⊕
0 −2 −1 0
.
Terakhir, dihitung matriks Bλ∗ yaitu Bλ∗ = E ⊕ Bλ+ 0 ε 0 −2 = ⊕ ε 0 −1 0 0 −2 = . −1 0 24 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Berdasarkan graf kritis G c (B) diketahui bahwa titik 1 dan titik 2 merupakan elemen dari N c (B), sehingga kolom ke-1 dan kolom ke-2 dari matriks Bλ∗ merupakan vektor eigen dari matriks Byang bersesuaian dengan nilaieigen λ(B) = 3, yaitu 0 −2 [Bλ∗ ].,1 = dan [Bλ∗ ].,2 = . Dapat dicermati −1 0 bahwa vektor eigen [Bλ∗ ].,1 bukan merupakan hasil operasi ⊗ sebarang bilangan real dengan vektor eigen [Bλ∗ ].,2 , begitu pula sebaliknya.
25 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Nilai dari Elemen Vektor Eigen Matriks Tak Tereduksi Teorema (4.1.5) Untuk setiap matriks tak tereduksi A ∈ Rn×n max hanya memiliki vektor-vektor eigen dengan elemen berhingga.
26 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Eigenmode sebagai Perluasan Nilai eigen dan Vektor Eigen Lemma (4.1.1) Jika pasangan vektor (η, v) adalah eigenmode tergeneralisasi dari matriks reguler A, maka vektor η merupakan perluasan nilai eigen dari matriks A dan vektor v adalah vektor eigennya. Lebih lanjut, vektor η = lim x(k) . k k→∞
(Heidergott dkk, 2006)
27 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Eksistensi Eigenmode dari Matriks Tak Tereduksi Teorema (4.1.6) Jika A ∈ Rn×n max adalah matriks tak tereduksi dengan nilai eigen λ dan vektor eigen v, maka terdapat pasangan vektor (η, v) yang merupakan eigenmode dari matriks tak tereduksi A.
28 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Ketidaktunggalan Eigenmode dari Matriks Tak Tereduksi Teorema (4.1.7) Untuk setiap matriks tak tereduksi A ∈ Rn×n max memiliki eigenmode yang tidak tunggal.
29 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Nilai dari Elemen Vektor dalam Eigenmode Matriks Tak Tereduksi Teorema (4.1.8) Untuk setiap matriks tak tereduksi A ∈ Rn×n max memiliki eigenmode berupa pasangan vektor dengan semua elemen vektor berhingga.
30 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Karakterisasi Nilai Eigen, Vektor Eigen, dan Eigenmode dari Matriks Tereduksi dalam Aljabar-Maxplus Relasi C adalah relasi ekivalen pada N . Akibatnya, relasi C dapat mempartisi N ke dalam kelas ekivalen yang saling asing, misal N = N1 ∪ . . . ∪ Nq . Matriks tereduksi A selalu dapat dijadikan suatu bentuk matriks blok segitiga atas sebagai berikut: A1,1 A1,2 . . . . . . A1,q E A2,2 . . . . . . A2,q .. E E A . , (2) 3,3 . . . .. .. .. .. .. . . E E . . . E Aq,q 31 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Matriks Ai,i merupakan matriks tak tereduksi atau Ai,i = ε, untuk setiap i ∈ q. Setiap elemen berhingga dari matriks As,r , 1 ≤ s < r ≤ q merupakan bobot arc dari suatu titik elemen Nr ke suatu titik elemen Ns . Bentuk matriks blok segitiga atas tidak tunggal. Untuk mendapatkan nilai eigen dan vektor eigen dari matriks A ∈ Rn×n max , algoritma dilakukan secara berulang dari bentuk persamaan linear x(k + 1) = A ⊗ x(k), k = 0, 1, 2, . . . .
(3)
32 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Eksistensi Nilai Eigen dan Vektor Eigen dari Matriks Tereduksi Teorema (4.2.1) Jika untuk sebarang keadaan awal x(0) 6= ε sistem Persamaan (3) memenuhi x(p) = c ⊗ x(q) untuk beberapa bilangan bulat p dan q dengan p > q ≥ 0 dan beberapa bilangan real c, maka x(k) = k→∞ k lim
λ λ ... λ
T
,
c . Selanjutnya, λ adalah suatu nilai eigen dari dengan λ = p−q matriks A dengan vektor eigen diberikan oleh
v=
p−q M
λ⊗(p−q−i) ⊗ x(q + i − 1) .
i=1
(Subiono, 2012)
33 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Suatu matriks tereduksi belum tentu memiliki nilai eigen yang tunggal Contoh 4.2.3. Diberikan matriks tereduksi representasi graf tidak strongly connected G(A) sebagai berikut: 1 ε A= . ε 3 Nilai eigen dari matriks A tidak tunggal. Hal tersebut tampak dari uraian berikut: 1 ε 0 1 0 ⊗ = =1⊗ , ε 3 ε ε ε dan
1 ε ε 3
⊗
ε 0
=
ε 3
=3⊗
ε 0
.
Jadi 1 dan 3 adalah nilai eigen dari matriks A. 34 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Contoh 4.2.4. Diberikan matriks tereduksi representasi graf tidak strongly connected G(B) sebagai berikut: 1 0 B= . ε 0 Nilai eigen dari matriks B tunggal. Hal tersebut tampak dari uraian berikut: 1 0 0 1 0 ⊗ = =1⊗ . ε 0 ε ε ε Sedangkan untuk a a 1 0 ⊗ =λ⊗ , ε 0 0 0
(4)
35 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Dari Persamaan (4) didapatkan max{1 + a, 0} = λ + a,
(5)
max{ε, 0} = λ.
(6)
dan
Dari Persamaan (6) diperoleh λ = 0, sehingga apabila λ = 0 disubstitusikan pada Persamaan (5) didapatkan max{1 + a, 0} = a.
(7)
Jadi tidak dapat ditemukan a yang memenuhi Persamaan (7).
36 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Ketidaktunggalan Vektor Eigen dari Matriks Tereduksi Teorema (4.2.2) Untuk setiap matriks tereduksi A ∈ Rn×n max yang memiliki nilai eigen, mempunyai vektor eigen tidak tunggal. Jika v ∈ Rnmax adalah vektor eigen yang bersesuaian dengan nilai eigen λ, maka α ⊗ v juga merupakan vektor eigen yang bersesuaian dengan nilai eigen λ untuk sebarang α ∈ R.
37 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Nilai dari Nilai Eigen Matriks Tereduksi Teorema (4.2.3) Jika matriks tereduksi A ∈ Rn×n max memiliki nilai eigen, maka nilai eigen tersebut memiliki nilai berhingga elemen bilangan real. Nilai dari Elemen Vektor Eigen Matriks Tereduksi Berdasarkan Contoh 4.2.3, dan Definisi 2.3.1 mengenai nilai eigen dan vektor eigen dalam aljabar max-plus, didapatkan vektor eigen dari matriks tereduksi memuat paling sedikit satu elemen berhingga.
38 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Penyelesaian dari persamaan x = (A ⊗ x) ⊕ b Teorema (4.2.4) n Misalkan A ∈ Rn×n max dan b ∈ Rmax . Jika bobot rata-rata sirkuit graf G(A) kurang dari atau sama dengan 0, maka x = A∗ ⊗ b ∞ L def dengan A∗ = E ⊕ A+ = A⊗i adalah penyelesaian dari i=0
x = (A ⊗ x) ⊕ b. Lebih lanjut, jika bobot sirkuit dalam G(A) adalah negatif, maka penyelesaiannya tunggal. (Subiono, 2012)
39 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Persamaan Rekurensi Nonhomogen Teorema (4.2.5) Perhatikan persamaan rekurensi nonhomogen berikut x(k + 1) = A ⊗ x(k) ⊕
m M
Bj ⊗ uj (k),
(8)
j=1
dengan A ∈ Rn×n max adalah matriks tak tereduksi yang memiliki n×m nilai eigen λ atau A = ε dengan λ = ε, matriks Bj ∈ Rmax j mj dengan mj ≥ 1 memenuhi Bj 6= E, sedangkan uj (k) ∈ Rmax m j memenuhi uj (k) = τjk ⊗ wL j (k), k ≥ 0 dengan wj ∈ Rmax dan τj ∈ R. Untuk suatu τ = τj terdapat bilangan bulat K ≥ 0 j∈m
dan vektor v ∈ R sedemikian hingga barisan x(k) = µ⊗k ⊗ v, dengan µ = λ ⊗ τ memenuhi persamaan rekurensi (8) untuk setiap k ≥ K . (K¨onigsberg, 2009) n
40 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Matriks tereduksi A dapat disajikan dalam bentuk matriks blok segitiga atas (2), dengan blok matriks Ai,i adalah matriks tak tereduksi sehingga λi = λ(Ai,i ) atau Ai,i = ε sehingga λi = ε. Selanjutnya, misal diambil vektor x(k) yang bersesuaian dengan matriks blok segitiga atas (2), yaitu x1 (k) x2 (k) x(k) = .. . . xq (k) Matriks blok segitiga atas dari matriks tereduksi A memenuhi Persamaan rekurensi (8), yaitu: xi (k + 1) = Ai,i ⊗ xi (k) ⊕
q M
Ai,j ⊗ xj (k); i ∈ q, k ≥ 0. (9)
j=i+1 41 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Teorema (4.2.6) Jika dalam Persamaan (9) matriks Aq,q adalah matriks tak tereduksi, dan untuk i ∈ q − 1 matriks Ai,i adalah matriks tak tereduksi atau Ai,i = ε, maka terdapat skalar ξ1 , ξ2 , . . . , ξq ∈ R dan vektor v1 , v2 , . . . , vq dengan seluruh elemen vektor berhingga sedemikian hingga xi (k) = ξi⊗k ⊗ vi , i ∈ q memenuhi Persamaan rekurensi (9) untuk setiap k ≥ 0. Skalar ξ1 , ξ2 , . . . , ξq ditentukan dengan M ξj ⊕ λi , ξi = j∈Hi
dengan Hi = {j ∈ q : j > i, Ai,j 6= E}. (K¨onigsberg, 2009) 42 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Eksistensi Eigenmode dari Matriks Tereduksi Akibat (4.2.1) Jika A ∈ Rn×n max adalah matriks tereduksi reguler, maka terdapat pasangan vektor (η, v) ∈ Rn × Rn yang merupakan eigenmode tergeneralisasi dari matriks A, sedemikian hingga untuk setiap k ≥ 0: A ⊗ (k × η + v) = (k + 1) × η + v. (K¨onigsberg, 2009)
43 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Ketidaktunggalan Eigenmode dari Matriks Tereduksi Teorema (4.2.7) Untuk setiap matriks tereduksi reguler A ∈ Rn×n max memiliki eigenmode yang tidak tunggal, yaitu jika (η, v) adalah eigenmode dari matriks A, maka (η, α ⊗ v) dengan α ∈ R juga merupakan eigenmode dari matriks A.
44 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Nilai dari Elemen Vektor dalam Eigenmode Matriks Tereduksi Teorema (4.2.8) Untuk setiap matriks tereduksi reguler A ∈ Rn×n max memiliki eigenmode berupa pasangan vektor dengan semua elemen vektor berhingga.
45 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Contoh Penerapan Hasil Karakterisasi dalam Masalah Sistem Transportasi dan Antrian Contoh 4.3.1 Sinkronisasi jadwal keberangkatan sistem transportasi umum busway transjakarta. Tabel 4.1. Waktu Tempuh Tiga Halte Busway Transjakarta dari Dua Koridor.
Sumber: Winarni, 2009 46 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Graf rute busway berdasarkan data Tabel 4.1 diberikan sebagai berikut: 1 2
3
Gambar 4.8. Graf Rute Busway Transjakarta dari Dua Koridor dan Tiga Halte.
47 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Proses sinkronisasi jadwal membutuhkan nilai eigen, vektor eigen, dan eigenmode dari matriks representasi graf. Oleh karena itu, terlebih dahulu dilakukan analisa ketiga komponen tersebut. Tahapan analisa diawali dengan identifikasi jenis graf, misal graf rute busway diberi nama graf G(A), maka graf G(A) adalah graf strongly connected. Matriks representasi dari graf G(A) adalah ε 8, 63 ε ε 43, 14 , A = 10, 31 ε 52, 81 ε yang merupakan matriks tak tereduksi. 48 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Nilai Eigen dari Matriks A
Berdasarkan karakterisasi nilai eigen, diketahui bahwa matriks tak tereduksi memiliki nilai eigen tunggal berhingga, sehingga jelas pada contoh kasus ini didapatkan nilai eigen tunggal berhingga, yaitu λ(A) = 47, 975.
49 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Vektor Eigen dari Matriks A Berdasarkan karakterisasi vektor eigen, diketahui bahwa matriks tak tereduksi memiliki vektor eigen yang tidak tunggal dengan semua elemen berhingga untuk setiap vektor eigen tersebut. Dalam contoh kasus ini, didapatkan vektor eigen yang tidak tunggal, yaitu −39, 345 , e α⊗v =α⊗ 4, 835 untuk setiap α ∈ R. Karena setiap entri vektor eigen adalah elemen R, sehingga jelas semua elemen vektor eigen berhingga. 50 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Eigenmode dari Matriks A Eigenmode dari matriks tak tereduksi juga tidak tunggal dengan semua elemen vektor dalam eigenmode berhingga, sehingga dalam kasus ini eigenmode yang diperoleh adalah tidak tunggal, yaitu 47, 975 −39, 345 , e (η, α ⊗ v) = 47, 975 , α ⊗ 47, 975 4, 835 untuk setiap α ∈ R.
51 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Sinkronisasi Jadwal Busway Transjakarta untuk 3 Halte dan 2 Koridor Tabel 4.2. Jadwal Keberangkatan Awal Busway Transjakarta untuk Tiap Halte.
dengan keperiodikan sama dengan 47 menit 58,5 detik. 52 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Contoh 4.3.2 Analisa sistem antrian pelayanan pergantian jenis tabungan customer pada satu petugas customer service.
Gambar 4.10. Petri Net Antrian Pelayanan Pergantian Jenis Tabungan pada Satu Petugas Customer Service. 53 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Petri net terdiri dari 7 transisi: t1 : customer datang ke bank, t2 : customer mengambil nomor antrian, t3 : costumer dilayani oleh customer service, t4 : customer service membawa berkas customer pada (teller), t5 : berkas customer selesai diproses teller, t6 : customer selesai dilayani oleh customer service, t7 : customer meninggalkan bank,
54 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Petri net terdiri dari 6 place: p1 : customer yang sedang menunggu giliran mengambil nomor antrian, p2 : customer yang sedang menunggu giliran dilayani customer service, p3 : customer yang sedang dilayani customer service, p4 : customer yang sedang menunggu pemrosesan berkas oleh teller, p5 : Idle atau customer service sedang tidak sibuk, p6 : customer yang sudah selesai dilayani oleh customer service.
55 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Model antrian pelayanan pergantian jenis tabungan bank pada satu petugas customer service: vt1 ,k t1 (k) t5 (k) = vt5 ,k ⊗ vt2 ,k ⊗ vt1 ,k t6 (k) vt6 ,k ⊗ vt5 ,k ⊗ vt2 ,k ⊗ vt1 ,k
ε vt5 ,k vt6 ,k ⊗ vt5 ,k
ε t1 (k − 1) ⊗ t5 (k − 1) . vt5 ,k t6 (k − 1) vt6 ,k ⊗ vt5 ,k
Lama masing-masing proses diberikan pada tabel berikut: Tabel 4.3. Daftar Proses Pelayanan Pergantian Jenis Tabungan Bank.
56 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Dengan data pada Tabel 4.3 diperoleh model antrian pelayanan pergantian jenis tabungan bank pada satu petugas customer service sebagain berikut: t1 (k) 8 ε ε t1 (k − 1) t5 (k) = 13, 5 5 5 ⊗ t5 (k − 1) . t6 (k) 33, 5 25 25 t6 (k − 1) Selanjutnya, akan dianalisa nilai eigen, vektor eigen, dan eigenmode dari matriks tereduksi 8 ε ε B = 13, 5 5 5 . 33, 5 25 25
57 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
matriks tereduksi belum tentu memiliki nilai eigen. Oleh karena itu, berikut akan dicari nilai eigen dari matriks tereduksi B dengan menggunakan Power. Misal dengan Algoritma 0 keadaan awal x(0) = 0 , diperoleh evolusi keadaan 0 16 8 0 0 , 13, 5 , 38, 5 , . . . . 58, 5 33, 5 0 Tidak dapat ditemukan bilangan bulat p > q ≥ 0 dan bilangan real c yang memenuhi x(p) = c ⊗ x(q). Jadi B tidak memiliki nilai eigen. Meskipun demikian, karena B adalah matriks tereduksi reguler maka dapat dicari eigenmode berupa pasangan vektor dengan semua elemen vektor berhingga. 58 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Langkah untuk mendapatkan eigenmode dari matriks B: Ditentukan bentuk matriks blok segitiga atas dari matriks B, yaitu: 5 5 13, 5 A = 25 25 33, 5 . ε ε 8 Dihitung nilai eigen dari matriks A2,2 , yaitu λ2 sehingga dapat diambil ξ2 = λ2 = 8 dan misal v2 = 0. 5 Dihitung nilai eigen dari matriks A1,1 = 25 Didapatkan λ1 = 25.
= 8, diambil 5 25
.
59 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Karena λ1 > ξ2 , maka ξ1 = λ1 = 25 dan dihitung vektor v1 : ξ1 ⊗ v1 = (A1,1 ⊗ v1 ) ⊕ (A1,2 ⊗ v2 ) v1 5 5 v1 13, 5 25 ⊗ = ⊗ ⊕ ⊗0 . v2 25 25 v2 33, 5 Dari persamaan di atas didapatkan 25 + v1 = max{5 + v1 , 5 + v2 , 13, 5} 25 + v1 = 13, 5 v1 = −11, 5. dan 25 + v2 25 + v2 25 + v2 v2
= = = =
max{25 + v1 , 25 + v2 , 33, 5} max{13, 5, 25 + v2 , 33, 5} 33, 5 8, 5. 60 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
−11, 5 Jadi, didapatkan v1 = . Oleh karena itu, pasangan 8, 5 T vektor (η, v) dengan η = 25 25 8 dan T v = −11, 5 8, 5 0 adalah eigenmode dari matriks A sebab untuk k = 0, memenuhi: T A ⊗ (0 × η + v) = 13, 5 33, 5 8 = 1 × η + v, untuk k = 1, memenuhi: A ⊗ (1 × η + v) =
38, 5 58, 5 16
T
= 2 × η + v,
dan seterusnya, vektor η dan v untuk k = 0, 1, 2, . . . memenuhi A ⊗ (k × η + v) = (k + 1) × η + v. 61 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Dari hasil eigenmode, dapat diketahui waktu berakhirnya tiap proses pelayanan customer saat ke-k. Misal waktu paling awal terjadi pada pukul 08.00, maka untuk k sama dengan 0 dan 1 didapatkan hasil seperti pada Tabel 4.4. Tabel 4.4. Waktu Proses Pelayanan Customer Pertama dan Kedua.
62 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Kesimpulan 1. Berdasarkan karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tak tereduksi diperoleh: a. Matriks tak tereduksi memiliki nilai eigen tunggal berupa suatu nilai berhingga. b. Vektor eigen yang bersesuaian dengan nilai eigen dari matriks tak tereduksi tidak tunggal dengan semua elemen berhingga. c. Matriks tak tereduksi memiliki eigenmode yang tidak tunggal dengan semua elemen vektor dalam eigenmode berhingga.
63 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
2. Berdasarkan karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tereduksi diperoleh: a. Matriks tereduksi belum tentu memiliki nilai eigen. Jika matriks tereduksi memiliki nilai eigen, maka nilai eigen tersebut belum tentu tunggal dan memiliki nilai berhingga. b. Vektor eigen yang bersesuaian dengan nilai eigen dari matriks tereduksi tidak tunggal, dan vektor eigen paling sedikit memuat satu elemen berhingga. c. Matriks tereduksi reguler memiliki eigenmode yang tidak tunggal dengan semua elemen vektor dalam eigenmode berhingga.
64 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
3. Hasil karakterisasi nilai eigen, vektor eigen, dan eigenmode dari matriks tak tereduksi maupun tereduksi dapat diterapkan dalam proses penyelesaian masalah sistem transportasi dan antrian.
65 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Saran
Penelitian mengenai karakterisasi nilai eigen, vektor eigen, dan eigenmode baik dari matriks tak tereduksi maupun matriks tereduksi dapat dilanjutkan untuk mencari jumlah maupun pola dari ketiga komponen yang diketahui memiliki karakter tidak tunggal. Selain itu, penelitian nilai eigen, vektor eigen, dan eigenmode dapat dikembangkan untuk karakter-karakter lain selain eksistensi, ketunggalan, dan nilai dari ketiga komponen tersebut.
66 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Daftar Pustaka Baccelli, F., Cohen, G., Olsder, G.J., dan Quadrat, J.P. (2001), Synchronization and Linearity, An Algebra for Discrete Event System, Wiley-Interscience, New York. Heidergott, B., Olsder, G. J., dan van der Woude, J. (2006), Max Plus at Work, Modelling and Analysis of Synchronized System: A Course on Max-Plus Algebra and Its Applications, Princeton University Press, United Kingdom. K¨onigsberg, Z.R. (2009), ”A Generalized Eigenmode Algorithm for Reducible Regular Matrices over the Max-Plus Algebra”, Chinese Control and Decision Conference, Chines, hal. 5598-5603. 67 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Shofianah, N. (2009), Analisis kedinamikan Sistem pada Penjadwalan Flow Shop Menggunakan Aljabar Max-Plus, Tesis Magister Matematika, Institut Teknologi Sepuluh Nopember, Surabaya. Subiono (2012), Aljabar Maxplus dan Terapannya, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember, Surabaya. Suyanto, Y.H. (2011), Penjadwalan Kegiatan Belajar Mengajar Di Sekolah Menengah Atas (SMAK) St. Louis 1 Surabaya Menggunakan Aljabar Max-Plus, Tesis Magister Matematika, Institut Tekonologi Sepuluh Nopember, Surabaya.
68 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
Telehala, M.M. (2010), Model Penjadwalan Kegiatan Pembelajaran Sekolah pada Kelas Moving dengan Menggunakan Aljabar Max-Plus, Tesis Magister Matematika, Institut Tekonologi Sepuluh Nopember, Surabaya. Winarni (2009), Penjadwalan Jalur Bus Dalam Kota dengan Aljabar Max-Plus, Tesis Magister Matematika, Institut Teknologi Sepuluh Nopember, Surabaya. Zuliyanto, A., Siswanto, dan Muslich (2012), ”Algoritma Eigenmode Tergeneralisasi untuk Matriks Tereduksi Reguler Di Dalam Aljabar Max-Plus”, Prosiding Seminar Nasional Matematika 2012.
69 / 70
PENDAHULUAN
DASAR TEORI
METODA PENELITIAN
PEMBAHASAN
KESIMPULAN DAN SARAN
70 / 70