PERSAMAAN LINEAR ATAS ALJABAR SUPERTROPICALrepository.its.ac.id/1229/2/1214201002-Master...

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

ix

DAFTAR ISI

LEMBAR PENGESAHAN ................................................................................. i

ABSTRAK ......................................................................................................... iii

ABSTRACT ....................................................................................................... v

KATA PENGANTAR ...................................................................................... vii

DAFTAR ISI ..................................................................................................... ix

DAFTAR NOTASI............................................................................................ xi

BAB 1 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

BAB 2 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

x

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

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

BAB 5 SIMPULAN DAN SARAN .............................................................. 81

5.1 Simpulan ................................................................................ 81

5.2 Saran ...................................................................................... 81

DAFTAR PUSTAKA ....................................................................................... 83

xi

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

vii

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.

viii

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

mailto:[email protected]

iii

KARAKTERISASI PENYELESAIAN SISTEM PERSAMAAN

LINEAR ATAS ALJABAR SUPERTROPICAL

Nama Mahasiswa : Dian Yuliati

NRP : 1214 201 002

Dosen Pembimbing : 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.

v

CHARACTERIZATION OF THE SOLUTION OF SYSTEM OF

LINEAR EQUATIONS OVER SUPERTROPICAL ALGEBRA

Name : Dian Yuliati

Student Identity Number : 1214 201 002

Supervisor : 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.

1

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

2

|𝐴 ⊗ 𝐵| = |𝐴| ⊗ |𝐵| [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

3

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.

4

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


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.

5

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 definisi-

definisi 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].

6

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 :

7

𝑎 × 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

𝑎 ⊗ 𝑏 = 𝑏⊗ 𝑎

(𝑎 ⊗ 𝑏)⊗ 𝑐 = 𝑎 ⊗ (𝑏 ⊗ 𝑐)

𝑎 ⊗ 𝑒 = 𝑒 ⊗ 𝑎 = 𝑎

8

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 𝑎 ⊗ 𝑏 ≝ 𝑎 + 𝑏, ∀ 𝑎, 𝑏 ∈ ℝ𝜀

□

9

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

𝑥⊗𝑛 = 𝑥 ⊗ 𝑥⊗…⊗ 𝑥⏟ 𝑛

= 𝑛 × 𝑥

10

Contoh 2.2. Berikut ini diberikan contoh operasi ⨁ dan ⊗ dalam aljabar max-plus.

Misal diambil 𝑎 = 9, 𝑏 = 8, 𝑐 = 1

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⊗1

3 =1

3× 9 = 3. ◊

1.3.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.

Diberikan matriks 𝐴 = [1 2 58 3 84 7 2

] dan 𝐵 = [5 2 76 1 32 4 1

] dimana 𝐴,𝐵 ∈ ℝmax𝑛×𝑛

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

11

[𝐴 ⊕𝐵]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 2 78 3 84 7 2

]

◊

1.3.3 Perkalian Matriks

Untuk sebarang matriks 𝐴 ∈ ℝmax𝑚×𝑛 dan skalar 𝜆 ∈ ℝmax maka perkalian 𝜆 ⊗𝐴

didefinisikan sebagai

[𝜆 ⊗ 𝐴]𝑖,𝑗 = 𝜆⊗ 𝑎𝑖,𝑗


Untuk sebarang matriks 𝐴 ∈ ℝmax𝑚×𝑝 dan 𝐵 ∈ ℝmax

𝑝×𝑛 perkalian matriks 𝐴⊗ 𝐵

didefinisikan sebagai :

[𝐴⊗ 𝐵]𝑖,𝑗 =⨁𝑎𝑖,𝑘⊗𝑏𝑘,𝑗

𝑝

𝑘=1


Contoh 2.4.


] dan skalar 𝜆 = 5 dimana ∈ ℝmax𝑛×𝑛 , 𝜆 ∈ ℝmax

maka

𝜆 ⊗ 𝑎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

12

𝜆 ⊗ 𝑎2,3 = 5 ⊗ 3 = 8

𝜆 ⊗ 𝑎3,1 = 5 ⊗ 5 = 10

𝜆 ⊗ 𝑎3,2 = 5 ⊗ 8 = 13

𝜆 ⊗ 𝑎3,3 = 5 ⊗ 9 = 14


𝜆 ⊗𝐴 = [10 8 1213 9 810 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.


] dimana 𝐴 ∈ ℝmax𝑛×𝑛

maka

𝐴⊗2 = 𝐴⊗ 𝐴 = [1 9 57 4 25 8 9

] ⊗ [1 9 57 4 25 8 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


13

𝐴⊗2 = [16 13 1411 16 1215 17 18

]

◊

1.3.5 Transpose Matriks

Transpose dari matriks 𝐴 ∈ ℝmax𝑚×𝑛 dinotasikan dengan 𝐴𝑇, didefinisikan sebagai

[𝐴𝑇]𝑖,𝑗 = [𝑎𝑗,𝑖]


Contoh 2.6.


] dimana 𝐴 ∈ ℝmax𝑛×𝑛

maka transpose dari matriks 𝐴 :

𝐴𝑇 = [1 2 52 4 68 2 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 {𝑎, 𝑏}

𝑎 ⊗ 𝑏 = 𝑎 + 𝑏, ∀ 𝑎, 𝑏 ∈ ℝ𝜀.

14

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. □

15

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 ≺ {𝑥, 𝑦} kecuali 𝑥 = 𝑦.

3. 𝑎 ⊕ 𝑎 = 𝑎𝑣 ⊕𝑎𝑣 = 𝑎⊕ 𝑎𝑣 = 𝑎𝑣⊕𝑎 = 𝑎𝑣.

4. −∞⊗ 𝑥 = 𝑥 ⊗−∞ = −∞ untuk setiap 𝑥 ∈ 𝑇.

5. 𝑎 ⊗ 𝑏 = 𝑎 + 𝑏 untuk semua 𝑎, 𝑏 ∈ ℝ.

6. 𝑎𝑣⊗𝑏 = 𝑎 ⊗ 𝑏𝑣 = 𝑎𝑣⊗𝑏𝑣 = (𝑎 + 𝑏)𝑣. □

Contoh 2.7. Berikut ini diberikan contoh operasi biner ⨁ dan ⊗ yang berlaku

dalam extended semiring tropical 𝑇.

1. −∞⊕ 5 = 5⊕−∞ = 5

2. 2⊕ 5 = max ≺ {2,5} = 5

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𝑣 ◊

1.6 Aljabar Supertropical

16

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.

17

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 𝑅.

18

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.


] dan 𝐵 = [5 3 68 2 36 4 1

] dimana 𝐴,𝐵 ∈ 𝑀𝑛(𝑅)

