ALJABAR MAX-PLUS DAN PENERAPANNYA M. Andy Rudhito Program Studi Pendidikan Matematika FKIP Universitas Sanata Dharma Yogyakarta 2016 ii PRAKATA Aljabar max-plus merupakan suatu struktur aljabar di mana himpunan semua bilangan real R {} dilengkapi dengan operasi max (maksimum) dan plus (penjumlahan). Aljabar ini berawal tahun 70an, tetapi baru berkembang dengan pesat sekitar tahun 90an. Permasalahan-permasalahan dalam jaringan (teori graf) yang terutama terkait dengan masalah sinkronisasi dapat dimodelkan dan diselesaikan dengan baik dengan aljabar max-plus. Permasalahan di atas yang dengan menggunakan matematika biasa berupa model matematika yang nonlinear, dengan menggunakan aljabar max-plus ini dapat berupa model yang linear dalam operasinya. Buku ini disajikan dalam beberapa bab dengan sistematika sebagai berikut. Bab 1 pendahuluan dan motivasi yang berisi masalah-masalah yang dapat dimodelkan dan diselesaikan dengan menggunakan aljabar max-plus, di antaranya adalah masalah sistem jaringan kereta api, sistem produksi sederhana, penjadwalan dalam jaringan proyek dan jaringan antrian. Bab 2 membahas konsep-konsep dasar aljabar max-plus yang meliputi matriks dan struktur aljabarnya. Bab 3 membahas tentang sistem persamaan linear max-plus, yang meliputi sistem input output dan sistem iteratif. Sistem persamaan linear max-plus ini akan digunakan sebagai dasar pemodelan masalah dengan menggunakan aljabar max-plus. Selanjutnya dibahas beberapa penerapan dari sistem persamaan linear max-plus. Bab 4 membahas tentang nilai eigen matriks atas aljabar max-plus. Nilai eigen ini sangat terkait dengan permasalahan yang terkait dengan sifat-sifat periodik dinamika jaringan. Dibahas pula beberapa penerapan dari konsep nilai dan vektor eigen maxplus ini terkait sifat periodik sistem. Bab 5 membahas varian lain aljabar max-plus, yakni aljabar min-plus dan aljabar max-min beserta penerapannya. Pembahasan dalam buku ini agak mengalami kesulitan kalau tidak dibantu aspek komputasinya dengan menggunakan komputer. Dalam tiap babnya akan diberikan aspek komputasinya dengan menggunakan bahasa MATLAB. iii Pada kesempatan ini penulis mengucapkan terimakasih kepada kolega dosen di Universitas Sanata Dharma yang telah memberikan dukungan positip. Jurusan Matematika FMIPA UGM, khusus dosen-dosen kuliah dan pembimbing tugas akhir selama penulis menempuh S2 dan S3. Para dosen dan mahasiswa dari berbagai perguruan tinggi di Indonesia yang telah mendiskusikan topik ini dalam berbagai kesempatan seminar dan perjumpaan-perjumpaan baik online maupun offline. Mahasiswa bimbingan skripsi saya, Regina Wahyudyah Sonata Ayu, yang telah bekerja keras menyelesaikan skripsi topik aljabar max-plus, di mana hasilnya juga merupakan bagian dari susunan buku ini. Akhirnya semoga buku ini bermanfaat dan dapat digunakan dalam kehidupan sehari-hari, maupun dikembangkan sebagai kajian ilmu matematika Yogyakarta, Pebruari 2016 Penulis (e-mail: [email protected]) iv DAFTAR ISI PRAKATA ................................................................................................... iii DAFTAR ISI ................................................................................................ iv BAB 1 PENDAHULUAN ............................................................................ 1 1.1 Sistem Jaringan Kereta Api ...................................................... 1 1.2 Sistem Produksi Sederhana ...................................................... 4 1.3 Penjadwalan Jaringan Proyek ................................................... 7 1.4 Jaringan Antrian........................................................................ 9 BAB 2 ALJABAR MAX-PLUS DAN MATRIKS ....................................... 12 2.1 Aljabar Max-Plus ...................................................................... 12 2.2 Matriks atas Aljabar Max-Plus ................................................. 15 2.3 Semimodul atas Aljabar Max-Plus ........................................... 23 BAB 3 SISTEM PERSAMAAN LINEAR MAX-PLUS DAN PENERAPANNYA ................................................................. 28 3.1 Sistem Persamaan Linear Input-Output (SPLIO) Max-Plus .................................................................................. . 28 3.2 Penerapan pada Sistem Produksi Sederhana ............................. 37 3.3 Eksistensi dan Ketunggalan SPLIO Max-Plus .......................... 58 3.4 Penerapan pada Masalah Ramp-Handling Pesawat ................. 75 3.5 Aljabar Matriks dan Teori Graf ................................................. 83 3.6 Sistem Persamaan Linear Iteratif (SPLI) Max-Plus .................. 93 3.7 Penerapan pada Penjadwalan Proyek ........................................ 98 BAB 4 NILAI, VEKTOR EIGEN MAX-PLUS DAN PENERAPANNYA... 111 4.1 Nilai Eigen dan Vektor Eigen Max-Plus ................................... 111 4.2 Penerapan pada Penjadwalan Kereta .......................................... 119 4.3 Penerapan Analis Model Antrian ................................................ 123 BAB 5 ALJABAR MIN-PLUS DAN ALJABAR MAX-MIN SERTA PENERAPANNYA .............................................................................. 128 5.1 Aljabar Min-Plus ........................................................................ 128 v 5.2 Penerapan Aljabar Min-Plus pada Masalah Lintasan Terpendek ................................................................................... 132 5.3 Aljabar Max-Min ........................................................................ 140 5.4 Penerapan Aljabar Max-Min pada Masalah Kapasitas Maksimum ................................................................................. 145 DAFTAR PUSTAKA ..................................................................................... 148 INDEKS ........................................................................................................... 151 vi BAB I PENDAHULUAN Dalam kehidupan sehari-hari terdapat beberapa masalah yang dapat dimodelkan secara matematis dengan sistem dinamika, misalnya sistem produksi perakitan, sistem jaringan telekomunikasi, sistem pemrosesan paralel pada komputer, sistem jaringan kereta, dan sebagainya. Dalam bab ini akan diberikan masalah-masalah dalam sistem jaringan kereta api, sistem produksi sederhana, penjadwalan dalam jaringan kerja dan jaringan antrian yang dapat dimodelkan dengan menggunakan aljabar max-plus. 1.1 Sistem Jaringan Kereta Api Diperhatikan suatu sistem jaringan kereta sederhana yang disajikan dalam Gambar 1.1.1 berikut: 5 2 3   3 Gambar 1.1.1 Jaringan Kereta Api Sederhana Misalkan di suatu kota terdapat dua stasiun keretaS danS yang dihubungkan 1 2 dengan suatu jaringan rel kereta seperti pada Gambar 1.1.1 di atas, dengan dua kereta untuk tiap stasiun. Misalkan pada waktu keberangkatan pertama empat kereta tersebut melakukan perjalanan sebagai berikut. Kereta pertama berangkat dari stasiun S , mengantar dan menjemput penumpang di pinggiran kota dan 1 kembali ke S . Kereta kedua berangkat dari stasiun S ,mengantar dan menjemput 1 1 penumpang di tengah kota dan menuju ke stasiunS . Kereta ketiga berangkat dari 2 stasiun S ,mengantar dan menjemput penumpang di tengah kota dan menuju ke 2 stasiun S .Kereta keempat berangkat dari stasiun S ,mengantar dan menjemput 1 2 1 2 penumpang di pinggiran kota dan kembali ke S . Pada waktu keberangkatan 1 kedua perjalanan kereta sebagai berikut. Kereta pertama dan keempat kembali melakukan perjalanan seperti pada waktu perjalanan sebelumnya. Kereta kedua berangkat dari stasiun S , mengantar dan menjemput penumpang di tengah kota 2 dan menuju ke stasiun S . Kereta ketiga berangkat dari stasiun S ,mengantar dan 1 1 menjemput penumpang di tengah kota dan menuju ke stasiun S . Pada waktu 2 keberangkatan ketiga perjalanan kereta seperti pada waktu perjalanan pertama, demikian seterusnya. Dengan demikian jaringan rel kereta ini dapt dipandang terdiri dari satu lingkar dalam (S  S S )dan dua lingkar luar (S  S dan 1 2 1 1 1 S  S ). 2 2 Kereta mencapai stasiun lain (atau yang sama) setelah suatu waktu tertentu, yang disebut sebagai waktu perjalanan, seperti yang ditunjukkan pada Gambar 1.1.1 di atas. Keberangkatan kereta di suatu stasiun harus menunggu kedatangan kereta yang lain sehingga penumpang mempunyai kesempatan berganti kereta untuk menuju tempat yang diinginkan. Waktu untuk menunggu kereta lain dan penumpang berganti kereta ini telah diperhitungkan dalam waktu perjalanan. Stasiun di pinggiran kota tidak dipertimbangkan karena tidak mempunyai peranan yang penting dalam pemodelan. Misalkan tidak ada jadwal keberangkatan kereta dan kereta langsung berangkat setelah penumpang berganti kereta pada suatu stasiun. Didefinisikan : x (k+1) : waktu keberangkatan ke-k + 1 pada stasiun S untuk i = 1, 2 . i i Jika proses keberangkatan dan kedatangan suatu kereta berkesinambungan, maka didapat: x (k+1) = max (2 + x (k), 5 + x (k)), 1 1 2 (1.1.1) x (k+1) = max (3 + x (k), 3 + x (k) ), 2 1 2 untuk k = 0, 1, 2, ... . Jika operasi max dinotasikan dengan , operasi penjumlahan dinotasikan dengan , maka persamaan (1.1.1) dapat dituliskan sebagai berikut: x (k+1) = (x (k)  2)  (x (k)  5), 1 1 2 3 (1.1.2) x (k+1) = (x (k)  3)  (x (k)  3). 2 1 2 Jika persamaan (1.1.2) di atas dituliskan dalam persamaan matriks, dengan cara yang serupa pada aljabar matriks biasa, di mana operasi penjumlahan diganti operasi maksimum dan operasi perkalian diganti dengan operasi penjumlahan, maka diperoleh persamaan matriks berikut: 𝑥 (𝑘 +1) 2 5 𝑥 (𝑘) [ 1 ] =  [ 1 ] (1.1.3)   𝑥2(𝑘+1) 3 3 𝑥2(𝑘) Persamaan (1.1.3) di atas secara ringkas dapat juga dituliskan sebagai x(k+1) = A  x(k) (1.1.4) 2 5 dengan x(k) = [x (k), x (k)] T dan A = .   1 2 3 3 Dalam prakteknya jaringan rel kereta beroperasi berdasarkan jadwal keberangkatan. Jadwal keberangkatan terdiri dari waktu keberangkatan kereta dari semua stasiun. Hal ini berarti bahwa sebuah kereta tidak dapat meninggalkan stasiun sebelum waktu jadwal keberangkatannya, meskipun kereta yang ditunggunya telah datang. Didefinisikan: d (k + 1) : jadwal keberangkatan ke-(k+1) pada stasiun S untuk i = 1, 2 . i i Kemudian didapat x (k+1) untuk i = 1, 2 sebagai berikut: i x (k+1) = max (x (k) + 2, x (k) + 5, d (k + 1)), 1 1 2 1 (1.1.5) x (k+1) = max (x (k) + 3, x (k) + 3, d (k + 1)), 2 1 2 2 untuk k = 0, 1, 2, ... . Jika operasi max dinotasikan dengan , operasi penjumlahan dinotasikan dengan , maka, persamaan (1.1.5) atas dapat dituliskan sebagai berikut: x (k+1) = (x (k)  2)  (x (k)  5)  d (k + 1), 1 1 1 1 (1.1.6) x (k+1) = (x (k)  3)  (x (k)  3)  d (k + 1), 2 1 2 2 4 untuk k = 0, 1, 2, ... . Jika persamaan (1.1.6) dituliskan dalam persamaan matriks akan diperoleh persamaan matriks berikut 2 5 d (k 1) x(k+1) =  x(k)  1 (1.1.7)     3 3 d2(k 1) untuk k = 0, 1, 2, ... , dengan x(k) = [x (k), x (k)] T . 1 2 Persamaan matriks (1.1.7) di atas dapat juga dituliskan dalam persamaan berikut: x(k+1) = A  x(k)  d(k + 1) (1.1.8) 2 5 untuk k = 0, 1, 2, ... , dengan x(k) = [x (k), x (k)] T, A = dan d(k + 1) =   1 2 3 3 [d (k + 1), d (k + 1)]T . 1 2 Pada bab-bab selanjutnya akan dibahas bagaimana cara menentukan keberangkatan awal kereta sehingga waktu keberangkatan selanjutnya akan periodik untuk periode waktu tertentu. 1.2 Sistem Produksi Sederhana Diperhatikan suatu sistem produksi sederhana (Schutter, 1996) yang disajikan dalam Gambar 1.2.1 berikut: d = 5 1 u(k) t = 2 t = 1 1 3 d = 3 3 t = 0 y(k) 5 d = 6 t = 0 2 4 t = 0 2 Gambar 1.2.1 Sistem Produksi Sederhana Sistem ini terdiri dari 3 unit pemrosesan P, P , P . Bahan baku dimasukkan ke 1 2 3 P danP , diproses dan dikirimkan keP . Waktu pemrosesan untuk P, P dan P 1 2 3 1 2 3 berturut-turut adalah d = 5, d = 6 dan d = 3 satuan waktu. Diasumsikan 1 2 3