PENYELESAIAN SISTEM DUA SISI DALAM ALJABAR MAX-PLUS

PENYELESAIAN SISTEM DUA SISI DALAM ALJABAR MAX-PLUS 1

Ratna Novitasari, 2Subiono 1 Jurusan Matematika FMIPA Universitas Diponegoro 2 Jurusan Matematika FMIPA Institut Teknologi Sepuluh Nopember e-mail : 1 [email protected], 2 [email protected] Abstrak. Dalam penelitian ini, sistem A  x  B  y akan diselesaikan dengan menggunakan iterasi. Adapun metode yang digunakan adalah metode alternatif. Selanjutnya, metode alternatif ini digunakan untuk menyelesaikan sistem dua sisi A  x  B  x . Kemudian diberikan sistem dua sisi dengan syarat khusus, yaitu C  y  D  y , dengan cij  d ij untuk setiap i  N dan j M yang akan diselesaikan dengan menggunakan iterasi. Keywords: Aljabar max-plus, sistem dua sisi.

1. Pendahuluan

Banyak penelitian yang telah membahas mengenai penyelesaian sistem dua sisi, antara lain Stepping Stone Method (Butkovic, 2006), Metode Alternatif (Cunninghame-Green, 2003) dan yang membandingkan kedua metode tersebut (Aminu, 2008). Pada penelitian ini, akan dibahas mengenai masalah penyelesaian dari sistem A  x  B  y , sistem dua sisi secara umum A  x  B  x dan sistem dua sisi dengan syarat khusus C  y  D  y , dengan cij  d ij untuk setiap i  N dan j  M, menggunakan iterasi. Untuk menentukan nilai komputasi digunakan toolbox Aljabar Max-Plus dengan program Scilab–4.1.2.

2. Aljabar Max-Plus

def

def

Didefinisikan     dan e  0 . Himpunan Rmaks adalah himpunan R    , dimana R adalah himpunan bilangan riil. Definisi dari struktur Aljabar dari Rmaks dijelaskan dalam definisi berikut ini: Definisi 1 Struktur aljabar Rmaks (Bacelli dkk., 1992, hal. 102) Simbol Rmaks menyatakan himpunan R    dengan dua operasi biner yaitu maksimum yang dinotasikan  dan penjumlahan yang dinotasikan  .

1

Untuk setiap a, b  Rmaks, didefinisikan operasi  def

dan



adalah

def

a  b  maks a, b  dan a  b  a  b . Sehingga untuk setiap a  Rmaks dan  ,

didapatkan a      a  a dan a      a   . Himpunan Rmaks dengan operasi  dan  disebut Aljabar Max-Plus dan dinyatakan dengan R = (Rmaks,  ,  ,  , e). m Himpunan matriks di dalam Aljabar Max-Plus dinyatakan dengan R nmak s , dimana m n, m  N. Didefinisikan n  1,2, , n. Elemen dari matriks A  R nmak s pada

baris ke i dan kolom ke j dinyatakan dengan aij atau Aij , untuk i  n dan js m .  a11  a Matriks A sebagaimana biasa dapat ditulis dengan A   21   a  n1

a12 a 22  an2

 a1m    a2m  .      a nm 

m Operasi penjumlahan matriks A, B  R nmak s , dinotasikan dengan A  B,

didefinisikan

A  Bij

 a ij  bij  maks a ij , bij , dimana i  n dan j  m .

m Adapun operasi perkalian A  R nmak s dengan skalar   R maks , didefinisikan oleh

  A    Aij    aij , dengan i  n dan j  m . m Tranpose dari matriks A  R nmak s

A  T

ij

dinotasikan AT, didefinisikan sebagai

 a ji , untuk i  n dan j  m .

Adapun definisi eigenvalue dan eigenvector dalam Aljabar Max-Plus diberikan sebagai berikut: Definisi 2 (Heidergott dkk., 2006) n Misalkan A  R nmak s adalah matriks bujur sangkar. Jika   R maks adalah sebuah

