perpustakaan.uns.ac.id
digilib.uns.ac.id
SISTEM LINEAR DALAM ALJABAR MAKS-PLUS
oleh ANITA NUR MUSLIMAH M01009009
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
commit to user
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRAK Anita Nur Muslimah. 2013. SISTEM LINEAR DALAM ALJABAR MAKSPLUS. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. ¯ dengan R ¯ = R∪ Aljabar maks-plus adalah aljabar linear atas semiring R {−∞} yang dilengkapi dengan operasi “⊕” yang menyatakan maksimum dan “⊗” yang menyatakan plus. Sistem linear dalam aljabar maks-plus terdiri atas sistem persamaan linear dan sistem pertidaksamaan linear. Penelitian ini bertujuan mengkaji ulang penyelesaian dari sistem linear dalam aljabar maks-plus dan kaitannya dengan himpunan bayangan dan matriks reguler kuat. Metode yang digunakan dalam skripsi ini adalah studi literatur. Jika matriks A adalah matriks reguler kuat maka banyaknya penyelesaian sistem A ⊗ x = b adalah 0, 1, atau ∞. Jika suatu sistem persamaan linear memiliki penyelesaian tunggal maka himpunan bayangan dari matriks A adalah himpunan bayangan sederhana. Kata kunci: sistem linear aljabar maks-plus, himpunan bayangan, matriks reguler kuat
commit to user
iii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRACT Anita Nur Muslimah. 2013. LINEAR SYSTEM IN MAX-PLUS ALGEBRA. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. ¯ where R ¯ = Max-plus algebra is the linear algebra over the semiring R R ∪ {−∞}, with the operations “⊕” which is maximum and “⊗” which is plus. There are two linear systems in the max-plus algebra. These are system of linear equations and system of linear inequalities. The purpose of this research is to review the solution of linear system in max-plus algebra and its relation with the image set and the strongly regular matrices. This essay method is study of literature. If A is a strongly regular matrix then the solution of system A ⊗ x = b is 0, 1 or ∞. If a system of linear equations has a unique solution then the image of matrix A is a simple image set. Key words: linear system of max-plus algebra, image set, strongly regular matrices
commit to user
iv
perpustakaan.uns.ac.id
digilib.uns.ac.id
KATA PENGANTAR
Segala puji dan syukur penulis panjatkan kepada Allah SWT yang telah melimpahkan rahmat dan karunia-Nya sehingga skripsi ini dapat selesai. Penulis menyadari bahwa dalam penulisan skripsi ini, penulis mendapat bimbingan, dukungan dan bantuan dari berbagai pihak. Oleh karena itu penulis mengucapkan terima kasih kepada 1. Bapak Drs. Siswanto, M.Si. selaku Pembimbing I yang telah membimbing dalam penelitian ini dan Ibu Dra. Purnami Widyaningsih, M.App.Sc. selaku Pembimbing II yang telah membimbing dalam penulisan skripsi ini, dan 2. semua pihak yang telah membantu. Penulis berharap skripsi ini dapat bermanfaat bagi semua pihak. Surakarta, Desember 2013
Penulis
commit to user
v
perpustakaan.uns.ac.id
digilib.uns.ac.id
MOTO
Lakukan yang terbaik. (Penulis)
commit to user
vi
perpustakaan.uns.ac.id
digilib.uns.ac.id
PERSEMBAHAN
Skripsi ini saya persembahkan kepada Bapak, Ibu dan kakakku.
commit to user
vii
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR ISI
HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
HALAMAN PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . .
ii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii I
PENDAHULUAN
1
1.1
Latar Belakang Masalah . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4
Manfaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
II LANDASAN TEORI
4
2.1
Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Teori Penunjang . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1
Aljabar Maks-Plus . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2
Aljabar Min-Plus . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
Kerangka Berpikir
. . . . . . . . . . . . . . . . . . . . . . . . . .
III METODE PENELITIAN
commit to user
IV PEMBAHASAN
10 11 13
viii
perpustakaan.uns.ac.id
digilib.uns.ac.id
4.1
Sistem Persamaan Linear . . . . . . . . . . . . . . . . . . . . . . .
13
4.2
Sistem Pertidaksamaan Linear . . . . . . . . . . . . . . . . . . . .
23
4.3
Himpunan Bayangan dan Matriks Reguler Kuat . . . . . . . . . .
25
V PENUTUP
38
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
5.2
Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
DAFTAR PUSTAKA
39
LAMPIRAN
41
commit to user
ix
perpustakaan.uns.ac.id
digilib.uns.ac.id
Bab I PENDAHULUAN 1.1
Latar Belakang Masalah
Tam [13] menyebutkan bahwa banyak teknologi pada bidang produksi yang dikembangkan dalam periode 1970-an dan 1980-an. Di bidang produksi terdapat penjadwalan mesin, antrian dan proses jaringan. Tiga hal tersebut adalah contoh discrete event system (DES ). Menurut Schutter dan Boom [11], DES adalah nonlinear dalam (R, +, ×). Namun, DES dapat diubah menjadi sistem linear dalam aljabar maks-plus. Tam [13] menyebutkan bahwa aljabar maks-plus adalah ¯ dengan R ¯ = R ∪ {−∞} yang dilengkapi dengan aljabar linear atas semiring R operasi “⊕” yang menyatakan maksimum dan “⊗” yang menyatakan plus. 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 mesin Mi untuk tahap ke-k adalah maksimum dari waktu selesai setiap mesin Mj memproduksi komponen Pi (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)
Di dalam (R, +, ×), persamaan (1.1) adalah nonlinear. Namun, di dalam maksplus persamaan (1.1) dapat disajikan sebagai commit to user xi (k + 1) = ai1 ⊗ x1 (k) ⊕ . . . ⊕ ain ⊗ xn (k) 1
perpustakaan.uns.ac.id
digilib.uns.ac.id
yang linear. Jadi, sistem yang memuat waktu mulai setiap mesin Mi untuk tahap ke-k + 1 dapat ditulis sebagai x (k) a a12 . . . a1n x (k + 1) 1 11 1 x2 (k + 1) a21 a22 . . . a2n x2 (k) = .. .. .. .. ⊗ .. .. . . . . . . xn (k) am1 am2 . . . amn xm (k + 1) (
)T atau x(k + 1) = A ⊗ x(k), dengan x(k) = x1 (k) x2 (k) . . . xn (k) adalah vektor yang memuat waktu mulai setiap mesin Mj untuk tahap ke-k. Menurut Tam [13], ide aljabar maks-plus ditemukan pertama kali pada tahun 1950-an. Pada tahun 1960, Cuninghame-Green mempublikasikan metode kolom maksimum untuk menyelesaikan suatu sistem persamaan linear. Setelah itu, Cuninghame-Green [8] mempublikasikan buku yang salah satu bahasannya adalah metode residu untuk menyelesaikan suatu sistem linear pada tahun 1979. Kemudian, publikasi tentang sistem linear dilakukan lagi pada tahun 2000 dan 2003 oleh Butkoviˇ c [4, 5]. Pada artikelnya tersebut dibahas himpunan bayangan sederhana pada pemetaan linear (maks, +) dan hubungan antara aljabar maksplus dengan kombinatorik. Lalu pada tahun 2010, Tam [13] mempublikasikan tesisnya yang memuat sistem linear pada aljabar maks-plus, himpunan bayangan serta matriks reguler kuat. Sebagaimana yang ditulis oleh Tam [13], himpunan bayangan dinotasikan ¯ n }. Kemudian, untuk vektordengan Im(A), yaitu Im(A) = {A ⊗ x|x ∈ R ¯ m yang bebas linear kuat, jika m = n maka matriks vektor A1 , A2 , . . . , An ∈ R A = (A1 , A2 , . . . , An ) disebut matriks reguler kuat. Tam [13] dan Butkoviˇ c [4] menyebutkan bahwa penyelesaian sistem persamaan linear dalam aljabar maksplus memiliki kaitan dengan himpunan bayangan dan matriks reguler kuat. Oleh karena itu, dalam skripsi ini dikaji ulang sistem linear dalam aljabar maks-plus, termasuk himpunan bayangan dan matriks reguler kuat dari sistem persamaan linear aljabar maks-plus yang telah dibahas dalam Tam [13] dan Butkoviˇ c [4]. Secommit to user lain itu, penulis juga memberikan pembuktian yang belum dijelaskan dan contohcontoh dari teorema. 2
perpustakaan.uns.ac.id
digilib.uns.ac.id
1.2
Perumusan Masalah
Berdasarkan latar belakang tersebut dapat dirumuskan tiga masalah yaitu 1. bagaimana menentukan sistem persamaan linear dalam aljabar maks-plus dan penyelesaiannya? 2. bagaimana menentukan sistem pertidaksamaan linear dalam aljabar maksplus dan penyelesaiannya? 3. bagaimana kaitan antara penyelesaian dari sistem persamaan linear aljabar maks-plus dengan himpunan bayangan dan matriks reguler kuat?
1.3
Tujuan
Penelitian ini bertujuan untuk 1. menentukan sistem persamaan linear dalam aljabar maks-plus dan penyelesaiannya, 2. menentukan sistem pertidaksamaan linear dalam aljabar maks-plus dan penyelesaiannya, dan 3. menjelaskan kaitan antara penyelesaian dari sistem persamaan linear aljabar maks-plus dengan himpunan bayangan dan matriks reguler kuat.
1.4
Manfaat
Skripsi ini diharapkan dapat memberikan penjelasan yang rinci mengenai sistem linear dalam aljabar maks-plus dan penyelesaiannya berdasarkan hasil penelitian yang telah dilakukan oleh peneliti sebelumnya.
commit to user
3
