BAB I PENDAHULUAN
1.1
Latar Belakang Masalah Aljabar max-plus adalah himpunan R := R ∪ {−∞} dilengkapi dengan op-
erasi a ⊕ b := max(a, b) dan a ⊗ b := a + b. Elemen identitas penjumlahan dan perkalian berturut-turut yaitu ε = −∞ dan e = 0. Operasi ini pada matriks atas aljabar max-plus bersifat assosiatif, komutatif, dan distributif. Aljabar max-plus memungkinkan untuk menggambarkan dan mempelajari bagian dari masalah nonlinear yang muncul misalnya dalam jaringan transprotasi, penjadwalan mesin, teknologi informasi, dan kejadian sistem dinamis diskrit, dengan menerapkan pendekatan aljabar linear. Contoh sistem jaringan transportasi berikut bisa memberikan indikasi khusus bagaimana kebutuhan transformasi aljabar ini muncul dalam kehidupan nyata. Dimisalkan pada suatu jaringan transportasi terdapat dua kota dengan S1 stasiun di kota pertama dan S2 stasiun di kota kedua. Lintasan dari S1 ke S2 dinamakan lintasan 1. Lintasan dari S2 ke S1 dinamakam lintasan 2. Lintasan 1 dan lintasan 2 dinamakan lintasan jarak jauh. Pada pada sistem ada dua lintasan lagi, satu lintasan mengelilingi kota 1 dan satu lintasan lagi mengelilingi kota 2. Berturut-turut dinamakan lintasan 3 dan lintasan 4. Lintasan 3 dan 4 dinamakan lintasan dalam kota. Lintasan 3 dapat digambarkan sebagai loop yang berawal dan berakhir pada S1 , begitu juga dengan lintasan 4 yang berawal dan berakhir pada S2 . Lintasan 3 dan 4 masing-masing terdapat 1 kereta. Pada kedua lintasan jarak jauh terdapat 2 kereta yang melintasinya secara bergantian.
1
2
Asumsi: 1. Waktu tempuh setiap lintasan adalah tetap. 2. Frekuensi kereta sama pada setiap lintasan. 3. Dua kereta pada stasiun Si harus meninggalkan stasiun secara bersamaan.
Misalkan xi (k)
= waktu keberangkatan ke-k untuk 2 kereta dari stasiun i.
aij
= waktu tempuh stasiun j ke stasiun i.
di (k)
= jadwal keberangkatan kereta ke-k untuk 2 kereta dari stasiun i
Masalah: Buatlah jadwal keberangkatan yang realistis dan teratur untuk kereta ke-1 sampai dengan kereta ke-7 dari stasiun S1 dan S2 . Jadwal keberangkatan realistis sendiri yaitu jika jadwal keberangkatan kereta ke-k di stasiun Si tidak lebih cepat dari kedatangan kereta ke-(k − 1) dari stasiun lainnya, sedangkan jadwal keberangkatan yang teratur yaitu untuk jadwal keberangkatan ke-(k + 1) merupakan jadwal keberangkatan ke-k ditambah suatu periode.
Dari penotasian dan asumsi di atas diperoleh: x1 (k + 1) ≥ x2 (k) + a12
(1.1)
x1 (k + 1) ≥ x1 (k) + a11 sehingga x1 (k + 1) = max{x2 (k) + a12 , x1 (k) + a11 } dan
(1.2)
3
x2 (k + 1) ≥ x1 (k) + a21
(1.3)
x2 (k + 1) ≥ x2 (k) + a22 sehingga x2 (k + 1) = max{x1 (k) + a21 , x2 (k) + a22 }
(1.4)
Sehingga diperoleh x1 (k + 1) = max{x2 (k) + a12 , x1 (k) + a11 }
(1.5)
x2 (k + 1) = max{x1 (k) + a21 , x2 (k) + a22 }
yang dalam aljabar max-plus dinotasikan x1 (k + 1) = (x2 (k) ⊗ a12 ) ⊕ (x1 (k) ⊗ a11 )
(1.6)
x2 (k + 1) = (x1 (k) ⊗ a21 ) ⊕ (x2 (k) ⊗ a22 )
atau x1 (k + 1) = (a11 ⊗ x1 (k)) ⊕ (a12 ⊗ x2 (k))
(1.7)
x2 (k + 1) = (a21 ⊗ x1 (k)) ⊕ (a22 ⊗ x2 (k))
atau
x1 (k + 1) a11 a12 x1 (k) = ⊗ a21 a22 x2 (k) x2 (k + 1)
(1.8)
4
secara umum
a11 a12 x(k + 1) = A ⊗ x(k), dengan A = . a21 a22
(1.9)
Agar jadwal keberangkatan teratur maka harus memenuhi
d(k + 1) = τ ⊗ d(k),
(1.10)
dengan τ merupakan periodenya. Karena jadwal keberangkatan harus realistis maka
x(k) ≤ d(k).
(1.11)
Jika x(k) pada Persamaan(1.9) diganti dengan d(k) diperoleh
d(k + 1) = A ⊗ d(k).
(1.12)
Dari Persamaan(1.10) dan Persamaan(1.12) diperoleh
A ⊗ d(k) = τ ⊗ d(k).
(1.13)
Jika d(k) pada Persamaan(1.13) diganti dengan x(k) diperoleh
A ⊗ x(k) = λ ⊗ x(k)
(1.14)
dengan λ ≤ τ . λ pada Persamaan(1.14) merupakan nilai eigen dari matriks A sedangkan x(k) adalah vektor eigen dari A yang berkorespondensi dengan nilai eigen λ.
5
Jadi untuk menyelesaikan jaringan transportasi harus mempelajari nilai eigen dan vektor eigen atas aljabar max-plus.
1.2
Perumusan Masalah Rumusan masalah yang dibahas dalam skripsi ini adalah:
1. Apa yang dimaksud dengan aljabar max-plus, matriks dan vektor atas aljabar max-plus, dan teori graf? 2. Bagaimana hubungan antara teori graf dan matriks atas aljabar max-plus? 3. Apa sifat-sifat nilai eigen dan vektor eigen matriks atas aljabar max-plus? 4. Bagaimana mencari nilai eigen dan vektor eigen atas aljabar max-plus? 5. Apa manfaat nilai eigen dan vektor eigen pada masalah jaringan transportasi?
1.3
Batasan Masalah Pada penulisan skripsi ini, penulis hanya membahas nilai eigen dan vektor
eigen untuk matriks atas Aljabar max-plus yang irreducible, sebab untuk matriks atas Aljabar max-plus yang reducible memerlukan penelitian yang lebih lanjut.
1.4
Maksud dan Tujuan Selain untuk memenuhi syarat kelulusan Program Strata-1 (S1) Program Studi
Matematika Universitas Gadjah Mada, penyusunan skripsi ini bertujuan untuk mempelajari lebih jauh mengenai Aljabar max-plus terutama mengenai sifat-sifat nilai eigen dan vektor eigen atas Aljabar max-plus termasuk didalamnya adalah bagaimana mencari nilai eigen dan vektor eigen untuk matriks atas Aljabar max-plus yang tidak dapat direduksi.
6
1.5
Tinjauan Pustaka Secara keseluruhan tulisan ini mengacu pada tesis yang ditulis oleh Kasie G.
Farlow yang berjudul M ax − P lus Algebra. Pada tesis ini terdapat pembahasan mengenai nilai eigen dan vektor eigen dari suatu matriks atas aljabar max-plus. Sebagai tambahan pendukung juga mengacu pada buku-buku lain diantaranya Syncronization and Linearity yang ditulis oleh F. Bacceli d.k.k. yang membahas tentang definisi aljabar max-plus, vektor dan matriks atas aljabar max-plus. Buku P engantar T eori Graf yang di tulis oleh Prof. Setiadji penulis gunakan untuk mempelajari tentang tori graf. Penulis juga mempelajari jurnal- jurnal untuk memahami nilai eigen dan vektor eigen yang ditulis oleh B. De Schutter d.k.k. yang berjudul On max-algebraic models for transportation networks dan Modelling and control of railway networks. Penulis juga mengacu pada buku aljabar linear elementer yang ditulis oleh Howard Anton untuk memahami dasar nilai eigen dan vektor eigen.
1.6
Metodologi Penelitian Metode yang digunakan dalam pembuatan skripsi ini adalah dengan terlebih
dahulu melakukan studi literatur mengenai masalah eigen. Dalam rangka mengumpulkan bahan, penulis mencari dan mengumpulkan buku-buku referensi dan jurnal-jurnal yang diperoleh dari perpustakaan maupun internet yang selanjutnya dikonsultasikan dengan dosen pembimbing.
1.7
Sistematika Penulisan Pada penulisan skripsi ini, penulis menggunakan sistematika sebagai berikut.
BAB I
PENDAHULUAN
Pada bab ini dibahas mengenai latar belakang masalah, perumusan masalah, batasan
7
masalah, maksud dan tujuan, tinjauan pustaka, metodologi penelitian, sistematika penulisan. BAB II
DASAR TEORI
Pada bab ini dibahas mengenai konsep dasar aljabar max-plus, matriks dan vektor atas aljabar max-plus, dan teori graf. BAB III NILAI EIGEN DAN VEKTOR EIGEN ATAS ALJABAR MAX-PLUS Pada bab ini dibahas mengenai nilai eigen dan vektor eigen matriks atas aljabar maxplus. BAB IV PENUTUP Pada bab ini berisi kesimpulan dan saran yang dapat diambil dari materi-materi yang teleh dibahas dalam bab-bab sebelumnya.
