Aljabar Maxplus dan Terapannya

Aljabar Maxplus dan Terapannya Version 1.1.1

10 Sepetember 2013

san Mate ru

a *

Matematika

ay

F M I PA

M

a atik m

*J u

Subiono

-I b T S , Sura

Subiono — Email: [email protected]

Alamat: Jurusan Matematika Institut Teknologi Sepuluh Nopember Sukolilo Surabaya Indonesia

2

Copyright

san Mate ru

a *

Matematika

ay

F M I PA

M

a atik m

*J u

c 2013 The Author.

-I b T S , Sura

c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

Kata Pengantar

Alhamdulillahirabbilalamin, segala puji hanyalah milikmu ya Allah yang telah meberikan "kebebasan bertanggung jawab" kepada manusia semasa hidupnya untuk suatu kebaikan dalam melaksanakan amanatnya di hamparan bumi yang dihuni beragam manusia. Sholawat dan Salam kepadamu ya Nabi Muhammad beserta para keluarganya dan para pengikutnya sampai nanti di hari akhir. Buku ini disusun dengan maksud untuk membantu dan mempermudah mahasiswa dalam mempelajari materi kuliah Aljabar MaxPlus. Selain dari pada itu juga dimaksudkan untuk menambah suatu wacana bagi para peminat lainnya dari berbagai disiplin ilmu yang membutuhkannya atau kalangan industri dan perguruan tinggi. Dalam buku ini diberikan beberapa konsep pengertian dari materi yang disajikan setelah itu diikuti dengan beberapa contoh untuk mempermudah pemahaman, selain itu juga diberikan beberapa contoh aplikasi. Topik bahasan disajikan dengan penekanan pada "matematika" tetapi tidaklah menjadikan para pemakai lain akan mengalami kesulitan dalam mempelajari buku ini, karena peletakan penekanan aspek matematika dibuat dengan porsi yang seimbang. Sehingga para peminat matematika tetap dapat menikmati dan menggunakan ilmunya terutama dalam Aljabar MaxPlus, begitu juga untuk para pemakai yang lainnya diharapkan mendapat tambahan wawasan untuk melihat matematika sebagai alat yang dibutuhkan terutama dalam kajian Aljabar MaxPlus untuk menyelesaikan masalah-masalah praktis yang dihadapinya. Untuk memudahkan pembaca mengikuti alur dari setiap topik bahasan dalam buku ini, diasumsikan pembaca mempunyai bekal pengetahuan "Aljabar" dan "Aljabar Linear" yang memadai sebagai pembanding dari segi Aljabar biasa dengan Aljabar MaxPlus. Persiapan penulisan materi buku ini membutuhkan waktu yang agak lama, sejak penulis mengajarkan mata kuliah "Sistem Event Diskrit" dijurusan Matematika FMIPA-ITS, Surabaya. Hampir keseluruhan materi dari mata kuliah ini adalah Aljabar MaxPlus. Beberapa materi disusun dari pengalaman mengajar tsb. Selain itu juga dari kumpulan makalah penulis dan hasil-hasil dari pembimbingan thesis mahasiswa. Penulis pada kesempatan ini menyampaikan keaktifan pembaca dalam mengkaji buku ini untuk menyampaikan kritik dan saran guna perbaikan buku ini, sehingga pada versi yang mendatang "mutu buku" yang baik bisa dicapai. Kritik dan saran ini sangat penting i

ii

Surabaya, 10 Sepetember 2013 san Mate u ur

M

Matematika

-I

TS

a *

b

ay

* F M I PA

a atik m

J

karena selain alasan yang telah disebutkan tadi, penulis percaya bahwa dalam sajian buku ini masih kurang dari sempurnah bahkan mungkin ada suatu kesalahan dalam sajian buku ini baik dalam bentuk redaksional, pengetikan dan materi yang menyebabkan menjadi suatu bacaan kurang begitu bagus. Buku ini dapat diperoleh secara gratis oleh siapapun tanpa harus membayar kepada penulis. Hal ini berdasarkan pemikiran penulis untuk kebebasan seseorang mendapatkan suatu bacaan yang tersedia secara bebas dengan maksud "kemanfaatan" dan "kejujuran". Yang dimaksud dengan kemanfaatan adalah bergunanya bacaan ini untuk kemudahan pembaca memperoleh informasi penting yang diperlukannya dan untuk pembelajaran. Sedangkan kejujuran adalah ikatan moral dari pembaca untuk tidak memdistribusi buku ini dengan tujuaan yang tidak bermanfaat. Penulis menulis buku ini berdasarkan pemikiran "kebebasan menulis" (tidak harus menggunakan media cetak penerbit) dengan asas "kemanfaatan" menggunakan media yang tersaji masa kini. Beberapa alat bantu untuk penulisan buku ini juga didapat secara gratis, yaitu perangkat lunak LATEX untuk Windows yaitu MIKTEX 2.9 dan TEXMAKER 3.5 sebagai salah satu media LATEX editor. Beberapa gambar yang ada dalam buku ini menggunakan perangkat lunak LATEXDraw 2.0.8 yang juga didapat secara gratis. Begitu juga beberapa bahan rujukan didapat secara gratis lewat internet. Selain itu untuk menyelesaikan beberapa contoh yang dibahas digunakan alat bantu perangkat lunak toolbox for maxplus algebra versi terbaru v 1.1.1. Toolbox ini penulis buat dan telah di upload di website ([13]). Tool box bisa di jalankan dengan perangkat lunak Scilab versi 5.3.2, perangkat lunak ini juga didapat dari internet secara gratis. Akhirnya, dengan segala kerendahan hati penulis memohon kepada Allah semoga penulisan ini bisa berlanjut untuk versi mendatang yang tentunya lebih "baik" dari Versi 1.0.1 yang tersedia saat ini dan semoga benar-benar buku yang tersaji ini bermanfaat bagi pembaca.

, Sura

b

Penulis


Daftar Isi

Kata Pengantar

i

1 Pendahuluan 1.1 Aljabar Max-Plus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Vektor dan Matriks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 7

2 Teori Spektral 2.1 Matriks dan Graf . . . . . . . . . . . . . . 2.2 Nilai karakteristik dan Vektor karakteristik 2.3 Penyelesaian Persamaan Linear . . . . . . 2.3.1 Sub-Penyelesaian Terbesar . . . . . 2.3.2 Analisis Penyelesaian A ⊗ x = b . . 2.3.3 Persamaan x = (A ⊗ x) ⊕ b . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

3 Contoh Aplikasi 3.1 Masalah Jadwal Penerbangan Pesawat pada suatu Bandara . 3.2 Sistem Produksi Sederhana . . . . . . . . . . . . . . . . . . . 3.3 Penjadwalan Sistem Jaringan Kereta dan Kestabilan . . . . 3.3.1 Contoh jaringan kereta . . . . . . . . . . . . . . . . . 3.3.2 Pengkajian model yang diharapkan . . . . . . . . . . 3.3.3 Jadwal keberangkatan . . . . . . . . . . . . . . . . . 3.3.4 Simulasi sistem terhadap keterlambatan . . . . . . . 3.4 Menentukan Jalur Tercepat . . . . . . . . . . . . . . . . . . 3.5 Model sistem antrian . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Model Aljabar maxplus dari Petri net dengan waktu. Daftar Pustaka

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

19 19 24 33 33 36 44

. . . . . . . . . .

47 47 49 53 54 56 56 58 61 62 63 67

iii

Bab

1

Pendahuluan Akhir-akhir ini baik dunia industri ataupun dunia akademik tertarik pada teknik untuk memodel, menganalisa dan mengontrol sistem-sistem yang kompleks seperti sistem manufaktur fleksibel, jaringan telekomunikasi, sistem proses parallel, sistem kontrol trafik, sistem logistik dsb. Macam-macam sistem yang telah di sebutkan tadi adalah contoh dari Sistem Event Diskrit (SED). Klas dari SED utamanya memuat sistem buatan manusia yang terdiri dari sejumlah resources (misalnya, mesin, kanal-kanal komunikasi, processor,.....) yang dipakai bersama oleh beberapa pengguna (misalnya, macam produk, paket informasi, job,.....) kesemuanya itu berkontribusi untuk mencapai beberapa tujuan bersama (misalnya, produk perakitan, transmisi dari sekumpulan paket informasi, komputasi parallel,......). Suatu gambaram karakteristik dari SED adalah ’kedinamikannya’ yaitu "eventdriven" yang bertolak belakang dengan "time-driven". Disini perilaku suatu SED lebih ditentukan oleh event dari pada waktu. Suatu event berkaitan dengan awal atau akhir dari suatu aktifitas. Bila ditinjau suatu sistem produksi, maka event yang mungkin adalah kelengkapan mesin telah menyelesaikan suatu produk, suatu buffer telah kosong dsb. Event terjadi dengan waktu diskrit. Interval diantara event tidak harus identik, bisa deterministik atau stokhastik. Umumnya kedinamikan dari SED dikarakteristikan oleh ’kesinkronan’ dan ’konkurensi’. Sinkronisasi memerlukan ketersediaan dari beberapa resources pada saat yang bersamaan (misalnya, sebelum bisa dirakit suatu produk pada suatu mesin, mesin harus dalam keadaan sedang tidak sibuk ("idle") dan beberapa komponen lain sudah harus tersedia sebelum suatu job tertentu bisa dieksekusi, dalam sistem proses parallel, processor dan semua data input yang diperlukan sudah harus tersedia,.....). Konkurensi tampak ketika pada suatu saat seorang pengguna harus memilih beberapa resources (misalnya, dalam suatu sistem produksi suatu job mungkin dieksekusi pada beberapa mesin yang bisa menangani job tsb. dan saat tersebut mesin-mesin harus dalam keadaan idle; dalam sistem proses parallel suatu "data-driven" dari suatu job mungkin dieksekusi pada beberapa processor yang teersedia pada saat tsb. atau dengan segera processor tsb. akan tersedia.....). Pendekatan aljabar max-plus dapat menentukan dan menganalisa berbagai sifat sistem, tetapi pendekatan hanya bisa diterapkan pada sebagian klas SED yang bisa diuraikan dengan model waktu invarian max-linier. Subklas ini adalah subklas dari waktu 1

2

Pendahuluan..

invarian SED deterministik dimana hanya sinkronisasi tampa kejadian yang konkurensi. Walaupun hanya sinkronisasi saja yang dipertimbangkan dalam aljabar max-plus, hal ini sudah dapat menganalisa perilaku suatu sistem yang ada. Beberapa gambaran konkrit dari pemakaian aljabar max-plus adalah pada suatu jaringan sistem transportasi, hal ini bisa didapat di ([7], [3] dan [12]). Selain itu aljabar max-plus juga dapat digunakan untuk menganalisa kedinamikan sistem pada penjadwalan flow shop ([9]). Sedangkan pembahasan berkaitan dengan Penjadwalan Jalur Bus Dalam Kota dapat dijumpai di [10]. Dalam konteks aljabar max-plus sistem model yang terjadi adalah linier dan non-linier pada aljabar biasa. Beberapa penghitungan dalam aljabar maxplus pada contoh-contoh menggunakan maxplus aljabar toolbox versi 1.0.1 ([13]). Pada bagian berikutnya dibahas pengertian aljabar max-plus dan beberapa notasi yang digunakan. Pembahasan yang lengkap dan rinci mengenai aljabar max-plus bisa dijumpai di [2] dan [1].

1.1

Aljabar Max-Plus

Dalam bagian ini dibahas beberapa konsep dasar yang akan digunakan untuk membahas sistem linear max-plus waktu-invariant. Pembahasan meliputi semimodul Rnmax atas aljabar max-plus Rmax , sistem persamaan linear max-plus, aljabar max-plus dan pengertian graf berarah. Pembahasan dimulai dengan pengertian semi ring dan contohnya. Selanjutnya operasi pada Rmax diperluas untuk matriks dalam Rm×n max serta relasi urutan didalamnya.

Definisi 1 Suatu semiring (S, +, ×), adalah suatu himpunan tak kosong S disertai dengan dua operasi biner + dan ×, yang memenuhi aksioma berikut: i) (S, +) merupakan semigrup komutatif dengan elemen netral 0, yaitu ∀x, y, z ∈ S memenuhi x+y = y+x (x + y) + z = x + (y + z) x + 0 = 0 + x = x, ii) (S, ×) adalah semigrup dengan elemen satuan 1, yaitu ∀x, y, z ∈ S memenuhi (x × y) × z = x × (y × z) x × 1 = 1 × x = x, iii) sifat penyerapan elemen netral 0 terhadap operasi ×, yaitu ∀x ∈ S memenuhi x × 0 = 0 × x = 0. iv) Operasi × distributif terhadap +, yaitu ∀x, y, z ∈ S berlaku (x + y) × z = (x × z) + (y × z), x × (y + z) = (x × y) + (x × z)


3

Aljabar Max-Plus..

def

Contoh 1.1.1 Diberikan Rε = R ∪ {ε} dengan R adalah himpunan semua bilangan real def dan ε = −∞. Pada Rε didefinisikan operasi berikut: ∀x, y ∈ Rε , def

def

x ⊕ y = max{x, y} dan x ⊗ y = x + y . Jadi 10 ⊕ −10 = max{10, −10} = 10 dan −7 ⊗ 14 = −7 + 14 = 7. Selanjutnya ditunjukkan (Rε , ⊕, ⊗) merupakan semiring dengan elemen netral ε dan elemen satuan e = 0, karena untuk setiap x, y, z ∈ Rε berlaku: i) x ⊕ y = max{x, y} = max{y, x} = y ⊕ x, (x ⊕ y) ⊕ z = max{max{x, y}, z} = max{x, y, z} = max{x, max{y, z}} = x ⊕ (y ⊕ z), x ⊕ ε = max{x, −∞} = max{−∞, x} = ε ⊕ x = x. ii) (x ⊗ y) ⊗ z = (x + y) + z = x + (y + z) = x ⊗ (y ⊗ z), x ⊗ e = x + 0 = 0 + x = e ⊗ x = x, iii) x ⊗ ε = x + (−∞) = −∞ = −∞ + x = ε ⊗ x, iv) (x ⊕ y) ⊗ z = max{x, y} + z = max{x + z, y + z} = (x ⊗ z) ⊕ (y ⊗ z), x ⊗ (y ⊕ z) = x + max{y, z} = max{x + y, x + z} = (x ⊗ y) ⊕ (x ⊗ y) .

Selanjutnya untuk lebih ringkasnya, penulisan semiring (Rǫ , ⊕, ⊗) ditulis sebagai Rmax . Definisi 1.1.1 Bila suatu semiring (S, +, ×) terhadap operasi × berlaku ∀x, y ∈ S, x × y = y × x, maka dikatakan semiring komutatif. Definisi 1.1.2 Bila suatu semiring (S, +, ×) mempunyai sifat idempoten terhadap operasi + yaitu untuk setiap x di S berlaku x + x = x, maka dikatakan semiring idempoten atau dioid. Contoh 1.1.2 Semiring Rmax merupakan semiring komutatif yang sekaligus idempoten, sebab untuk setiap x, y ∈ Rε berlaku x⊗y = x+y = y+x = y⊗x dan x⊕x = max{x, x} = x . Definisi 1.1.3 Suatu semiring komutatif (S, +, ×) dinamakan semifield bila setiap elemen x di S − {0} mempunyai invers terhadap operasi ×, yaitu untuk setiap x di S − {0} ada x−1 sehingga x × x−1 = x−1 × x = 1.


4

Pendahuluan..

Contoh 1.1.3 Semiring komutatif Rmax merupakan semifield, sebab untuk setiap x ∈ R ada −x, sehingga berlaku x ⊗ (−x) = x + (−x) = 0. Dari Contoh 1.1.2 dan 1.1.3 di atas terlihat bahwa Rmax merupakan semifield idempoten. Elemen-elemen Rmax akan disebut juga dengan skalar. Seperti halnya dalam aljabar biasa, prioritas urutan operasi ⊗ lebih dulu atas operasi ⊕. Misalnya, 10 ⊗ −7 ⊕ 6 ⊗ 2 mempunyai arti (10 ⊗ −7) ⊕ (6 ⊗ 2) = 3 ⊕ 8 = max{3, 8} = 8, perintah dalam Scilab sbb: -->maxplusoplus(maxplusotimes(10,-7),maxplusotimes(6,2)) ans = 8. sedangkan 10 ⊗ (−7 ⊕ 6) ⊗ 2 = 10 ⊗ 6 ⊗ 2 = 10 + 6 + 2 = 18, perintah dalam Scilab sbb: -->maxplusotimes(maxplusotimes(10,maxplusoplus(-7,6)),2) ans = 18 Pangkat dalam aljabar max-plus secara biasa diperkenalkan dengan menggunakan sifat assosiatif. Himpunan bilangan asli digabung dengan bilangan nol dinotasikan oleh N dan didefinisikan untuk x ∈ Rmax dan untuk semua n ∈ N dengan n 6= 0 def

x⊗n = x | ⊗x⊗ {z. . . ⊗ x}

(1.1)

n

def

sedangkan untuk n = 0 didefenisikan x⊗n = e(= 0). Perhatikan bahwa untuk setiap n ∈ N, x⊗n dalam aljabar biasa dibaca sebagai def

x⊗n = x | +x+ {z. . . + x} = n × x. n

Suatu contoh, misalnya

9⊗2 = 2 × 9 = 18.

Terinspirasi oleh pengertian pangkat ini, dengan cara serupa pangkat negatif dari bilangan real sebagai mana contoh berikut 8⊗−2 = −2 × 8 = −16 = 16⊗−1 . c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

5

Aljabar Max-Plus..

Hal yang sama, akar-akar max-plus diperkenalkan sebagai x⊗α = α × x, Suatu contoh, misalnya 1

9⊗ 3 =

untuk α ∈ R. 1 ×9=3 3

dan

1 1 16⊗− 4 = − × 16 = −4. 4 Penghitungan pangkat dalam contoh-contoh tsb. bisa dilakukan dengan menggunakan aljabar maxplus toolbox ([13]).