maka

[𝐴 ⊕ 𝐵]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

19

[𝐴 ⊕𝐵]2,3 = 2⊕ 3 = 3

[𝐴 ⊕𝐵]3,1 = 5⊕ 6 = 6

[𝐴 ⊕𝐵]3,2 = 8⊕ 4 = 8

[𝐴 ⊕𝐵]3,3 = 9⊕ 1 = 9


𝐴⊕ 𝐵 = [5 3 68 4 36 8 9

]

◊

1.7.2 Perkalian Matriks

Untuk sebarang matriks 𝐴 ∈ 𝑀𝑚×𝑛(𝑅) dan skalar 𝜆 ∈ 𝑅 maka perkalian 𝜆 ⊗ 𝐴


[𝜆 ⊗ 𝐴]𝑖,𝑗 = 𝜆⊗ 𝑎𝑖,𝑗


Untuk sebarang matriks 𝐴 ∈ 𝑀𝑚×𝑝(𝑅) dan 𝐵 ∈ 𝑀𝑝×𝑛(𝑅) perkalian matriks 𝐴⊗ 𝐵


[𝐴⊗ 𝐵]𝑖,𝑗 =⨁𝑎𝑖,𝑘⊗𝑏𝑘,𝑗

𝑝

𝑘=1


Contoh 2.11.


] dan skalar 𝜆 = 2 dimana 𝐴 ∈ 𝑀𝑛(𝑅) , 𝜆 ∈ 𝑅

maka

𝜆 ⊗ 𝑎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

20

𝜆 ⊗ 𝑎3,2 = 2 ⊗ 8 = 10

𝜆 ⊗ 𝑎3,3 = 2 ⊗ 9 = 11


𝜆 ⊗𝐴 = [7 5 910 6 57 10 11

]

◊

Contoh 2.12.


] dan 𝐵 = [3 2 57 4 25 8 9

] dimana 𝐴, 𝐵 ∈ 𝑀𝑛(𝑅)

maka

[𝐴⊗ 𝐵]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


𝐴⊗ 𝐵 = [10 13 1411 10 1215 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 = 𝐼𝑛.

21

Contoh 2.13.


] dimana 𝐴 ∈ 𝑀𝑛(𝑅)

maka