skalar dan v  R nmaks adalah sebuah vektor yang memuat minimal satu elemen yang berhingga sehingga memenuhi A  v    v , maka  disebut eigenvalue dari matriks A dan v adalah eigenvector dari matriks A yang bersesuaian dengan eigenvalue . Untuk mendapatkan eigenvalue dan eigenvector dari suatu matriks dalam Aljabar Max-Plus digunakan algoritma maxalgol (Subiono, 2007).

2

3. Penyelesaian Sistem Dua Sisi

Persamaan linear Ax = b dalam Aljabar Max-Plus ditulis A  x  b . Matriks n m A  Rmaks dan b  R n . Karena  berarti maksimum, maka didapatkan A  x  b ,

sehingga untuk setiap i  n dan ,j  m dalam aljabar biasa menjadi: aij  x j  bi ,  x j  bi  aij ,  x j  min bi  aij , i  n,   x j  maks bi  aij , i  n,   x j  maksa ji   bi , i  n,

  x  AT   b  ,





 x   AT   b  .

(1)

Pada sistem A  x  B  y , dengan matriks A dan B mempunyai baris atau kolom minimal terdiri dari satu elemen berhingga. Sistem A  x  B  y ini akan diselesaikan menggunakan Persamaan (3.1) dengan cara iterasi. Contoh 1. Diberikan suatu persamaan A  x  B  y dan akan didapatkan penyelesaiannya.  3   0 1 1   3 1         T Matriks A   1 1 0  dan B   3 2  dengan A     1 1  dan    1 2 3 1   0 0 2         5   1 3 3   . Misalkan di ambil x  x0    3  . B   1 2 1  1   T

8  4     1 Untuk r = 0, didapatkan A  x   6  , dan y    serta B  y   5  .  3  4  4     1  4  3       1 Untuk r = 1, diperoleh x   3  , A  x   4  , y    dan B  y   4  .  2  2  4  4      

3

 0  3     Untuk r = 2, diperoleh x   3  , dan A  x   4  .  2  4      3  3     Karena A  x   4  dan B  y   4  , maka penyelesaian dari persamaan  4  4      0   1 A  x  B  y adalah x   3  dan y    .  2  2  



Cunningham-Green(2003) mengenalkan suatu algoritma yang konvergen ke suatu penyelesaian yang berhingga dari sebarang titik awal berhingga. Metode ini dinamakan Metode Alternatif, dengan algoritmanya adalah sebagai berikut. Algoritma 1. (Cunninghame-Green, 2003) 1. Pilih sebarang vektor x yang berhingga. 2. Tetapkan r = 0 dan x(0) = x. 3. Hitung a  A  x .





4. Definisikan y   B T  a . 5. Hitung b  B  y .





6. Hitung x   AT  b . 7. Tetapkan r = r + 1 dan ulangi hingga konvergen. Bukti:

 



Diketahui bahwa U   U T  W  W . Maka

 



 



A  x  A   AT   B  y   B  y  B   B T   A  x   A  x Jadi, A  x  B  y .

Berikut ini diberikan contoh untuk mendapatkan penyelesaian dari persamaan dengan menggunakan metode alternatif di atas. Contoh 2. Diberikan A  x  B  y , dengan matriks A dan B seperti pada Contoh 1.

4

 9  5     Jika diberikan x  x0    8  diperoleh x   8  dan  5 7    

merupakan penyelesaian dari

A x  B y

dengan

 6 y    yang juga 7  5  0     x  8   3 7  2    

dan

 6 1 y       . 7  2 1 1     Jika diberikan x  x0    7  diperoleh x   5  dan  4  4    

merupakan

penyelesaian

dari

A x  B y ,

tetapi

 3 y    yang juga  3 1  0     x   5   3  4  2    

dan

 3  1  y       .  3  2  Jadi, penyelesaian dari persamaan A  x  B  y tidak tunggal yaitu pasangan  0 1     1  3 x   3  dan y    , x   5  dan y    atau kelipatan masing-masing.  2  3  2  4    



