perpustakaan.uns.ac.id
digilib.uns.ac.id
NILAI EIGEN DAN VEKTOR EIGEN MATRIKS TERREDUKSI DALAM ALJABAR MAKS-PLUS BESERTA APLIKASINYA
oleh
BUDI AGUNG PRASOJO M0105001
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 2013
commit to user i
perpustakaan.uns.ac.id
digilib.uns.ac.id
SKRIPSI
NILAI EIGEN DAN VEKTOR EIGEN MATRIKS TERREDUKSI DALAM ALJABAR MAKS-PLUS BESERTA APLIKASINYA yang disiapkan dan disusun oleh BUDI AGUNG PRASOJO NIM. M0105001 dibimbing oleh Pembimbing I,
Pembimbing II,
Drs. Siswanto, M.Si NIP. 19670813 199203 1 002
Supriyadi Wibowo, M.Si NIP. 19681110 199512 1 001
telah dipertahankan didepan Dewan Penguji Pada hari Kamis, tanggal 21 Maret 2013 dan dinyatakan telah memenuhi syarat. Anggota Tim Penguji
Tanda Tangan
1. Drs. Santoso B. W., M. Si
1. . . . . . . . . . . . . . .
2. Irwan Susanto, S. Si, DEA
2. . . . . . . . . . . . . . .
Surakarta, 21 Maret 2013
Disahkan oleh Fakultas Matematika dan Ilmu Pengetahuan Alam Dekan,
Ketua Jurusan Matematika
Prof. Ari Handono Ramelan, M.Sc, Ph.D NIP. 19610223 198601 1 001
Irwan Susanto, S. Si, DEA NIP. 19710511 199512 1 001
commit to user ii
perpustakaan.uns.ac.id
digilib.uns.ac.id
MOTO
Awali segala kegiatan dengan Basmalah dan diakhiri dengan Hamdalah.
Dibalik kesulitan pasti ada kemudahan.
commit to user iii
perpustakaan.uns.ac.id
digilib.uns.ac.id
PERSEMBAHAN
Tulisanku ini kupersembahkan untuk 1. Kedua orang tuaku Mardjono dan Darti sudiarti atas pengorbanan, doa, bimbingan, dan dukungannya kepadaku, 2. Seluruh keluarga yang selalu menyemangati dan memberi motivasi kepadaku, 3. Teman-temanku egi, agus yulianto, dimas b, dan semuanya yang terus memberi dukungan, semangat, dan masukan kepadaku.
commit to user iv
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRAK Budi Agung Prasojo. 2013. NILAI EIGEN DAN VEKTOR EIGEN MATRIKS TERREDUKSI DALAM ALJABAR MAKS-PLUS BESERTA APLIKASINYA. Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sebelas Maret. Aljabar maks-plus yang dinotasikan dengan
adalah himpunan
yang dilengkapi operasi maksimum (
penjumlahan ( ). Operasi
dan
{ }
) dan operasi
menggantikan operasi penjumlahan (+) dan
pergandaan ( ) pada aljabar konvensional yang bersifat field, sedangkan pada aljabar maks-plus bersifat semifield idempotent. Tujuan penelitian ini adalah menentukan nilai eigen dan vektor eigen suatu matriks terreduksi dalam aljabar maks-plus, dan menerapkannya ke dalam suatu contoh kasus. Nilai eigen dan vektor eigen suatu matriks terreduksi berkaitan erat dengan perilaku periodik suatu sistem
( + 1) =
( ) dengan
=
0, 1, 2, …. Perilaku periodik berhubungan dengan vektor waktu cycle (sikel), jika setiap komponen vektor waktu sikelnya sama maka nilai ini disebut dengan laju
pertumbuhan asimtotik dari sistem. Metodologi yang digunakan adalah studi literatur dan dilakukan pengkajian ulang tentang nilai eigen dan vektor eigen suatu matriks terreduksi dalam aljabar maks-plus dengan disertai contoh kasus tentang sistem produksi sederhana. Hasil dari penelitian ini adalah diperolehnya analog nilai eigen dan vektor ×
eigen matriks
dari bentuk persamaan linear
berturut-turut dalam aljabar maks-plus, yaitu =
dan
=
= 1
(
(
)
( +
( + 1) =
( )
1)).
Kata kunci : Aljabar max-plus, Field, Semifield Idempotent, Nilai Eigen dan Vektor Eigen, Matriks Terreduksi. .
commit to user v
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRACT Budi Agung Prasojo. 2013. EIGEN VALUE AND EIGEN VECTOR IN REDUCIBLE
MAX-PLUS
ALGEBRAIC
MATRIX
WITH
AN
APPLICATIONS. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. Max-plus algebra which is constructed by with maximum (
) and addition (
is the set
) operation.
and
{ } with
operation
replace addition (+) and multiplication ( ) in the conventional algebra has a properties as field, where as max-plus algebra properties semifield idempotent. Objective of this research is to determine the eigen value and eigen vector in reducible max-plus algebraic matrix and apply in a applications. Eigen value and eigen vector in reducible matrix occasion of periodic behavior system ( + 1) =
( ) where
= 0, 1, 2, …. Periodical act has a relationship with
the cycle periode vector, when each component has same cycle periode vector
then the value is called asimptotic growth rapid of the system. The method of this research is a literary study and we reviewed how to construct max-plus algebraic eigen value and eigen vector on reducible matrix with an example of simple production system. This research results eigen value and eigen vector in reducible max-plus algebraic matrix there is =
×
dan
from equation linear form
=
= 1
(
(
)
( +
( + 1) = 1)).
( ),
Key word : Max-Plus Algebra, Field, Semifield Idempotent, eigen value and eigen vector, Reducible Matrix.
commit to user vi
perpustakaan.uns.ac.id
digilib.uns.ac.id
KATA PENGANTAR
Aljabar maks-plus telah digunakan untuk memodelkan dan menganalisis secara aljabar masalah perencanaan, sistem produksi, komunikasi, sistem antrian dengan kapasitas berhingga, dan lalu lintas [2]. Aljabar maks-plus mulai dikenal karena sifatnya yang identik dengan aljabar konvensional. Banyak paper yang menjelaskan tentang ekuivalensi teorema dalam aljabar linear konvensional di aljabar maks-plus. Satu yang menarik perhatian penulis adalah karya Butkovic, Farlow, dan Subiono yang membahas tentang nilai eigen dan vektor eigen matriks terreduksi dalam aljabar maks-plus. Oleh karena itu, penulis bertujuan untuk mengkaji ulang paper tersebut. Skripsi ini dibagi menjadi 5 bagian. Bab 1 berisikan latar belakang masalah, rumusan masalah, tujuan, dan manfaat dari penelitian ini. Pada bab 2 dipaparkan tentang penelitian-penelitian yang mendahului dan teori-teori penunjang 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 tentang kesimpulan dan saran. Skripsi ini tidak dapat selesai tanpa adanya bantuan dari berbagai pihak. Penulis mengucapkan terima kasih kepada Bapak Drs. Siswanto, M.Si dan Supriyadi Wibowo, M.Si sebagai pembimbing I dan pembimbing II atas bimbingannya selama penulisan skripsi ini. Tak lupa penulis juga mengucapkan terima kasih kepada teman-teman yang senantiasa memberikan dukungan, kritik, dan saran kepada penulis. Walaupun tulisan ini jauh dari sempurna, penulis berharap skripsi ini dapat bermanfaat.
Surakarta, 21 Maret 2013
Penulis
commit to user vii
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR ISI
JUDUL .................................................................................................................... i PENGESAHAN ..................................................................................................... ii MOTTO ................................................................................................................ iii PERSEMBAHAN ................................................................................................. iv ABSTRAK ............................................................................................................. v ABSTRACT .......................................................................................................... vi KATA PENGANTAR ......................................................................................... vii DAFTAR ISI ....................................................................................................... viii DAFTAR GAMBAR ............................................................................................. x DAFTAR NOTASI ............................................................................................... xi
I
II
PENDAHULUAN
1
1.1
Latar Belakang Masalah ................................................................. 1
1.2
Perumusan Masalah ....................................................................... 3
1.3
Tujuan Penulisan ............................................................................ 3
1.4
Manfaat Penulisan .......................................................................... 3
LANDASAN TEORI
4
2.1
Tinjauan Pustaka ............................................................................ 4
2.2
Teori-Teori Penunjang ................................................................... 5 2.2.1 Sistem Persamaan Linear dan Matriks ............................... 6 2.2.2 Nilai Eigen dan Vektor Eigen Suatu Matriks ..................... 7 2.2.3 Aljabar Maks-Plus .............................................................. 7 2.2.4 Matriks dalam Aljabar Maks-Plus...................................... 9
2.3
Kerangka Pemikiran ..................................................................... 10
commit to user viii
perpustakaan.uns.ac.id
digilib.uns.ac.id
III
METODE PENELITIAN
11
IV
PEMBAHASAN
12
V
4.1
Graf dalam Aljabar Maks-Plus ..................................................... 12
4.2
Matriks Terreduksi ....................................................................... 14
4.3
Contoh Kasus ............................................................................... 22
PENUTUP
27
5.1
Kesimpulan .................................................................................. 27
5.2
Saran ............................................................................................. 28
DAFTAR PUSTAKA
29
commit to user ix
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR GAMBAR
4.1 4.2
Graf Komunikasi ( ) ........................................................................... 14
Sistem Produksi Sederhana ...................................................................... 22
commit to user x
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR NOTASI : bilangan real : operasi maksimum : operasi penjumlahan : :
0
:
aljabar maks-plus
: ( ×
( )
= ( , )
[ ]
{ },
,
)
: himpunan matriks dalam aljabar maks-plus berukuran :
matriks identitas terhadap operasi
:
matriks identitas terhadap operasi
:
graf komunikasi dari
:
graf berarah
:
matriks persegi
:
elemen matriks
:
matriks
dengan elemen-elemen
:
pangkat
dari matriks
:
vektor di dalam aljabar maks-plus
:
vektor di dalam aljabar konvensional
:
bilangan asli
: transpose dari matriks = ( , )
(, , ) ( , )
| | | |
:
graf
:
vertex / Titik
:
edge / Busur
:
path / Lintasan
:
himpunan path dari ke dengan panjang
: :
bobot busur ( , )
:
bobot suatu lintasan
panjang lintasan
commit to user xi
×
perpustakaan.uns.ac.id
| |
digilib.uns.ac.id
:
bobot rata-rata lintasan
:
norma dari
= ( , )
:
reduce graf
:
himpunan node / vertex
( )
:
himpunan arc / edge
:
vektor waktu sikel
:
node dapat ditempuh dari node
:
nilai eigen
:
vektor eigen
( )
commit to user xii