TESIS – SM 142501
KARAKTERISASI PENYELESAIAN SISTEM PERSAMAAN LINEAR ATAS ALJABAR SUPERTROPICAL Dian Yuliati NRP. 1214 201 002 DOSEN PEMBIMBING Dr. Subiono, M.S.
PROGRAM MAGISTER JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2016
THESIS – SM 142501
CHARACTERIZATION OF THE SOLUTIONS OF SYSTEM OF LINEAR EQUATIONS OVER SUPERTROPICAL ALGEBRA Dian Yuliati NRP. 1214 201 002 SUPERVISOR Dr. Subiono, M.S. MASTER’S DEGREE DEPARTMENT OF MATHEMATICS FACULTY OF MATHEMATICS AND NATURAL SCIENCES SEPULUH NOPEMBER INSTITUTE OF TECHNOLOGY SURABAYA 2016
DAFTAR ISI
LEMBAR PENGESAHAN ................................................................................. i ABSTRAK......................................................................................................... iii ABSTRACT ....................................................................................................... v KATA PENGANTAR ...................................................................................... vii DAFTAR ISI ..................................................................................................... ix DAFTAR NOTASI............................................................................................ xi BAB 1
BAB 2
PENDAHULUAN .............................................................................. 1 1.1
Latar Belakang ......................................................................... 1
1.2
Rumusan Masalah .................................................................... 3
1.3
Batasan Masalah ....................................................................... 3
1.4
Tujuan Penelitian ...................................................................... 4
1.5
Manfaat Penelitian .................................................................... 4
KAJIAN PUSTAKA DAN DASAR TEORI ..................................... 5 2.1
Penelitian Terdahulu ................................................................. 5
2.2
Semiring ................................................................................... 6
2.3
Aljabar Max-Plus...................................................................... 8
2.3.1 Matriks atas Aljabar Max-Plus ................................................ 10 2.3.2 Penjumlahan Matriks .............................................................. 10 2.3.3 Perkalian Matriks.................................................................... 11 2.3.4 Perpangkatan Matriks ............................................................. 12 2.3.5 Transpose Matriks .................................................................. 13 2.3.6 Matriks Identitas ..................................................................... 13 2.4
Aljabar Tropical ..................................................................... 13
2.5
Perluasan Aljabar Tropical ..................................................... 14
2.6
Aljabar Supertropical ............................................................. 16
2.6.1 Semiring dengan Ghost ........................................................... 16 2.6.2 Semiring Supertropical ........................................................... 16 2.6.3 Relasi Ghost Surpass .............................................................. 17 2.7
Matriks atas semiring Supertropical........................................ 18
2.7.1 Penjumlahan Matriks .............................................................. 18 2.7.2 Perkalian Matriks.................................................................... 19
ix
2.7.3 Perpangkatan Matriks ............................................................. 20 2.7.4 Transpose Matriks .................................................................. 21 2.7.5 Determinan ............................................................................. 22 2.7.6 Minor dan Adjoint .................................................................. 22 2.7.7 Matriks Non Singular dan Singular ......................................... 23 2.7.8 Matriks Pseudo-Zero .............................................................. 24 2.7.9 Matriks Identitas ..................................................................... 25 2.7.10 Pseudo-Invers Matriks ............................................................ 25 2.7.11 Matriks Invertibel ................................................................... 28 2.8
Sistem Persamaan Linear atas Aljabar Max-Plus..................... 29
2.8.1 Sistem Persamaan Linear Aljabar Max-Plus............................ 29 2.8.2 Karakterisasi Penyelesaian Sistem Persamaan Linear atas Aljabar Max-Plus.................................................................... 34 2.9
Sistem Persamaan Linear atas Aljabar Supertropical .............. 43
BAB 3
METODE PENELITIAN ................................................................ 45
BAB 4
PEMBAHASAN ............................................................................... 47
BAB 5
4.1
Karakterisasi Penyelesaian Sistem Persamaan Linear Tak Homogen atas Aljabar Supertropical ...................................... 47
4.2
Karakterisasi Penyelesaian Sistem Persamaan Linear Homogen atas Aljabar Supertropical ...................................................... 71
SIMPULAN DAN SARAN .............................................................. 81 5.1
Simpulan ................................................................................ 81
5.2
Saran ...................................................................................... 81
DAFTAR PUSTAKA ....................................................................................... 83
x
DAFTAR NOTASI
𝑅𝑚𝑎𝑥
: Aljabar Max-plus
◊
: Akhir Contoh
□
: Akhir Definisi
■
: Akhir Teorema dan Lemma
∈
: Anggota
1R
: Elemen identitas pada semiring 𝑅
0R
: Elemen nol pada semiring 𝑅
∪
: Gabungan
ℝ
: Himpunan bilangan real
𝑀𝑛 (𝑅)
: Himpunan matriks ukuran 𝑛 × 𝑛 dengan entri matriks anggota 𝑅
ℝ𝑣
: Himpunan dengan anggotanya elemen ghost pada extended semiring tropical
𝒯
: Himpunan dengan anggotanya elemen tangible pada aljabar supertropical
𝒢
: Himpunan dengan anggotanya elemen ghost pada aljabar supertropical
𝒢0
: Ideal ghost
𝑎𝑣
: Nilai a pada pemetaan ghost
𝑣
: Pemetaan ghost
⊨
: Relasi ghost surpass pada 𝑅
𝑅
: Semiring supertropical
⨁
: Operasi max
⊗
: Operasi plus
∀
: Untuk setiap
xi
KATA PENGANTAR
Puji syukur Alhamdulillah penulis panjatkan kehadirat Allah SWT yang telah melimpahkan Rahmat, Taufiq, dan Hidayah-Nya, serta junjungan Beliau Rasulullah SAW atas suri teladan yang dibawanya sehingga penulis dapat menyelesaikan Tesis yang berjudul “Karakterisasi Penyelesaian Sistem Persamaan Linear Atas Aljabar Supertropical” ini tepat pada waktunya. Tesis ini merupakan sebagian persyaratan kelulusan dalam memperoleh gelar Magister di Program Studi Magister Matematika, Fakultas MIPA, Institut Teknologi Sepuluh Nopember. Penyusunan Tesis ini tidak lepas dari bimbingan, bantuan, dan dukungan moral maupun spiritual dari banyak pihak. Oleh sebab itu, penulis mengucapkan terima kasih yang sebesar-besarnya kepada : 1.
Ibu, Bapak, beserta keluarga tercinta yang selalu memberikan dukungan, doa, dan motivasi agar penulis dapat menyelesaikan Tesis ini.
2.
Prof. Ir. Joni Hermana, M.Sc.ES., Ph.D. selaku Rektor Institut Teknologi Sepuluh Nopember Surabaya.
3.
Prof. Ir. Djauhar Manfaat, M.Sc., Ph.D. selaku Direktur Program Pascasarjana Institut Teknologi Sepuluh Nopember Surabaya.
4.
Dr. Imam Mukhlash, M.T., selaku Ketua Jurusan Matematika Institut Teknologi Sepuluh Nopember Surabaya.
5.
Dr. Subiono, M.S., selaku Koordinator Program Studi Pascasarjana Matematika dan juga dosen pembimbing yang telah meluangkan waktu untuk membimbing, memberikan masukan dan mendorong penulis dalam menyelesaikan Tesis ini.
6.
Dr. Haryanto, M.Si., selaku dosen wali yang telah memberikan motivasi, arahan, dan bimbingan selama penulis menempuh kuliah.
7.
Bapak / Ibu Dosen penguji yang telah memberikan masukan dan juga motivasi bagi penulis sehingga Tesis ini dapat selesai tepat waktu.
vii
8.
Seluruh dosen Matematika yang telah memberikan bekal dan ilmu pengetahuan serta staf administrasi Program Studi Magister Matematika atas segala bantuannya.
9.
Sahabat penulis lainnya atas semua bantuan, semangat, dan dukungannya selama proses penulisan Tesis ini.
10. Keluarga besar Pascasarjana Matematika ITS 2014, dan semua pihak yang telah membantu proses penulisan Tesis ini yang tidak dapat penulis sebutkan satu persatu. Terima kasih. Semoga Allah SWT memberikan anugerah dan karunia-Nya kepada semua pihak yang telah membantu menyelesaikan Tesis ini. Penulis menyadari bahwa dalam penulisan Tesis ini masih banyak kekurangan, sehingga kritik dan saran dari pembaca sangat penulis harapkan untuk perbaikan kedepannya. Kritik dan saran bisa dikirim melalui email penulis
[email protected]. Akhirnya semoga Tesis ini dapat bermanfaat bagi pembaca, khususnya mahasiswa Institut Teknologi Sepuluh Nopember.
Surabaya, Januari 2016
Penulis
viii
KARAKTERISASI PENYELESAIAN SISTEM PERSAMAAN LINEAR ATAS ALJABAR SUPERTROPICAL Nama Mahasiswa NRP Dosen Pembimbing
: Dian Yuliati : 1214 201 002 : Dr. Subiono, M.S.
ABSTRAK Aljabar tropical adalah semiring idempotent sekaligus semifield. Salah satu contoh dari aljabar tropical yang memiliki struktur semiring idempoten sekaligus semifield yaitu aljabar max-plus. Aljabar max-plus didefinisikan sebagai ℝmax = (ℝ𝜀 ,⊕,⊗), dimana ℝ𝜀 = ℝ ∪ {−∞} dengan ℝ adalah semua bilangan real, 𝜀 ≝ −∞ , 𝑎⨁𝑏 ≝ max{𝑎, 𝑏} dan 𝑎 ⊗ 𝑏 ≝ 𝑎 + 𝑏 untuk setiap 𝑎, 𝑏 ∈ ℝ𝜀 . Berbeda dengan aljabar linear biasa, aljabar max-plus tidak mempunyai elemen invers terhadap operasi ⊕. Hal ini yang menyulitkan untuk menyelesaikan sistem persamaan linear 𝐴 ⊗ 𝒙 = 𝒃 di ℝmax . Oleh karena itu dikonstruksikan struktur baru yang merupakan perluasan dari ℝmax yang disebut extended semiring tropical yang dinotasikan sebagai 𝕋 = ℝ ∪ {−∞} ∪ ℝ𝑣 dimana ℝ𝑣−∞ = ℝ𝑣 ∪ {−∞} disebut ideal dari 𝕋, 𝑣 ∶ 𝕋 → ℝ𝑣−∞ disebut pemetaan ghost yang memenuhi 𝑣 (𝑎) = 𝑎, ∀𝑎 ∈ ℝ𝑣−∞ dan 𝑣(𝑎) = 𝑎𝑣 ,∀𝑎 ∈ ℝ . Secara lebih umum perluasan dari aljabar tropical dinamakan aljabar supertropical. Oleh karena itu dapat digeneralisasikan penyelesaian sistem persamaan linear menggunakan relasi ghost surpass ⊨. Dengan relasi ghost surpass penyelesaian sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃 akan diperlemah menjadi 𝐴 ⊗ 𝒙 ⊨ 𝒃. Dari hasil penelitian didapatkan bahwa sistem persamaan linear tak homogen 𝐴 ⊗ 𝒙 ⊨ 𝒃 atas aljabar supertropical mempunyai solusi tangible yang tunggal jika dan hanya jika |𝐴| ∈ 𝒯 dan (adj(A) ⊗ 𝒃) ∈ 𝒯0 𝑛 , serta mempunyai penyelesaian tidak tunggal jika dan hanya jika |𝐴| ∈ 𝒢0 ≠ 𝜀 atau (adj(A) ⊗ 𝒃) ∉ 𝒯0 𝑛 . Sedangkan sistem persamaan linear homogen 𝐴 ⊗ 𝒙 ⊨ 𝜺 atas aljabar supertropical mempunyai penyelesaian trivial jika dan hanya jika |𝐴| ∈ 𝒯 dan mempunyai penyelesaian tak trivial jika dan hanya jika |𝐴| ∈ 𝒢0 ≠ 𝜀.
Kata kunci : aljabar tropical, aljabar supertropical, sistem persamaan linear.
iii
CHARACTERIZATION OF THE SOLUTION OF SYSTEM OF LINEAR EQUATIONS OVER SUPERTROPICAL ALGEBRA Name Student Identity Number Supervisor
: Dian Yuliati : 1214 201 002 : Dr. Subiono, M.S.
ABSTRACT Tropical algebra is idempotent semirings and semifields. Max-plus algebra is one of many idempotent semirings and semifields. Max-plus algebra is defined as ℝmax = (ℝ𝜀 ,⊕,⊗), where ℝ𝜀 = ℝ ∪ {−∞} with ℝ is the set of real numbers, 𝜀 ≝ −∞ , 𝑎⨁𝑏 ≝ max{𝑎, 𝑏} and 𝑎 ⊗ 𝑏 ≝ 𝑎 + 𝑏 for every 𝑎, 𝑏 ∈ ℝ𝜀 . In contrast to conventional linear algebra, there are no inverse elements with respect to ⊕ in ℝmax . It also causes difficulty when solving linear systems of equations 𝐴 ⊗ 𝒙 = 𝒃. Therefore a new structure that generalizes max-plus algebra is constructed and it is called extended tropical semiring, denoted as 𝕋 = ℝ ∪ {−∞} ∪ ℝ𝑣 where 𝑣 = ℝ𝑣 ∪ {−∞} is called ideal of 𝕋, 𝑣 ∶ 𝕋 → ℝ𝑣−∞ is called the ghost map ℝ−∞ satisfying 𝑣 (𝑎) = 𝑎, ∀𝑎 ∈ ℝ𝑣 and 𝑣 2 (𝑎) = 𝑣 (𝑎),∀𝑎 ∈ 𝕋. Generally, the extension of tropical algebra is called supertropical algebra. Therefore we can generalize the method to solve system of linear equations using ghost surpass relation, then system of linear equations 𝐴 ⊗ 𝒙 = 𝒃 will be weakened 𝐴 ⊗ 𝒙 ⊨ 𝒃. Based on the results of the study showed that characterization of the solution of 𝑛 × 𝑛 non-homogeneous system of linear equations 𝐴 ⊗ 𝑥 ⊨ 𝑏 over supertropical algebra has a unique solution if only if |𝐴| ∈ 𝒯 and (adj(A) ⊗ 𝑏) ∈ 𝒯0 𝑛 . Moreover, it has an infinite numbers of solutions if only if |𝐴| ∈ 𝒢0 ≠ 𝜀 or (adj(A) ⊗ 𝒃) ∉ 𝒯0 𝑛 . While for characterization of the solution of 𝑛 × 𝑛 system homogeneous of linear equations 𝐴 ⊗ 𝑥 ⊨ 𝜀 over supertropical algebra has a trivial solution if and only if |𝐴| ∈ 𝒯 and a non-trivial solution if and only if |𝐴| ∈ 𝒢0 ≠ 𝜀.
Keywords : tropical algebra, supertropical algebra, system of linear equations.
v
BAB I PENDAHULUAN END
1.1
Latar Belakang Aljabar tropical merupakan salah satu bidang dalam matematika yang telah
berkembang selama satu dekade terakhir. Aljabar tropical dipelopori oleh ahli matematika dan komputer Imre Simon, seorang peneliti dari Brazil pada tahun 1980an [1]. Aljabar tropical adalah semiring idempotent sekaligus semifield. Salah satu contoh dari aljabar tropical yang memiliki struktur semiring idempoten sekaligus semifield yaitu aljabar max-plus [2]. Dalam papernya, Izhakian (2009) memperkenalkan struktur baru yang merupakan perluasan dari aljabar max-plus yang disebut extended semiring tropical [3]. Perluasan tersebut muncul untuk mengatasi kesulitan dalam mempelajari polinomial atas aljabar max-plus sehingga dibutuhkan struktur baru yang lebih luas yang mencakup aljabar max-plus. Secara lebih umum perluasan dari aljabar tropical dinamakan aljabar supertropical. Karena aljabar supertropical merupakan kajian yang relatif baru, maka berbagai penelitian mengenai aljabar supertropical terus dilakukan. Pada tahun 2010, Izhakian dan Rowen dalam penelitian yang berjudul “Supertropical Algebra” membahas tentang faktorisasi polinomial atas aljabar supertropical, penelitian ini menjelaskan bahwa setiap polinomial dapat difaktorkan dalam bentuk linier maupun kuadrat [4]. Pada tahun yang sama, Izhakian dkk dalam penelitian berjudul “Supertropical Linear Algebra” membahas tentang dasar teori atas aljabar supertropical yang sifat-sifatnya didapatkan dari aljabar linier dengan memanfaatkan relasi ghost surpasses [5]. Masih pada tahun yang sama, Izhakian dan Rowen dalam penelitian “Supertropical Polynomial and Resultant” membahas mengenai polinomial relatif prima atas aljabar supertropical [6]. Pada tahun 2011, Izhakian dan Rowen melakukan penelitian yang berjudul “Supertropical Matrix Algebra”, penelitian tersebut membahas tentang teori matriks atas semiring supertropical yaitu jika |𝐴| dan |𝐵| keduanya tangible maka
1
|𝐴 ⊗ 𝐵| = |𝐴| ⊗ |𝐵| [7]. Kemudian penelitian berlanjut pada “Supertropical Matrix Algebra II” yang membahas eksistensi adj 𝐴 dari matriks non singular sehingga didapatkan pseudo-invers kanan dan pseudo-invers kiri yang tunggal sehubungan dengan matriks pseudo-identitas yang bersesuaian dengan 𝐴, selain itu juga dibahas sifat adjoint dan penerapannya untuk menghitung vektor eigen atas aljabar supertropical [8]. Pada tahun yang sama, penelitian berlanjut pada “Supertropical Matrix Algebra III: Powers of Matrices and Their Supertropical Eigenvalues” yang membahas mengenai teori matriks atas aljabar supertropical, polinomial karakteristik serta dekomposisi Jordan dan nilai eigen dari matriks atas aljabar supertropical [9]. Masih pada tahun yang sama, Izhakian dkk mengembangkan penelitian pada teori valuasi atas aljabar supertropical diantaranya berjudul “Supertropical Semirings and Supervaluations”, “Dominance and Transmissions in Supertropical Valuation Theory”, Monoid Valuations and Value Ordered Supervaluations” dan “A Glimpse on Supertropical Valuation Theory”. Pada tahun 2012, Izhakian dkk dalam penelitian yang berjudul “Dual Spaces and Bilinear Forms in Supertropical Linear Algebra” membahas tentang ruang dual dan bentuk bilinear atas aljabar supertropical [10]. Pada tahun yang sama, Adi Niv melakukan penelitian berjudul “Factorization of Supertropical Matrices” yang membahas mengenai faktorisasi matriks atas aljabar supertropical, didapatkan bahwa tidak semua matriks non singular atas aljabar supertropical bisa difaktorkan menjadi matriks-matriks elementer [11]. Pada tahun 2013, Izhakian dkk melakukan penelitian yang berjudul “Supertropical Monoids : Basics and Canonical Factorization” membahas mengenai monoid supertropical dan valuasi yang digunakan dalam teori matriks dan geometri tropical [12]. Selanjutnya, pada tahun 2014 Adi Niv dalam penelitian berjudul “Characteristic Polynomial of Supertropical Matrices” membahas mengenai polinomial karakteristik serta nilai eigen atas aljabar supertropical [13]. Pada tahun 2015, Izhakian dkk melakukan penelitian “Supertropical Quadratic Forms I” yang menjelaskan mengenai bentuk kuadratik pada modul atas semiring supertropical [14], kemudian penelitian tersebut berlanjut pada “Supertropical Quadratic Forms II” [15]. Pada tahun yang sama, Adi Niv dalam
2
salah satu bagian disertasinya yang berjudul “On Pseudo-Inverses of Matrices and Their Characteristic Polynomials in Supertropical Algebra” membahas mengenai matriks pseudo-invers atas aljabar supertropical, polinomial karakteristik dan nilai eigen dari matriks pseudo-invers atas aljabar supertropical [16], akan tetapi dalam penelitian tersebut belum dibahas pengembangannya pada sistem persamaan linear. Sistem persamaan linear merupakan salah satu permasalahan penting dalam matematika karena sebagian besar masalah matematika yang dijumpai dalam aplikasi ilmiah maupun industri melibatkan penyelesaian sistem persamaan linear. Dalam aljabar linear telah diketahui bahwa sistem persamaan linear terbagi menjadi sistem persamaan linear homogen dan tak homogen. Suatu sistem persamaan linear dalam keterkaitannya dengan solusi, mempunyai tiga kemungkinan diantaranya mempunyai solusi tunggal, solusi banyak dan tidak mempunyai solusi. Keberadaan solusi ini sangat tergantung dari sistem persamaan linear itu sendiri. Sebagai pengembangan dari teori matriks aljabar supertropical maka pada penelitian ini akan dilakukan pembahasan mengenai karakterisasi penyelesaian sistem persamaan linear tak homogen dan sistem persamaan linear homogen atas aljabar supertropical.
1.2
Rumusan Masalah Berdasarkan latar belakang yang telah diuraikan, pokok permasalahan
yang dikaji dalam penelitian ini sebagai berikut. 1.
Bagaimana karakterisasi penyelesaian sistem persamaan linear tak homogen atas aljabar supertropical ?
2.
Bagaimana karakterisasi penyelesaian sistem persamaan linear homogen atas aljabar supertropical ?
1.3
Batasan Masalah Agar permasalahan dalam penelitian ini dapat terfokus dan sesuai dengan
waktu yang direncanakan, maka perlu dilakukan pembatasan masalah. Batasan yang diberikan dalam penelitian ini adalah matriks yang dibahas adalah matriks persegi.
3
1.4
Tujuan Penelitian Berdasarkan rumusan masalah di atas, tujuan dari penelitian ini adalah
sebagai berikut. 1.
Menentukan karakterisasi penyelesaian sistem persamaan linear tak homogen atas aljabar supertropical.
2.
Menentukan karakterisasi penyelesaian sistem persamaan linear homogen atas aljabar supertropical.
1.5
Manfaat Penelitian Manfaat dari penelitian ini adalah sebagai berikut.
1.
Sebagai salah satu referensi bagi peneliti yang berminat mengembangkan penelitian khususnya mengenai sistem persamaan linear atas aljabar supertropical.
2.
Sebagai pengembangan ilmu aljabar khususnya aljabar supertropical.
4
BAB II KAJIAN PUSTAKA DAN DASAR TEORI
Pada bab ini dijelaskan mengenai kajian pustaka dan landasan teori yang berkaitan dengan penelitian. Kajian pustaka dan landasan teori tersebut meliputi definisi yang menjadi dasar dalam pembahasan pada bab selanjutnya. Pada definisidefinisi tersebut akan diberikan contoh untuk mempertegas maksud dari definisi tersebut. Bagian pertama pada bab ini akan dibahas mengenai penelitian terdahulu, selanjutnya akan dibahas mengenai semiring, aljabar max-plus, aljabar tropical, aljabar supertropical, matriks atas semiring supertropical dan sistem persamaan linear atas aljabar supertropical.
1.1 Penelitian Terdahulu Aljabar max-plus merupakan suatu struktur aljabar (ℝ𝜀 ⊕,⊗ ) yang tidak mempunyai elemen invers terhadap operasi ⊕. Dengan kata lain jika 𝑎 ∈ ℝ𝜀 maka tidak ada 𝑏 ∈ ℝ𝜀 sehingga 𝑎 ⊕ 𝑏 = 𝑏 ⊕ 𝑎 = 𝜀 , kecuali jika 𝑎 = 𝜀 dengan 𝜀 adalah elemen nol. Selanjutnya, Izhakian (2009) dalam jurnal Communications in Algebra melakukan penelitian yang berjudul “Tropical Arithmetic and Matrix Algebra”, penelitian tersebut secara khusus memperkenalkan struktur baru yang merupakan perluasan dari aljabar max-plus yang disebut extended semiring tropical [3]. Selanjutnya, perluasan dari aljabar tropical secara umum dinamakan aljabar supertropical. Aljabar supertropical merupakan teori yang relatif baru. Sampai saat ini penelitian mengenai aljabar supertropical telah mengalami perkembangan. Berikut beberapa penelitian mengenai aljabar supertropical diantaranya Izhakian dan Rowen (2010) dalam Advances in Mathematics meneliti tentang “Supertropical Algebra”. Jurnal tersebut menjelaskan dasar-dasar teori atas aljabar supertropical serta faktorisasi polinomial atas aljabar supertropical yaitu setiap polinomial atas aljabar supertropical dapat difaktorkan baik dalam bentuk linier maupun kuadrat [4].
5
Selanjutnya Izhakian dan Rowen (2011) dalam Israel Journal Mathematics melakukan penelitian yang berjudul “Supertropical Matrix Algebra. Jurnal tersebut membahas mengenai teori matriks atas aljabar supertropical yaitu jika |𝐴| dan |𝐵| keduanya tangible maka |𝐴 ⊗ 𝐵| = |𝐴| ⊗ |𝐵|, selain itu |𝐴| adalah elemen ghost jika baris atau kolom dari 𝐴 bergantung linier [7]. Masih pada tahun 2011, Izhakian dan Rowen dalam “Supertropical Matrix Algebra II”, Israel Journal Mathematics secara khusus membahas mengenai eksistensi adj 𝐴 dari matriks non singular sehingga didapatkan pseudo-invers kanan dan pseudo-invers kiri yang tunggal sehubungan dengan matriks pseudo-identitas yang bersesuaian dengan 𝐴. Selain itu juga dibahas sifat adjoint dan penerapannya untuk menghitung vektor eigen atas aljabar supertropical [8]. Selanjutnya peneliti lain yaitu Adi Niv (2015) dalam Journal Linear Algebra and Its Applications melakukan penelitian yang berjudul “On Pseudo-Inverses of Matrices and Their Characteristic Polynomials in Supertropical Algebra. Jurnal
tersebut membahas mengenai
matriks pseudo-invers atas aljabar supertropical, selain itu juga membahas polinomial karakteristik dan nilai eigen dari matriks pseudo-invers atas aljabar supertropical [16].
1.2 Semiring Definisi 2.1. [17]. Semiring (𝑆, +, ×) adalah suatu himpunan tak kosong 𝑆 disertai dengan dua operasi biner + yang mempunyai makna penjumlahan dan × yang mempunyai makna perkalian yang memenuhi aksioma berikut : 1. (𝑆, +) adalah semigrup komutatif dengan elemen netral 0, yaitu ∀ 𝑎, 𝑏, 𝑐 ∈ 𝑆 memenuhi : 𝑎+𝑏 =𝑏+𝑎 (𝑎 + 𝑏 ) + 𝑐 = 𝑎 + (𝑏 + 𝑐 ) 𝑎+0 =0+𝑎 = 𝑎 2. (𝑆, ×) adalah semigrup dengan elemen satuan 1, yaitu ∀ 𝑎, 𝑏, 𝑐 ∈ 𝑆 memenuhi: (𝑎 × 𝑏) × 𝑐 = 𝑎 × (𝑏 × 𝑐) 𝑎×1 = 1×𝑎 = 𝑎 3. Sifat penyerapan elemen netral 0 terhadap operasi ×, yaitu ∀ 𝑎 ∈ 𝑆 memenuhi : 6
𝑎×0= 0×𝑎 = 0 4. Operasi distributif × terhadap +, yaitu ∀ 𝑎, 𝑏, 𝑐 ∈ 𝑆 berlaku : (𝑎 + 𝑏 ) × 𝑐 = (𝑎 × 𝑐 ) + (𝑏 × 𝑐 ) 𝑎 × ( 𝑏 + 𝑐 ) = (𝑎 × 𝑏 ) + (𝑎 × 𝑐 )
□
Definisi 2.2. [17]. Suatu semiring (𝑆, +, ×) disebut semiring komutatif jika terhadap operasi × bersifat komutatif, yaitu ∀ 𝑎, 𝑏 ∈ 𝑆 maka 𝑎 × 𝑏 = 𝑏 × 𝑎. □ Definisi 2.3. [17]. Semiring idempoten adalah suatu semiring (𝑆, +, ×) dimana pada operasi penjumlahannya berlaku 𝑎 + 𝑎 = 𝑎, ∀ 𝑎 ∈ 𝑆. □ Definisi 2.4. [17]. Suatu semiring (𝑆, +, ×) dikatakan semifield jika setiap elemen 𝑎 di 𝑆 − {0} mempunyai invers terhadap operasi ×, yaitu untuk setiap 𝑎 di 𝑆 − {0} terdapat 𝑎−1 sedemikian hingga 𝑎 × 𝑎−1 = 𝑎−1 × 𝑎 = 1. □ Contoh 2.1. Diberikan himpunan ℝ𝜀 = ℝ ∪ {𝜀} dengan ℝ adalah himpunan semua bilangan real dan 𝜀 ≝ −∞ beserta operasi biner ⊕ dan ⊗ yang didefinisikan sebagai berikut : 𝑎 ⊕ 𝑏 = max {𝑎, 𝑏} dan 𝑎 ⊗ 𝑏 = 𝑎 + 𝑏, ∀ 𝑎, 𝑏 ∈ ℝ𝜀 . Dapat ditunjukkan bahwa (ℝ𝜀 , ⊕, ⊗) merupakan semiring idempoten sekaligus semifield dengan elemen netral 𝜀 = −∞ dan elemen satuan e = 0. Maka untuk ∀ 𝑎, 𝑏, 𝑐 ∈ ℝ𝜀 berlaku : i.
(ℝ𝜀 , ⊕) adalah semigrup komutatif 𝑎⨁𝑏=𝑏⨁𝑎 (𝑎 ⨁ 𝑏) ⨁ 𝑐 = 𝑎 ⨁ (𝑏 ⨁ 𝑐) 𝑎⨁𝜀 =𝜀⨁𝑎=𝑎
ii.
(ℝ𝜀 , ⊗) adalah semigrup komutatif 𝑎⊗𝑏 =𝑏⊗𝑎 (𝑎 ⊗ 𝑏) ⊗ 𝑐 = 𝑎 ⊗ (𝑏 ⊗ 𝑐) 𝑎⊗𝑒 =𝑒⊗𝑎 =𝑎
7
iii.
Elemen netral 𝜀 merupakan elemen penyerap terhadap operasi perkalian 𝑎⊗𝜀 = 𝜀⊗𝑎 =𝜀
iv.
Distributif operasi perkalian terhadap penjumlahan (𝑎 ⨁ 𝑏) ⊗ 𝑐 = (𝑎 ⊗ 𝑐) ⨁ (𝑏 ⊗ 𝑐) 𝑎 ⊗ (𝑏 ⨁ 𝑐 ) = (𝑎 ⊗ 𝑏) ⨁ (𝑎 ⊗ 𝑐) Selanjutnya akan ditunjukkan bahwa (ℝ𝜀 , ⊕, ⊗) merupakan semiring
komutatif dan idempoten. Untuk setiap 𝑎, 𝑏 ∈ ℝ𝜀 maka berlaku 𝑎 ⊗ 𝑏 = 𝑏 ⊗ 𝑎 dan 𝑎 ⨁ 𝑎 = max {𝑎, 𝑎} = 𝑎. Selain itu aljabar (ℝ𝜀 , ⊕, ⊗) juga merupakan semifield, sebab untuk setiap 𝑎 ∈ ℝ terdapat – 𝑎 sehingga 𝑎 ⊗ (−𝑎) = 𝑎 + (−𝑎) = 0. ◊ Selanjutnya, untuk lebih ringkasnya maka penulisan semiring (𝑆, +, ×) dituliskan sebagai 𝑆. Definisi 2.5. Diberikan semiring 𝑅 dan 𝑆. Pemetaan 𝑓 ∶ 𝑅 → 𝑆 dikatakan homomorfisma jika ∀ 𝑎, 𝑏 ∈ 𝑅 berlaku : 𝑓 (𝑎 + 𝑏) = 𝑓(𝑎) + 𝑓(𝑏) 𝑓 (𝑎 × 𝑏) = 𝑓 (𝑎) × 𝑓(𝑏) Perlu diperhatikan bahwa operasi biner + pada 𝑎 + 𝑏 pada umumnya tidak sama pada 𝑓 (𝑎) + 𝑓(𝑏) begitu juga operasi biner × pada 𝑎 × 𝑏 pada umumnya tidak sama pada 𝑓(𝑎) × 𝑓(𝑏). Homomorfisma 𝑓 dinamakan idempoten bila 𝑓 2 = 𝑓. □
1.3 Aljabar Max-Plus Pada bagian ini akan dibahas beberapa definisi dasar dari aljabar max-plus. Definisi 2.6. [18]. Aljabar max-plus adalah suatu himpunan tidak kosong ℝ𝜀 = ℝ ∪ {𝜀} dengan ℝ adalah himpunan semua bilangan real dan 𝜀 ≝ −∞ disertai dua operasi biner yang didefinisikan sebagai berikut : 𝑎 ⊕ 𝑏 ≝ max {𝑎, 𝑏} dan 𝑎 ⊗ 𝑏 ≝ 𝑎 + 𝑏, ∀ 𝑎, 𝑏 ∈ ℝ𝜀 □
8
Selanjutnya, aljabar max-plus (ℝ𝜀 , ⨁, ⊗) cukup dituliskan dengan ℝmax . Berikut ini adalah sifat-sifat yang berlaku dalam aljabar max-plus. Untuk ∀ 𝑎, 𝑏, 𝑐 ∈ ℝmax berlaku : 1.
Assosiatif (𝑎 ⨁ 𝑏) ⨁ 𝑐 = 𝑎 ⨁ (𝑏 ⨁ 𝑐) (𝑎 ⊗ 𝑏) ⊗ 𝑐 = 𝑎 ⊗ (𝑏 ⊗ 𝑐)
2.
Komutatif 𝑎 ⨁ 𝑏 = 𝑏 ⨁ 𝑎 dan 𝑎 ⊗ 𝑏 = 𝑏 ⊗ 𝑎
3.
Distributif ⊗ terhadap ⨁ 𝑎 ⊗ (𝑏 ⨁ 𝑐 ) = (𝑎 ⊗ 𝑏) ⨁ (𝑎 ⊗ 𝑐)
4.
Eksistensi elemen nol, yaitu 𝜀 𝑎⨁𝜀 =𝜀⨁𝑎 =𝑎
5.
Eksistensi elemen satuan, yaitu 𝑒 𝑎⊗𝑒 =𝑒⊗𝑎 =𝑎
6.
Idempoten terhadap ⨁ 𝑎⨁𝑎=𝑎
7.
Sifat penyerapan elemen nol 𝜀 terhadap operasi ⊗ 𝑎 ⊗ 𝑒 = 𝑒 ⊗ 𝑎 = 𝑎.
Aljabar max-plus ℝmax merupakan semiring komutatif dan idempotent, sebab untuk setiap 𝑎, 𝑏 ∈ ℝ𝜀 maka berlaku 𝑎 ⊗ 𝑏 = 𝑏 ⊗ 𝑎 dan 𝑎 ⨁ 𝑎 = max {𝑎, 𝑎} = 𝑎. Selain itu aljabar max-plus ℝmax juga merupakan semifield, sebab untuk setiap 𝑎 ∈ ℝ terdapat – 𝑎 sehingga 𝑎 ⊗ (−𝑎) = 𝑎 + (−𝑎) = 0. Untuk bilangan bulat tak negatif 𝑛, pangkat dari 𝑥 ∈ ℝmax dalam aljabar max-plus dinyatakan sebagai berikut : 𝑒 , 𝑥 ⊗𝑛 = {𝑥 ⏟⊗ 𝑥 ⊗ … ⊗ 𝑥 ,
untuk 𝑛 = 0 untuk 𝑛 > 0
𝑛
sehingga dapat dituliskan 𝑥 ⊗𝑛 = ⏟ 𝑥 ⊗ 𝑥 ⊗ …⊗ 𝑥 = 𝑛 × 𝑥 𝑛
9
Contoh 2.2. Berikut ini diberikan contoh operasi ⨁ dan ⊗ dalam aljabar max-plus. 1
Misal diambil 𝑎 = 9, 𝑏 = 8, 𝑐 = 3 dengan 𝑎, 𝑏, 𝑐 ∈ ℝmax , maka 1.
𝑎 ⊕ 𝑏 = 9 ⊕ 8 = max {9,8} = 9.
2.
𝑎 ⊗ 𝑏 = 9 ⊗ 8 = 9 + 8 = 17.
3.
𝑎⊗𝑏 = 9⊗8 = 8 × 9 = 72.
4.
𝑎⊗𝑐 = 9⊗3 = 3 × 9 = 3.
1.3.1
1
1
◊
Matriks atas Aljabar Max-Plus Himpunan semua matriks berukuran 𝑚 × 𝑛 atas aljabar max-plus
dinotasikan sebagai ℝ𝑚×𝑛 max yaitu suatu matriks berukuran 𝑚 × 𝑛 dengan entri-entri matriks merupakan anggota ℝmax . Untuk 𝑚, 𝑛 ∈ ℕ dengan 𝑚 ≠ 0 dan 𝑛 ≠ 0. Operasi penjumlahan dan perkalian pada matriks ℝ𝑚×𝑛 max merupakan perluasan operasi biner ⊕ dan ⊗ pada ℝmax .
1.3.2
Penjumlahan Matriks
Penjumlahan matriks 𝐴, 𝐵 ∈ ℝ𝑚×𝑛 max dinotasikan sebagai 𝐴 ⊕ 𝐵 didefinisikan oleh : [𝐴 ⊕ 𝐵]𝑖,𝑗 = [𝑎𝑖,𝑗 ⊕ 𝑏𝑖,𝑗 ] = max {𝑎𝑖,𝑗 , 𝑏𝑖,𝑗 } untuk 𝑖 ∈ 𝑚 dan 𝑗 ∈ 𝑛, dengan 𝑚 = {1, 2, … , 𝑚} dan 𝑛 = {1, 2, … , 𝑛}. Contoh 2.3. 1 Diberikan matriks 𝐴 = [8 4
2 3 7
5 5 2 ] [ dan 𝐵 = 8 6 1 2 2 4
7 3] dimana 𝐴, 𝐵 ∈ ℝ𝑛×𝑛 max 1
maka [𝐴 ⊕ 𝐵]1,1 = 1 ⊕ 5 = 5 [𝐴 ⊕ 𝐵]1,2 = 2 ⊕ 2 = 2 [𝐴 ⊕ 𝐵]1,3 = 5 ⊕ 7 = 7 [𝐴 ⊕ 𝐵]2,1 = 8 ⊕ 6 = 8 [𝐴 ⊕ 𝐵]2,2 = 3 ⊕ 1 = 3 10
[𝐴 ⊕ 𝐵]2,3 = 8 ⊕ 3 = 8 [𝐴 ⊕ 𝐵]3,1 = 4 ⊕ 2 = 4 [𝐴 ⊕ 𝐵]3,2 = 7 ⊕ 4 = 7 [𝐴 ⊕ 𝐵]3,3 = 2 ⊕ 1 = 2 dengan menggunakan notasi matriks didapat 5 𝐴 ⊕ 𝐵 = [8 4
2 7 3 8] 7 2 ◊
1.3.3
Perkalian Matriks
Untuk sebarang matriks 𝐴 ∈ ℝ𝑚×𝑛 max dan skalar 𝜆 ∈ ℝmax maka perkalian 𝜆 ⊗ 𝐴 didefinisikan sebagai [𝜆 ⊗ 𝐴]𝑖,𝑗 = 𝜆 ⊗ 𝑎𝑖,𝑗 untuk 𝑖 ∈ 𝑚 dan 𝑗 ∈ 𝑛, dengan 𝑚 = {1, 2, … , 𝑚} dan 𝑛 = {1, 2, … , 𝑛}. 𝑝×𝑛 Untuk sebarang matriks 𝐴 ∈ ℝ𝑚×𝑝 max dan 𝐵 ∈ ℝmax
perkalian matriks 𝐴 ⊗ 𝐵
didefinisikan sebagai : 𝑝
[𝐴 ⊗ 𝐵]𝑖,𝑗 = ⨁ 𝑎𝑖,𝑘 ⊗ 𝑏𝑘,𝑗 𝑘=1
untuk 𝑖 ∈ 𝑚 dan 𝑗 ∈ 𝑛, dengan 𝑚 = {1, 2, … , 𝑚} dan 𝑛 = {1, 2, … , 𝑛}. Contoh 2.4. 5 3 Diberikan matriks 𝐴 = [8 4 5 8 maka
7 3] dan skalar 𝜆 = 5 dimana ∈ ℝ𝑛×𝑛 max , 𝜆 ∈ ℝmax 9
𝜆 ⊗ 𝑎1,1 = 5 ⊗ 5 = 10 𝜆 ⊗ 𝑎1,2 = 5 ⊗ 3 = 8 𝜆 ⊗ 𝑎1,3 = 5 ⊗ 7 = 12 𝜆 ⊗ 𝑎2,1 = 5 ⊗ 8 = 13 𝜆 ⊗ 𝑎2,2 = 5 ⊗ 4 = 9
11
𝜆 ⊗ 𝑎2,3 = 5 ⊗ 3 = 8 𝜆 ⊗ 𝑎3,1 = 5 ⊗ 5 = 10 𝜆 ⊗ 𝑎3,2 = 5 ⊗ 8 = 13 𝜆 ⊗ 𝑎3,3 = 5 ⊗ 9 = 14 dengan menggunakan notasi matriks didapat 10 8 12 𝜆 ⊗ 𝐴 = [13 9 8] 10 13 14 ◊
1.3.4
Perpangkatan Matriks
Untuk sebarang matriks persegi 𝐴 ∈ ℝ𝑛×𝑛 max dan 𝑘 bilangan bulat positif, pangkat ke𝑘 dari 𝐴 dinotasikan sebagai : 𝐴⊗𝑘 = 𝐴 ⏟⊗ 𝐴 ⊗ 𝐴 ⊗ … ⊗ 𝐴 𝑘
untuk 𝑘 ∈ ℕ dengan 𝑘 ≠ 0 dan 𝐴⊗0 = 𝐼𝑛 . Contoh 2.5. 1 9 Diberikan matriks 𝐴 = [7 4 5 8 maka 𝐴
⊗2
5 2] dimana 𝐴 ∈ ℝ𝑛×𝑛 max 9 1 = 𝐴 ⊗ 𝐴 = [7 5
9 4 8
5 1 2 ] ⊗ [7 9 5
9 4 8
5 2] 9
[𝐴 ⊗ 𝐴]1,1 = (1 ⊗ 1) ⊕ (9 ⊗ 7) ⊕ (5 ⊗ 5) = 2 ⊕ 16 ⊕ 10 = 16 [𝐴 ⊗ 𝐴]1,2 = (1 ⊗ 9) ⊕ (9 ⊗ 4) ⊕ (5 ⊗ 8) = 10 ⊕ 13 ⊕ 13 = 13 [𝐴 ⊗ 𝐴]1,3 = (1 ⊗ 5) ⊕ (9 ⊗ 2) ⊕ (5 ⊗ 9) = 6 ⊕ 11 ⊕ 14 = 14 [𝐴 ⊗ 𝐴]2,1 = (7 ⊗ 1) ⊕ (4 ⊗ 7) ⊕ (2 ⊗ 5) = 8 ⊕ 11 ⊕ 7 = 11 [𝐴 ⊗ 𝐴]2,2 = (7 ⊗ 9) ⊕ (4 ⊗ 4) ⊕ (2 ⊗ 8) = 16 ⊕ 8 ⊕ 10 = 16 [𝐴 ⊗ 𝐴]2,3 = (7 ⊗ 5) ⊕ (4 ⊗ 2) ⊕ (2 ⊗ 9) = 12 ⊕ 6 ⊕ 11 = 12 [𝐴 ⊗ 𝐴]3,1 = (5 ⊗ 1) ⊕ (8 ⊗ 7) ⊕ (9 ⊗ 5) = 6 ⊕ 15 ⊕ 14 = 15 [𝐴 ⊗ 𝐴]3,2 = (5 ⊗ 9) ⊕ (8 ⊗ 4) ⊕ (9 ⊗ 8) = 14 ⊕ 12 ⊕ 17 = 17 [𝐴 ⊗ 𝐴]3,3 = (5 ⊗ 5) ⊕ (8 ⊗ 2) ⊕ (9 ⊗ 9) = 10 ⊕ 10 ⊕ 18 = 18 dengan menggunakan notasi matriks didapat
12
16 13 14 𝐴⊗2 = [11 16 12] 15 17 18 ◊
1.3.5
Transpose Matriks
𝑇 Transpose dari matriks 𝐴 ∈ ℝ𝑚×𝑛 max dinotasikan dengan 𝐴 , didefinisikan sebagai
[𝐴𝑇 ]𝑖,𝑗 = [𝑎𝑗,𝑖 ] untuk 𝑖 ∈ 𝑚 dan 𝑗 ∈ 𝑛, dengan 𝑚 = {1, 2, … , 𝑚} dan 𝑛 = {1, 2, … , 𝑛}. Contoh 2.6. 1 2 [ Diberikan matriks 𝐴 = 2 4 5 6
8 2] dimana 𝐴 ∈ ℝ𝑛×𝑛 max 1
maka transpose dari matriks 𝐴 : 1 𝐴𝑇 = [2 8
2 4 2
5 6]. 1 ◊
1.3.6
Matriks Identitas
Matriks identitas 𝐼 merupakan matriks persegi 𝑛 × 𝑛 yang didefinisikan sebagai berikut : [𝐼 ]𝑖,𝑗 = {
𝑒, untuk 𝑖 = 𝑗 𝜀, lainnya
untuk 𝑖 ∈ 𝑛 dan 𝑗 ∈ 𝑛 , dengan 𝑛 = {1, 2, … , 𝑛}.
1.4 Aljabar Tropical Definisi 2.7. [2]. Aljabar tropical adalah suatu semiring idempotent sekaligus semifield.
□
Contoh 2.3. Diberikan aljabar max-plus ℝmax = (ℝ𝜀 , ⊕, ⊗) dimana ℝ𝜀 = ℝ ∪ {𝜀} dengan ℝ adalah himpunan semua bilangan real dan 𝜀 ≝ −∞ beserta operasi biner ⊕ dan ⊗ yang didefinisikan sebagai berikut : 𝑎 ⊕ 𝑏 = max {𝑎, 𝑏} 𝑎 ⊗ 𝑏 = 𝑎 + 𝑏, ∀ 𝑎, 𝑏 ∈ ℝ𝜀 .
13
Berdasarkan Definisi 2.6 aljabar max-plus ℝmax merupakan semiring idempoten sekaligus semifield. Dengan demikian aljabar max-plus ℝmax adalah aljabar tropical.
1.5 Perluasan Aljabar Tropical Berikut ini akan dijelaskan perluasan dari aljabar tropical dengan mengambil kasus khusus dari aljabar tropical yaitu aljabar maxplus. Aljabar max-plus ℝmax merupakan struktur aljabar yang tidak mempunyai elemen invers terhadap operasi ⊕. Dengan kata lain jika 𝑎 ∈ ℝ𝜀 maka tidak ada 𝑏 ∈ ℝ𝜀 sehingga ⊕ 𝑏 = 𝑏 ⊕ 𝑎 = 𝜀 , kecuali jika 𝑎 = 𝜀 dengan 𝜀 adalah elemen nol. Teorema 2.1. [17]. Diberikan semiring ℝmax = (ℝ𝜀 , ⊕, ⊗). Idempoten dari ⊕ berakibat bahwa elemen invers terhadap operasi ⊕ tidak ada. Bukti : Misalkan bahwa 𝑎 ≠ 𝜀 mempunyai suatu invers terhadap ⊕ yaitu 𝑏, didapat 𝑎⊕𝑏= 𝜀 tambahkan 𝑎 pada kedua ruas persamaan, didapat 𝑎 ⊕ (𝑎 ⊕ 𝑏 ) = 𝑎 ⊕ 𝜀 (𝑎 ⊕ 𝑎 ) ⊕ 𝑏 = 𝑎 ⊕ 𝜀 dengan sifat idempoten, persamaan menjadi 𝑎⊕𝑏 =𝑎 hal ini bertentangan dengan kenyataan bahwa 𝑎 ⊕ 𝑏 = 𝜀 dan 𝑎 ≠ 𝜀.
∎
Selanjutnya, aljabar max-plus dikembangkan menjadi struktur semiring yang lebih luas yang disebut extended semiring tropical dengan memunculkan elemen baru yaitu elemen ghost. Definisi 2.8. [4]. Extended semiring tropical dinotasikan sebagai (𝑇, ⊕, ⊗) dengan 𝑇 = ℝ ∪ {−∞} ∪ ℝ𝑣 , dimana ℝ adalah himpunan semua bilangan real dan ℝ𝑣 = {𝑎𝑣 : 𝑎 ∈ ℝ}. Elemen netral pada 𝑇 adalah 𝜀 ≝ −∞ dan elemen satuan □
𝑒 ≝ 0.
14
Dalam hal ini ℝ𝑣−∞ = ℝ𝑣 ∪ {−∞} merupakan ideal dari 𝑇 disebut ideal ghost. Sedangkan pemetaan 𝑣 ∶ 𝑇 → ℝ𝑣−∞ disebut pemetaan ghost. Untuk setiap 𝑥 ∈ ℝ𝑣−∞ maka 𝑣(𝑥 ) = 𝑥 merupakan pemetaan identitas dan untuk setiap 𝑎 ∈ ℝ maka 𝑣 (𝑎 ) = 𝑎 𝑣 . Definisi 2.9. [3]. Diberikan Extended semiring tropical 𝑇. Didefinisikan relasi urutan parsial ≺ pada 𝑇 sebagai berikut : Untuk ∀ 𝑎, 𝑏 ∈ ℝ , ∀ 𝑎𝑣 , 𝑏𝑣 ∈ ℝ𝑣 dan ∀ 𝑥, 𝑦 ∈ 𝑇 berlaku : 1.
−∞ ≺ 𝑥, ∀ 𝑥 ∈ 𝑇 \ {−∞}.
2.
Untuk setiap bilangan real 𝑎 ≺ 𝑏 maka 𝑎 ≺ 𝑏, 𝑎 ≺ 𝑏𝑣 , 𝑎𝑣 ≺ 𝑏, dan 𝑎𝑣 ≺ 𝑏𝑣 .
3.
𝑎 ≺ 𝑎𝑣 untuk setiap 𝑎 ∈ ℝ.
□
Aksioma 2.1. [3]. Diberikan Extended semiring tropical 𝑇. Notasi 𝑚𝑎𝑥≺ adalah maksimum pada urutan ≺. Operasi biner ⊕ dan ⊗ pada 𝑇 memenuhi aksioma sebagai berikut. Untuk ∀ 𝑎, 𝑏 ∈ ℝ , ∀ 𝑎𝑣 , 𝑏𝑣 ∈ ℝ𝑣 dan ∀ 𝑥, 𝑦 ∈ 𝑇 maka 1.
−∞ ⊕ 𝑥 = 𝑥 ⊕ −∞ = 𝑥 untuk setiap 𝑥 ∈ 𝑇.
2.
𝑥 ⊕ 𝑦 = max
3.
𝑎 ⊕ 𝑎 = 𝑎𝑣 ⊕ 𝑎𝑣 = 𝑎 ⊕ 𝑎𝑣 = 𝑎𝑣 ⊕ 𝑎 = 𝑎𝑣 .
4.
−∞ ⊗ 𝑥 = 𝑥 ⊗ −∞ = −∞ untuk setiap 𝑥 ∈ 𝑇.
5.
𝑎 ⊗ 𝑏 = 𝑎 + 𝑏 untuk semua 𝑎, 𝑏 ∈ ℝ.
6.
𝑎𝑣 ⊗ 𝑏 = 𝑎 ⊗ 𝑏𝑣 = 𝑎𝑣 ⊗ 𝑏𝑣 = (𝑎 + 𝑏)𝑣 .
≺
{𝑥, 𝑦} kecuali 𝑥 = 𝑦.
□
Contoh 2.7. Berikut ini diberikan contoh operasi biner ⨁ dan ⊗ yang berlaku dalam extended semiring tropical 𝑇. 1.
−∞ ⊕ 5 = 5 ⊕ −∞ = 5
2.
2 ⊕ 5 = max
3.
2 ⊕ 2 = 2𝑣 ⊕ 2𝑣 = 2 ⊕ 2𝑣 = 2𝑣 ⊕ 2 = 2𝑣
4.
−∞ ⊗ 5 = 5 ⊗ −∞ = −∞
5.
8 ⊗ 6 = 8 + 6 = 14
6.
5 𝑣 ⊗ 4 = 5 ⊗ 4𝑣 = 5𝑣 ⊗ 4𝑣 = (5 + 4)𝑣 = 9𝑣
≺
{2,5} = 5
1.6 Aljabar Supertropical 15
◊
Perluasan dari aljabar tropical secara umum dinamakan aljabar supertropical. Struktur dari semiring supertropical merupakan perumuman dari 𝑇. Diberikan semiring 𝑅 ≝ 𝒯 ∪ {−∞} ∪ 𝒢 dan suatu ideal 𝒢0 ≝ 𝒢 ∪ {−∞} disebut ideal ghost yang merupakan ideal dari semiring 𝑅. Pemetaan 𝑣 ∶ 𝑅 → 𝒢0 disebut pemetaan ghost, pemetaan 𝑣 merupakan pemetaan homomorfisma idempoten yang memenuhi 𝑣(𝑥 ) = 𝑥 ⊕ 𝑥, ∀ 𝑥 ∈ 𝑅 dan 𝑣 2 (𝑥 ) = 𝑣(𝑥 ). Dalam hal ini 𝒯 = 𝑅 ∖ 𝒢0 adalah himpunan yang anggotanya elemen tangible. Sedangkan 𝒢 adalah himpunan yang anggotanya merupakan elemen ghost.
1.6.1
Semiring dengan Ghost
Definisi 2.10. [19]. Semiring dengan ghost (𝑅, 𝒢0 , 𝑣) adalah semiring 𝑅 (dengan elemen netral 0𝑅 dan elemen satuan 1𝑅 ), 𝒢0 = 𝒢 ∪ 0𝑅 disebut ideal ghost, sedangkan 𝑣 ∶ 𝑅 → 𝒢0 disebut pemetaan ghost yang memenuhi : 𝑣(𝑥 ) = 𝑥 ⊕ 𝑥,
□
∀𝑥 ∈𝑅
Untuk ∀ 𝑥 ∈ 𝒢0 , pemetaan ghost merupakan pemetaan identitas yang memenuhi 𝑣 (𝑥 ) = 𝑥
, ∀ 𝑥 ∈ 𝒢0
Pemetaan ghost merupakan pemetaan homomorfisma idempoten yang memenuhi 𝑣 2 (𝑥 ) = 𝑣 (𝑥 ),
1.6.2
∀𝑥 ∈ 𝑅
Semiring Supertropical
Definisi 2.11. [19]. Semiring supertropical merupakan semiring dengan ghost (𝑅, 𝒢0 , 𝑣) yang memenuhi beberapa sifat tambahan yaitu ∀ 𝑎, 𝑏 ∈ 𝑅 berlaku : jika 𝑎𝑣 = 𝑏𝑣 maka 𝑎 ⊕ 𝑏 = 𝑎𝑣 dan jika 𝑎 ≠ 𝑏 maka 𝑎 ⊕ 𝑏 ∈ {𝑎, 𝑏}
□
Contoh 2.8 Diberikan Extended semiring tropical dinotasikan (𝑇, ⊕, ⊗ ) dengan 𝑇 = ℝ ∪ {−∞} ∪ ℝ𝑣 , dimana ℝ adalah himpunan semua bilangan real dan ℝ𝑣 = {𝑎𝑣 : 𝑎 ∈ ℝ}. Elemen netral pada 𝑇 adalah 𝜀 ≝ −∞ dan elemen satuan 𝑒 ≝ 0. Dalam hal ini ℝ𝑣−∞ = ℝ𝑣 ∪ {−∞} merupakan ideal dari 𝑇 disebut ideal ghost.
16
Sedangkan 𝑣 ∶ 𝑇 → ℝ𝑣−∞ disebut pemetaan ghost, untuk setiap 𝑥 ∈ ℝ𝑣−∞ maka 𝑣 (𝑥 ) = 𝑥 merupakan pemetaan identitas dan untuk setiap 𝑎 ∈ ℝ maka 𝑣 (𝑎) = 𝑎𝑣 . Dalam hal ini himpunan ℝ diidentifikasi sebagai 𝒯 yaitu himpunan yang anggotanya merupakan elemen tangible, ℝ𝑣 diidentifikasi sebagai 𝒢 yaitu himpunan yang anggotanya merupakan elemen ghost dan extended semiring tropical 𝑇 diidentifikasi sebagai 𝑅. Dengan demikian extended semiring tropical 𝑇 adalah kasus khusus dari semiring supertropical 𝑅.
◊
Kasus khusus dari semiring supertropical yang akan digunakan untuk pembahasan pada Bab IV adalah extended semiring tropical 𝑇 yang akan dituliskan sebagai 𝑅.
1.6.3
Relasi Ghost Surpass Pada semiring supertropical 𝑅, untuk setiap 𝑎 ∈ 𝑅 maka 𝑎 ⊕ 𝑎 = −∞
hanya berlaku untuk 𝑎 = −∞ sedangkan untuk setiap 𝑎 ∈ 𝒯 maka 𝑎 ⊕ 𝑎 = 𝑎𝑣 dan untuk setiap 𝑎 ∈ 𝒢 maka 𝑎 ⊕ 𝑎 = 𝑎. Selanjutnya akan diperkenalkan suatu relasi ghost surpass pada 𝑅 berikut ini. Definisi 2.12. [8]. Diberikan semiring supertropical 𝑅. Relasi ⊨ merupakan relasi ghost surpass pada 𝑅 yang didefinisikan sebagai berikut : 𝑎 ⊨ 𝑏 jika 𝑎 = 𝑏 ⊕ 𝑐 untuk beberapa 𝑐 ∈ 𝒢0 Berikut diberikan beberapa sifat relasi ghost surpass pada 𝑅. Untuk setiap 𝑎, 𝑏, 𝑐 ∈ 𝑅 berlaku : 1. Sifat antisimetri jika 𝑎 ⊨ 𝑏 dan 𝑏 ⊨ 𝑎, maka 𝑎 = 𝑏. 2. Sifat transitif jika 𝑎 ⊨ 𝑏 dan 𝑐 ⊨ 𝑑, maka 𝑎 ⊕ 𝑐 ⊨ 𝑏 ⊕ 𝑑 dan 𝑎 ⊗ 𝑐 ⊨ 𝑏 ⊗ 𝑑 3. Sifat tidak simetri untuk setiap 𝑎 ∈ 𝒯, 𝑎𝑣 ⊨ 𝑎 akan tetapi 𝑎 ⊭ 𝑎𝑣 .
Contoh 2.9. Berikut ini diberikan contoh sifat relasi ghost surpass pada 𝑅. 17
□
Untuk setiap 𝑎, 𝑏, 𝑐 ∈ 𝑅 berlaku : 1.
Untuk 𝑎 = 𝑏 = 8 maka 𝑎 ⊨ 𝑏 dan 𝑏 ⊨ 𝑎 berlaku sifat antisimetri.
2.
Untuk 6𝑣 ⊨ 5𝑣 dan 9 ⊨ 9 berlaku sifat transitif karena 6𝑣 ⊕ 9 ⊨ 5𝑣 ⊕ 9 ⟺ 9 ⊨ 9 dan 6𝑣 ⊗ 9 ⊨ 5𝑣 ⊗ 9 ⟺ 15𝑣 ⊨ 14𝑣 .
3.
Untuk 4 ∈ 𝒯 maka 4𝑣 ⊨ 4 akan tetapi 4 ⊭ 4𝑣 berlaku sifat tidak simetri. ◊
Selanjutnya, pada himpunan 𝑅 akan digunakan relasi ghost surpass ⊨ sebagai pengganti dari relasi " =”.
1.7 Matriks atas Semiring Supertropical Matriks persegi atas semiring supertropical dinotasikan sebagai 𝑀𝑛 (𝑅) yaitu suatu matriks berukuran 𝑛 × 𝑛 dengan entri-entri matriks merupakan anggota 𝑅. Operasi penjumlahan dan perkalian pada matriks 𝑀𝑛 (𝑅) merupakan perluasan operasi biner ⊕ dan ⊗ pada 𝑅. Selanjutnya, relasi ghost surpass pada 𝑅 juga dapat diperluas pada matriks 𝑀𝑛 (𝑅). Jika 𝐴 ⊨ 𝐵 maka 𝑎𝑖,𝑗 ⊨ 𝑏𝑖,𝑗 untuk setiap 𝑖 dan 𝑗.
1.7.1
Penjumlahan Matriks Penjumlahan
matriks
𝐴, 𝐵 ∈ 𝑀𝑚×𝑛 (𝑅) dinotasikan
sebagai
𝐴⊕𝐵
didefinisikan oleh : [𝐴 ⊕ 𝐵]𝑖,𝑗 = [𝑎𝑖,𝑗 ⊕ 𝑏𝑖,𝑗 ] untuk 𝑖 ∈ 𝑚 dan 𝑗 ∈ 𝑛.
Contoh 2.10. 1 Diberikan matriks 𝐴 = [7 5 maka
2 4 8
5 5 3 2] dan 𝐵 = [8 2 9 6 4
6 3] dimana 𝐴, 𝐵 ∈ 𝑀𝑛 (𝑅) 1
[𝐴 ⊕ 𝐵]1,1 = 1 ⊕ 5 = 5 [𝐴 ⊕ 𝐵]1,2 = 2 ⊕ 3 = 3 [𝐴 ⊕ 𝐵]1,3 = 5 ⊕ 6 = 6 [𝐴 ⊕ 𝐵]2,1 = 7 ⊕ 8 = 8 [𝐴 ⊕ 𝐵]2,2 = 4 ⊕ 2 = 4 18
[𝐴 ⊕ 𝐵]2,3 = 2 ⊕ 3 = 3 [𝐴 ⊕ 𝐵]3,1 = 5 ⊕ 6 = 6 [𝐴 ⊕ 𝐵]3,2 = 8 ⊕ 4 = 8 [𝐴 ⊕ 𝐵]3,3 = 9 ⊕ 1 = 9 dengan menggunakan notasi matriks didapat 5 𝐴 ⊕ 𝐵 = [8 6
3 6 4 3] 8 9 ◊
1.7.2
Perkalian Matriks
Untuk sebarang matriks 𝐴 ∈ 𝑀𝑚×𝑛 (𝑅) dan skalar 𝜆 ∈ 𝑅 maka perkalian 𝜆 ⊗ 𝐴 didefinisikan sebagai : [𝜆 ⊗ 𝐴]𝑖,𝑗 = 𝜆 ⊗ 𝑎𝑖,𝑗 untuk 𝑖 ∈ 𝑚 dan 𝑗 ∈ 𝑛. Untuk sebarang matriks 𝐴 ∈ 𝑀𝑚×𝑝 (𝑅) dan 𝐵 ∈ 𝑀𝑝×𝑛 (𝑅) perkalian matriks 𝐴 ⊗ 𝐵 didefinisikan sebagai : 𝑝
[𝐴 ⊗ 𝐵]𝑖,𝑗 = ⨁ 𝑎𝑖,𝑘 ⊗ 𝑏𝑘,𝑗 𝑘=1
untuk 𝑖 ∈ 𝑚 dan 𝑗 ∈ 𝑛.
Contoh 2.11. 5 3 Diberikan matriks 𝐴 = [8 4 5 8 maka
7 3] dan skalar 𝜆 = 2 dimana 𝐴 ∈ 𝑀𝑛 (𝑅) , 𝜆 ∈ 𝑅 9
𝜆 ⊗ 𝑎1,1 = 2 ⊗ 5 = 7 𝜆 ⊗ 𝑎1,2 = 2 ⊗ 3 = 5 𝜆 ⊗ 𝑎1,3 = 2 ⊗ 7 = 9 𝜆 ⊗ 𝑎2,1 = 2 ⊗ 8 = 10 𝜆 ⊗ 𝑎2,2 = 2 ⊗ 4 = 6 𝜆 ⊗ 𝑎2,3 = 2 ⊗ 3 = 5 𝜆 ⊗ 𝑎3,1 = 2 ⊗ 5 = 7 19
𝜆 ⊗ 𝑎3,2 = 2 ⊗ 8 = 10 𝜆 ⊗ 𝑎3,3 = 2 ⊗ 9 = 11 dengan menggunakan notasi matriks didapat 7 5 9 𝜆 ⊗ 𝐴 = [10 6 5] 7 10 11 ◊ Contoh 2.12. 1 Diberikan matriks 𝐴 = [7 5 maka
2 4 8
5 3 2 2] dan 𝐵 = [7 4 9 5 8
5 2] dimana 𝐴, 𝐵 ∈ 𝑀𝑛 (𝑅) 9
[𝐴 ⊗ 𝐵]1,1 = (1 ⊗ 3) ⊕ (2 ⊗ 7) ⊕ (5 ⊗ 5) = 4 ⊕ 9 ⊕ 10 = 10 [𝐴 ⊗ 𝐵]1,2 = (1 ⊗ 2) ⊕ (2 ⊗ 4) ⊕ (5 ⊗ 8) = 3 ⊕ 6 ⊕ 13 = 13 [𝐴 ⊗ 𝐵]1,3 = (1 ⊗ 5) ⊕ (2 ⊗ 2) ⊕ (5 ⊗ 9) = 6 ⊕ 4 ⊕ 14 = 14 [𝐴 ⊗ 𝐵]2,1 = (7 ⊗ 3) ⊕ (4 ⊗ 7) ⊕ (2 ⊗ 5) = 10 ⊕ 11 ⊕ 7 = 11 [𝐴 ⊗ 𝐵]2,2 = (7 ⊗ 2) ⊕ (4 ⊗ 4) ⊕ (2 ⊗ 8) = 9 ⊕ 8 ⊕ 10 = 10 [𝐴 ⊗ 𝐵]2,3 = (7 ⊗ 5) ⊕ (4 ⊗ 2) ⊕ (2 ⊗ 9) = 12 ⊕ 6 ⊕ 11 = 12 [𝐴 ⊗ 𝐵]3,1 = (5 ⊗ 3) ⊕ (8 ⊗ 7) ⊕ (9 ⊗ 5) = 8 ⊕ 15 ⊕ 14 = 15 [𝐴 ⊗ 𝐵]3,2 = (5 ⊗ 2) ⊕ (8 ⊗ 4) ⊕ (9 ⊗ 8) = 7 ⊕ 12 ⊕ 17 = 17 [𝐴 ⊗ 𝐵]3,3 = (5 ⊗ 5) ⊕ (8 ⊗ 2) ⊕ (9 ⊗ 9) = 10 ⊕ 10 ⊕ 18 = 18 dengan menggunakan notasi matriks didapat 10 𝐴 ⊗ 𝐵 = [11 15
13 14 10 12] 17 18 ◊
1.7.3
Perpangkatan Matriks
Untuk sebarang matriks persegi 𝐴 ∈ 𝑀𝑛 (𝑅) dan 𝑘 bilangan bulat positif, pangkat ke-𝑘 dari 𝐴 dinotasikan sebagai : 𝐴⊗𝑘 = ⏟ 𝐴 ⊗ 𝐴 ⊗ 𝐴 ⊗ …⊗ 𝐴 𝑘
untuk 𝑘 ∈ ℕ dengan 𝑘 ≠ 0 dan 𝐴⊗0 = 𝐼𝑛 .
20
Contoh 2.13. 1 2 Diberikan matriks 𝐴 = [7 4 5 8 maka
5 2] dimana 𝐴 ∈ 𝑀𝑛 (𝑅) 9
1 𝐴⊗2 = 𝐴 ⊗ 𝐴 = [7 5
2 4 8
1 5 2 ] ⊗ [7 5 9
2 4 8
5 2] 9
[𝐴 ⊗ 𝐴]1,1 = (1 ⊗ 1) ⊕ (2 ⊗ 7) ⊕ (5 ⊗ 5) = 2 ⊕ 9 ⊕ 10 = 10 [𝐴 ⊗ 𝐴]1,2 = (1 ⊗ 2) ⊕ (2 ⊗ 4) ⊕ (5 ⊗ 8) = 3 ⊕ 6 ⊕ 13 = 13 [𝐴 ⊗ 𝐴]1,3 = (1 ⊗ 5) ⊕ (2 ⊗ 2) ⊕ (5 ⊗ 9) = 6 ⊕ 4 ⊕ 14 = 14 [𝐴 ⊗ 𝐴]2,1 = (7 ⊗ 1) ⊕ (4 ⊗ 7) ⊕ (2 ⊗ 5) = 8 ⊕ 11 ⊕ 7 = 11 [𝐴 ⊗ 𝐴]2,2 = (7 ⊗ 2) ⊕ (4 ⊗ 4) ⊕ (2 ⊗ 8) = 9 ⊕ 8 ⊕ 10 = 10 [𝐴 ⊗ 𝐴]2,3 = (7 ⊗ 5) ⊕ (4 ⊗ 2) ⊕ (2 ⊗ 9) = 12 ⊕ 6 ⊕ 11 = 12 [𝐴 ⊗ 𝐴]3,1 = (5 ⊗ 1) ⊕ (8 ⊗ 7) ⊕ (9 ⊗ 5) = 6 ⊕ 15 ⊕ 14 = 15 [𝐴 ⊗ 𝐴]3,2 = (5 ⊗ 2) ⊕ (8 ⊗ 4) ⊕ (9 ⊗ 8) = 7 ⊕ 12 ⊕ 17 = 17 [𝐴 ⊗ 𝐴]3,3 = (5 ⊗ 5) ⊕ (8 ⊗ 2) ⊕ (9 ⊗ 9) = 10 ⊕ 10 ⊕ 18 = 18 dengan menggunakan notasi matriks didapat 10 13 14 𝐴⊗2 = [11 10 12] 15 17 18 ◊
1.7.4
Transpose Matriks Transpose dari matriks 𝐴 ∈ 𝑀𝑛 (𝑅) dinotasikan dengan 𝐴𝑇 , didefinisikan
sebagai [𝐴𝑇 ]𝑖,𝑗 = [𝑎𝑗,𝑖 ] untuk 𝑖 ∈ 𝑛 dan 𝑗 ∈ 𝑛.
Contoh 2.14. 1 2 Diberikan matriks 𝐴 = [2 4 5 6
3𝑣 2 ] dimana 𝐴 ∈ 𝑀𝑛 (𝑅) 1
maka transpose dari matriks 𝐴 : 1 𝐴 =[2 3𝑣 𝑇
2 4 2
5 6]. 1 ◊
21
1.7.5
Determinan
Definisi 2.13. [8]. Determinan supertropical dari matriks 𝐴 ∈ 𝑀𝑛 (𝑅) didefinisikan sebagai : |𝐴| = ⨁ 𝑎1,𝜎(1) ⊗ 𝑎2,𝜎(2) ⊗ … ⊗ 𝑎𝑛,𝜎(𝑛) 𝜎∈𝑆𝑛
dimana 𝜎 ∈ 𝑆𝑛 dengan 𝑆𝑛 adalah himpunan semua permutasi {1,2, … , 𝑛}. Dalam hal ini determinan supertropical disebut juga dengan permanen.
□
Contoh 2.15. 1 2 3𝑣 Diberikan matriks 𝐴 = [2 4 2 ] dimana 𝐴 ∈ 𝑀𝑛 (𝑅). 5 6 1 Banyaknya permutasi dari {1, 2, 3} adalah 3! = 6 permutasi dari {1, 2, 3} adalah (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) maka |𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) |𝐴 | = ( 1 ⊗ 4 ⊗ 1 ) ⊕ (1 ⊗ 2 ⊗ 6 ) ⊕ (2 ⊗ 2 ⊗ 1 ) ⊕ (2 ⊗ 2 ⊗ 5 ) ⊕ (3𝑣 ⊗ 2 ⊗ 6) ⊕ (3𝑣 ⊗ 4 ⊗ 5) |𝐴| = 6 ⊕ 9 ⊕ 5 ⊕ 9 ⊕ 11𝑣 ⊕ 12𝑣 = 12𝑣 .
1.7.6
◊
Minor dan Adjoint
Definisi 2.14. Diberikan matriks 𝐴 ∈ 𝑀𝑛 (𝑅), minor entri 𝑎𝑖,𝑗 dinyatakan dengan 𝑀𝑖,𝑗 dan didefinisikan sebagai determinan dari matriks setelah baris ke-𝑖 dan kolom ke-𝑗 dihilangkan dari 𝐴. Sedangkan kofaktor dari 𝑎𝑖,𝑗 dituliskan sebagai 𝑐𝑜𝑓𝑖,𝑗 = cof11 𝑀𝑖,𝑗 . Matriks kofaktor dari 𝐴 ditulis sebagai Cof(𝐴) = [ ⋮ cof𝑛1 Sedangkan adjoin 𝐴 dinyatakan sebagai adj(𝐴) = (Cof(𝐴))𝑇
22
⋯ ⋱ ⋯
cof1𝑛 ⋮ ]. cof𝑛𝑛 □
Determinan dari 𝐴 dapat dihitung menggunakan ekspansi kofaktor sepanjang baris ke−𝑖 atau sepanjang kolom ke−𝑗 sebagai berikut : 1.
Ekspansi baris ke−𝑖 𝑛
|𝐴| = ⨁ 𝑎𝑖𝑗 ⊗ cof𝑖,𝑗 (𝐴) 𝑗=1
2.
Ekspansi kolom ke−𝑗 𝑛
|𝐴| = ⨁ 𝑎𝑖𝑗 ⊗ cof𝑖,𝑗 (𝐴) 𝑖=1
Contoh 2.16. 2 Diberikan matriks 𝐴 = [4 2
3 1 5
1 3] dimana 𝐴 ∈ 𝑀𝑛 (𝑅) 1 8 5𝑣 9 Cof(𝐴) = [6 3𝑣 7] 6 5𝑣 7
determinan 𝐴 dengan ekspansi kofaktor sepanjang baris pertama 𝑛
|𝐴| = ⨁ 𝑎𝑖𝑗 ⊗ cof𝑖,𝑗 (𝐴) 𝑗=1
|𝐴| = 𝑎11 ⊗ cof11 ⊕ 𝑎12 ⊗ cof12 ⊕ 𝑎13 ⊗ cof13 |𝐴 | = ( 2 ⊗ 8 ) ⊕ ( 3 ⊗ 5 𝑣 ) ⊕ (1 ⊗ 9 ) |𝐴| = 10 ⊕ 8𝑣 ⊕ 10 = 10𝑣 . determinan 𝐴 dengan ekspansi kofaktor sepanjang kolom kedua 𝑛
|𝐴| = ⨁ 𝑎𝑖𝑗 ⊗ cof𝑖,𝑗 (𝐴) 𝑖=1
|𝐴| = 𝑎12 ⊗ cof12 ⊕ 𝑎22 ⊗ cof22 ⊕ 𝑎32 ⊗ cof32 |𝐴 | = ( 3 ⊗ 5 𝑣 ) ⊕ (1 ⊗ 5 𝑣 ) ⊕ (5 ⊗ 5 𝑣 ) |𝐴| = 8𝑣 ⊕ 6𝑣 ⊕ 10𝑣 = 10𝑣 .
1.7.7
◊
Matriks Non Singular dan Singular
Definisi 2.15. [19]. Suatu matriks persegi 𝐴 ∈ 𝑀𝑛 (𝑅) atas aljabar supertropical disebut non singular jika |𝐴| ∈ 𝒯 dan singular jika |𝐴| ∈ 𝒢0 .
23
□
Contoh 2.17. 1 5 Diberikan matriks 𝐴 = [1 1 3 1 permutasi dari {1, 2, 3} adalah
2 2] dimana 𝐴 ∈ 𝑀𝑛 (𝑅) 3
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) maka |𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) |𝐴 | = ( 1 ⊗ 1 ⊗ 3 ) ⊕ (1 ⊗ 2 ⊗ 1 ) ⊕ (5 ⊗ 1 ⊗ 3 ) ⊕ (5 ⊗ 2 ⊗ 3 ) ⊕ (2 ⊗ 1 ⊗ 1) ⊕ (2 ⊗ 1 ⊗ 3) |𝐴| = 5 ⊕ 4 ⊕ 9 ⊕ 10 ⊕ 4 ⊕ 6 = 10 ∈ 𝒯. Karena |𝐴| ∈ 𝒯 sehingga matriks 𝐴 non singular.
◊
Contoh 2.18. 1 5 Diberikan matriks 𝐴 = [1 1 0 2 permutasi dari {1, 2, 3} adalah
2 2] dimana 𝐴 ∈ 𝑀𝑛 (𝑅 1
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) Maka |𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) |𝐴 | = ( 1 ⊗ 1 ⊗ 1 ) ⊕ (1 ⊗ 2 ⊗ 2 ) ⊕ (5 ⊗ 1 ⊗ 1 ) ⊕ (5 ⊗ 2 ⊗ 0 ) ⊕ (2 ⊗ 2) ⊕ (2 ⊗ 1 ⊗ 0) |𝐴| = 3 ⊕ 5 ⊕ 7 ⊕ 7 ⊕ 5 ⊕ 3 = 7𝑣 ∈ 𝒢0 . Karena |𝐴| ∈ 𝒢0 sehingga matriks 𝐴 singular.
1.7.8
◊
Matriks Pseudo-Zero
Definisi 2.16. [16]. Matriks pseudo-zero 𝑍𝐺 atas aljabar supertropical merupakan matriks persegi 𝑛 × 𝑛 yang didefinisikan sebagai berikut :
24
𝜀 , untuk 𝑖 = 𝑗 [𝑍𝐺 ]𝑖,𝑗 = { 𝑣 𝜀 atau 𝑎 ∈ 𝒢0 , lainnya untuk 𝑖 ∈ 𝑛 dan 𝑗 ∈ 𝑛, dengan 𝑛 ≝ {1, 2, … , 𝑛}.
1.7.9
□
Matriks Identitas
Definisi 2.17. [16]. Matriks identitas 𝐼 merupakan matriks persegi 𝑛 × 𝑛 yang didefinisikan sebagai berikut : 𝑒, [𝐼 ]𝑖,𝑗 = { 𝜀,
untuk 𝑖 = 𝑗 lainnya
untuk 𝑖 ∈ 𝑛 dan 𝑗 ∈ 𝑛, dengan 𝑛 ≝ {1, 2, … , 𝑛}.
□
Definisi 2.18. [16]. Matriks pseudo-identitas 𝐼𝒢 atas aljabar supertropical merupakan matriks persegi 𝑛 × 𝑛 yang didefinisikan sebagai berikut : , 𝑒 [𝐼𝒢 ] = { 𝑣 𝑖,𝑗 𝜀 atau 𝑎 ∈ 𝒢0 ,
untuk 𝑖 = 𝑗 lainnya
untuk 𝑖 ∈ 𝑛 dan 𝑗 ∈ 𝑛. Dalam hal ini 𝐼𝒢 sama dengan 𝐼 ⊕ 𝑍𝐺 .
□
Definisi 2.19. [16]. Matriks pseudo-identitas ghost 𝐼𝒢̅ atas aljabar supertropical merupakan matriks persegi 𝑛 × 𝑛 yang didefinisikan sebagai berikut [ 𝐼̅𝒢 ]
𝑒𝑣
𝑖,𝑗
={
, 𝑣
𝜀 atau 𝑎 ∈ 𝒢0 ,
untuk 𝑖 = 𝑗 lainnya
untuk 𝑖 ∈ 𝑛 dan 𝑗 ∈ 𝑛. Dalam hal ini 𝐼𝒢̅ sama dengan 𝐼 𝑣 ⊕ 𝑍𝐺 .
□
1.7.10 Pseudo-Invers Matriks Definisi 2.20. [16]. Diberikan matriks 𝐴 ∈ 𝑀𝑛 (𝑅), pseudo-invers 𝐴∇ dari 𝐴 atas aljabar supertropical didefinisikan sebagai : 𝐴∇ =
1𝑅 ⊗ adj(A) |𝐴 |
jika |𝐴| ∈ 𝒯 𝐴∇ = (
1𝑅 𝑣 ) ⊗ adj(A) |𝐴 |
jika |𝐴| ∈ 𝒢0 dengan |𝐴| ≠ 𝜀.
□ 25
Contoh 2.19. 1 5 Diberikan matriks 𝐴 = [1 1 3 1 permutasi dari {1, 2, 3} adalah
2 2] dimana 𝐴 ∈ 𝑀𝑛 (𝑅) 3
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) maka |𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) |𝐴 | = ( 1 ⊗ 1 ⊗ 3 ) ⊕ (1 ⊗ 2 ⊗ 1 ) ⊕ (5 ⊗ 1 ⊗ 3 ) ⊕ (5 ⊗ 2 ⊗ 3 ) ⊕ (2 ⊗ 1 ⊗ 1) ⊕ (2 ⊗ 1 ⊗ 3) |𝐴| = 5 ⊕ 4 ⊕ 9 ⊕ 10 ⊕ 4 ⊕ 6 = 10. karena |𝐴| = 10 ∈ 𝒯 matriks 𝐴 non singular. 4 5 4 Cof(𝐴) = [8 5 8] 7 3𝑣 6 4 8 7 adj(𝐴) = [5 5 3𝑣 ] 4 8 6 maka pseudo-invers dari 𝐴 𝐴∇ =
1𝑅 ⊗ adj(A) |𝐴 |
4 1𝑅 ⊗ [5 10 4 4 𝐴∇ = −10 ⊗ [5 4 −6 −2 ∇ [ 𝐴 = −5 −5 −6 −2 𝐴∇ =
8 5 8 8 5 8
7 3𝑣 ] 6 7 3𝑣 ] 6 −3 −7𝑣 ] −4
dan 1 𝐴 ⊗ 𝐴 = [1 3 ∇
5 1 1
2 −6 −2 −3 0 2] ⊗ [−5 −5 −7𝑣 ] = [−4𝑣 −6 −2 −4 3 −3𝑣
0𝑣 0 1𝑣
−2𝑣 −2𝑣 ] = 𝐼𝒢 0
Berdasarkan Contoh 2.19 didapatkan perkalian 𝐴 ⊗ 𝐴∇ = 𝐼𝒢 menghasilkan pseudo-identitas.
◊
26
Contoh 2.20. 1 5 2 Diberikan matriks 𝐴 = [1 1 2] dimana 𝐴 ∈ 𝑀𝑛 (𝑅 0 2 1 grup permutasi dari {1, 2, 3} adalah (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) maka |𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) |𝐴 | = ( 1 ⊗ 1 ⊗ 1 ) ⊕ (1 ⊗ 2 ⊗ 2 ) ⊕ (5 ⊗ 1 ⊗ 1 ) ⊕ (5 ⊗ 2 ⊗ 0 ) ⊕ (2 ⊗ 1 ⊗ 2) ⊕ (2 ⊗ 1 ⊗ 0) |𝐴 | = 3 ⊕ 5 ⊕ 7 ⊕ 7 ⊕ 5 ⊕ 3 = 7 𝑣 . karena |𝐴| = 7𝑣 ∈ 𝒢0 matriks 𝐴 singular. 4 2𝑣 Cof(𝐴) = [6 2𝑣 7 3𝑣 4 6 adj(𝐴) = [2𝑣 2𝑣 3 5
3 5] 6 7 3𝑣 ] 6
maka pseudo-invers dari 𝐴 𝐴∇ = (
1𝑅 𝑣 ) ⊗ adj(A) |𝐴 |
4 1𝑅 𝑣 ) ⊗ [2 𝑣 7 3 4 ∇ 𝑣 ( ) 𝐴 = −7 ⊗ [2𝑣 3 −3𝑣 −1𝑣 ∇ 𝐴 = [−5𝑣 −5𝑣 −4𝑣 −2𝑣
𝐴∇ = (
6 7 2𝑣 3𝑣 ] 5 6 6 7 2𝑣 3𝑣 ] 5 6 0𝑣 −4𝑣 ] −1𝑣
dan 0𝑣 0𝑣 −1𝑣 Berdasarkan Contoh 2.20 didapatkan perkalian 𝐴 ⊗ 𝐴∇ = 𝐼̅𝒢 1 ∇ 𝐴 ⊗ 𝐴 = [1 0
5 2 −3𝑣 1 2] ⊗ [−5𝑣 2 1 −4𝑣
−1𝑣 −5𝑣 −2𝑣
pseudo-identitas ghost.
0𝑣 0𝑣 −4𝑣 ] = [−2𝑣 −1𝑣 −3𝑣
1𝑣 1𝑣 ] = 𝐼𝒢̅ 0𝑣 menghasilkan ◊
27
1.7.11 Matriks Invertibel Definisi 2.21. [16]. Suatu matriks 𝐴 ∈ 𝑀𝑛 (𝑅) invertibel jika terdapat matriks 𝐵 ∈ 𝑀𝑛 (𝑅) sedemikian hingga berlaku 𝐴 ⊗ 𝐵 = 𝐵 ⊗ 𝐴 = 𝐼.
□
Definisi 2.22. [7]. Suatu matriks persegi 𝐴 ∈ 𝑀𝑛 (𝑅) pseudo-invertibel atas aljabar supertropical jika terdapat matriks persegi 𝐵 ∈ 𝑀𝑛 (𝑅) sedemikian hingga 𝐴 ⊗ 𝐵 dan 𝐵 ⊗ 𝐴 adalah pseudo-identitas. Jika 𝐴 pseudo-invertibel maka 𝐵 adalah pseudo-invers dari 𝐴.
□
Contoh 2.21. 1 [ Diberikan matriks 𝐴 = 1 3
5 1 1
−6 2 ] [ 2 dan 𝐵 = −5 −6 3
−2 −5 −2
−3 −7𝑣 ], dimana −4
𝐴, 𝐵 ∈ 𝑀𝑛 (𝑅) maka 1 5 𝐴 ⊗ 𝐵 = [1 1 3 1
2 −6 ] [ ⊗ −5 2 −6 3
−2 −5 −2
−3 0 −7𝑣 ] = [−4𝑣 −4 −3𝑣
0𝑣 0 1𝑣
−2𝑣 −2𝑣 ] = 𝐼𝒢 0
dalam hal ini matriks 𝐵 disebut pseudo-invers kanan dari 𝐴, sedangkan 𝐼𝒢 merupakan pseudo-identitas kanan dari 𝐴 −6 𝐵 ⊗ 𝐴 = [−5 −6
−2 −5 −2
−3 1 𝑣] ⊗ [ −7 1 −4 3
5 2 0 1 2] = [−4𝑣 1 3 −1𝑣
−1𝑣 0 −1𝑣
0𝑣 −3𝑣 ] = 𝐼𝒢 0
dalam hal ini matriks 𝐵 disebut pseudo-invers kiri dari 𝐴, sedangkan 𝐼𝒢 merupakan pseudo-identitas kiri dari 𝐴.
◊
Contoh 2.22. 1 Diberikan matriks 𝐴 = [1 0
5 1 2
2 −3𝑣 2] dan 𝐵 = [−5𝑣 1 −4𝑣
−1𝑣 −5𝑣 −2𝑣
0𝑣 −4𝑣 ], dimana 𝐴, 𝐵 ∈ −1𝑣
𝑀𝑛 (𝑅) maka 1 5 𝐴 ⊗ 𝐵 = [1 1 0 2
2 −3𝑣 2] ⊗ [−5𝑣 1 −4𝑣
−1𝑣 −5𝑣 −2𝑣 28
0𝑣 0𝑣 𝑣] = [ −4 −2𝑣 −1𝑣 −3𝑣
0𝑣 0𝑣 −1𝑣
1𝑣 1𝑣 ] = 𝐼𝒢̅ 0𝑣
dalam hal ini matriks 𝐵 disebut pseudo-invers kanan dari 𝐴, sedangkan 𝐼𝒢̅ merupakan pseudo-identitas ghost kanan dari 𝐴 −3𝑣 𝐵 ⊗ 𝐴 = [−5𝑣 −4𝑣
−1𝑣 −5𝑣 −2𝑣
1 5 0𝑣 −4𝑣 ] ⊗ [1 1 −1𝑣 0 2
2 0𝑣 2] = [−4𝑣 1 −1𝑣
2𝑣 0𝑣 1𝑣
1𝑣 −3𝑣 ] = 𝐼𝒢̅ 0𝑣 dalam hal ini matriks 𝐵 disebut pseudo-invers kiri dari 𝐴, sedangkan 𝐼𝒢̅ merupakan pseudo-identitas ghost kiri dari 𝐴.
◊
1.8 Sistem Persamaan Linear Atas Aljabar Max-Plus Berikut diberikan penjelasan mengenai sistem persamaan linear aljabar max-plus dan karakterisasi penyelesaian sistem persamaan linear atas aljabar max-plus.
1.8.1
Sistem persamaan Linear Aljabar Max-Plus Sistem persamaan linear max-plus 𝐴 ⊗ 𝒙 = 𝒃 tidak selalu mempunyai
penyelesaian. Sebagai contoh : Contoh 2.23. Selesaikan 𝐴 ⊗ 𝒙 = 𝒃 di ℝmax , jika 𝑥1 0 10 −∞ 2 𝐴 = [−∞ 4 3 ] , 𝑥 = [𝑥2 ] dan , 𝑏 = [6] 𝑥3 −∞ −∞ 0 2 dalam bentuk perkalian matriks dapat ditulis sebagai : 𝑥1 0 10 −∞ 2 𝑥 [−∞ 4 3 ] ⊗ [ 2 ] = [6 ] 𝑥3 −∞ −∞ 0 2 sistem diatas ekuivalen dengan (0 ⊗ 𝑥1 ) ⊕ (10 ⊗ 𝑥2 ) ⊕ (−∞ ⊗ 𝑥3 ) = 2 (−∞ ⊗ 𝑥1 ) ⊕ (4 ⊗ 𝑥2 ) ⊕ (3 ⊗ 𝑥3 ) = 6 (−∞ ⊗ 𝑥1 ) ⊕ (−∞ ⊗ 𝑥2 ) ⊕ (0 ⊗ 𝑥3 ) = 2 sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃 tersebut tidak punya penyelesaian, sebab bila punya 𝑥1 penyelesaian berarti ada 𝒙 = [𝑥2 ] sehingga 𝑥3 𝑥1 0 10 −∞ 2 𝑥 [−∞ ] [ ] [ ⊗ = 4 3 2 6] 𝑥 3 2 −∞ −∞ 0 didapat 29
(−∞ ⊗ 𝑥1 ) ⊕ (−∞ ⊗ 𝑥2 ) ⊕ (0 ⊗ 𝑥3 ) = 2 ⇔ (0 ⊗ 𝑥3 ) = 2 ⇔ 𝑥3 = 2 (−∞ ⊗ 𝑥1 ) ⊕ (4 ⊗ 𝑥2 ) ⊕ (3 ⊗ 𝑥3 ) = 6 ⇔ (4 ⊗ 𝑥2 ) ⊕ 5 = 6 ⇔ 𝑥2 = 2 (0 ⊗ 𝑥1 ) ⊕ (10 ⊗ 𝑥2 ) ⊕ (−∞ ⊗ 𝑥3 ) = 2 ⇔ 𝑥1 ⊕ 12 = 2 terlihat bahwa tidak akan ada 𝑥1 ∈ ℝ𝑚𝑎𝑥 sehingga 𝑥1 ⊕ 12 = 2 ⇔ 𝑚𝑎𝑥 {𝑥1 , 12} = 2. Jadi 𝐴 ⊗ 𝒙 = 𝒃 tidak punya penyelesaian. Contoh tersebut menjelaskan bahwa 𝐴 ⊗ 𝒙 = 𝒃 di ℝmax belum tentu mempunyai penyelesaian. Sedangkan 𝐴 ⊗ 𝒙 ≤ 𝒃 selalu punya penyelesaian. Untuk itulah masalah penyelesaian 𝐴 ⊗ 𝒙 = 𝒃 diperlemah dengan mendefinisikan konsep subpenyelesaian berikut ini. 𝑛 𝑚 ′ Definisi 2.23. [20]. Diberikan 𝐴 ∈ ℝ𝑚×𝑛 max dan 𝒃 ∈ ℝmax . Vektor 𝒙 ∈ ℝmax disebut
suatu sub-penyelesaian sistem persamaan linear 𝐴 ⊗ 𝒙 = 𝒃 jika vektor 𝒙′ tersebut memenuhi 𝐴 ⊗ 𝒙′ ≤ 𝒃. Sub-penyelesaian sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃 selalu ada karena untuk 𝒙 = 𝜺 didapat 𝐴 ⊗ 𝒙 = 𝜺 ≤ 𝒃.
□
̂ dari sistem sistem 𝐴 ⊗ 𝒙 = 𝒃 disebut Definisi 2.24. [20]. Suatu subpenyelesaian 𝒙 ̂ untuk setiap subsub-penyelesaian terbesar sistem 𝐴 ⊗ 𝒙 = 𝒃 jika 𝒙′ ≤ 𝒙 penyelesaian 𝒙′ dari sistem 𝐴 ⊗ 𝒙 = 𝒃.
□
Teorema 2.2. [20]. Diberikan 𝐴 ∈ ℝ𝑚×𝑛 max dengan unsur-unsur setiap kolomnya tidak semuanya sama dengan 𝜀 dan 𝒃 ∈ ℝ𝑚 max . Sub-penyelesaian terbesar 𝐴 ⊗ 𝒙 = ̂ dengan 𝒃 ada dan diberikan oleh 𝒙 ̂𝒋 = max(−𝒃𝒊 + 𝐴𝑖𝑗 ) −𝒙 𝑖
untuk setiap 𝑖 = 1, 2, 3, … , 𝑚 dan 𝑗 = 1, 2, 3, … , 𝑛. Bukti : 𝐴11 ⊗ 𝑥1 ⊕ 𝐴12 ⊗ 𝑥2 ⊕ … ⊕ 𝐴1𝑛 ⊗ 𝑥𝑛 ≤ 𝑏1 𝐴 ⊗ 𝑥1 ⊕ 𝐴22 ⊗ 𝑥2 ⊕ … ⊕ 𝐴2𝑛 ⊗ 𝑥𝑛 ≤ 𝑏2 𝐴 ⊗ 𝒙 ≤ 𝒃 ⇔ { 21 ⋮ 𝐴𝑚1 ⊗ 𝑥1 ⊕ 𝐴𝑚2 ⊗ 𝑥2 ⊕ … ⊕ 𝐴𝑚𝑛 ⊗ 𝑥𝑛 ≤ 𝑏𝑛
30
𝑛
⇔ (⨁(𝐴𝑖𝑗 ⊗ 𝑥𝑗 ) ≤ 𝑏𝑖 , ∀𝑖) 𝑗=1
⇔ (𝐴𝑖𝑗 ⊗ 𝑥𝑗 ) ≤ 𝑏𝑖 , ∀𝑖, 𝑗 ⇔ (𝐴𝑖𝑗 + 𝑥𝑗 ) ≤ 𝑏𝑖 , ∀𝑖, 𝑗 karena unsur setiap kolom dari matriks 𝐴 tidak semuanya sama dengan 𝜀, maka untuk setiap 𝑗 selalu ada 𝑖 sehingga 𝐴𝑖𝑗 ≠ 𝜀 yang berarti −𝐴𝑖𝑗 ada. Mengingat untuk setiap 𝑎 ∈ ℝmax berlaku 𝑎 ⊗ 𝜀 = 𝜀 dan 𝑎 ⊕ 𝜀 = 𝑎 maka koefisien-koefisien 𝐴𝑖𝑗 = 𝜀 tidak akan berpengaruh pada nilai 𝐴 ⊗ 𝒙, sehingga berlaku : (𝐴𝑖𝑗 + 𝑥𝑗 ) ≤ 𝑏𝑖 , ∀𝑖, 𝑗 ⇔ (𝐴𝑖𝑗 + 𝑥𝑗 ≤ 𝑏𝑖 , ∀𝑖, 𝑗 dengan 𝐴𝑖𝑗 ≠ 𝜀) ⇔ (𝑥𝑗 ≤ 𝑏𝑖 − 𝐴𝑖𝑗 , ∀𝑖, 𝑗 dengan 𝐴𝑖𝑗 ≠ 𝜀) ⇔ (𝑥𝑗 ≤ min(𝑏𝑖 − 𝐴𝑖𝑗 ) , ∀ 𝑗 dengan 𝐴𝑖𝑗 ≠ 𝜀) 𝑖
⇔ (−𝑥𝑗 ≠ max(−𝑏𝑖 + 𝐴𝑖𝑗 ) , ∀𝑗) 𝑖
Jadi sub-penyelesaian sistem 𝐴 ⊗ 𝒙 = 𝒃 di atas adalah setiap vektor 𝒙′ yang setiap komponen-komponennya memenuhi −𝑥𝑗 ′ = max(−𝑏𝑖 + 𝐴𝑖𝑗 ) , ∀𝑗. 𝑖
Jika vektor 𝑥̂ = [𝑥̂1 , 𝑥̂2 , … , 𝑥̂𝑛 ]𝑇 didefinisikan dengan −𝑥̂𝑗 = max(−𝑏𝑖 + 𝐴𝑖𝑗 ) 𝑖
untuk setiap 𝑗 = 1, 2, … , 𝑛, maka diperoleh : (−𝑥̂𝑗 = max(−𝑏𝑖 + 𝐴𝑖𝑗 ) ∀𝑗) ⇔ (𝑥̂𝑗 = min(𝑏𝑖 − 𝐴𝑖𝑗 ) , ∀𝑗 dengan 𝐴𝑖𝑗 ≠ 𝜀) 𝑖
𝑖
⇔ (𝑥̂𝑗 ≤ (𝑏𝑖 − 𝐴𝑖𝑗 ), ∀𝑖, 𝑗 dengan 𝐴𝑖𝑗 ≠ 𝜀) 𝑛
⇔ (⨁(𝐴𝑖𝑗 ⊗ 𝑥̂𝑗 ) ≤ 𝑏𝑖 , ∀𝑖) 𝑗=1
⇔ (𝐴𝑖𝑗 ⊗ 𝑥̂𝑗 ≤ 𝑏) Jadi vektor 𝑥̂ tersebut merupakan sub-penyelesaian sistem 𝐴 ⊗ 𝒙 = 𝒃. Karena −𝑥𝑗 ′ ≥ max(−𝑏𝑖 + 𝐴𝑖𝑗 ) = −𝑥̂𝑗 , ∀𝑗 maka 𝑥𝑗 ′ ≤ 𝑥̂𝑗 , ∀𝑗. Akibatnya 𝒙′ ≤ ̂ 𝒙. Jadi 𝑖
vektor ̂ 𝒙 tersebut merupakan sub-penyelesaian terbesar sistem 𝐴 ⊗ 𝒙 = 𝒃. ∎
31
Dengan demikian, maka diketahui cara untuk menyelesaikan sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃. Langkah pertama terlebih dahulu dihitung sub-penyelesaian terbesarnya, kemudian diperiksa sub-penyelesaian terbesar tersebut memenuhi sistem persamaan atau tidak. Untuk menghitung sub-penyelesaian terbesar sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃, dapat diperhatikan bahwa : max(−𝑏𝑖 + 𝐴𝑖1 ) 𝑖 −𝑥̂1 max(−𝑏𝑖 + 𝐴𝑖2 ) −𝑥̂2 𝑖 ]= ̂=[ −𝒙 ⋮ ⋮ −𝑥̂𝑛 max (−𝑏 𝑖 + 𝐴𝑖𝑚 )] [ 𝑖 max(𝐴𝑖1 − 𝑏𝑖 ) 𝑖
=
max(𝐴𝑖2 − 𝑏𝑖 ) 𝑖
⋮ (𝐴𝑖𝑚 − 𝑏𝑖 ) ] [max 𝑖
𝐴11 ⊗ (−𝑏1 ) ⊕ 𝐴21 ⊗ (−𝑏2 ) ⊕ … ⊕ 𝐴𝑚1 ⊗ (−𝑏𝑚 ) 𝐴 ⊗ (−𝑏1 ) ⊕ 𝐴22 ⊗ (−𝑏2 ) ⊕ … ⊕ 𝐴𝑚2 ⊗ (−𝑏𝑚 ) ] = 𝐴𝑇 ⊗ (−𝒃) = [ 12 ⋮ 𝐴1𝑛 ⊗ (−𝑏1 ) ⊕ 𝐴2𝑛 ⊗ (−𝑏2 ) ⊕ … ⊕ 𝐴𝑚𝑛 ⊗ (−𝑏𝑚 ) Sub-penyelesaian terbesar 𝐴 ⊗ 𝒙 = 𝒃 dapat ditentukan dengan langkah pertama ̂ = 𝐴𝑇 ⊗ (−𝒃) atau 𝒙 ̂ = −(𝐴𝑇 ⊗ (−𝒃)). menghitung −𝒙
Contoh 2.24. Selesaikan 𝐴 ⊗ 𝒙 = 𝒃 di ℝmax , jika 𝑥1 1 2 6 5 𝐴 = [2 3 1 ] , 𝑥 = [𝑥 2 ] , 𝑏 = [4 ] 𝑥3 4 1 −2 3 dalam bentuk perkalian matriks dapat ditulis sebagai 𝑥1 1 2 6 5 [2 3 1 ] ⨂ [𝑥 2 ] = [4 ] 𝑥3 4 1 −2 3 akan ditentukan penyelesaian terbesar sistem persamaan tersebut dengan terlebih dahulu menentukan sub-penyelesaian terbesarnya. ̂ = 𝐴𝑇 ⊗ (−𝒃) Pertama dihitung −𝒙 1
̂ = 𝐴𝑇 ⊗ (−𝒃) = [2 −𝒙 6
2 3 1
32
4 −5 1 1 ] ⨂ [−4] = [−1] −2 −3 1
−1
̂=[1] 𝒙 −1 1 2 6 −1 5 −1 karena [2 3 1 ] ⊗ [ 1 ] = [4], maka [ 1 ] merupakan penyelesaian sistem. 4 1 −2 −1 3 −1
Selanjutnya akan diberikan contoh sistem persamaan linear aljabar max-plus yang mempunyai sub-penyelesaian terbesar akan tetapi tidak mempunyai penyelesaian sebagai berikut. Contoh 2.25. Selesaikan 𝐴 ⊗ 𝒙 = 𝒃 di ℝmax , jika 𝑥1 2 2 1 2 𝐴 = [2 1 3 ] , 𝑥 = [𝑥 2 ] , 𝑏 = [6 ] 𝑥3 3 2 5 4 dalam bentuk perkalian matriks dapat ditulis sebagai 𝑥1 2 2 1 2 𝑥 [2 1 3 ] ⨂ [ 2 ] = [6 ] 𝑥3 3 2 5 4 akan ditentukan penyelesaian terbesar sistem persamaan tersebut dengan terlebih dahulu menentukan sub-penyelesaian terbesarnya. 2
2
3
−2
0
̂ = 𝐴𝑇 ⊗ (−𝒃) = [2 1 2] ⨂ [−6] = [0] −𝒙 1
2 2
Karena [2 1 3 2
3 5 −4 1 0 ̂ 𝒙=[0] −1 1 2 2 0 0 3] ⨂ [ 0 ] = [2] ≤ [6], maka [ 0 ] bukan merupakan penyelesaian −1 4 4 −1 5
sistem. Akan tetapi persamaan linear tersebut memiliki sub-penyelesaian terbesar yang bukan merupakan penyelesaian.
1.8.2
Karakterisasi Penyelesaian Sistem Persamaan Linear atas Aljabar Max-Plus
33
Berdasarkan [17] telah dijelaskan mengenai karakterisasi penyelesaian sistem persamaan linear atas aljabar max-plus sebagai berikut : Diberikan sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃 dengan 𝐴 ∈ ℝ𝑚×𝑛 max , 𝒙 ∈ ℝ𝑛max dan 𝒃 ∈ ℝ𝑚 max . Sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃 yang terdiri dari 𝑛 persamaan dan 𝑛 peubah dapat ditulis dalam bentuk perkalian matriks sebagai berikut 𝐴⊗𝒙= 𝒃 𝑎11 𝑎21 [ ⋮ 𝑎𝑛1
𝑎12 𝑎22 ⋮ 𝑎𝑛2
… … ⋱ …
𝑎1𝑛 𝑥1 𝑏1 𝑎2𝑛 𝑥2 𝑏2 ⋮ ]⊗[ ⋮ ] = [ ⋮ ] 𝑎𝑛𝑛 𝑥𝑛 𝑏𝑛
atau (𝑎11 ⊗ 𝑥1 ) ⊕ (𝑎12 ⊗ 𝑥2 ) ⊕ … ⊕ (𝑎1𝑛 ⊗ 𝑥𝑛 ) = 𝑏1 (𝑎21 ⊗ 𝑥1 ) ⊕ (𝑎22 ⊗ 𝑥2 ) ⊕ … ⊕ (𝑎2𝑛 ⊗ 𝑥𝑛 ) = 𝑏2 ⋮
⋮
⋮
⋮
(𝑎𝑛1 ⊗ 𝑥1 ) ⊕ (𝑎𝑛2 ⊗ 𝑥2 ) ⊕ … ⊕ (𝑎𝑛𝑛 ⊗ 𝑥𝑛 ) = 𝑏𝑛 Kasus yang pertama dibahas ada suatu penyelesaian dan beberapa elemen dari 𝒃 adalah 𝜀. Tanpa menghilangkan keumumannya, persamaan dapat disusun ulang sehingga elemen-elemen yang berhingga disusun dengan urutan yang pertama, didapat : 𝑎1,1 𝑎2,1 [ ⋮ 𝑎𝑛,1
𝑎1,2 𝑎2,2 ⋮ 𝑎𝑛,2
… … ⋱ …
𝑏1 𝑎1,𝑛 𝑥1 ⋮ 𝑎2,𝑛 𝑥2 𝑏 𝑘 ⋮ ] ⊗ [ ⋮ ] = −∞ 𝑎𝑛,𝑛 𝑥𝑛 ⋮ [−∞]
dapat dituliskan sebagai : (𝑎1,1 ⊗ 𝑥1 ) ⊕ (𝑎1,2 ⊗ 𝑥2 ) ⊕ … ⊕ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) = 𝑏1 ⋮ (𝑎𝑘,1 ⊗ 𝑥1 ) ⊕ (𝑎𝑘,2 ⊗ 𝑥2 ) ⊕ … ⊕ (𝑎𝑘,𝑛 ⊗ 𝑥𝑛 ) = 𝑏𝑘 (𝑎𝑘+1,1 ⊗ 𝑥1 ) ⊕ (𝑎𝑘+1,2 ⊗ 𝑥2 ) ⊕ … ⊕ (𝑎𝑘+1,𝑛 ⊗ 𝑥𝑛 ) = −∞ ⋮ (𝑎𝑛,1 ⊗ 𝑥1 ) ⊕ (𝑎𝑛,2 ⊗ 𝑥2 ) ⊕ … ⊕ (𝑎𝑛,𝑛 ⊗ 𝑥𝑛 ) = −∞ Lakukan penomoran ulang pada peubah untuk 𝑗 sehingga 𝑎𝑘+1,𝑗 , … , 𝑎𝑛,𝑗 = 𝜀 34
terjadi pertama, didapatkan 𝑥1 𝑏1 ⋮ ⋮ 𝐴1 𝐴2 𝑥𝑙 −∞ ⋯ −∞ 𝑏𝑘 ]⊗ 𝑥 [ = ⋮ ⋱ ⋮ 𝐴3 −∞ 𝑙+1 ⋮ −∞ ⋯ −∞ ⋮ [ 𝑥𝑛 ] [−∞] dengan matriks 𝐴1 berukuran 𝑘 × 𝑙. Misalkan : 𝑥1 𝑏1 ̅ ̅=[⋮] 𝒃 = [ ⋮ ] dan 𝒙 𝑥𝑙 𝑏𝑘 Catatan bahwa : 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian, maka 𝑥𝑙+1 , … , 𝑥𝑛 = ̅. Jadi 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian bila dan hanya ̅=𝒃 −∞ dan 𝐴1 ⊗ 𝒙 ̅ dan penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃 ̅ adalah penyelesaian dari 𝐴1 ⊗ 𝒙 ̅=𝒃 bila 𝒙 adalah ̅ 𝒙 −∞ ] 𝒙=[ ⋮ −∞ Oleh karena itu, penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃 dengan beberapa elemen 𝒃 takhingga ̅ dengan semua elemen dari 𝒃 ̅ berhingga. Jadi dapat direduksi ke bentuk 𝐴1 ⊗ ̅ 𝒙=𝒃 pembahasan persamaan 𝐴 ⊗ 𝒙 = 𝒃 dapat ditekankan pada semua elemen 𝒃 berhingga. Bila 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian, maka : 𝑎𝑖𝑗 ⊗ 𝑥𝑗 ≤ 𝑏𝑖 , ∀𝑖 ∈ 𝑛 , 𝑗 ∈ 𝑛 jika dituliskan secara terpisah untuk setiap 𝑖 didapat 𝑎𝑖1 + 𝑥1 ≤ 𝑏1 atau 𝑥1 ≤ 𝑏1 − 𝑎𝑖1 didapat 𝑥1 ≤ 𝑏1 − 𝑎11 𝑥1 ≤ 𝑏2 − 𝑎21 ⋮ 𝑥1 ≤ 𝑏𝑛 − 𝑎𝑛1 atau 𝑥1 ≤ min{(𝑏1 − 𝑎11 ), (𝑏2 − 𝑎21 ), … , (𝑏𝑛 − 𝑎𝑛1 ) } Jadi, jika sistem mempunyai penyelesaian maka harus memenuhi 𝑥1 ≤ min{(𝑏1 − 𝑎11 ), (𝑏2 − 𝑎21 ), … , (𝑏𝑛 − 𝑎𝑛1 ) } 35
dengan demikian penyelesaian 𝑥 yang mungkin memenuhi 𝑥1 ≤ min{(𝑏1 − 𝑎11 ), (𝑏2 − 𝑎21 ), … , (𝑏𝑛 − 𝑎𝑛1 ) } 𝑥2 ≤ min{(𝑏1 − 𝑎12 ), (𝑏2 − 𝑎22 ), … , (𝑏𝑛 − 𝑎𝑛2 ) } ⋮ 𝑥𝑛 ≤ min{(𝑏1 − 𝑎1𝑛 ), (𝑏2 − 𝑎2𝑛 ), … , (𝑏𝑛 − 𝑎𝑛𝑛 ) } ̅ adalah Jadi calon penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃 yang dinotasikan dengan 𝒙 𝑥̅1 𝑥̅ ̅ = [ 2 ], 𝒙 ⋮ 𝑥̅ 𝑛 dengan 𝑥1 = min{(𝑏1 − 𝑎11 ), (𝑏2 − 𝑎21 ), … , (𝑏𝑛 − 𝑎𝑛1 ) } 𝑥2 = min{(𝑏1 − 𝑎12 ), (𝑏2 − 𝑎22 ), … , (𝑏𝑛 − 𝑎𝑛2 ) } ⋮ 𝑥𝑛 = min{(𝑏1 − 𝑎1𝑛 ), (𝑏2 − 𝑎2𝑛 ), … , (𝑏𝑛 − 𝑎𝑛𝑛 ) } Selanjutnya didefinisikan matriks “discrepancy” (ketidaksesuaian) dinotasikan 𝐷𝐴,𝑏 dengan 𝐷𝐴,𝑏
𝑏1 − 𝑎11 𝑏2 − 𝑎21 =[ ⋮ 𝑏𝑛 − 𝑎𝑛1
𝑏1 − 𝑎12 𝑏2 − 𝑎22 ⋮ 𝑏𝑛 − 𝑎𝑛2
… 𝑏1 − 𝑎1𝑛 ⋮ 𝑏2 − 𝑎2𝑛 ] ⋮ ⋮ … 𝑏𝑛 − 𝑎𝑛𝑛
̅. minimum dari setiap kolom 𝐷𝐴,𝑏 adalah elemen dari 𝒙 Selanjutnya didefinisikan matriks tereduksi ketaksesuaian 𝑅𝐴,𝑏 sebagai berikut : 𝑅𝐴,𝑏 = [𝑟𝑖,𝑗 ] dengan 𝑟𝑖,𝑗 = {
1, jika 𝑑𝑖,𝑗 = minimum dari kolom ke − j 0 , yang lainnya
Dalam hal ini matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 dapat digunakan untuk menentukan perilaku penyelesaian dari sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃. Dengan demikian dapat diketahui kekonsistenan dan ketunggalan dari penyelesaian 𝐴 ⊗ 𝒙 = 𝒃. Berikut diberikan contoh kasus penyelesaian sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃. Contoh 2.26 Kasus 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian tunggal
36
Selesaikan 𝐴 ⊗ 𝒙 = 𝒃, jika 𝑥1 1 1 −9 4 𝐴 = [−4 18 −8] , 𝑥 = [𝑥2 ] dan , 𝑏 = [−6] 𝑥3 −3 2 1 −4 didapatkan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 sebagai berikut : 0 𝐷𝐴,𝑏 = [−2 −5
0 0 10 −3 −24 2 ] dan 𝑅𝐴,𝑏 = [0 1 1 0 −4 1
1 0] 0
terlihat bahwa setiap kolom matriks 𝑅𝐴,𝑏 hanya terdapat tepat satu elemen bernilai 1. Hal ini menandakan bahwa 𝐴 ⊗ 𝒙 = 𝒃 hanya mempunyai tepat satu ̅ dengan elemen-elemennya adalah minimum dari setiap kolom penyelesaian 𝒙 matriks 𝐷𝐴,𝑏 yaitu −5 ̅ = [−24] 𝒙 −3 hal ini bisa di cek sebagai berikut : 1 ̅ [ 𝐴 ⊗ 𝒙 = −4 2
−9 18 1
𝑚𝑎𝑥(−4, −33,1) 4 −5 1 ( ) ] [ [ ] −8 ⊗ −24 = [𝑚𝑎𝑥 −9, −6, −11 ] = −6] = 𝒃. −4 −3 −3 𝑚𝑎𝑥(−3, −23, −7)
Dari hal tersebut dapat dijelaskan bahwa :
Pada baris pertama nilai maksimum dicapai hanya satu kali, dengan demikian persamaan baris pertama menetapkan elemen 𝑥3 = −3.
Pada baris kedua nilai maksimum dicapai hanya satu kali. Dengan demikian persamaan baris kedua menetapkan elemen 𝑥2 = −24.
Pada baris ketiga didapatkan nilai maksimum dicapai hanya satu kali. Dengan demikian persamaan baris ketiga menetapkan elemen 𝑥1 = −5. Setiap elemen-elemen yang sudah dipilih ini tidak bisa diubah, bila diubah
yang lain maka akan membentuk pertaksamaan. Karena pada keseluruhan baris nilai maksimum hanya dicapai satu kali, maka hanya terdapat satu cara untuk mencapai persamaan pada semua baris yaitu dengan menetapkan elemen 𝑥1 = −5, 𝑥2 = −24, 𝑥3 = −3.
Dengan
demikian
persamaan
𝐴⊗𝒙=𝒃
memiliki
penyelesaian tunggal. Contoh 2.27 Kasus 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian tak hingga banyak
37
Selesaikan 𝐴 ⊗ 𝒙 = 𝒃, jika 𝑥1 2 1 −9 4 𝐴 = [−4 18 −8] , 𝑥 = [𝑥2 ] dan , 𝑏 = [1] 𝑥3 3 2 1 −4 didapatkan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 sebagai berikut : 1 1 11 −2 𝐷𝐴,𝑏 = [5 −17 9 ] dan 𝑅𝐴,𝑏 = [0 1 1 2 7
0 1 0
1 0] 0
terlihat bahwa setiap kolom matriks 𝑅𝐴,𝑏 terdapat setidaknya satu elemen bernilai 1, sedangkan pada baris ke-1 terdapat nilai 1 lebih dari satu. Hal tersebut ̅. Elemenmenandakan bahwa 𝐴 ⊗ 𝒙 = 𝒃 mempunyai banyak penyelesaian 𝒙 elemen minimum dari setiap kolom matriks 𝐷𝐴,𝑏 yaitu 1 ̅ = [−17] 𝒙 −2 Hal ini bisa di cek sebagai berikut : 1 ̅ = [−4 𝐴⊗𝒙 2
−9 18 1
𝑚𝑎𝑥 (2, −26, 2) 4 1 2 ( ) ] [ [ ] ⊗ ] = = [ 𝑚𝑎𝑥 −3, 1, −10 1] = 𝒃. −8 −17 −4 −2 3 𝑚𝑎𝑥 (3, −16, −6)
dari hal tersebut dapat dijelaskan bahwa :
Pada baris pertama nilai maksimum dicapai dua kali yaitu pada saat elemen 𝑥1 = 1 dan elemen 𝑥3 = −2.
Pada baris kedua nilai maksimum dicapai hanya satu kali. Dengan demikian persamaan baris kedua menetapkan elemen 𝑥2 = −17.
Pada baris ketiga nilai maksimum dicapai hanya satu kali. Dengan demikian persamaan baris ketiga menetapkan elemen 𝑥1 = 1.
Elemen-elemen yang sudah dipilih yaitu 𝑥2 = −17 dan 𝑥1 = 1 tidak bisa diubah, bila diubah yang lain maka baris kedua dan ketiga akan membentuk pertaksamaan. Karena persamaan baris ketiga telah menetapkan 𝑥1 = 1, maka dengan menetapkan elemen 𝑥3 < −2 pada baris pertama tetap membentuk persamaan dan tidak akan mengubah persamaan pada baris lain. Sehingga persamaan pada semua baris akan tercapai dengan menetapkan elemen 𝑥1 = 1, 𝑥2 = −17, 𝑥3 < −2. Dengan demikian 𝐴 ⊗ 𝒙 = 𝒃 memiliki penyelesaian tak hingga banyak yaitu
38
1 ̅ = [−17] untuk setiap 𝑝3 < −2 𝒙 𝑝3 Contoh 2.28. Kasus 𝐴 ⊗ 𝒙 = 𝒃 tidak mempunyai penyelesaian Selesaikan 𝐴 ⊗ 𝒙 = 𝒃, jika 𝑥1 1 −9 4 1 𝑥 𝐴 = [−4 18 −8] , 𝑥 = [ 2 ] dan , 𝑏 = [2] 𝑥3 2 1 −4 3 didapatkan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 sebagai berikut : 𝐷𝐴,𝑏
0 10 −3 1 [ ] [ = 6 −16 10 dan 𝑅𝐴,𝑏 = 0 1 2 7 0
0 1 0
1 0] 0
Terlihat bahwa tidak semua kolom matriks 𝑅𝐴,𝑏 setidaknya memuat satu elemen bernilai 1, yaitu pada baris ke-3 semua elemennya bernilai 0. Hal tersebut menandakan bahwa 𝐴 ⊗ 𝒙 = 𝒃 tidak mempunyai penyelesaian. Elemen-elemen minimum dari setiap kolom matriks 𝐷𝐴,𝑏 yaitu 0 ̅ = [−16] 𝒙 −3 Selanjutnya bisa di cek bahwa : 1 ̅ = [−4 𝐴⊗𝒙 2
−9 18 1
𝑚𝑎𝑥 (1, −25, 1) 4 0 1 1 −8] ⊗ [−16] = [𝑚𝑎𝑥 (−4, 2, −11)] = [2] < [2] = 𝒃. −4 −3 2 3 𝑚𝑎𝑥 (2, −15, −7)
Dari hal tersebut dapat dijelaskan bahwa :
Pada baris pertama nilai maksimum dicapai dua kali yaitu pada saat elemen 𝑥1 = 0 dan elemen 𝑥3 = −3.
Pada baris kedua nilai maksimum dicapai hanya satu kali. Dengan demikian persamaan baris kedua menetapkan elemen 𝑥2 = −17.
Pada baris ketiga tidak terdapat elemen yang dapat mencapai nilai maksimum yang bisa membentuk persamaan, sehingga baris ketiga membentuk pertaksamaan. Oleh karena itu persamaan pada baris ketiga tidak tercapai. Dengan demikian 𝐴 ⊗ 𝒙 = 𝒃 tidak mempunyai penyelesaian.
39
Berdasarkan Contoh 2.26 sampai 2.28 didapatkan matriks 𝑅𝐴,𝑏 untuk penyelesaian tunggal, tak hingga banyak dan tidak mempunyai penyelesaian sebagai berikut : Solusi tunggal 0 𝐷𝐴,𝑏 = [−2 −5 𝑅𝐴,𝑏
10 −3 −24 2 ] −4 1 0 0 1 = [0 1 0] 1 0 0
Solusi tak hingga
Tidak mempunyai
banyak
penyelesaian
1 11 𝐷𝐴,𝑏 = [5 −17 1 2 1 0 𝑅𝐴,𝑏 = [0 1 1 0
−2 9] 7 1 0] 0
0 𝐷𝐴,𝑏 = [6 1 𝑅𝐴,𝑏
10 −3 −16 10 ] 2 7 0 1 0 = [1 0 1 ] 0 0 0
Berikut diberikan Teorema mengenai beberapa hal yang telah dibahas. Teorema 2.3 [17]. Diberikan persamaan 𝐴 ⊗ 𝒙 = 𝒃 dengan 𝐴 ∈ ℝ𝑚×𝑛 max , 𝒙 ∈ ℝ𝑛max dan 𝒃 ∈ ℝ𝑚 max . Bila suatu baris dari matriks 𝑅𝐴,𝑏 semua elemennya bernilai 0, maka persamaan 𝐴 ⊗ 𝒙 = 𝒃 tidak punya penyelesaian. Bila setidaknya pada setiap baris matriks 𝑅𝐴,𝑏 paling sedikit memuat sebuah elemen bernilai 1, maka 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian. Bukti. Tanpa menghilangkan keumuman, misalkan baris ke-𝑘 dari 𝑅𝐴,𝑏 semua elemennya ̅ adalah suatu penyelesian dari persamaan 𝐴 ⊗ 𝒙 = bernilai 0 dan andaikan bahwa 𝒙 𝒃, maka : ̅𝑗 ≤ 𝑚𝑖𝑛{𝑏𝑙 − 𝑎𝑙,𝑗 } < (𝑏𝑘 − 𝑎𝑘,𝑗 ), ∀𝑙 ∈ 𝑛. 𝒙 Jadi
̅𝑗 + 𝑎𝑘,𝑗 < 𝑏𝑘 untuk semua 𝑗. Dengan demikian 𝒙 ̅ tidak memenuhi 𝒙
̅ adalah suatu penyelesaian dari persamaan ke- 𝑘. Hal ini bertentangan dengan 𝒙 ̅ bukan penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃 sehingga 𝐴 ⊗ 𝒙 = 𝒃 tidak 𝐴 ⊗ 𝒙 = 𝒃. Jadi 𝒙 ̅ bukan penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃 punya penyelesaian. Berikutnya, andaikan 𝒙 ̅𝑗 < 𝑏𝑘 − 𝑎𝑘,𝑗 untuk semua 𝑘, 𝑗. Jadi : maka 𝒙 ̅𝑗 } ≤ 𝑏𝑘 , ∀𝑗 ∈ 𝑛 𝑚𝑎𝑥{𝑎𝑘,𝑗 + 𝒙 dan bila ̅ 𝒙 bukan penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃, maka ada suatu 𝑘 dengan ̅𝑗 } < 𝑏𝑘 , ∀𝑗 ∈ 𝑛 𝑚𝑎𝑥{𝑎𝑘,𝑗 + 𝒙 karena ̅𝑗 = 𝑚𝑖𝑛{𝑏𝑙 − 𝑎𝑙,𝑗 } untuk beberapa 𝑙 𝒙
40
maka tidak ada elemen di baris ke- 𝑘 pada matriks 𝑅𝐴,𝑏 yang bernilai 1. Hal ini bertentangan bahwa setiap baris dari matriks 𝑅𝐴,𝑏 setidaknya memuat elemen yang ̅ adalah suatu penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃. bernilai 1. Jadi haruslah 𝒙
∎
Teorema 2.3 tersebut menjelaskan eksistensi dari penyelesaian 𝐴 ⊗ 𝒙 = 𝒃. Eksistensi
tersebut
belum
menjelaskan
bilamana
𝐴⊗𝒙=𝒃
memiliki
penyelesaiaan tunggal dan tidak tunggal. Untuk hal tersebut diperlukan definisi sebagai berikut : Definisi 2.25 [17]. Elemen bernilai 1 pada suatu baris 𝑅𝐴,𝑏 dinamakan elemen peubah tetap bila nilai 1 hanya muncul sekali pada baris tersebut atau bila nilai 1 berada pada kolom yang sama seperti halnya nilai 1 hanya satu-satunya pada baris tersebut. Sedangkan sisa nilai 1 lainnya dinamakan elemen slack. Berikut ini diberikan matriks 𝑅𝐴,𝑏 yang didapat dari Contoh 2.26 dan 2.27 untuk mempertegas Definisi 2.25 mengenai elemen peubah tetap dan elemen slack. Solusi tunggal
𝑅𝐴,𝑏
0 = [0 𝟏
0 𝟏 0
Solusi tak hingga banyak
𝟏 0] 0
𝑅𝐴,𝑏
𝟏 0 = [0 𝟏 𝟏 0
1 0] 0
Dari tabel tersebut dapat dijelaskan beberapa hal sebagai berikut : Berdasarkan Contoh 2.26 didapat matriks 𝐷𝐴,𝑏
0 = [−2 −5
0 10 −3 −24 2 ] dan 𝑅𝐴,𝑏 = [0 𝟏 −4 1
0 𝟏 0
𝟏 0] 0
semua elemen 𝟏 adalah peubah tetap. Persamaan baris pertama menetapkan elemen 𝑥3 = −3, Persamaan baris kedua menetapkan elemen 𝑥2 = −24, dan Persamaan baris ketiga menetapkan elemen 𝑥1 = −5. Setiap elemen-elemen yang sudah dipilih tidak bisa diubah, bila diubah maka tidak akan memenuhi 𝐴 ⊗ 𝒙 = 𝒃. Berdasarkan Contoh 2.27 didapat matriks
41
𝐷𝐴,𝑏
𝟏 1 11 −2 = [5 −17 9 ] dan 𝑅𝐴,𝑏 = [ 0 𝟏 1 2 7
0 1 𝟏 0] 0 0
semua elemen 𝟏 adalah peubah tetap. Sedangkan sisa nilai 1 lainnya dinamakan elemen slack. Pada Contoh 2.26 terdapat satu elemen slack. Pada baris pertama terdapat dua kemungkinan yaitu menetapkan elemen 𝑥1 atau 𝑥3 . Persamaan baris kedua menetapkan elemen 𝑥2 , dan persamaan baris ketiga telah menetapkan elemen 𝑥1 . Karena elemen 𝑥1 tidak bisa dirubah, maka pada baris pertama dengan menetapkan elemen 𝑥3 < −2 akan membentuk persamaan karena maksimum hanya dicapai satu kali dan tidak akan mengubah persamaan lain. Dengan demikian, dengan menetapkan 𝑥1 = 1, 𝑥2 = −17 dan 𝑥3 <𝑣 − 2 persamaan semua baris selalu benar. Berikut ini diberikan penjelasan mengenai hal yang telah dibahas. Teorema 2.4 [17]. Diberikan persamaan 𝐴 ⊗ 𝒙 = 𝒃 dengan 𝐴 ∈ ℝ𝑚×𝑛 max , 𝒙 ∈ ℝ𝑛max dan 𝒃 ∈ ℝ𝑚 max dan diasumsikan 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian. Bila setiap baris dari matriks 𝑅𝐴,𝑏 hanya ada satu anggota yang bernilai 1, maka persamaan 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian tunggal. Bila ada elemen slack pada matriks 𝑅𝐴,𝑏 maka 𝐴 ⊗ 𝒙 = 𝒃 mempunyai penyelesaian tidak tunggal. Bukti. Bila disetiap baris 𝑅𝐴,𝑏 hanya ada satu elemen bernilai 1, maka disetiap baris 𝑅𝐴,𝑏 ada suatu elemen peubah tetap dan tidak ada elemen slack. Dengan demikian semua elemen 𝒙 tetap, jadi penyelesaian tunggal. Selanjutnya, misalkan 𝑟𝑖,𝑗 adalah satu elemen slack pada 𝑅𝐴,𝑏 dan 𝒙 adalah penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃. Karena 𝑟𝑖,𝑗 bukan elemen peubah tetap, maka tidak ada elemen peubah tetap pada kolom ke- 𝑗 ̅𝑗 . dari matriks 𝑅𝐴,𝑏 . Jadi persamaan bisa dicapai tanpa menggunakan elemen 𝒙 ̅𝑗 menunjukkan nilai maksimum yang mungkin untuk Dengan demikian walaupun 𝒙 ̅𝑗 tidak elemen ini, akan tetapi untuk setiap nilai yang lebih kecil atau samadengan 𝒙 akan mempengaruhi eksistensi persamaan baris yang telah ditetapkan.
1.9 Sistem Persamaan Linear atas Aljabar Supertropical 42
∎
Sebagaimana dalam aljabar linear biasa, sistem persamaan linear atas aljabar supertropical terbagi menjadi sistem persamaan tak homogen dan sistem persamaan homogen. Dalam aljabar supertropical, akan digunakan relasi ghost surpass ⊨ pada 𝑅 sebagai pengganti dari relasi “=”. Sistem persamaan tak homogen atas aljabar supertropical dinyatakan sebagai 𝐴 ⊗ 𝒙 ⊨ 𝒃. Sedangkan bila semua entri dari 𝒃 = 𝜺 ≝ −∞, maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 disebut sistem persamaan homogen atas aljabar supertropical.
43
BAB III METODE PENELITIAN
Pada bagian ini diuraikan beberapa metode penelitian yang digunakan untuk mencapai tujuan penelitian.
1.
Studi Literatur. Pada tahap ini, dikaji dan diuraikan teori-teori yang mendukung proses penelitian. Diantaranya penelitian terdahulu, semiring, aljabar max-plus, aljabar tropical, perluasan aljabar tropical, aljabar supertropical dan sistem persamaan linear atas aljabar max-plus dan aljabar supertropical.
2.
Menentukan karakterisasi penyelesaian sistem persamaan linear tak homogen atas aljabar supertropical. Berdasarkan kajian teori dan pengamatan pada beberapa definisi, teorema dan contoh pada kasus-kasus tertentu, maka pada tahap ini dilakukan karakterisasi terhadap penyelesaian sistem persamaan linear tak homogen atas aljabar supertropical . Karakterisasi terhadap penyelesaian sistem persamaan linear tak homogen adalah memiliki penyelesaian tunggal atau tidak tunggal.
3.
Menentukan karakterisasi penyelesaian sistem persamaan linear homogen atas aljabar supertropical. Berdasarkan kajian teori dan pengamatan pada beberapa definisi, teorema dan contoh pada kasus-kasus tertentu, maka pada tahap ini dilakukan karakterisasi terhadap penyelesaian sistem persamaan linear homogen atas aljabar supertropical . Karakterisasi terhadap penyelesaian sistem persamaan linear homogen adalah memiliki penyelesaian trivial atau tak trivial.
4.
Membuat Simpulan Berdasarkan karakterisasi penyelesaian sistem persamaan linear tak homogen maupun homogen atas aljabar supertropical, dilakukan proses pembuatan simpulan. Simpulan dibuat untuk menjawab rumusan masalah.
45
BAB IV PEMBAHASAN
Pada bab ini akan dipaparkan pembahasan mengenai karakterisasi penyelesaian sistem persamaan linear atas aljabar supertropical. Pembahasan diawali dengan menentukan karakterisasi penyelesaian sistem persamaan linear tak homogen yang kemudian dilanjutkan pada sistem persamaan linear homogen. Adapun karakterisasi penyelesaian yang dibahas pada sistem persamaan linear tak homogen adalah mempunyai penyelesaian tunggal atau tidak tunggal. Sedangkan karakterisasi penyelesaian yang dibahas pada sistem persamaan linear homogen adalah mempunyai penyelesaian trivial atau tak trivial.
4.1 Karakterisasi Penyelesaian Sistem Persamaan Linear Tak Homogen atas Aljabar Supertropical Pada bagian sebelumnya telah dijelaskan bahwa aljabar max-plus merupakan suatu struktur aljabar (ℝ𝜀 ,⊕,⊗) yang tidak mempunyai elemen invers terhadap operasi ⊕. Dengan kata lain, jika 𝑎 ∈ ℝ𝜀 maka tidak ada 𝑏 ∈ ℝ𝜀 sehingga 𝑎 ⊕ 𝑏 = 𝜀, kecuali jika 𝑎 = 𝜀 dengan 𝜀 ≝ −∞ adalah elemen nol. Hal ini yang menyulitkan untuk menyelesaikan sistem persamaan linear 𝐴 ⊗ 𝒙 = 𝒃 di ℝmax . Sebagai motivasi dari pembahasan sistem persamaan linear tak homogen, akan diberikan sistem persamaan tak homogen di ℝmax sebagai berikut. Selesaikan 𝐴 ⊗ 𝒙 = 𝒃 di ℝmax , jika 𝑥1 0 10 −∞ 2 𝐴 = [−∞ 4 3 ] , 𝑥 = [𝑥2 ] dan , 𝑏 = [6] 𝑥3 −∞ −∞ 0 2 dalam bentuk perkalian matriks dapat ditulis sebagai : 𝑥1 0 10 −∞ 2 𝑥 [−∞ 4 3 ] ⊗ [ 2 ] = [6 ] 𝑥3 −∞ −∞ 0 2 sistem diatas ekuivalen dengan (0 ⊗ 𝑥1 ) ⊕ (10 ⊗ 𝑥2 ) ⊕ (−∞ ⊗ 𝑥3 ) = 2
47
(−∞ ⊗ 𝑥1 ) ⊕ (4 ⊗ 𝑥2 ) ⊕ (3 ⊗ 𝑥3 ) = 6 (−∞ ⊗ 𝑥1 ) ⊕ (−∞ ⊗ 𝑥2 ) ⊕ (0 ⊗ 𝑥3 ) = 2 sistem persamaan 𝐴 ⊗ 𝒙 = 𝒃 tersebut tidak punya penyelesaian, sebab bila punya 𝑥1 𝑥 penyelesaian berarti ada 𝒙 = [ 2 ] sehingga 𝑥3 𝑥1 2 0 10 −∞ [−∞ 4 3 ] ⊗ [𝑥 2 ] = [ 6 ] 𝑥3 2 −∞ −∞ 0 didapat (−∞ ⊗ 𝑥1 ) ⊕ (−∞ ⊗ 𝑥2 ) ⊕ (0 ⊗ 𝑥3 ) = 2 ⇔ (0 ⊗ 𝑥3 ) = 2 ⇔ 𝑥3 = 2 (−∞ ⊗ 𝑥1 ) ⊕ (4 ⊗ 𝑥2 ) ⊕ (3 ⊗ 𝑥3 ) = 6 ⇔ (4 ⊗ 𝑥2 ) ⊕ 5 = 6 ⇔ 𝑥2 = 2 (0 ⊗ 𝑥1 ) ⊕ (10 ⊗ 𝑥2 ) ⊕ (−∞ ⊗ 𝑥3 ) = 2 ⇔ 𝑥1 ⊕ 12 = 2 terlihat bahwa tidak akan ada 𝑥1 ∈ ℝ𝑚𝑎𝑥 sehingga 𝑥1 ⊕ 12 = 2 ⇔ max{𝑥1 , 12} = 2.
(4.1)
Jadi 𝐴 ⊗ 𝒙 = 𝒃 tidak punya penyelesaian. Oleh karena itu dikonstruksikan suatu semiring khusus yang merupakan perluasan dari ℝmax sedemikian hingga semua persamaan yang berbentuk persamaan (4.1) mempunyai penyelesaian. Semiring yang merupakan perluasan dari ℝmax disebut extended semiring tropical yang merupakan kasus khusus dari aljabar supertropical.
Pada
bagian
sebelumnya
telah
dijelaskan
mengenai
pengkonstruksian 𝑅 yang merupakan perluasan dari ℝmax . Dengan struktur semiring yang baru ini maka dapat digeneralisasikan suatu penyelesaian sistem persamaan linear menggunakan relasi ghost surpass ⊨ pada 𝑅. Pada pembahasan selanjutnya akan digunakan relasi ghost surpass ⊨ sebagai pengganti relasi =. Dengan relasi ghost surpass penyelesaian sistem persamaan
𝐴⊗𝒙 = 𝒃
akan
diperlemah
menjadi
𝐴 ⊗ 𝒙 ⊨ 𝒃.
Diantara
kemungkinan penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝒃 yang ada, dapat diklasifikasikan ke dalam penyelesaian tangible, ghost dan nol (𝜀 ≝ −∞). Selanjutnya, pembahasan akan difokuskan pada penyelesaian tangible dan nol (𝒙 ∈ 𝒯0 𝑛 ) dari sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃. Sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 mempunyai penyelesaian tunggal yang dapat diperoleh dengan menggunakan aturan Cramer.
48
Berikut diberikan penjelasan mengenai relasi ghost surpass pada 𝑅. Definisi 4.1. [8]. Diberikan 𝑎, 𝑏 ∈ 𝑅, maka 𝑎 ⊨ 𝑏 ⟺ 𝑎 = 𝑏 ⊕ 𝑐 untuk beberapa 𝑐 ∈ 𝒢0 □ Definisi 4.2. [8]. Diberikan 𝑎 ∈ 𝑅 , 𝑏 ∈ 𝒯 maka 𝑎 ⊨ 𝑏 ⟺ 𝑎 ⊕ 𝑏 ∈ 𝒢0 dan 𝑎 ⊨ 𝜀 ⟺ 𝑎 ∈ 𝒢0 □ Definisi 4.3. [5]. Diberikan 𝑎, 𝑏 ∈ 𝒯 maka 𝑎⊨𝑏⟺𝑎=𝑏 □ Definisi 4.4. [8]. Diberikan 𝑎 ∈ 𝒢0 , dan 𝑏 ∈ 𝑅 maka 𝑎 ⊨ 𝑏 ⟺ 𝑎 ≽𝒗 𝑏
□
Selanjutnya, akan dijelaskan mengenai himpunan penyelesaian dari suatu persamaan dengan menggunakan relasi ghost surpass pada 𝑅. Diberikan 𝑎 ∈ 𝒯 dan 𝑥 ∈ 𝑅. Jika diasumsikan persamaan dalam relasi ghost surpass dinyatakan sebagai : 1.
𝑥⊨𝑎
maka himpunan penyelesaian dari 𝑥 adalah {𝑎} ∪ {𝑏𝑣 |𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 𝑎 } 2.
𝑥 ⊨ 𝑎𝑣
maka himpunan penyelesaian dari 𝑥 adalah {𝑏𝑣 |𝑏 ∈ 𝒯 𝑑𝑎𝑛 𝑏 ≽𝑣 𝑎 } 3.
𝑥⊨𝜀
maka himpunan penyelesaian dari 𝑥 adalah {𝜀 } ∪ {𝑏𝑣 |𝑏 ∈ 𝒯 }
49
Contoh 4.1. Diberikan persamaan dalam relasi ghost surpass sebagai berikut : 1.
𝑥⊨2
himpunan penyelesaian dari 𝑥 adalah {2} ∪ {𝑏𝑣 |𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 2 } 2.
𝑥 ⊨ 8𝑣
himpunan penyelesaian dari 𝑥 adalah {𝑏𝑣 |𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 8 } 3.
𝑥⊕4⊨3
himpunan penyelesaian dari 𝑥 adalah {4} ∪ {𝑏𝑣 |𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 4 } 4.
𝑥 ⊕ 2𝑣 ⊨ 5
himpunan penyelesaian dari 𝑥 adalah {5} ∪ {𝑏𝑣 |𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 5 } 5.
𝑥 ⊕ 6𝑣 ⊨ 3
himpunan penyelesaian dari 𝑥 adalah {𝑏|𝑏 ∈ 𝒯 𝑑𝑎𝑛 𝑏 ≼𝑣 6 } ∪ {𝑑 𝑣 |𝑑 ∈ 𝒯 } ◊ Lemma 4.1. Diberikan 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝑅. Untuk setiap 𝑥 ∈ 𝑅 berlaku 𝑎 ⊗ 𝑥 ⊨ 𝑏 jika dan hanya jika 𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏. Bukti : i. Kasus yang pertama : akan ditinjau untuk 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝒯 untuk setiap 𝑎 ∈ 𝒯 terdapat 𝑎⊗−1 = −𝑎 ∈ 𝒯 sehingga 𝑎⊗−1 ⊗ 𝑏 ∈ 𝒯 jika 𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏 akan dibuktikan 𝑎 ⊗ 𝑥 ⊨ 𝑏 ⟺𝑎⊗𝑥 ⊨𝑏 ⟺ (𝑎 ⊗ (𝑎⊗−1 ⊗ 𝑏)) ⊨ 𝑏 ⟺ (𝑎 ⊗ 𝑎⊗−1 ⊗ 𝑏) ⊨ 𝑏 ⟺ (𝑎 ⊗ 𝑎⊗−1 ) ⊗ 𝑏 ⊨ 𝑏 ⟺𝑒⊗𝑏 ⊨𝑏 ⟺𝑏⊨𝑏 untuk setiap 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝒯 terbukti jika 𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏 maka 𝑎 ⊗ 𝑥 ⊨ 𝑏.
50
ii. Kasus yang kedua : akan ditinjau untuk 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝒢. untuk setiap 𝑎 ∈ 𝒯 terdapat 𝑎⊗−1 = −𝑎 ∈ 𝒯 sehingga 𝑎⊗−1 ⊗ 𝑏 ∈ 𝒢 jika 𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏 akan dibuktikan 𝑎 ⊗ 𝑥 ⊨ 𝑏 ⟺𝑎⊗𝑥 ⊨𝑏 ⟺ (𝑎 ⊗ (𝑎⊗−1 ⊗ 𝑏)) ⊨ 𝑏 ⟺ (𝑎 ⊗ 𝑎⊗−1 ⊗ 𝑏) ⊨ 𝑏 ⟺ (𝑎 ⊗ 𝑎⊗−1 ) ⊗ 𝑏 ⊨ 𝑏 ⟺𝑒⊗𝑏 ⊨𝑏 ⟺𝑏⊨𝑏 untuk setiap 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝒢 terbukti jika 𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏 maka 𝑎 ⊗ 𝑥 ⊨ 𝑏 .
∎
Teorema 4.1. [21]. Jika 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝒯. Untuk 𝑥 ∈ 𝒯 maka 𝑥 = 𝑎⊗−1 ⊗ 𝑏 adalah penyelesaian tunggal dari persamaan 𝑎 ⊗ 𝑥 ⊨ 𝑏. Bukti : Berdasarkan lemma 4.1 diketahui bahwa : 𝑎 ⊗ 𝑥 ⊨ 𝑏 ⟺ 𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏. Untuk 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝒯 berlaku 𝑎⊗−1 ⊗ 𝑏 ∈ 𝒯. Berdasarkan Definisi 4.3, maka diperoleh jika 𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏 dengan 𝑥 ∈ 𝒯 dan 𝑎⊗−1 ⊗ 𝑏 ∈ 𝒯 maka 𝑥 = 𝑎⊗−1 ⊗ 𝑏. Akan dibuktikan bahwa 𝑥 = 𝑎 ⊗−1 ⊗ 𝑏 merupakan penyelesaian tunggal dari persamaan 𝑎 ⊗ 𝑥 ⊨ 𝑏. Misalkan 𝑦 ∈ 𝒯 juga merupakan penyelesaian dari 𝑎 ⊗ 𝑥 ⊨ 𝑏, maka 𝑎 ⊗ 𝑦 ⊨ 𝑏 ⟺ 𝑦 ⊨ 𝑎⊗−1 ⊗ 𝑏 diketahui bahwa 𝑥 ⊨ 𝑎 ⊗−1 ⊗ 𝑏 merupakan penyelesaian dari 𝑎 ⊗ 𝑥 ⊨ 𝑏 sehingga didapat {
𝑥 ⊨ 𝑎⊗−1 ⊗ 𝑏 𝑦 ⊨ 𝑎⊗−1 ⊗ 𝑏
karena 𝑥 ∈ 𝒯, 𝑦 ∈ 𝒯 maka berdasarkan Definisi 4.3 didapat bahwa 𝑥 ⊨ 𝑦 ⟺ 𝑥 = 𝑦. Jadi terbukti bahwa jika 𝑦 merupakan penyelesaian yang lain dari 𝑎 ⊗ 𝑥 ⊨ 𝑏 maka pastilah 𝑦 = 𝑥 = 𝑎⊗−1 ⊗ 𝑏. Dengan kata lain, penyelesaian dari persamaan 𝑎 ⊗ 𝑥 ⊨ 𝑏 adalah tunggal yaitu 𝑥 = 𝑎⊗−1 ⊗ 𝑏.
51
∎
Teorema 4.2. [21]. Diberikan 𝑎 ∈ 𝒯 dan 𝑏 ∈ 𝒯. Solusi dari persamaan dengan relasi ghost surpass 𝑎 ⊗ 𝑥 ⊨ 𝑏 secara umum dapat ditulis sebagai : 𝑥𝑡 = 𝑥 ⊕ 𝑡 𝑣 dengan beberapa 𝑡 𝑣 ∈ 𝒢0 . Bukti : Berdasarkan Definisi 4.2 diketahui bahwa : 𝑎 ⊗ 𝑥 ⊨ 𝑏 ⟺ 𝑎 ⊗ 𝑥 ⊕ 𝑏 ⊨ 𝜀 ⟺ 𝑎 ⊗ 𝑥 ⊕ 𝑏 ∈ 𝒢0 Berdasarkan Teorema 4.1 diperoleh 𝑥 = 𝑎⊗−1 ⊗ 𝑏 adalah solusi tunggal dari persamaan 𝑎 ⊗ 𝑥 ⊨ 𝑏. Untuk semua 𝑡 ∈ 𝒯 dengan jelas dapat diperoleh 𝑎 ⊗ 𝑡 𝑣 ⊨ 𝜀 karena 𝑎 ⊗ 𝑡 𝑣 ∈ 𝒢0 dengan menambahkan persamaan 𝑎 ⊗ 𝑡 𝑣 ⊨ 𝜀 pada 𝑎 ⊗ 𝑥 ⊕ 𝑏 ⊨ 𝜀 didapat ⟺ (𝑎 ⊗ 𝑡 𝑣 ) ⊕ (𝑎 ⊗ 𝑥 ) ⊕ 𝑏 ⊨ 𝜀 ⟺ 𝑎 ⊗ (𝑥 ⊕ 𝑡 𝑣 ) ⊕ 𝑏 ⊨ 𝜀 sehingga diperoleh penyelesaiannya ⟺ (𝑎 ⊗ 𝑥 ) ⊕ (𝑎 ⊕ 𝑡 𝑣 ) ⊕ 𝑏 ⊨ 𝜀 ⟺ (𝑎 ⊗ 𝑥 ) ⊕ (𝑎 ⊕ 𝑡 𝑣 ) ⊨ 𝑏 ⟺ 𝑎 ⊗ (𝑥 ⊕ 𝑡 𝑣 ) ⊨ 𝑏 kalikan kedua ruas dengan 𝑎⊗−1 dari sebelah kiri diperoleh ⟺ 𝑎⊗−1 ⊗ 𝑎 ⊗ (𝑥 ⊕ 𝑡 𝑣 ) ⊨ 𝑎 ⊗−1 ⊗ 𝑏 ⟺ 𝑒 ⊗ (𝑥 ⊕ 𝑡 𝑣 ) ⊨ 𝑎⊗−1 ⊗ 𝑏 ⟺ (𝑒 ⊗ 𝑥 ) ⊕ (𝑒 ⊗ 𝑡 𝑣 ) ⊨ 𝑎⊗−1 ⊗ 𝑏 ⟺ 𝑥 ⊕ 𝑡 𝑣 ⊨ 𝑎⊗−1 ⊗ 𝑏 jika diasumsikan 𝑥𝑡 = 𝑥 ⊕ 𝑡 𝑣 , maka diperoleh 𝑥𝑡 ⊨ 𝑥 berdasarkan Definisi 4.1 diperoleh 𝑥𝑡 ⊨ 𝑥 ⟺ 𝑥𝑡 = 𝑥 ⊕ 𝑡 𝑣 dengan beberapa 𝑡 𝑣 ∈ 𝒢0 . Jika 𝑡 ≽𝑣 𝑥 maka 𝑥𝑡 = 𝑡 𝑣 . Oleh karena itu secara umum penyelesaian dari relasi ghost surpass 𝑎 ⊗ 𝑥 ⊨ 𝑏 dapat dituliskan sebagai 𝑥𝑡 = 𝑥 ⊕ 𝑡 𝑣 dengan beberapa 𝑡 𝑣 ∈ 𝒢0 .
∎
Persamaan 𝑎 ⊗ 𝑥 ⊨ 𝑏 dalam aljabar supertropical menggunakan relasi ghost surpass selalu mempunyai penyelesaian di 𝑅. Oleh karena itu 𝑅 dikatakan sebagai penutup dari ℝmax .
52
Relasi ghost surpass pada 𝑅 dapat diperluas untuk kasus vektor. Selanjutnya akan diberikan beberapa definisi terkait hal tersebut. Definisi 4.5. [8]. Diberikan 𝒖 ∈ 𝑅𝑛 dan 𝒘 ∈ 𝒯0 𝑛 , maka 𝒖 ⊨ 𝒘 ⟺ 𝒖 ⊕ 𝒘 ∈ 𝒢0 (𝑛) ekuivalen dengan 𝑢𝑖 ⊨ 𝑤𝑖 ⟺ 𝑢𝑖 ⊕ 𝑤𝑖 ∈ 𝒢0 untuk setiap 𝑖 ∈ 𝑛 □ Berdasarkan Definisi 4.5 dapat ditunjukkan bahwa : 1.
Jika 𝒖 ∈ 𝒯0 𝑛 maka 𝑢𝑖 ⊨ 𝑤𝑖 ⟺ 𝑢𝑖 = 𝑤𝑖 untuk setiap 𝑖 ∈ 𝑛.
2.
Jika 𝒖 ∈ 𝒢0 (𝑛) maka 𝑢𝑖 ⊨ 𝑤𝑖 ⟺ 𝑢𝑖 ≽𝒗 𝑤𝑖 untuk setiap 𝑖 ∈ 𝑛.
Definisi 4.6. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅), 𝒙 ∈ 𝑅𝑛 dan 𝒃 ∈ 𝒯0 𝑛 , maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 ⟺ 𝐴 ⊗ 𝒙 ⊕ 𝒃 ∈ 𝒢0 (𝑛). Jika diasumsikan 𝐴 = [𝑎𝑖𝑗 ], maka 𝑛
𝑝𝑖 = ⨁ 𝑎𝑖𝑗 ⊗ 𝑥𝑗 𝑗=1
diperoleh 𝑝𝑖 ⊨ 𝑏𝑖 ⟺ 𝑝𝑖 ⊕ 𝑏𝑖 ∈ 𝒢0 untuk setiap 𝑖 ∈ 𝑛 □ Berdasarkan Definisi 4.6 dapat ditunjukkan bahwa : 1.
Jika 𝒑 ∈ 𝒯0 𝑛 maka 𝑝𝑖 ⊨ 𝑏𝑖 ⟺ 𝑝𝑖 = 𝑏𝑖 untuk setiap 𝑖 ∈ 𝑛.
2.
Jika 𝒑 ∈ 𝒢0 (𝑛) maka 𝑝𝑖 ⊨ 𝑏𝑖 ⟺ 𝑝𝑖 ≽𝒗 𝑏𝑖 untuk setiap 𝑖 ∈ 𝑛.
Selanjutnya akan dibahas mengenai penyelesaian sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 dalam aljabar supertropical dengan menggunakan aturan Cramer. Sebelumnya akan diberikan beberapa Lemma terkait aturan Cramer. Lemma 4.2. [8]. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅), maka berlaku : 𝐴 ⊗ adj(A) ⊨ |𝐴| ⊗ 𝐼𝐴 Bukti : Akan dibuktikan 𝐴 ⊗ adj(A) ⊨ |𝐴| ⊗ 𝐼𝐴 .
53
Berdasarkan Definisi 4.2 mengenai relasi ghost surpass, maka untuk membuktikan 𝐴 ⊗ adj(A) ⊨ |𝐴| ⊗ 𝐼𝐴 sama juga dengan membuktikan bahwa : (𝐴 ⊗ adj(A)) ⊕ (|𝐴| ⊗ 𝐼𝐴 ) ∈ 𝒢0 (𝑛) didapat (𝐴 ⊗ adj(A)) ⊕ (|𝐴| ⊗ 𝐼𝐴 ) = [𝐴𝑖,𝑗 ] ⊗ [𝐶𝑜𝑓𝑗,𝑖 (𝐴)] ⊕ |𝐴| ⊗ 𝐼𝐴 = (|𝐴| ⊗ 𝐼𝐴 ) ⊕ (|𝐴| ⊗ 𝐼𝐴 ) ∈ 𝒢0 (𝑛) dengan demikian dapat disimpulkan bahwa 𝐴 ⊗ adj(A) = |𝐴| ⊗ 𝐼𝐴 .
∎
Lemma 4.3. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅) dengan partisi dari matriks 𝐴 yaitu 𝐹 adalah matriks berukuran (𝑛 − 1) × (𝑛 − 1) dari 𝐴 𝐻 adalah matriks berukuran 1 × (𝑛 − 1) dari 𝐴 𝐺 adalah matriks berukuran (𝑛 − 1) × 1 dari 𝐴 dan 𝑎𝑛,𝑛 adalah elemen tangible dari matriks 𝐴 sehingga 𝐹 𝐴 = [𝐻
𝐺 𝑎𝑛,𝑛 ]
maka berlaku : 𝐹 |𝐴 | = | 𝐻
𝐺 ( ( ) ) 𝑎𝑛,𝑛 | = (|𝐹| ⊗ 𝑎𝑛,𝑛 ) ⊕ 𝐻 ⊗ adj F ⊗ 𝐺 ∎
Berikut diberikan formula Cramer dalam aljabar supertropical. Teorema 4.3. [8]. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅) dan 𝒃 ∈ 𝒯0 𝑛 . Untuk setiap penyelesaian 𝒙 ∈ 𝑅𝑛 dari sistem persamaan 𝐴⊗𝒙 ⊨𝒃
(4.2)
memenuhi : |𝐴| ⊗ 𝒙 ⊨ adj(A) ⊗ 𝒃
(4.3)
maka penyelesaian 𝒙 = |𝐴|⊗−1 ⊗ (adj(A) ⊗ 𝒃). Bukti : Akan ditunjukkan bahwa 𝒙 = |𝐴|⊗−1 ⊗ adj(A) ⊗ 𝒃 merupakan penyelesaian dari sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃. Berdasarkan Lemma 4.2 didapat :
54
𝐴 ⊗ adj(A) ⊨ |𝐴| ⊗ 𝐼𝐴
(4.4)
Asumsikan |𝐴| ∈ 𝒯, kalikan kedua ruas dari persamaan (4.4) dengan |𝐴|⊗−1 ⊗ 𝒃 dari sebelah kanan didapat (𝐴 ⊗ adj(A)) ⊗ (|𝐴|⊗−1 ⊗ 𝒃 ) ⊨ (|𝐴| ⊗ 𝐼𝐴 ) ⊗ (|𝐴|⊗−1 ⊗ 𝒃 ) ⟺ 𝐴 ⊗ (adj(A) ⊗ |𝐴|⊗−𝟏 ⊗ 𝒃) ⊨ (|𝐴| ⊗ |𝐴|⊗−1 ) ⊗ (𝐼𝐴 ⊗ 𝒃 ) ⟺ 𝐴 ⊗ (|𝐴|⊗−1 ⊗ adj(A) ⊗ 𝒃) ⊨ (𝐼𝐴 ⊗ 𝒃 ) ⟺ 𝐴 ⊗ 𝒙 ⊨ 𝒃. dapat dilihat bahwa 𝒙 = |𝐴|⊗−1 ⊗ adj(A) ⊗ 𝒃 merupakan penyelesaian dari sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃.
∎
Teorema 4.4. [8]. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅) dan 𝒃 ∈ 𝒯0 𝑛 . Jika diasumsikan (adj(A) ⊗ 𝒃) ∈ 𝒯0 𝑛 dan |𝐴| ∈ 𝒯, maka 𝒙 = |𝐴|⊗−𝟏 ⊗ (adj(A) ⊗ 𝒃) adalah solusi tunggal dari 𝐴 ⊗ 𝒙 ⊨ 𝒃. Bukti : Akan ditunjukkan bahwa 𝒙 = |𝐴|⊗−1 ⊗ (adj(A) ⊗ 𝒃) merupakan solusi tunggal dari 𝐴 ⊗ 𝒙 ⊨ 𝒃. ketunggalan solusi dari persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 akan dibuktikan dengan menggunakan induksi matematika. untuk 𝑛 = 1 jelas, sebab berdasarkan Teorema 4.1 diperoleh 𝑎⊗𝑥 ⊨𝑏 𝑥 = 𝑎⊗−1 ⊗ 𝑏 diasumsikan benar untuk 𝑛 = 𝑘 − 1 akan dibuktikan benar untuk 𝑛 = 𝑘 Jika diasumsikan partisi dari 𝐴 ∈ 𝑀𝑛 (𝑅), 𝒃 ∈ 𝒯0 𝑛 dan 𝒙 ∈ 𝒯0 𝑛 sebagai berikut : 𝐻 𝐴=[ 𝐹
𝑋 𝑎1,𝑛 𝑏 ] , 𝒃 = [ 1] , 𝒙 = [ ] 𝑥 𝐵 𝐺 𝑛
dengan 𝐻 matriks berukuran 1 × (𝑛 − 1) dari 𝐴 𝐹 matriks berukuran (𝑛 − 1) × (𝑛 − 1) dari 𝐴 𝐺 matriks berukuran (𝑛 − 1) × 1 dari 𝐴 𝐵 matriks berukuran (𝑛 − 1) × 1 dari 𝒃
55
𝑋 matriks berukuran (𝑛 − 1) × 1 dari 𝒙 𝑎1,𝑛 adalah elemen tangible dari matriks 𝐴 𝑏1 adalah elemen tangible dari vektor 𝒃 dan 𝑥𝑛 adalah elemen tangible dari vektor 𝒙 sehingga persamaan 𝐴⊗𝒙 ⊨𝒃 dapat ditulis sebagai 𝐻 [ 𝐹
𝑋 𝑎1,𝑛 𝑏 ] ⊗ [ ] ⊨ [ 1] 𝑥 𝐵 𝐺 𝑛
𝐴⊗𝒙 ⊨ 𝒃 ⟺ {
(𝐻 ⊗ 𝑋) ⊕ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) ⊨ 𝑏1 (𝐹 ⊗ 𝑋 ) ⊕ (𝐺 ⊗ 𝑥 𝑛 ) ⊨ 𝐵
(4.5) (4.6)
dari Lemma 4.2 diketahui bahwa : 𝐴 ⊗ adj(A) = |𝐴| ⊗ 𝐼𝐴 sehingga ⊗−1
𝐴 = (adj(A))
⊗ |𝐴| ⊗ 𝐼𝐴 ⊗−1
⟺ 𝐴 = |𝐴| ⊗ (adj(A))
⊗ 𝐼𝐴 ⊗−1
⟺ 𝐴⊗−1 = (|𝐴| ⊗ (adj(A))
⊗−1
⊗ 𝐼𝐴 )
⟺ 𝐴⊗−1 = |𝐴|⊗−1 ⊗ adj(A) ⊗ (𝐼𝐴 )⊗−1 ⟺ 𝐴⊗−1 = |𝐴|⊗−1 ⊗ adj(A) berdasakan Definisi 2.20, maka didapat 𝐴∇ = |𝐴|⊗−1 ⊗ adj(A) dari persamaan (4.6) diperoleh (𝐹 ⊗ 𝑋 ) ⊨ 𝐵 ⊕ (𝐺 ⊗ 𝑥 𝑛 ) kalikan kedua ruas dengan 𝐹 ∇ dari sebelah kiri, diperoleh 𝐹 ∇ ⊗ (𝐹 ⊗ 𝑋) ⊨ 𝐹 ∇ ⊗ (𝐵 ⊕ (𝐺 ⊗ 𝑥𝑛 )) (𝐹 ∇ ⊗ 𝐹 ⊗ 𝑋 ) ⊨ ( 𝐹 ∇ ⊗ 𝐵 ) ⊕ (𝐹 ∇ ⊗ 𝐺 ⊗ 𝑥 𝑛 ) 𝑋 ⊨ (𝐹 ∇ ⊗ 𝐵 ) ⊕ ( 𝐹 ∇ ⊗ 𝐺 ⊗ 𝑥 𝑛 ) 𝑋 ⊨ 𝐹 ∇ ⊗ (𝐵 ⊕ (𝐺 ⊗ 𝑥𝑛 )) 𝑋 ⊨ (|𝐹 |⊗−1 ⊗ adj(F)) ⊗ (𝐵 ⊕ (𝐺 ⊗ 𝑥𝑛 )) substitusikan persamaan (4.7) pada persamaan (4.5), diperoleh
56
(4.7)
(𝐻 ⊗ 𝑋) ⊕ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) ⊨ 𝑏1 ⟺ 𝐻 ⊗ (|𝐹 |⊗−1 ⊗ adj(F)) ⊗ (𝐵 ⊕ (𝐺 ⊗ 𝑥𝑛 )) ⊕ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) ⊨ 𝑏1 ⟺ (|𝐹 |⊗−1 ⊗ 𝐻 ⊗ adj(F)) ⊗ (𝐵 ⊕ (𝐺 ⊗ 𝑥𝑛 )) ⊕ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) ⊨ 𝑏1 ⟺ (|𝐹|⊗−1 ⊗ 𝐻 ⊗ adj(F) ⊗ 𝐵) ⊕ (|𝐹 |⊗−1 ⊗ 𝐻 ⊗ adj(F) ⊗ (𝐺 ⊗ 𝑥𝑛 )) ⊕ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) ⊨ 𝑏1
(4.8)
kalikan persamaan (4.8) dengan |𝐹 | dari sebelah kiri, diperoleh ⟺ (𝐻 ⊗ adj(F) ⊗ 𝐵) ⊕ (𝐻 ⊗ adj(F) ⊗ (𝐺 ⊗ 𝑥𝑛 )) ⊕ |𝐹 | ⊗ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) ⊨ |𝐹 | ⊗ 𝑏1 ⟺ |𝐹 | ⊗ (𝑎1,𝑛 ⊗ 𝑥𝑛 ) ⊕ (𝐻 ⊗ adj(F) ⊗ (𝐺 ⊗ 𝑥𝑛 )) ⊨ (|𝐹 | ⊗ 𝑏1 ) ⊕ (𝐻 ⊗ adj(F) ⊗ 𝐵) ⟺ 𝑥𝑛 ⊗ ((|𝐹 | ⊗ 𝑎1,𝑛 ) ⊕ (𝐻 ⊗ adj(F) ⊗ 𝐺 )) ⊨ (|𝐹 | ⊗ 𝑏1 ) ⊕ (𝐻 ⊗ adj(F) ⊗ 𝐵) ⟺ 𝑥𝑛 ⊨
(|𝐹 | ⊗ 𝑏1 ) ⊕ (𝐻 ⊗ adj(F) ⊗ 𝐵) ((|𝐹 | ⊗ 𝑎1,𝑛 ) ⊕ (𝐻 ⊗ adj(F) ⊗ 𝐺 ))
dari Lemma 4.3, diperoleh |𝐴| = ((|𝐹 | ⊗ 𝑎1,𝑛 ) ⊕ (𝐻 ⊗ adj(F) ⊗ 𝐺 )) dan (adj(A) ⊗ 𝑏)𝑛 = (|𝐹 | ⊗ 𝑏1 ) ⊕ (𝐻 ⊗ adj(F) ⊗ 𝐵) sehingga diperoleh 𝑥𝑛 ⊨
(adj(A) ⊗ 𝑏)𝑛 |𝐴|
⟺ 𝑥𝑛 ⊨ |𝐴|⊗−1 ⊗ (adj(A) ⊗ 𝑏)𝑛 karena (adj(A) ⊗ 𝒃) ∈ 𝒯0 𝑛 dan |𝐴| ∈ 𝒯 didapat 𝑥𝑛 ∈ 𝒯0 𝑛 untuk setiap 𝑛. Jadi terbukti bahwa : 𝒙 = |𝐴|⊗−𝟏 ⊗ (adj(A) ⊗ 𝒃) ∎
merupakan solusi tunggal.
57
Dengan kata lain, jika diasumsikan 𝐷𝑥𝑖 adalah determinan dari matriks yang diperoleh dengan cara mengganti kolom ke-𝑖 dari matriks 𝐴 dengan 𝒃 sehingga (adj(A) ⊗ 𝑏)𝑖 = 𝐷𝑥𝑖 dan diasumsikan 𝐷 = |𝐴| maka persamaan 4.2 : |𝐴| ⊗ 𝒙 ⊨ adj(A) ⊗ 𝒃 menjadi ⟺ 𝐷 ⊗ 𝒙 ⊨ adj(A) ⊗ 𝒃 ⟺ 𝒙 ⊨ adj(A) ⊗ 𝒃 ⊗ 𝐷⊗−𝟏 ⟺ 𝑥𝑖 ⊨ (adj(A) ⊗ 𝒃)𝑖 ⊗ 𝐷⊗−𝟏 ⟺ 𝑥𝑖 ⊨ 𝐷𝑥𝑖 ⊗ 𝐷⊗−𝟏 ⟺ 𝑥𝑖 = 𝐷⊗−1 ⊗ 𝐷𝑥𝑖 jika 𝐷𝑥𝑖 ∈ 𝒯 dan 𝐷 ∈ 𝒯 maka dihasilkan 𝑥𝑖 ∈ 𝒯0 𝑛 untuk setiap 𝑖 ∈ 𝑛, sehingga dengan menggunakan sifat relasi ghost surpass diperoleh 𝑥𝑖 = 𝐷⊗−1 ⊗ 𝐷𝑥𝑖 Hal ini sesuai dengan formula Cramer pada aljabar klasik.
∎
Berdasarkan Teorema yang telah dibahas, didapatkan syarat perlu dan syarat cukup sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 atas aljabar supertropical mempunyai penyelesaian tunggal yang tangible yaitu jika dan hanya jika |𝐴| ∈ 𝒯 dan (adj(A) ⊗ 𝒃) ∈ 𝒯0 𝑛 . Jika kondisi tersebut tidak terpenuhi maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 mempunyai penyelesaian tidak tunggal. Berikut ini diberikan contoh kasus sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 mempunyai penyelesaian tunggal dan tidak tunggal. 4.1.1 Penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝒃 dimana |𝑨| ∈ 𝓣 dalam Aljabar Supertropical Contoh 4.2. Kasus 𝐴 ⊗ 𝒙 ⊨ 𝒃 mempunyai penyelesaian tunggal Selesaikan 𝐴 ⊗ 𝒙 ⊨ 𝒃, jika 𝑥1 1 −9 4 1 𝑥 𝐴 = [−4 18 −8] , 𝑥 = [ 2 ] dan , 𝑏 = [−6] 𝑥3 2 1 −4 −3 penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝒃 dengan menggunakan aturan Cramer 𝐷 = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 )
58
⟺ 𝐷 = (1 ⊗ 18 ⊗ −4) ⊕ (1 ⊗ −8 ⊗ 1) ⊕ (−9 ⊗ −4 ⊗ −4) ⊕ (−9 ⊗ −8 ⊗ 2) ⊕ (4 ⊗ −4 ⊗ 1) ⊕ (4 ⊗ 18 ⊗ 2) ⟺ 𝐷 = 15 ⊕ −6 ⊕ −17 ⊕ −15 ⊕ 1 ⊕ 24 = 24 ∈ 𝒯. 1 𝐷1 = |−6 −3
−9 18 1
4 −8| −4
⟺ 𝐷1 = (1 ⊗ 18 ⊗ −4) ⊕ (1 ⊗ −8 ⊗ 1) ⊕ (−9 ⊗ −6 ⊗ −4) ⊕ (−9 ⊗ −8 ⊗ −3) ⊕ (4 ⊗ −6 ⊗ 1) ⊕ (4 ⊗ 18 ⊗ −3) ⟺ 𝐷1 = 15 ⊕ −6 ⊕ −19 ⊕ −20 ⊕ −1 ⊕ 19 = 19 ∈ 𝒯. 1 1 4 𝐷2 = |−4 −6 −8| 2 −3 −4 ⟺ 𝐷2 = (1 ⊗ −6 ⊗ −4) ⊕ (1 ⊗ −8 ⊗ −3) ⊕ (1 ⊗ −4 ⊗ −4) ⊕ (1 ⊗ −8 ⊗ 2) ⊕ (4 ⊗ −4 ⊗ −3) ⊕ (4 ⊗ −6 ⊗ 2) ⟺ 𝐷2 = −9 ⊕ −10 ⊕ −9 ⊕ −5 ⊕ −3 ⊕ 0 = 0 ∈ 𝒯. 1 −9 1 𝐷3 = |−4 18 −6| 2 1 −3 ⟺ 𝐷3 = (1 ⊗ 18 ⊗ −3) ⊕ (1 ⊗ −6 ⊗ 1) ⊕ (−9 ⊗ −4 ⊗ −3) ⊕ (−9 ⊗ −6 ⊗ 2) ⊕ (1 ⊗ −4 ⊗ 1) ⊕ (1 ⊗ 18 ⊗ 2) ⟺ 𝐷3 = 16 ⊕ −4 ⊕ −16 ⊕ −13 ⊕ −2 ⊕ 21 = 21 ∈ 𝒯. sehingga diperoleh 𝐷1 19 adj(A) ⊗ 𝒃 = [𝐷2 ] = [ 0 ] ∈ 𝒯0 𝑛 𝐷3 1 penyelesaian dari persamaan tersebut adalah 𝐷1 19 = = −24 ⊗ 19 = −5 𝐷 24 𝐷2 0 𝑥2 = = = −24 ⊗ 0 = −24 𝐷 24 𝐷1 21 𝑥3 = = = −24 ⊗ 21 = −3 𝐷 24 hal ini bisa di cek sebagai berikut : 𝑥1 =
1 𝐴 ⊗ 𝒙 = [−4 2
−9 18 1
𝑚𝑎𝑥(−4, −33,1) 4 −5 1 −8] ⊗ [−24] = [𝑚𝑎𝑥(−9, −6, −11)] = [−6] = 𝒃. −4 −3 −3 𝑚𝑎𝑥(−3, −23, −7)
59
karena 𝐷 ∈ 𝒯 dan 𝐷𝑥𝑖 ∈ 𝒯 untuk setiap 𝑖, maka persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 dalam aljabar supertropical 𝑅 mempunyai penyelesaian tunggal. Dengan demikian penyelesaian tersebut merupakan penyelesaian tunggal di ℝmax . Contoh 4.3. Kasus 𝐴 ⊗ 𝒙 ⊨ 𝒃 mempunyai penyelesaian tidak tunggal Selesaikan 𝐴 ⊗ 𝒙 ⊨ 𝒃, jika 𝑥1 1 −9 4 2 𝑥 𝐴 = [−4 18 −8] , 𝑥 = [ 2 ] dan , 𝑏 = [1] 𝑥3 2 1 −4 3 penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝒃 dengan menggunakan aturan Cramer 𝐷 = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) ⟺ 𝐷 = (1 ⊗ 18 ⊗ −4) ⊕ (1 ⊗ −8 ⊗ 1) ⊕ (−9 ⊗ −4 ⊗ −4) ⊕ (−9 ⊗ −8 ⊗ 2) ⊕ (4 ⊗ −4 ⊗ 1) ⊕ (4 ⊗ 18 ⊗ 2) ⟺ 𝐷 = 15 ⊕ −6 ⊕ −17 ⊕ −15 ⊕ 1 ⊕ 24 = 24 ∈ 𝒯. 2 𝐷1 = |1 3
−9 18 1
4 −8| −4
⟺ 𝐷1 = (2 ⊗ 18 ⊗ −4) ⊕ (2 ⊗ −8 ⊗ 1) ⊕ (−9 ⊗ 1 ⊗ −4) ⊕ (−9 ⊗ −8 ⊗ 3) ⊕ (4 ⊗ 1 ⊗ 1) ⊕ (4 ⊗ 18 ⊗ 3) ⟺ 𝐷1 = 16 ⊕ −5 ⊕ −12 ⊕ −14 ⊕ 6 ⊕ 25 = 25 ∈ 𝒯. 1 𝐷2 = |−4 2
2 1 3
4 −8| −4
⟺ 𝐷2 = (1 ⊗ 1 ⊗ −4) ⊕ (1 ⊗ −8 ⊗ 3) ⊕ (2 ⊗ −4 ⊗ −4) ⊕ (2 ⊗ −8 ⊗ 2) ⊕ (4 ⊗ −4 ⊗ 3) ⊕ (4 ⊗ 1 ⊗ 2) ⟺ 𝐷2 = −2 ⊕ −4 ⊕ −6 ⊕ −4 ⊕ 3 ⊕ 7 = 7 ∈ 𝒯. 1 −9 2 𝐷3 = |−4 18 1| 2 1 3 ⟺ 𝐷3 = (1 ⊗ 18 ⊗ 3) ⊕ (1 ⊗ 1 ⊗ 1) ⊕ (−9 ⊗ −4 ⊗ 3) ⊕ (−9 ⊗ 1 ⊗ 2) ⊕ (2 ⊗ −4 ⊗ 1) ⊕ (2 ⊗ 18 ⊗ 2) ⟺ 𝐷3 = 22 ⊕ 3 ⊕ −10 ⊕ −6 ⊕ −1 ⊕ 22 = 22𝑣 ∈ 𝒢0 . sehingga diperoleh
60
◊
𝐷1 25 adj(A) ⊗ 𝒃 = [𝐷2 ] = [ 7 ] ∉ 𝒯0 𝑛 𝐷3 22𝑣 penyelesaian dari persamaan tersebut adalah 𝐷1 25 = = −24 ⊗ 25 = 1 𝐷 24 𝐷2 7 𝑥2 = = = −24 ⊗ 7 = −17 𝐷 24 𝐷1 22𝑣 = = −24 ⊗ 22𝑣 = −2𝑣 𝑥3 = 24 𝐷 𝑥1 =
hal ini bisa di cek sebagai berikut : 1 𝐴 ⊗ 𝒙 = [−4 2
−9 18 1
𝑚𝑎𝑥(2, −26,2) 1 2 4 2𝑣 −8] ⊗ [−17] = [ 𝑚𝑎𝑥 (−3,1, −10) ] = [ 1 ] ⊨ [1] = 𝒃. −2𝑣 3 −4 3 𝑚𝑎𝑥 (3, −16, −6𝑣 )
karena 𝐷 ∈ 𝒯 dan terdapat 𝐷𝑥𝑖 ∈ 𝒢 untuk beberapa 𝑖, maka persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 dalam aljabar supertropical 𝑅 mempunyai penyelesaian tidak tunggal. penyelesaian tangible dengan 𝑘3 ∈ 𝒯 adalah 1 𝒙 = [−17] untuk setiap 𝑘3 ≼𝑣 − 2. 𝑘3
◊
Proposisi 4.1. [8] Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅) dimana |𝐴| ∈ 𝒢0 ≠ 𝜀, 𝒃 ∈ 𝒯0 𝑛 dan 𝒙 ∈ 𝒯0 𝑛 maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃
mempunyai penyelesaian 𝑘 ⊗ 𝒙 ∈
𝑅𝑛 dengan 𝒙 adalah kolom ke-𝑖 yang tangible dari adj(𝐴) untuk beberapa 𝑖 ∈ 𝑛 dan 𝑘 ∈ 𝒯.
∎
4.2.1 Penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝒃 dimana |𝑨| ∈ 𝓖𝟎 ≠ 𝜺 dalam Aljabar Supertropical Contoh 4.4. Kasus 𝐴 ⊗ 𝒙 ⊨ 𝒃 mempunyai penyelesaian tidak tunggal Selesaikan 𝐴 ⊗ 𝒙 ⊨ 𝒃, jika 1 𝐴 = [4 2
2 1 2
𝑥1 3 1 𝑥 5] , 𝒙 = [ 2 ] dan 𝒃 = [1] 𝑥3 2 4
61
|𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 )
⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) ⟺ |𝐴| = (1 ⊗ 1 ⊗ 2) ⊕ (1 ⊗ 5 ⊗ 2) ⊕ (2 ⊗ 4 ⊗ 2) ⊕ (2 ⊗ 5 ⊗ 2) ⊕ (3 ⊗ 4 ⊗ 2) ⊕ (3 ⊗ 1 ⊗ 2) ⟺ |𝐴| = 4 ⊕ 8 ⊕ 8 ⊕ 9 ⊕ 9 ⊕ 6 = 9𝑣 ∈ 𝒢0 . Penyelesaian dari 𝐴 ⊗ 𝒙 ⊨ 𝒃 adalah 7 5 7 adj(A) = [7 5 7] 6 4 6 penyelesaian 𝒙 merupakan kolom ke-𝑖 yang tangible dari adj(𝐴) yaitu kolom ke-1, kolom ke-2 dan kolom ke- 3. jika 𝒙 adalah kolom ke-1 dan kolom ke-3 dari Adj (𝐴), maka 7 𝒙 = [7 ] 6 hal ini bisa di cek sebagai berikut : 2 3 7 1 9𝑣 𝑣 ] [ ] [ ] [ ⊗ = ⊨ 7 1 5 1] 11 𝑣 2 2 6 4 9 jika 𝒙 adalah kolom ke-2 dari Adj (𝐴), maka 1 𝐴 ⊗ 𝒙 = [4 2
5 𝒙 = [5 ] 4 hal ini bisa di cek sebagai berikut : 1 𝐴 ⊗ 𝒙 = [4 2
2 3 1 5 7𝑣 𝑣 1 5 ] ⊗ [5 ] = [9 ] ⊨ [1 ] 2 2 4 4 7𝑣
penyelesaian lain dari 𝐴 ⊗ 𝒙 ⊨ 𝒃 adalah 𝑝1 𝒙 = 𝑘 ⊗ [𝑝2 ] 𝑝3 dengan 𝑝1 = 7, 𝑝2 = 7, 𝑝3 = 6 atau 𝑝1 = 5, 𝑝2 = 5, 𝑝3 = 4. Untuk setiap 𝑘 ∈ 𝒯 yang besar sedemikian hingga memenuhi 𝐴 ⊗ 𝒙 ⊨ 𝒃.
62
◊
Dalam hal ini |𝐴| ≠ 𝜀 bukan merupakan syarat perlu dari sistem 𝐴 ⊗ 𝒙 ⊨ 𝒃 dalam aljabar supertropical 𝑅 agar memiliki solusi untuk semua nilai 𝒃.
Contoh 4.5. Diberikan 𝑒 𝐴 = [𝑒 𝑒
𝑒 𝑒 𝑒
𝜀 𝜀] 𝜀
|𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) ⟺ |𝐴 | = (𝑒 ⊗ 𝑒 ⊗ 𝜀 ) ⊕ (𝑒 ⊗ 𝜀 ⊗ 𝑒 ) ⊕ (𝑒 ⊗ 𝑒 ⊗ 𝜀 ) ⊕ (𝑒 ⊗ 𝜀 ⊗ 𝑒 ) ⊕ (𝜀 ⊗ 𝑒 ⊗ 𝑒) ⊕ (𝜀 ⊗ 𝑒 ⊗ 𝑒) ⟺ 𝐷 = 𝜀 ⊕ 𝜀 ⊕ 𝜀 ⊕ 𝜀 ⊕ 𝜀 ⊕ 𝜀 = 𝜀. Ambil 𝑡 ∈ 𝒯 dan 𝑏𝑖 ≼𝑣 𝑡 untuk semua nilai 𝑖, dan 𝑥 = [𝑡
𝑡
𝜀 ]𝑇
maka diperoleh 𝑒 𝐴 ⊗ 𝒙 = [𝑒 𝑒
𝑒 𝑒 𝑒
𝑚𝑎𝑥(𝑡, 𝑡, 𝜀 ) 𝜀 𝑡 𝑡𝑣 𝜀 ] ⊗ [𝑡 ] = [𝑚𝑎𝑥(𝑡, 𝑡, 𝜀 )] = [𝑡 𝑣 ]. 𝜀 𝜀 𝑚𝑎𝑥(𝑡, 𝑡, 𝜀 ) 𝑡𝑣
𝑡 Dari yang diketahui bahwa 𝑏𝑖 ≼𝑣 𝑡 untuk semua nilai 𝑖 berarti 𝑏𝑖 ≼𝑣 [𝑡] 𝑡 berdasarkan perhitungan, maka didapatkan bahwa : meskipun |𝐴| = 𝜀 dapat ditemukan nilai 𝒙 sehingga memenuhi 𝐴 ⊗ 𝒙 ⊨ 𝒃 dengan 𝑥 = [𝑡
𝑡
𝜀 ]𝑇 .
Berikut diberikan contoh penyelesaian sistem persamaan linear 𝐴 ⊗ 𝒙 = 𝒃 dalam aljabar supertropical. Contoh 4.6. Selesaikan 𝐴 ⊗ 𝒙 = 𝒃, jika 𝑥1 4 0 −2 5 𝑥 𝐴 = [−1 −2 −5] , 𝑥 = [ 2 ] dan , 𝒃 = [1] 𝑥3 −1 −2 −2 2 Penyelesaian 𝐴 ⊗ 𝒙 = 𝒃 dengan menggunakan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 didapatkan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 sebagai berikut :
63
1 5 𝐷𝐴,𝑏 = [2 3 3 4
7 1 0 6] dan 𝑅𝐴,𝑏 = [0 1 0 0 4
0 0] 1
terlihat bahwa setiap kolom matriks 𝑅𝐴,𝑏 hanya terdapat tepat satu elemen bernilai 1. Hal ini menandakan bahwa 𝐴 ⊗ 𝒙 = 𝒃 hanya mempunyai tepat satu penyelesaian 𝒙 dengan elemen-elemennya adalah minimum dari setiap kolom matriks 𝐷𝐴,𝑏 yaitu 1 𝒙 = [3 ] 4 hal ini bisa di cek sebagai berikut : 4 𝐴 ⊗ 𝒙 = [−1 −1
0 −2 −2
𝑚𝑎𝑥(5,3,2) −2 1 5 ( ) ] [ ] [ ⊗ = [ 𝑚𝑎𝑥 0,1, −1 ] = −5 3 1] = 𝒃. −2 4 𝑚𝑎𝑥(0,1,2) 2
Dari hal tersebut dapat dijelaskan bahwa :
Pada baris pertama nilai maksimum dicapai hanya satu kali, dengan demikian persamaan baris pertama menetapkan elemen 𝑥1 = 1.
Pada baris kedua nilai maksimum dicapai hanya satu kali. Dengan demikian persamaan baris kedua menetapkan elemen 𝑥2 = 3.
Pada baris ketiga didapatkan nilai maksimum dicapai hanya satu kali. Dengan demikian persamaan baris ketiga menetapkan elemen 𝑥3 = 4. Setiap elemen-elemen yang sudah dipilih ini tidak bisa diubah, bila diubah
yang lain maka akan membentuk pertaksamaan. Karena pada keseluruhan baris, nilai maksimum hanya dicapai satu kali, maka hanya terdapat satu cara untuk mencapai persamaan pada semua baris yaitu dengan menetapkan elemen 𝑥1 = 1, 𝑥2 = 3, 𝑥3 = 4. Dengan demikian persamaan 𝐴 ⊗ 𝒙 = 𝒃 memiliki penyelesaian tunggal.
Selanjutnya,
persamaan
𝐴⊗𝒙=𝒃
akan
diselesaikan
dengan
menggunakan aturan Cramer dalam aljabar supertropical sebagai berikut 𝐷 = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) ⟺ 𝐷 = (4 ⊗ −2 ⊗ −2) ⊕ (4 ⊗ −5 ⊗ −2) ⊕ (0 ⊗ −1 ⊗ −2) ⊕
64
(0 ⊗ −5 ⊗ −1) ⊕ (−2 ⊗ −1 ⊗ −2) ⊕ (−2 ⊗ −2 ⊗ −1) ⟺ 𝐷 = 0 ⊕ −3 ⊕ −3 ⊕ −6 ⊕ −5 ⊕ −5 = 0 ∈ 𝒯. 5 𝐷1 = [1 2
0 −2 −2
−2 −5] −2
⟺ 𝐷1 = (5 ⊗ −2 ⊗ −2) ⊕ (5 ⊗ −5 ⊗ −2) ⊕ (0 ⊗ 1 ⊗ −2) ⊕ (0 ⊗ −5 ⊗ 2) ⊕ (−2 ⊗ 1 ⊗ −2) ⊕ (−2 ⊗ −2 ⊗ 2) ⟺ 𝐷1 = 1 ⊕ −2 ⊕ −1 ⊕ −3 ⊕ −3 ⊕ −2 = 1 ∈ 𝒯. 4 5 −2 𝐷2 = [−1 1 −5] −1 2 −2 ⟺ 𝐷2 = (4 ⊗ 1 ⊗ −2) ⊕ (4 ⊗ −5 ⊗ 2) ⊕ (5 ⊗ −1 ⊗ −2) ⊕ (5 ⊗ −5 ⊗ −1) ⊕ (−2 ⊗ −1 ⊗ 2) ⊕ (−2 ⊗ 1 ⊗ −1) ⟺ 𝐷2 = 3 ⊕ 1 ⊕ 2 ⊕ −1 ⊕ −1 ⊕ −2 = 3 ∈ 𝒯. 4 0 5 𝐷3 = [−1 −2 1] −1 −2 2 ⟺ 𝐷3 = (4 ⊗ −2 ⊗ 2) ⊕ (4 ⊗ 1 ⊗ −2) ⊕ (0 ⊗ −1 ⊗ 2) ⊕ (0 ⊗ 1 ⊗ −1) ⊕ (5 ⊗ −1 ⊗ −2) ⊕ (5 ⊗ −2 ⊗ −1) ⟺ 𝐷3 = 4 ⊕ 3 ⊕ 1 ⊕ 0 ⊕ 2 ⊕ 2 = 4 ∈ 𝒯. sehingga diperoleh 𝐷1 1 ( ) 𝐷 adj A ⊗ 𝒃 = [ 2 ] = [3] ∈ 𝒯0 𝑛 𝐷3 4 penyelesaian dari persamaan tersebut adalah 𝐷1 1 = = −0 ⊗ 1 = 1 𝐷 0 𝐷2 3 𝑥2 = = = −0 ⊗ 3 = 3 𝐷 0 𝐷1 4 𝑥3 = = = −0 ⊗ 4 = 4 𝐷 0 𝑥1 =
hal ini bisa di cek sebagai berikut : 4 𝐴 ⊗ 𝒙 = [−1 −1
0 −2 −2
𝑚𝑎𝑥(5,3,2) −2 1 5 −5] ⊗ [3] = [𝑚𝑎𝑥(0,1, −1)] = [1] = 𝒃 −2 4 𝑚𝑎𝑥(0,1,2) 2
65
karena 𝐷 ∈ 𝒯 dan 𝐷𝑥𝑖 ∈ 𝒯 untuk setiap 𝑖, maka penyelesaian tersebut merupakan ◊
penyelesaian tunggal di ℝmax .
Selanjutnya, akan diberikan contoh penyelesaian sistem persamaaan linear 𝐴 ⊗ 𝒙 = 𝒃 dengan 𝐴𝑚×𝑛 (𝑅) adalah matriks berukuran 𝑚 × 𝑛 dengan entri matriks anggota 𝑅. 𝒃 ∈ 𝑅𝑛 adalah vektor tangible, dan 𝒙 ∈ 𝑅𝑚 .
Contoh 4.7. (Banyak persamaan kurang dari banyak peubah) 𝑥1 7 2 5 1 𝑥 ] , 𝑥 = [ 2] , 𝑏 = [ ] Selesaikan 𝐴 ⊗ 𝒙 = 𝒃, jika 𝐴 = [ 10 3 8 2 𝑥3
2 [5 1
𝐴𝑇 ⊗ 𝐴 ⊗ 𝒙 = 𝐴𝑇 ⊗ 𝒃 𝑥1 2 3 3 7 2 5 1 ] [𝑥 ] [ ] [ ⊗ 2 = 5 8] ⊗ [ ] 8 ⊗ 10 3 8 2 𝑥3 1 2 2 𝑥1 6 11 5 13 𝑥 [11 16 10] ⊗ [ 2 ] = [18] 𝑥3 12 5 10 4
Penyelesaian 𝐴 ⊗ 𝒙 = 𝒃 dengan menggunakan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 didapatkan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 sebagai berikut : 7 2 𝐷𝐴,𝑏 = [7 2 7 2
8 1 1 8] dan 𝑅𝐴,𝑏 = [1 1 8 1 1
1 1] 1
terlihat bahwa setiap kolom matriks 𝑅𝐴,𝑏 terdapat setidaknya satu elemen bernilai 1, sedangkan pada setiap baris terdapat nilai 1 lebih dari satu. Hal tersebut menandakan bahwa 𝐴 ⊗ 𝒙 = 𝒃 mempunyai banyak penyelesaian 𝒙. Elemenelemen minimum dari setiap kolom matriks 𝐷𝐴,𝑏 yaitu 7 𝒙 = [2 ] 8 Hal ini bisa di cek sebagai berikut : 6 11 5 7 13𝑣 [11 16 10] ⊗ [2] = [18𝑣 ]. 8 5 10 4 12𝑣 dari hal tersebut dapat dijelaskan bahwa :
66
Pada setiap baris nilai maksimum dicapai lebih dari satu kali. Sehingga persamaan pada semua baris akan tercapai dengan menetapkan 𝑥1 = 7 , 𝑥2 < 2 , 𝑥3 < 8 atau 𝑥1 < 7 , 𝑥2 = 2 , 𝑥3 < 8 atau 𝑥1 < 7 , 𝑥2 < 2 , 𝑥3 = 8. Dengan demikian persamaan 𝐴 ⊗ 𝒙 = 𝒃 memiliki penyelesaian tak hingga banyak yaitu 7 𝑘 [ 𝒙 = 2 ] untuk setiap 𝑘2 < 2 dan 𝑘3 < 8 𝑘3 𝑘1 [ 𝒙 = 2 ] untuk setiap 𝑘1 < 7 dan 𝑘3 < 8 𝑘3 𝑘1 𝒙 = [𝑘2 ] untuk setiap 𝑘1 < 7 dan 𝑘2 < 2 8 Selanjutnya,
persamaan
𝐴⊗𝒙=𝒃
akan
diselesaikan
dengan
menggunakan aturan Cramer dalam aljabar supertropical sebagai berikut. 𝐷 = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) ⟺ 𝐷 = (6 ⊗ 16 ⊗ 4) ⊕ (6 ⊗ 10 ⊗ 10) ⊕ (11 ⊗ 11 ⊗ 4) ⊕ (11 ⊗ 10 ⊗ 5) ⊕ (5 ⊗ 11 ⊗ 10) ⊕ (5 ⊗ 16 ⊗ 5) ⟺ 𝐷 = 26 ⊕ 26 ⊕ 26 ⊕ 26 ⊕ 26 ⊕ 26 = 26𝑣 ∈ 𝒢0 . 13 11 5 𝐷1 = [18 16 10] 12 10 4 ⟺ 𝐷1 = (13 ⊗ 16 ⊗ 4) ⊕ (13 ⊗ 10 ⊗ 10) ⊕ (11 ⊗ 18 ⊗ 4) ⊕ (11 ⊗ 10 ⊗ 12) ⊕ (5 ⊗ 18 ⊗ 10) ⊕ (5 ⊗ 16 ⊗ 12) ⟺ 𝐷1 = 33 ⊕ 33 ⊕ 33 ⊕ 33 ⊕ 33 ⊕ 33 = 33𝑣 ∈ 𝒢0 . 6 13 5 𝐷2 = [11 18 10] 5 12 4 ⟺ 𝐷2 = (6 ⊗ 18 ⊗ 4) ⊕ (6 ⊗ 10 ⊗ 12) ⊕ (13 ⊗ 11 ⊗ 4) ⊕ (13 ⊗ 10 ⊗ 5) ⊕ (5 ⊗ 11 ⊗ 12) ⊕ (5 ⊗ 18 ⊗ 5) ⟺ 𝐷2 = 28 ⊕ 28 ⊕ 28 ⊕ 28 ⊕ 28 ⊕ 28 = 28𝑣 ∈ 𝒢0 . 6 𝐷3 = [11 5
11 13 16 18] 10 12
67
⟺ 𝐷3 = (6 ⊗ 16 ⊗ 12) ⊕ (6 ⊗ 18 ⊗ 10) ⊕ (11 ⊗ 11 ⊗ 12) ⊕ (11 ⊗ 18 ⊗ 5) ⊕ (13 ⊗ 11 ⊗ 10) ⊕ (13 ⊗ 11 ⊗ 10) ⟺ 𝐷3 = 34 ⊕ 34 ⊕ 34 ⊕ 34 ⊕ 34 ⊕ 34 = 34𝑣 ∈ 𝒢0 . sehingga diperoleh 𝐷1 33𝑣 adj(A) ⊗ 𝒃 = [𝐷2 ] = [28𝑣 ] ∉ 𝒯0 𝑛 𝐷3 34𝑣 penyelesaian dari persamaan tersebut adalah 𝐷1 33𝑣 = 𝑣 = −26𝑣 ⊗ 33𝑣 = 7𝑣 𝐷 26 𝐷2 28𝑣 𝑥2 = = 𝑣 = −26𝑣 ⊗ 28𝑣 = 2𝑣 𝐷 26 𝐷1 34𝑣 = 𝑣 = −26𝑣 ⊗ 34𝑣 = 8𝑣 𝑥3 = 26 𝐷 hal ini bisa di cek sebagai berikut 𝑥1 =
6 [11 5
11 5 7 13𝑣 16 10] ⊗ [2] = [18𝑣 ] 8 10 4 12𝑣
penyelesaian tangible lain dengan 𝑘 ∈ 𝒯 adalah 7 𝒙 = [𝑘2 ] untuk setiap 𝑘2 < 2 dan 𝑘3 < 8 𝑘3 𝑘1 𝒙 = [ 2 ] untuk setiap 𝑘1 < 7 dan 𝑘3 < 8 𝑘3 𝑘1 𝒙 = [𝑘2 ] untuk setiap 𝑘1 < 7 dan 𝑘2 < 2 8 karena 𝐷 ∈ 𝒢0 dan 𝐷𝑥𝑖 ∈ 𝒢0 untuk setiap 𝑖, maka persamaan 𝐴 ⊗ 𝒙 = 𝒃 ◊
mempunyai penyelesaian tidak tunggal.
Contoh 4.8. (Banyak persamaan lebih dari banyak peubah) 1 [ Selesaikan 𝐴 ⊗ 𝒙 = 𝒃, jika 𝐴 = 3 9
2 3 𝑥1 ] [ ] [ 4 , 𝑥 = 𝑥 , 𝑏 = 6] 2 2 7
𝐴𝑇 ⊗ 𝐴 ⊗ 𝒙 = 𝐴𝑇 ⊗ 𝒃
68
1 [ 2
3 1 2 𝑥1 1 3 9 3 9 ] ⊗ [6 ] ] ⊗ [3 4 ] ⊗ [ 𝑥 ] = [ 2 2 4 2 4 2 7 9 2 𝑥 18 11 1 16 [ ] ⊗ [𝑥 ] = [ ] 11 8 2 9
Penyelesaian 𝐴 ⊗ 𝒙 = 𝒃 dengan menggunakan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 didapatkan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 sebagai berikut : 1 5] dan 𝑅𝐴,𝑏 = [ 1 1
−2 𝐷𝐴,𝑏 = [ −2
0 ] 1
terlihat bahwa setiap kolom matriks 𝑅𝐴,𝑏 terdapat setidaknya satu elemen bernilai 1. Sedangkan setiap baris ke-2 matriks 𝑅𝐴,𝑏 terdapat nilai 1 lebih dari satu. Hal tersebut menandakan bahwa 𝐴 ⊗ 𝒙 = 𝒃 mempunyai banyak penyelesaian 𝒙. Elemen-elemen minimum dari setiap kolom matriks 𝐷𝐴,𝑏 yaitu −2 𝒙=[ ] 1 hal ini bisa di cek sebagai berikut : 18 [ 11
𝑚𝑎𝑥 (16, 12) 16 11 −2 ]⊗[ ] = [ ] = [ 𝑣 ] ⊨ 𝒃. 𝑚𝑎𝑥(9, 9) 9 8 1
Dari hal tersebut dapat dijelaskan bahwa :
Pada baris pertama nilai maksimum dicapai hanya satu kali, dengan demikian persamaan baris pertama menetapkan elemen 𝑥1 = −2.
Pada baris kedua nilai maksimum dicapai lebih dari satu kali yaitu pada saat elemen 𝑥1 = −2 dan 𝑥2 = 1.
Elemen-elemen yang sudah dipilih yaitu 𝑥1 = −2 tidak bisa diubah, bila diubah yang lain maka baris pertama akan membentuk pertaksamaan. Karena persamaan baris pertama telah menetapkan 𝑥1 = −2, maka dengan menetapkan 𝑥2 < 1 pada baris pertama tetap membentuk persamaan dan tidak akan mengubah persamaan pada baris lain. Sehingga persamaan pada semua baris akan tercapai dengan menetapkan elemen 𝑥1 = −2, 𝑥2 < 1 . Dengan demikian 𝐴 ⊗ 𝒙 = 𝒃 memiliki penyelesaian tak hingga banyak yaitu 𝒙=[
−2 ] untuk setiap 𝑘2 < 1 𝑘2
69
Selanjutnya,
persamaan
𝐴⊗𝒙=𝒃
akan
diselesaikan
dengan
menggunakan aturan Cramer dalam aljabar supertropical sebagai berikut. 𝐷 = (𝑎11 ⊗ 𝑎22 ) ⊕ (𝑎12 ⊗ 𝑎21 ) ⟺ 𝐷 = (18 ⊗ 8) ⊕ (11 ⊗ 11) ⟺ 𝐷 = 26 ⊕ 22 = 26 ∈ 𝒯. 16 11 ] 9 8 ⟺ 𝐷1 = (16 ⊗ 8) ⊕ (11 ⊗ 9) 𝐷1 = [
⟺ 𝐷1 = 24 ⊕ 20 = 24 ∈ 𝒯. 18 16 ] 11 9 ⟺ 𝐷2 = (18 ⊗ 9) ⊕ (16 ⊗ 11)
𝐷2 = [
⟺ 𝐷2 = 27 ⊕ 27 = 27𝑣 ∈ 𝒢0 . sehingga diperoleh [
𝐷1 24 ] = [ 𝑣 ] ∉ 𝒯0 𝑛 𝐷2 27
penyelesaian dari persamaan tersebut adalah 𝐷1 24 = = −26 ⊗ 24 = −2 𝐷 26 𝐷2 27𝑣 𝑥2 = = = −26 ⊗ 27𝑣 = 1𝑣 𝐷 26 𝑥1 =
hal ini dapat dicek sebagai berikut 18 [ 11
𝑚𝑎𝑥 (16, 12) 16 11 −2 ]⊗[ ] = [ ] = [ 𝑣] 𝑚𝑎𝑥(9, 9) 8 1 9
penyelesaian tangible lain dengan 𝑘 ∈ 𝒯 adalah 𝒙=[
−2 ] untuk setiap 𝑘2 < 1 𝑘2
karena 𝐷 ∈ 𝒯 dan 𝐷𝑥𝑖 ∈ 𝒢0 untuk beberapa 𝑖, maka persamaan 𝐴 ⊗ 𝒙 = 𝒃 ◊
mempunyai penyelesaian tidak tunggal.
70
4.2 Karakterisasi
Penyelesaian
Sistem
Persamaan
Linear
Homogen atas Aljabar Supertropical Pada bagian ini akan dibahas mengenai sistem persamaan linear homogen. Sebagai motivasi dari pembahasan sistem persamaan linear homogen, akan diberikan sistem persamaan homogen di ℝmax sebagai berikut. Selesaikan 𝐴 ⊗ 𝒙 = 𝜺 di ℝmax , jika 𝑥1 0 5 −∞ 𝐴=[ 2 7 8 ] , 𝑥 = [𝑥 2 ] 𝑥3 −∞ −∞ 0 dalam bentuk perkalian matriks dapat ditulis sebagai : 𝑥1 −∞ 0 5 −∞ 𝑥 [ 2 7 8 ] ⊗ [ 2 ] = [−∞] 𝑥3 −∞ −∞ −∞ 0 sistem diatas ekuivalen dengan (0 ⊗ 𝑥1 ) ⊕ (5 ⊗ 𝑥2 ) ⊕ (−∞ ⊗ 𝑥3 ) = −∞ (2 ⊗ 𝑥1 ) ⊕ (7 ⊗ 𝑥2 ) ⊕ (8 ⊗ 𝑥3 ) = −∞ (−∞ ⊗ 𝑥1 ) ⊕ (−∞ ⊗ 𝑥2 ) ⊕ (0 ⊗ 𝑥3 ) = −∞ sistem persamaan 𝐴 ⊗ 𝒙 = 𝜺 diatas tidak mempunyai penyelesaian tak trivial, 𝑥1 sebab bila punya penyelesaian tak trivial berarti ada 𝒙 = [𝑥2 ] tidak semuanya sama 𝑥3 dengan 𝜀 sehingga 0 [ 2 −∞
5 7 −∞
𝑥1 −∞ −∞ 𝑥 8 ] ⊗ [ 2 ] = [−∞] 𝑥3 −∞ 0
didapat (−∞ ⊗ 𝑥1 ) ⊕ (−∞ ⊗ 𝑥2 ) ⊕ (0 ⊗ 𝑥3 ) = −∞ ⇔ 𝑥3 = −∞ (0 ⊗ 𝑥1 ) ⊕ (5 ⊗ 𝑥2 ) ⊕ (−∞ ⊗ 𝑥3 ) = −∞ ⇔ 𝑥1 ⊕ (5 ⊗ 𝑥2 ) = −∞ terlihat bahwa tidak akan ada 𝑥1 , 𝑥2 ∈ ℝ𝑚𝑎𝑥 sehingga 𝑥1 ⊕ (5 ⊗ 𝑥2 ) = −∞, maka satu-satunya penyelesaian dari sistem tersebut adalah 𝑥1 −∞ [𝑥2 ] = [−∞] 𝑥3 −∞ jadi persamaan 𝐴 ⊗ 𝒙 = 𝜺 hanya mempunyai penyelesaian trivial dan tidak mempunyai penyelesaian tak trivial.
71
Pada
pembahasan
sebelumnya
telah
dijelaskan
bahwa
dapat
dikonstruksikan suatu semiring khusus yang merupakan perluasan dari ℝmax . Sedemikian hingga penyelesaian sistem persamaan linear dapat digeneralisasikan dengan menggunakan relasi ghost surpass di 𝑅. Sejalan dengan pembahasan pada bagian sebelumnya, maka dengan menggunakan relasi ghost surpass penyelesaian sistem persamaan 𝐴 ⊗ 𝒙 = 𝜺 akan diperlemah menjadi 𝐴 ⊗ 𝒙 ⊨ 𝜺. Berikut diberikan penjelasan mengenai relasi ghost surpass dalam aljabar supertropical pada persamaan homogen. Definisi 4.7. [5]. Diberikan 𝑎 ∈ 𝑅, maka 𝑎 ⊨ 𝜀 ⟺ 𝑎 = 𝜀 ⊕ 𝑐 untuk beberapa 𝑐 ∈ 𝒢0 □ Definisi 4.8. [5]. Diberikan 𝑎 ∈ 𝑅, maka 𝑎 ⊨ 𝜀 ⟺ 𝑎 ∈ 𝒢0
□
Selanjutnya, akan dijelaskan mengenai himpunan penyelesaian dari suatu persamaan homogen dengan menggunakan relasi ghost surpass pada 𝑅. 𝑥⊨𝜀 himpunan penyelesaian dari 𝑥 adalah {𝜀 } ∪ {𝑏𝑣 |𝑏 ∈ 𝒯 } □ Lemma 4.4. [8]. Jika 𝑎 ∈ 𝒯 dan 𝑥 ∈ 𝒯0 maka persamaan 𝑎 ⊗ 𝑥 ∈ 𝒢0 hanya mempunyai penyelesaian trivial 𝑥 = 𝜀. Bukti : Berdasarkan Definisi 4.8 diketahui bahwa : 𝑎 ⊨ 𝜀 ⟺ 𝑎 ∈ 𝒢0 diperoleh 𝑎 ⊗ 𝑥 ⊨ 𝜀 ⟺ 𝑎 ⊗ 𝑥 ∈ 𝒢0 jika 𝑎 ∈ 𝒯 maka untuk setiap 𝑥 ∈ 𝒯0 hanya terdapat penyelesaian trivial 𝑥 = 𝜀 sehingga memenuhi 𝑎 ⊗ 𝑥 ∈ 𝒢0 .
∎
Selanjutnya, relasi ghost surpass dari persamaan linear homogen atas aljabar supertropical akan diperluas untuk kasus vektor.
72
Definisi 4.9. Diberikan 𝒖 ∈ 𝑅𝑛 , maka 𝒖 ⊨ 𝜺 ⟺ 𝒖 ∈ 𝒢0 (𝑛) ekuivalen dengan 𝑢𝑖 ⊨ 𝜺 ⟺ 𝑢𝑖 ∈ 𝒢0 untuk setiap 𝑖 ∈ 𝑛 □ Definisi 4.10. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅), 𝒙 ∈ 𝑅𝑛 , maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 ⟺ 𝐴 ⊗ 𝒙 ∈ 𝒢0 (𝑛) □ Berikut ini diberikan beberapa definisi terkait penyelesaian 𝐴 ⊗ 𝒙 ∈ 𝒢0 (𝑛). Definisi 4.11. [19]. Suatu himpunan vektor 𝑉 = {𝒗𝟏 , 𝒗𝟐 , . . , 𝒗𝒏 } ⊂ 𝑅(𝑛) dikatakan bebas supertropical, jika 𝑛
⨁ 𝛼𝑖 ⊗ 𝒗𝒊 ∈ 𝒢0 (𝑛) 𝑖=1
mengakibatkan 𝛼𝑖 = 𝜀 ≝ −∞ untuk setiap 𝑖 ∈ 𝑛.
□
Definisi 4.12. [19]. Suatu himpunan vektor 𝑉 = {𝒗𝟏 , 𝒗𝟐 , . . , 𝒗𝒏 } ⊂ 𝑅(𝑛) dikatakan bergantung supertropical, jika terdapat skalar 𝛼1 , … , 𝛼𝑛 ∈ 𝒯0 dimana tidak semua 𝛼𝑖 = 𝜀 sehingga 𝑛
⨁ 𝛼𝑖 ⊗ 𝑣𝑖 ∈ 𝒢0 (𝑛) 𝑖=1
□
dengan 𝒯0 ≝ 𝒯 ∪ {−∞} dan 𝑖 ∈ 𝑛.
Contoh-contoh berikut menjelaskan hal-hal yang berkaitan dengan Definisi 4.11 dan 4.12.
Contoh 4.9. −∞ 0 10 Diberikan 𝑉 = {𝒗𝟏 , 𝒗𝟐 , 𝒗𝟑 } di 𝑅 , dengan 𝒗𝟏 = [−∞], 𝒗𝟐 = [ 4 ], 𝒗𝟑 = [ 3 ] 0 −∞ −∞ 3
vektor 𝒗𝟏 , 𝒗𝟐 dan 𝒗𝟑 adalah bebas supertropical. Untuk membuktikan hal tersebut maka harus ditunjukkan bahwa satu-satunya cara agar
73
−∞ 0 10 𝛼1 ⊗ [−∞] ⊕ 𝛼2 ⊗ [ 4 ] ⊕ 𝛼3 ⊗ [ 3 ] ∈ 𝒢0 (3) 0 −∞ −∞ yaitu jika semua skalar 𝛼1 , 𝛼2 , 𝛼3 adalah −∞. Persamaan di atas dapat ditulis sebagai suatu sistem linear dengan peubah-peubah 𝛼1 , 𝛼2 , 𝛼3 sebagai berikut : (0 ⊗ 𝛼1 ) ⊕ (10 ⊗ 𝛼2 ) ⊕ (−∞ ⊗ 𝛼3 ) ∈ 𝒢0 (−∞ ⊗ 𝛼1 ) ⊕ (4 ⊗ 𝛼2 ) ⊕ (3 ⊗ 𝛼3 ) ∈ 𝒢0 (−∞ ⊗ 𝛼1 ) ⊕ (−∞ ⊗ 𝛼2 ) ⊕ (0 ⊗ 𝛼3 ) ∈ 𝒢0 dalam bentuk perkalian matriks dituliskan sebagai 𝛼1 0 10 −∞ (3) [−∞ 4 3 ] ⊗ [𝛼2 ] ∈ 𝒢0 𝛼3 −∞ −∞ 0 Pada baris ketiga didapat (−∞ ⊗ 𝛼1 ) ⊕ (−∞ ⊗ 𝛼2 ) ⊕ (0 ⊗ 𝛼3 ) ∈ 𝒢0 ⟺ 𝛼3 ∈ 𝒢0 ⟺ 𝛼3 = −∞. Pada baris kedua didapat (−∞ ⊗ 𝛼1 ) ⊕ (4 ⊗ 𝛼2 ) ⊕ (3 ⊗ −∞) ∈ 𝒢0 ⟺ (𝛼2 ⊗ 4) ∈ 𝒢0 ⟺ 𝛼2 = −∞. Pada baris pertama didapat (0 ⊗ 𝛼1 ) ⊕ (10 ⊗ −∞) ⊕ (−∞ ⊗ 𝛼3 ) ⟺ 𝛼1 = −∞. dengan demikian satu-satunya penyelesaian dari sistem ini adalah 𝛼1 = −∞ , 𝛼2 = −∞ dan 𝛼3 = −∞. Dari contoh tersebut terlihat bahwa matriks koefisien dari sistem ini adalah non singular. Hal ini dapat ditunjukkan sebagai berikut : 0 𝑉 = [−∞ −∞
10 4 −∞
−∞ 3 ] 0
akan dicari determinan dari 𝑉 |𝑉 | = (𝑣11 ⊗ 𝑣22 ⊗ 𝑣33 ) ⊕ (𝑣11 ⊗ 𝑣23 ⊗ 𝑣32 ) ⊕ (𝑣12 ⊗ 𝑣21 ⊗ 𝑣33 ) ⊕ (𝑣12 ⊗ 𝑣23 ⊗ 𝑣31 ) ⊕ (𝑣13 ⊗ 𝑣21 ⊗ 𝑣32 ) ⊕ (𝑣13 ⊗ 𝑣22 ⊗ 𝑣31 ) |𝑉 | = (0 ⊗ 4 ⊗ 0) ⊕ (0 ⊗ 3 ⊗ −∞) ⊕ (10 ⊗ −∞ ⊗ 0) ⊕ (10 ⊗ 3 ⊗ −∞) ⊕ (−∞ ⊗ −∞ ⊗ −∞) ⊕ (−∞ ⊗ 4 ⊗ −∞) |𝑉 | = 4 ⊕ −∞ ⊕ −∞ ⊕ −∞ ⊕ −∞ ⊕ −∞ = 4 ∈ 𝒯 karena |𝑉 | = 4 ∈ 𝒯, maka 𝑉 matriks non singular.
74
◊
Contoh 4.10. −∞ 2 0 Diberikan 𝑉 = {𝒗𝟏 , 𝒗𝟐 , 𝒗𝟑 } di 𝑅3 , dengan 𝒗𝟏 = [−∞] , 𝒗𝟐 = [ 4 ], 𝒗𝟑 = [ 2 ] 0 −∞ 0 vektor 𝒗𝟏 , 𝒗𝟐 dan 𝒗𝟑 adalah bergantung supertropical. Untuk membuktikan hal tersebut maka harus ditunjukkan bahwa terdapat skalar 𝛼1 , 𝛼2 , 𝛼3 ∈ 𝒯0 dimana tidak semua 𝛼𝑖 = 𝜀 dengan 𝑖 = 1,2,3 sehingga −∞ 2 0 𝛼1 ⊗ [−∞] ⊕ 𝛼2 ⊗ [ 4 ] ⊕ 𝛼3 ⊗ [ 2 ] ∈ 𝒢0 (3) 0 −∞ 0 persamaan di atas dapat ditulis sebagai suatu sistem linear dengan peubah-peubah 𝛼1 , 𝛼2 , 𝛼3 sebagai berikut : (0 ⊗ 𝛼1 ) ⊕ (2 ⊗ 𝛼2 ) ⊕ (−∞ ⊗ 𝛼3 ) ∈ 𝒢0 (−∞ ⊗ 𝛼1 ) ⊕ (4 ⊗ 𝛼2 ) ⊕ (2 ⊗ 𝛼3 ) ∈ 𝒢0 (0 ⊗ 𝛼1 ) ⊕ (−∞ ⊗ 𝛼2 ) ⊕ (0 ⊗ 𝛼3 ) ∈ 𝒢0 dalam bentuk perkalian matriks dituliskan sebagai 𝛼1 0 2 −∞ (3) [−∞ 4 2 ] ⊗ [𝛼2 ] ∈ 𝒢0 𝛼3 0 −∞ 0 pada baris ketiga didapat (0 ⊗ 𝛼1 ) ⊕ (−∞ ⊗ 𝛼2 ) ⊕ (0 ⊗ 𝛼3 ) ⟺ 𝛼1 ⊕ 𝛼3 ∈ 𝒢0 ⟺ 𝛼1 = 𝛼3 . terlihat bahwa dapat ditemukan skalar 𝛼1 = 𝛼3 , sehingga untuk setiap skalar 𝛼1 , 𝛼3 ∈ 𝒯0 dimana 𝛼1 = 𝛼3 akan memenuhi persamaan tersebut, dengan demikian sistem ini mempunyai penyelesaian tak trivial. Dari contoh tersebut terlihat bahwa matriks koefisien dari sistem ini adalah singular. Hal ini dapat ditunjukkan sebagai berikut : 0 𝑉 = [−∞ 0
2 4 −∞
−∞ 2 ] 0
akan dicari determinan dari 𝑉 |𝑉 | = (𝑣11 ⊗ 𝑣22 ⊗ 𝑣33 ) ⊕ (𝑣11 ⊗ 𝑣23 ⊗ 𝑣32 ) ⊕ (𝑣12 ⊗ 𝑣21 ⊗ 𝑣33 ) ⊕ (𝑣12 ⊗ 𝑣23 ⊗ 𝑣31 ) ⊕ (𝑣13 ⊗ 𝑣21 ⊗ 𝑣32 ) ⊕ (𝑣13 ⊗ 𝑣22 ⊗ 𝑣31 ) |𝑉 | = (0 ⊗ 4 ⊗ 0) ⊕ (0 ⊗ 2 ⊗ −∞) ⊕ (2 ⊗ −∞ ⊗ 0) ⊕ (2 ⊗ 2 ⊗ 0) ⊕ (−∞ ⊗ 2 ⊗ 0) ⊕ (−∞ ⊗ 4 ⊗ 0) |𝑉 | = 4 ⊕ −∞ ⊕ −∞ ⊕ 4 ⊕ −∞ ⊕ −∞ = 4𝑣 ∈ 𝒢0
75
karena |𝑉 | = 4𝑣 ∈ 𝒢0 , maka 𝑉 matriks singular.
◊
Berikut diberikan penjelasan mengenai beberapa hal yang telah dibahas. Vektor-vektor 𝒂𝒊 dengan 𝑖 = 1,2, … , 𝑛 dalam ruang vektor 𝑉 bebas supertropical, ekuivalen dengan 𝑥1 ⊗ 𝒂𝟏 ⊕ 𝑥2 ⊗ 𝒂𝟐 ⊕ … ⊕ 𝑥𝑛 ⊗ 𝒂𝒏 ∈ 𝒢0 (𝑛) dipenuhi hanya untuk 𝑥1 = 𝑥2 = ⋯ = 𝑥𝑛 = 𝜀 ≝ −∞. Bila 𝑉 = 𝑅𝑛 maka vektor-vektor 𝒂𝒊 dengan 𝑖 = 1,2, … , 𝑛 dalam ruang vektor 𝑉 atas 𝑅 bebas supertropical memiliki arti bahwa sistem persamaan linear homogen 𝑥1 ⊗ 𝒂𝟏 ⊕ 𝑥2 ⊗ 𝒂𝟐 ⊕ … ⊕ 𝑥𝑛 ⊗ 𝒂𝒏 ∈ 𝒢0 (𝑛) mempunyai penyelesaian trivial yaitu 𝑥𝑖 = 𝜀 ≝ −∞ dengan 𝑖 = 1,2, … , 𝑛. Bila persamaan homogen ini mempunyai penyelesaian tak trivial, yaitu 𝒙𝒊 ≠ 𝜺 untuk beberapa 𝑖 dengan 𝒙𝒊 ∈ 𝒯0 . Hal ini berarti bahwa vektor-vektor 𝒂𝒊 tersebut tidak bebas supertropical atau bergantung supertropical. Berikut diberikan Teorema mengenai eksistensi dan ketunggalan dari penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝜺 atas aljabar supertropical. Teorema 4.5. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅) maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 mempunyai penyelesaian tak trivial jika dan hanya jika |𝐴| ∈ 𝒢0 ≠ 𝜀.
∎
Teorema 4.6. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅) maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 mempunyai penyelesaian trivial jika dan hanya jika |𝐴| ∈ 𝒯.
∎
Selanjutnya, diberikan penjelasan terkait penyelesaian tak trivial dari persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 dalam aljabar supertropical. Proposisi 4.2. [8]. Diberikan 𝐴 ∈ 𝑀𝑛 (𝑅) dimana |𝐴| ∈ 𝒢0 ≠ 𝜀 dan 𝒙 ∈ 𝒯0 𝑛 maka sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 mempunyai penyelesaian 𝑘 ⊗ 𝒙 ∈ 𝑅𝑛 dengan 𝒙 adalah kolom ke-𝑖 dari adj(𝐴) untuk beberapa 𝑖 ∈ 𝑛 dan 𝑘 ∈ 𝒯.
76
∎
4.4.1 Penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝜺 dimana |𝑨| ∈ 𝓣 dalam Aljabar Supertropical Contoh 4.13. 𝑥1 −1 𝑥 6 ] , 𝑥 = [ 2] 𝑥3 3
1 4 Selesaikan 𝐴 ⊗ 𝒙 ⊨ 𝜺, jika 𝐴 = [1 0 3 1
sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 ⟺ 𝐴 ⊗ 𝒙 ∈ 𝒢0 (3) 𝑥1 1 4 −1 𝑥 [1 0 6 ] ⊗ [ 2 ] ∈ 𝒢0 (3) 𝑥3 3 1 3 ekuivalen dengan (1 ⊗ 𝑥1 ) ⊕ (4 ⊗ 𝑥2 ) ⊕ (−1 ⊗ 𝑥3 ) ∈ 𝒢0 (1 ⊗ 𝑥1 ) ⊕ (0 ⊗ 𝑥2 ) ⊕ (6 ⊗ 𝑥3 ) ∈ 𝒢0 (3 ⊗ 𝑥1 ) ⊕ (1 ⊗ 𝑥2 ) ⊕ (3 ⊗ 𝑥3 ) ∈ 𝒢0 determinan dari 𝐴 |𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) |𝐴 | = ( 1 ⊗ 0 ⊗ 3 ) ⊕ (1 ⊗ 6 ⊗ 1 ) ⊕ (4 ⊗ 1 ⊗ 3 ) ⊕ (4 ⊗ 6 ⊗ 3 ) ⊕ (−1 ⊗ 1 ⊗ 1) ⊕ (−1 ⊗ 0 ⊗ 3) |𝐴| = 4 ⊕ 8 ⊕ 8 ⊕ 13 ⊕ 1 ⊕ 2 = 13 ∈ 𝒯. |𝐴| = 13 ∈ 𝒯, maka penyelesaian dari 𝐴 ⊗ 𝒙 ∈ 𝒢0 (3) adalah 𝑥1 𝜀 [𝑥2 ] = [𝜀 ] 𝑥3 𝜀 hal ini bisa di cek sebagai berikut : 1 4 [1 0 3 1
𝜀 𝜀 −1 𝜀 6 ] ⊗ [ ] = [𝜀 ] ∈ 𝒢0 (3) 𝜀 𝜀 3
karena |𝐴| ∈ 𝒯 maka persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 dalam aljabar supertropical 𝑅 mempunyai penyelesaian trivial. Dengan demikian penyelesaian tersebut merupakan penyelesaian trivial di ℝmax .
77
◊
4.4.2 Penyelesaian 𝐴 ⊗ 𝒙 ⊨ 𝜺 dimana |𝑨| ∈ 𝓖𝟎 ≠ 𝜺 dalam Aljabar Supertropical Contoh 4.14. 1 2 Selesaikan 𝐴 ⊗ 𝒙 ⊨ 𝜺, jika 𝐴 = [4 1 2 2
𝑥1 3 5 ] , 𝑥 = [𝑥 2 ] 𝑥3 2
sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 ⟺ 𝐴 ⊗ 𝒙 ∈ 𝒢0 (3) 𝑥1 1 2 3 𝑥 [4 1 5] ⊗ [ 2 ] ∈ 𝒢0 (3) 𝑥3 2 2 2 ekuivalen dengan (1 ⊗ 𝑥1 ) ⊕ (2 ⊗ 𝑥2 ) ⊕ (3 ⊗ 𝑥3 ) ∈ 𝒢0 (4 ⊗ 𝑥1 ) ⊕ (1 ⊗ 𝑥2 ) ⊕ (5 ⊗ 𝑥3 ) ∈ 𝒢0 (2 ⊗ 𝑥1 ) ⊕ (2 ⊗ 𝑥2 ) ⊕ (2 ⊗ 𝑥3 ) ∈ 𝒢0 determinan dari 𝐴 |𝐴| = (𝑎11 ⊗ 𝑎22 ⊗ 𝑎33 ) ⊕ (𝑎11 ⊗ 𝑎23 ⊗ 𝑎32 ) ⊕ (𝑎12 ⊗ 𝑎21 ⊗ 𝑎33 ) ⊕ (𝑎12 ⊗ 𝑎23 ⊗ 𝑎31 ) ⊕ (𝑎13 ⊗ 𝑎21 ⊗ 𝑎32 ) ⊕ (𝑎13 ⊗ 𝑎22 ⊗ 𝑎31 ) |𝐴 | = ( 1 ⊗ 1 ⊗ 2 ) ⊕ (1 ⊗ 5 ⊗ 2 ) ⊕ (2 ⊗ 4 ⊗ 2 ) ⊕ (2 ⊗ 5 ⊗ 2 ) ⊕ (3 ⊗ 4 ⊗ 2) ⊕ (3 ⊗ 1 ⊗ 2) |𝐴| = 4 ⊕ 8 ⊕ 8 ⊕ 9 ⊕ 9 ⊕ 6 = 9𝑣 ∈ 𝒢0 . |𝐴| = 9𝑣 ∈ 𝒢0 , maka penyelesaian dari 𝐴 ⊗ 𝒙 ∈ 𝒢0 (3) adalah 7 adj(A) = [7 6
5 7 5 7] 4 6
penyelesaian 𝒙 merupakan kolom ke-𝑖 dari adj(𝐴) yaitu kolom ke-1, 2 dan 3. jika 𝒙 adalah kolom ke-1 dan kolom ke-3 dari Adj (𝐴), maka 7 𝒙 = [7 ] 6 hal ini bisa di cek sebagai berikut : 1 𝐴 ⊗ 𝒙 = [4 2
2 1 2
3 7 9𝑣 (3) 5] ⊗ [7] = [11𝑣 ] ∈ 𝒢0 2 6 9𝑣
78
jika 𝒙 adalah kolom ke-2 dari Adj (𝐴), maka 5 𝒙 = [5 ] 4 hal ini bisa di cek sebagai berikut : 1 𝐴 ⊗ 𝒙 = [4 2
2 3 7𝑣 5 (3) 1 5] ⊗ [5] = [9𝑣 ] ∈ 𝒢0 2 2 7𝑣 4
penyelesaian lain dari 𝐴 ⊗ 𝒙 ∈ 𝒢0 (3) adalah 𝑝1 𝒙 = 𝑘 ⊗ [𝑝2 ] 𝑝3 untuk setiap 𝑘 ∈ 𝒯 dengan 𝑝1 = 7, 𝑝2 = 7, 𝑝3 = 6 atau 𝑝1 = 5, 𝑝2 = 5, 𝑝3 = 4. ◊
79
BAB V SIMPULAN DAN SARAN
Berdasarkan hasil penelitian dan pembahasan yang telah diberikan, dapat dibuat simpulan serta saran untuk pengembangan dan perbaikan penelitian selanjutnya. 5.1
Simpulan Simpulan yang dapat diambil dari hasil penelitian dan pembahasan yang
telah diberikan adalah sebagai berikut : 1.
Penyelesaian sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 atas aljabar supertropical dengan 𝐴 ∈ 𝑀𝑛 (𝑅), 𝒃 ∈ 𝒯0 𝑛 dan 𝒙 ∈ 𝑅𝑛 terbagi menjadi penyelesaian tangible, ghost, dan nol.
2.
Sistem persamaan tak homogen 𝐴 ⊗ 𝒙 ⊨ 𝒃 atas aljabar supertropical dengan 𝐴 ∈ 𝑀𝑛 (𝑅), 𝒃 ∈ 𝒯0 𝑛 dan 𝒙 ∈ 𝑅𝑛 mempunyai penyelesaian tangible yang tunggal jika dan hanya jika |𝐴| ∈ 𝒯 dan (adj(A) ⊗ 𝒃) ∈ 𝒯0 𝑛 . Serta mempunyai penyelesaian tangible yang tidak tunggal jika dan hanya jika |𝐴| ∈ 𝒢0 ≠ 𝜀 atau (adj(A) ⊗ 𝒃) ∉ 𝒯0 𝑛 .
3.
Sistem persamaan homogen 𝐴 ⊗ 𝒙 ⊨ 𝜺 atas aljabar supertropical dengan 𝐴 ∈ 𝑀𝑛 (𝑅), dan 𝒙 ∈ 𝑅𝑛 mempunyai penyelesaian trivial jika dan hanya jika |𝐴| ∈ 𝒯. Serta mempunyai penyelesaian tak trivial jika dan hanya jika |𝐴| ∈ 𝒢0 ≠ 𝜀.
5.2
Saran Saran untuk penelitian selanjutnya adalah a.
Metode yang digunakan untuk menentukan penyelesaian sistem persamaan linear 𝐴 ⊗ 𝒙 ⊨ 𝒃 atas aljabar supertropical bisa digunakan metode lain selain aturan Cramer dan matriks 𝐴 tidak persegi.
b.
Untuk sistem persamaan 𝐴 ⊗ 𝒙 ⊨ 𝒃 dengan 𝐴 ∈ 𝑀𝑛 (𝑅) dapat dibuat program untuk menghitung nilai determinan pada aturan Cramer, sehingga dapat mempermudah penyelesaiannya.
81
DAFTAR PUSTAKA
[1]
History of Tropical Algebra, (tanggal akses : 1 Mei 2015), (http:\\ en.m.wikipedia.org/wiki/tropical_geometry).
[2]
Litvinov, G. L., (2005), “The Maslov Dequantization, Idempotent and Tropical Mathematics : a Very Brief Introduction”, arXiv : 0507014v1.
[3]
Izhakian, Z., (2009), ”Tropical Arithmetic and Matrix Algebra”, Communications in Algebra, 37 : 4, hal. 1445-1468.
[4]
Izhakian, Z., dan Rowen, L., (2010a), ”Supertropical Algebra”, Advances in Mathematics, 225, hal. 2222-2286.
[5]
Izhakian, Z., Knebush, M., dan Rowen, L., (2010b), Supertropical Linear Algebra, Mathematisches Forschungsinstitut Oberwolfach, ISSN 1864-7596.
[6]
Izhakian, Z., dan Rowen, L., (2010c), ”Supertropical Polynomials and Resultants”, Journal of Algebra, 324, hal. 1860-1886.
[7]
Izhakian, Z., dan Rowen, L.,(2011a), “Supertropical Matrix Algebra”, Israel Journal Mathematics, 182, hal. 383-424.
[8]
Izhakian, Z., dan Rowen, L.,(2011b), “Supertropical Matrix Algebra II : Solving Tropical Equations”, Israel Journal Mathematics, 186, hal. 69-97.
[9]
Izhakian, Z., dan Rowen, L.,(2011c), “Supertropical Matrix Algebra III : Power of Matrices and Their Supertropical Eigenvalues”, Journal of Algebra, 341, hal. 25-149.
[10] Izhakian, Z., Knebush, M., dan Rowen, L., (2012), “Dual Space and Bilinear Forms in Supertropical Linear Algebra”, Journal Linear and Multilinear Algebra, 60 : 7, hal. 865-883. [11] Niv, Adi., (2012), “Factorization of Supertropical Matrices”, 1202.3615v1.
83
arXiv :
[12] Izhakian, Z., Knebush, M., dan Rowen, L., (2013), “Supertropical Monoids : Basics and Canonical Factorization”, Journal of Pure and Applied Algebra, 217, hal. 2135-2162. [13] Niv, Adi., (2014), “Characteristic Polynomials of Supertropical Matrices”, Communications in Algebra, 42, hal. 528-539. [14] Izhakian, Z., Knebush, M., dan Rowen, L., (2015a), “Supertropical Quadratic Forms I”, Journal of Pure and Applied Algebra, article in press. [15] Izhakian, Z., Knebush, M., dan Rowen, L., (2015b), “Supertropical Quadratic Forms II”, arXiv : 1506.03404v1. [16] Niv, Adi., (2015), “On Pseudo-Inverses of Matrices and Their Characteristic Polynomials in Supertropical Algebra”, Linear Algebra and Its Applications, 471, hal. 264-290. [17] Subiono, (2015), “Aljabar Min-Max Plus dan Terapannya Versi 3.0.0”, Jurusan Matematika, ITS, Surabaya. [18] Baccelli, F., Cohen, G., Olsder, G.J., dan Quadrat, J.P., (2001), “Synchronization and Linearity”, John Wiley & Sons, New York. [19] Izhakian, Z., Rhodes, J., dan Rowen, L., (2011), “Supertropical Algebra and Representation”, Join work. [20] Rudhito, Andy., (2003), “Sistem Linear Max-Plus Waktu Invariant”, Tesis : Pascasarjana Universitas Gadjah Mada, Yogyakarta. [21] Gaubert, S., (1992), “Theorie des Systemes Lineaires dans les Dioides”, Ph.D Theses, Ecole des Mines de Paris, Perancis.
84
BIODATA PENULIS
Penulis yang memiliki nama lengkap Dian Yuliati lahir di Madiun,
14
Juli
1987.
Penulis
telah
menempuh
pendidikan formal mulai dari SD Negeri 1 Sebayi, SMP Negeri 1 Saradan, dan SMA Negeri 1 Mejayan Madiun. Setelah lulus dari SMA, penulis melanjutkan studi S1 di Jurusan Pendidikan Matematika Universitas Negeri Surabaya. Penulis lulus sarjana dengan tujuh semester dengan mendapat gelar Sarjana Pendidikan. Penulis melanjutkan studi S2 di Jurusan Matematika Institut Teknologi Sepuluh Nopember Surabaya pada tahun 2014 dengan NRP. 1214 201 002. Untuk membentuk jaringan atau membutuhkan informasi yang berhubungan dengan Tesis ini, penulis dapat dihubungi melalui email :
[email protected].
85