Pada sistem A  x  B  y , jika x = y maka didapatkan A  x  B  x yang merupakan sistem dua sisi. Dengan menggunakan metode alternatif, akan diselesaikan sistem dua sisi seperti pada contoh berikut ini. Contoh 3. Diberikan suatu Sistem A  x  B  x dan akan didapatkan penyelesaiannya. 3     1 1  dan matriks B    . Misalkan matriks A   1 1   3 1  5  3 Ambil sebarang x  x0     . Maka diperoleh x    .  3  5

5

 4  4   3 Jika diberikan nilai awal x  x0     diperoleh x       . 7  6   5 9  7   3 Jika diberikan nilai awal x  x0     diperoleh x       .  2  9   5 Jadi, penyelesaian dari persamaan

A x  B x

adalah

 3 x     5

atau 

kelipatannya.

Berikut ini adalah sistem dua sisi dengan syarat khusus yaitu:

C  y  D  y , dengan cij  d ij untuk setiap i  N dan j M,

(2)

dengan N menyatakan himpunan baris {1, 2, ...., n} dan M adalah himpunan kolom {1, 2, ...., m} dari matriks C dan D. Ukuran matriks C dan D ini haruslah sama. Berikut ini akan diberikan suatu lemma yang menyatakan syarat bahwa sistem dua sisi tidak mempunyai penyelesaian. Lemma 1. (Cechlarova, 2005) Jika ada sebuah baris i sehingga cij > dij untuk setiap j, maka sistem dua sisi tidak mempunyai penyelesaian. Bukti: Akan dibuktikan dengan menggunakan kontradiksi. Anggap bahwa sebuah vektor y adalah sebuah penyelesaian dari Sistem dua sisi (2) dan bahwa nilai maksimum pada ruas kiri adalah cij  y j  makscik  y k . Dan nilai maksimum pada ruas k

kanan adalah d il  y l  maksd ik  y k . k

Maka didapatkan cij  y j  cil  y l  d il  y l . Karena cil  y l  d il  y l , berarti bahwa y bukan merupakan penyelesaian dari Sistem dua sisi (2) sebab jika y merupakan penyelesaian seharusnya cil  y l  d il  y l . 

Jadi, kontradiksi.

6

Dari Lemma 1. di atas, memberikan akibat sebagai berikut: Akibat 1. (Cechlarova, 2005) Untuk tiap Sistem dua sisi (2) yang mempunyai penyelesaian, ada untuk tiap baris i suatu indeks j sehingga cij = dij. Bukti: Misalkan vektor y adalah penyelesaian dari Sistem dua sisi (2). Sehingga nilai maksimum pada ruas kiri adalah cij  y j  maks cik  y k  . k

Sedangkan nilai maksimum pada ruas kanan adalah d il  y l  maks d ik  y k . k

Maka didapatkan cij  y j  d il  y l . Hal ini berarti untuk tiap baris i ada l = j 

sehingga cij  y j  d ij  y j dan didapatkan cij  d ij .

Pada sistem dua sisi C  x  D  x , cij  d ij untuk setiap i  N dan j M. Jika diberikan nilai awal x sebarang, maka didapatkan D  x  y . Sehingga sistem



berubah menjadi C  x  y . Karena C dan y diketahui, maka x   C T   y



bisa diperoleh. Hal ini dilakukan berulang-ulang hingga didapatkan nilai x yang memenuhi C  x  D  x . Berikut ini akan diberikan contoh menyelesaikan sistem dua sisi C  x  D  x , dimana cij  d ij untuk setiap i  N dan j M. Contoh 4. Diberikan suatu sistem dua sisi C  x  D  x , dimana cij  d ij untuk setiap iN 1 2 4 8  0 1 4 5     dan jM dengan matriks C   6 3 9 4  dan matriks D   2 3 9 2  .  7 3 8 0  7 3 7 0    

1  2 T Didapatkan matriks C   4  8 

6 3 9 4

7 0 2   3 1 3 T dan D    8 4 9     0 5 2

7

7  3 . 7  0 