-->maxpluspwr(9,2) ans = 18. -->maxpluspwr(8,-2) ans = -16. // cek apakah maxpluspwr(8,-2)=maxpluspwr(16,-1) sbb: -->isequal( maxpluspwr(8,-2),maxpluspwr(16,-1)) ans = T -->maxpluspwr(9,1/3) ans = 3. -->maxpluspwr(16,-1/4) ans = - 4. Sebagai mana telah ditunjukkan dalam Contoh 1.1.2 dan 1.1.3 bahwa Rmax merupakan semifield idempoten, yaitu semiring komutatif yang idempoten dengan setiap elemen x 6= ε mempunyai invers −x terhadap operasi ⊗. Berikut ini diberikan lagi beberapa contoh dari semiring komutatif yang idempoten. Contoh 1.1.4 • Aljabar min-plus didefinisikan sebagai Rmin = (Rε′ , ⊕′ , ⊗) dimana Rε′ = R ∪ {ε′ } def def dengan ε′ = +∞ dan x ⊕′ y = min{x, y} untuk semua x, y ∈ Rε′ . Struktur aljabar min-plus Rmin = (Rε′ , ⊕′ , ⊗) isomorpik dengan struktur aljabar max-maxplus Rmax = (Rε , ⊕, ⊗). Misalkan pemetaan f : Rmax → Rmin dengan f (x) = −x untuk setiap x ∈ Rmax . Didapat untuk setiap x, y ∈ Rmax f (x ⊕ y) = −(x ⊕ y) = − max{x, y} = min{−x, −y} = f (x) ⊕′ f (y) c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

6

Pendahuluan..

dan f (x ⊗ y) = −(x + y) = (−x) + (−y) = f (x) ⊗ f (y). Jelas bahwa pemetaan f adalah bijektif. • Misalkan Rmax,min = (R, ⊕′ , ⊕) dengan R = R ∪ {ε, ε′}, ε ⊕ ε′ = ε′ ⊕ ε = ε′ dan ε ⊕′ ε′ = ε′ ⊕′ ε = ε. • Misalkan himpunan S takkosong dan R adalah himpunan dari semua himpunan bagian dari S, maka (R, ∪, ∩) merupakan semiring komutatif idempoten dengan X ∪ ∅ = ∅ ∪ X = X, ∀X ∈ R dan X ∩ S = S ∩ X = X, ∀X ∈ R. Hal yang sama (R, ∩, ∪) merupakan semiring komutatif idempoten.

Struktur aljabar semiring komutatif idempoten ini berbeda dengan aljabar biasa yang telah banyak dikenal. Hal ini dapat dilihat dalam masalah berikut. Apakah mungkin untuk mendefinisikan elemen invers terhadap operasi ⊕ dalam Rmax ? Suatu contoh, apakah mungkin mendapatkan penyelesaian persamaan 8 ⊕ x = 4?

(1.2)

Sebagaimana dalam aljabar biasa bila kedua sisi persamaan (1.2) dikurangi dengan 8, didapat penyelesaian x = −8 ⊕ 4. Tetapi, apakah mungkin memberikan arti terhadap −8 dalam persamaan diatas ? Apapun hal ini, bila kembali pada persamaan (1.2) didapat persamaan max{8, x} = 4.

(1.3)

Jelas bahwa tidak akan ada bilangan yang memenuhi persamaan (1.3). Dilain pihak dalam aljabar min-plus, persamaan (1.3) menjadi min{8, x} = 4 mempunyai penyelesaian x = 4. Selanjutnya bila dipertukarkan bilangan 4 dan 8 dalam persamaan (1.2) didapat 4 ⊕ x = 8. Persamaan ini tidak mempunyai penyelesaian dalam aljabar min-plus. Dari apa yang telah didiskusikan ini, muncul suatu pertanyaan apakah ada suatu semiring khusus sedemikian hingga semua persamaan yang berbentuk persamaan (1.2) mempunyai penyelesaian. Teorema berikut merupakan jawabannya. Teorema 1.1.1 Diberikan semiring Rmax = (R, ⊕, ⊗). Idempoten dari ⊕ berakibat bahwa elemen invers terhadap ⊕ tidak ada. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

7

Vektor dan Matriks..

Bukti Misalkan bahwa a 6= ε mempunyai suatu invers terhadap ⊕ yaitu b, didapat a ⊕ b = ε. Tambahkan a pada kedua ruas persamaan, didapat a ⊕ a ⊕ b = a ⊕ ε. Dengan sifat idempoten, persamaan menjadi a ⊕ b = a. hal ini bertentangan dengan a ⊕ b = ε.

1.2

Vektor dan Matriks

Dalam bagian ini dikenalkan matriks atas Rmax . Himpunan matriks ukuran n × n dalam def n×m aljabar max-plus dinotasikan oleh Rmax . Untuk n ∈ N dengan n 6= 0, didefinisikan n = n×m {1, 2, . . . , n}. Elemen A ∈ Rmax baris ke-i kolom ke-j dinotasikan oleh ai,j untuk i ∈ n dan j ∈ m. Dalam hal ini matriks A ditulis sebagai   a1,1 a1,2 . . . a1,m  a2,1 a2,2 . . . a2,m    A =  .. ..  . .. . .  . . .  . an,1 an,2 . . . an,m

Ada kalanya elemen ai,j juga dinotasikan sebagai [A]i,j ,

i ∈ n, j ∈ m.

(1.4)

n×m Penjumlahan matriks A, B ∈ Rmax dinotasikan oleh A ⊕ B didefenisikan oleh

[A ⊕ B]i,j = ai,j ⊕ bi,j = max{ai,j , bi,j },

(1.5)

untuk i ∈ n dan j ∈ underlinem. Contoh 1.2.1 Diberikan matriks 1 e A= 2 5 maka

[A ⊕ B]1,1 [A ⊕ B]1,2 [A ⊕ B]2,1 [A ⊕ B]2,2

dan B =

−3 3 ε 10

,

= 1 ⊕ −3 = max{1, −3} = 1 = e ⊕ 3 = max{0, 3} = 3 = 2 ⊕ ε = max{2, −∞} = 2 = 5 ⊕ 10 = max{5, 10} = 10


8

Pendahuluan..

Dengan menggunakan notasi matriks didapat 1 3 A⊕B = 2 10

perintah dalam Scilab sbb: -->A=[1 0;2 5] A = 1. 0. 2. 5. -->B=[-3 3;-%inf 10] B = - 3. 3. -Inf 10. -->maxplusoplus(A,B) ans = 1. 3. 2. 10. n×m Catatan bahwa, untuk A, B ∈ Rmax berlaku bahwa A ⊕ B = B ⊕ A, sebab [A ⊕ B]i,j = max{ai,j , bi,j } = max{bi,j , ai,j } = [B ⊕ A]i,j untuk i ∈ n dan j ∈ m. n×m Untuk A ∈ Rmax dan skalar α ∈ Rmax perkalian α ⊗ A didefinisikan sebagai def

[α ⊗ A]i,j = α ⊗ ai,j

(1.6)

untuk i ∈ n dan j ∈ m. Sebagai contoh, misalkan matriks A seperti dalam Contoh 1.2.1 dan α = 3, maka [α ⊗ A]1,1 = 3 ⊗ 1 = 3 + 1 = 4 [α ⊗ A]1,2 = 3 ⊗ e = 3 + 0 = 3 [α ⊗ A]2,1 = 3 ⊗ 2 = 3 + 2 = 5 [α ⊗ A]2,2 = 3 ⊗ 5 = 3 + 5 = 8 Dengan menngunakan notasi matriks didapat 4 3 α⊗A= 5 8 dalam Scilab perintahnya: -->alp=3 alp = 3. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

9


-->A=[1 0;2 5] A = 1. 0. 2. 5. -->maxplusotimes(alp,A) ans = 4. 3. 5. 8. n×p Untuk matriks A ∈ Rmax dan B ∈ Rp×m max perkalian matriks A ⊗ B didefinisikan sebagai

[A ⊗ B]i,j =

p L

ai,k ⊗ bk,j

(1.7)

k=1

= max{ai,k + bk,j }, k∈p

untuk i ∈ n dan j ∈ m. Perkalian matriks ini serupa dalam perkalian matriks aljabar biasa dimana + diganti dengan max dan × dengan +. Contoh 1.2.2 Diberikan matriks 1 e A= 2 5 maka

[A ⊗ B]1,1 [A ⊗ B]1,2 [A ⊗ B]2,1 [A ⊗ B]2,2

dan B =

−3 3 ε 10

,

= 1 ⊗ −3 ⊕ e ⊗ ε = max{1 + (−3), 0 + (−∞)} = −2 = 1 ⊗ 3 ⊕ e ⊗ 10 = max{1 + 3, 0 + 10} = 10 = 2 ⊗ −3 ⊕ 5 ⊗ ε = max{2 + (−3), 5 + (−∞)} = −1 = 2 ⊗ 3 ⊕ 5 ⊗ 10 = max{2 + 3, 5 + 10} = 15

Dengan menngunakan notasi matriks didapat −2 10 . A⊗B = −1 15

Perhatikan bahwa perkalian matriks tidak selalu komutatif. Untuk matriks A dan B dalam Contoh 1.2.2 didapat 5 8 6= A ⊗ B. B⊗A= 12 15 Dalam Scilab ketik: -->A=[1 0;2 5] A = 1. 0. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

10

Pendahuluan..

2. 5. -->B=[-3 3;-%inf 10] B = - 3. 3. -Inf 10. -->maxplusotimes(A,B) ans = - 2. 10. - 1. 15. -->maxplusotimes(B,A) ans = 5. 8. 12. 15. cek bahwa A ⊗ B 6= B ⊗ A: -->~isequal(maxplusotimes(A,B),maxplusotimes(B,A)) ans = T Sifat-sifat berikut berkaitan dengan sifat-sifat elementer perkalian dan penjumlahan matriks dalam aljabar maxplus. Teorema 1.2.1 Beberapa sifat berikut berlaku untuk sebarang matriks A, B dan C dengan ukuran yang bersesuaian dan operasi matriks terdefinisi. i) (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) ii) (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C) iii) A ⊗ (B ⊕ C) = (A ⊗ B) ⊕ (A ⊗ C) iv) (A ⊕ B) ⊗ C = (A ⊗ C) ⊕ (A ⊗ C) v) A ⊕ A = A . Bukti Akan dibuktikan untuk ii) dan iii) sedangkan bukti yang lainnya mengikuti dari definisi n×p operasi dan sifat-sifat operasi pada Rmax . Bukti ii), ambil sebarang matriks A ∈ Rmax ,B ∈ p×q q×m Rmax , C ∈ Rmax . Elemenbaris ke-i kolom ke-j matriks (A ⊗ B) ⊗ C adalah p q L L ai,l ⊗ bl,k ⊗ ck,j [(A ⊗ B) ⊗ C]i,j = =

=

k=1 l=1 q L p L

ai,l ⊗ bl,k ⊗ ck,j q L ai,l ⊗ bl,k ⊗ ck,j

k=1 l=1 p L

l=1

k=1

= [A ⊗ (B ⊗ C)]i,j ,


11


n×p untuk i ∈ n dan j ∈ m. Bukti iii), ambil sebarang matriks A ∈ Rmax dan B, C ∈ Rp×m max . Elemenbaris ke-i kolom ke-j matriks A ⊗ (B ⊕ C) adalah

[A ⊗ (B ⊕ C)]i,j = = =

p L

k=1 p L

ai,k ⊗ (bk,j ⊕ ck,j ) (ai,k ⊗ bk,j ⊕ ai,k ⊗ ck,j ) p L ai,k ⊗ bk,j ⊕ ai,k ⊗ ck,j

k=1 p L

k=1

k=1

= [(A ⊗ B)]i,j ⊕ [(A ⊗ C)]i,j , untuk i ∈ n dan j ∈ m.

Matriks ε(n, m) menyatakan matriks ukuran n × m dengan semua elemen sama dengan ǫ dan matriks E(n, m) adalah matriks ukuran n × m yang didefinisikan oleh ( e untuk i = j, def [E(n, m)]i,j = ǫ untuk i 6= j. Bila n = m, maka matriks E(n, n) dinamakan matriks identitas. Bila dimensi jelas dalam konteks, matriks ε (n, m) dan E(n, m) cukup ditulis ε dan E. Hal berikut jelas bahwa n×m untuk setiap matriks A ∈ Rmax memenuhi A ⊕ ε (n, m) = ε (n, m) ⊕ A, A ⊗ E(m, m) = A = E(n, n) ⊗ A. Matriks ε (m, n) dan E(m, n) dalam Scilab, misal ε (3, 5) -->maxpluszeros(3,5) ans = -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf

-Inf -Inf -Inf

sedangkan untuk E(5, 3) dan E(3, 3) adalah : -->maxpluseye(5,3) ans = 0. -Inf -Inf -Inf 0. -Inf -Inf -Inf 0. -Inf -Inf -Inf -Inf -Inf -Inf -->maxpluseye(3,3) ans = 0. -Inf -Inf -Inf 0. -Inf -Inf -Inf 0. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

12

Pendahuluan..

Dalam Rm×n max penjumlahan matriks ⊕ sebagaimana didefinisikan di (1.5) adalah asn×n sosiatif, komutatif dan mempunyai elemen nol ε (n, m). Dalam Rmax , perkalian matriks ⊗ sebagaimana didefinisikan di (1.7) adalah assosiatif, distributif terhadap ⊕ dan mempunyai elemen satuan E(n, n) serta elemen penyerap ε (n, n) untuk ⊗. Dalam pembahasan man×n triks ini, (Rmax , ⊕, ⊗) adalah semiring idempoten dengan elemen nol ε dan elemen satuan E, tetapi bukan semiring komutatif sebagaimana ditunjukkan dalam Contoh 1.2.2. ⊤ Transpose dari suatu elemen A ∈ Rm×n didefinisikan sebagai max dinotasikan oleh A def ⊤ [A ]i,j = aj,i , untuk i ∈ n dan j ∈ m. Sebagaimana sebelumnya, juga dalam penjumlahan dan perkalian matriks operasi ⊗ mempunyai prioritas urutan atas operasi ⊕. n×n Untuk A ∈ Rmax , pangkat ke-k dari A dinotasikan oleh A⊗k didefinisikan sebagai def

A⊗k = A {z. . . ⊗ A}, | ⊗A⊗

(1.8)

k

def

untuk k ∈ N dengan k 6= 0 dan A⊗0 = E(n, n). Elemen baris ke-i kolom ke-j dari matriks A⊗2 adalah adalah ⊗2

[A ]i,j =

n M

ai,r ⊗ ar,j = max {ai,r + ar,j }. 1≤r≤n

r=1

Elemen baris ke-i kolom ke-j dari matriks A⊗3 adalah adalah ! n n M M ⊗3 ar2 ,r1 ⊗ ar1 ,j = max {ai,r1 + ar1 ,r2 + ar2 ,j }. ai,r2 [A ]i,j = 1≤r1 ,r2 ≤n

r1 =1

r2 =1

Secara umum elemen baris ke-i kolom ke-j dari matriks A⊗k adalah adalah ! n n M M ai,rk−1 . . . [A⊗k ]i,j = ar2 ,r1 ⊗ ar1 ,j = max {ai,rk−1 + . . . + ar2 ,r1 + ar1 ,j }. rk−1 =1

1≤r1 ,...,rk−1 ≤n

r1 =1

n×n Selanjutnya, untuk α ∈ Rmax dan A ∈ Rmax elemen baris ke-i kolom ke-j matriks (α ⊗A)⊗k adalah

[(α ⊗ A)⊗k ]i,j =

{(α + ai,rk−1 ) + . . . + (α + ar2 ,r1 ) + (α + ar1 ,j )} = |α + α{z . . . + α} + max {ai,rk−1 + . . . + ar2 ,r1 + ar1 ,j } max

1≤r1 ,...,rk−1 ≤n

1≤r1 ,...,rk−1 ≤n

k

= α⊗k ⊗ [A⊗k ]i,j .

n×n Sehingga untuk setiap α ∈ Rmax dan A ∈ Rmax berlaku

(α ⊗ A)⊗k = α⊗k ⊗ A⊗k ,

untuk k = 1, 2, . . ..

(1.9)

n×n Selanjutnya untuk setiap A ∈ Rmax trace dari matriks A dinotasikan oleh trace(A) didefinn L isikan sebagai trace(A) = ai,i . i=1


13


Contoh 1.2.3 Diberikan matriks 

 1 2 ε A =  ε 3 4 . 5 ε 6

Maka matriks pangkat berikut A⊗2



     1 2 ε 1 2 ε 2 5 6 = A ⊗ A =  ε 3 4  ⊗  ε 3 4  =  9 6 10  5 ε 6 5 ε 6 11 7 12

A⊗3 = A ⊗ A⊗2

dan trace(A) =

3 L



     1 2 ε 2 5 6 11 8 12 =  ε 3 4  ⊗  8 6 10  =  15 11 16  5 ε 6 10 6 12 17 13 18

ai,i = max{1, 3, 6} = 6, trace(A⊗2 ) =

i=1

trace(A⊗3 ) =

3 L

[A⊗3 ]i,i = max{10, 10, 18} = 18.

3 L

[A⊗2 ]i,i = max{2, 6, 12} = 12,

i=1

i=1

Hasil penghitungan Contoh 1.2.3 dilakukan dalam Scilab sbb: -->A=[1 2 -%inf;-%inf 3 4;5 -%inf 6] A = 1. 2. -Inf -Inf 3. 4. 5. -Inf 6. -->a2=maxpluspwr(A,2) a2 = 2. 5. 6. 9. 6. 10. 11. 7. 12. -->a3=maxpluspwr(A,3) a3 = 11. 8. 12. 15. 11. 16. 17. 13. 18. -->maxplustrace(A) ans = 6. -->maxplustrace(a2) ans = 12. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

14

Pendahuluan..

-->maxplustrace(a3) ans = 18. Misalkan (S, +, ×) adalah semiring komutatif dengan elemen netral 0 dan 1. Semimodul M atas S adalah semigrup komutatif (M, +) bersama operasi perkalian skalar • : S×M → M , dituliskan sebagai (α, x) 7→ α•x yang memenuhi aksioma berikut: ∀α, β ∈ S dan ∀x, y ∈ M berlaku: i) α • (x + y) = α • x + α • y, ii) (α + β) • x = α • x + β • x, iii) α • (β • x) = (α × β) • x, iv) 1 • x = x, v) 0 • x = 0. n×1 Suatu elemen dari suatu semimodul dinamakan vektor. Suatu contoh, Rmax adalah semin×1 n modul atas Rmax , dalam hal ini Rmax cukup ditulis Rmax . Elemen ke-j dari suatu vektor x ∈ Rnmax dinotasikan oleh xj dan ditulis juga sebagai [x]j . Vektor di Rnmax dengan semua elemennya sama dengan e dinamakan vektor satuan dinotasikan oleh u ditulis sebagai [u]j = e untuk semua j ∈ n. Untuk setiap α ∈ Rmax vektor α⊗u adalah vektor yang semua elemennya sama dengan α. Untuk setiap j ∈ n kolom ke-j dari matriks satuan E(n, n) dinamakan vektor basis ke-j dari Rnmax dan dinotasikan oleh ej . Jadi elemen ke-j dari vektor ej sama dengan e sedangkan elemen lainnya sama dengan ǫ. Berikut ini diberikan suatu relasi pada suatu himpunan yang berkaitan dengan urutan dalam himpunan tersebut. Pengertian dari relasi ini dan beberapa sifat akan berguna dalam kajian aljabar max-plus Rmax .

