Solusi Maksimal dari Sistem Linear Dua Sisi atas Aljabar Max-Min

Zakia Nur Ramadhani Putri, Dr.rer.nat. Ari Suparwanto, M.Si.; Dr. Sutopo, S.Si., M.Si.

2026 | Tesis | S2 Matematika

Aljabar Max-min adalah himpunan $\overline{\mathbb{R}} = \mathbb{R} \cup \{-\infty,+ \infty\}$ yang dilengkapi dengan dua operasi biner, maksimum $(\oplus)$ dan minimum $(\otimes)$. Struktur $(\overline{\mathbb{R}}, \oplus, \otimes)$ merupakan semiring komutatif idempoten. Tesis ini membahas mengenai solusi maksimal dari sistem linear dua sisi atas aljabar max-min dalam bentuk $A\otimes x=B\otimes x$. Pembahasan dilakukan secara bertahap, dimulai dari kasus matriks $A$ dan $B$ berukuran $1\times n$ dengan $x\in\overline{\mathbb{R}}^n$ dibagi menjadi tiga kasus: tanpa diberikan batasan, dengan diberikan batas atas, dan dengan diberikan batas bawah. Selanjutnya, kasus matriks berukuran $1\times n$ diperumum untuk kasus matriks $A$ dan $B$ berukuran $m\times n$. Hasil penelitian pada tesis ini berupa rumus dan algoritma untuk menentukan solusi maksimal dari sistem linear dua sisi atas aljabar max-min. Disajikan juga implementasi Python dari algoritma yang diperoleh, serta contoh penerapan pada jaringan distribusi logistik untuk menunjukkan bagaimana model dapat diterapkan.

Max-min algebra is a set $\overline{\mathbb{R}} = \mathbb{R} \cup \{-\infty,+ \infty\}$ equipped with two binary operations, maximum $(\oplus)$ and minimum $(\otimes)$. The structure $(\overline{\mathbb{R}}, \oplus, \otimes)$ is an idempotent commutative semiring. This research discusses the determination of the maximal solution of two-sided systems of linear equations in the form of $A \otimes x = B \otimes x$. The discussion is carried out gradually, starting from the case where matrices $A$ and $B$ are of size $1 \times n$ for variables $x \in \overline{\mathbb{R}}^n$ under three conditions: unconstrained, with a given upper bound, and with a given lower bound. Furthermore, these results are generalized for the case of matrices $A$ and $B$ of size $m \times n$. The results of this research are the mathematical formulas and an algorithm to calculate the maximal solution of the two-sided systems of linear equations. A Python implementation of the algorithm is provided, an illustrative example on a logistics distribution network is presented to demonstrate how the model is applied.

Kata Kunci : aljabar max-min, sistem linear dua sisi, solusi maksimal, algoritma