KEPERIODIKAN DARI PERPANGKATAN MATRIKS TEREDUKSI DALAM ALJABAR MAX-PLUS DAN APLIKASI PADA KELAS SIKLIK

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW

KEPERIODIKAN DARI PERPANGKATAN MATRIKS TEREDUKSI DALAM ALJABAR MAX-PLUS DAN APLIKASI PADA KELAS SIKLIK Venn Yan Ishak Ilwaru1, Dr. Subiono,MS2 1)

Mahasiswa Magister MIPA Matematika Institut Teknologi Sepuluh Nopember 2) Dosen MIPA Matematika Institut Teknologi Sepuluh Nopember [email protected] ABSTRAK k

Pada aljabar max-plus telah diketahui bahwa barisan pangkat A dalam aljabar max, dengan A adalah matriks persegi yang tereduksi, menjadi periodik setelah waktu transient terbatas T(A), dan periode akhir  sama dengan siklisitas graf kritis dari A. Dalam hubungan ini dipelajari masalah komputasi dari

n  n sebagai berikut: (1) diberikan k, hitung periodik pangkat Ar l dengan r  k (mod  ) dan r  T  A  . (2) diberikan x, dapatkan periodik akhir dari  A  x . Ide matriks persegi yang berukuran

utama adalah menggunakan penskalaan similaritas diagonal yang sesuai A  X penskalaan visualisasi. Untuk mempelajari peran dari kelas siklik pada graf kritis.

1

AX , yang disebut

Keywords: Kelas Siklik, Graf Kritis, Periodik Pangkat, Periodik akhir.

PENDAHULUAN Pada Aljabar max-plus banyak permasalahan yang muncul, sehingga permasalahan itu dapat diselesaikan dengan mendapatkan suatu solusi yang tepat. Dalam penyelesaiannya, dibutuhkan analisis atau dengan menggunakan komputasi. Aljabar max-plus sering digunakan untuk memodelkan suatu permasalahan seperti transportasi, manufacturing, penjadwalan, sistem antrian, lalu lintas dan sebagainya. Salah satu kegunaan dari pada aljabar max-plus yaitu dapat menyelesaikan dan mendapatkan suatu keperiodikan dari suatu permasalahan. Periodik yang dimaksud disini adalah periodik regime. Untuk mempelajari periodik regime, maka perlu dibahas visualisasi, matriks Booelan dan matriks pangkat. Sehingga dapat membantu dalam menyelesaiakan dan mendapatkan suatu periodik regime. Pada penelitian ini akan dibahas mengenai permasalahan yang diberikan oleh Sergei Sergeev (2009) yaitu menghitung periodik Pangkat A r dan mendapatkan perilaku periodik akhir dari A l  x serta mengaplikasikan ke kelas siklik pada graf kritis. Adapun tujuan dari penelitian ini adalah: 1. Dapat menghitung periodik pangkat A r dengan r  k mod   dan r  T  A jika k diketahui. 2. Dapat menemukan perilaku periodik akhir A l  x jika x diketahui. 3. Dapat mengaplikasikan ke kelas siklik pada graf kritis.









M22-1

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW BAHAN DAN METODE Dalam penulisan makalah ini bahan yang digunakan adalah dengan menggunakan studi literatur berupa buku-buku, jurnal dan lain-lain yang dapat digunakan untuk menunjang penulisan ini. Metode yang digunakan adalah dengan mengkaji teori-teori seperti definisi, proposisi dan teorema yang akan dipakai untuk menyelesaikan masalah keperiodikan. Adapun langkah-langkah pengerjaan dalam penelitian ini adalah sebagai berikut: 1. Membahas Keperiodikan Pada tahap ini, dibahas tentang keperiodikan suatu matriks persegi pada aljabar max-plus dengan cara mengkaji teori-teori sperti definisi dan teorema-teorema yang akan dipakai untuk menyelesaikan masalah periodik keperiodikan. 2. Menyelesaikan dan mendapatkan masalah periodik pangkat dan perilaku periodik akhir Pada tahap ini dibahas tentang penyelesaian suatu periodik pangkat A r dan mendapatkan suatu perilaku periodik akhir A l  x dengan menggunakan definisi dan teorema yang terkait. 3. Mengaplikasikan ke kelas siklik pada graph kritis Pada tahap ini, dibahas mengenai aplikasi dari pembahasan periodik regime ke kelas siklik pada graf kritis dengan memberikan contoh-contoh.





