KARAKTERISASI PENYELESAIAN SISTEM KESETIMBANGAN LINEAR DITINJAU DARI MATRIKS ATAS ALJABAR MAKS-PLUS TERSIMETRI

GREGORIA ARIYANTI, Dr. rer. nat. Ari Suparwanto, M.Si.; Dr. Budi Surodjo, M.Si.

2018 | Disertasi | S3 Matematika

Aljabar maks-plus adalah suatu struktur aljabar yang terdiri dari himpunan $\mathbb{R}_{\epsilon} = \mathbb{R}\cup \{\epsilon\}$ dengan $\epsilon :=-\infty$, dilengkapi operasi maksimum dan operasi penjumlahan. Elemen di dalam aljabar maks-plus yang bukan $\epsilon$ tidak mempunyai invers terhadap operasi penjumlahan. Untuk mengatasi hal tersebut, maka aljabar maks-plus dikembangkan menjadi struktur yang lebih luas yang disebut aljabar maks-plus tersimetri. Di dalam aljabar maks-plus tersimetri, didefinisikan elemen invers terhadap operasi penjumlahan, sehingga dapat didefinisikan determinan suatu matriks atas aljabar maks-plus tersimetri. Hal ini merupakan kelebihan dari aljabar maks-plus tersimetri, dibandingkan dengan aljabar maks-plus. Tujuan utama penelitian ini adalah ingin mengetahui karakterisasi penyelesaian sistem kesetimbangan linear ditinjau dari matriks atas aljabar maks-plus tersimetri. Adapun tujuan secara khusus yaitu mengeksplorasi matriks invertibel atas aljabar maks-plus tersimetri, menemukan syarat perlu atau syarat cukup untuk penyelesaian sistem kesetimbangan linear $A\otimes x \nabla b$ dengan $A$ matriks bukan persegi ($A\in M_{m \times n}(\mathbb{S})$ dengan $m \neq n$), menentukan nilai eigen dari matriks atas aljabar maks-plus tersimetri, dan mengembangkan dia-gonalisasi suatu matriks atas aljabar maks-plus tersimetri.\\ \indent Untuk mengembangkan karakteristik matriks invertibel, dilakukan melalui mengeksplorasi matriks dengan mengacu pada sifat elemen di dalam aljabar maks-plus tersimetri yang memiliki invers terhadap operasi $\oplus$, yang berakibat dapat didefini-sikannya determinan. Relasi yang berlaku pada aljabar maks-plus tersimetri adalah relasi kesetimbangan, sehingga sistem linear atas aljabar maks-plus tersimetri tidak berbentuk persamaan tetapi berupa kesetimbangan. Oleh karena itu, sistem linear atas aljabar maks-plus tersimetri disebut sistem kesetimbangan linear. Untuk memba-ngun syarat perlu dan cukup penyelesaian sistem kesetimbangan linear, dilakukan dengan meninjau matriks penyusun sistem kesetimbangan linear tersebut. Penyelesaian yang dimaksud adalah penyelesaian atas himpunan elemen positif, himpunan elemen negatif, dan himpunan elemen setimbang. Suatu matriks pada sistem kesetimbangan linear dapat difaktorkan dan salah satu proses faktorisasi matriks adalah diagonalisasi. Proses diagonalisasi matriks dapat dilakukan setelah ditentukannya nilai eigen dari matriks tersebut.\\ \indent Dari hasil penelitian diperoleh bahwa suatu matriks $A$ atas aljabar maks-plus tersimetri invertibel jika dan hanya jika $det^{+}A \ominus det^{-}A \in \mathbb{S}-\mathbb{S}^{\bullet}$. Untuk matriks $X$ yang memenuhi $A \otimes X \otimes A \nabla A$, sistem kesetimbangan linear $A\otimes x \nabla b$ mempu-nyai penyelesaian, yaitu $x = X \otimes b \oplus (E \ominus X \otimes A)\otimes h$ dengan $h$ sebarang, jika dan hanya jika $A \otimes X \otimes b \nabla b$. Untuk menentukan nilai eigen suatu matriks atas aljabar maks-plus tersimetri, tidak sesederhana seperti menentukan nilai eigen dalam aljabar konvensional. Oleh karena itu, diperlukan suatu langkah menentukan nilai eigen dengan menggunakan alat yang disebut Masalah Linear Komplementer Diperluas (\emph{Extended Linear Complementarity Problem} atau \emph{ELCP}). Persamaan karakteristik yang diperoleh dari suatu matriks atas aljabar maks-plus tersimetri dapat dibawa ke sistem kesetimbangan linear melalui \emph{ELCP}. Akar persamaan karakteristik yang diperoleh akan merupakan penyelesaian dari sistem kesetimbangan linear, yang selanjutnya merupakan nilai eigen dari matriks tersebut. \\