Definisi 1.2.1 Suatu relasi ≤ pada suatu himpunan P dinamakan urutan parsial pada P bila untuk semua a, b, c ∈ P memenuhi 1. a ≤ a, sifat refleksif, 2. bila a ≤ b dan b ≤ a, maka a = b, sigat antisimetri, 3. bila a ≤ b dan b ≤ c, maka a ≤ c, sifat transitif.

Selanjutnya bila berlaku a ≤ b atau b ≤ a, maka a dan b dikatkan dapat-dibandingkan (comparable). Penulisan a ≤ b juga bisa ditulis b ≥ a. Bila a ≤ b dan a 6= b, maka ditulis dengan a ≺ b. Bila setiap dua elemen dari P dapat-dibandingkan, maka urutan parsial ≤ dinamakan urutan total. Berikut ini diberikan suatu teorema yang berkaitan dengan pengertian urutan parsial pada suatu semigrup komutatif idempoten. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

15


Teorema 1.2.2 Diberikan suatu semigrup komutatif idempoten (S, +). Bila pada S didefinisikan suatu relasi ≤ oleh a ≤ b ⇔ a + b = b, maka relasi ≤ adalah urutan parsial pada S. Bukti Diberikan sebarang elemen a, b dan c di S, maka 1. karena S idempoten, maka a + a = a ⇔ a ≤ a, 2. bila a ≤ b dan b ≤ a, maka a + b = b dan b + a = a dan karena S komutatif, maka a + b = b + a = a, jadi a = b, 3. bila a ≤ b dan b ≤ c, maka a + b = b dan b + c = c dan karena S mempunyai sifat assosiatif, maka a + c = a + (b + c) = (a + b) + c = b + c = c, jadi a ≤ c.

Contoh 1.2.4 Dalam Rmax relasi ≤max yang didefinisikan sebagai x ≤max y ⇔ x ⊕ y = y

(1.10)

adalah urutan parsial sebab (Rmax , ⊕) adalah semigrup komutatif idempoten disertai dengan relasi ≤max yang diberikan dalam 1.10 dan berdasarkan Teorema 1.2.2, maka relasi ≤max pada Rmax adalah urutan parsial. Selanjutnya untuk setiap x, y ∈ Rmax , berlaku x ⊕ y = max{x, y} = y ⇔ x ≤max y atau y ⊕ x = max{x, y} = x ⇔ y ≤max x. Jadi relasi ≤max terurut total. Catatan bahwa, relasi ≤max pada Rmax ekivalen dengan relasi ≤ pada R ∪ {−∞}, sebab x ≤max y ⇔ x ⊕ y = y ⇔ max(x, y) = y ⇔ x ≤ y.

Contoh 1.2.5 Dalam Rm×n max relasi ≤max yang didefinisikan sebagai A ≤max B ⇔ A ⊕ B = B ⇔ [A ⊕ B]i,j = [B]i,j ⇔ [A]i,j ≤max [B]i,j , ∀i ∈ m dan ∀j ∈ n (1.11) m×n adalah urutan parsial sebab (Rmax , ⊕) adalah semigrup komutatif idempoten disertai dengan relasi ≤max yang diberikan dalam 1.11 dan berdasarkan Teorema 1.2.2, maka relasi ≤max pada Rm×n max adalah urutan parsial. Urutan parsial ini bukan urutan total, sebab untuk dua matriks A dan B masing-masing berukuran 2 × 2 sebagai mana berikut 1 3 1 2 M 0 3 0 3 1 2 . = , maka A ⊕ B = ,B = A= 4 4 4 1 3 4 4 1 3 4

Terlihat bahwa A ⊕ B 6= B dan B ⊕ A 6= A.


16

Pendahuluan..

Dalam Contoh 1.2.5 bila ukuran baris m = n dan ukuran kolom n = 1, maka didapat Rnmax . Sehingga dengan relasi ≤max pada Rnmax yang diberikan oleh x ≤max y ⇔ x ⊕ y = y ⇔ [x ⊕ y]j = [y]j ⇔ [x]j ≤max [y]j , ∀j ∈ n juga merupakan relasi urutan parsial yang bukan urutan total, sebab ada x, y ∈ R2max dengan 2 0 2 0 2 x= ,y = , berlaku x ⊕ y = ⊕ = . −1 3 −1 3 3 Terlihat bahwa x ⊕ y 6= y dan y ⊕ x 6= x. Sifat berikut mengenai perkalian matriks denga vektor dalam Rmax yang dikaitkan dengan relasi urutan parsial. n Teorema 1.2.3 Diberikan matriks A ∈ Rm×n max . Bila vektor x, y ∈ Rmax dengan x ≤max y, maka A ⊗ x ≤max A ⊗ y.

Bukti Untuk sebarang elemen x, y ∈ Rnmax dengan x ≤max y berlaku, maka x ⊕ y = y ⇔ A ⊗ (x ⊕ y) = A ⊗ y ⇔ (A ⊗ x) ⊕ (A ⊗ y) = A ⊗ y ⇔ A ⊗ x ≤max A ⊗ y.

Contoh 1.2.6 Diberikan matriks 7 5 1 2 . ,y = dan vektor x = A= 8 6 3 4 Jelas bahwa x ≤max y dan 10 7 1 2 8 5 1 2 . = ⊗ dan A ⊗ y = = ⊗ A⊗x= 12 8 3 4 10 6 3 4 Terlihat bahwa A ⊗ x ≤max A ⊗ y.

Perintah dalam Scilab untuk Contoh 1.2.6: c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

17


-->A=[1 2;3 4] A = 1. 2. 3. 4. -->x=[5;6] x = 5. 6. -->y=[7;8] y = 7. 8. -->maxplusotimes(A,x) <= maxplusotimes(A,y) ans = T T Suatu pemetaan f dari Rnmax ke Rnmax dikatakan affin bila f (x) = A ⊗ x ⊕ b untuk beberapa n×n A ∈ Rmax dan b ∈ Rnmax . Bila b = ε, maka f dinamakan linear. Suatu relasi berulang x(k + 1) = f (x(k)) untuk k ∈ N dinamakan affin atau linear bila f suatu pemetaan affin atau linear. n×m Suatu matriks A ∈ Rmax dinamakan reguler bila disetiap baris A memuat setidaknya satu elemen tidak sama dengan ε. Kereguleran adalah suatu kondisi teknik belaka, bila A tidak reguler, maka A memuat baris redundan dan setiap sistem yang mempunyai model x(k + 1) = A ⊗ x(k) juga bisa dimodelkan oleh versi redundan dari natriks A yang mana semua baris redundan dan kolom terkait diabaikan. n×n Suatu matriks A ∈ Rmax dikatakan matriks segitiga bawah bila ai,j = ǫ untuk 1 ≤ i ≤ j ≤ n. Matriks A dikatakan dikatakan matriks segitiga atas bila matriks transpose A⊤ merupakan matriks segitiga bawah. Untuk himpunan terhitung (countable), operator max harus dipahami sebagai suatu supremum. Secara formal, misalkan {ai |i ∈ N} adalah himpunan terhitung dengan ai ∈ Rmax , maka ∞ M def M def ai = ai = sup ai . i≥0

i=0

i≥0

Dalam aljabar max-plus mudah diselidiki aturan Fubini, yaitu untuk {ai,j ∈ Rmax |i, j ∈ N}, MM MM ai,j = ai,j . (1.12) i≥0 j≥0

Bahkan, untuk setiap k, j ≥ 0, bila ak,j ≤

j≥0 i≥0

L

ai,j , maka

i≥0

M j≥0

ak,j ≤

MM

ai,j ,

j≥0 i≥0


18

Pendahuluan..

untuk k ≥ 0, sebagai akibat MM k≥0 j≥0

ak,j ≤

MM

ai,j .

j≥0 i≥0


Bab

2

Teori Spektral Dalam bab ini dibahas teori spektral dari matriks atas semiring Rmax . Dalam Bagian 2.1 dikaji hubungan diantara graf dan matriks atas semiring Rmax , dalam Bagian 2.2 dibahas pengertian nilai karakteristik dan vektor karakteristik dari suatu matriks persegi atas semiring Rmax selanjutnya dalam Bagian 2.3 dibahas suatu penyelesaian dari persamaan linear dalam Rmax .

2.1

Matriks dan Graf

n×n Misalkan matriks A ∈ Rmax , suatu graf berarah dari matriks A adalah G(A) = (E, V ). Graf G(A) mempunyai n titik, himpunan semua titik dari G(A) dinyatakan oleh V . Suatu garis dari titik j ke titik i ada bila ai,j 6= ε, garis ini dinotasikan oleh (j, i). Himpunan semua garis dari graf G(A) dinotasikan oleh E. Bobot dari garis (j, i) adalah nilai dari ai,j yang dinotasikan oleh w(j, i) = ai,j ∈ Rmax . Bila ai,j = ε, maka garis (j, i) tidak ada. Suatu barisan garis (i1 , i2 ), (i2 , i3 ), . . . , (il−1 , il ) dari suatu graf dinamakan suatu path. Suatu path dikatakan elementer bila tidak ada titik terjadi dua kali dalam path tsb. Suatu sirkuit adalah path elementer tertutup, yaitu (i1 , i2 ), (i2 , i3 ), . . . , (il−1 , i1 ). Bobot dari suatu path p = (i1 , i2 ), (i2 , i3 ), . . . , (il−1 , il ) dinotasikan oleh |p|w dan diberikan oleh |p|w = w(i1 , i2 )+w(i2, i3 )+. . .+w(il−1, il ) = (ai2 ,i1 +ai3 ,i2 +. . .+ail ,il−1 ), sedangkan panjang dari path p atau banyaknya garis dalam path p dinotasikan oleh |p|l . Bobot rata-rata dari path p adalah bobot dari p dibagi oleh banyaknya garis dalam path p, yaitu

(ai2 ,i1 + ai3 ,i2 + . . . + ail ,il−1 ) |p|w = . |p|l (l − 1) Sirkuit rata-rata adalah bobot rata-rata dari suatu sirkuit. Sebarang sirkuit dengan sirkuit rata-rata maksimum dinamakan sirkuit kritis. Suatu graf dikatakan strongly connected bila suatu path ada untuk setiap titik i ke setiap titik j. Bila graf G(A) adalah strongly connected, maka matriks A juga dikatakan irreducible (taktereduksi). Untuk suatu matriks 19

20

Teori Spektral..

n×n persegi A ∈ Rmax , matriks A+ didefinisikan sebagai + def

A =

∞ M

A⊗i .

(2.1)

i=1

Catatan bahwa, elemen [A⊗k ]i,j adalah bobot maksimum dari semua path dengan panjang k dari titik j ke titik i. Jadi elemen [A+ ]i,j adalah bobot maksimum dari path-path dengan panjang sebarang dari titik j ke titik i, sehingga didapat [A+ ]i,j = max{[A⊗k ]i,j | k ≥ 1}. Perhatikan bahwa dalam Persamaan (2.1) matriks pangkat A⊗i , i = 1, 2, . . . , +∞. Berikut ini diberikan suatu teorema mengenai A+ dengan matriks pangkat A⊗i berhenti untuk i = n dengan n adalah ukuran dari matriks A yaitu banyaknya baris dan banyaknya kolom dari A. n×n Teorema 2.1.1 Misalkan A ∈ Rmax sedemikian hingga setiap sirkuit di G(A) mempunyai bobot sirkuit rata-rata kurang atau sama dengan 0. Maka

A+ =

∞ M

n×n A⊗i = A ⊕ A⊗2 ⊕ . . . ⊕ An ∈ Rmax .

(2.2)

i=1

Bukti Karena A berukuran n × n, maka semua path di G(A) dari i ke j dengan panjang lebih besar dari n merupakan setidaknya satu sirkuit dan suatu path dari i ke j dengan panjang setidaknya n. Oleh karena sirkuit di G(A) mempunyai bobot takpositif, didapat [A+ ]j,i ≤ max{[A⊗i ]j,i | i ∈ n}. Hal ini menyimpulkan bahwa A+ = A ⊕ A⊗2 ⊕ . . . ⊕ An . Contoh 2.1.1 Diberikan matriks 

 5 ε 5 A =  ε 6 3 . 6 6 3

Gambar graf dari matriks A ini diberikan dalam Gambar 2.1. Dalam gambar ini ada lima sirkuit yaitu (1, 1); (1, 3), (3, 1); (3, 3); (2, 3), (3, 2) dan (2, 2). Masing-masing sirkuit mempunyai sirkuit rata-rata 5/1 = 5, (6 + 5)/2 = 11 , 3/1 = 3, (6 + 3)/2 = 92 dan 6/1 = 6. 2 Terlihat bahwa sirkuit rata-rata maksimum adalah 6 terjadi pada sirkuit (2, 2). Jadi sirkuit kritis dari graf G(A) adalah sirkuit (2, 2). Juga tampak bahwa graf G(A) adalah strongly connected. Jadi matriks A taktereduksi.


21

Matriks dan Graf..

5

6

5 1

2

3

6

6

3

3 Gambar 2.1: Graf G(A)

Contoh 2.1.2 Diberikan matriks 

  A=  

ε ε ε ε ε

5 ε ε 3 ε

3 2

ε 2 ε 4 ε



  .  

8

3b

2 7

b

4

2 ε ε ε ε

2b

5

1b

ε 8 ε 7 4

4 b

4

5

Gambar 2.2: Graf G(A) tanpa sirkut

Gambar 2.2 adalah graf dari matriks A, terlihat graf G(A) tidak memuat satupun sirkuit, dengan demikian sirkuit rata-rata maksimum tidak ada. Perhatikan juga bahwa graf G(A) tidak strongly connected. Jadi matriks A adalah tereduksi. Sirkuit rata-rata maksimum dari suatu graf G(A) adalah suatu bagian penting dari matriks A, sebab sirkuit rata-rata maksimum berkaitan dengan suatu karakteristik dari matriks A. Pada Contoh 2.1.2, graf G(A) tidak memuat satupun sirkuit. Bagaimanapun hal ini untuk matriks A berukuran yang agak besar tentunya mengecek graf G(A) tidak memuat satupun sirkuit tidaklah mudah. Oleh karena itu akan diberikan suatu sifat yang berkaitan dengan masalah ini. Sifat yang akan dibahas berhubungan dengan matriks pangkat. Oleh karena itu sedikit dibahas ulang mengenai matriks pangkat. Untuk matriks persegi A berukuran n × n, maka A⊗2 = A ⊗ A. Elemen elemen ke-i, j dari A adalah [A2 ]i,j = max{ai,k +ak,j } menyatakan bobot maksimum k

dari semua path dengan panjang 2 dari titik j ke titik i dalam graf G(A). Secara umum, [A⊗k ]i,j adalah bobot maksimum dari semua path dengan panjang k dari titik j ke titik i dalam graf G(A). c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

22

Teori Spektral..

Teorema 2.1.2 Misalkan matriks A berukuran n × n. Graf G(A) tidak memuat satupun sirkuit bila dan hanya bila A⊗k = ε (n, n), ∀k ≥ n. Bukti Misalkan G(A) tidak memuat sirkuit. Karena G(A) mempunyai n titik, maka tidak ada path dengan panjang k ≥ n. Jadi A⊗k = ε (n, n), ∀k ≥ n. Selanjutnya, misalkan A⊗k = ε(n, n), ∀k ≥ n, yaitu tidak ada path dalam G(A) dengan panjang k ≥ n. Karena sirkuit selalu bisa diperluas ke sebarang path yang panjang, hal berakibat bahwa tidak ada sirkuit dalam G(A). Contoh 2.1.3 Diberikan lagi matriks pada Contoh  ε 5 13 ε ε 6  A⊗2 =  ε ε ε ε ε 11 ε ε ε

dan

A⊗4

 ε ε  = ε ε ε

2.1.2, maka    ε ε 13 ε 7 ε 7 ε ε ε ε ε  ε ε    ⊗3 ε ε ε ε ε  ε ε , A =    ε ε 9 ε ε  ε 5 ε ε ε ε ε ε ε

  ε ε 11 ε ε ε ε ε ε ε   ⊗5 ε ε ε ε ε , A =   ε ε ε ε ε ε ε ε ε ε

ε ε ε ε ε

ε ε ε ε ε

ε ε ε ε ε

 ε ε  ε  = ε (5, 5). ε ε