𝐴⊗2 = 𝐴⊗ 𝐴 = [1 2 57 4 25 8 9

] ⊗ [1 2 57 4 25 8 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


𝐴⊗2 = [10 13 1411 10 1215 17 18

]

◊

1.7.4 Transpose Matriks

Transpose dari matriks 𝐴 ∈ 𝑀𝑛(𝑅) dinotasikan dengan 𝐴𝑇, didefinisikan

sebagai [𝐴𝑇]𝑖,𝑗 = [𝑎𝑗,𝑖] untuk 𝑖 ∈ 𝑛 dan 𝑗 ∈ 𝑛.

Contoh 2.14.

Diberikan matriks 𝐴 = [1 2 3𝑣

2 4 25 6 1


maka transpose dari matriks 𝐴 :

𝐴𝑇 = [1 2 52 4 63𝑣 2 1

].

◊

22

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.

Diberikan matriks 𝐴 = [1 2 3𝑣

2 4 25 6 1

] dimana 𝐴 ∈ 𝑀𝑛(𝑅).

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 𝑐𝑜𝑓𝑖,𝑗 =

𝑀𝑖,𝑗. Matriks kofaktor dari 𝐴 ditulis sebagai Cof(𝐴) = [cof11 ⋯ cof1𝑛⋮ ⋱ ⋮

cof𝑛1 ⋯ cof𝑛𝑛

].

Sedangkan adjoin 𝐴 dinyatakan sebagai adj(𝐴) = (Cof(𝐴))𝑇 □

23

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.



Cof(𝐴) = [8 5𝑣 96 3𝑣 76 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. □

24

Contoh 2.17.




(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.


] dimana 𝐴 ∈ 𝑀𝑛(𝑅


(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 :

25

[𝑍𝐺]𝑖,𝑗 = {𝜀 , 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 :

[𝐼𝒢]𝑖,𝑗 ={𝑒 , untuk 𝑖 = 𝑗


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

[ �̅�𝒢 ]𝑖,𝑗 ={𝑒𝑣 , untuk 𝑖 = 𝑗


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 |𝐴| ≠ 𝜀. □

26

Contoh 2.19.




(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.

Cof(𝐴) = [4 5 48 5 87 3𝑣 6

]

adj(𝐴) = [4 8 75 5 3𝑣

4 8 6]

maka pseudo-invers dari 𝐴

𝐴∇ =1𝑅

|𝐴|⊗ adj(A)

𝐴∇ =1𝑅10⊗ [

4 8 75 5 3𝑣

4 8 6]

𝐴∇ = −10⊗ [4 8 75 5 3𝑣

4 8 6]

𝐴∇ = [−6 −2 −3−5 −5 −7𝑣

−6 −2 −4]

dan

𝐴⊗ 𝐴∇ = [1 5 21 1 23 1 3

]⊗ [−6 −2 −3−5 −5 −7𝑣

−6 −2 −4] = [

0 0𝑣 −2𝑣

−4𝑣 0 −2𝑣

−3𝑣 1𝑣 0

] = 𝐼𝒢

Berdasarkan Contoh 2.19 didapatkan perkalian 𝐴 ⊗ 𝐴∇ = 𝐼𝒢 menghasilkan

pseudo-identitas. ◊

27

Contoh 2.20.


] dimana 𝐴 ∈ 𝑀𝑛(𝑅

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.

Cof(𝐴) = [4 2𝑣 36 2𝑣 57 3𝑣 6

]

adj(𝐴) = [4 6 72𝑣 2𝑣 3𝑣

3 5 6]

maka pseudo-invers dari 𝐴

𝐴∇ = (1𝑅

|𝐴|)𝑣

⊗ adj(A)

𝐴∇ = (1𝑅

7)𝑣

⊗ [4 6 72𝑣 2𝑣 3𝑣

3 5 6]

𝐴∇ = (−7)𝑣⊗ [4 6 72𝑣 2𝑣 3𝑣

3 5 6]

𝐴∇ = [−3𝑣 −1𝑣 0𝑣

−5𝑣 −5𝑣 −4𝑣

−4𝑣 −2𝑣 −1𝑣]

dan

𝐴 ⊗𝐴∇ = [1 5 21 1 20 2 1

] ⊗ [−3𝑣 −1𝑣 0𝑣

−5𝑣 −5𝑣 −4𝑣

−4𝑣 −2𝑣 −1𝑣] = [

0𝑣 0𝑣 1𝑣

−2𝑣 0𝑣 1𝑣

−3𝑣 −1𝑣 0𝑣] = 𝐼�̅�

Berdasarkan Contoh 2.20 didapatkan perkalian 𝐴 ⊗ 𝐴∇ = �̅�𝒢 menghasilkan

pseudo-identitas ghost. ◊

28

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.


] dan 𝐵 = [−6 −2 −3−5 −5 −7𝑣

−6 −2 −4], dimana

𝐴,𝐵 ∈ 𝑀𝑛(𝑅)

maka

𝐴 ⊗ 𝐵 = [1 5 21 1 23 1 3

] ⊗ [−6 −2 −3−5 −5 −7𝑣

−6 −2 −4] = [

0 0𝑣 −2𝑣

−4𝑣 0 −2𝑣

−3𝑣 1𝑣 0

] = 𝐼𝒢

dalam hal ini matriks 𝐵 disebut pseudo-invers kanan dari 𝐴, sedangkan

𝐼𝒢 merupakan pseudo-identitas kanan dari 𝐴

𝐵⊗ 𝐴 = [−6 −2 −3−5 −5 −7𝑣

−6 −2 −4]⊗ [

1 5 21 1 23 1 3

] = [0 −1𝑣 0𝑣

−4𝑣 0 −3𝑣

−1𝑣 −1𝑣 0

] = 𝐼𝒢

dalam hal ini matriks 𝐵 disebut pseudo-invers kiri dari 𝐴, sedangkan 𝐼𝒢 merupakan

pseudo-identitas kiri dari 𝐴. ◊

Contoh 2.22.


] dan 𝐵 = [−3𝑣 −1𝑣 0𝑣

−5𝑣 −5𝑣 −4𝑣

−4𝑣 −2𝑣 −1𝑣], dimana 𝐴, 𝐵 ∈

𝑀𝑛(𝑅)

maka

𝐴 ⊗ 𝐵 = [1 5 21 1 20 2 1

] ⊗ [−3𝑣 −1𝑣 0𝑣

−5𝑣 −5𝑣 −4𝑣

−4𝑣 −2𝑣 −1𝑣] = [

0𝑣 0𝑣 1𝑣

−2𝑣 0𝑣 1𝑣

−3𝑣 −1𝑣 0𝑣] = 𝐼�̅�

29

dalam hal ini matriks 𝐵 disebut pseudo-invers kanan dari 𝐴, sedangkan

𝐼�̅� merupakan pseudo-identitas ghost kanan dari 𝐴

𝐵 ⊗ 𝐴 = [−3𝑣 −1𝑣 0𝑣

−5𝑣 −5𝑣 −4𝑣

−4𝑣 −2𝑣 −1𝑣] ⊗ [

1 5 21 1 20 2 1

] = [0𝑣 2𝑣 1𝑣

−4𝑣 0𝑣 −3𝑣

−1𝑣 1𝑣 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

𝐴 = [0 10 −∞−∞ 4 3−∞ −∞ 0

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝑏 = [

262]

dalam bentuk perkalian matriks dapat ditulis sebagai :

[0 10 −∞−∞ 4 3−∞ −∞ 0

]⊗ [

𝑥1𝑥2𝑥3] = [

262]

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

penyelesaian berarti ada 𝒙 = [𝑥1𝑥2𝑥3] sehingga

[0 10 −∞−∞ 4 3−∞ −∞ 0

]⊗ [

𝑥1𝑥2𝑥3] = [

262]

didapat

30

(−∞⊗ 𝑥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 sub-

penyelesaian 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 𝐴⊗ 𝒙 = 𝜺 ≤ 𝒃. □

Definisi 2.24. [20]. Suatu subpenyelesaian �̂� dari sistem sistem 𝐴⊗ 𝒙 = 𝒃 disebut

sub-penyelesaian terbesar sistem 𝐴⊗ 𝒙 = 𝒃 jika 𝒙′ ≤ �̂� untuk setiap sub-

penyelesaian 𝒙′ dari sistem 𝐴⊗ 𝒙 = 𝒃. □

Teorema 2.2. [20]. Diberikan 𝐴 ∈ ℝmax𝑚×𝑛 dengan unsur-unsur setiap kolomnya

tidak semuanya sama dengan 𝜀 dan 𝒃 ∈ ℝmax𝑚 . Sub-penyelesaian terbesar 𝐴⊗ 𝒙 =

𝒃 ada dan diberikan oleh �̂� dengan

−�̂�𝒋 = max𝑖(−𝒃𝒊 + 𝐴𝑖𝑗)

untuk setiap 𝑖 = 1, 2, 3,… ,𝑚 dan 𝑗 = 1, 2, 3,… , 𝑛.

Bukti :

𝐴⊗ 𝒙 ≤ 𝒃 ⇔ {

𝐴11⊗𝑥1⊕𝐴12⊗𝑥2⊕…⊕𝐴1𝑛⊗𝑥𝑛 ≤ 𝑏1𝐴21⊗𝑥1⊕𝐴22⊗𝑥2⊕…⊕𝐴2𝑛⊗𝑥𝑛 ≤ 𝑏2

⋮𝐴𝑚1⊗𝑥1⊕𝐴𝑚2⊗𝑥2⊕…⊕𝐴𝑚𝑛⊗𝑥𝑛 ≤ 𝑏𝑛

31

⇔ (⨁(𝐴𝑖𝑗 ⊗𝑥𝑗)

𝑛

𝑗=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 𝐴⊗ 𝒙 = 𝒃.

∎

32

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 :

−�̂� = [

−�̂�1−�̂�2⋮−�̂�𝑛

] =

[ max𝑖 (−𝑏𝑖 + 𝐴𝑖1 )

max𝑖 (−𝑏𝑖 + 𝐴𝑖2 )

⋮max𝑖 (−𝑏𝑖 + 𝐴𝑖𝑚 )]

=

[ max𝑖(𝐴𝑖1 − 𝑏𝑖)

max𝑖(𝐴𝑖2 − 𝑏𝑖)

⋮max𝑖(𝐴𝑖𝑚 − 𝑏𝑖) ]

= [

𝐴11⊗ (−𝑏1) ⊕ 𝐴21⊗ (−𝑏2) ⊕…⊕ 𝐴𝑚1⊗ (−𝑏𝑚)

𝐴12⊗ (−𝑏1) ⊕ 𝐴22⊗ (−𝑏2) ⊕…⊕ 𝐴𝑚2⊗ (−𝑏𝑚)⋮

𝐴1𝑛⊗ (−𝑏1) ⊕ 𝐴2𝑛⊗ (−𝑏2) ⊕ …⊕ 𝐴𝑚𝑛⊗ (−𝑏𝑚)

] = 𝐴𝑇 ⊗ (−𝒃)

Sub-penyelesaian terbesar 𝐴⊗ 𝒙 = 𝒃 dapat ditentukan dengan langkah pertama

menghitung −�̂� = 𝐴𝑇⊗ (−𝒃) atau �̂� = −(𝐴𝑇⊗ (−𝒃)).

Contoh 2.24.


𝐴 = [1 2 62 3 14 1 −2

] , 𝑥 = [

𝑥1𝑥2𝑥3] , 𝑏 = [

543

]

dalam bentuk perkalian matriks dapat ditulis sebagai

[1 2 62 3 14 1 −2

]⨂[

𝑥1𝑥2𝑥3] = [

543

]

akan ditentukan penyelesaian terbesar sistem persamaan tersebut dengan terlebih

dahulu menentukan sub-penyelesaian terbesarnya.

Pertama dihitung −�̂� = 𝐴𝑇⊗ (−𝒃)

−�̂� = 𝐴𝑇⊗ (−𝒃) = [1 2 4

2 3 1

6 1 −2

]⨂ [−5

−4

−3

] = [1

−1

1

]

33

�̂� = [−1

1

−1

]

karena [1 2 62 3 14 1 −2

]⊗ [−11−1] = [

543], maka [

−11−1] merupakan penyelesaian sistem.

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.


𝐴 = [2 2 12 1 33 2 5

] , 𝑥 = [

𝑥1𝑥2𝑥3] , 𝑏 = [

264]

dalam bentuk perkalian matriks dapat ditulis sebagai

[2 2 12 1 33 2 5

]⨂ [

𝑥1𝑥2𝑥3] = [

264]

akan ditentukan penyelesaian terbesar sistem persamaan tersebut dengan terlebih

dahulu menentukan sub-penyelesaian terbesarnya.

−�̂� = 𝐴𝑇⊗ (−𝒃) = [2 2 3

2 1 2

1 3 5

]⨂ [−2

−6

−4

] = [0

0

1

]

�̂� = [0

0

−1

]

Karena [2 2 12 1 33 2 5

]⨂ [00−1] = [

224] ≤ [

264], maka [

00−1] bukan merupakan penyelesaian

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

34

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 𝑎12 … 𝑎1𝑛𝑎21 𝑎22 … 𝑎2𝑛⋮ ⋮ ⋱ ⋮𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛

]⊗ [

𝑥1𝑥2⋮𝑥𝑛

] = [

𝑏1𝑏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 𝑎1,2 … 𝑎1,𝑛𝑎2,1 𝑎2,2 … 𝑎2,𝑛⋮ ⋮ ⋱ ⋮𝑎𝑛,1 𝑎𝑛,2 … 𝑎𝑛,𝑛

] ⊗ [

𝑥1𝑥2⋮𝑥𝑛

] =

[ 𝑏1⋮𝑏𝑘−∞⋮−∞]

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,𝑗 , … , 𝑎𝑛,𝑗 = 𝜀

35

terjadi pertama, didapatkan

[

𝐴1 𝐴2−∞ ⋯ −∞⋮ ⋱ ⋮−∞ ⋯ −∞

𝐴3] ⊗

[ 𝑥1⋮𝑥𝑙𝑥𝑙+1⋮𝑥𝑛 ]

=

[ 𝑏1⋮𝑏𝑘−∞⋮−∞]

dengan matriks 𝐴1 berukuran 𝑘 × 𝑙. Misalkan :

�̅� = [𝑏1⋮𝑏𝑘

] dan �̅� = [𝑥1⋮𝑥𝑙]

Catatan bahwa : 𝐴⊗ 𝒙 = 𝒃 mempunyai penyelesaian, maka 𝑥𝑙+1, … , 𝑥𝑛 =

−∞ dan 𝐴1⊗ �̅� = �̅�. Jadi 𝐴⊗ 𝒙 = 𝒃 mempunyai penyelesaian bila dan hanya

bila �̅� adalah penyelesaian dari 𝐴1⊗ �̅� = �̅� dan penyelesaian dari 𝐴 ⊗𝒙 = 𝒃

adalah

𝒙 = [

�̅�−∞⋮−∞

]

Oleh karena itu, penyelesaian dari 𝐴⊗ 𝒙 = 𝒃 dengan beberapa elemen 𝒃 takhingga

dapat direduksi ke bentuk 𝐴1⊗ �̅� = �̅� dengan semua elemen dari �̅� berhingga. Jadi

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) }

36

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𝑛), … , (𝑏𝑛 − 𝑎𝑛𝑛) }

Jadi calon penyelesaian dari 𝐴 ⊗𝒙 = 𝒃 yang dinotasikan dengan �̅� adalah

�̅� = [

�̅�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 𝑏1 − 𝑎12 … 𝑏1 − 𝑎1𝑛𝑏2 − 𝑎21 𝑏2 − 𝑎22 ⋮ 𝑏2 − 𝑎2𝑛

⋮ ⋮ ⋮ ⋮𝑏𝑛 − 𝑎𝑛1 𝑏𝑛 − 𝑎𝑛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

37

Selesaikan 𝐴⊗ 𝒙 = 𝒃, jika

𝐴 = [1 −9 4−4 18 −82 1 −4

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝑏 = [

1−6−3]

didapatkan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏 sebagai berikut :

𝐷𝐴,𝑏 = [0 10 −3−2 −24 2−5 −4 1

] dan 𝑅𝐴,𝑏 = [0 0 10 1 01 0 0

]

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

�̅� = [−5−24−3

]

hal ini bisa di cek sebagai berikut :

𝐴⊗ �̅� = [1 −9 4−4 18 −82 1 −4

]⊗ [−5−24−3

] = [𝑚𝑎𝑥(−4,−33,1)

𝑚𝑎𝑥(−9, −6,−11)

𝑚𝑎𝑥(−3, −23,−7)] = [

1−6−3] = 𝒃.

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

38

Selesaikan 𝐴 ⊗𝒙 = 𝒃, jika

𝐴 = [1 −9 4−4 18 −82 1 −4

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝑏 = [

213]


𝐷𝐴,𝑏 = [1 11 −25 −17 91 2 7

] dan 𝑅𝐴,𝑏 = [1 0 10 1 01 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

menandakan bahwa 𝐴⊗ 𝒙 = 𝒃 mempunyai banyak penyelesaian �̅�. Elemen-

elemen minimum dari setiap kolom matriks 𝐷𝐴,𝑏 yaitu

�̅� = [1−17−2

]

Hal ini bisa di cek sebagai berikut :

𝐴⊗ �̅� = [1 −9 4−4 18 −82 1 −4

]⊗ [1−17−2

] = [𝑚𝑎𝑥(2,−26, 2)

𝑚𝑎𝑥(−3, 1,−10)

𝑚𝑎𝑥(3,−16,−6)] = [

213] = 𝒃.

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 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

39

�̅� = [1−17𝑝3

] untuk setiap 𝑝3 < −2

Contoh 2.28. Kasus 𝐴 ⊗ 𝒙 = 𝒃 tidak mempunyai penyelesaian


𝐴 = [1 −9 4−4 18 −82 1 −4

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝑏 = [

123]


𝐷𝐴,𝑏 = [0 10 −36 −16 101 2 7

] dan 𝑅𝐴,𝑏 = [1 0 10 1 00 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 −9 4−4 18 −82 1 −4

]⊗ [0−16−3

] = [𝑚𝑎𝑥(1,−25, 1)

𝑚𝑎𝑥(−4, 2,−11)

𝑚𝑎𝑥(2,−15,−7)] = [

122] < [

123] = 𝒃.


Pada baris pertama nilai maksimum dicapai dua kali yaitu pada saat elemen

𝑥1 = 0 dan elemen 𝑥3 = −3.



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.

40

Berdasarkan Contoh 2.26 sampai 2.28 didapatkan matriks 𝑅𝐴,𝑏 untuk penyelesaian

tunggal, tak hingga banyak dan tidak mempunyai penyelesaian sebagai berikut :

Solusi tunggal

Solusi tak hingga

banyak

Tidak mempunyai

penyelesaian

𝐷𝐴,𝑏 = [0 10 −3−2 −24 2−5 −4 1

] 𝐷𝐴,𝑏 = [1 11 −25 −17 91 2 7

] 𝐷𝐴,𝑏 = [0 10 −36 −16 101 2 7

]

𝑅𝐴,𝑏 = [0 0 10 1 01 0 0

] 𝑅𝐴,𝑏 = [1 0 10 1 01 0 0

] 𝑅𝐴,𝑏 = [0 1 01 0 10 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

bernilai 0 dan andaikan bahwa �̅� adalah suatu penyelesian dari persamaan 𝐴⊗ 𝒙 =

𝒃, maka :

�̅�𝑗 ≤ 𝑚𝑖𝑛{𝑏𝑙 − 𝑎𝑙,𝑗} < (𝑏𝑘 − 𝑎𝑘,𝑗), ∀𝑙 ∈ 𝑛.

Jadi �̅�𝑗 + 𝑎𝑘,𝑗 < 𝑏𝑘 untuk semua 𝑗. Dengan demikian �̅� tidak memenuhi

persamaan ke- 𝑘. Hal ini bertentangan dengan �̅� adalah suatu penyelesaian dari

𝐴⊗ 𝒙 = 𝒃. Jadi �̅� bukan penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃 sehingga 𝐴⊗ 𝒙 = 𝒃 tidak

punya penyelesaian. Berikutnya, andaikan �̅� bukan penyelesaian dari 𝐴⊗ 𝒙 = 𝒃

maka �̅�𝑗 < 𝑏𝑘 − 𝑎𝑘,𝑗 untuk semua 𝑘, 𝑗. Jadi :

𝑚𝑎𝑥{𝑎𝑘,𝑗 + �̅�𝑗} ≤ 𝑏𝑘 , ∀𝑗 ∈ 𝑛

dan bila �̅� bukan penyelesaian dari 𝐴⊗ 𝒙 = 𝒃, maka ada suatu 𝑘 dengan

𝑚𝑎𝑥{𝑎𝑘,𝑗 + �̅�𝑗} < 𝑏𝑘 , ∀𝑗 ∈ 𝑛

karena

�̅�𝑗 = 𝑚𝑖𝑛{𝑏𝑙 − 𝑎𝑙,𝑗} untuk beberapa 𝑙

41

maka tidak ada elemen di baris ke- 𝑘 pada matriks 𝑅𝐴,𝑏 yang bernilai 1. Hal ini

bertentangan bahwa setiap baris dari matriks 𝑅𝐴,𝑏 setidaknya memuat elemen yang

bernilai 1. Jadi haruslah �̅� adalah suatu penyelesaian dari 𝐴 ⊗ 𝒙 = 𝒃. ∎

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

Solusi tak hingga banyak

𝑅𝐴,𝑏 = [

0 0 𝟏

0 𝟏 0

𝟏 0 0] 𝑅𝐴,𝑏 = [

𝟏 0 1

0 𝟏 0

𝟏 0 0]

Dari tabel tersebut dapat dijelaskan beberapa hal sebagai berikut :

Berdasarkan Contoh 2.26 didapat matriks

𝐷𝐴,𝑏 = [0 10 −3−2 −24 2−5 −4 1

] dan 𝑅𝐴,𝑏 = [0 0 𝟏

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

42

𝐷𝐴,𝑏 = [1 11 −25 −17 91 2 7

] dan 𝑅𝐴,𝑏 = [𝟏 0 1

0 𝟏 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 �̅�𝑗.

Dengan demikian walaupun �̅�𝑗 menunjukkan nilai maksimum yang mungkin untuk

elemen ini, akan tetapi untuk setiap nilai yang lebih kecil atau samadengan �̅�𝑗 tidak

akan mempengaruhi eksistensi persamaan baris yang telah ditetapkan. ∎

1.9 Sistem Persamaan Linear atas Aljabar Supertropical

43

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.

45

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


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


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.

47

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.


𝐴 = [0 10 −∞−∞ 4 3−∞ −∞ 0

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝑏 = [

262]


[0 10 −∞−∞ 4 3−∞ −∞ 0

]⊗ [

𝑥1𝑥2𝑥3] = [

262]


(0 ⊗ 𝑥1)⊕ (10⊗ 𝑥2) ⊕ (−∞⊗ 𝑥3) = 2

48

(−∞⊗ 𝑥1)⊕ (4⊗ 𝑥2) ⊕ (3⊗ 𝑥3) = 6

(−∞⊗ 𝑥1)⊕ (−∞⊗𝑥2) ⊕ (0⊗ 𝑥3) = 2

sistem persamaan 𝐴⊗ 𝒙 = 𝒃 tersebut tidak punya penyelesaian, sebab bila punya

penyelesaian berarti ada 𝒙 = [

𝑥1𝑥2𝑥3] sehingga

[0 10 −∞−∞ 4 3−∞ −∞ 0

]⊗ [

𝑥1𝑥2𝑥3] = [

262]

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.

49

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. 𝑥 ⊨ 𝑎𝑣


{𝑏𝑣|𝑏 ∈ 𝒯 𝑑𝑎𝑛 𝑏 ≽𝑣 𝑎 }

3. 𝑥 ⊨ 𝜀


{𝜀} ∪ {𝑏𝑣|𝑏 ∈ 𝒯 }

50

Contoh 4.1. Diberikan persamaan dalam relasi ghost surpass sebagai berikut :

1. 𝑥 ⊨ 2

himpunan penyelesaian dari 𝑥 adalah

{2} ∪ {𝑏𝑣|𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 2 }

2. 𝑥 ⊨ 8𝑣


{𝑏𝑣|𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 8 }

3. 𝑥 ⊕ 4 ⊨ 3


{4} ∪ {𝑏𝑣|𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 4 }

4. 𝑥 ⊕ 2𝑣 ⊨ 5


{5} ∪ {𝑏𝑣|𝑏 ∈ 𝒯 dan 𝑏 ≽𝑣 5 }

5. 𝑥 ⊕ 6𝑣 ⊨ 3


{𝑏|𝑏 ∈ 𝒯 𝑑𝑎𝑛 𝑏 ≼𝑣 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 𝑎 ⊗ 𝑥 ⊨ 𝑏.

51

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⊗𝑏. ∎

52

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 .

53

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) ⊨ |𝐴| ⊗ 𝐼𝐴.

54

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 :

55

𝐴⊗ 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 𝒃

56

𝑋 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

𝐴 = (adj(A))⊗−1

⊗ |𝐴| ⊗ 𝐼𝐴

⟺ 𝐴 = |𝐴| ⊗ (adj(A))⊗−1

⊗ 𝐼𝐴

⟺ 𝐴⊗−1 = (|𝐴|⊗ (adj(A))⊗−1

⊗ 𝐼𝐴)⊗−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))⊗ (𝐵 ⊕ (𝐺 ⊗ 𝑥𝑛)) (4.7)

substitusikan persamaan (4.7) pada persamaan (4.5), diperoleh

57

(𝐻⊗ 𝑋) ⊕ (𝑎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. ∎

58

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 −9 4−4 18 −82 1 −4

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝑏 = [

1−6−3]

penyelesaian 𝐴⊗ 𝒙 ⊨ 𝒃 dengan menggunakan aturan Cramer

𝐷 = (𝑎11⊗𝑎22⊗𝑎33)⊕ (𝑎11⊗𝑎23⊗𝑎32)⊕ (𝑎12⊗𝑎21⊗𝑎33)

⊕ (𝑎12⊗𝑎23⊗𝑎31) ⊕ (𝑎13⊗𝑎21⊗𝑎32) ⊕ (𝑎13⊗𝑎22⊗𝑎31)

59

⟺ 𝐷 = (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 −9 4−6 18 −8−3 1 −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 ∈ 𝒯.

𝐷2 = |1 1 4−4 −6 −82 −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 ∈ 𝒯.

𝐷3 = |1 −9 1−4 18 −62 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

adj(A)⊗ 𝒃 = [𝐷1𝐷2𝐷3

] = [1901] ∈ 𝒯0

𝑛

penyelesaian dari persamaan tersebut adalah

𝑥1 =𝐷1𝐷=19

24= −24⊗ 19 = −5

𝑥2 =𝐷2𝐷=0

24= −24⊗ 0 = −24

𝑥3 =𝐷1𝐷=21

24= −24⊗ 21 = −3


𝐴⊗ 𝒙 = [1 −9 4−4 18 −82 1 −4

]⊗ [−5−24−3

] = [𝑚𝑎𝑥(−4,−33,1)

𝑚𝑎𝑥(−9, −6,−11)

𝑚𝑎𝑥(−3, −23,−7)] = [

1−6−3] = 𝒃.

60

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


𝐴 = [1 −9 4−4 18 −82 1 −4

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝑏 = [

213]

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 ∈ 𝒯.

𝐷1 = |2 −9 41 18 −83 1 −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 ∈ 𝒯.

𝐷2 = |1 2 4−4 1 −82 3 −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 ∈ 𝒯.

𝐷3 = |1 −9 2−4 18 12 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

61


] = [25722𝑣

] ∉ 𝒯0𝑛


𝑥1 =𝐷1𝐷=25

24= −24⊗ 25 = 1

𝑥2 =𝐷2𝐷=7

24= −24⊗ 7 = −17

𝑥3 =𝐷1𝐷=22𝑣

24= −24⊗ 22𝑣 = −2𝑣


𝐴⊗ 𝒙 = [1 −9 4−4 18 −82 1 −4

]⊗ [1−17−2𝑣

] = [𝑚𝑎𝑥(2, −26,2)

𝑚𝑎𝑥(−3,1,−10)

𝑚𝑎𝑥(3,−16,−6𝑣)] = [

2𝑣

13

] ⊨ [213] = 𝒃.

karena 𝐷 ∈ 𝒯 dan terdapat 𝐷𝑥𝑖 ∈ 𝒢 untuk beberapa 𝑖, maka persamaan 𝐴⊗ 𝒙 ⊨ 𝒃

dalam aljabar supertropical 𝑅 mempunyai penyelesaian tidak tunggal.

penyelesaian tangible dengan 𝑘3 ∈ 𝒯 adalah

𝒙 = [1−17𝑘3

] untuk setiap 𝑘3 ≼𝑣− 2. ◊

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


𝐴 = [1 2 34 1 52 2 2

] , 𝒙 = [

𝑥1𝑥2𝑥3] dan 𝒃 = [

114]

62

|𝐴| = (𝑎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

adj(A) = [7 5 77 5 76 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

𝒙 = [776]


𝐴⊗ 𝒙 = [1 2 34 1 52 2 2

]⊗ [776] = [

9𝑣

11𝑣

9𝑣] ⊨ [

114]

jika 𝒙 adalah kolom ke-2 dari Adj (𝐴), maka

𝒙 = [554

]


𝐴⊗ 𝒙 = [1 2 34 1 52 2 2

] ⊗ [554

] = [7𝑣

9𝑣

7𝑣] ⊨ [

114]

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 𝐴⊗ 𝒙 ⊨ 𝒃. ◊

63

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.


𝐴 = [4 0 −2−1 −2 −5−1 −2 −2

] , 𝑥 = [

𝑥1𝑥2𝑥3] dan , 𝒃 = [

512

]

Penyelesaian 𝐴⊗ 𝒙 = 𝒃 dengan menggunakan matriks 𝐷𝐴,𝑏 dan 𝑅𝐴,𝑏


64

𝐷𝐴,𝑏 = [1 5 72 3 63 4 4

] dan 𝑅𝐴,𝑏 = [1 0 00 1 00 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

𝒙 = [134]


𝐴⊗ 𝒙 = [4 0 −2−1 −2 −5−1 −2 −2

]⊗ [134] = [

𝑚𝑎𝑥(5,3,2)

𝑚𝑎𝑥(0,1,−1)

𝑚𝑎𝑥(0,1,2)] = [

512

] = 𝒃.



persamaan baris pertama menetapkan elemen 𝑥1 = 1.


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)⊕

65

(0 ⊗ −5⊗−1)⊕ (−2⊗−1⊗−2)⊕ (−2⊗−2⊗−1)

⟺ 𝐷 = 0⊕−3⊕−3⊕−6⊕−5⊕−5 = 0 ∈ 𝒯.

𝐷1 = [5 0 −21 −2 −52 −2 −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 ∈ 𝒯.

𝐷2 = [4 5 −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 ∈ 𝒯.

𝐷3 = [4 0 5−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

adj(A) ⊗ 𝒃 = [𝐷1𝐷2𝐷3

] = [134] ∈ 𝒯0

𝑛


𝑥1 =𝐷1𝐷=1

0= −0⊗ 1 = 1

𝑥2 =𝐷2𝐷=3

0= −0⊗ 3 = 3

𝑥3 =𝐷1𝐷=4

0= −0⊗4 = 4


𝐴⊗ 𝒙 = [4 0 −2−1 −2 −5−1 −2 −2

]⊗ [134] = [

𝑚𝑎𝑥(5,3,2)

𝑚𝑎𝑥(0,1,−1)

𝑚𝑎𝑥(0,1,2)] = [

512

] = 𝒃

66

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)

Selesaikan 𝐴 ⊗𝒙 = 𝒃, jika 𝐴 = [2 5 13 8 2

] , 𝑥 = [

𝑥1𝑥2𝑥3] , 𝑏 = [

710]

𝐴𝑇 ⊗𝐴⊗ 𝒙 = 𝐴𝑇⊗𝒃

[2 35 81 2

]⊗ [2 5 13 8 2

]⊗ [

𝑥1𝑥2𝑥3] = [

2 35 81 2

] ⊗ [710]

[6 11 511 16 105 10 4

]⊗ [

𝑥1𝑥2𝑥3] = [

131812]



𝐷𝐴,𝑏 = [7 2 87 2 87 2 8

] dan 𝑅𝐴,𝑏 = [1 1 11 1 11 1 1

]


1, sedangkan pada setiap baris terdapat nilai 1 lebih dari satu. Hal tersebut

menandakan bahwa 𝐴⊗ 𝒙 = 𝒃 mempunyai banyak penyelesaian 𝒙. Elemen-

elemen minimum dari setiap kolom matriks 𝐷𝐴,𝑏 yaitu

𝒙 = [728]

Hal ini bisa di cek sebagai berikut :

[6 11 511 16 105 10 4

] ⊗ [728] = [

13𝑣

18𝑣

12𝑣].

dari hal tersebut dapat dijelaskan bahwa :

67

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𝑘3

] untuk setiap 𝑘2 < 2 dan 𝑘3 < 8

𝒙 = [𝑘12𝑘3


𝒙 = [𝑘1𝑘28



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.

𝐷1 = [13 11 518 16 1012 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.

𝐷2 = [6 13 511 18 105 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.

𝐷3 = [6 11 1311 16 185 10 12

]

68

⟺ 𝐷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


] = [33𝑣

28𝑣

34𝑣] ∉ 𝒯0

𝑛


𝑥1 =𝐷1𝐷=33𝑣

26𝑣= −26𝑣⊗33𝑣 = 7𝑣

𝑥2 =𝐷2𝐷=28𝑣

26𝑣= −26𝑣⊗28𝑣 = 2𝑣

𝑥3 =𝐷1𝐷=34𝑣

26𝑣= −26𝑣⊗34𝑣 = 8𝑣

hal ini bisa di cek sebagai berikut

[6 11 511 16 105 10 4

]⊗ [728] = [

13𝑣

18𝑣

12𝑣]

penyelesaian tangible lain dengan 𝑘 ∈ 𝒯 adalah

𝒙 = [7𝑘2𝑘3


𝒙 = [𝑘12𝑘3


𝒙 = [𝑘1𝑘28


karena 𝐷 ∈ 𝒢0 dan 𝐷𝑥𝑖 ∈ 𝒢0 untuk setiap 𝑖, maka persamaan 𝐴 ⊗𝒙 = 𝒃

mempunyai penyelesaian tidak tunggal. ◊

Contoh 4.8. (Banyak persamaan lebih dari banyak peubah)

Selesaikan 𝐴 ⊗𝒙 = 𝒃, jika 𝐴 = [1 23 49 2

] , 𝑥 = [𝑥1𝑥2] , 𝑏 = [

367]

𝐴𝑇 ⊗𝐴⊗ 𝒙 = 𝐴𝑇⊗𝒃

69

[1 3 92 4 2

]⊗ [1 23 49 2

] ⊗ [𝑥1𝑥2] = [

1 3 92 4 2

]⊗ [367]

[18 1111 8

]⊗ [𝑥1𝑥2] = [

169]



𝐷𝐴,𝑏 = [−2 5−2 1

] dan 𝑅𝐴,𝑏 = [1 01 1

]


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

𝒙 = [−21]


[18 1111 8

]⊗ [−21] = [

𝑚𝑎𝑥(16,12)

𝑚𝑎𝑥(9, 9)] = [

169𝑣] ⊨ 𝒃.



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𝑘2] untuk setiap 𝑘2 < 1

70


menggunakan aturan Cramer dalam aljabar supertropical sebagai berikut.

𝐷 = (𝑎11⊗𝑎22) ⊕ (𝑎12⊗𝑎21)

⟺ 𝐷 = (18⊗ 8)⊕ (11⊗ 11)

⟺ 𝐷 = 26⊕ 22 = 26 ∈ 𝒯.

𝐷1 = [16 119 8

]

⟺ 𝐷1 = (16⊗ 8)⊕ (11⊗ 9)

⟺ 𝐷1 = 24⊕ 20 = 24 ∈ 𝒯.

𝐷2 = [18 1611 9

]

⟺ 𝐷2 = (18⊗ 9)⊕ (16⊗ 11)

⟺ 𝐷2 = 27⊕ 27 = 27𝑣 ∈ 𝒢0.

sehingga diperoleh

[𝐷1𝐷2] = [

2427𝑣

] ∉ 𝒯0𝑛


𝑥1 =𝐷1𝐷=24

26= −26⊗ 24 = −2

𝑥2 =𝐷2𝐷=27𝑣

26= −26⊗ 27𝑣 = 1𝑣

hal ini dapat dicek sebagai berikut

[18 1111 8

]⊗ [−21] = [

𝑚𝑎𝑥(16,12)

𝑚𝑎𝑥(9, 9)] = [

169𝑣]

penyelesaian tangible lain dengan 𝑘 ∈ 𝒯 adalah

𝒙 = [−2𝑘2] untuk setiap 𝑘2 < 1

karena 𝐷 ∈ 𝒯 dan 𝐷𝑥𝑖 ∈ 𝒢0 untuk beberapa 𝑖, maka persamaan 𝐴 ⊗𝒙 = 𝒃

mempunyai penyelesaian tidak tunggal. ◊

71

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

𝐴 = [0 5 −∞2 7 8−∞ −∞ 0

] , 𝑥 = [

𝑥1𝑥2𝑥3]


[0 5 −∞2 7 8−∞ −∞ 0

]⊗ [

𝑥1𝑥2𝑥3] = [

−∞−∞−∞

]


(0 ⊗ 𝑥1) ⊕ (5⊗ 𝑥2) ⊕ (−∞⊗ 𝑥3) = −∞

(2 ⊗ 𝑥1) ⊕ (7⊗ 𝑥2) ⊕ (8⊗ 𝑥3) = −∞

(−∞⊗𝑥1) ⊕ (−∞⊗𝑥2) ⊕ (0⊗ 𝑥3) = −∞

sistem persamaan 𝐴⊗ 𝒙 = 𝜺 diatas tidak mempunyai penyelesaian tak trivial,

sebab bila punya penyelesaian tak trivial berarti ada 𝒙 = [

𝑥1𝑥2𝑥3] tidak semuanya sama

dengan 𝜀 sehingga

[0 5 −∞2 7 8−∞ −∞ 0

]⊗ [

𝑥1𝑥2𝑥3] = [

−∞−∞−∞

]

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.

72

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 𝑅.

𝑥 ⊨ 𝜀


{𝜀} ∪ {𝑏𝑣|𝑏 ∈ 𝒯 }

□

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.

73

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.

Diberikan 𝑉 = {𝒗𝟏, 𝒗𝟐, 𝒗𝟑} di 𝑅3, dengan 𝒗𝟏 = [0−∞−∞

], 𝒗𝟐 = [104−∞

], 𝒗𝟑 = [−∞30]

vektor 𝒗𝟏 , 𝒗𝟐 dan 𝒗𝟑 adalah bebas supertropical. Untuk membuktikan hal tersebut

maka harus ditunjukkan bahwa satu-satunya cara agar

74

𝛼1 ⊗ [0−∞−∞

]⊕ 𝛼2⊗ [104−∞

]⊕ 𝛼3⊗ [−∞30] ∈ 𝒢0

(3)

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

[0 10 −∞−∞ 4 3−∞ −∞ 0

]⊗ [

𝛼1𝛼2𝛼3] ∈ 𝒢0

(3)

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. ◊

75

Contoh 4.10.

Diberikan 𝑉 = {𝒗𝟏, 𝒗𝟐, 𝒗𝟑} di 𝑅3 , dengan 𝒗𝟏 = [0−∞0] , 𝒗𝟐 = [

24−∞

], 𝒗𝟑 = [−∞20]

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

𝛼1 ⊗ [0−∞0]⊕ 𝛼2⊗ [

24−∞

]⊕ 𝛼3⊗ [−∞20] ∈ 𝒢0

(3)

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

[0 2 −∞−∞ 4 20 −∞ 0

]⊗ [

𝛼1𝛼2𝛼3] ∈ 𝒢0

(3)

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 2 −∞−∞ 4 20 −∞ 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

76

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 𝑘 ∈ 𝒯. ∎

77

4.4.1 Penyelesaian 𝐴⊗ 𝒙 ⊨ 𝜺 dimana |𝑨| ∈ 𝓣 dalam Aljabar Supertropical

Contoh 4.13.

Selesaikan 𝐴 ⊗𝒙 ⊨ 𝜺, jika 𝐴 = [1 4 −11 0 63 1 3

] , 𝑥 = [

𝑥1𝑥2𝑥3]

sistem persamaan 𝐴⊗ 𝒙 ⊨ 𝜺 ⟺ 𝐴⊗ 𝒙 ∈ 𝒢0(3)

[1 4 −11 0 63 1 3

] ⊗ [

𝑥1𝑥2𝑥3] ∈ 𝒢0

(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] = [

𝜀𝜀𝜀]


[1 4 −11 0 63 1 3

] ⊗ [𝜀𝜀𝜀] = [

𝜀𝜀𝜀] ∈ 𝒢0

(3)

karena |𝐴| ∈ 𝒯 maka persamaan 𝐴 ⊗ 𝒙 ⊨ 𝜺 dalam aljabar supertropical 𝑅

mempunyai penyelesaian trivial. Dengan demikian penyelesaian tersebut

merupakan penyelesaian trivial di ℝmax . ◊

78

4.4.2 Penyelesaian 𝐴⊗ 𝒙 ⊨ 𝜺 dimana |𝑨| ∈ 𝓖𝟎 ≠ 𝜺 dalam Aljabar

Supertropical

Contoh 4.14.

Selesaikan 𝐴 ⊗𝒙 ⊨ 𝜺, jika 𝐴 = [1 2 34 1 52 2 2

] , 𝑥 = [

𝑥1𝑥2𝑥3]

sistem persamaan 𝐴⊗ 𝒙 ⊨ 𝜺 ⟺ 𝐴⊗ 𝒙 ∈ 𝒢0(3)

[1 2 34 1 52 2 2

]⊗ [

𝑥1𝑥2𝑥3] ∈ 𝒢0

(3)

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

adj(A) = [7 5 77 5 76 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

𝒙 = [776]


𝐴⊗ 𝒙 = [1 2 34 1 52 2 2

]⊗ [776] = [

9𝑣

11𝑣

9𝑣] ∈ 𝒢0

(3)

79

jika 𝒙 adalah kolom ke-2 dari Adj (𝐴), maka

𝒙 = [554

]


𝐴⊗ 𝒙 = [1 2 34 1 52 2 2

] ⊗ [554

] = [7𝑣

9𝑣

7𝑣] ∈ 𝒢0

(3)

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.

◊

81

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.

83

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”, arXiv :

1202.3615v1.

84

[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.

85

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].

mailto:[email protected]

PERSAMAAN LINEAR ATAS ALJABAR SUPERTROPICALrepository.its.ac.id/1229/2/1214201002-Master...

Documents

Transcript of PERSAMAAN LINEAR ATAS ALJABAR SUPERTROPICALrepository.its.ac.id/1229/2/1214201002-Master...