JMP : Volume 4 Nomor 2, Desember 2012, hal. 289 - 297
SEMI RING POLINOM ATAS ALJABAR MAX-PLUS Suroto Prodi Matematika, Jurusan MIPA, Fakultas Sains dan Teknik Universitas Jenderal Soedirman e-mail :
[email protected]
ABSTRACT. In this paper we define polynomials over a max plus algebra. Furthermore we prove that the set of such polynomials is a semi ring. Key words: semi ring, max-plus algebra, polynomial ABSTRAK. Pada makalah ini didefinisikan polinom atas aljabar max-plus. Lebih lanjut dibuktikan bahwa himpunan semua polinom tersebut merupakan semi ring. Kata kunci: semi ring, aljabar max-plus, polinom
1. PENDAHULUAN Misalkan π adalah suatu himpunan tidak kosong. Himpunan π yang dilengkapi dengan suatu operasi biner yang bersifat assosiatif dinamakan semi grup (Fraelligh, 2000). Menurut Golan (2005), himpunan π yang dilengkapi dengan dua buah operasi biner yakni penjumlahan (dinotasikan +) dan pergandaan (dinotasikan Γ) dinamakan semi ring apabila memenuhi: 1.
(π, +) merupakan semi grup komutatif dengan elemen netral.
2.
(π,Γ) merupakan semi grup dengan elemen satuan.
3.
Elemen netral merupakan elemen penyerap terhadap operasi Γ.
4.
Operasi + distributif terhadap operasi Γ.
Semi ring π dikatakan idempoten apabila untuk setiap π β π berlaku π + π = π dan dikatakan komutatif apabila operasi pergandaannya bersifat komutatif (Mora, dkk, 2009). Suatu semi ring komutatif yang setiap elemen tak netralnya mempunyai invers terhadap operasi pergandaan dinamakan semi lapangan. Misalkan diberikan struktur aljabar βmax β β βͺ {ββ} dengan β adalah himpunan semua bilangan riil, yang dilengkapi dengan dua buah operasi biner yakni operasi penjumlahan dan pergandaan. Aljabar max-plus merupakan struktur aljabar
290
Suroto
yang terbentuk dari βmax dengan dilengkapi operasi βmaximumβ sebagai operasi penjumlahannya dan operasi βplusβ sebagai operasi pergandaannya, yakni π β π = maximum (π, π) dan π β π = π + π untuk setiap a, b β βmax (Farlow, 2009). Elemen identitas terhadap operasi penjumlahannya adalah ββ dan terhadap operasi pergandaannya adalah 0. Himpunan βmax yang dilengkapi dengan operasi penjumlahan dan pergandaan tersebut merupakan semi ring, dan selanjutnya dinamakan semi ring max-plus (Akian, dkk., 2006). Menurut Bacelli, dkk (2001), semi ring max-plus tersebut juga merupakan semi lapangan idempoten. Pembahasan aljabar max-plus bisa diperluas pada kajian matriks yang dilakukan dengan cara mendefinisikan matriks dengan entri-entrinya adalah elemen pada aljabar max-plus. Kajian mengenai matriks atas aljabar max plus telah dilakukan oleh Rudhito, dkk (2008) dan diperoleh bahwa matriks atas aljabar maxplus terhadap operasi penjumlahannya merupakan semi grup komutatif idempoten, sedangkan terhadap operasi pergandaannya merupakan semi grup. Telah diketahui sebelumnya bahwa aljabar max-plus merupakan semi lapangan idempoten. Pada makalah ini, pembahasan aljabar max-plus diperluas pada kajian polinom dengan cara membentuk polinom yang koefisiennya adalah elemenelemen pada aljabar max-plus. Selanjutnya, struktur aljabar max-plus dan sifatsifatnya sebagai semi lapangan akan digunakan untuk membuktikan beberapa sifat yang berkaitan dengan polinom yang dibentuk dari aljabar max-plus tersebut.
2. SEMIRING POLINOM ATAS ALJABAR MAX-PLUS Bagian ini merupakan bagian utama pada penulisan makalah ini. Terlebih dahulu didefinisikan polinomial dengan setiap koefisiennya adalah elemen-elemen pada aljabar max-plus, seperti dinyatakan pada definisi berikut: Definisi 2.1 Misalkan βmax adalah aljabar max-plus maka polinom yang berbentuk π
π(π₯) = β ππ π₯ π = π0 + π1 π₯ + β― + ππ π₯ π π=0
Semi Ring Polinom Atas Aljabar Max-Plus
291
dengan π0 , π1 , π2 , β¦ , ππ ββmax dinamakan polinom atas aljabar max-plus dengan indeterminate x. Untuk selanjutnya, himpunan semua polinom atas aljabar max-plus dinotasikan dengan βmax[x], yakni βmax [x] = {π0 + π1 π₯ + β― + ππ π₯ π |π0 , π1 , β¦ , ππ β βmax }. Dua buah polinom di βmax [x] dikatakan sama apabila untuk setiap koefisien yang letaknya bersesuaian nilainya sama, yaitu π0 + π1 π₯ + β― + ππ π₯ π = π0 + π1 π₯ + β― + ππ π₯ π jika ππ = ππ untuk setiap π β₯ 0. Definisi 2.2 Untuk setiap π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π di βmax [x] , didefinisikan operasi penjumlahan polinom seperti berikut: (π0 + π1 π₯ + β― + ππ π₯ π ) + (π0 + π1 π₯ + β― + ππ π₯ π ) = π0 + π1 π₯ + β― + ππ π₯ π (2.1) dengan ππ = ππ β ππ = πππ₯(ππ , ππ ) untuk setiap i. Terlebih dahulu ditunjukkan bahwa operasi penjumlahan pada persamaan (2.1) terdefinisi dengan baik (well defined) di βmax [x]. Misalkan polinomial π0 + π1 π₯ + β― + ππ π₯ π ,
π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π , β0 + β1 π₯ + β― + βπ π₯ π
di βmax [x]. Jika π0 + π1 π₯ + β― + ππ π₯ π = π0 + π1 π₯ + β― + ππ π₯ π π0 + π1 π₯ + β― + ππ π₯ π = β0 + β1 π₯ + β― + βπ π₯ π maka (π0 + π1 π₯ + β― + ππ π₯ π ) + (π0 + π1 π₯ + β― + ππ π₯ π ) = (π0 β π0 ) + (π1 β π1 )π₯ + β― + (ππ β ππ )π₯ π = (π0 β β0 ) + (π1 β β1 )π₯ + β― + (ππ β βπ )π₯ π = (π0 + π1 π₯ + β― + ππ π₯ π ) + (β0 + β1 π₯ + β― + βπ π₯ π ).
292
Suroto
Dengan demikian, operasi penjumlahan pada βmax [x] terdefinisi dengan baik (well defined). Definisi 2.3 Untuk setiap π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π di βmax [x] , didefinisikan operasi penjumlahan polinom seperti berikut: (π0 + π1 π₯ + β― + ππ π₯ π ) Γ (π0 + π1 π₯ + β― + ππ π₯ π ) = π0 + π1 π₯ + β― + ππ+π π₯ π+π (2.2) dengan ππ = βππ=0 ππ ππβπ = (π0 β ππ ) β (π1 β ππβ1 ) β β¦ β (ππβ1 β π1 ) β (ππ β π0 ) = πππ₯((π0 + ππ ), (π1 + ππβ1 ), β¦ , (ππβ1 + π1 ), (ππ + π0 )) Secara analog dengan operasi penjumlahan pada βmax [x], diperoleh bahwa operasi pergandaan pada βmax [x] juga terdefinisi dengan baik (well defined). Sebelumnya sudah dijelaskan tentang pendefinisian operasi penjumlahan dan pergandaan pada βmax [x] yang terdefinisi dengan baik. Selanjutnya diperoleh bahwa βmax [x] terhadap operasi penjumlahan pada persamaan (2.1) memenuhi aksiomaaksioma semigrup, seperti dinyatakan pada proposisi berikut: Proposisi 2.1 (βmax [x], +) adalah semi grup komutatif dengan elemen netral. Bukti. Untuk setiap π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π polinom-polinom di βmax [x] berlaku : i. (π0 + π1 π₯ + β― + ππ π₯ π ) + (π0 + π1 π₯ + β― + ππ π₯ π ) = π‘0 + π‘1 π₯ + β― + π‘π π₯ π dengan π‘π = ππ β ππ , untuk setiap i. Karena βmax adalah semi lapangan, maka berlaku π‘π = ππ β ππ adalah elemen di βmax. Sehingga π‘0 + π‘1 π₯ + β― + π‘π π₯ π merupakan polinom di βmax [x]. Dengan demikian, operasi penjumlahan tertutup pada βmax [x].
Semi Ring Polinom Atas Aljabar Max-Plus
293
ii. ((π0 + π1 π₯ + β― + ππ π₯ π ) + ( π0 + π1 π₯ + β― + ππ π₯ π )) + ( π0 + π1 π₯ + β― + ππ π₯ π ) = π0 + π1 π₯ + β― + ππ π₯ π , dengan ππ = (ππ β ππ ) β ππ untuk setiap i. Karena βmax adalah semi lapangan, maka berlaku (ππ β ππ ) β ππ = ππ β (ππ β ππ ) untuk setiap i. Dari sini diperoleh bahwa ((π0 + π1 π₯ + β― + ππ π₯ π ) + ( π0 + π1 π₯ + β― + ππ π₯ π )) + ( π0 + π1 π₯ + β― + ππ π₯ π ) = (π0 + π1 π₯ + β― + ππ π₯ π ) + (( π0 + π1 π₯ + β― + ππ π₯ π ) + ( π0 + π1 π₯ + β― + ππ π₯ π )). Dengan demikian, operasi penjumlahan bersifat assosiatif di βmax [x]. iii. (π0 + π1 π₯ + β― + ππ π₯ π ) + (π0 + π1 π₯ + β― + ππ π₯ π ) = π‘0 + π‘1 π₯ + β― + π‘π π₯ π dengan π‘π = ππ β ππ , untuk setiap i. Karena βmax adalah semi lapangan, maka berlaku ππ β ππ = ππ β ππ untuk setiap i. Dengan demikian diperoleh bahwa (π0 + π1 π₯ + β― + ππ π₯ π ) + (π0 + π1 π₯ + β― + ππ π₯ π ) = (π0 + π1 π₯ + β― + ππ π₯ π ) + (π0 + π1 π₯ + β― + ππ π₯ π ) sehingga operasi penjumlahan bersifat komutatif di βmax [x]. iv. Polinom netral didefinisikan sebagai polinom dengan semua koefisiennya adalah elemen netral pada βmax yakni ββ. Polinom netral ini mempunyai bentuk π0 + π1 π₯ + β― + ππ π₯ π dengan ππ = ββ, untuk setiap i. Polinomial ini merupakan elemen identitas di βmax [x] terhadap operasi penjumlahan. Dengan demikian, eksistensi elemen netral pada βmax [x] terpenuhi. Untuk selanjutnya, polinom netral cukup ditulis 0(π₯).
294
Suroto
Dari uraian di atas, terbukti bahwa βmax [x] terhadap operasi penjumlahan adalah semi grup komutatif dengan elemen netral. β Selain itu, diperoleh bahwa βmax [x] terhadap operasi pergandaan pada persamaan (2.2) juga memenuhi aksioma-aksioma semigrup, seperti dinyatakan pada proposisi berikut: Proposisi 2.2 (βmax [x],Γ) adalah semi grup dengan elemen satuan. Bukti. Untuk setiap π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π polinom-polinom di βmax [x] berlaku : i. (π0 + π1 π₯ + β― + ππ π₯ π ) Γ (π0 + π1 π₯ + β― + ππ π₯ π ) = π‘0 + π‘1 π₯ + β― + π‘π π₯ π dengan π‘π = βππ=0 ππ ππβπ . Karena
βmax adalah semi lapangan, maka π‘π =
βππ=0 ππ ππβπ adalah elemen pada βmax . Jadi π‘0 + π‘1 π₯ + β― + π‘π π₯ π adalah polinom di βmax [x]. Dengan demikian, operasi pergandaan tertutup di βmax [x]. ii. ((π0 + π1 π₯ + β― + ππ π₯ π ) Γ ( π0 + π1 π₯ + β― + ππ π₯ π )) Γ ( π0 + π1 π₯ + β― + ππ π₯ π ) π π π = ((βππ=0 ππ π₯ π ) Γ (βπ π=0 ππ π₯ )) Γ (βπ=0 ππ π₯ ) π π π π = [βπ+π π=0 (βπ=0 ππ ππβπ )π₯ ] Γ (βπ=0 ππ π₯ ) π
= βπ+π+π [βππ=0(βπ=0 ππ ππβπ )ππ ]π₯ π π=0 = βπ+π+π (βπ+π+π=π ππ ππ ππ )π₯ π π=0 πβπ
= βπ+π+π [βππ=0 ππ (βπ=0 ππ ππβπβπ )]π₯ π π=0 π π = (βππ=0 ππ π₯ π ) Γ [βπ+π π=0 (βπ=0 ππ ππβπ ) π₯ ] π π π = (βππ=0 ππ π₯ π ) Γ ((βπ π=0 ππ π₯ ) Γ (βπ=0 ππ π₯ ))
Semi Ring Polinom Atas Aljabar Max-Plus
295
= (π0 + π1 π₯ + β― + ππ π₯ π ) Γ (( π0 + π1 π₯ + β― + ππ π₯ π ) Γ ( π0 + π1 π₯ + β― + ππ π₯ π )) Dengan demikian operasi pergandaan bersifat assosiatif di βmax [x] iii. Polinom satuan pada βmax [x] didefinisikan sebagai polinomial yang berbentuk π0 + π1 π₯ + β― + ππ π₯ π dengan π0 adalah elemen satuan di βmax yakni 0 dan ππ adalah elemen netral pada βmax yakni ββ untuk setiap π β 0. Polinom ini merupakan elemen identitas di βmax [x] terhadap operasi pergandaan. Dengan demikian, eksistensi elemen satuan pada βmax [x] terpenuhi. Untuk selanjutnya, elemen satuan pada βmax [x] dinotasikan dengan 1(π₯). Dari uraian tersebut di atas, terbukti bahwa βmax [x] dengan operasi pergandaan adalah semi grup dengan elemen satuan. β Selanjutnya dari hasil yang diperoleh pada Proposisi 2.1 dan Proposisi 2.2 dapat ditunjukkan bahwa βmax [x] terhadap operasi penjumlahan dan pergandaan pada persamaan (2.1) dan (2.2) adalah semi ring, seperti yang dinyatakan pada proposisi berikut yang merupakan hasil utama pada paper ini. Proposisi 2.3 (βmax [x], +,Γ) adalah semi ring. Bukti. Sebelumnya sudah diketahui bahwa βmax merupakan semi lapangan, sehingga elemen netral pada βmax merupakan elemen penyerap terhadap operasi pergandaan, yakni π β ββ = ββ β π = ββ untuk setiap a β βmax. Karena ββ adalah elemen penyerap pada βmax, maka untuk setiap polinom π0 + π1 π₯ + β― + ππ π₯ π di βmax [x] berlaku 0(π₯) Γ ( π0 + π1 π₯ + β― + ππ π₯ π ) = 0(π₯) Γ ( π0 + π1 π₯ + β― + ππ π₯ π ) = 0(π₯).
296
Suroto
Dengan demikian, elemen netral pada βmax [x] yakni 0(π₯) merupakan elemen penyerap terhadap operasi pergandaan. Selanjutnya, untuk setiap polinom π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π , π0 + π1 π₯ + β― + ππ π₯ π di βmax [x] berlaku [(π0 + π1 π₯ + β― + ππ π₯ π ) + ( π0 + π1 π₯ + β― + ππ π₯ π )] Γ ( π0 + π1 π₯ + β― + ππ π₯ π ) π π π = ((βππ=0 ππ π₯ π ) + (βπ π=0 ππ π₯ )) Γ (βπ=0 ππ π₯ )
= (βππ=0(ππ β ππ )π₯ π ) Γ (βππ=0 ππ π₯ π ) π π π = ((βππ=0 ππ π₯ π ) Γ (βππ=0 ππ π₯ π )) + ((βπ π=0 ππ π₯ ) Γ (βπ=0 ππ π₯ ))
= [(π0 + π1 π₯ + β― + ππ π₯ π ) Γ ( π0 + π1 π₯ + β― + ππ π₯ π )] +[(π0 + π1 π₯ + β― + ππ π₯ π ) Γ ( π0 + π1 π₯ + β¦ + ππ π₯ π )] Secara analog diperoleh bahwa ( π0 + π1 π₯ + β― + ππ π₯ π ) Γ [(π0 + π1 π₯ + β― + ππ π₯ π ) + ( π0 + π1 π₯ + β― + ππ π₯ π )] = [( π0 + π1 π₯ + β― + ππ π₯ π ) Γ (π0 + π1 π₯ + β― + ππ π₯ π )] +[( π0 + π1 π₯ + β― + ππ π₯ π ) Γ ( π0 + π1 π₯ + β― + ππ π₯ π )] Jadi operasi penjumlahan distributif terhadap operasi pergandaan. Karena (βmax [x], +) adalah semi grup komutatif dengan elemen netral, (βmax [x],Γ) adalah semi grup dengan elemen satuan, elemen netral pada βmax [x] merupakan elemen penyerap terhadap operasi pergandaan, dan operasi penjumlahan distributif terhadap operasi pergandaan, maka terbukti bahwa (βmax [x], +,Γ) adalah semi ring. β Untuk selanjutnya, semi ring (βmax [x], +,Γ) ini dinamakan semi ring polinomial atas aljabar max-plus.
Semi Ring Polinom Atas Aljabar Max-Plus
297
3. KESIMPULAN Perluasan kajian aljabar max-plus dapat dilakukan pada kajian polinom yang dilakukan dengan cara mendefinisikan polinom dengan koefisiennya adalah elemenelemen pada aljabar max-plus. Polinom yang dibentuk ini selanjutnya dinamakan sebagai polinom atas aljabar max-plus. Himpunan semua polinom atas aljabar maxplus yang dilengkapi dengan operasi penjumlahan polinomial merupakan semi grup komutatif dengan elemen netral, sedangkan dengan operasi pergandaan polinomial merupakan semi grup dengan elemen satuan. Lebih lanjut, himpunan semua polinomial atas aljabar max-plus ini merupakan semi ring. Penelitian lanjut dapat dilakukan untuk semi modul atas semiring polinomial atas aljabar max-plus. 4. DAFTAR PUSTAKA Akian, M., Bapat, R., and Gaubert, S. (2006). Max-Plus Algebra. Chapman and Hall Bacelli, F., Cohen, G., Olsder, G.J., and Quadrat, J.P. (2001). Synchronization and Linearity. An Algebra for Discrete Event Systems. John Wiley & Sons. New York Farlow, K.G. (2009). Max-Plus Algebra. Masterβs Thesis. Virginia Polytechnic Institute and State University Fraleigh, J.B. (2000). A First Course in Abstract Algebra. Addison-Wesley Publising Company, Inc. New York Golan, J.S. (2005). Some Recent Apllications of Semiring Theory. National Cheng Kung University, Tainan. Mora, W., Wasanawichit, A. , and Kemprasit, Y. (2009). Invertible Matrices over Idempotent Semirings. Chamchuri Journal of Mathematics, Vol 1 Number 2, (55-61) Rudhito, A.M., Wahyuni, S. , Suparwanto, A., dan Susilo, F. (2008). Matriks atas Aljabar Max-Plus Interval. Jurnal Natur Indonesia 13(2), Februari 2011 (9499)