Terlihat bahwa hanya ada 5 pasang titik dengan panjang 2. Misalnya dari titik 3 ke 1 dengan panjang maksimum 13, yaitu 3 → 2 → 1. Dan hanya ada 3 pasang titik dengan pamjang 3. Misalnya dari titik 3 ke titik 1 dengan panjang maksimum 13 yaitu : 3 → 2 → 4 → 1. Berikut ini diberikan keujudan dari sirkuit rata-rata maksimum untuk matriks persegi taktereduksi. Sebelum membahas sifat ini, diberikan notasi λ(A) yang menyatakan nilai sirkuit rata-rata maksimum dari suatu matriks persegi A. Teorema 2.1.3 Bila A ∈ Rn×n taktereduksi, maka ada λ(A) yang diberikan oleh n n M M tr A⊗k λ(A) = , dengan tr(A) = ai,i . k i=1 k=1 c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

(2.3)

23

Matriks dan Graf..

Bukti Perhatikan bahwa

n M ⊗k tr(A ) = A i,i k

i=1

menyatakan bobot sirkuit maksimum dari semua sirkuit dengan panjang k dalam G(A), dengan demikian bila dibagi oleh k merupakan bobot rata-rata maksimum dari sirkuit dengan panjang k. Oleh karena itu untuk k = 1, 2 . . . , n dan bila C(A) adalah himpunan semua sirkuit elementer dari graf G(A) didapat didapat n |p|w M tr A⊗k λ(A) = max = . p∈C(A) |p|l k k=1 Dalam Scilab perintah-perintah untuk menentukan sirkuit rata-rata maksimum, lintasan kritis dan menguji kondisi strongly connected dari suatu graf G(A) adalah sebagai berikut: -->A=[5 -%inf 5;-%inf 6 3;6 6 3] A = 5. -Inf 5. -Inf 6. 3. 6. 6. 3. // maximum cycle rata-rata dari matriks A (sirkuit rata-rata maksimum) -->mcm=maxplusmcm(A) mcm = 6. // cek graf G(A) strongly connected -->s = maxplusscg(A) s = T // T menunjukkan true, jadi benar bahwa G(A) strongly connected. // menentukan lintasan kritis (sirkuit kritis). -->[l,d,x]=maxplusccir(A) x = 2. // lintasan kritis dari titik 2 kembali ke 2 d = 1. // banyaknya garis dalam lintasan kritis. l = 6. // maximum cycle rata-rata. // // Contoh berikut menunjukkan bahwa sirkuit rata-rata maksimum // tidak ada, sebab G(A) tidak memuat sirkuit. -->A = [-%inf 5. -%inf 2. -%inf; -%inf -%inf 8. -%inf 2. ; c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

24

Teori Spektral..

-%inf -%inf -%inf -%inf -%inf; -%inf 3. 7. -%inf 4.; -%inf -%inf 4. -%inf -%inf]; -->maxplusmcm(A) !--error 10000 No any circuit of The Graph G(A) at line 13 of function maxplusmcm called by : maxplusmcm(A) // // bisa dicek bahwa A pangkat 5 sama dengan matriks nol // -->maxpluspwr(A,5) ans = - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf - Inf

2.2

Nilai karakteristik dan Vektor karakteristik

Pengertian nilai-karakteristik dan vektor-karakteristik yang bersesuaian dari suatu matriks persegi A berukuran n × n sebagaimana dijumpai dalam aljabar linear biasa juga dijumpai dalam aljabar maxplus, yaitu bila diberikan suatu persamaan: A⊗x=λ⊗x dalam hal ini masing-masing vektor x ∈ Rnmax dan λ ∈ R dinamakan vektor-karakteristik dan nilai-karakteristik dari matriks A dengan vektor x 6= (ε, ε, . . . , ε)⊤ . Suatu algoritma untuk memperoleh vektor-karakteristik dan nilai karakteristik dari matriks persegi A bisa ditemui di [4]. Algorithma untuk menentukan nilai-karakteristik dan vektor-karakteristik n×n dari matriks A ∈ Rmax dilakukan secara berulang dari bentuk persamaan linear x(k + 1) = A ⊗ x(k), k = 0, 1, 2, . . . .

(2.4)

Perilaku periodik dari Persamaan (2.4) baik untuk matriks A yang taktereduksi maupun yang tereduksi erat kaitannya dengan apa yang dinamakan vektor waktu sikel yang didefinisikan sebagai: x(k) . (2.5) lim k→∞ k Limit ini ada untuk setiap keadaan awal x(0) 6= (ε, ε, . . . , ε)′ dan untuk matriks dalam Persamaan (2.4) yang tereduksi selalu bisa dijadikan suatu bentuk blok matriks segitiga c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

25

Nilai karakteristik dan Vektor karakteristik..

atas, hal ini bisa dilihat di [1] yang diberikan oleh bentuk: 

A1,1 A1,2  ε A2,2    ε ε ε ε

. . . A1,q . . . A2,q .. .. . . . . . Aq,q

    

dan untuk setiap i = 1, 2, . . . , q, Ai,i berukuran qi × qi adalah matriks tak tereduksi dengan nilai karakteristik λi . Dalam hal yang demikian vektor waktu sikel diberikan oleh 

x(k)   = k→∞ k  lim

λ1 λ2 .. . λq



  , 

dengan 

  λi =  

λi λi .. . λi

    

dan vektor λ i berukuran qi × 1. Keujudan nilai karakteristik dari matriks persegi A diberikan dalam teorema berikut. Teorema 2.2.1 Bila untuk sebarang keadaan awal x(0) 6= ε sistem Persamaan (2.4) memenuhi x(p) = c ⊗ x(q) untuk beberapa bilangan bulat p dan q dengan p > q ≥ 0 dan beberapa bilangan real c , maka 

x(k)   = k→∞ k  lim

λ λ .. . λ



  , 

c . Selanjutnya λ adalah suatu nilai karakteristik dari matriks A dengan p−q vektor karakteristik diberikan oleh

dengan λ =

p−q M (p−q−i) λ⊗ ⊗ x(q + i − 1) . v= i=1


26

Teori Spektral..

Bukti : Misalkan l = p − q, didapat

i

x(k) x(q + il) c⊗ ⊗ x(q) = lim = lim i→∞ q + il i→∞ k→∞ k q + il ! i c⊗ x(q) = lim ⊗ lim i→∞ q + il i→∞ q + il x(q) ic ⊗ lim = lim i→∞ q + il i→∞ q + il c c = ⊗0 = ⊗0 l p−q lim

dengan vektor 

  0= 

Jadi bila λ =

0 0 .. . 0



  . 

c , maka vektor waktu sikel adalah p−q



x(k)   = k→∞ k  lim

λ λ .. . λ



  . 

Selanjutnya bila p−q M (p−q−i) λ⊗ ⊗ x(q + i − 1) , v= i=1


27


maka A⊗v = A⊗

! p−q M (p−q−i) λ⊗ ⊗ x(q + i − 1) i=1

p−q

=

M

(p−q−i) A ⊗ λ⊗ ⊗ x(q + i − 1)

M

λ⊗

(p−q−i)

M

λ⊗

(p−q−i)

i=1 p−q

=

⊗ (A ⊗ x(q + i − 1))

i=1 p−q

=

⊗ x(q + i)

i=1 p−q+1

=

M

λ⊗

(p−q−j+1)

⊗ x(q + j + 1)

j=2

= λ⊗

p−q+1

M

λ

⊗(p−q−j)

⊗ x(q + j − 1)

j=2

p−q

= λ⊗

M

λ

⊗(p−q−j)

⊗ x(q + j − 1)

j=1

!

!

= λ ⊗ v.

Persamaan yang terakhir diperoleh dari x(p) = λ⊗

(p−q)

⊗ x(q),

yang berakibat bahwa λ⊗

−1

⊗ x(p) = λ⊗

(p−q−1)

⊗ x(q).

Dari hasil Teorema (2.2.1), Algoritma berikut dapat digunakan untuk menentukan nilai karakteristik sekaligus vektor karakteristik dari suatu matriks persegi A. 1. Mulai dari sebarang vektor awal x(0) 6= ε . 2. Iterasi persamaan (2.4) sampai ada bilangan bulat p > q ≥ 0 dan bilangan real c sehingga suatu perilaku periodik terjadi, yaitu x(p) = c ⊗ x(q). 3. Hitung nilai-karakteristik λ =

c . p−q

4. Hitung vektor-karakteristik v =

p−q L i=1

λ⊗(p−q−i) ⊗ x(q + i − 1) .


28

Teori Spektral..

Contoh 2.2.1 Diberikan matriks tereduksi A1,1 A1,2 A= ε A2,2 dengan A1,1 = 2, A1,2 = [2 ε] dan A2,2 =

1 4 2 2

Jelas bahwa matriks A1,1 dan A2,2 matriks diberikan oleh  2  A= ε ε Untuk keadaan awal

, ε=

ε ε

.

taktereduksi. Dengan demikian matriks A  2 ε 1 4 . 2 2

 0 x(0) =  0  , 0

didapat evolusi keadaan 



         0 2 6 8 12  0  ,  4  ,  6  ,  10  ,  12  , . . . 0 2 6 8 12

Terlihat bahwa x(2) = 6⊗x(0), dalam hal ini q = 0, p = 2 dan c = 6. Jadi nilai karakteristik dari matriks A diberikan oleh 6 c = =3 λ= p−q 2−0 dan vektor karakteristiknya adalah v = =

2−0 M

i=1 2 M

λ⊗ 3⊗

(2−0−i)

(2−i)

⊗ x(0 + i − 1)

⊗ x(i − 1)

i=1



0 1 = (3⊗ ⊗  0 0    3  3 ⊕ = 3   3  = 4 . 3





 2 ) ⊕ (3⊗0 ⊗  4 ) 2  2 4  2


29


Cek hasil yang didapat  Contoh 2.2.2  5  A= ε 6

       2 2 ε 3 6 3  ε 1 4  ⊗ 4  =  7  = 3 ⊗ 4 . ε 2 2 3 6 3

Diberikan matriks          ε 5 0 0 5 11 6 3  , untuk x(0) =  0  didapat  0  ,  6  ,  12  , . . . 6 3 0 0 6 12

Terlihat q = 1 dan p = 2, sebab



   11 5 6    12 = 6 ⊗ 6  dan λ = x(2) = 6 ⊗ x(1), yaitu = 6. 2−1 12 6

Sesuai langkah 4 dalam algorithma didapat vektor-karakteristik v = x(1).

Misalkan C(A) adalah himpunan semua sirkuit elementer dari graf G(A) dan |p|w p∈C(A) |p|l

λ = max

(2.6)

menyatakan bobot maksimum dari sirkuit rata-rata. Perhatikan lagi matriks A+ yang didefinisikan oleh persamaan (2.1), biasanya A+ adalah divergen, untuk kasus ini adalah memungkinkan untuk mempertimbangkan perilaku asimtotik dengan menggunakan matriks A+ λ . Bila λ sebagi mana diberikan dalam (2.6), maka matriks Aλ didefinisikan sebagai def

Aλ = λ⊗−1 ⊗ A.

(2.7)

Dalam hal ini matriks Aλ merujuk sebagai matriks ternormalkan. Disini jelas bahwa bobot maksimu sirkuit rata-rata dari G(Aλ ) adalah nol. Sehingga berdasarkan Teorema 2.2 didapat n M + ⊗2 ⊗n Aλ = A⊗i (2.8) λ = Aλ ⊕ Aλ ⊕ . . . ⊕ Aλ . i=1

Selanjutnya graf lintasan kritis dari matriks A dinotasikan oleh G c (A). Dalam hal ini graf G c (A) tepat sama dengan graf G c (Aλ ) kecuali untuk bobotnya, sehingga untuk semua titik η di graf G c (Aλ ), didapat [A+ (2.9) λ ]η,η = 0 sebab setiap titik di graf kritikal termuat didalam suatu sirkuit dan setiap sirkuit dari graf kritikal mempunyai bobot sama dengan nol. Selanjutnya didefinisikan M def A∗λ = E ⊕ A+ A⊗i (2.10) λ = λ . i≥0


30

Teori Spektral..

Sehingga didapat + ∗ A+ λ = Aλ ⊗ (E ⊕ Aλ ) = Aλ ⊗ Aλ .

(2.11)

Misalkan [B]•,k kolom ke-k dari matriks B, sehingga dari Persamaan (2.10) didapat [A∗λ ]•,η = [E ⊕ A+ λ ]•,η .

(2.12)

Dari Persamaan (2.12), elemen ke-i dari vektor [A∗λ ]•,η memenuhi ε ⊕ [A+ ∗ + λ ]i,η untuk i 6= η, [Aλ ]i,η = [E ⊕ Aλ ]i,η = 0 ⊕ [A+ λ ]i,η untuk i = η. Dari Persamaan (2.9) dan untuk η adalah titik di G c (A), didapat ∗ [A+ λ ]•,η = [Aλ ]•,η .

Sehingga dengan menggunakan Persamaan (2.11) didapat [Aλ ⊗ A∗λ ]•,η = [A∗λ ]•,η Hal ini memberikan Aλ ⊗ [A∗λ ]•,η = [A∗λ ]•,η atau ekivalen dengan A ⊗ [A∗λ ]•,η = λ ⊗ [A∗λ ]•,η . Hal ini menunjukkan bahwa nilai-karakteristik dari matriks A adalah λ dan kolom ke-η c dari matriks A+ λ , merupakan vektor karakteristik dari A untuk semua η di graf G (A). + Menghitung nilai-karakteristik, vektor karakteristik dan Aλ dalam Scilab sebagai berikut: -->A=[5 -%inf 5;-%inf 6 3;6 6 3] A = 5. - Inf 5. - Inf 6. 3. 6. 6. 3. -->[l,v,d]=maxplusmaxalgol(A) // menghitung nilai-karakteristik dan d = // vektor karakteristik 1.// nilai dari d=p-q v = 5. 6. 6. // v adalah vektor-karakteristik l = 6. // nilai c dalam algorithma yang merupakan nilai-karakteristik. // menghitung maksimum rata-rata sikel (lambda) -->[mcm] = maxplusmcm(A) mcm = c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

31


6. // lambda (nilai-karakteristik A) // menentukan lintasan kritis -->[l,d,x] = maxplusccir(A) x = 2. // lintasan kritis d = 1. // panjang lintasan kritis l = 6. // lambda -->[ap,lam] = maxplusaplus(A) lam = 6. ap = - 1. - 1. - 1. - 3. 0. - 3. 0. 0. - 1. // ap adalah matriks A lambda plus, lam adalah lambda. // lintasan kritis dari G(A) adalah 2 ke 2, jadi // kolom ke-2 dari matriks ap adalah vektor-karakteristik dari A -->isequal(maxplusotimes(A,ap(:,2)),maxplusotimes(lam,ap(:,2))) ans = T Secara umum, vektor karakteristik dari matriks persegi yang besesuaian dengan nilai karakteristik tidaklah tunggal. Hal ini ditunjukkan dalam contoh berikut. Contoh 2.2.3

dan

1 0 0 1

1 0 0 1

⊗

⊗

0 0

−1 0

=

1 1

=

0 1

=1⊗

0 0

=1⊗

−1 0

.

Kedua vektor karakteristik tidak sebanding, sebab bila 0 −1 =a⊗ untuk beberapa a ∈ R 0 0 maka didapat 0 = a − 1 yaitu a = 1 dan 0 = a suatu hal yang tidak mungkin. Intepretasi dari nilai-karakteristik dan vektor-karakteristik dalam Contoh 2.1.1 adalah sebagai berikut: Misalkan ada tiga aktifitas yang beroperasi secara periodik. Diasumsikan bahwa aktifitas ini beroperasi tidak secara bebas dan output dari satu aktifitas menjadi input aktifitas tertentu lainnya. Satu aktifitas hanya bisa dimulai bila beberapa aktifitas c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

32

Teori Spektral..

tertentu lainnya sudah menyelesaikan pekerjaannya dan mengirimkan hasilnya ke aktifitas yang ditentukan. Jadi satu aktifitas tertentu hanya bisa memulai kegiatannya pada saat yang ke-(k + 1) bila beberapa aktifitas yang lainnya telah menyelesaikan kegiatannya pada saat yang ke-k dan mengirimkan hasilnya keaktifitas tsb. Elemen aij dari matriks A menunjukkan waktu tunggu dari aktifitas i untuk memulai kegiatannya saat yang ke-(k + 1) setelah aktifitas j menyelesaikan kegiatannya dan mengirimkan hasilnya ke aktifitas i pada saat yang ke-k. Bila elemen aij = ε, maka hal ini menunjukkan bahwa aktifitas i tidak bergantung pada aktifitas j. Selanjutnya evolusi sistem dalam Contoh 2.1.1 diberikan oleh persamaan x(k + 1) = A ⊗ x(k), k = 0, 1, 2, . . . .

(2.13)

Bila dipilih x(0) adalah vektor-karakteristik dari matriks A, maka sistem (2.13) akan beroperasi secara periodik dengan periode sebesar nilai-karakteristik λ = 6. Hal ini sesuai dengan bentuk persamaan berikut : x(k + 1) = A ⊗ x(k) = λ⊗

(k+1)

⊗ x(0), k = 0, 1, 2, . . . .

Sehingga didapat barisan aktifitas x(k) :         0 6 12 18  1  ,  7  ,  13  ,  19  , . . . 1 7 13 19 x(0),

x(1),

x(2),

x(3),

...

Evolusi dari Persamaan 2.14 dapat dilakukan dalam Scilab sebagi berikut: -->A=[5 -%inf 5;-%inf 6 3;6 6 3] A = 5. -Inf 5. -Inf 6. 3. 6. 6. 3. -->x0=[0;1;1] x0 = 0. 1. 1. -->X = maxplussys(A,x0,3) X = 0. 6. 12. 18. 1. 7. 13. 19. 1. 7. 13. 19. // untuk menentukan vektor waktu sikel sebagai berikut -->vec=maxplusctv(A) c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

(2.14)

33

Penyelesaian Persamaan Linear..

vec

=

