persamaankarakteristik suatumatriks …...perpustakaan.uns.ac.id digilib.uns.ac.id commit to user...
TRANSCRIPT
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
PERSAMAAN KARAKTERISTIK SUATU MATRIKS
DALAM ALJABAR MAX-PLUS
oleh
ADIMAS BANJAR
M0107019
SKRIPSI
ditulis dan diajukan untuk memenuhi sebagian persyaratan
memperoleh gelar Sarjana Sains Matematika
JURUSAN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
2012
i
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
ABSTRAK
Adimas Banjar. 2012. PERSAMAAN KARAKTERISTIK SUATUMATRIKSDALAM ALJABAR MAX PLUS . Fakultas Matematika dan Ilmu PengetahuanAlam. Universitas Sebelas Maret.
Aljabar max-plus dibentuk dari himpunan Rmax = {−∞} ∪R yang dileng-kapi dengan operasi maksimum (⊕) dan penjumlahan (⊗). Aljabar max-plus
merupakan suatu idempotent semi-field. Sedangkan aljabar konvensional adalahhimpunan R yang dilengkapi penjumlahan (+) dan perkalian (×) dan meru-pakan suatu field. Aljabar max-plus mempunyai struktur yang mirip denganaljabar konvensional menyebabkan sifat dan konsep aljabar linear mempunyaiekuivalensi dalam aljabar max-plus. Penelitian ini dilaksanakan guna menen-tukan persamaan karakteristik suatu matriks dalam aljabar max-plus. Hasil daripenelitian ini adalah persamaan karakteristik dalam aljabar max-plus, yaitu
λ⊗n ⊕⊕
k∈ℓ
dk ⊗ λ⊗n−k =⊕
k∈
dk ⊗ λ⊗n−k,
dengan dk adalah koefisien tertinggi untuk setiap λ⊗n−k
.
Kata kunci: Aljabar max-plus, aljabar linear, persamaan karakteristik
iv
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
ABSTRACT
Adimas Banjar. 2012. CHARACTERISTIC EQUATION ON MAX PLUSALGEBRAIC MATRICES Faculty of Mathematics and Natural Sciences, SebelasMaret University.
Max-plus algebra is constructed by the set Rmax = R ∪ {−∞} endowed withmaximum (⊕) and addition (⊗) operations. Max-plus algebra have propertiesas idempotent semi-field. In other hand, the properties of conventional algebrathat constructed by the set of R endowed with addition (+) and multiplication(×) operations is a field. There is exist remarkable similarity between max-plusalgebra and conventional algebra, as consequence there is many linear algebraconcept have a max-plus analogue. The main objective of this research is to findcharacteristic equation on max-algebraic matrices. Method of this research is aliterary study. Result of this research are max-algebraic characteristic equation,that is
λ⊗n ⊕⊕
k∈ℓ
dk ⊗ λ⊗n−k =⊕
k∈
dk ⊗ λ⊗n−k,
where dk are the highest coefficient from λ⊗n−k
Key words: Max-plus algebra, linear algebra, characteristic polynomial
v
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
PERSAMAAN KARAKTERISTIK SUATU MATRIKS
DALAM ALJABAR MAX-PLUS
oleh
ADIMAS BANJAR
M0107019
SKRIPSI
ditulis dan diajukan untuk memenuhi sebagian persyaratan
memperoleh gelar Sarjana Sains Matematika
JURUSAN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
2012
i
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
SKRIPSI
PERSAMAAN KARAKTERISTIK SUATU MATRIKS DALAM
ALJABAR MAX-PLUS
yang disiapkan dan disusun oleh
ADIMAS BANJAR
M0107019
dibimbing oleh
Pembimbing I Pembimbing II
Drs. Siswanto, M.Si Dra. Respatiwulan, M.Si
NIP. 19670813 199203 1 002 NIP. 19680611 199302 2 001
telah dipertahankan di depan Dewan Penguji
pada hari Rabu, 8 Februari 2012
dan dinyatakan telah memenuhi syarat.
Anggota Tim Penguji Tanda Tangan
1. Drs. Pangadi, M.Si 1. ................................
NIP. 19571012 199103 1 001
2. Dra. Yuliana Susanti, M.Si 2. ................................
NIP. 19661007 199302 1 001
Surakarta, 10 Februari 2012
Disahkan oleh
Fakultas Matematika dan Ilmu Pengetahuan Alam
Dekan, Ketua Jurusan Matematika
Ir. Ari Handono Ramelan, M.Sc.(Hons) Ph.D Irwan Susanto, S.Si, DEA
NIP. 19610223 198601 1 001 NIP. 19710511 199512 1 001
ii
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
MOTO
Tidak ada mimpi yang dapat dicapai tanpa pengorbanan.
Setiap pengorbanan tidak ada yang sia-sia.
iii
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
ABSTRAK
Adimas Banjar. 2012. PERSAMAAN KARAKTERISTIK SUATUMATRIKSDALAM ALJABAR MAX PLUS . Fakultas Matematika dan Ilmu PengetahuanAlam. Universitas Sebelas Maret.
Aljabar max-plus dibentuk dari himpunan Rmax = {−∞} ∪R yang dileng-kapi dengan operasi maksimum (⊕) dan penjumlahan (⊗). Aljabar max-plus
merupakan suatu idempotent semi-field. Sedangkan aljabar konvensional adalahhimpunan R yang dilengkapi penjumlahan (+) dan perkalian (×) dan meru-pakan suatu field. Aljabar max-plus mempunyai struktur yang mirip denganaljabar konvensional menyebabkan sifat dan konsep aljabar linear mempunyaiekuivalensi dalam aljabar max-plus. Penelitian ini dilaksanakan guna menen-tukan persamaan karakteristik suatu matriks dalam aljabar max-plus. Hasil daripenelitian ini adalah persamaan karakteristik dalam aljabar max-plus, yaitu
λ⊗n ⊕⊕
k∈ℓ
dk ⊗ λ⊗n−k =⊕
k∈
dk ⊗ λ⊗n−k,
dengan dk adalah koefisien tertinggi untuk setiap λ⊗n−k
.
Kata kunci: Aljabar max-plus, aljabar linear, persamaan karakteristik
iv
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
ABSTRACT
Adimas Banjar. 2012. CHARACTERISTIC EQUATION ON MAX PLUSALGEBRAIC MATRICES Faculty of Mathematics and Natural Sciences, SebelasMaret University.
Max-plus algebra is constructed by the set Rmax = R ∪ {−∞} endowed withmaximum (⊕) and addition (⊗) operations. Max-plus algebra have propertiesas idempotent semi-field. In other hand, the properties of conventional algebrathat constructed by the set of R endowed with addition (+) and multiplication(×) operations is a field. There is exist remarkable similarity between max-plusalgebra and conventional algebra, as consequence there is many linear algebraconcept have a max-plus analogue. The main objective of this research is to findcharacteristic equation on max-algebraic matrices. Method of this research is aliterary study. Result of this research are max-algebraic characteristic equation,that is
λ⊗n ⊕⊕
k∈ℓ
dk ⊗ λ⊗n−k =⊕
k∈
dk ⊗ λ⊗n−k,
where dk are the highest coefficient from λ⊗n−k
Key words: Max-plus algebra, linear algebra, characteristic polynomial
v
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
PERSEMBAHAN
Tulisanku ini kupersembahkan untuk
kedua orang tuaku Bapak Haryono dan Ibu Indrasti Nur Rahayu atas
pengorbanan, do’a, bimbingan, dan dukungannya kepadaku
Mbak Enya dan Mas Omman yang selalu menyemangati dan memberikanku
motivasi,
adik-adikku Zulva, Aziza, Ayyub, Wi’am, Kun-Kun, Wicak, dan Wibi yang
telah memberikanku semangat.
vi
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
KATA PENGANTAR
Aljabar max-plus adalah salah satu dari idempotent semi-field yang memi-
liki banyak kegunaan di berbagai bidang matematika. Aljabar max-plus mulai
dikenal karena strukturnya yang mirip dengan aljabar konvensional. Banyak
penelitian yang menjelaskan tentang ekuivalensi teorema dalam aljabar linear
konvensional di aljabar max-plus. Satu yang menarik perhatian penulis adalah
karya Schutter dan Moor yang membahas tentang persamaan karakteristik su-
atu matriks dalam aljabar max-plus. Oleh karena itu, penulis bertujuan untuk
mengkaji ulang hasil penelitian tersebut.
Skripsi ini dibagi menjadi 5 bagian. Bab 1 berisikan latar belakang masalah,
rumusan masalah, tujuan, dan manfaat dari penelitian ini. Pada bab 2 di-
paparkan tentang penelitian-penelitian yang mendahului dan teori-teori penun-
jang sebagai dasar penulisan. Kemudian, langkah-langkah penelitian dirangkum
dalam metodologi penelitian yang dipaparkan pada bab 3. Pada bab 4 diuraikan
tentang hasil penelitian yang telah dilaksanakan. Terakhir, bab 5 berisikan ten-
tang kesimpulan dan saran.
Skripsi ini tidak dapat selesai tanpa adanya bantuan dari berbagai pihak.
Penulis mengucapan terima kasih kepada Bapak Drs. Siswanto, M.Si. dan
Ibu Dra. Respatiwulan, M.Si. sebagai Pembimbing I dan Pembimbing II atas
bimbingannya selama penulisan skripsi ini. Tak lupa, penulis juga mengucapkan
terima kasih kepada Nugroho, Gery, Adi, Agus, Ika, dan Hokki yang senanti-
asa memberikan dukungan, kritik, dan saran kepada penulis. Penulis berharap
skripsi ini dapat bermanfaat.
Surakarta, Januari 2012
Penulis
vii
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
DAFTAR ISI
HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
HALAMAN PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . . ii
MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
DAFTAR NOTASI DAN SIMBOL . . . . . . . . . . . . . . . . . . . . x
I PENDAHULUAN 1
1.1 Latar Belakang Masalah . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Manfaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
II LANDASAN TEORI 3
2.1 Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Teori-Teori Penunjang . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Sistem Persamaan Linear dan Matriks . . . . . . . . . . . 5
2.2.2 Determinan Matriks . . . . . . . . . . . . . . . . . . . . . 6
2.2.3 Persamaan Karakteristik Suatu Matriks . . . . . . . . . . 7
2.2.4 Aljabar Max-Plus . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.5 Matriks dalam Aljabar max-plus . . . . . . . . . . . . . . . 11
viii
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
2.3 Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . . 12
IIIMETODE PENELITIAN 13
IVPEMBAHASAN 14
4.1 Persamaan Karakteristik Suatu Matriks dalam Aljabar max-plus . 14
4.2 Contoh Kasus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
V PENUTUP 21
5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
DAFTAR PUSTAKA 22
ix
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
DAFTAR NOTASI DAN SIMBOL
S ⊂ T : S adalah himpunan bagian dari T
R : himpunan bilangan real
Rm×n : matriks berukuran m× n dengan elemen R
In : matriks identitas berukuran n× n
Aαβ : submatriks dari A dengan elemen baris dinyatakan oleh α dan elemen
kolom yang dinyatakan oleh β
Ckn : himpunan seluruh subhimpunan dengan kerdinalitas k dari himpunan
{1, 2, . . . , n}
Pn : himpunan seluruh permutasi dari himpunan {1, 2, . . . , n}
f : D → T : fungsi dengan domain D dan kodomain T
≍ : ekuivalensi asimtotik
λ : nilai eigen dari suatu matriks A
⊕ : operasi penjumlahan aljabar max-plus
⊗ : operasi pergandaaan aljabar max-plus
ε : elemen identitas untuk ⊕; ε = −∞
x⊗r
: pangkat ke-r dari x dalam aljabar max-plus
En : matriks identitas berukuran n× n dalam aljabar max-plus
Rmax : R ∪ {−∞}
Rm×nmax : matriks berukuran m× n dengan elemen Rmax
x
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Bab I
PENDAHULUAN
1.1 Latar Belakang Masalah
Sistem kejadian diskrit (skd) adalah nama klasifikasi masalah sistem den-
gan sumber daya terbatas yang digunakan oleh beberapa pengguna demi men-
capai tujuan bersama. Contoh-contoh masalah skd antara lain adalah jaringan
transportasi, jaringan telekomunikasi, sistem antrian dengan kapasitas berhingga,
sistem produksi, dan berbagai masalah dengan sumber daya yang terbatas [10].
Dari masalah skd dapat dibentuk model matematika yang biasanya berbentuk
sistem persamaan non-linear. Mencari penyelesaian sistem persamaan non-linear
dengan metode penyelesaian sistem dinamik tidaklah mudah. Dalam perkemban-
gannya, menurut Schutter dan Boom [12] jika digunakan aljabar max-plus untuk
mempelajari sifat skd, maka diperoleh suatu model berbentuk sistem persamaan
linear. Masalah skd akan lebih mudah diselesiakan jika model berbentuk sistem
yang linear.
Skd merupakan sistem yang komponennya bekerja dalam suatu siklus, kare-
na tiap komponen harus menunggu hasil dari komponen lain yang berada dalam
sistem tersebut untuk bekerja. Muncul masalah bagaimana cara mengatur sis-
tem agar seluruh komponennya dapat memulai siklus bersamaan. Nilai eigen
mendeskripsikan waktu maksimal yang diperlukan satu komponen dalam sistem
untuk menyelesaikan kerjanya [5]. Mencari nilai eigen dalam aljabar max-plus
yang diperoleh dari model adalah cara menyelesaikan permasalahan tersebut [3].
Menurut Anton [1] jika A adalah suatu matriks berukuran n × n, maka nilai
eigen λ dapat diperoleh dengan mencari akar-akar yang tidak nol dari persamaan
det(λI − A) = 0. Persamaan tersebut disebut sebagai persamaan karakteristik
dari A.
1
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Menurut Bacelli [2], aljabar max-plus adalah himpunan R∪{−∞} bersama
dengan operasi maksimum (⊕) dan penjumlahan (⊗) yang menggantikan op-
erasi penjumlahan dan perkalian pada aljabar konvensional. Aljabar konvensional
merupakan field, sedangkan aljabar max-plus (Rmax,⊕,⊗) merupakan idempotent
semi-field. Karena kemiripan strukturnya, berbagai sifat dan konsep pada aljabar
linear, seperti aturan Crammer, teorema Cayley-Hamilton, masalah nilai eigen,
dan persamaan karakteristik memiliki ekuivalensi secara aljabar max-plus [7].
Penelitian yang telah dilaksanakan Schutter dan Boom menjelaskan men-
genai sistem persamaan linear dalam aljabar max-plus [10]. Kemudian, Schutter
dan Moor pada [11] dan Farlow pada [7] menunjukkan bagaimana menentukan
persamaan karakteristik dari suatu matriks dalam aljabar max-plus. Sejalan den-
gan kedua penelitian tersebut, penulisan skripsi ini bertujuan untuk mengkaji
ulang tulisan Schutter dan Moor dan Farlow tentang persamaan karakteristik
dalam aljabar max-plus dengan memberikan penyempurnaan penjelasan, bukti
teorema, dan contoh kasus.
1.2 Perumusan Masalah
Berdasarkan latar belakang masalah, dapat dirumuskan masalah yaitu
bagaimana menentukan persamaan karakteristik suatu matriks dalam aljabar
max-plus?
1.3 Tujuan
Tujuan dari penulisan skripsi ini adalah menentuan persamaan karakteris-
tik suatu matriks dalam aljabar max-plus.
1.4 Manfaat
Manfaat penulisan skripsi ini adalah pengayaan di bidang aljabar, khusus-
nya aljabar max-plus, yaitu dapat menentukan persamaan karakteristik suatu
matriks dalam aljabar max-plus.
2
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Bab II
LANDASAN TEORI
Bab kedua skripsi ini terbagi menjadi tiga bagian. Bagian pertama dije-
laskan mengenai tinjauan pustaka penelitian-penelitian yang dilaksanakan dan
digunakan sebagai dasar dilaksanakannya penelitian ini. Pada bagian kedua di-
jelaskan mengenai teori-teori penunjang yang meliputi definisi-definisi yang di-
gunakan dalam pembahasan selanjutnya. Setelah dijelaskan mengenai landasan
teori yang digunakan, pada bagian terakhir bab ini dibangun alur pemikiran
dalam penulisan skripsi ini yang dijelaskan dalam kerangka pemikiran.
2.1 Tinjauan Pustaka
Aljabar max-plus adalah salah satu jenis dari idempotent semi-field. Jenis
idempotent semi-field yang lain adalah aljabar min-plus. Operasi penjumlah-
an dalam himpunan tersebut adalah operasi minimum dengan elemen identitas
∞ [7]. Aljabar max-plus diperkenalkan oleh Klene pada papernya yang memba-
has tentang jaringan syaraf dan automata di tahun 1956 [8]. Dalam perkemban-
gannya, diketahui bahwa aljabar max-plus juga dapat digunakan untuk memo-
delkan, menganalisis, dan mengontrol beberapa subkelas sistem kejadian diskrit
(skd) [12]. Beberapa contoh skd tersebut adalah jaringan telekomunikasi, sistem
kontrol lalu lintas, sistem logistik, sistem transportasi, jaringan komputer, dan
sebagainya.
Karakteristik yang paling menonjol dari skd adalah dinamisasi sistem yang
berdasarkan atas kejadian. Kejadian adalah keadaan dari dimulainya hingga
berakhirnya suatu aktivitas. Misalkan dalam suatu proses produksi, kejadian
yang dapat terjadi antara lain adalah input, proses, dan output. Diasumsikan
bahwa jika satu kejadian selesai, maka kejadian selanjutnya akan langsung terjadi
3
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
dan interval tiap-tiap kejadian tidak harus sama.
Pada umumnya model matematika dari skd menghasilkan model yang non-
linear jika dideskripsikan menggunakan aljabar konvensional. Akan tetapi terda-
pat beberapa subkelas dari skd yang dapat dideskripsikan menggunakan aljabar
max-plus [2] yang dilengkapi dengan operasi maksimisasi dan penjumlahan se-
bagai operasi dasarnya, sehingga diperoleh model yang linear. Adapun subke-
las tersebut adalah skd dengan sinkronisasi tanpa adanya kejadian yang berca-
bang. Operasi hitung maksimisasi menggambarkan sinkronisasi komponen skd
yang akan langsung melaksanakan operasi setelah seluruh operasi komponen se-
belumnya selesai. Sedangkan operasi hitung penjumlahan menggambarkan durasi
dari seluruh aktivitas. Waktu penyelesaian operasi diperoleh dari penjumlahan
dari waktu dimulainya operasi dengan durasi aktivitas. Deskripsi tersebut menye-
babkan aljabar max-plus dapat menghasilkan model yang linear [12]. Hal inilah
yang menyebabkan aljabar max-plus mempunyai banyak kegunaan di berbagai
bidang.
Pada awal tahun enam puluhan fakta kegunaan aljabarmax-plus ditemukan
secara independen oleh beberapa peneliti, antara lain adalah Cunningham-Green
dan Giffler. Hal tersebut menyebabkan banyak peneliti mulai tertarik untuk
meneliti aljabar max-plus, adapun beberapa perintisnya adalah Cunningham-
Green, Gaubert, Gondran, dan Minoux. Mereka menemukan bahwa berbagai
teorema dan teknik yang digunakan dalam aljabar linear klasik mempunyai analo-
gi pada aljabar max-plus [6]. Bacelli [2] telah menjelaskan bagaimana pentingnya
nilai eigen suatu matriks pada aljabar max-plus. Dalam jurnalnya Bapat [3],
Chung [5], dan Butkovic [4] telah menjelaskan bagaimana menyelesaikan masalah
nilai eigen tersebut. Akan tetapi nilai eigen suatu matriks dapat pula diperoleh
dari persamaan karakteristik matriks tersebut [1]. Schutter dan Moor pada [11]
dan Farlow pada [7] telah menunjukkan analogi dari persamaan karakteristik pa-
da aljabar max-plus. Sejalan dengan kedua penelitian tersebut, penelitian ini
dilaksanakan bertujuan untuk mengkaji ulang kedua penelitian tersebut disertai
dengan penyempurnaan penjelasan, bukti teorema, dan contoh kasus.
4
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
2.2 Teori-Teori Penunjang
Untuk dapat mencapat tujuan penelitian, perlu diuraikan terlebih dahulu
beberapa hal yang mendasari penelitian ini. Beberapa hal tersebut antara lain
adalah pengertian aljabar max-plus, struktur aljabar max-plus, pengertian sistem
persamaan linear dan matriks dalam aljabar konvensional, matriks dalam aljabar
max-plus, dan terakhir adalah beberapa sifat dan konsep aljabar linear dalam
aljabar konvensional.
2.2.1 Sistem Persamaan Linear dan Matriks
Dua definisi yang berhubungan dengan sistem persamaan linear berikut diambil
dari Lipschutz [9].
Definisi 2.2.1 (Definisi Persamaan Linear). Bentuk umum dari suatu persamaan
linear dengan variabel bebas x1, x2, . . . , xn adalah
a1x1 + a2x2 + · · ·+ anxn = b,
dengan a1, a2, . . . , an, b adalah suatu konstanta. Konstanta ak disebut koefisien
dari xk untuk k = 1, 2, . . . , n. Sedangkan b disebut sebagai konstanta dari per-
samaan.
Definisi 2.2.2 (Definisi Sistem Persamaan Linear). Bentuk umum dari suatu
sistem persamaan linear dengan variabel bebas x1, x2, . . . , xn adalah
a11x1 + a12x2+ · · ·+ a1nxn = b1
a21x1 + a22x2+ · · ·+ a2nxn = b2
...
am1x1 + am2x2+ · · ·+ amnxn = bm
, (2.1)
dengan aij, bi adalah konstanta.
Sistem (2.1) dapat dibentuk menjadi suatu bentuk barisan angka yang dise-
5
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
but matriks perbesaran. Berikut adalah bentuk matriks perbesaran tersebut.
M =
a11 a12 · · · a1n b1
a21 a22 · · · a2n b2...
......
......
am1 am2 · · · amn bm
.
Dapat dilihat bahwa setiap baris dari M berkorespodensi dengan setiap per-
samaan dari sistem. Sedangkan, setiap kolom dalam sistem berkorespodensi den-
gan setiap variabel dari sistem, kecuali kolom terakhir yang berkorespodensi den-
gan konstanta dari sistem. Barisan angka tersebut biasa disebut sebagai matriks
dan berikut adalah definisi matriks.
Definisi 2.2.3 (Lipschutz [9]). Jika A adalah suatu barisan angka berbentuk
persegi empat sebagai berikut
A =
a11 a12 · · · a1n
a21 a22 · · · a2n...
......
...
am1 am2 · · · amn
,
maka barisan A disebut sebagai matriks. Matriks tersebut dapat dituliskan se-
bagai A = (aij) dengan i = 1, . . . , m, j = 1, . . . , n.
Ukuran dari suatu matriks ditentukan dari jumlah baris dan kolomnya. Se-
bagai contoh jika suatu matriks memiliki tiga baris dan dua kolom, maka ukuran
dari matriks tersebut adalah 3×2. Matriks dengan ukuran m×n disebut sebagai
matriks m× n.
2.2.2 Determinan Matriks
Menurut Anton [1], determinan adalah suatu fungsi yang bernilai real dari suatu
matriks persegi berukuran n misal A = (aij) dan dinotasikan sebagai det(A) atau
6
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
|A| atau ∣∣∣∣∣∣∣∣∣∣∣∣
a11 a12 · · · a1n
a21 a22 · · · a2n...
......
...
an1 an2 · · · ann
∣∣∣∣∣∣∣∣∣∣∣∣
.
Misal terdapat suatu matriks A = (aij) dengan i = 1, 2, . . . , n dan j =
1, 2, . . . , n, akan dibentuk suatu produk perkalian yang diambil dari n elemen
dari A. Dari masing-masing kolom dari matriks A diambil satu elemen. Selain
berasal dari kolom yang berbeda, elemen tersebut harus berasala dari baris yang
berbeda pula, sehingga hasil perkalian n elemen tersebut dapat dituliskan sebagai
a1j1a2j2 . . . anjn.
Indeks angka pertama diperoleh dari baris, sehingga urutannya adalah 1, 2, . . . , n.
Sedangkan untuk indeks angka kedua diperoleh dari kolom yang berbeda, sehing-
ga diperoleh dari permutasi σ = j1, j2, . . . , jn ∈ Sn.
Definisi 2.2.4. Determinan dari A = (aij) yang dinotasikan sebagai det(A) atau
|A| adalah suatu jumlahan seluruh hasil permutasi dari Sn dan dikalikan dengan
sgn σ, yaitu
|A| =∑
σ∈Sn
(sgn σ)a1σ(1)a2σ(2) · · ·anσ(n).
Dengan sgn σ adalah
sgn σ =
1, jika σ permutasi genap;
−1, jika σ permutasi ganjil.
2.2.3 Persamaan Karakteristik Suatu Matriks
Jika dimisalkan A adalah suatu matriks persegi berukuran n× n, maka matriks
karakteristik dari A adalah matriks λIn − A dengan In adalah matriks identitas
berukuran n dan λ adalah variabel bebas. Matriks karateristik dari A dapat
7
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
dituliskan sebagai
λIn −A =
λ− a11 −a12 · · · −a1n
−a21 λ− a22 · · · −a2n...
......
...
−an1 −an2 · · · λ− ann
.
Dengan mencari determinan dari matriks karakteristik dari A, diperoleh suatu
polinomial, yaitu
∆A(λ) = det(λIn −A).
Polinomial ∆A(λ) adalah polinomial yang disebut sebagai polinomial karak-
teristik dari A. Kemudian, persamaan karakteristik dari A adalah
∆A(λ) = det(λIn −A) = 0.
2.2.4 Aljabar Max-Plus
Pada bagian ini dijelaskan lebih lanjut mengenai struktur, sifat-sifat, dan beber-
apa operasi dasar dalam aljabar max-plus. Dalam penelitiannya, Bacelli [2] dan
Siswanto [13] telah membahas beberapa definisi yang berkaitan dengan struktur
aljabar max-plus.
Definisi 2.2.5 (Definisi Monoid). Monoid (K, ∗) adalah himpunan K bersama
dengan operasi biner (∗), yang memiliki sifat asosiatif dan elemen identitas.
Definisi 2.2.6 (Definisi Grup). Grup (G, ∗) adalah himpunan G bersama dengan
operasi biner (∗), yang memiliki sifat asosiatif, elemen identitas, dan elemen
invers.
Definisi 2.2.7 (Definisi Semi-ring). Semi-ring (S,⊕,⊗) adalah himpunan S ber-
sama dengan operasi biner ⊕ membentuk monoid abelian, dengan operasi biner
⊗ membentuk monoid, bersifat distributif pada ⊗ terhadap ⊕.
Definisi 2.2.8 (Definisi Dioid). Dioid (D,⊕,⊗) adalah semi-ring yang idempo-
tent, yaitu a⊕ a untuk setiap a ∈ D.
8
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Definisi 2.2.9 (Definisi Semi-field). Semi-field (S,⊕,⊗) adalah himpunan S
bersama dengan operasi penjumlahan ⊕ membentuk monoid abelian, dengan
operasi pergandaan ⊗ membentuk grup, bersifat distributif pada ⊗ terhadap ⊕.
Aljabar max-plus atau (Rmax,⊕,⊗) adalah suatu semi-field yang dibentuk
oleh himpunan Rmax = R ∪ {−∞} yang dilengkapi dengan operasi max sebagai
operasi penjumlahan ⊕ dan operasi plus sebagai operasi pergandaan ⊗ yang
dituliskan sebagai berikut
a⊕ b = max(a, b) a⊗ b = a + b.
Berikut adalah contoh penggunaan operasi hitung tersebut.
3⊕ 2 = max(3, 2) = 3 = max(2, 3) = 2⊕ 3,
4⊗ 5 = 4 + 5 = 9 = 5 + 4 = 5⊗ 4.
Elemen identitas terhadap operasi pergandaan ⊗ adalah e = 0. Sedangkan ele-
men identitas terhadap operasi penjumlahan ⊕ adalah ε = −∞. Selanjutnya,
sifat-sifat dasar dari aljabar max-plus dijelaskan pada Lema 2.2.1. Karena pem-
buktian bersifat dasar sehingga tidak disertakan.
Lema 2.2.1. Untuk setiap x, y, z ∈ Rmax berlaku sifat
1. assosiatif x⊕ (y ⊕ z) = (x⊕ y)⊕ z dan x⊗ (y ⊗ z) = (x⊗ y)⊗ z,
2. komutatif x⊕ y = y ⊕ x dan x⊗ y = y ⊗ x,
3. distributif x⊗(y⊕z) = (x⊗y)⊕(x⊗z) dan (x⊕y)⊗z = (x⊗z)⊕(y⊗z)
4. elemen nol x⊕ ε = ε⊕ x = x
5. elemen unit x⊗ e = e⊗ x = x
6. invers terhadap pergandaan adalah jika x 6= e maka akan terdapat elemen
y yang tunggal dengan x⊗ y = e
7. elemen penyerap x⊗ ε = ε⊗ x = ε
8. idempotent terhadap penjumlahan x⊕ x = x.
9
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Aljabar max-plus juga dikenal sebagai aljabar dari fungsi dengan pertum-
buhan asiptotik dalam aljabar konvensional. Untuk memperjelas hal tersebut,
diberikan definisi dan lema berikut.
Definisi 2.2.10. Jika p : (0,∞) → (0,∞) dan u ∈ (−∞,∞), maka didefinisikan
p ≍ esu yang berarti lims→∞ s−1ln(p) = u.
Lema 2.2.2. Jika f ≍ esa dan g ≍ esb dengan a, b ∈ [−∞,∞), maka
f + g ≍ es(a⊕b) dan fg ≍ es(a⊗b)
Bukti. Jika digunakan Definisi 2.2.10 pada fg maka diperoleh
lims→∞
s−1 ln(fg) = lims→∞
s−1 ln(f) + lims→∞
s−1 ln(g) = a + b = a⊗ b,
yang berarti terbukti bahwa fg ≍ es(a⊗b). Kemudian, dapat diketahui bahwa
max(f, g) ≤ f + g ≤ 2max(f, g). Jadi, jika digunakan kembali Definisi 2.2.10
maka diperoleh
lims→∞
s−1 ln(max(esa, esb)
)≤ lim
s→∞
s−1 ln(esa+esb) ≤ lims→∞
s−1(ln(max(esa, esb)
)+ ln 2
).
Karena s−1 ln(max(esa, esb)
)= max(a, b), dan dengan menggunakan teorema apit,
diperoleh bahwa
lims→∞
s−1 ln(f + g) = max(a, b) = a⊕ b.
Jika Definisi 2.2.10 dan Lema 2.2.2 digunakan pada fungsi eksponensial esa
dan esb akan diperoleh operasi ⊕ dan ⊗ sebagai berikut
esaesb ≍ es(a⊗b)
esa + esb ≍ es(a⊕b).
Hubungan aljabar max-plus dengan aljabar konvensional tersebut sering digu-
nakan untuk membuktikan sifat-sifat dalam aljabar max-plus.
10
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
2.2.5 Matriks dalam Aljabar max-plus
Berikut adalah definisi matriks dalam aljabar max-plus sebagaimana telah
dijelaskan oleh Farlow dalam [7].
Definisi 2.2.11 (Definisi Matriks dalam Aljabar Max-Plus). Himpunan matriks
berukuran m × n dengan elemen-elemen Rmax dinotasikan dengan Rm×nmax . Him-
punan tersebut dapat dituliskan sebagai
Rm×nmax =
a11 a12 · · · a1n
a21 a22 · · · a2n...
......
...
am1 am2 · · · amn
∣∣∣∣∣aij ∈ Rmax
.
Elemen baris ke-i dan kolom ke-j dari matriks A ∈ Rm×nmax dinyatakan oleh
aij atau dapat ditulis sebagai [A]ij .
Selanjutnya dijelaskan mengenai operasi matriks dalam aljabar max-plus.
Definisi-definisi berikut diacu dari Farlow [7] dan Siswanto [13].
Definisi 2.2.12 (Operasi Hitung dari Matriks dalam Aljabar Max-Plus).
1. Untuk setiap A,B ∈ Rm×nmax , definisi penjumlahan A⊕B adalah
[A⊕ B]ij = aij ⊕ bij = max(aij , bij).
2. Untuk setiap A ∈ Rm×kmax dan B ∈ R
k×nmax, definisi pergandaan A⊗B adalah
[A⊗B]il =k⊕
j=1
(aij ⊗ bjl) = maxj∈{1,2,...}
(aij + bjl).
3. Transpose dari matriks dituliskan sebagai AT dan didefinisikan seperti dalam
aljabar konvensional, yaitu
[AT ]ij = [A]ji.
11
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
4. Untuk matriks berukuran n× n dalam aljabar max-plus memiliki identitas
En yang didefinisikan sebagai
[En]ij =
e, jika i = j;
ε, jika i 6= j,
dengan ε adalah elemen identitas dari operasi max yaitu −∞ sedangkan e
adalah elemen identitas dari operasi penjumlahan yaitu 0.
5. Untuk suatu matriks A ∈ Rn×nmax dan bilangan bulat positif k, pangkat k dari
A dituliskan sebagai A⊗k dan didefinisikan dengan
A⊗k =A⊗ A⊗ . . .⊗ A︸ ︷︷ ︸
k kali.
Untuk k = 0, berlaku A⊗0 = En.
6. Untuk sebarang matriksA ∈ Rn×nmax dan α ∈ Rmax, operasi α⊗A didefinisikan
dengan
[α⊗ A]ij = α⊗ [A]ij.
2.3 Kerangka Pemikiran
Berdasarkan tinjauan pustaka dapat disusun suatu kerangka pemikiran
langkah-langkah penyelesaian masalah dalam penulisan skripsi ini. Pertama,
akan dipahami terlebih dahulu mengenai struktur aljabar max-plus. Kedua, di-
lanjutkan dengan memahami tentang sistem persamaan linear aljabar max-plus
dan bagaimana membuat suatu matriks dari sistem tersebut. Ketiga, memaha-
mi konsep-konsep aljabar linear dalam aljabar max-plus, khususnya determinan
matriks dalam aljabar max-plus. Setelah memahami determinan matriks dalam
aljabar max-plus barulah dapat ditentukan persamaan karakteristik dari suatu
matriks. Kemudian, untuk memperjelas pembahasan, akan diberikan contoh ka-
sus mengenai penentuan persamaan karakteristik dari suatu matriks.
12
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Bab III
METODE PENELITIAN
Metode penelitian yang dilakukan dalam penulisan skripsi ini adalah ka-
jian pustaka, yaitu dengan mengumpulkan berbagai referensi buku, skripsi, jur-
nal, maupun informasi dari halaman websites mengenai struktur aljabar, aljabar
max-plus, sifat-sifat aljabar linear, dan sistem persamaan linear aljabar max-plus.
Dari metode tersebut, diharapkan dapat dikaji ulang bagaimana penentuan per-
samaan karakteristik dari suatu matriks dalam aljabar max-plus dan kemudian
memberikan contoh penerapannya dalam contoh kasus.
Berikut adalah langkah-langkah yang dilakukan dalam penulisan skripsi ini.
1. Menerapkan persamaan karakteristik suatu matriks dalam aljabar konven-
sional,
2. menerapkan sistem persamaan linear dalam bentuk matriks pada aljabar
max-plus,
3. menentukan persamaan karakteristik suatu matriks dalam aljabarmax-plus,
dan
4. memberikan contoh kasus berupa model dari jalur kereta api sederhana
yang diambil dari Vries [14].
13
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Bab IV
PEMBAHASAN
Pada bab ini diberikan hasil studi dan pembahasan. Bab ini terdiri dari dua
bagian. Pada bagian pertama akan dijelaskan tentang bagaimana cara mengkons-
truksikan persamaan karakteristik suatu matriks dalam aljabar max-plus. Kemu-
dian, akan diberikan contoh kasus tentang jaringan kereta api sederhana pada
bagian yang kedua.
4.1 Persamaan Karakteristik Suatu Matriks dalam
Aljabar max-plus
Sebelum membahas persamaan karakteristik dalam aljabar max-plus, ter-
lebih dahulu didefinisikan persamaan karakteristik suatu matriks dalam aljabar
konvensional. Jika A adalah suatu matriks berukuran n×n dan ϕ ⊂ {1, 2, . . . n},
maka Aϕϕ adalah submatriks yang diperoleh dengan menghapus seluruh baris
dan kolom dari A kecuali elemen dari baris dan kolom yang dinyatakan oleh ϕ.
Kemudian, persamaan karakteristik suatu matriks adalah
det(λI − A) = λn + c1λn−1 + . . .+ cn−1λ+ cn = 0 (4.1)
untuk ck = (−1)k∑
σ∈Ckn
det(Aσσ) dengan Ckn adalah himpunan dari seluruh sub-
himpunan k elemen dari himpunan {1, 2, . . . , n}. Karena dalam aljabar max-plus
tidak didefinisikan operasi pengurangan, koefisien ckλn−k dari persamaan (4.1)
yang bertanda negatif dipindahkan ke ruas kanan. Sifat-sifat dari permutasi di-
gunakan untuk memisahkan antara koefisien ckλn−k yang bernilai positif.
Digunakan pendekatan melalui fungsi eksponensial, yaitu matriks esA
untuk menentukan analogi persamaan karakteristik dalam aljabar max-plus. Jika
14
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
matriks esA disubstitusikan pada persamaan (4.1), maka diperoleh
det(λI − esA) = λn + γ1λn−1 + . . .+ γn−1λ+ γn = 0, (4.2)
dengan γk(s) = (−1)k∑
σ∈Ckn
det(esAσσ).
Didefinisikan Γk = {ζ : ∃{i1, i2, . . . , ik} ∈ Ckn, ∃ρ ∈ Pk sedemikian se-
hingga ζ =∑k
r=1 airiρ(r)} untuk k = 1, 2, . . . , n dengan Pn adalah himpunan selu-
ruh permutasi σ : {1, 2, . . . , n} → {1, 2, . . . , n}. Nilai Γk merupakan himpunan
pangkat dari esζ yang terjadi pada γk(s). Jika didefinisikan Ik(ζ) adalah koefisien
dari esζ untuk setiap ζ ∈ Γk dengan k ∈ 1, 2, . . . , n, maka Ik(ζ) = Iek(ζ)− Iok(ζ)
dengan
1. Iek(ζ) adalah nilai dari ρ ∈ P ek sedemikian sehingga {i1, i2, . . . , in} ∈ Ck
n dan
ζ =∑k
r airiρ(r),
2. Iok(ζ) adalah nilai dari ρ ∈ P ok sedemikian sehingga {i1, i2, . . . , in} ∈ Ck
n dan
ζ =∑k
r airiρ(r),
untuk P en sebagai permutasi genap dan P o
n sebagai permutasi ganjil.
Nilai Ik(ζ) disubstitusikan pada γk(s) dan diperoleh
γk(s) = (−1)k∑
ζ∈Γk
Ik(s)esζ. (4.3)
Didefinisikan dominan dari γk(s) adalah
dk = max{ζ ∈ Γk : Ik(ζ) 6= 0}.
Jika digunakan Definisi 2.2.10 pada persamaan (4.3), maka diperoleh
|γk(s)| ≍ esdk .
Kemudian didefinisikan nilai koefisien dari γk(s) sebagai γ̄k(s) = (−1)kIk(dk)
untuk k = 1, 2, . . . , n. Misal ℓ = {k : γ̄k(s) > 0} dan = {k : γ̄k(s) < 0}, agar
dapat memisahkan koefisien yang positif dengan negatif. Sebagai contoh untuk
setiap ζ ∈ Γ1 = {aii : i = 1, 2, . . . , n} diketahui bahwa Io1(ζ) = 0 dan Ie1(ζ) > 0.
Hal ini menyebabkan I1(d1) > 0 sehingga γ̄1 < 0 yang berarti 1 ∈ . Sejalan
15
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
dengan Γ1 seluruh γk(s) dengan γ̄k(s) < 0 atau k ∈ dipindah ke ruas kanan
agar tanda negatif dapat dihilangkan. Seluruh γk(s) dengan k ∈ dipindahkan
ke ruas kanan dan diperoleh
λn +∑
k∈ℓ
γ̄k(s)esdkλn−k =
∑
k∈
γ̄k(s)esdkλn−k. (4.4)
Kemudian, agar Lema 2.2.2 dapat digunakan, variabel λ pada persamaan
(4.4) diganti dengan variabel esλ dan diperoleh
esλn
+∑
k∈ℓ
γ̄k(s)esdkesλ
n−k
≍∑
k∈
γ̄k(s)esdkesλ
n−k
esλn
+∑
k∈ℓ
γ̄k(s)esdkλ
n−k
≍∑
k∈
γ̄k(s)esdkλ
n−k
Jika digunakan Definisi 2.2.10, maka diperoleh
lims→∞
s−1 ln(esλ
n
+∑
k∈ℓ
γ̄k(s)es(dkλ
n−k))= lim
s→∞
s−1 ln(∑
k∈
γ̄k(s)es(dkλ
n−k))
(4.5)
Kemudian, digunakan Lema 2.2.2 pada persamaan (4.5) dan diperoleh
maxk∈ℓ
(nλ, dk +
((n− k)λ
)+ ln
(γ̄k(s)
))= max
k∈
(dk +
((n− k)λ
)+ ln
(γ̄k(s)
)).
Karena ln(γ̄k(s)
)dapat diabaikan, persamaan karakteristik suatu matriks dalam
aljabar max-plus adalah
λ⊗n ⊕⊕
k∈ℓ
dk ⊗ λ⊗n−k =⊕
k∈
dk ⊗ λ⊗n−k (4.6)
4.2 Contoh Kasus
Kasus berikut diambil dari penelitian yang telah dilaksanakan oleh Vries et.
al [14]. Misalkan diketahui suatu jaringan rel kereta api sederhana seperti yang
dapat dilihat pada Gambar 4.1. Pada jaringan tersebut, terdapat rute kereta dari
P menuju ke S dan sebaliknya yang melewati stasiun Q. Selain itu terdapat rute
dari stasiun Q ke R dan sebaliknya. Pada stasiun Q kereta dari P dan S harus
mendahulukan kereta yang berjalan pada rute Q ke R dan sebaliknya.
Waktu keberangkatan dari kereta ke-k pada rute i dinotasikan sebagai xi(k),
untuk i = 1, 2, . . . , n dengan n adalah jumlah rute yang berbeda pada jaringan.
16
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Gambar 4.1. Jaringan rel kereta api sederhana.
Kereta ke-(k + 1) harus memenuhi beberapa kondisi untuk dapat berjalan pada
rute i. Kondisi pertama adalah kereta harus telah tiba di stasiun. Dianggap
bahwa kereta dari rute j akan melanjutkan perjalanan melewati rute i, sehingga
diperoleh kondisi berikut.
xi(k + 1) ≥ aij ⊗ xj(k), (4.7)
dengan xi(k + 1) adalah waktu keberangkatan ke-(k + 1) pada rute i dan aij
adalah waktu tempuh yang diperlukan untuk melewati rute j ke i ditambah
dengan waktu yang diperlukan penumpang untuk turun dan naik dari kereta.
Kondisi kedua adalah setiap kereta dapat menunggu kereta lain yang berhu-
bungan. Hal tersebut menyebabkan munculnya kondisi berikut.
xi(k + 1) ≥ ail ⊗ xl(k), (4.8)
untuk l adalah himpunan seluruh rute sebelum i dengan ail adalah waktu tempuh
pada rute l ke i ditambah dengan waktu yang diperlukan penumpang untuk turun
dan naik dari kereta.
Diasumsikan bahwa kereta langsung berangkat jika seluruh kondisi telah
dipenuhi. Waktu keberangkatan kereta ke-(k + 1) pada rute i yang dituliskan
dalam aljabar max-plus adalah
xi(k + 1) = aij(k)⊗ xj(k)⊕⊕
l
ail(k)xl(k).
Sehingga, model dari jaringan pada Gambar 4.1 dengan memperhatikan kondisi
17
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
(4.7) dan (4.8) adalah sebagai berikut
x1(k + 1) = a2(k)⊗ x2(k)
x2(k + 1) = a3(k)⊗ x3(k)⊕ a4(k)⊗ x4(k)
x3(k + 1) = a1(k)⊗ x1(k)⊕ a3(k)⊗ x3(k)⊕ a4(k)⊗ x4(k)
x4(k + 1) = a1(k)⊗ x1(k)⊕ a3(k)⊗ x3(k).
Jika dimisalkan x(k) =(x1(k), . . . , xi(k), . . . , xn(k)
)T, maka model dapat dit-
uliskan menjadi x(k+1) = A(k)⊗x(k) dengan A(k) adalah suatu matriks, yaitu
A(k) =
ε a2 ε ε
ε ε a3 a4
a1 ε a3 a4
a1 ε a3 ε
. (4.9)
Jika waktu tempuh ai(k) deterministik dengan satuan waktu, maka perilaku
sistem x(k + 1) = A(k) ⊗ x(k) ditentukan oleh nilai eigen dalam aljabar max-
plus dari matriks A(k). Menurut Chung [5], nilai eigen adalah nilai besarnya
waktu maksimal yang diperlukan kereta untuk dapat melewati rute manapun
yang ada dalam jaringan tersebut. Dalam artikel ini hanya dibahas bagaimana
cara mencari persamaan karakteristik dari matriks A tersebut.
Jika dimisalkan a1 = 14, a2 = 17, a3 = 11, a4 = 9, maka nilai a1, a2, a3, a4
disubstitusikan pada matriks (4.9) dan diperoleh matriks A berikut
A =
ε 17 ε ε
ε ε 11 9
14 ε 11 9
14 ε 11 ε
.
Kemudian, akan dicari persamaan karakteristik dari matriks A. Persamaan
karakteristik dari matriks A akan dicari dengan dua cara. Cara pertama adalah
memperoleh persamaan karakteristik dengan menggunakan matriks esA. Sedan-
gkan cara kedua adalah dengan menggunakan persamaan (4.6).
18
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Pertama akan digunakan matriks esA untuk memperoleh persamaan karak-
teristik dari matriks A. Berikut adalah matriks esA.
esA =
0 e17s 0 0
0 0 e11s e9s
e14s 0 e11s e9s
e14s 0 e11s 0
Kemudian, jika matriks esA disubstitusikan ke dalam persamaan (4.1), maka
diperoleh
det(λI − esA) = λ4 − e11sλ3 − e20sλ2 +−(e42s + e40s)λ− e51s = 0 (4.10)
Koefisien dengan pangkat tertinggi dari seluruh γk mempunyai tanda negatif.
Oleh karena itu, seluruh γk dipindahkan ke ruas kanan. Jika hanya diambil
pangkat terbesar dari γk, maka diperoleh persamaan (4.11), yaitu
λ4 = e11sλ3 + e31sλ2 + e42sλ+ e51s. (4.11)
Jika nilai λ diganti dengan esλ dan digunakan Definisi 2.2.10 pada persamaan
(4.12), maka diperoleh
lims→∞
s−1(esλ
4)= lim
s→∞
s−1(e11sesλ
3
+ e31sesλ2
+ e42sesλ + e51s)
(4.12)
Kemudian, jika digunakan Lema 2.2.2, maka diperoleh persamaan karakteristik
dari matriks A adalah
λ⊗4
= 11⊗ λ⊗3
⊕ 31⊗ λ⊗2
⊕ 42⊗ λ⊕ 51. (4.13)
Kemudian, jika digunakan persamaan (4.6) untuk menentukan persamaan
karakteristik dari matriks A, berikut adalah langkah-langkah penyelesaiannya.
Dengan menggunakan definisi Γk untuk i = 1, 2, 3, 4, diperoleh Γ1 = {ε, 11},
Γ2 = {ε, 20}, Γ3 = {ε, 40, 42}, dan Γ4 = {ε, 51}. Kemudian berikut adalah nilai
Ik(ζ) untuk k = 1, 2, 3, 4.
I1(ε) = 1, I1(11) = 1
I2(ε) = −4, I2(20) = −1
I3(ε) = −10, I3(40) = 1, I3(42) = −2
I4(ε) = −5, I4(51) = −1.
19
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Kemudian dicari dk untuk k = 1, 2, 3, 4. Karena max{Γ1} = 11 dan I1(11) 6= 0,
diperoleh d1 = 11. Dengan cara yang sama, diperoleh d2 = 20, d3 = 42, dan
d4 = 51. Hal tersebut menyebabkan γ̄1 = −1, γ̄2 = −1, γ̄3 = −1, dan γ̄4 = −1.
Diperoleh ℓ = {} dan = {1, 2, 3, 4}. Persamaan karakteristik dari matriks A
dengan memperhatikan persamaan (4.6) adalah
λ⊗4
= 11⊗ λ⊗3
⊕ 31⊗ λ⊗2
⊕ 42⊗ λ⊕ 51. (4.14)
Tampak bahwa persamaan (4.13) dan (4.14) sama. Sehingga terbukti bah-
wa dengan menggunakan det(λI − esA) ataupun persamaan (4.6) diperoleh hasil
sama. Mencari persamaan karakteristik menggunakan det(λI− esA) masih mem-
butuhkan penggunaan operasi (+) dan (×) pada aljabar konvensional, sehingga
tidak efektif. Sedangkan, pada persamaan (4.6) hanya menggunakan operasi
dalam aljabar max-plus.
Kemudian, nilai eigen dari matriks A dapat diperoleh dengan memfak-
torkan persamaan karakteristik tersebut. Dari nilai eigen yang diperoleh terse-
but, misalkan λ dapat diartikan bahwa kereta dalam jaringan tersebut dapat
diberangkatkan tiap λ satuan waktu.
20
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
Bab V
PENUTUP
5.1 Kesimpulan
Sesuai dengan masalah yang telah dirumuskan, diperoleh kesimpulan per-
samaan karakteristik suatu matriks dalam aljabar max-plus adalah
λ⊗n ⊕⊕
k∈ℓ
dk ⊗ λ⊗n−k =⊕
k∈
dk ⊗ λ⊗n−k,
dengan
dk = max{ζ ∈ Γk : Ik(ζ) 6= 0}.
Nilai Γk adalah himpunan pangkat yang mungkin terjadi untuk setiap λ dan Ik(ζ)
adalah koefisien dari ζ ∈ Γk.
5.2 Saran
Penelitian ini hanya membahas tentang bagaimana menentukan persamaan
karakteristik suatu matriks dalam aljabar max-plus. Jika pembaca tertarik da-
pat melakukan penelitian tentang bagaimana cara memperoleh algoritma untuk
memperoleh nilai eigen dan vektor eigen dari persamaan karakteristik.
21