HASIL DAN DISKUSI PERIODISITAS DAN KOMPLEKSITAS Proyektor Spektral dan Matriks Periodesitas nn Untuk matriks A  Rmax yang tereduksi dan terdefinisi, sesuai dengan matriks Q  A  dengan

elemen-elemen: c

aij   aik* akj* , i, j  1,..., nc

(1)

k 1

Operator max-plus linear matriks Q  A  adalah proyektor spectral max-plus linear yang n berkaitan dengan A, dalam arti bahwa projek Rmax pada eigencone V  A  .

Oprator ini sangat berkaitan dengan masalah periodisitas. Q  A  disebut juga matriks orbital. Preposisi 1 n n Diberikan A  Rmax yang tereduksi dan terdefinisi dan diberikan semua komponen strongly connected (s.c.c)dari C  A  adalah primitive, maka terdapat bilangan bulat T  A  sehingga

Ar  Q  A  , untuk semua r  T  A  . Preposisi 2 n n Untuk matriks A  Rmax yang tereduksi dan terdefinisi, setiap kolom kritis (atau baris) dari

Q  A  adalah sama dengan korenspondensi kolom (atau baris) dari A*

Ketika C  A  mempunyai komponen inprimitif, sesuai dengan preposisi 1 bahwa semua

  adalah primitive, dimana 

komponen dari C A

adalah siklisitas dari C  A  . Oleh karena

itu, untuk setiap r yang cukup besar adalah kelipatan dari  , Ar adalah matriks dari proyektor spectral dalam eigencone dari A . Ini juga mengakibatkan bahwa untuk r yang cukup besar,

M22-2

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW

  dari  A  yakni

mempunyai Ar  Ar  . Jumlah r setelah dimulai disebut transient dari Ar dan dinotasikan dengan T  A  . Juga diketahui bahwa  adalah periode akhir bilangan bulat  sehingga A

r 

r

sedikitnya

 A untuk semua r  T  A  . r

Preposisi 3 n n Diberikan A  Rmax yang tereduksi dan terdefinisi. Baris dan kolom kritis dari Ar menjadi periodik untuk r  n 2 .

Sifat-sifat Periodik Pangkat Periodik pangkat dari matriks yang tereduksi dan terdefinisi dijelaskan dengan preposisi berikut Preposisi 4 n n Diberikan matriks A  Rmax yang tereduksi dan terdefinisi dan t  0 sehingga t  T  A  . Maka untuk setiap bilangan bulat l  0

ak .

t  l 

c

  aki  Ai. t

t  l 

i 1

Preposisi 5 Diberikan matriks

, a.k

t  l 

c

  aik  A.i t

i 1

t  l 

, 1 k  n

(2)

n n yang tereduksi dan terdefinisisi dan diberikan i, j  N c  A  A  Rmax

sedemikian sehingga i  l  j  , untuk 0  1   . 1. Terdapat t sedemikian sehingga untuk setiap r  n 2

aij

t  l 

A.ri  A.rjl , aij

t  l 

Arj .  Air. l

(3)

2. Jika matriks A adalah visualisasi maka untuk semua r  n 2

A.ri  A.rjl , Arj .  Air. l

(4)

Akibat 6 nn Diberikan A  Rmax dan r  n 2 . Semua baris dari matriks Ar dengan indeks yang sama dengan kelas siklik adalah sama satu sama yang lain dan berlaku untuk kolom. Preposisi 5 disebutkan bahwa untuk setiap matriks pangkat Ar untuk r  n 2 , kolom kritis atau baris kritis dapat diperoleh dari kolom kritis atau baris kritis dari Spektral Proyektor

Q  A  dengan permutasi himpunan dari kolom atau baris yang korenspondensi dengan kelas

siklik dari C  A  Preposisi 7 Semua matriks pangkat Ar untuk r  T  A  mempunyai kolom span yang sama, yang mana

 

eigencone-nya adalah V A .

  adalah kolom span akhir dari matriks A. dengan cara yang sama diperoleh baris span dari matriks A adalah V   A   . Cones dapat diperumum dengan kolom atau baris kritis dari kleene star  A  . Untuk basis dari cone ini, dapat diambil Preposisi 7 menjelaskan bahwa V A