0   0 Misal di ambil x  x0    . 0   0   5  5     Untuk r = 0, maka diperoleh y  D  x   9  sehingga didapatkan C  x   9  . 7 7    

 0     3  Akibatnya, diperoleh nilai x   C T   y    . 1     3  





 4  4     Untuk r = 1, didapatkan nilai y  D  x   8  sehingga C  x   8  . Maka 7 7    

 0     2  T diperoleh nilai x   C   y    . 1     4  





 3  3     Untuk r = 2, diperoleh nilai y  D  x   8  sehingga C  x   8  . Akibatnya 7 7    

 0     1  T didapatkan nilai x   C   y    . 1     5  





 3   Untuk r = 3, didapatkan y  D  x   8  . 7  

Maka penyelesaian dari sistem dua sisi C  x  D  x , dimana cij  d ij untuk  0     1  setiap i  N dan j M adalah x    . 1     5  



8

Berikut ini diberikan algoritma untuk menyelesaikan sistem dua sisi. Algoritma 2. 1. Pilih sebarang vektor x yang berhingga. 2. Tetapkan r = 0 dan x(0) = x. 3. Hitung b  B  x .





4. Definisikan x   AT  b . 5. Hitung a  A  x .





6. Hitung x   B T   a . 7. Ulangi hingga memenuhi A  x  B  x . Pembuktian Algoritma 2 sama dengan pembuktian Algoritma 1. Berikut ini diberikan contoh untuk mendapatkan penyelesaian dari persamaan dengan menggunakan Algoritma 2 di atas. Contoh 5. Diberikan suatu sistem dua sisi C  x  D  x , dimana cij  d ij untuk setiap iN dan jM dengan matriks C dan D seperti pada Contoh 4. 1  1      0  2  Jika diberikan nilai awal x  x0     maka diperoleh x    yang 1 0     0   4      0     1  merupakan kelipatan dari x    . 1     5    2  4     8  4 Jika diberikan nilai awal x  x0     maka diperoleh x    yang bukan 0 2      3  2      0     1  merupakan kelipatan dari x    . 1     5  

9

9 9     1 8 Jika diberikan nilai awal x  x0     maka diperoleh x    yang bukan 6 6     7  2      0   4      1   4 merupakan kelipatan dari x    atau x    . 1 2       5  2    

Jadi, penyelesaian sistem dua sisi C  x  D  x , dimana cij  d ij untuk setiap  0   4 9        1   4 8 i  N dan j  M adalah tidak tunggal yaitu x    , x    , x    atau 1 2 6         5  2  2       

kelipatannya.

4. Kesimpulan

Sistem dua sisi A  x  B  x dapat diselesaikan dengan iterasi menggunakan metode alternatif. Sistem dua sisi dengan syarat khusus C  y  D  y , dengan cij  d ij untuk setiap i  N dan j M, dapat diselesaikan dengan menggunakan

iterasi. Penyelesaian yang dihasilkan bisa tunggal atau tidak tunggal yang berupa kelipatannya.

5. Daftar Pustaka Aminu, Abdulhadi, Butkovic,P., (2008), Comparison of methods for solving twosided systems in max-algebra, Baccelli, F., Cohen, G., Olsder, G.J. dan Quadrat, J.P. (1992), Synchronization and Linearity An Algebra for Discrete Event Systems, John Wiley & Sons, New York.

10

Butkovic, P., Zimmermann, K., (2006), A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Theoret.Comput. Sci., 154 hal. 437-446. Cechlarova, K. (2005), “Eigenvectors of Interval Matrices over Max-Plus Algebra”, Journal of Discrete Applied Mathematics, vol. 150, hal. 2–15. Cunninghame-Green, R. A., Butkovic, P. (2003), “The Equation A  x  B  y over(max, +)”, Journal of Theoretical Computer Science, vol. 293, hal. 3 – 12. Heidergott, B., Olsder, G.J. dan Woude, J. van der (2006), Max Plus at Work, Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications, Princeton University Press, New Jersey. Subiono (2007), Max-plus Algebra Toolbox, ver. 1.0, Jurusan Matematika Institut Teknologi Sepuluh Nopember, Surabaya.

11