Max-plus algebra is a structure of algebra consisting of the set $\mathbb{R}_{\epsilon} = \mathbb{R}\cup \{\epsilon\}$, including the operations of maximum and addition. Elements of the max-plus algebra which does not $\epsilon$ have no inverse of addition. To complete the problem, so max-plus algebra is extended , it is called the symmetrized max plus algebra. In the symmetrized max plus algebra, we define the inverse of the operations $\oplus$, so that the determinant of a matrix over the symmetrized max plus algebra can be defined. This is an excess of the symmetrized max plus algebra, compared to the max plus algebra. The main purpose of this study is to know the characterization of the solution in the linear balance system. The specific purpose is to explore the invertible matrix over the symmetrized max-plus algebra, to construct the necessary conditions or sufficient conditions of solution of the linear balance system with $m \times n$ matrix, to determine the eigenvalues of the matrix over the symmetrized max-plus algebra, and to develop the diagonalization of a matrix over the symmetrized max-plus algebra.\\ \indent To develop the characteristics of the invertible matrix, it is carried through explores the matrix by referring to the properties of elements in the symmetrized max-plus algebra that has an inverse to the $\oplus$ operation, which result to the determinant. Relation that applies to the symmetrized max plus algebra is a relation of balance. Therefore, the linear systems over the symmetrized max plus algebra is called the li-near balance systems. To construct the necessary and sufficient conditions of solution of the linear balance systems, they are carried out by reviewing the matrix of the compilers of the linear balance system. Solution to this mean can be classified into three groups, namely the set of positive elements, the set of negative elements, and the set of elements in balance. A matrix of the linear balance systems can be factored into a product of matrices and the factorization process of matrix is called diagonalization. Matrix diagonalization process can be performed after it determines the eigenvalues of the matrix.\\ \indent From the results of the study it can be conclude that a matrix $A$ is invertible over the symmetrized max-plus algebra if and only if $det^{+} A \ominus det^{-}A \in \mathbb{S}- \mathbb{S}^{\bullet}$. For a $X$ matrix that satisfies $A \otimes X \otimes A \nabla A$, the linear balance system $A \otimes x \nabla b$ has a solution, i.e. $x = X \otimes b \oplus (E \ominus X \otimes A) \otimes h$ with arbitrary $h$, if and only if $A \otimes X \otimes b \nabla b$. To determine the eigenvalues of a matrix over the symmetrized max plus algebra, it is not as simple as determining the eigenvalues in conventional algebra. Therefore, it will be developed a step to determine the eigenvalues by using a tool called the Extended Linear Complementarity Problem or ELCP. The characteristic equation obtained from a matrix on the symmetrized max plus algebra can be changed into the linear balance systems through ELCP. The roots of the characteristic equation obtained will be the solution of the linear balance systems, which can be the eigenvalue of the matrix.\\

Kata Kunci : aljabar maks-plus tersimetri, sistem kesetimbangan linear, nilai eigen, diagonalisasi.