6. 6. 6. // Terlihat semua komponen vektor waktu sikel // bernilai sama yaitu 6 yang menunjukkan // nilai karakteristik dari matriks A.

2.3

Penyelesaian Persamaan Linear

Kekurangan dari aljabar max-plus adalah tidak adanya invers additive, hal ini menyulitkan untuk menyelesaikan sistem persamaan linear seperti A ⊗ x = b. Sebagaimana dalam aljabar biasa penyelesaian persamaan A ⊗ x = b tidak selalu ada, bila ada hal ini belum tentu tunggal. Pada bagian ini juga akan dibahas bentuk yang lainnya dari persamaan linear.

2.3.1

Sub-Penyelesaian Terbesar

Sebagai motifasi, diberikan persamaan dimensi satu a + x = b,

(2.15)

dengan a, b adalah bilangan real tak negatif. Jelas bahwa bila a > b, maka Persamaan (2.15) tidak mempunyai penyelesaian. Sebaliknya bila a ≤ b, maka Persamaan (2.15) mempunyai penyelesaian x = b − a. Begitu juga untuk persamaan berikut a ⊕ x = b,

(2.16)

dengan a, b ∈ R . Jelas bahwa bila a > b, maka Persamaan (2.16) tidak mempunyai penyelesaian. Sebaliknya bila a ≤ b, maka Persamaan (2.16) mempunyai penyelesaian x = b. Perhatikan bahwa Persamaan (2.15) dapat ditulis dalam bentuk a ⊗ x = b. Selanjutnya dibahas a diganti oleh matriks A. Pertama, kasus untuk matriks A tidak harus matriks persegi. Untuk matriks A ini, selalu didapat apa yang dikenal dengan subpenyelesaian terbesar dari A ⊗ x = b. Sub-penyelesaian terbesar adalah vektor terbesar x yang memenuhi A ⊗ x ≤ b. Penyelesaian ini dinotasikan oleh x∗ (A, b). Sub-penyelesaian terbesar tidak harus merupakan suatu penyelesaian dari A ⊗ x = b. 1 1 ε . ,b = A= 2 3 4 Persamaan A ⊗ x = btidak punya penyelesaian, sebab bila punya penyelesaian berarti ada p 1 ε p 1 x = sehingga ⊗ = . Didapat p = 0 dan max{3, 4 + q} = 2, q 3 4 q 2 terlihat bahwa tidak akan ada q ∈ Rmax sehingga max{3, 4 + q} = 2. Jadi A ⊗ x = b c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

34

Teori Spektral..

tidak punya penyelesaian. Dilain pihak secara umum, pertaksamaan A ⊗ x ≤ b selalu penya penylesaian. Hal ini bisa ditunjukkan bahwa untuk x = ε didapat A ⊗ x = ε ≤ b. Contoh-contoh diatas menjelaskan bahwa A⊗x = b belum tentu punya penyelesaian, dilain pihak A⊗x ≤ b selalu punya penyelesaian, bahkan penyelesaian terbesar x yang memenuhi A ⊗ x ≤ b diberikan oleh teorema berikut. Teorema 2.3.1 Misalkan A ∈ Rm×n max adalah suatu matriks yang setiap kolomnya memuat setidaknya satu elemen tidak sama dengan ε dan b ∈ Rm max , maka [x∗ (A, b)]j = min{bi − ai,j | i ∈ m, dan ai,j > ε}. Bukti Perhatikan bahwa A ⊗ x ≤ b adalah ekivalen dengan masing-masing berikut: 1. untuk semua i dan j, ai,j + xj ≤ bi 2. untuk semua i dan j, xj ≤ bi − ai,j atau ai,j = ε 3. untuk semua j, xj ≤ min{bi − ai,j | i ∈ m dan ai,j > ε}. Hal ini menjelaskan bahwa x adalah suatu penyelesaian dari A ⊗ x ≤ b bila dan hanya bila untuk semua j, xj ≤ min{bi − ai,j | i ∈ m dan ai,j > ε}. Oleh karena itu, [x∗ (A, b)]j = min{bi − ai,j | i ∈ m dan ai,j > ε} adalah penyelesaian maksimum dari A ⊗ x ≤ b. Teorema 2.3.1 menjelaskan penyelesaian dari A ⊗ x ≤ b, sedangkan penyelesaian dari A ⊗ x = b bila ada diberikan oleh sifat berikut. Lemma 2.3.1 Bila suatu penyelesaian dari A⊗x = b ada, maka sub-penyelesaian terbesar adalah penyelesaiannya. Bukti Misalkan x′ adalah suatu penyelesaian maksimum dari A ⊗ x = b, maka x memenuhi pertaksamaan A ⊗ x ≤ b. Jadi haruslah x′ adalah sub-penyelesaian terbesar. Sebagaimanana diketahui bahwa sub-penyelesaian x∗ (A, b) adalah maksimum penyelesaian dari A ⊗ x ≤ b. Karena penyelesaian dari A ⊗ x = b ada, maka x∗ (A, b) adalah penyelesaiannya. Hal ini menunjukkan bahwa sub-penyelesaian terbesar adalah suatu penyelesaian. Perhatikan bahwa, untuk semua j ∈ n, xj ≤ min{bi −ai,j | i ∈ m} dapat diganti oleh: untuk semua j ∈ n, xj ≤ − max{−bi + ai,j | i ∈ m} atau untuk semua j ∈ n, −xj ≥ max{−bi + ai,j | i ∈ m}. Atau secara matriks dalam aljabar max-plus adalah −x⊤ ≥ −b⊤ ⊗ A. Contoh-contoh berikut menjelaskan hal-hal yang berkaitan dengan Teorema 2.3.1 dan Lemma 2.3.1. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

35


Contoh 2.3.1 Misalkan A =

2 0 1 3

penyelesaian terbesarnya adalah x = Hal ini bisa dicek sebagai berikut:

Jadi x =

−5 −4

⊗

5 4

,b = . Dengan menggunakan Teorema 2.3.1, 3 . Penyelesaian ini juga memenuhi A ⊗ x = b. 1

2 0 1 3

=

−3 −1

= −x⊤ .

3 2 0 3 5 . Sehingga didapat A ⊗ x = ⊗ = = b. 1 1 3 1 4

3 2 20 Contoh 2.3.2 Misalkan A = ,b = . Dengan menggunakan Teorema 2.3.1, 1 4 4 3 . Tetapi penyelesaian ini memenuhi A ⊗ x 6= b, penyelesaian terbesarnya adalah x = 0 jadi A ⊗ x = b tidak punya penyelesaian. Hal ini bisa dicek sebagai berikut: 3 2 −20 −4 ⊗ = −3 0 = −x⊤ . 1 4 3 2 3 6 20 3 . Sehingga didapat A ⊗ x = ⊗ = ≤ = b. Jadi x = 0 1 4 0 4 4 Teorema 2.3.1 telah diimplementasikan dalam toolbox aljabar max-plus, sehingga Contoh 2.3.1 dan Contoh 2.3.2 dapat dilakukan dalam Scilab 5.1.1 sebagai berikut: // maxplus(A,x)=b punya penyelesaian -->A=[2 0; 1 3] A = 2. 0. 1. 3. -->b=[5;4] b = 5. 4. -->x = maxpluslinsol(A,b) x = 3. 1. // Cek maxplusotimes(A,x)==b -->maxplusotimes(A,x)==b ans = c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

36

Teori Spektral..

T T // maxplus(A,x)=b tidak punya penyelesaian -->A=[3 2; 1 4] A = 3. 2. 1. 4. -->b=[20;4] b = 20. 4. -->x = maxpluslinsol(A,b) x = 3. 0. // Cek maxplusotimes(A,x) <= b -->maxplusotimes(A,x)<=b ans = T T // Cek bahwa maxplusotimes(A,x) tidak sama dengan b -->~isequal(maxplusotimes(A,x)-b,zeros(2,1)) ans = T

2.3.2

Analisis Penyelesaian A ⊗ x = b

Pada pembahasan sebelumya telah dibahas tentang persamaan A ⊗ x = b.

(2.17)

Persamaan ini selalu mempunyai peyelesiaan suboptimal x yang memenuhi A ⊗ x ≤ b. Pada bagian ini dibahas beberapa kemungkinan penyelesaian Persamaan (2.17) bila ada yaitu bila mempunyai penyelesaian tunggal dan banyak penyelesaian. Disamping itu juga dibahas bila Persamaan (2.17) tidak mempunyai penyelesaian. Persamaan (2.17) ditulis ulang dalam bentuk       b1 x1 a1,1 a1,2 · · · a1,n  a2,1 a2,2 · · · a2,n   x2   b2         .. ..  ⊗  ..  =  ..  .. ..  . . .  .  .  . bm xn am,1 am,2 · · · am,n c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

37


atau (a1,1 ⊗ x1 ) ⊕ (a1,2 ⊗ x2 ) ⊕ · · · ⊕ (a1,n ⊗ xn ) = b1 (a2,1 ⊗ x1 ) ⊕ (a2,2 ⊗ x2 ) ⊕ · · · ⊕ (a2,n ⊗ xn ) = b2 .. . (am,1 ⊗ x1 ) ⊕ (am,2 ⊗ x2 ) ⊕ · · · ⊕ (am,n ⊗ xn ) = bm atau ditulis dalam notasi baku, harus diselesaikan secara simultan sistem persamaan max {(a1,1 + x1 ), (a1,2 + x2 ), · · · , (a1,n + xn )} = b1 max {(a2,1 + x1 ), (a2,2 + x2 ), · · · , (a2,n + xn )} = b2 .. . max {(am,1 + x1 ), (am,2 + x2 ), · · · , (am,n + xn )} = bm

Kasus yang pertama dibahas ada suatu penyelesaian dan beberapa elemen dari b adalah ε. Tanpa menghilangkan keumumannya, persamaan dapat disusun ulang sehingga elemenelemen yang berhingga disusun dengan urutan yang pertamam didapat 

a1,1 a1,2  a2,1 a2,2   .. ..  . . am,1 am,2

... ... .. . ...

  b1     ..  a1,n x1 .  x2    a2,n     bk  ..  ⊗  ..  =  ε   .  .  .  ..  am,n xn ε

Tulis dalam bentuk baku, didapat max {(a1,1 + x1 ), (a1,2 + x2 ), · · · , (a1,n + xn )} = .. . max {(ak,1 + x1 ), (ak,2 + x2 ), · · · , (ak,n + xn )} = max {(ak+1,1 + x1 ), (ak+1,2 + x2 ), · · · , (ak+1,n + xn )} = .. . max {(am,1 + x1 ), (am,2 + x2 ), · · · , (am,n + xn )} =

b1 bk ε ε

Lakukan penomeran ulang pada peubah untuk j sehingga ak+1,j , . . . , am,j = ε c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

38

Teori Spektral..

terjadi pertama, didapat 

   x1 b1 A1 | A2  .   .   − −− − − −   ..   ..        −∞ . . . −∞ |   xl   bk   ⊗ = ,  ..  xl+1  −∞ .. . .     . . . | A3    ...   ...  −∞ . . . −∞ | xn −∞ 



dengan matriks A1 berukuran k × l. Misalkan     x1 b1  ..   ..  ¯ b =  .  dan x¯ =  .  . xl bk

Catatan bahwa, A ⊗ x = b mempunyai penyelesaian, maka xl+1 = · · · = xn = −∞ dan ¯ Jadi, A ⊗ x = b mempunyai penyelesaian bila dan hanya bila x¯ adalah A1 ⊗ x¯ = b. ¯ dan penyelesaian dari A ⊗ x = b adalah penyelesaian dari A1 ⊗ x¯ = b   x¯ −∞   x =  ..  .  .  −∞

Oleh karena itu, penyelesaian dari A ⊗ x = b dengan beberapa elemen b takhingga dapat ¯ dengan semua elemen dari b ¯ berhingga. Jadi pembahasan direduksi kebentuk A1 ⊗ x¯ = b persamaan A ⊗ x = b dapat ditekankan pada semua elemen b berhinnga. Bila A ⊗ x = b mempunyai penyelesaian, maka ai,j + xj ≤ bi , untuk semua i ∈ m dan j ∈ n.