T 



*

M22-3

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW

  ( ekuivalensi dengan Q  A  atau A

dari setiap himpunan kolom A

*



t

untuk t  T  A  ),

yang mengindikasikan bentuk himpunan minimal dari semua kelas siklik dari C  A  . nc nc Diambil t  T  A  . Untuk setiap l  0 , diberikan C    Rmax atau sebaliknya R    Rmax l

l

menjadi matriks yang diekstrak dari klom kritis dari At l atau sebaliknya dari baris kritis At l . Diberikan C : C  0 , R : R  0 . Dengan notasi ini dan dari preposisi 4 dan preposisi 5, n n maka dapat disimpulkan bahwa untuk visualisasi matriks tereduksi A  Rmax

At l  C l   R  C  R l 

(5)

   , R    A    R

C    C  A l

l

C

l

C

l

(6)

Persamaan (5) ternyata ekuivalensi dengan persamaan (2). Lebih lanjut i  l  j  jika dan hanya jika terdapat indeks p  i  dan s   j  sedemikina sehingga

 A   C

elemen

 p, s 

dari

l

adalah 1, dan semua baris dari R atau kolom dari C, dengan indeks yang sama dengan

kelas siklik adalah sama satu sama lain . Dengan menggabungkan persamaan (5) dan persamaan (6) maka diperoleh

  R

At l  C  A

C

l

(7)

Jika A tidak tervisualisasi tetapi terdefinisi tereduksi, maka persamaan (6) dan (7) dapat dituliskan. Diberikan B  X 1 AX tervisualisasi. Menerapkan penskalaan invers XBX 1 pada persamaan (7) (dimana B digantikan dengan A) maka diperoleh persamaan dari bentuk yang sama, dimana C dan R adalah matriks yang diekstrak dari kolom kritis atau sebaliknya baris dari

 

C c c yang didefinisikan dengan At dan A  digantikan dengan matriks A   aij   Rmax C

C

a , if  i, j   Ec  A  , aijC    ij i, j  c if  i, j   Ec  A  ,  0 Menyelesaiakan masalah keperiodikan dengan Matriks Persegi n n Diberikan A  Rmax dan   A   1 . t-attraction cone Attr  A, t  adalah max cone yang terdiri

dari semua vektor x, untuk yang terdapat bilangan bulat r sehingga Ar  x  Ar t  x dan hal ini juga berlaku untuk semua bilangan bulat yang lebih besar atau sama dengan r. Preposisi 8 Diberikan matriks A tereduksi dan terdefinisi. Sistem Ar  x  Ar t  x ekuivalensi dengan semua r  T  A  . Bukti: Diberikan x yang memenuhi As  x  As t  x untuk s  T  A  , maka juga akan memenuhi sistem ini untuk semua yang lebih besar s. karena periodisitas untuk semua k dari T  A   k  s terdapat l  s sehingga Ak  Al . Ak  x  Ak t  x juga memenuhi T  A   k  s

M22-4

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW Akibat 9

Attr  A, t   Attr  At ,1

Komponen dari Ar  x  Ar t  x dengan indeks pada N c  A   1,..., c disebut kritis dan subsistem dari komponen-komponen dengan indeks ini disebut subsistem kritis. Lemma 10 Diberikan matriks

A x A r

r t

A

tereduksi

dan

terdefinisi

dan

diberikan

r  T  A  . Maka

 x ekuivalensi dengan subsistem kritis.

Berikutnya diberikan batasan dalam menghitung kompleksitas dalam memutuskan apakah x  Attr  A, t  , seperti masalah-masalah yang lain yang dapat diformulasikan seperti di bahwah ini. P1. diberikan x, uji apakah x  Attr  A, t  P2. diberikan x: 0  k   , hitung periodik matriks pangkat Ar dimana r  k  mod   .





P3. diberikan x, hitung periodik akhir dari Ar  x, r  0 , yang berarti sedikitnya bilangan bulat  sedemikian sehingga A

r 

 x  A untuk semua r  T  A  . r

Teorema 11 n n Untuk setiap matriks A  Rmax yang tereduksi, maka masalah P1-P3 dapat diselesaikan pada

