MASALAH NILAI EIGEN DAN VEKTOR EIGEN YANG DIPERUMUM MATRIKS ATAS ALJABAR MAKS-PLUS
oleh DIAN RIZKI NURAINI M0111021
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2016
i
ABSTRAK Dian Rizki Nuraini. 2016. MASALAH NILAI EIGEN DAN VEKTOR EIGEN YANG DIPERUMUM MATRIKS ATAS ALJABAR MAKS-PLUS. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Aljabar maks-plus adalah semiring R dengan R = R∪{−∞} yang dilengkapi operasi ⊕ = maks dan operasi ⊗ = +. Masalah nilai eigen dituliskan sebagai A ⊗ x = λ ⊗ x dengan λ merupakan nilai eigen dan x(k) merupakan vektor eigen dari matriks A. Masalah nilai eigen dan vektor eigen yang diperumum dituliskan sebagai A ⊗ x = λB ⊗ x dengan A, B matriks nonnegatif. Selain itu, masalah nilai eigen dan vektor eigen yang diperumum pada aljabar maks-plus dapat pula dituliskan dalam bentuk A ⊗ x = λ ⊗ B ⊗ x. Tujuan dari penelitian ini adalah menentukan nilai eigen dan vektor eigen dari masalah nilai eigen yang diperumum untuk matriks atas aljabar maks-plus. Hasil penelitian ini adalah nilai eigen dan vektor eigen dari masalah nilai eigen yang diperumum untuk matriks tak tereduksi dan matriks tereduksi pada aljabar maks-plus. Kata kunci: Aljabar maks-plus, nilai eigen, vektor eigen, masalah nilai eigen dan vektor eigen yang diperumum
iii
ABSTRACT Dian Rizki Nuraini. 2016. GENERALIZED EIGEN VALUE AND EIGEN VECTOR PROBLEM MATRIX ON MAX-PLUS ALGEBRA. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. Max-plus algebra is the semiring R where R = R ∪ {−∞} is equipped with operations ⊕ = max and ⊗ = plus. Eigenvalue problem A ⊗ x = λ ⊗ x where λ is called eigenvalue and x(k) is called eigenvector of matrices A. Generalized eigenvalue problem and eigenvector A ⊗ x = λB ⊗ x where A and B are nonnegative matrices. In addition, generalized eigenvalue and eigenvector problem in max-plus algebra can also written in the form of A ⊗ x = λ ⊗ B ⊗ x. The aims of this research are to obtain eigenvalue and eigenvector from generalized eigenvalue problem matrix on max-plus algebra. The results of this research are eigenvalue and eigenvector from generalized eigenvalue problem for irreducible matrix and reducible matrix in max-plus algebra. Key words: max-plus algebra, eigenvalue, eigenvector, generalized eigenvalue and eigenvector problem
iv
BAB I PENDAHULUAN 1.1
Latar Belakang Masalah
Aljabar maks-plus sering digunakan untuk memodelkan permasalahan seperti sistem antrian, penjadwalan, dan sistem produksi. Tiga hal tersebut adalah contoh discrete event system (DES ). Menurut Schutter dan Boom [11], DES adalah sistem nonlinear dalam (R, +, ×). Namun DES dapat diubah menjadi sistem linear dalam aljabar maks-plus. Menurut Tam [14] aljabar maks-plus adalah aljabar linear atas semiring R dengan R = R∪{−∞} yang dilengkapi dengan operasi ”⊕” yang menyatakan maksimum dan ”⊗” yang menyatakan plus. Butkovic dan Cuninghame-Green [4] menyebutkan bahwa ϵ = −∞ merupakan elemen identitas untuk penjumlahan dan e = 0 merupakan elemen identitas untuk perkalian. Farlow [7] menyebutkan bahwa penyelesaian dan teknik perhitungan dalam aljabar maks-plus analog dengan aljabar biasa. Menurut Tam [14] penjadwalan mesin di pabrik adalah contoh DES yang linear dalam aljabar maks-plus. Misalkan aij adalah lamanya mesin Mj memproduksi komponen Pi yang dibutuhkan mesin Mi untuk tahap selanjutnya, xj (k) adalah waktu mulai mesin Mj untuk tahap ke-k, dengan i = 1, . . . , m dan j = 1, . . . , n. Jadi, waktu selesai setiap mesin memproduksi komponen Pi untuk tahap ke-k adalah aij + xj (k − 1). Oleh karena itu, waktu mulai untuk tahap ke-k mesin Mi adalah maksimum dari waktu selesai setiap mesin Mj memproduksi komponen Pi yang dapat dituliskan sebagai maks{ai1 + x1 (k − 1), . . . , ain + xn (k − 1)}, dengan k = 2, 3, . . .. Dengan demikian, waktu mulai setiap mesin Mi untuk tahap ke-k + 1 adalah xi (k + 1) = maks{ai1 + x1 (k), . . . , ain + xn (k)}.
1
(1.1)
Di dalam (R, +, ×), persamaan (1.1) adalah nonlinear. Namun, di dalam aljabar maks-plus persamaan (1.1) dapat disajikan dalam bentuk linear yaitu xi (k + 1) = ai1 ⊗ x1 (k) ⊕ . . . ⊕ ain ⊗ xn (k). Jadi, sistem yang memuat waktu mulai setiap mesin Mi untuk tahap ke-k + 1 dapat ditulis sebagai x(k + 1) = A ⊗ x(k)
(1.2)
dengan A adalah matriks bujur sangkar dengan elemennya berupa lama waktu yang dibutuhkan untuk memproduksi barang. Pada saat mesin melakukan tugas yang sama berulang kali sampai waktu berakhir, dalam setiap tahapnya mesin akan memulai dan menyelesaikan proses serta menunggu hingga semua komponen yang dibutuhkan pada tahap selanjutnya sudah siap. Salah satu kriteria yang diinginkan pengusaha adalah melihat kapan dapat memilih waktu untuk memulai prosesnya bahwa selisih dua tahap yang berurutan dari setiap mesin adalah konstanta. Untuk suatu λ ∈ R pada tahap ke-k + 1 diperoleh x(k + 1) = λ ⊗ x(k), ∀k ∈ N.
(1.3)
Dari persamaan (1.2) dan (1.3) diperoleh A ⊗ x(k) = λ ⊗ x(k).
(1.4)
Berdasarkan persamaan (1.4), λ merupakan nilai eigen dan x(k) merupakan vektor eigen dari matriks A. Menurut Tam [14] sistem produksi pada pabrik itu akan mencapai steady state apabila dapat ditentukan x(k) dan λ. Dalam hal ini, masalah untuk menentukan λ dan x(k) disebut masalah nilai eigen dan vektor eigen. Matriks tak tereduksi mempunyai nilai eigen tunggal. Sedangkan matriks tereduksi dimungkinkan mempunyai nilai eigen tidak tunggal. Masalah nilai eigen untuk sebuah matriks A yang disajikan persamaan (1.4) dapat ditulis sebagai A ⊗ x = λ ⊗ B ⊗ x, dimana B = I dan I adalah matriks identitas (Bapat et al [2]). A ⊗ x = λ ⊗ B ⊗ x disebut masalah nilai eigen dan vektor eigen 2
yang diperumum (Cuninghame-Green dan Butkoviˇc [5]). Adapun A⊗x = λB ⊗x disebut masalah nilai eigen dan vektor eigen yang diperumum untuk matriks nonnegatif (Binding dan Volkmer [3]). Binding dan Volkmer [3] telah menjelaskan tentang masalah nilai eigen dan vektor eigen yang diperumum untuk matriks tak tereduksi nonnegatif. Dalam hal ini, Elsner dan van den Driessche [6] menjelaskan tentang metode pangkat untuk menentukan nilai eigen dan vektor eigen pada matriks nonnegatif. Adapun Cuninghame-Green dan Butkoviˇc [5] telah membahas masalah eigen yang diperumum pada aljabar maks-plus untuk matriks tak tereduksi dan matriks tereduksi. Oleh karena itu, dalam penelitian ini dibahas mengenai masalah nilai eigen dan vektor eigen yang diperumum untuk matriks tak tereduksi dan matriks tereduksi atas aljabar maks-plus.
1.2
Perumusan Masalah
Berdasarkan latar belakang masalah, dapat disusun perumusan masalah yaitu bagaimana menyelesaikan masalah nilai eigen dan vektor eigen yang diperumum untuk matriks atas aljabar maks-plus.
1.3
Tujuan
Tujuan penelitian ini adalah dapat menentukan penyelesaian nilai eigen dan vektor eigen yang diperumum untuk matriks atas aljabar maks-plus.
1.4
Manfaat
Skripsi ini diharapkan dapat memberikan pengetahuan dan penjelasan yang rinci mengenai masalah nilai eigen dan vektor eigen yang diperumum untuk matriks atas aljabar maks-plus berdasarkan penelitian yang telah dilakukan oleh peneliti sebelumnya.
3