Pertaksamaan ini dapat diperlakukan secara terpisah unuk setiap j, didapat ai,1 + x1 ≤ bi atau x1 ≤ bi − ai,1 atau x1 ≤ min{(b1 − a1,1 , (b2 − a2,1 ), . . . , (bm − am,1 )}. Jadi bila sistem mempunyai penyelesaian haruslah memenuhi x1 ≤ min{(b1 − a1,1 , (b2 − a2,1 ), . . . , (bm − am,1 )}. Dengan demikian penyelesaian x yang mungkin memenuhi x1 ≤ min{(b1 − a1,1 , (b2 − a2,1 ), . . . , (bm − am,1 )} x2 ≤ min{(b1 − a1,2 , (b2 − a2,2 ), . . . , (bm − am,2 )} .. . xn ≤ min{(b1 − a1,n , (b2 − a2,n ), . . . , (bm − am,n )}. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

39


Jadi, calon penyelesaian dari A ⊗ x = b yang dinotasikan dengan x¯ adalah     x¯1 x1 = min{(b1 − a1,1 , (b2 − a2,1 ), . . . , (bm − am,1 )}    x¯2   x2 = min{(b1 − a1,2 , (b2 − a2,2 ), . . . , (bm − am,2 )}   x¯ =  ..  , dengan ..  . .    x¯n xn = min{(b1 − a1,n , (b2 − a2,n ), . . . , (bm − am,n )}

Selanjutnya didefinisikan matriks "discrepancy" (ketidaksesuaian) dinotasikan oleh DA,b dengan   b1 − a1,1 b1 − a1,2 . . . b1 − a1,n ..   . b2 − a2,n   b2 − a2,1 b2 − a2,2 DA,b =   .. .. .. ..   . . . . bm − am,1 bm − am,2 . . . bm − am,n

Catatan bahwa, minimum dari setiap kolom DA,b adalah elemen dari x¯. Selanjutnya didefenisikan matriks tereduksi ketaksesuaian RA,b oleh RA,b = [ri,j ] dengan ri,j =

1, bila di,j = minimum dari kolom ke j 0, yang lainnya

Contoh 1 Selesaikan A ⊗ x = b, bila  2 0 A= 3 9 Matriks DA,b

     3 1 6 x1 10 4 6  , x = x2  dan b =   . 5 1 −2 x3 6 3 11 

4 10 = 2 2

3 6 4 5

  0 1 5 0 0 4  dan RA,b =  1 0 7 1 0 8

 0 1 , 0 0

perhatikan bahwa setiap kolom matriks RA,b hanya terdapat tepat satu elemen bernilai 1. Hal ini mengisyaratkan A ⊗ x = b hanya mempunyai tepat satu penyelesaian x¯ dengan elemen-elemen adalah minimum dari setiap kolom matrik DA,b , yaitu   2  x¯ = 3 . 4 c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

40

Teori Spektral..

Selanjutnya bisa dicek bahwa    2 3 1 2 0 4 6     ⊗ 3 A ⊗ x¯ =  3 1 −2 4 9 6 3   6 10  =  5 11 = b. 

Matriks DA,b dan RA,b penting untuk menentukan perilaku penyelesaian dari A ⊗ x = b. Telah diketahui bahwa penyelesaian dari A ⊗ x = b bila ada yaitu x dengan elemen xi diberikan oleh xj = min{bk − ak,j } = min{−ak,j + bk } = ⊕′k (−ak,j ⊕ bk ), k

k

jadi dalam min plus aljabar x diberikan oleh x = −AT ⊗′ b. Dengan demikian didapat     6 2 −2 0 −3 −9   ′ 10    x = −3 −4 −1 −6 ⊗   = 3 5 4 −1 −6 2 −3 11 



Contoh 2 Selesaikan A ⊗ x = b, bila

Matriks

 2 0 A= 3 9 DA,b

     3 1 8 x1    4 6 x2  dan b = 13 . , x = 5 1 −2 x3 6 3 10 

6 13 = 2 1

5 9 4 4

  0 0 7 0 0 7  dan RA,b =  0 1 7 1 1 7

 1 1 , 1 1

perhatikan bahwa setiap kolom matriks RA,b hanya terdapat setidaknya satu elemen bernilai 1 sedangkan baris ke-2 dan ke-3 terdapat nilai 1 lebih dari satu. Hal ini mengisyaratkan c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

41


A ⊗ x = b hmempunyai lebih dari satu (takhingga) penyelesaian x¯ dengan elemen adalah minimum dari setiap kolom matrik DA,b , yaitu   1 x¯ = 4 . 7 Selanjutnya bisa dicek bahwa

   2 3 1 1 0 4 6     ⊗ 4 A ⊗ x¯ =  3 1 −2 7 9 6 3   8 13  =  5 10 = b. 

Bisa diecek bahwa penyelesaian yang lain adalah   c1  x¯ = c2  , 7 dengan c1 ≤ 1 dan c2 ≤ 4. Contoh 3 Selesaikan A ⊗ x = b, bila

Matriks

 2 0 A= 3 9

DA,b

     3 1 6 x1    4 6 x2  dan b = 12 . , x = 5 1 −2 x3 6 3 9 

4 12 = 2 0

3 8 4 3

  0 1 5 0 0 6  dan RA,b =  0 0 7 1 1 6

 1 0 , 0 0

perhatikan bahwa tidak semua kolom matriks RA,b setidaknya memuat satu elemen bernilai 1, yaitu baris ke-2 semua elemennya bernilai 0 begitu juga baris ke-3 semua elemennya bernilai 0. Hal ini mengisyaratkan A ⊗ x = b tidak mempunyai penyelesaian, tetapai c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

42

Teori Spektral..

hanya mempunyai subpenyelesaian obtimal x¯ dengan elemen adalah minimum dari setiap kolom matrik DA,b , yaitu   0 x¯ = 3 . 5

Selanjutnya bisa dicek bahwa

   2 3 1 0 0 4 6     ⊗ 3 A ⊗ x¯ =  3 1 −2 5 9 6 3   6 11  =  4 19   6 12  ≤   5  = b. 9 

Perhatikan bahwa untuk suatu kolom j pada matriks DA,b , elemen minimum dari kolom ini adalah penyelesaian maksimum dari sistem pertaksamaan untuk xj . Dengan mengubah sistem pertaksamaan ini menjadi persamaan, didapat persamaan pada setiap baris pertaksamaan, dengan demikian haruslah ada setidaknya satu minimum di setiap baris DA,b , yaitu ada setidaknya satu elemen sama dengan 1 disetiap baris matriks RA,b agar supaya ada penyelesaiaan. Pada Contoh 1 setiap kolom matriks RA,b hanya terdapat tepat satu elemen bernilai 1, hal ini mengisyaratkan persamaan A ⊗ x = b mempunyai penyelesaian tunggal. Berikut ini diberikan teorema mengenai beberapa hal yang telah dibahas. Teorema 2.3.2 Diberikan persamaan A ⊗ x = b dengan ukuran A adalah m × n, x berukuran n × 1 dan b berukuran m × 1 yang semua elemennya berhingga. Bila suatu baris dari matriks RA,b semua elemennya bernilai 0, maka A ⊗ x = b tidak punya penyelesaian. Bila setidaknya pada setiap baris matriks RA,b memuat elemen bernilai 1, maka x¯ adalah suatu penyelesaian dari A ⊗ x = b. Bukti Tanpa menghilangkan kegeneralitasan, misalkan baris ke-k dari matriks RA,b semua elemennya bernilai 0 dan andaikan bahwa x˜ adalah suatu penyelesaian dari A ⊗ x = b. Maka x˜j ≤ min{bl − al,j } < (bk − ak,j ). l

Jadi x˜j + ak,j < bk untuk semua j. Dengan demikian x˜ tidak memenuhi persamaan kek. Hal ini bertentangan dengan x˜ adalah suatu penyelesaian dari A ⊗ x = b. Jadi x˜ bukan penyelesaian dari A ⊗ x = b atau persamaan A ⊗ x = b tidak punya penyelesaian. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

43


Berikutnya, andaikan x¯ bukan suatu penyelesaian dari A ⊗ x = b, maka x¯j ≤ bk − ak,j untuk semua k, j. Jadi max{ak,j + x¯j } ≤ bk j

dan bila x¯ bukan penyelesaian dari A ⊗ x = b, maka ada suatu k dengan max{ak,j + x¯j } < bk j

hal ini ekivalen dengan x¯j < bk − ak,j , untuk semua j. Karena x¯j = min{bl − al,j }, untuk beberapa l, maka tidak ada elemen di baris ke-k pada matriks RA,b yang bernilai 1. Hal ini bertentangan bahwa setiap baris dari matriks RA,b setidaknya memuat elemen yang bernilai 1. Jadi haruslah x¯ adalah suatu penyelesaian dari A ⊗ x = b. Salah satu hasil Teorema 2.3.2 adalah eksistensi dari penyelesaian A ⊗ x = b. Eksistensi ini belum menjelaskan bilamana tunggal dan tidak tunggal. Untuk hal ini diperluhkan definisi berikut. Definisi 2 Elemen bernilai 1 pada suatu baris RA,b dinamakan elemen peubah tetap bila • bila nilai 1 hanya satu-satunya pada baris tsb. atau • bila nilai tsb. pada kolom yang yang sama seperti halnya hanya satu-satunya nilai 1. Sisa nilai 1 lainnya dinamakan elemen slack. Pada Contoh 1 matriks RA,b

 1 0 0 0 0 1  =  1 0 0 1 0 0



1 adalah peubah tetap. Persamaan baris pertama menetapkan elemen semua elemen x2 = 3 dan persamaan baris kedua menetapkan elemen x3 = 4. Persamaan baris ketiga menetapkan elemen x1 = 2, dalam hal ini ketika persamaan baris keempat dicapai semua elemen x sudah dipilih. Setiap elemen-elemen yang telah dipilih ini tidak bisa diubah, bila diubah yang lain akan membentuk pertaksamaan. Begitu juga pada Contoh 2, matriks   1 0 0 0 0 1  RA,b =  0 1 1 1 1 1 c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

44

Teori Spektral..

1 adalah peubah tetap sedangkan semua elemen sisa lainnya yang bernilai 1 semua elemen adalah elemen slack. Ada tiga elemen slack. Persamaan baris pertama menetapkan elemen x3 = 7. Elemen penyelesaian persamaan baris kedua sudah ditetapkan oleh persamaan baris pertama. Pada persamaan baris ketiga ada dua cara yang mungkin untuk mencapai persamaan yaitu x2 = 4 atau x3 = 7, Tetapi x3 sudah ditetapkan sebelumnya sama dengan 7. Jadi asalkan x2 ≤ 4 tidak akan mengubah persamaan pada baris diatasnya. Dengan cara yang sama pada persamaan baris keempat asalkan x1 ≤ 1 tidak akan mengubah persamaan pada baris diatasnya. Dengan demikian, dengan menetapkan x3 = 7 dan untuk x2 ≤ 4 dan x1 ≤ 1 persamaan semua baris selalu benar. Teorema 2.3.3 Diberikan persamaan A ⊗ x = b dengan ukuran A adalah m × n, x berukuran n × 1 dan b berukuran m × 1 yang semua elemennya berhingga. Tambahan pula, persamaan A ⊗ x = b mempunyai penyelesaian. Bila setiap baris dari matriks RA,b hanya ada satu bernilai 1, maka penyelesaian A ⊗ x = b tunggal. Bila ada elemen slack pada matriks RA,b , maka penyelesaian dari A ⊗ x = b adalah tidak tunggal. Bukti Bila disetiap baris RA,b hanya ada satu elemen bernilai 1, maka disetiap baris RA,b ada suatu elemen peubah tetap dan tidak ada elemen slack. Dengan demikian semua elemen x tetap, jadi penyelesaian tunggal. Selanjutnya, misalkan ri,j adalah satu elemen slack pada RA,b dan x¯ adalah penyelesaian dari A ⊗ x = b. Karena ri,j bukan elemen peubah tetap, maka tidak ada elemen peubah tetap pada kolom ke-j dari matriks RA,b . Jadi persamaan bisa dicapai tanpa menggunakan elemen x¯j . Dengan demikian walaupun nilai x¯j menunjukkan nilai maksimum yang mungkin untuk elemen ini, setiap nilai yang lebih kecil atau sama dengan x¯j tidak mempengaruhi eksistensi persamaan baris yang telah ditetapkan.

2.3.3

Persamaan x = (A ⊗ x) ⊕ b

n×n Mengikuti Persamaan (2.1) dan (2.2), secara formal untuk sebarang A ∈ Rmax didefinisikan def

A∗ = E ⊕ A+ =

∞ M

A⊗i .

(2.18)

i=0

Dari hasil Teorema 2.1.1, jelas bahwa A∗ ada untuk setiap matriks persegi A dengan graf G(A) hanya mempunyai bobot sirkuit takpositip. Catatan bahwa A⊗n merujuk pada bobot maksimum dari path dengan panjang n. Jadi path ini memuat setidaknya satu sirkuit. Bila semua sirkuit mempunyai bobot sirkuit takpositip, maka ⊗n

[A

]i,j

n−1 O ≤ [A⊗i ]i,j , i, j ∈ n, i=0


45


dan kondisi dalam Teorema 2.1.1, A∗ bisa ditentukan sebagai berikut ∗

A =

n−1 M

A⊗i .

(2.19)

i=0

Penyelesaian dari persamaan x = (A ⊗ x) ⊕ b diberikan dalam teorema berikut. n×n Teorema 2.3.4 Misalkan A ∈ Rmax dan b ∈ Rnmax . Bila bobot rata-rata sirkuit graf G(A) kurang dari atau sama 0, maka x = A∗ ⊗ b adalah penyelesaian dari x = (A ⊗ x) ⊕ b. Lagipula, bila bobot sirkuit dalam G(A) adalah negatip, maka penyelesaiannya tunggal.

Bukti Akan ditunjukkan bahwa A∗ ⊗ b = A ⊗ (A∗ ⊗ b) ⊕ b. Berdasarkan Teorema 2.1.1, A∗ ada, sehingga didapat ∗

A ⊗b = =

∞ M

A⊗i ⊗ b

i=0 ∞ M

!

A⊗i ⊗ b

i=1

= A⊗

∞ M

⊕ (E ⊗ b) !

A⊗i ⊗ b

i=0

⊕ (E ⊗ b)

= A ⊗ (A∗ ⊗ b) ⊕ b. Selanjutnya ditunjukkan ketunggalan penyelesaian, misalkan x adalah penyelesaian x = b ⊕ (A ⊗ x). Substitusikan x dalam b ⊕ (A ⊗ x), yaitu x = b ⊕ (A ⊗ b) ⊕ (A⊗2 ⊗ x), ulangi lagi proses ini, sehingga didapat x = b ⊕ (A ⊗ b) ⊕ (A⊗2 ⊗ x) ⊕ (A⊗3 ⊗ x) = b ⊕ (A ⊗ b) ⊕ . . . ⊕ (A⊗(i−1) ⊗ b) ⊕ (A⊗i ⊗ x) i−1 M = (A⊗l ⊗ b) ⊕ (A⊗i ⊗ x).

(2.20)

l=0

Elemen-elemen A⊗i adalah bobot maksimum dari path dengan panjang i. Untuk i cukup besar, setiap path memuat satu atau lebih sirkuit elementer turunan sebagai subpath dan kalau i menuju ∞ banyaknya sirkuit elementer yang terjadi menuju ∞. Karena sirkuit mempunyai bobot negatip, maka elemen-elemen A⊗i menuju ε untuk i menuju ∞, yaitu lim A⊗i ⊗ x = ε.

i→∞


46

Teori Spektral..

Jadi, untuk i menuju ∞ Persamaan (2.20) menjadi x = A∗ ⊗ b, yang mana untuk ini ! i−1 i−1 M M A⊗l ⊗ b = A∗ ⊗ b. (A⊗l ⊗ b) = lim lim i→∞

l=0

i→∞

l=0


Bab

3

Contoh Aplikasi Pada bab ini diberikan beberapa contoh aplikasi dari Aljabar maxplus.

3.1

Masalah Jadwal Penerbangan Pesawat pada suatu Bandara

Tiga pesawat penerbangan komersial berangkat masing-masing dari bandara A,B dan C dengan tujuan bandara utama D yang mana dua pesawat terhubung sudah menanti masing-masing di gate 1 dan gate 2. Waktu keberangkatan dari D dan penutupan gate diberikan dan tidak bisa diubah. Durasi waktu transfer diantara tiga kedatangan dan dua keberangkatan pesawat adalah aij , i = 1, 2, j = 1, 2, 3. A x1

D

d1

a11 b1

a21

B x2

C x3

d2

gate 1

a12 a22

d3

b2

a13

gate 2

a23

Sedangkan lamanya waktu penerbangan dari A ke D adalah d1 , dari B ke D adalah d2 dan dari C ke D adalah d3 . Bila x1 , x2 dan x3 masing-masing menyatakan waktu keberangkatan pesawat dari A,B dan C dan b1 , b2 masing-masing menyatakan waktu penutupan gate 1 dan gate 2, maka buat model aljabar maxplusnya. Selanjutnya bila diketahui d1 = 150, d2 = 120, d3 = 135, a11 = 10, a12 = 20, a13 = 30, a21 = 15, a22 = 35, a23 = 35 dan b1 = 180, b2 = 175, maka hitung x1 , x2 dan x3 . Selanjutnya terjemahkan hasil hitungan, yaitu pukul berapa masing-masing pesawat berangkat dari A, B dan C serta pukul berapa gate 1 dan gate 2 ditutup.

47

48

Contoh Aplikasi..

Jawab Model aljabar maxplusnya adalah max{150 + 10 + x1 , 120 + 20 + x2 , 135 + 30 + x3 } = 180 max{150 + 15 + x1 , 120 + 35 + x2 , 135 + 35 + x3 } = 175 atau A⊗x=b dengan   x1 160 140 165 180   , x = x2 . A= dan b = 165 155 170 175 x3

Untuk menyelesaikan persamaan ini bisa digunakan Scilab sebagai berikut: -->A=[160 140 165;165 155 170] A = 160. 140. 165. 165. 155. 170. -->b=[180;175] b = 180. 175. -->[x] = maxpluslinsol(A,b) x = 10. 20. 5. -->isequal(maxplusotimes(A,x),b) ans = F -->maxplusotimes(A,x)<=b ans = T T Terlihat bahwa A ⊗ x 6= b, tetapi A ⊗ x ≤ b ini berarti x1 = 10, x2 = 20, x3 = 5. adalah penyelesaian suboptimal dari A ⊗ x ≤ b. Bila satuan durasi waktu adalah menit, maka salah satu tafsiran x1 = 10 adalah pukul 06.10, x1 = 20 adalah pukul 06.20 dan x3 = 5 adalah pukul 06.05. Dengan demikian b1 = 180 adalah pukul 09.00 dan b2 = 175 adalah pukul 08.55. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

49

Sistem Produksi Sederhana..

u(k)

t1 = 2

d1 = 5 P1

t3

=

t2

1

d3 = 3

= 0 d2 = 6

t4

=0

P3

t5 = 0

y(k)

P2 Gambar 3.1: Sistem Produksi Sederhana

3.2

Sistem Produksi Sederhana

Diberikan sistem produksi sederhana sebagaimana diberikan dalam Gambar 3.1. Sistem produksi ini terdiri dari 3 unit pemroses P1 , P2 dan P3 . Bahan baku dimasukkan pada proses P1 dan P2 untuk diproses dan hasilnya dikirim ke P3 dimana dilakukan perakitan. Waktu proses yang dibutuhkan masing-masing diberikan oleh: d1 = 5, d2 = 6 dan d3 = 3 satuan waktu. Bila diasumsikan diperlukan t1 = 2 satuan waktu dari bahan baku untuk mencapai P1 dan dibutuhkan t3 = 1 satuan waktu untuk menyelesaikan produk dari pemroses P1 untuk mencapai P3 . Waktu perjalanan lainya (t2 , t4 dan t5 ) diasumsikan nol. Diantara input dan pemroses terdapat buffer dengan kapasitas yang cukup besar untuk menjamin bahwa buffer tidak akan pernah overflow. Suatu unit pemroses hanya bisa mulai bekerja untuk menghasilkan produk yang baru bila ia telah menyelesaikan proses yang sebelumnya. Diasumsikan pula bahwa setiap unit pemroses sesegera mungkin mulai bekerja bila semua komponen telah tersedia. Didifinisikan: • u(k) adalah waktu dimana bahan baku dimasukkan ke sistem untuk saat yang ke(k + 1). • xi (k) adalah waktu dimana pemroses yang ke-i mulai aktif saat yang ke-k, i = 1, 2, 3. • y(k) adalah waktu dimana produk selesai saat yang ke-k meninggalkan sistem (ditawarkan kedunia luar/konsumen). Selanjutnya ditentukan waktu kapan pemroses P1 mulai bekerja untuk saat yang ke-(k + 1). Bila dimasukkan bahan baku ke sistem saat yang ke-(k + 1), maka bahan baku ini tersedia sebagai input pemroses P1 pada waktu t = u(k) + 2. Bagaimanapun P1 hanya dapat mulai bekerja untuk memroses bahan baku tsb. sesegera mungkin bila P1 telah menyelesaiakan proses yang sedang berjalan saat ini, yaitu proses saat yang ke-k. Karena waktu pemrosesan pada P1 adalah d1 = 5 satuan waktu, maka produk diantara yang ke-k akan meninggalkan P1 pada saat t = x1 (k) + 5. Juga, karena P1 mulai bekerja sesegera mungkin saat bahan baku telah tersedia dan hasil produk saat yang ke-k sudah meninggalkan P1 , maka diperoleh: x1 (k + 1) = max(x1 (k) + 5, u(k) + 2)

(3.1)


50

Contoh Aplikasi..

untuk semua k ∈ N0 , dimana N0 menyatakan himpunan bilangan bulat tak negatif. Kondisi awal bahwa pemroses P1 kosong dan "idle" ini menunjukkan bahwa x1 (0) = ε. Oleh karena itu dari (3.1) didapat x1 (1) = u(0)+2. Dengan menggunakan alasan yang serupa, pemroses P2 dan P3 mulai bekerja saat yang ke-(k +1) dan produk ditawarkan kekonsumen saat yang ke-k diberikan sebagai berikut: x2 (k + 1) = max(x2 (k) + 6, u(k) + 0) x3 (k + 1) = max(x1 (k) + 5 + 1, x2 (k) + 6 + 0, x3 (k) + 3) = max(x1 (k) + 6, x2 (k) + 6, x3 (k) + 3) y(k) = x3 (k) + 3 + 0

(3.2) (3.3) (3.4)

untuk semua k ∈ N0 Kondisi bahwa semua buffer pada saat awal adalah kosong berkenaan dengan x1 (0) = x2 (0) = x3 (0) = ε. Selanjutnya bila ditulis kembali persamaan evolusi dari sistem produksi dengan menggunakan simbol ⊕ dan ⊗, persamaan (3.1), (3.2), (3.3) dan (3.4) menjadi x1 (k + 1) x2 (k + 1) x3 (k + 1) y(k)

5 ⊗ x1 (k) ⊕ 2 ⊗ u(k) 6 ⊗ x2 (k) ⊕ u(k) 6 ⊗ x1 (k) ⊕ 6 ⊗ x2 (k) ⊕ 3 ⊗ x3 (k) 3 ⊗ x3 (k).

= = = =

Bila persamaan-persamaan evolusi terakhir diatas ditulis kembali ke bentuk matriks aljabarmax-plus, diperoleh 

5  ε x(k + 1) = 6 y(k) = [ε ε ′

   ε ε 2 6 ε  ⊗ x(k) ⊕  0  ⊗ u(k) 6 3 ε 3] ⊗ x(k)

dimana x(k) = [x1 (k) x2 (k) x3 (k)] dan notasi diatas adalah model dari persamaan

′

menyatakan transpos. Catatan model

x(k + 1) = A ⊗ x(k) ⊕ B ⊗ u(k) y(k) = C ⊗ x(k), dengan



   5 ε ε 2 A =  ε 6 ε  , B =  0  dan C = [ε ε 3] 6 6 3 ε

Selanjutnya dikembangkan sistem ini dengan asumsi bahwa bila saat waktu bahan baku dimasukan kesistem ketika saat waktu setelah hasil produk selesai ditawarkan kekonsumen c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

51

Sistem Produksi Sederhana..

(u(k) = y(k)), maka evolusi dari keadaan sistem diberikan oleh:

= A ⊗ x(k)

M

= A ⊗ x(k) = A¯ ⊗ x(k)

M

x(k + 1) = A ⊗ x(k)

dimana A¯ = A

M

M

B ⊗ u(k) B ⊗ y(k) B ⊗ C ⊗ x(k)

B ⊗ C.

Untuk menghitung A¯ bisa digunakan Aljabar Max-Plus Toolbox dalam Scilab sebagai berikut: -->A=[5 -%inf -%inf; --> -%inf 6 -%inf; --> 6 6 3] A = 5. - Inf - Inf - Inf 6. - Inf 6. 6. 3. -->B=[2;0;-%inf] B = 2. 0. - Inf -->C=[-%inf -%inf 3] C = - Inf - Inf 3. -->Abar=maxplusoplus(A,maxplusotimes(B,C)) Abar = 5. - Inf 5. - Inf 6. 3. 6. 6. 3. diperoleh nilai



 5 ε 5 A¯ =  ε 6 3  , 6 6 3

dalam hal ini tentunya lebih dulu telah diberikan nilai-nilai dari matriks A, B dan C kedalam Scilab. Selanjutnya dikaji perilaku dinamik dari sistem dengan mensimulasikan beberapa keadaan awal. Untuk keadaan awal x = [0 0 0]′ , diperoleh evolusi sistem untuk c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

52

Contoh Aplikasi..

k = 0, 1, 2, . . . , 10: 0 5 11 17 23 29 35 41 47 53 59 x = 0 6 12 18 24 30 36 42 48 54 60 0 6 12 18 24 30 36 42 48 54 60 y = 3 9 15 21 27 33 39 45 51 57 63 Terlihat keadaan sistem mencapi periodik pada saat k = 1 dengan periode sama dengan 6. Perintah dalam Scilab untuk memperoleh x dan y sebagai berikut -->[X] = maxplussys(Abar,[0;0;0],10) X = column 1 to 8 0. 5. 11. 17. 23. 0. 6. 12. 18. 24. 0. 6. 12. 18. 24. column 9 to 11 47. 53. 59. 48. 54. 60. 48. 54. 60. -->for i=1:11 -->y(:,i)=maxplusotimes(C,X(:,i)); -->end -->y y = column 1 to 9 3. 9. 15. 21. 27. column 10 to 11 57. 63.

29. 30. 30.

35. 36. 36.

41. 42. 42.

33.

39.

45.

51.

Berikutnya dicoba keadaan awal x = [1 2 2]′ , diperoleh evolusi sistemya: 1 7 13 19 25 31 37 43 49 55 61 x = 2 8 14 20 26 32 38 44 50 56 62 2 8 14 20 26 32 38 44 50 56 62 y = 5 11 17 23 29 35 41 47 53 59 65 Terlihat mulai awal keadaan sistem sudah periodik dengan periode sama dengan 6. Akhirnya, dicoba lagi dengan keadaan awal x = [20 1 23]′, didapat evolusi sistemnya: 20 28 33 38 44 50 55 61 67 73 79 x = 1 26 32 39 44 50 56 62 68 74 80 23 26 34 38 45 50 56 62 68 74 80 c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

Penjadwalan Sistem Jaringan Kereta dan Kestabilan..

53

y = 26 29 37 41 48 53 59 65 71 77 83 Terlihat keadaan sistem mencapi periodik pada saat k = 6 dengan periode sama dengan 6. Dari beberapa keadaan awal yang diberikan, bisa disimpulkan bahwa keadaan awal x = [1 2 2]′ merupakan keadaan yang baik untuk mengawali saat keadaan sistem aktif, yaitu saat waktu awal masing-masing proses P1 , P2 dan P3 aktif. Sebab dengan keadaan awal ini, akan diperoleh suatu jadual dari setiap mesin aktif secara teratur dengan periode sama dengan 6. Suatu pertanyaan muncul, bagaimana menentukan suatu keadaan awal dari sistem supaya memperoleh evolusi suatu keadaan sistem periodik dengan periode yang hingga (finite)? Pertanyaan ini bisa dijawab dengan menggunakan pengertian vektorkarakteristik dan nilai karakteristik dari suatu matriks persegi. Perhatikan bisa dicek ¯ bahwa vektor keadaan awal x = [1 2 2]′ adalah suatu vektor-karakteistik dari matriks A, sedangkan nilai-karakteristik dari A¯ sama dengan 6. Hal ini bisa dicek dalam Silab sebagai berikut. -->z = maxplusisegv(Abar,[1;2;2],6) z = T Terlihat bahwa benar matriks A¯ mempunyai nilai karakteristik 6 dengan vektor-karaktereistik [1 2 2]′ . Suatu hal yang menarik adalah kajian untuk menguji kestabilan dari jadual yang teratur ini bila terjadi gangguan, misalnya ada satu atau lebih mesin produksi rusak. Hal ini tentunya akan membangkitkan suatu keterlambatan suatu mesin proses yang lain dalam pemrosesan. Akibat gangguan ini, suatu pertanyaan yang mendasar adalah apakah sistem bisa kembali lagi menghasilkan jadual yang periodik? Dengan kata yang lain apakah sistem stabil? Pertanyaan ini bisa dijawad dengan pengertian berkaitan dengan kestabilan dan mengetahui apa syarat-syaratnya sistem yang dikaji adalah stabil.

3.3

Penjadwalan Sistem Jaringan Kereta dan Kestabilan

Pada bagian ini diskusikan jaringan transportasi, khususnya jaringan sistem kereta bisa dimodelkan jika diberikan suatu jadwal keberangkatan dari sistem kereta tsb. Model yang dihasilkan bisa digunakan untuk menganalisa perilaku dan ketegaran (robustness) jaringan tsb. Sistem transportasi dipandang sebagai Sistem Event Diskrit dan digunakan aljabar max-plus dalam pemodelan dikerjakan pada abstrasi tingkat tertentu yang akan menghasilkan ciri struktur tertentu jaringan yang bisa dipakai untuk menganalisa dibawah asumsi yang bisa diterima. Alasan utama digunakannya aljabar max-plus disebabkan kemudahannya dalam menanganai proses sinkronisasi. Sistem transportasi adalah suatu contoh dimana sinkronisasi memainkan suatu peranan yang penting. Dalam bidang sain transportasi penggunaan aljabar max-plus adalah relatif baru. Beberapa hasil kerja dari sistem transportasi dengan menggunakan aljabar max-plus bisa dijumpai di [7] dan [3]. Diasumsikan bahwa suatu jaringan kereta beroperasi dengan suatu jadwal keberangkatan c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

54

Contoh Aplikasi..

dari semua kereta yang sudah ditentukan secara periodik dengan interval T . Periode T sama untuk semua kereta, yaitu bila keberangkatan kereta i dijadwalkan berangkat pada waktu di , maka kereta ini dijadwalkan berangkat pada waktu di + k.T , k ∈ N dimana N menyatakan himpunan bilangan alam. Semua waktu perjalan diketahui tetap. Pembatasan ini dimaksudkan bahwa kereta tidak dapat melaju melebihi jadwal yang sudah ditentukan juga tidak memperlambat lajunya sehingga membangkitkan keterlambatan. Asumsi yang lainnya adalah semua waktu perjalanan, dan jadwal disajikan oleh bilangan alam untuk memudahkan analisa dan pemrograman. Hal ini cukup beralasan disebabkan kebanyakan jadwal diberikan dalam menit atau jam. Untuk suatu sistem yang realistik, suatu kondisi dari keberangkatan kereta haruslah memenuhi bahwa kereta sebelumnya yang terjadwal berangkat pada T satuan waktu sudah berangkat lebih dulu. Selain dari pada itu diasumsikan bila suatu kereta terlambat karena sesuatu hal, keterlambatan ini tidak boleh melebihi T . Diasumsikan juga perpindahan penumpang dari satu kereta ke kereta lainya harus terjamin, ini berarti suatu kereta tidak boleh berangkat sebelum kereta tertentu lainya sudah datang. Selajutnya diasumsikan, keberangkatan kereta tidak boleh mendahului jadwal keberangkatan yang sudah ditentukan.

3.3.1

Contoh jaringan kereta

Pada bagian ini dibahas suatu contoh bagaimana menurunkan model jaringan sistem kereta bila diberikan jadwal keberangkatan dari kereta. Dari jadwal yang ada ditentukan banyaknya kereta yang beroperasi pada sistem tsb. disetiap jalur yang ada dengan menggunakan waktu acuan jam 11:58. Selanjutnya dibuat sinkronisasi diantara kereta yang ada pada masing-masing jalur, hal ini dimaksudkan untuk menjamin tejadinya perpindahan penumpang dari suatu kereta dari jalur tertentu ke kereta lainya dengan jalur yang berbeda. Waktu perjalanan dari masing-masing kereta diketahui tetap. Waktu perjalanan tsb. ditentukan dari selisih diantara waktu kedatangan dengan waktu keberangkatan kereta. Misalkan model yang dikaji meliputi 4 stasiun kereta A, B, C dan D yang dihubungkan oleh 3 jalur, seperti ditunjukkan oleh Gambar 3.2. Jalur 1 adalah lintasan kereta dari A ke B ke C, kembali lagi ke A. Jalur 2 adalah lintasan kereta dari A ke B ke D, kembali lagi ke A. Sedangkan jalur 3 adalah lintasan kereta dari C ke D kembali lagi ke C. Angka diatas dan disamping garis panah menunjukkan lamanya waktu perjalanan. Sedangkan jadwal C

88 b 70 b

A

b

b

72 70b

b

B b

72

b b

90 78 b 42 b b

40

76 b

D

Gambar 3.2: Jalur Sistem Kereta


55


keberangkatan kereta, waktu perjalan dan banyaknya kereta pada masing-masing jalur pada saat jam 11:58 sebagai acuan waktu diberikan oleh tabel berikut: Jalur 1 1 1 1 2 2 2 2 3 3

dari A1 B1 C1 B1 A2 B2 D1 B2 C2 D2

ke B1 C1 B1 A1 B2 D1 B2 A2 D2 C2

jadwal berangkat 50 10 47 25 17 30 20 2 45 25

lama perjalanan 70 88 90 72 70 42 40 72 76 78

banyaknya kereta 2 1 2 1 1 1 1 1 2 1

Disini masing-masing A1 ,B1 ,C1 ,A2 ,B2 ,C2 dan D2 bisa dianggap sebagai platfom pada stasiun A, B, C dan D. Sedangkang aturan sinkronisasi diantara kereta diberikan sebagai berikut: • Pada jalur 1, kereta ke-(k + 1) yang berangkat dari platfom B1 ke arah C harus menunggu kedatangan kereta ke-k yang berangkat dari platfom D1 menuju B. Kereta ke-(k + 1) yang berangkat dari platfom C1 kearah B harus menunggu kedatangan kereta ke-k yang berangkat dari platfom D2 menuju C. • Pada jalur 2, kereta ke-(k + 1) yang berangkat dari platfom B2 ke arah D harus menunggu kedatangan kereta ke-(k − 1) (sebab ada 2 kereta pada jalur lintasan dari C1 ke B1 ) yang berangkat dari platfom C1 menuju B. Kereta ke-(k+1) yang berangkat dari D2 kearah B harus menunggu kedatangan kereta ke-(k − 1) (sebab ada 2 kereta pada jalur lintasan dari C2 ke D2 ) yang berangkat dari C2 menuju D. • Pada jalur 3, kereta ke-(k + 1) yang berangkat dari platfom C2 ke arah D harus menunggu kedatangan kereta ke-k yang berangkat dari platfom B1 menuju C. Kereta ke-(k + 1) yang berangkat dari platfom D2 kearah C harus menunggu kedatangan kereta ke-k yang berangkat dari platfom B2 menuju D. Selanjutnya dari informasi jadwal keberangkatan, lamanya waktu perjalanan dan posisi kereta pada saat acuan waktu seperti yang telah ditentukan serta aturan sinkronisasi yang telah diberikan dibuat suatu model sistem jaringan kereta. Bila xi (k), i = 1, 2, . . . , 10 masing-masing adalah keberangkatan kereta yang ke-k dari A1 ke B1 , dari B1 ke C1 , dari C1 ke B1 , dari B1 ke A1 , dari A2 ke B2 , dari B2 ke D1 , dari D1 ke B2 , dari B2 ke A2 , dari C2 ke D2 dan dari D2 ke C2 , didapat suatu persamaan yang diberikan oleh bentuk berikut: x(k + 1) = A ⊗ x(k),

(3.5)


56

Contoh Aplikasi..

dimana x(k) = (x1 (k), x2 (k), . . . , x13 (k))′ dan   . . . 72 . . . . . . . . .  . . . . . . 40 . . . 70 . .      . 88 . . . . . . . 78 . . .     . . . . . . . . . . . 90 .    . . . . . . . 72 . . . . .      . . . . 70 . . . . . . 90 .   . 42 . . . . . . 76  A= ,  . . . .  . . . . . . 40 . . . . . .      . 88 . . . . . . . 78 . . .    . . . . . 42 . . . . . . 76      0 . . . . . . . . . . . .    . . 0 . . . . . . . . . .  . . . . . . . . 0 . . . .

(3.6)

dimana untuk alasan kemudahan dinotasikan ε dengan . = ε. Catatan: total keseluruhan kereta adalah 13, hal ini sama dengan dimensi dari pada x pada (3.5). Fariabel keadaan x11 , x12 dan x13 dinamakan fariabel keadaan pembantu.

3.3.2

Pengkajian model yang diharapkan

Maksud dari bagian ini adalah mendiskusikan model sistem jaringan yang diharapkan yang dikaitkan dengan realita jadwal yang ada. Seperti yang dibahas pada bagian terdahulu bahwa model yang telah diturunkan yaitu (3.5), tentunya model tsb. memenuhi asumsi yang telah ditetapkan. Jika model tsb. dikaitkan dengan realita jadwal yang ada, diperoleh:  x(k + 1) = A ⊗ x(k) ⊕ d(k + 1)  y(k) = C ⊗ x(k) , (3.7)  x(0) = x0

dimana x(k) = (x1 (k), x2 (k), . . . , x13 )′ , A seperti diberikan pada persamaan (3.6), d(k) adalah vektor jadwal keberangkatan kereta yang ke-k dan C = (O E)′, dimana O = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)′ dan E = (ε, ε, ε)′.

3.3.3

Jadwal keberangkatan

Vektor d(k) ∈ Rnε berisi jadwal keberangkatan semua kereta yang ke-k. Karena kereta dijadwal berangkat modulo T , dalam aljabar max-plus diperoleh hubungan: d(k) = d(0) ⊗ T ⊗

k

(3.8)

berlaku untuk semua k. Ini juga bisa ditulis sebagai: d(k) = d(0) + (k.T ) ⊗ η, c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

(3.9)


57

dimana η = (0, 0, . . . , 0)′ ∈ Rnε , vektor-satuan dalam aljabar max-plus. Jadi dalam aljabar biasa d(k) = (d1 (0) + (k.T ), d2(0) + (k.T ), . . . , dn (0) + (k.T ))′. Catatan: sebagaimana telah diketahui dalam fariabel keadaan berisi sebagian fariabel keadaan pembantu. Begitu juga dalam vektor jadwal keberangkatan d(k), berisi jadwal keberangkatan yang sesungguhnya, sedangkan sisanya bukan jadwal keberangkatan yang sesungguhnya. Pada contoh jaringan yang dibahas d(k) diberikan oleh:   50 + 60.k  10 + 60.k     47 + 60.k     25 + 60.k     17 + 60.k     30 + 60.k     20 + 60.k d(k) =     2 + 60.k     45 + 60.k     25 + 60.k    −10 + 60.k   −13 + 60.k −15 + 60.k

dimana di (k), i = 1, 2, . . . , 10 merupakan jadwal keberangkatan yang sebenarnya, sedangkan sisanya bukan jadwal yang sebenarnya. Bilangan 60 menunjukkan periodenya (modulo 60), sedangkan −10 berasal dari 50 − 60, −13 berasal dari 47 − 60 dan −15 berasal dari 45 − 60. Jadwal akan bermanfaat bila sistem beroperasi dengan jadwal tsb. Dalam hal ini akan dikatakan jadwal keberangkatan kereta adalah realistik bagi sistem (3.7).

Difinisi 1 Untuk sistem (3.7) jadwal keberangkatan kereta d adalah realistik bila untuk semua k ≥ 0 A ⊗ d(k) ≤ d(k + 1). (3.10) Dikatakan suatu sistem adalah realistik bila ia mempunyai suatu jadwal keberangkatan kereta yang realistik. Jadwal keberangkatan kereta yang diberikan pada bagian sebelumnya adalah realistik, sebab: A ⊗ d(k) ≤ d(k + 1). Difinisi 2 Vektor keterlambatan z(k) untuk k ≥ 0 didifinisikan sebagai z(k) = x(k) − d(k).

(3.11)

Maksimum keterlambatan dari keberangkatan kereta ke-k dinotasikan oleh: ||z(k)||⊕ =

n M

zi (k).

i=0


58

Contoh Aplikasi..

Berikut ini diberikan suatu teorema yang menyatakan bahwa keterlabatan dari beberapa kereta tidak akan menyebabkan meningkatnya vektor keterlambatan.

Teorema 1 Untuk setiap kondisi awal x(0) dalam suatu sistem dengan jadwal keberangkatan yang realistik, maksimum keterlambatan tidak akan meningkat, yaitu untuk semua k ≥ 0 ||z(k + 1)||⊕ ≤ ||z(k)||⊕ . Berikut ini diberikan pengertian suatu sistem dikatakan stabil.

Difinisi 3 Suatu sistem dengan jadwal keberangkatan adalah stabil bila setiap keterlambatan awal setelah hingga beberapa keberangkatan berikutnya keterlambatan tidak muncul lagi. Secara formalnya, untuk semua x0 ada suatu k(x0 ) ∈ N sedemikian hingga ||z(k)||⊕ = 0, untuk semua k ≥ k(x0 ). Selanjutnya diberikan suatu teorema yang memberikan syarat perluh dan cukup suatu sistem stabil.

Teorema 2 Sistem (3.7) adalah stabil bila dan hanya bila λ < T . Dimana λ adalah nilai karakteristik dari matriks A. Teorema (2), memberikan suatu syarat kapan suatu sistem akan stabil. Pada bahasan berikut ini, akan dibahas lagi sistem yang telah diturunkan pada bagian sebelumnya, terutama dibahas kestabilan sistem bila terjadi beberapa keberangkatan kereta terlambat. Dari hasil yang dikaji bisa diamati keterlambatan yang terjadi besarnya semakin mengecil untuk periode keberangkatan yang berikutnya, sampai pada suatu waktu keberangkatan tertentu tidak terjadi keterlambatan keberangkatan kereta.

3.3.4

Simulasi sistem terhadap keterlambatan

Pada bagian ini diberikan suatu simulasi dari sistem yang dikaji bila beberapa kereta mengalami keterlambatan. Misalkan terjadi keterlambatan keberangkatan sebesar 8 menit masing-masing pada kereta yang berangkat dari A1 dan C2 . Dan terjadi keterlambatan sebesar 25 menit dan 18 menit masing-masing pada kereta yang berangkat dari B1 ke A1 dan dari B2 ke A2 . Dalam hal ini keberangkatan awal karena keterlambatan tsb. diberikan c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono


59

oleh x(0) dan vektor keterlambatan z(0) diberikan oleh:     8 58 0  10      0  47      25  50      0  17      0  30       , z(0) = x(0) − d(0) =  0  20 x(0) =      18  20      8  53      0  25      0 −10     0 −13 0 −15

Selanjutnya dengan menggunakan persamaan (3.7) dan (3.11) diperoleh:     12 122 0  60      0 103     0  77      15  92      0  87       , z(1) =  0  , 72 x(1) =      0  60      0 103     0  72      8  58      0  47  8 53     0 149 0 128     0 150     0 137     0 132     12 162        x(2) = 129 , z(2) =   0 , 0 112     0 150     0 129     12 122     0 103 0 103 c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

60

Contoh Aplikasi..

   0. 209. 2. 192.     0. 216.     0. 193.     0. 184.     0. 202.      , z(3) = 4. , 204. x(3) =      0. 169.     0. 216.     0. 204.     0. 149.     0. 150. 0. 150.     0. 265. 0. 244.     0. 282.     0. 240.     0. 241.     0. 254.      , z(4) = 0. , 244. x(4) =      2. 244.     0. 282.     0. 244.     0. 209.     0. 216. 0. 216. 

dan



   312. 0. 284. 0.     332. 0.     306. 0.     316. 0.     311. 0.      , z(5) = 0. 296. x(5) =      284. 0.     332. 0.     296. 0.     265. 0.     282. 0. 282. 0.

Terlihat bahwa akibat keterlambatan awal pada keberangkatan beberapa kereta, keterlambatan keberangkatan berikutnya terlambat sebesar 12 menit terjadi pada lintasan A1 ke c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

61

Menentukan Jalur Tercepat..

B1 . Keterlambatan ini menyebabkan keterlambatan berikutnya sebesar 12 menit terjadi pada lintasan B2 ke D1 . Sedangkan keterlambatan sebesar 15 menit pada lintasan A2 ke B2 menyebabkan keterlambatan sebesar 2 menit pada keberangkatan dari B1 ke C1 dan keterlambatan sebesar 12 menit pada jalur B2 ke D1 menyebabkan keterlambatan sebesar 4 menit pada keberangkatan dari D1 ke B2 . Keterlambatan sebesar 4 menit pada jalur D1 ke B2 menyebabkan keterlambatan keberangkatan sebesar 2 menit pada keberangkatan dari B2 ke A2 . Setelah itu untuk k > 4 sistem tidak mengalami keterlambatan lagi, ini berarti sistem beroperasi sesuai jadwal keberangkatan ada. Dalam hal ini dikatakan sistem mencapai keadaan stabil untuk k > 4. Catatan: nilai karakteristik dari matriks A yang dikaji adalah λ = 56, sedangkan T = 60. Jadi bukanlah hal yang mengherankan bahwa sistem yang dikaji adalah stabil, sebab λ = 56 < T = 60. Menurut Teorema 2, sistem stabil. Berikut ini diberikan ringkasan hasil apa yang telah dibahas pada keseluruhan bagian ini. Telah dikaji suatu model sistem jaringan kereta yang diturunkan dari jadwal keberangkatan kereta dengan menggunakan aljabar max-plus. Selanjutnya telah ditunjukkan pula bila terjadi keterlambatan dari beberapa kereta pada sistem yang ada keterlambatan ini akan semakin mengecil sampai pada suatu keberangkatan tertentu berikutnya sudah tidak ada keterlambatan lagi. Hal ini menunjukkan sistem kembali beroperasi dengan jadwal keberangkatan sebagaimana bila tidak ada keterlambatan. Dengan kata lain sistem yang dikaji adalah stabil.

3.4

Menentukan Jalur Tercepat

Diberikan gambar suatu jalur sebagai berikut. 3 3 1 B

1

C

b

b

2

2 3

1 b

D

b

E

2

2

2 b

A 3 8 Persoalan Lintasan Tercepat merupakakan persoalan min plus aljabar. berkaitan dengan masalah ini adalah

Matriks yang

 ∞ 3 3 ∞ 8  2 ∞ 1 3 ∞    A=  2 2 ∞ 1 ∞ ∞ 3 2 ∞ 1  ∞ ∞ ∞ 2 ∞ 


62

Contoh Aplikasi..

Untuk menentukan waktu tercepat diperlukan matriks A∗ yang diberikan oleh A∗ =  A ⊕′ A2 ⊕′ A3 ⊕′ A4 5 3 3 4 5 2 3 1 2 3    2 2 3 1 2 =    4 3 2 3 1 6 5 4 2 3

3.5

Model sistem antrian

Berikut ini diberikan pengertian dari Petri net yang digunakan dalam pembahasan berikutnya terutama bila Petri net ini dikaitkan dengan waktu. Suatu grap G = (E, V ) dikatakan bipartisi bila himpunan titik-titik V dapat dipartisi menjadi dua himpunan bagian yang saling asing V1 dan V2 sedemikian hingga setiap garis di G menghubungkan suatu titik dari V1 ke satu titik V2 begitu juga sebaliknya. Petri net adalah grap bipartisi. Himpunan V dipartisi menjadi dua himpunan bagian P dan T yang masing-masing menyatakan place dan transisi. Suatu place p ∈ P dan suatu transisi t ∈ P dapat diintepretasikan sebagai suatu kondisi dan suatu event dari suatu diskripsi suatu model yang dibahas. Masing-masing kondisi p ∈ P yang ’terpenuhi’ diberi tanda titik (token). Suatu token dalam suatu place mempunyai arti bahwa sepanjang place ini penting bagi suatu transisi yang dihubungkannya menyebabkan transisi ini menjadi aktif (event bisa berlangsung). Jadi dengan dua, tiga, empat, . . . token, event ini bisa berlangsung dua, tiga, empat, . . . kali. Untuk memperjelas pengertian ini diberikan suatu contoh Petri net dari suatu model sistem antrian sederhana dengan satu server. Contoh ini akan dibahas lagi terutama bila Petri net dari sistem antrian sederhana dengan satu server ini dikaitkan dengan waktu (Petri netnya dinamakan Petri net dengan waktu). Selanjutnya diturunkan bentuk modelnya dari Petri net dengan waktu ini dalam aljabar maxplus. Gambar dari sistem antrian sederhana dengan satu server beserta Petri netnya (Petri net tanpa waktu) diberikan sebagi berikut.

Dalam Gambar 3.3 bagian (i), a menyatakan kedatangan pelanggan menuju sistem antrian sedangkan d menyatakan pelanggan telah dilayani oleh server dan meninggalkannya. Sedangkan Gambar 3.3 bagian (ii) merupakan penyajian Petri net dari sistem antrian pada bagian (i). Petri net ini terdiri dari himpunan place P = {Q, B, I} dan himpunan transisi T = {a, s, d}. Masing-masing place Q, B dan I menyatakan kondisi antri, sibuk dan idel. Sedangkan transisi a, s dan d masing-masing menyatakan event kedatangan, mulai dilayani dan meninggalkan server. Tanda satu token dalam place I menyatakan bahwa sistem antrian dalam keadaan idel. Dalam kondisi ini transisi s tidak bisa aktif sebab walaupun sistem dalam keadaan idel tetapi kondisi di Q kosong/tidak ada yang antri (tidak ada token). Dalam keadaan ini, yang paling mungkin terjadi adalah transisi a yaitu pelanggan datang. Bila hal ini terjadi, maka place Q berisi satu token. Keadaan yang terakhir ini menyatakan bahwa sistem dalam kondisi idel dan sudah ada satu pelanggan yang antri. c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

63

Model sistem antrian..

a a

Q

d

b

I

s

(i)

B d (ii) Gambar 3.3: Antrian satu server dan Petri netnya

Oleh karena itu, transisi s bisa terjadi, yaitu server sudah bisa memulai untuk melayani satu pelanggang. Dalam keadaan ini, masing-masing satu token di B dan Q berkurang dan satu token berada di place B (sistem antrian dalam keadaan sibuk).

3.5.1

Model Aljabar maxplus dari Petri net dengan waktu.

Sebagaimana telah disebutkan dalam bagian sebelumnya, model maxplus aljabar dari petri net dengan waktu untuk sistem antrian sederhana akan dibahas dalam bagian ini. Petri net dalam Gambar 3.3 bagian (ii) bila dikaitkan dengan waktu akan berubah. Gambar Petri net berikut merupakan gambar dari Petri net dari sistem antrian sederhana yang dikaitkan dengan waktu. va,k

a(k) Q

b

I

s(k) B d(k)

vd,k

Gambar 3.4: Gambar Petri net dengan waktu

Dalam Gambar 3.4 ini, bila a(k) menyatakan waktu kedatangan pelanggan saat yang ke-k, c Aljabar Maxplus dan Terapannya, Copyright: 2013 Subiono

64

Contoh Aplikasi..

va,k menyatakan lamanya kedatangan pelanggan saat yang ke-k, s(k) menyatakan waktu pelayanan dimulai saat yang ke-k, d(k) menyatakan waktu pelanggan meninggalkan pelayanan saat yang ke-k dan vd,k menyatakan lamanya pelanggan meninggalkan pelayanan saat yang ke-k, maka didapat a(k) = va,k + a(k − 1), k = 1, 2, . . . s(k) = max{a(k), d(k − 1)}, k = 1, 2, . . . d(k) = vd,k + s(k), k = 1, 2, . . . = vd,k + max{a(k), d(k − 1)} = max{(vd,k + va,k ) + a(k − 1), vd,k + d(k − 1)} Sehingga dengan menggunakan notasi aljabar maxplus didapat persamaan a(k) va,k c a(k − 1) = ⊗ , d(k) vd,k ⊗ va,k vd,k d(k − 1)

(3.12)

dimana c diplih supaya (va,k ⊗ a(k − 1)) ⊕ (c ⊗ d(k − 1)) = va,k ⊗ a(k − 1), untuk k = 1, 2, 3, . . . dan keadaan awal a(0) = d(0) = 0. Persamaan (3.12) adalah bentuk aljabar maxplus dari sistem model antrian dengan satu server dan terlihat bahwa evolusi dari keadaan a(k) dan d(k) bergantung pada nilainilai dari va,k dan vd,k untuk k = 1, 2, 3, . . .. Dalam kenyataannya, va,k dan vd,k adalah barisan bilangan real positip. Sebelum mengakhiri bagian ini, diberikan suatu contoh. Contoh 4 Bila diberikan sample path dari va,k dan vd,k sebagai berikut va,k = {0.5, 0.5, 1, 0.5, 2, . . .}, vd,k = {1, 1.5, 0.5, 0.5, 1, . . .} didapat

a(2) d(2)

a(3) d(3)

Dalam hal ini c = ε.

a(1) d(1)

a(4) d(4)

a(5) d(5)

=

0.5 ε 1.5 1

=

0.5 ε 2 1.5

=

1 ε 1.5 0.5

=

=

0.5 ε 1 0.5

2 ε 3 1

=

⊗

0.5 1.5

⊗

1 3

⊗

⊗

⊗

0 0

2 3.5

2.5 4

0.5 1.5

=

=

=

=

1 3

2 3.5

2.5 4

4.5 5.5


Model sistem antrian..

65

Dari beberapa pembahasan model antrian ini diberikan beberapa catatan. Model sistem antrian yang dibahas sangat sederhana yaitu antrian hanya dengan satu server, hal ini untuk memberikan suatu ide awal menurunkan model antrian dengan menggunakan aljabar maxplus. Kedepannya kajian bisa diperluas untuk antrian dengan lebih dari satu server, bahkan bila memungkinkan dikaji model antrian yang lebih realistis. Misalnya kapasitas antrian berhingga dan pada saat kondisi tertentu server down sehingga memerlukan perbaikan supaya bisa melayani lagi pelanggannya. Untuk kasus ini Petri net dari antrian bentuknya akan berubah dan bagaimana model aljabar maxplusnya bila memungkinkan. Dalam Contoh 4 nilai c dipilih ε (konstan), akibat pemilihan ini matriks model menjadi tidak strongly connected. Bila dikehendaki matriks modelnya menjadi strongly connected, maka pemilihan nilai c adalah bervariasi. Nilai c yang bervariasi, nilai-nilai dari va,k dan vd,k yang merupakan barisan dari bilangan real positip menyebabkan matriks model yang diperoleh erat kaitannya dengan matriks interval dalam aljabar maxplus. Model antrian selain disajikan dalam bentuk Petri net, bisa disajikan dalam bentuk apa yang dinamakan automata. Kajian yang telah dibahas mengispirasikan suatu apa yang dinamakan Aljabar Maxplus Automata lewat pendekatan model antrian. Beberapa pembahasan mengenai Aljabar Maxplus Automata didahului dengan suatu model yang dinamakan ’heap’.


66

Contoh Aplikasi..


Daftar Pustaka

[1] Bernd Heidergott, Geert Jan Olsder, and Jacob van der Woude. " Max Plus at Work Modelling and Analysis of Synchronized System: A Course on Max-Plus Algebra and Its Application", Princeton University Press, Priceton and Oxford, 2006. [2] Baccelli, F., G. Cohen, G.J. Olsder, and J.-P. Quadrat. "Synchronization and Linearity", John Wiley and Sons, Now York, 1992. Buku ini dapat juga di download dari Web site http://www-rocq.inria.fr/metalau/cohen/SED/bookonline.html [3] Subiono. "On Classes of Min-Max-Plus Systems and Their Applications", PhD thesis, Delft University of Technology, The Netherlands, 2000. Buku ini dapat juga di download dari Web site /http://www.its.ac.id/personal/material.php?id=Subiono [4] Subiono, and J.W. van der Woude. "Power Algorithms for (max,+)-and bipartite (min,max,+)-systems". Discrete Event Dynamic Systems, 10:369-389, 2000. [5] Woude J.W. van der, and Subiono. "Condition for the structural existtence of an eigenvalue of a bipartite (min,max,+) system". Theoretical Computer Science, 293:1324, 2003. [6] Soto y Koelemeijer. "On the Behaviour of Classes of Min-Max-Plus System". PhD thesis, Delft University of Technology, The Netherlands, 2003. [7] Braker, J.G. "Algorithms and Applications in Timed Discrete Event Systems". PhD thesis, Delft University of Technology, The Netherlands, 1993. [8] Ratna Novitasari. "Analisis Masalah Generator dari Possible dan Universal Eigenvector pada Matriks Interval dalam Aljabar Max-Plus". Thesis S2, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember, Surabaya, 2009. [9] Nur Shofiana. "Analisis Kedinamikan Sistem pada Penjadwalan Flow Shop Menggunakan Aljabar Max-Plus". Thesis S2, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember, Surabaya, 2009. 67

68

DAFTAR PUSTAKA

[10] Winarni. "Penjadwalan Jalur Bus Dalam Kota dengan Aljabar Max-Plus" . Thesis S2, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember, Surabaya, 2009. [11] B. De Schutter. "Max-Algebraic system Theory For Discrete Event Systems" . PhD. Thesis, Katholike Universiteit Leuven, Departement Elektrotechniek, 1996. [12] G.J. Olsder, Subiono. "On Large Scale Max-Plus Algebra Models in Railway Systems". Proceeding of IFAC conference on System Structure and Control, Nantes, France, pp.681-685, 1998. [13] Subiono, Dieky Adzkiya. " Max-Plus Algebra Toolbox, ver. 1.0.1". Jurusan Matematika ITS, Surabaya, 2009. File toolbox bisa didownload di: /http://www.its.ac.id/personal/material.php?id=Subiono [14] Jörg Raisch. "Course Notes Discrete Event and Hybrid Systems". Technische Universität Berlin, 2009. [15] Maria H.Andersen, "Max-Plus Algebra: Properties and Applications". Master of Science in Mathematic Thesis Department of Mathematics, Laramie, WY, May 2002. [16] Cassandras, C.G., "Discrete Event Systems: Modelling and Performance Analysis", Aksen Associates Incoperated Publisher, Boston, 1993.


Aljabar Maxplus dan Terapannya

Recommend Documents