O  n3 log n  kali.

Bukti: Pertama perhatikan bahwa   A  dan vektor subeigen dapat dihitung dan mengidentifikasi

 

semua titik kritis yang tidak lebih dari O n3 operasi, yang dilakukan dengan algoritma FloydWarshall. Selanjutnya mengidentifikasi semua kelas siklik C  A  dengan kondensasi Balcer-

 

Veinott pada O n 2 operasi. Dengan preposisi 3, kolom kritis dan baris kritis menjadi periodik untuk r  n 2 . Dengan mengetahui kolom kritis dan baris kritis pada r '  T  A  , itu sudah cukup untuk menghitung

Ar untuk r  n 2 , yang dapat diselesaikan dengan O  log n  matriks persegi  A, A2 , A4 ,...





dan diperlukan O n3 log n kali dan mengikuti persamaan (3), untuk menerapkan permutasi

 

yang sesuai pada kelas siklik yang diperlukan O n 2 . Dengan lemma 10, P1 dapat diselesaikan

 

dengan verifikasi dari subsistem kritis dari Ar '  x  Ar ' t  x yang diperlukan O n 2 r

operasi. Dengan menggunakan bantuan persamaan (2), sisa submatriks non kritis dari A , untuk setiap r  T  A  sehingga r  k  mod   dapat dihitung pada O n3 . Ini adalah

 

penyelesaian untuk P2. Baris non kritis dari matriks A merupakan generalisasi dari baris kritis, periodik akhir dari Ar  x ditentukan dari komponen-konponen kritis. Untuk visualisasi matriks, diketahui







bahwa Air. t  Arj . untuk semua i, j sehingga i  t  j  . Ini berarti Ar  x

 A i

r t

 x

j

untuk i  t  j  , artinya bahwa untuk menentukan periode dibutuhkan hanya sub vektor dari

M22-5

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW

Ar  x untuk setiap sembarang r  n 2 . Untuk i  c dan r  n 2 , barisan

 A  x  , t  0 r

i

dapat direpresentasikan dengan barisan dari koordinat kritis dari A  x yang ditentukan oleh suatu permutasi pada kelas siklik   dari s.c.c, termasuk i. Untuk menghitung periode, dapat r

diambil contoh banyaknya   secara berurutan pada barisan dan periksa semua periode-periode yang mungkin, yang membutuhkan lebih dari  2 operasi. Periode dari Ar  x akan tampak

 

seperti l.c.m. pada periode ini. Semua operasi di atas tidak membutuhkan lebih dari O n3 kali. Ini adalah penyelesaian P3. KESIMPULAN Berdasarkan hasil dan pembahasan maka dapat disimpulkan bahwa:

1. Jika k diketahui maka dapat menghitung periodik pangkat A r dengan r  k mod   dan r  T  A

2. Jika x maka dapat ditemukan perilaku periodik akhir mengaplikasikan ke kelas siklik pada graf kritis.

A

l



x

serta dapat

M22-6

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW DAFTAR PUSTAKA [1] Bacelli, F., Cohen, G., Olsder, G. J., dan Quadrat, J. P. (2001), Synchronization and Linearity, John Wiley & Sons, New York. [2] C .H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, New Jersey, 1982 [3] Heidergott, Bernd. (2006), Max Plus Algebra And Queues, Vrije Universiteit. Department of Econometrics and Operations Research De Boelelaan 1105, 1081 HV Amsterdam, The Netherlands. [4] P. Butkoviˇc, R.A. Cuninghame-Green, On matrix powers in max-algebra, Linear Algebra Appl. [5] Novitasari, Ratna. (2008), Analisis Masalah Generator Dari Possible Dan Universal Eigenvector Pada Matriks Interval Dalam Aljabar Max-Plus, Tesis, Institut Teknologi Sepuluh Nopember, Surabaya [6] R.A. Brualdi, H.J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1991 [7] Subiono. (2009). Aljabar Max-Plus, Institut Teknologi Sepuluh Nopember, Surabaya [8] S. Sergeev,(2009) Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes, Linear Algebra Appl. [9] S. Sergeev, H. Schneider, P. Butkovic,(1992) On visualization scaling, subeigenvectors and Kleene stars in max algebra, Linear Algebra Appl.

M22-7