UNIVERSITAS INDONESIA PERBANDINGAN SISTEM PERSAMAAN LINIER DALAM ALJABAR KLASIK DAN ALJABAR MAX-PLUS TESIS MULYADI NPM

UNIVERSITAS INDONESIA

PERBANDINGAN SISTEM PERSAMAAN LINIER DALAM ALJABAR KLASIK DAN ALJABAR MAX-PLUS

TESIS

MULYADI NPM. 0906577362

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI MAGISTER MATEMATIKA DEPOK Juli 2011

Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

UNIVERSITAS INDONESIA

PERBANDINGAN SISTEM PERSAMAAN LINIER DALAM ALJABAR KLASIK DAN ALJABAR MAX-PLUS

TESIS diajukan sebagai salah satu syarat untuk memperoleh gelar Magister Sains

MULYADI NPM. 0906577362

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI MAGISTER MATEMATIKA DEPOK 2011

i Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

HALAMAN PERNYATAAN ORISINALITAS

Tesis ini adalah hasil karya sendiri, dan semua sumber baik yang dikutip maupun dirujuk telah saya nyatakan dengan benar.

Nama

: MULYADI

NPM

: 0906577362

Tanda Tangan

:

Tanggal

: 13 Juli 2011

ii Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

HALAMAN PENGESAHAN

Tesis ini diajukan oleh : Nama : NPM : Program Studi : Judul Tesis :

Mulyadi 0906577362 Magister Matematika Perbandingan Sistem Persamaan Linier dalam Aljabar Klasik dan Aljabar Max-Plus.

Telah berhasil dipertahankan dihadapan dewan penguji dan diterima sebagai bagian persyaratan yang diperlukan untuk memperoleh gelar magister sains pada program studi magister matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Indonesia.

DEWAN PENGUJI

Pembimbing I

:

Dr. Hengki Tasman, M.Si

Pembimbing II

:

Prof. Dr. Djati Kerami

Penguji

:

Prof. Dr. Belawati H Widjaja

Penguji

:

Dr.rer.nat. Hendri Murfi, M.Kom

Ditetapkan di

: Depok

Tanggal

: 13 Juli 2011

iii Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

KATA PENGANTAR

Alhamdulillah, segala puji hanya bagi Allah SWT, Rabb Yang Maha Kuasa, yang telah melimpahkan segala rahmat dan karunia sehingga penulis dapat menyelesaikan tesis ini. Penulisan tesis ini dilakukan dalam rangka memenuhi syarat untuk mencapai gelar Magister Sains Jurusan Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia. Saya sadar bahwa penyelesaian tesis ini tidak terlepas dari bantuan dan dukungan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin mengucapkan terima kasih kepada pihak-pihak yang telah berjasa dalam penulisan tesis ini maupun selama penulis kuliah. Ucapan terima kasih terhatur kepada: 1. Bapak Dr. Hengki Tasman, M.Si, selaku dosen pembimbing tesis yang teramat banyak memberikan nasihat, bantuan, masukan dan dorongan semangat kepada penulis dalam menyelesaikan tesis ini; 2. Bapak Prof. Dr. Djati Kerami, selaku dosen pembimbing dan Ketua Program Studi Magister Matematika yang sekaligus dosen pembimbing akademik dan Bapak Dr. rer. nat Hendri Murfi, M.Kom selaku sekretaris Program Studi Magister Matematika yang telah banyak memberikan arahan kepada penulis selama menyelesaikan masa studi; 3. Bapak Dr. Yudi Satria, M.T, selaku ketua Departemen Matematika FMIPA UI dan Ibu Rahmi Rusin S.Si, M.Sc.Tech, selaku Sekretaris Departemen Matematika FMIPA UI; 4. Seluruh staf pengajar di Program Magister Matematika FMIPA UI, atas arahan, bimbingan, dan ilmu pengetahuan yang telah diberikan selama perkuliahan; 5. Pemerintah Propinsi Jambi melalui Dinas Pendidikan Propinsi yang telah memberikan kesempatan dan dukungan melalui program beasiswa. 6. Ibunda tercinta (Waliyem dan Yamcik A.Ma.Pd) yang telah memberikan dukungan moral, materiil, serta doa yang tidak pernah berhenti; 7. Istriku tercinta Renny Marina dan anakku tersayang Annida Syahidah Maharani, Farwah Atikah Parameswari, atas segala dukungan, kesabaran, semangat, dan doa;

iv Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

8. Keluarga besar saya (mas Sudadi, Mbak Mulyani, Dik Wahadi, Dik Eni Ernawaty) yang telah memberikan dukungan moral, materiil, serta doa yang tidak pernah berhenti; 9. Saudara iparku tercinta (Sih Parmini, Saudi, Arika Febriyani, Awal Rulizal, Rakhmat Juniadi, Lidia Atrika). 10. Mas Lismanto, Dhek Pahrin, Dhek Henang, Mbak Desi, Mas Susila, Mas Haryono, Akang Salim, Mbak Iik, Ibu Sri Samsiyah dan semua teman-teman S2 UI dari Jambi angkatan pertama yang telah berjuang bersama. 11. Kepada semua teman-teman yang telah memberi semangat terutama temanteman megister angkatan 2009 di Matematika UI. 12. Kepada semua pihak yang telah membantu penulis dalam pengerjaan tesis ini, yang namanya tidak bisa disebutkan satu-persatu, penulis ucapkan terima kasih.

Akhir kata, saya berharap kepada Tuhan Yang Maha Kuasa berkenan membalas segala kebaikan semua pihak yang telah membantu. Semoga tesis ini dapat bermanfaat bagi yang membacanya, terutama untuk pengembangan ilmu pengetahuan.

Penulis 2011

v Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI TUGAS AKHIR UNTUK KEPENTINGAN AKADEMIK Sebagai civitas akademik Universitas Indonesia, saya yang bertanda tangan di bawah ini ; Nama

:

Mulyadi

NPM

:

0906577362

Program Studi

:

Magister Matematika

Departemen

:

Matematika

Fakultas

:

Matematika dan Ilmu Pengetahuan Alam

Jenis Karya

:

Tesis

Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Indonesia, hak bebas biaya royalti noneksklusif (Non-exclusive royalti-free right) atas karya ilmiah saya berjudul : “ Perbandingan Sistem Persamaan linier dalam Aljabar Klasik dan Aljabar Maxplus” beserta perangkat yang ada (jika diperlukan). Dengan hak bebas biaya royalti non eksklusif ini Universitas Indonesia berhak untuk menyimpan, mengalih media/formatkan, mengelola dalam bentuk data (data base), merawat, dan mempublikasikan tugas akhir saya selama tetap mencantumkan nama saya sebagai penulis/pencipta dan sebagai hak cipta.

Demikian pernyataan ini saya buat dengan sebenarnya.

Dibuat di

: Depok

Pada Tanggal

: 13 Juli 2011

Yang menyatakan

(Mulyadi)

vi Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

ABSTRAK

Nama Program Studi Judul Tesis

: : :

Mulyadi Magister Matematika Perbandingan Sistem Persamaan linier dalam Aljabar Klasik dan Aljabar Max-plus.

Aljabar Max-plus mempunyai karakteristik yang berbeda dengan aljabar klasik. Dalam tesis ini dikaji struktur Aljabar Max-plus dan perbedaan sistem persamaan linier dalam Aljabar Max-plus dan aljabar klasik.

Kata kunci : Aljabar Max-Plus, Sistem Persamaan Linier.

vii Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

ABSTRACT

Name Study Program Title

: : :

Mulyadi Magister of Mathematics Comparison of linear equation systems in classical algebra and Max-Plus Algebra.

Max-Plus algebra has characteristics that are different from clasisical algebra. In this thesis, algebraic structure of Max-plus algebra studied. Differences of linear equation systems in Max-plus algebra and classical algebra are explored.

Key words: Max-plus algebra, , linear equation system.

viii Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

DAFTAR ISI

HALAMAN JUDUL............................................................................................. HALAMAN PERNYATAAN ORISINALITAS .................................................. LEMBAR PENGESAHAN .................................................................................. KATA PENGANTAR .......................................................................................... LEMBAR PERSETUJUAN PUBLIKASI ILMIAH ............................................ ABSTRAK ............................................................................................................ DAFTAR ISI ......................................................................................................... DAFTAR TABEL ................................................................................................. DAFTAR GAMBAR ........................................................................................... BAB 1

i ii iii iv vi vii ix xi xii

PENDAHULUAN ................................................................................. 1.1 Latar Belakang ................................................................................ 1.2 Permasalahan................................................................................... 1.3 Tujuan Penelitian ............................................................................ 1.4 Manfaat Penelitian .......................................................................... 1.5 Metode Penelitian............................................................................ 1.6 Sistematika Penulisan .....................................................................

1 1 2 2 2 2 2

BAB 2 ALJABAR MAX-PLUS ........................................................................ 2.1 Definisi aljabar Max-plus ................................................................ 2.2 Matriks dalam aljabar Max-Plus .................................................. 2.3 Teori Graf dan aljabar Max-Plus...................................................

4 4 11 17

BAB 3 BEBERAPA PERBANDINGAN DALAM ALJABAR KLASIK DAN ALJABAR MAX-PLUS ........................................................................ 22 3.1 Fungsi Linier ................................................................................... 22 3.1.1 Fungsi linier dalam aljabar klasik ...................................... 22 3.1.2 Fungsi linier dalam aljabar Max-plus ................................ 22 3.2 Fungsi Afin ..................................................................................... 24 3.2.1 Fungsi afin aljabar klasik ................................................... 25 3.2.2 Fungsi afin aljabar Max-plus ............................................. 25 3.3 Persamaan Afin ............................................................................... 27 3.3.1 Persamaan linier (afin) aljabar klasik ................................ 27 3.3.2 Pertidaksamaan linier (afin) aljabar klasik ........................ 28 3.3.3 Persamaan afin aljabar Max-Plus ................................... 29 3.4 Sistem Persamaan Linier ................................................................ 37 3.4.1 Sistem Persamaan Linier aljabar klasik ............................. 37 3.4.2 Sistem Persamaan Linier aljabar Max-Plus bentuk = .................................................... 38 3.4.3 Sistem Persamaan Linier aljabar Max-Plus bentuk ................................................................... 41 3.4.4 Sistem Persamaan Linier aljabar Max-Plus bentuk ........................................................................ 45 ix Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

BAB 4

PENUTUP.............................................................................................. 4.1 Kesimpulan ....................................................................................... 4.2 Saran ..................................................................................................

50 50 50

DAFTAR PUSTAKA ...........................................................................................

51

x Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

DAFTAR TABEL Tabel 1 Pengoperasian pada aljabar Max-plus ....................................................

8

Tabel 2 Pengoperasian pangkat pada aljabar Max -plus ......................................

9

Tabel 3 Pengoperasian pangkat pada aljabar Max -plus ....................................

11

Tabel 4 Perbandingan fungsi linier pada aljabar klasik dan aljabar Max-plus .

24

Tabel 5 Perbandingan fungsi afin pada aljabar klasik dan aljabar Max-plus ...

26

Tabel 6 Perbandingan persamaan linier pada aljabar klasik dan persamaan afin aljabar Max-plus ..................................................................................

36

Tabel 7 Perbandingan persamaan linier pada aljabar klasik dan aljabar Max-plus 48

xi Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

DAFTAR GAMBAR

Gambar 1

Graf

Gambar 2

Grafik fungsi linier

Gambar 3


Gambar 4

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

19

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

23

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

24


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

24

Gambar 5


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

24

Gambar 6


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

24

Gambar 7

Grafik fungsi afin

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

25

Gambar 8

Grafik fungsi afin

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

25

Gambar 9


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

26

Gambar 10


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

26

Gambar 11


Gambar 12

Grafik fungsi afin

Gambar 13


Gambar 14

Grafik fungsi afin

Gambar 15

Grafik pertidaksamaan

Gambar 16

dan

........

26

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

26

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

26

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

26

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

29

Teorema 3.3.3.2 (a.1) Persamaan

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

30

Gambar 17

Teorema 3.3.3.2 (a.2) Persamaan

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

30

Gambar 18

Teorema 3.3.3.2 (b.1) Persamaan

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

30

Gambar 19

Teorema 3.3.3.2 (b.2) Persamaan

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

30

Gambar 20

Teorema3.3.3.2 (c) Persamaan

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

30

Gambar 21

Teorema 3.3.3.2 (d) Persamaan

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

30

Gambar 22

Teorema 3.3.3.2 (e) Persamaan

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

31

Gambar 23

Grafik SPL

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

38

Gambar 24

Graf

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

42

Gambar 25

Grafik SPL

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

48

Gambar 26

Grafik SPL

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

48

xii Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

BAB I PENDAHULUAN

1.1 Latar Belakang Matematika merupakan ilmu yang mendasari semua disiplin ilmu yang ada, baik disiplin ilmu sosial, ilmu esakta, sains dan teknologi, sehingga menempatkan matematika sebagai mother of sciences. Salah satu cabang matematika adalah aljabar. Aljabar memegang peranan sangat penting dalam perkembangan disiplin ilmu – ilmu lain. Perkembangan aljabar sangat berkaitan erat dengan cabang – cabang ilmu matematika yang lain seperti Geometri, Teori Bilangan, Statistik, Ilmu Komputer, Logika, Ilmu Analisis bahkan Matematika Terapan dan lain- lain[6]. Aljabar Max-plus merupakan salah satu topik dalam ruang lingkup aljabar. Aljabar Max-plus didefinisikan sebagai himpunan semua bilangan real, yang dilengkapi Operasi

adalah himpunan

dengan dua operasi biner yaitu

menyatakan operasi maksimum, dan dinotasikan

, dengan

.

adalah operasi jumlahan. Himpunan

yang dilengkapi dua operasi biner (

. Aljabar Max-plus yang dinotasikan

dinotasikan merupakan salah satu

struktur aljabar yang semilapangan komutatif idempoten [2, 5, 6, 10]. Elemen identitas pada operasi penjumlahan

(elemen nol) dan elemen identitas pada operasi perkalian

(elemen satu) berturut-turut adalah

, dan

. Operasi

didefini-

sikan sebagai berikut [2, 3, 5, 6, 10]:

Bentuk lain dari aljabar Max-plus adalah aljabar Min-plus, dengan minimum dan identitas jumlahannya adalah

menyatakan

Operasi dasar pada aljabar Max-plus

adalah maksimum dan penjumlahan, yang dalam operasi aljabar linier klasik (konvensional) adalah penjumlahan dan perkalian. Beberapa sifat dan konsep dalam aljabar linier, akan berlaku dalam aljabar Max-plus [2, 5, 6].

1 Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

Universitas Indonesia

2

1.2 Permasalahan Aljabar Max-plus merupakan salah satu topik dalam ruang lingkup aljabar. Untuk itu struktur aljabar Max-plus perlu dipelajari secara mendalam. 1.2.1 Masalah umum Bagaimana konsep dasar aljabar Max-plus ? 1.2.2 Masalah khusus Bagaimana perbedaan sistem persamaan linier dalam aljabar klasik dan aljabar Max-plus ? 1.3 Tujuan Penelitian Berdasarkan latar belakang dan permasalahan di atas, dalam tesis ini bertujuan untuk: 1.3.1 Menjelaskan konsep dasar aljabar Max-plus. 1.3.2 Menjelaskan perbedaan sistem persamaan linier dalam aljabar klasik dan aljabar Max-plus.

1.4 Manfaat Penelitian Secara umum penelitian ini bermanfaat untuk memberikan wawasan yang relatif baru dalam bidang teori sistem linier. 1.5 Metode Penelitian Penelitian dilakukan dengan mempelajari karya ilmiah yang disajikan dalam bentuk buku, disertasi ataupun paper yang relevan dengan topik penelitian. Kemudian hasilnya dijabarkan dan disusun kembali secara rinci menjadi suatu karya tulis.

1.6 Sistematika Penulisan Tesis ini terdiri dari empat bab, yaitu: Bab I : Mengemukakan latar belakang, permasalahan, tujuan, manfaat, metode penelitian dan sistematika penulisan. Bab II: Membahas konsep-konsep dasar tentang aljabar Max-plus, matriks dan graf

Universitas Indonesia Perbandingan sistem..., Mulyadi, FMIPA UI, 2011

3

Bab III: Membahas fungsi linier dan fungsi afin, persamaan linier dan persamaan afin, sistem persamaan linier dalam aljabar Max-plus, dan beberapa perbandingan aljabar linier dan aljabar Max-plus. Bab IV: Kesimpulan dari pembahasan dan saran. Daftar Pustaka


BAB II ALJABAR MAX-PLUS Pada bab ini dibahas beberapa konsep dasar operasi dalam aljabar Max-plus. Pembahasan meliputi sifat–sifat aljabar Max-plus [2, 5, 10], matriks dan operasinya dalam aljabar Max-plus [3, 5, 10, 11], teori graf dalam aljabar Max-plus [2, 5, 6, 11,12]. 2.1. Definisi Aljabar Max-Plus Pada aljabar Max-plus, sifat- sifatnya dapat diketahui dari beberapa definisi dan sifat dalam aljabar klasik pada umumnya [2, 5,10]. Beberapa definisi yang berkaitan adalah sebagai berikut. Definisi 2.1.1 Misalkan

adalah himpunan tak kosong. Operasi biner

pada

adalah suatu fungsi

Definisi 2.1.2 Sistem matematika adalah suatu himpunan tak kosong yang dilengkapi oleh satu atau lebih operasi biner. Definisi 2.1.3 Himpunan

bersama dua operasi biner

pada

dikatakan semila-

pangan jika: A.

Sistem matematika (

,

) memenuhi aksioma- aksioma berikut:

a. Bersifat asosiatif; ,

.

b. Bersifat komutatif; , c. Terdapat elemen identias 0 (nol) di B.

Sistem matematika (

, sehingga

,

, ) suatu grup, jika memenuhi;

a. Bersifat asosiatif; ,

.

b. Terdapat elemen identitas 1(satuan) ,

yang bersifat; .

4 Perbandingan sistem..., Mulyadi, FMIPA UI, 2011


5

c. Menpunyai invers,

C.

D.

terdapat

yang bersifat:

Bersifat distributif kanan ; ,

.

,

.

Bersifat distributif kiri ;

Definsi 2. 1.4 Himpunan

pada

yang dilengkapi dua operasi biner

dikatakan semi-

lapangan yang komutatif dan idempoten jika: A.

Sistem matematika

B.

Bersifat komutatif terhadap operasi , yaitu

C.

Bersifat idempoten terhadap operasi

merupakan semilapangan; , ,

, yaitu

Teorema 2.1.5 Unsur nol (0) pada semilapangan

yang idempoten memenuhi

,

. Bukti: Berdasarkan sifat idempoten, kita mempunyai:

, kedua ruas ditambahkan

Dengan demikian,

berlaku 0

, dengan Definisi 2.1.3 B (c)

, maka = Terbukti bahwa

= =

=

= .

.


6

Definisi 2.1.6 Diberikan himpunan bilangan real sama dengan dua operasi biner sembarang bilangan

ber-

(dibaca o kali). Jika diberikan

(dibaca o plus) dan

dan y, maka

gan tersebut, dan

dinotasikan sebagai

adalah nilai maksimum dari salah satu bilan-

adalah penjumlahan dari kedua bilangan tersebut. Dengan de-

mikian sistem matematika yang mempunyai operasi

yang dimaknakan dendan

gan nilai maksimum dan penjumlahan disebut aljabar Max-plus dinotasikan didefinisikan: , , .

untuk setiap

Dari Definisi 2.1.6 operasi biner

pada

mum dari dua bilangan. Hal ini berakibat

didefinisikan sebagai nilai maksijika dan hanya jika

.

Teorema 2. 1.7 merupakan semilapangan yang komutatif dan idempoten. Bukti: I.

merupakan semilapangan. 1. Sistem matematika (

memenuhi aksioma- aksioma berikut:

a. Bersifat asosiatif;

operasi

bersifat asosiatif di

b. Bersifat komutatif; = operasi

bersifat komutatif di

c. Terdapat unsur nol

di

, .

; ,

Jadi

adalah unsur nol di

terhadap operasi

.


7

2. Sistem matematika (

membentuk suatu grup.

a. Bersifat asosiatif; , operasi

bersifat asosiatif di

b. Terdapat unsur satuan

yang bersifat;

adalah unsur satuan di c. Untuk setiap

terhadap operasi

terdapat

yang bersifat:

Jadi 3. Operasi

terhadap operasi bersifat distributif kanan terhadap

.

. ,

. operasi 4. Operasi

bersifat distributif kanan terhadap operasi

bersifat distributif kiri terhadap

di

.

. ,

. operasi

bersifat distributif kiri terhadap operasi

Jadi berdasarkan 1 sampai 4 II.

Selanjutnya

di

.

merupakan suatu semilapangan.

semilapangan dikatakan komutatif dan idempoten, jika;

1. Terhadap operasi

bersifat komutatif; ,

terhadap operasi 2. Terhadap operasi

bersifat komutatif di

.

bersifat idempotent; ,

operasi

bersifat idempoten di

Jadi berdasarkan (I) dan (II)

adalah semilapangan yang komutatif dan idem-

poten.


8

Operasi biner

pada

yang merupakan operasi maksimum pada aljabar klasik,

tidak mempunyai invers (balikan). Dengan demikian pada pat

yang bersifat

jika

atau

operasi

,

karena

. Jadi jelaslah bahwa

tidak terdajika dan hanya

tidak mempunyai invers terhadap

dalam aljabar Max-plus.

Diberikan operasi biner

(dibaca o bagi) pada

yang didefinisikan sebagai

operasi pengurangan dalam aljabar klasik. Sesuai kaidah pengoperasian, pada aljabar Max-plus operasi biner

dan

dilakukan operasi lebih dulu daripada operasi biner

.

Contoh 2.1.9 Tabel 1. Pengoperasian dalam aljabar Max- plus Operasi pada aljabar

Operasi pada aljabar klasik

Hasil 5 7

8 18 11 9 7+ ( 6–4

2 =

=

6 14


9

Definisi 2.1.10 Diberikan kat

dengan

dari elemen x

adalah himpunan bilangan asli, dan x

. Pang-

dalam aljabar Max-plus dinotasikan dengan

dide-

finisikan sebagai berikut: =

, (operasi perkalian dalam

n

n bilangan real biasa).

Jika diperluas pangkat aljabar Max-plus secara umum diperoleh sebagai berikut: a. Jika b. Jika c. Jika d. Jika

maka , maka , maka dan

. ( untuk , maka

. =

=

Contoh 2.1.11 Tabel 2. Pengoperasian pangkat pada aljabar Max-plus Operasi pada aljabar


Hasil


10

Operasi pada aljabar


Hasil

=

12

= =

20

=

Beberapa sifat dalam operasi bilangan pangkat pada aljabar Max-plus adalah sebagai berikut. Lemma 2.1.12 Untuk setiap

dan x, y

berlaku:

1. 2. 3. 4. Bukti: 1. n

m n

m

+

= .

2.

= m

m

= n

=

=

n

3. 4. m

m


11

m

m

Dalam urutan pengoperasian pangkat pada aljabar Max-plus operasi biner lakukan terlebih dahulu daripada operasi biner

di-

.

Contoh: 2.1.13 Tabel 3. Pengoperasian pangkat pada aljabar Max-plus Operasi pada aljabar

Nilai


32

2.2 MATRIKS DALAM ALJABAR MAX- PLUS Pada subbab ini dibahas pengantar tentang matriks dalam aljabar Max-plus. Sebagai bahan rujukan dalam materi ini dapat ditemukan dalam [2,3, 5,10]. Pada subbab 2.1 telah dijelaskan bahwa aljabar Max-plus adalah semilapangan yang idempoten, selanjutnya diperkenalkan struktur baru yang disebut moduloid. Definisi 2.2.1 Diberikan semilapangan yang idempoten operasi punan

dengan elemen identitas 0 (nol) pada

dan elemen identitas 1(satu) pada operasi

. Moduloid

atas

adalah him-

yang dilengkapi dengan:

1. Operasi biner

dan elemen identitas 0;

2. Operasi biner


12

dan memenuhi aksioma- aksioma berikut: a. Bersifat asosiatif;

,

b. Bersifat komutatif;

,

c.

,

d.

,

e.

,

f.

,

g.

,

setiap setiap setiap

Definisi 2.2.2 Suatu himpunan matriks berordo

dengan

pada aljabar Max-plus

. Secara lengkap ditulis matriks dalam

dinotasikan sebagai untuk menyatakan kolom ke-

menyatakan baris ke-

dengan

dan

dengan

Matriks

dituliskan sebagai berikut:

.

Teorema 2.2.3 Diberikan

yang dilengkapi operasi biner , dengan

biner Maka

dari

pada

,

.

adalah merupakan moduloid atas

pada

. ,

setiap

=

dan operasi .

.

Bukti:

adalah merupakan moduloid atas

jika :

a. Bersifat komutatif ;

b. Bersifat asosiatif;

,


13

,

c.

dan

; ,

d.

dan

;

e.

dan

; ;

f.

.

g.

Jadi berdasarkan aksioma dalam Definisi 2.2.1

merupakan moduloid atas

.

Definisi 2.2.4 Moduloid

dengan penambahan satu operasi biner

yang dinotasikan dengan

disebut aljabar idempoten, jika memenuhi aksioma – aksioma berikut: a. Bersifat asosiatif; b. Terdapat elemen identitas

(satu) di

yang bersifat

= =

,

c. Bersifat distributif kiri; d. Bersifat distributif kanan; Teorema 2.2.5 Moduloid

yang ditambah satu operasi biner

pada

=

=

yaitu:

,

adalah

aljabar idempoten. Bukti:

a. Bersifat asosiatif;

= =

=

,

; b. Terdapat unsur satuan

( = 0) yang merupakan matriks berukuran

dengan elemen – elemen diagonal utama sama dengan lain sama dengan

Matriks

bersifat

=

,

dan elemen-elemen yang =

,

.


14

Matriks

disebut matriks identitas. Dibuktikan

=

=

,

sebagai berikut: = Dengan

, untuk untuk

dan

.

sehingga

dituliskan menjadi; Untuk

,

Dan demikian seterusnya, hingga sampai

, sehingga diperoleh:

. =

, untuk

. Dengan

untuk

dan

sehingga

dituliskan menjadi : Untuk

,

Dan demikian seterusnya, hingga sampai

, sehingga diperoleh:

. Dengan demikian dari

dan

terbukti bahwa

=

=

,

c. Bersifat distributif kiri;


15

,

.

d. Bersifat distributif kanan;

,

.

Dengan demikian dari (a), (b), (c) dan (d) terbukti bahwa

adalah aljabar

idempoten. Definisi 2.2.6 1. Diberikan

, maka transpose dari matriks

dinotasikan dengan

, didefinisikan sebagai:

2. Diberikan

, dengan

, untuk setiap

. Matriks

disebut

pangkat

dari

matriks nol Max-plus. 3. Diberikan

dan diberikan

matriks

dinotasikan dengan =

didefinisikan sebagai:

.

n Untuk

,

adalah sebuah matriks identitas. Lebih lanjut dapat di-

perjelas untuk pangkat pada matriks sebagai berikut [4, 9, 10, 12]: Untuk unsur =

pada matriks

adalah: =

.


16

pada matriks

Untuk unsur

adalah:

=

=

=

.

Dari ilustrasi di atas, maka secara umum unsur

pangkat matriks dalam al-

jabar Max-plus dapat disimpulkan sebagai berikut: =

=

.

= Selanjutnya jika diberikan

dan diberikan sebarang skalar

adalah pangkat, maka unsur

matriks

,

didefinisikan

sebagai berikut: = =(

+ n

=

, untuk dan

Jadi untuk sebarang = Jika diberikan sebarang

,

maka berlaku:

, untuk , maka

.

Contoh 2.2.7 1. Diberikan matriks

,

dan

Tentukan: a.

.

b. 5 .


17

c.

. d.

. e.

.

2.3 TEORI GRAF DAN ALJABAR MAX-PLUS Secara khusus teori graf mempunyai peranan penting dalam masalah sistem persamaan linier. Sebagai bahan rujukan terdapat pada [2,5,6,11,12] Definisi 2.3.1 Sebuah graf berarah

adalah pasangan V dan E, dinotasikan sebagai

dengan V adalah himpunan simpul – simpul dan busur. Sebuah busur tertentu nya dari

dengan

adalah himpunan busur – adalah busur berarah yang arah-

.


18

Definisi 2.3.2 Diberikan matriks

, graf terhubung dari matriks

dengan simpul

adalah graf . Graf berarah

dan busur

dikatakan berbobot, jika untuk setiap busur dengan bilangan real

Bilangan real

dipasangkan

disebut bobot busur

yang dinotasikan

. Contoh 2.3.3 Diberikan matriks

, maka graf

mempunyai simpul

dengan bobot masing – masing busur adalah :

dan busur 1, -2, 4, dan 3. Definisi 2.3.4 Diberikan suatu graf berarah lam graf berarah ,

. Sebuah lintasan (path)

adalah barisan berhingga dari busur sedemikian hingga setiap (

. Suatu lintasan

yang panjangnya

,

da) dengan

adalah busur dari graf berarah

yang mempunyai panjang

Himpunan lintasan dari

=

dari

dinotasikan dengan

dinotasikan dengan

. .

Contoh 2.3.5 Diberikan graf seperti berikut: 1

2

3

Gambar 1. Graf

Dari Gambar 1 barisan busur (3, 2),(2, 2), (2, 1), (1, 1), (1,2) merupakan suatu lintasan dalam graf

yang dapat direpresentasikan dengan 3 2 2

dengan panjang 5, karena tersusun atas 5 busur, yang dinotasikan dengan Lintasan 1 2

3

1

2, .

2 mempunyai panjang 4, karena terdiri atas 4 busur dan ditulis

.


19

Definisi 2.3.6 Sebuah simpul

dapat dicapai dari simpul

. Sebuah graf berarah

diartikan ada sebuah lintasan dari

terhubung kuat jika setiap simpul dapat dicapai

dari setiap simpul yang lain. Definisi 2.3.7 Diberikan graf berarah

. Sebuah sirkuit adalah suatu lintasan tertu-

tup atau dengan kata lain simpul awal dan simpul akhir sama, sedemikian hingga . Selanjutnya sebuah sirkuit yang terdiri atas satu busur disebut sebuah loop. Sebuah sirkuit elementer adalah sirkuit yang simpul-simpulnya muncul tidak lebih dari sekali, kecuali simpul awal yang muncul tepat dua kali. Panjang lintasan terpendek yang dilalui dari simpul

ke

adalah jarak. Lintasan dan sirkuit dari

mempunyai bo-

bot, bobotnya adalah ditentukan dari elemen-elemen matriks

.

Contoh 2.3.8 Pada graf berarah dalam contoh 2.3.5 lintasan

1 2

dan 1 2

merupakan suatu sirkuit elementer dengan panjang 3 dan panjang 2. Lintasan 1 dan 1

merupakan suatu loop, karena hanya ada satu busur. Lintasan 1 2 dan 3

2

2

merupakan sirkuit dengan panjang 5.

Definisi 2.3.9 Diberikan suatu graf berarah berbobot Bobot suatu lintasan

dari simpul

ke

dengan dengan panjang

. Bobot rata-rata lintasan

.

dinotasikan dengan

(perhitungannya dalam aljabar

klasik). Contoh 2.3.10 Graf

pada contoh 2.3.3 mempunyai lintasan

=1 2

, dengan

dan . Bobot rata-rata lintasan

adalah

=

= .


20

Berikut ini adalah interpretasi dalam teori graf untuk pangkat , graf terhubung dari

adalah graf

maka elemen kedalam = = Karena

max

max

1 i1, i 2 ,..., i k 1 n

max

dengan

adalah :

1 i1, i 2 ,..., i k 1 n

1 i1, i 2 ,..., i k 1 n

Jika

pada matriks

( Ai, i k 1  ...  Ai 2 , i1  Ai1, j )

( Ai1, j  Ai 2 , i1  ...  Ai, i k 1) , untuk setiap

( Ai1, j  Ai 2 , i1  ...  Ai, i k 1) merupakan bobot lintasan dengan

panjang

dari simpul ( sebagai simpul awal) ke simpul (sebagai simpul akhir) dalam

graf

. Dengan demikian

dalam graf

merupakan bobot maksimum semua lintasan

dengan panjang

dari simpul

tidak ada lintasan dengan panjang

ke simpul . Jika dalam graf

dari simpul ke simpul

maka bobot maksimum

didefinisikan dengan Contoh 2.3.11 Diberikan matriks dengan panjang diberikan

, bobot maksimum semua lintasan dalam yang ditentukan dari elemen-elemen di

. Misalkan

berikut:

=

,

=

,

Diperhatikan bahwa

=

= , maka bobot maksimum semua lintasan di

dengan panjang 2 yang berawal dari simpul 1 dan berakhir di simpul 3 adalah Lintasan tersebut adalah 1 2 =

=

.

dan bobot lintasan adalah

. Dimana lintasan dengan panjang 2 yang berawal dari

simpul 2 dan berakhir di simpul 3 hanya ada satu lintasan. bobot maksimum semua lintasan di

= 4 artinya adalah

dengan panjang 2 yang berawal dari simpul 2

dan berakhir di simpul 3 adalah 4. Lintasan tersebut adalah 2 2

=

=

= 6 yaitu bobot

. Demikian halnya dengan

maksimum semua lintasan di

dengan panjang 3 yang berawal dari simpul 2 dan

berakhir di simpul 1 adalah 6. Lintasan di

dengan panjang 3 ada 4 yaitu


21

(1). , (2). , (3). , (4). . Berdasarkan ke- 4 lintasan di atas, diperoleh bobot maksimum dari lintasan =

. Demikian juga untuk

maksimum sirkuit dalam adalah 1. Untuk

= 1 yaitu bobot

dengan panjang 3 yang berawal dan berakhir di simpul 3 = 7 artinya bobot maksimum dari lintasan dalam

dengan

panjang 4 yang berawal dari simpul 3 dan berakhir di simpul 1 adalah 7.


BAB III BEBERAPA PERBANDINGAN DALAM ALJABAR KLASIK DAN ALJABAR MAX-PLUS Pada bab ini dibahas beberapa konsep yang meliputi fungsi linier, fungsi afin, sistem persamaan linier dalam aljabar klasik dan aljabar Max-plus. 3.1 FUNGSI LINIER Pada subbab ini dibahas tentang fungsi linier pada aljabar klasik dan aljabar maxplus [2, 5, 6, 10]. 3.1.1

Fungsi linier dalam aljabar klasik

Definisi 3.1.1.1 Fungsi

dikatakan fungsi linier, jika memenuhi; Untuk sebarang

berlaku : (1)

Untuk sebarang

dan skalar

berlaku : (2)

Contoh 3.1.1.2 Tunjukan

dengan

, untuk setiap

adalah fungsi linier

Penyelesaian: Ambil sebarang

, maka : (3)

dan untuk sebarang

dan skalar

berlaku: (4)

Dari (3) dan (4) terbukti bahwa 3.1.2

adalah fungsi linier.

Fungsi linier dalam aljabar Max-plus

Definsi 3.1.2.1 Fungsi

dikatakan fungsi linier dalam aljabar Max –plus, jika meme-

nuhi: Untuk setiap

, berlaku

.

22



23

Dengan memisalkan

didapat

. Akibatnya diperoleh

kemiringan fungsi linier (garis) tersebut

= 1. Jadi kemiringan semua fungsi

linier dalam aljabar Max-plus bentuk di atas adalah selalu 1. Fungsi linier

, mempunyai titik potong terhadap sumbu

diperoleh dengan mensubtitusikan titik

ke dalam fungsi

yang ,

sebagai berikut : = = =

(kedua ruas ditambah dengan (-a)) =

Jadi titik potong fungsi lanjutnya

untuk

terhadap sumbu

menentukan

titik

, terhadap sumbu

potong

fungsi

adalah titik linier

aljabar

. SeMax-plus

yang diperoleh dengan mensubtitusikan titik

ke dalam fungsi

, sebagai berikut:

. Jadi titik potong fungsi

terhadap sumbu


adalah titik

.

, aljabar Max-plus sebagai berikut: y

Rmax

y=f(x)= a × x a -a

0

Rmax x

Gambar 2. Grafik fungsi linier


24

Contoh 3.1.2.2 Tabel 4. Perbandingan fungsi linier aljabar klasik dan aljabar Max-plus No 1.

Operasi pada aljabar klasik a.

Operasi pada aljabar Max-plus a.

y

y Rmax y=f(x) = x

y=f(x)= 1 × x

x 0

1

Rmax x

-1 0



2.

b.

b. y

y Rmax

y=f(x) = 2x

y=f(x)= 2 × x 2

y=f(x) = x x 0

1 -2


-1 0

y=f(x)= 1 × x Rmax x


Diperhatikan grafik fungsi linier Tabel 4 di atas, diketahui bahwa grafik fungsi linier aljabar klasik

diperoleh dengan merotasikan fungsi linier Pada fungsi linier aljabar Max-plus

dengan menggeser sejajar dengan

sejauh

sebesar diperoleh

satuan.

3.2 Fungsi Afin Pada subbab ini dibahas tentang fungsi afin dalam aljabar klasik dan aljabar Maxplus [2, 5, 6, 10].


25

3.2.1 Fungsi afin aljabar klasik Definisi 3.2.1.1 Fungsi

dikatakan fungsi afin dalam aljabar klasik, jika untuk setiap

dan ada

berlaku

.

Langkah – langkah untuk menggambar grafik fungsi afin klasik sebagai berikut : 1. Menggambarkan grafik fungsi linier untuk 2. Mengeser fungsi linier

sebesar

; satuan searah sumbu

Contoh 3.2.1.2 Tentukan grafik fungsi afin Selesaian: y

y y=f(x) = 2x +3

3 y=f(x) = 2x

y=f(x) = 2x 3 -3/2

x 0

Gambar 7. Grafik fungsi afin

x

0

Gambar 8. Grafik fungsi afin

3.2.2 Fungsi afin aljabar Max-plus Definisi 3.2.2.1 dikatakan fungsi afin dalam aljabar Max –plus, jika meme-

Fungsi nuhi: Untuk setiap

, dan ada

, berlaku

Dalam aljabar klasik nilai afin, pada titik

dituliskan

. =

. Langkah – langkah untuk menggambar grafik fungsi afin aljabar Max-plus sebagai berikut : 1. Menggambarkan grafik fungsi linier untuk 2. Menggambarkan grafik fungsi linier


26

3. Menggabungkan langkah 1 dan langkah 2, kemudian dipilih nilai maksimum dari kedua fungsi, untuk setiap Untuk

memperjelas,

.

diberikan

=

gambar

fungsi

afin

aljabar

Max-plus

sesuai urutan langkah langkah di atas, sebagai

berikut: Rmax

y

y=f(x)= a a -a

y = f(x)=b

× x Rmax x

0

Rmax x

0

Gambar 10. Fungsi linier

Gambar 9. Fungsi linier y

Rmax

y

Rmax

Rmax

y

y=f(x)= a × x

y=f(x)= (a × x) + b y = f(x) =b

Y = f(x)= b

a

a -a

Rmax x

0

-a

Rmax x

0

Gambar 12. Fungsi afin

Gambar 11. Fungsi linier dan

Contoh 3.2.2.2 Tabel 5. Perbandingan fungsi afin pada aljabar klasik dan aljabar Max-plus

No


Operasi pada aljabar Max-plus

1.

Tentukan grafik fungsi afin

Tentukan grafik fungsi afin

Selesaian:

Selesaian: y

3

y=f(x)= (1 × x) + 3

y=f(x) = x

3

x -3

0

1 -1

Gambar 13. Grafik

Rmax

y

y=f(x) = x+3

0

Rmax x

Gambar 14. Grafik


27

Diperhatikan dalam fungsi afin Tabel 5 di atas, diketahui bahwa grafik fungsi linier aljabar klasik diperoleh dengan menggeser fungsi linier sumbu

sejauh

satuan searah

Pada fungsi afin aljabar Max-plus diperoleh dengan menggabungkan fungsi

linier

dan

sehingga diperoleh

dan dipilih

dari gabungan keduanya yang maksimum. 3.3 Persamaan Afin Pada subbab ini dibahas tentang persamaan afin dalam aljabar klasik dan aljabar Max-plus [2, 5, 6, 10]. 3.3.1. Persamaan linier (Afin) pada aljabar klasik Dari bentuk fungsi afin

, dengan

maka pembuat nol fungsi afin tersebut adalah

konstanta dan akibatnya

.

adalah merupakan bentuk umum persamaan linier

Sedemikian hingga,

dengan satu peubah. Langkah-langkah dalam menyelesaikan persamaan linier satu peubah sebagai berikut: 1. Kedua ruas persamaan ditambah atau dikurangi dengan bilangan sebesar 2. Kedua ruas persamaan dikalikan dengan bilangan sebesar bilangan sebesar

atau dibagi dengan

Contoh 3.3.1.1 Tentukan nilai yang memenuhi persamaan linier Penyelesaian:

( kedua ruas ditambah dengan -6)

( kedua ruas dikalikan )

.


28

3.3.2. Pertidaksamaan linier (Afin) pada aljabar klasik Dari bentuk fungsi afin

, dengan

maka pembuat tak nol persamaan fungsi afin adalah

konstanta dan , akibatnya

. Sedemikian hingga pertidaksamaan tersebut yang mungkin adalah menggunakan salah tanda relasi “

Misalkan

sedemikian hingga

akibatnya

,

merupakan salah satu bentuk pertidaksamaan linier

dengan satu peubah. Langkah-langkah dalam menyelesaikan pertidaksamaan linier satu peubah sebagai berikut: 1. Kedua ruas pertidaksamaan ditambah atau dikurangi dengan bilangan sebesar 2. Kedua ruas pertidaksamaan dikalikan dengan bilangan sebesar atau dibagi dengan bilangan sebesar 3. Jika kedua ruas pertidaksamaan dikalikan dengan bilangan sebesar atau dibagi dengan bilangan sebesar –

, maka tanda pertidaksamaan harus dibalik.

Contoh 3.3.2.1 Tentukan nilai

yang memenuhi pertidakasamaan linier

Penyelesaian:

( kedua ruas ditambah dengan -6)

( kedua ruas dikalikan )

.


29

Dalam gambar grafik fungsi linier diperoleh : y 6

-2

y = f(x) = 3x + 6

x

0

Gambar 15. Grafik pertidaksamaan

3.3.3. Persamaan afin aljabar Max-plus Definisi 3.3.3.1 Bentuk umum persamaan afin aljabar Max-plus adalah : , untuk setiap terhadap operasi biner

(1)

tidak mempunyai invers, sehingga (1) ti-

dak dapat dinyatakan menjadi bentuk

. Maka untuk menyelesaikan per-

samaan afin aljabar Max-plus kita perlukan teorema berikut. Teorema 3.3.3.2 [2, 6] Secara umum selesaian persamaan afin aljabar Max-plus (1) adalah sebagai berikut: a. Jika

maka (1) mem-

punyai selesaian unik yaitu: b. Jika

dan

, dan

. atau

tidak terpenuhi, maka persamaan (1) tidak mempunyai selesaian. c. Jika

dan

, maka persamaan (1) mempunyai selesaian

dan selesaian tidak unik. d. Jika

dan


dan selesaian tidak unik. e. Jika semua

dan

, maka persamaan (1) mempunyai selesaian untuk

.

Bukti:


30

1.

Pembuktian selesaian persamaan afin secara geometris: y Rmax

y b b’

b’ b a

a’

a’

Rmax x

a

Rmax x

Gambar 16. Teorema 3.3.3.2 (a.1)

Gambar 17. Teorema 3.3.3.2 (a.2)

Persamaan afin

Persamaan afin

y Rmax

y b b’

b’ b a’

a

a

Rmax x

a’

Rmax x

Gambar 18. Teorema 3.3.3.2 (b.1)

Gambar 19. Teorema 3.3.3.2 (b.2)

Persamaan afin

Persamaan afin

Rmax

y Rmax

y b b’ a=a’

b=b’

Rmax x

a’

a

Rmax x

Gambar 20. Teorema 3.3.3.2 (c)

Gambar 21. Teorema 3.3.3.2 (d)

Persamaan afin

Persamaan afin


31

Rmax

y b=b’

a=a’

Rmax x

Gambar 22. Teorema 3.3.3.2 (e)

Persamaan afin

2.

Pembuktian selesaian dari persamaan afin: a. Jika

, maka selesaian persamaan (1) adalah unik yaitu Untuk memperolehnya akan kita tinjau 2 kasus

yaitu: a.1.Kasus pertama persamaan

:

Untuk menyelesaikan persamaan

, terdapat dua subkasus

selesaian yaitu: a.1.1. Selesaian untuk persamaan punyai selesaian karena a.1.2. Selesaian untuk persamaaan selesaian

. Subkasus ini tidak mem. Subkasus ini mempunyai (2)

a.2. Kasus kedua persamaan Untuk menyelesaian persamaan

, terdapat dua subkasus

yaitu: a.2.1. Selesaian untuk persamaaan selesaian a.2.2. Selesaian untuk persamaaan

Subkasus ini mempunyai (3) Subkasus ini tidak mempunyai

selesaian karena


32

Selanjutnya, diperhatikan persamaan (2) dan (3). Jika persamaan (2) kita substitusikan ke dalam persamaan (1) maka diperoleh : Ruas kiri : Diperhatikan persamaan (1) ruas kiri yaitu; yaitu ;

dan persamaan (2)

. Jika (2) disubstitusi ke dalam (1) akan diperoleh : =

=

.

Ruas kanan : Diperhatikan persamaan (1) ruas kanan yaitu;

yaitu;

dan bentuk (2)

. Jika (2) disubstitusi ke dalam (1) akan diperoleh : =

=

bahwa dalam (1) diketahui

=

Dimana

maka hasil ruas kiri akan memberikan

selesaian yang sama dengan ruas kanan yaitu:

.

Dengan kata lain tapi, karena

Akan te,

maka

selesaiannya selalu sama dengan

belum tentu

, hal ini dikarenakan tidak ada syarat yang

menjamin bahwa nilai

. Jadi persamaan (2) yaitu;

bukan merupakan selesaian dari persamaan (1) yaitu;

.

Selanjutnya, jika persamaan (3) kita substitusikan ke dalam persamaan (1) yaitu , maka diperoleh: Ruas kiri : Diperhatikan persamaaan (1) ruas kiri yaitu; yaitu;

dan persamaan (3)

. Jika (3) disubstitusi ke dalam (1) ruas kiri diperoleh : =

=

=

=

.

Ruas kanan : Diperhatikan persamaan (1) ruas kanan yaitu; yaitu;

dan persamaan (3)

. Jika (3) disubstitusi ke dalam (1) ruas kiri diperoleh : =

karena dalam (1) diketahui bahwa

=

=

,

. Maka hasil ruas kiri dan ruas kanan

memberikan selesaian yang sama yaitu: Jadi

. Dengan kata lain =

, me-


33

rupakan selesaian dari persamaan (1) yaitu: dan

dengan

.

Sedangkan untuk pembuktian dengan yaitu;

dan

akan memberikan

pada persamaan (1) selesaian unik yaitu ;

) dengan langkah – langkah yang sama dengan syarat

= dan

di atas.

b. Jika

, dan

tidak terpenuhi, maka persamaan (1) tidak mempunyai selesaian. c. Jika

dan


dan selesaian tidak unik. Dalam memperoleh selesian (1) kita tinjau 2 kasus yaitu : c.1. Kasus pertama persamaan Untuk

menyelesaikan atau

: persamaan

,

dengan

syarat

, terdapat dua subkasus selesaian yaitu:

c.1.1. Selesaian untuk persamaan atau

dengan

, dengan syarat . Karena

subkasus pertama

mempunyai selesaian yang merupakan irisan dari , untuk setiap

dengan

yaitu daerah yang dibatasi oleh

. c.1.2. Selesaian untuk persamaaan

pada subkasus kedua mem-

punyai selesaian dengan

.

Selanjutnya, bila persamaan (4) yaitu; samaan (1) yaitu;

(4) disubstitusikan ke dalam per-

akan diperoleh:

Ruas kiri: Diperhatikan persamaan (1) ruas kiri yaitu;

yaitu;

dan persamaan (4)

. Jika (4) disubstitusi ke dalam (1) maka diperoleh : =

=


dan persamaan (4)

. Jika (4) disubstitusi ke dalam (1), maka diperoleh :


34

=

=

(1) diketahui bahwa

=

, karena dalam

. Maka diperoleh selesaian ruas kiri dan ruas kanan

tidak sama. Sedemikian sehingga (1), dengan dalam kasus ini adalah

dan

atau

mempunyai

.

c.2. Kasus kedua persamaan Untuk menyelesaikan persamaan atau

, dengan syarat

ditinjau dua subkasus yaitu:

c.2.1. Subkasus pertama adalah selesaian untuk persamaaan syarat

atau

dengan

, maka selesaian dari persamaan sub-

kasus pertama adalah irisan antara

dengan

yaitu

c.2.2. Subkasus kedua adalah selesaian untuk persamaaan

karena

.

diketahui bahwa

, maka subkasus kedua menjadi penyataan

yang tidak benar. Berdasarkan kedua subkasus di atas, selesaian persamaan (1) dengan syarat dan

adalah irisan

atau

dari

dan

yaitu

.

Sedangkan untuk pembuktian dengan

dan

pada persamaan (1)

akan memberikan selesaian unik yaitu , dengan langkah – langkah yang sama dengan syarat

dan

. d. Jika

, maka selesaian persamaan (1) adalah . Untuk memperoleh selesaian persamaan (1) yaitu; ditinjau dalam dua kasus:

d.1. Kasus pertama persamaan

;

Untuk menyelesaikan persamaan atau

, dengan syarat

, terdapat dua subkasus penyelesian yaitu:

d.1.1. Selesaian untuk persamaan atau

dengan

, dengan syarat . Karena

subkasus pertama ti-

dak mempunyai selesaian.


35

d.1.2. Selesaian untuk persamaaan atau

dengan syarat

pada subkasus kedua adalah irisan antara yaitu

dengan

. Dengan demikian pada kasus

pertama mempunyai selesaian

.

d.2. Kasus kedua persamaan

.

Untuk menyelesaian persamaan atau

, dengan syarat

, ditinjau dalam dua subkasus yaitu:

d.2.1. Subkasus pertama, selesaian untuk

maka

d.2.2. Subkasus kedua, selesaian untuk Diketahui bahwa

dengan syarat

dengan

untuk setiap

. disubtitusikan ke dalam persamaan

Selanjutnya, bila persamaan (1) yaitu:

.

, maka subkasus kedua selesian persamaan

tersebut adalah irisan antara adalah

(5)

maka diperoleh:

Ruas kiri : Diperhatikan persamaan (1) ruas kiri yaitu;

yaitu;

dan persamaan (5)

Jika (5) disubstitusi ke dalam (1) diperoleh: =

=

.


dan persamaan (5)

Jika (5) disubstitusi ke dalam (1) diperoleh : =

dikarenakan

=

, hal ini

untuk setiap

Dengan demikian diperoleh selesaian ruas kiri dan ruas kanan tidak sama. Karena

dan

lah

maka selesaian persamaan (1) dalam kasus kedua ada-

atau

Sedangkan untuk

. dan

pada persamaan (1) mempunyai selesaian

, dengan langkah – langkah yang

sama dengan syarat

dan

.


36

Contoh 3.3.3.3 Tentukan nilai x yang memenuhi persamaan: a. Persamaan afin aljabar Max-plus di atas memenuhi Teorema 3.3.3.2 bagian , maka selesaiannya adalah

.

b. Persamaan afin aljabar Max-plus di atas memenuhi Teorema 3.3.3.2 bagian , maka selesaiannya adalah

.

Contoh 3.3.3.4 Tabel 6. Perbandingan persamaan linier pada aljabar klasik dan persamaan afin aljabar Max-plus No


Operasi pada aljabar Max-plus

1.

Tentukan nilai yang memenuhi Tentukan nilai x yang memenuhi perpersamaaa linier berikut: samaan: a. Penyelesaian: a. Penyelesaian: Persamaan afin aljabar Max-plus di atas memenuhi teorema 3.3.3.2 bagian

, maka .

Nilai dari persamaan adalah 2.

Jadi

nilai yang memenuhi persamaan adalah

.


37

b. Penyelesaian:

b. Penyelesaian: Persamaan afin aljabar Max-plus diatas memenuhi teorema 3.3.3.2 bagian

, maka

Jadi selesaiannya adalah Nilai dari persamaan adalah .

3.4

.

Sistem Persamaan Linier Pada subbab ini dibahas tentang sistem persamaan linier dalam aljabar klasik [1]

dan aljabar Max-plus [2, 5, 6, 10, 12]. 3.4.1 Sistem Persamaan Linier [SPL] Aljabar Klasik Sistem persamaan linier dalam aljabar klasik dua peubah (variabel) secara umum dituliskan sebagai berikut:

Kedua sistem persamaan linier di atas dapat diilustrasikan dalam grafik kartesius yang berbentuk garis; sebut

. Selesaian sistem persamaan linier ada tiga, yang

berpadanan dengan titik – titik potong 1. Jika garis

.

berpotongan di satu titik

maka sistem

persamaan linier mempunyai selesaian tunggal. 2. Jika garis

berhimpit dibanyak titik

maka sistem

peramaan linier mempunyai selesaian banyak. 3. Jika garis

saling sejajar

maka sistem persamaan linier

tidak mempunyai selesaian.


38

Contoh 3.4.1.1 Tentukan nilai

yang memenuhi SPL berikut:

a. Penyelesaian: Dengan mensubtitusikan (2) ke dalam (1) diperoleh

Pada grafik

kartesius kedua garis berpotongan pada titik y 3x + 2y = 9 9/2 4 3 x+y=4 1

x

3 4

Gambar 23. Grafik SPL

dan

3.4.2 Sistem Persamaan Linier aljabar Max-plus Bentuk

=

Sistem persamaan linier aljabar Max-plus secara umum berbentuk

=

. Di samping bentuk umum, ada dua bentuk khusus sistem persamaan linier aljabar Max-plus yang dibahas yaitu maan linier aljabar Max-plus berukuran

dan

dan =

. Sistem persa-

, dengan

adalah sebuah matriks berukuran

dan

adalah matriks . Dalam mencari

selesaiannya sistem persamaan linier aljabar Max-plus bentuk umum diubah ke dalam bentuk kanonik. Definisi 3.4.2.1 Sistem persamaan linier aljabar Max-plus bentuk kanonik jika 1. Jika

=

dikatakan ber-

memenuhi: maka

dan jika

maka

.


39

2. Jika

maka

dan jika

maka

Bentuk umum sistem persamaan linier aljabar Max- plus

=

untuk

menentukan selesaiannya diubah ke dalam bentuk kanonik dengan cara mengubah:  Jika  Jika

maka

dan jika

maka

maka

dan jika

maka

Selanjutnya, sistem persamaan linier aljabar Max- plus

=

yang

telah diubah kedalam bentuk kanonik dapat diselesaikan dengan cara seperti menyelesaikan sistem persamaan linier dalam aljabar klasik. Selesaian dalam sistem persamaan linier aljabar Max- plus

=

mempunyai tiga kemungkinan:

1. Tidak terdapat selesaian. 2. Mempunyai selesaian yang tunggal. 3. Mempunyai selesaian yang banyak. Akan tetapi sistem persamaan linier aljabar Max- plus

=

, belum

dapat ditentukan jenis selesaianya. Contoh 3.4.2.2 Selesaikan sistem persamaan linier aljabar Max- plus berikut : =

(1)

Sistem persamaan di atas diubah menjadi bentuk kanonik yaitu:

Dengan demikian diperoleh dua persamaan afin yaitu: a).

3

b).

1

Dengan mensubtitusikan persamaan afin (a) ke dalam persamaan afin (b) diperoleh persamaan afin yang baru yaitu:

3=

1. Berdasarkan Teorema


40

3.3.3.2 (b), persamaan afin

3=

1 tidak menpunyai selesaian, karena

tidak memenuhi salah satu dari persamaan afin yang mempunyai selesaian. Dengan demikian sistem persamaan (1) tidak mempunyai selesaian. Contoh 3.4.2.3 Selesaikan sistem persamaan linier aljabar Max- plus berikut; =

(2)

Sistem persamaan di atas diubah menjadi bentuk kanonik yaitu:

Dengan demikian diperoleh dua persamaan afin yaitu: a). b).

3

Dengan mensubtitusikan persamaan afin (b) ke dalam persamaan afin (a) diperoleh persamaan afin yang baru yaitu:

3=

(a) maka selesaian persamaan afin

3=

yaitu:

. Berdasarkan Teorema 3.3.3.2 adalah

= -2. Selanjutnya hasil selesaian dari

disubtitusikan ke (b) diperoleh

. Sedemikian sehingga selesaian sistem persa-

maan linier aljabar Max-plus (2) adalah

.

Contoh 3.4.2.4 Tentukan selesaian dari sistem persamaan linier aljabar Max- plus berikut adalah =

(3)

Sistem persamaan linier di atas diubah menjadi bentuk kanonik yaitu:


41

Dengan demikian diperoleh dua persamaan afin yaitu: a).

4

b). Dengan mensubtitusikan persamaan afin (a) ke dalam persamaan afin (b) diperoleh persamaan afin yang baru yaitu:

=

(c) maka selesaian persamaan afin

=

yaitu:

4. Berdasarkan Teorema 3.3.3.2 4 adalah

. Selanjutnya hasil selesaian dari

tusikan ke (b) diperoleh

disubti-

. Sedemikan sehingga selesaian sistem persamaan linier

aljabar Max-plus (3) adalah

.

3.4.3 Sistem Persamaan Linier aljabar Max-plus Bentuk Untuk mencari selesaian sistem persamaan linier aljabar Max-plus bentuk . Pandang bahwa

adalah matriks persegi yang berukuran

adalah matriks kolom yang berukuran

dan

. Selesaian di atas erat kaitanya dengan ben-

tuk graf dari suatu matriks. Bentuk graf dimaksud adalah graf preseden yang didefinisikan sebagai berikut: Definisi 3.4.3.1. Diberikan

. Graf preseden matriks

dengan

adalah graf berarah berbobot

dan

.

Contoh 3.4.3.2 Diberikan bot

, graf preseden dari matriks dengan

adalah graf berarah berbo-

dan

Bila disajikan dalam gambar adalah sebagai berikut:


42

3

1 1

2

-4

2 1 1 3 2

Gambar 24. Graf

Teorema 3.4.3.3 [2, 5, 12] Diberikan

. Jika hanya ada sirkuit dengan bobot nonpositif di

,

maka selesaian untuk sistem persamaan linier Aljabar Max-plus bentuk adalah

, dengan

Lebih lanjut jika semua sirkuit

.

berbobot negatif, maka selesaian sistem persa-

maan linier aljabar Max-plus bentuk

adalah tunggal.

Bukti: Eksistensi dari a. Keberadaan dari

.

1. Elemen- elemen dengan panjang

adalah merupakan bobot maksimum dari semua lintasan yang menghubungkan simpul ke simpul .

2.

, maka

adalah bobot mak-

simum dari semua lintasan yang mungkin, yang menghubungkan simpul

ke

simpul . 3.

ada jika dan hanya jika tidak ada komponen yang terhubung secara kuat di

yang mempunyai sirkuit dengan bobot positif.

Bukti: () Andaikan ada komponen yang terhubung kuat di

yang mempunyai sir-

kuit dengan bobot positif. Misalkan:

Sirkuit

mempunyai

mempunyai bobot minimal bot

.

mempunyai bobot minimal

ada, karena komponen

bobot

artinya

mempunyai minimal boAkibatnya

makin besar ketika

tidak

Hal ini kontra-


43

diksi dengan

ada. Jadi pengandaian salah, haruslah tidak ada komponen

yang terhubung kuat di

() Andaikan

yang mempunyai sirkuit dengan bobot positif.

tak ada. Maka

tidak mempunyai lintasan yang berbo-

bot maksimum. Maka bobot lintasan dari simpul

ke simpul

semakin besar

dengan semakin panjangnya lintasan. Sedemikan hingga, karena bobot lintasan semakin besar maka bobot sirkuit

atau

juga semakin besar. Jadi

ada sirkuit dengan bobot positif, maka kontradiksi. Sehingga pengadaian salah, ada. Berdasarkan Teorema 3.4.3.3, maka syarat perlu dan sya-

haruslah

rat cukup, keberadaan

terpenuhi. Selanjutnya akan ditunjukan bahwa

adalah selesaian dari

. =

= = = = = = b. Ketunggalan selesaian dari Untuk Menunjukan ketunggalan selesaian dari persamaan salkan

adalah selesaian

Subtitusikan

Mikedalam

yaitu: =

(bila dilakukan subtitusi nilai

secara terus

menerus, akan diperoleh);

=

(

(b.1)


44

Elemen- elemen Untuk

adalah bobot maksimum dari lintasan dengan panjang

.

cukup besar, setiap lintasan mengandung satu atau lebih sirkuit elementer se-

bagai sublintasan. Jika rena sirkuit di

banyaknya sirkuit elemeter yang terjadi menuju

mempunyai bobot negatif, maka elemen-elemen

Kauntuk

, yaitu:

Jadi, untuk (

persamaan (b.1) menjadi = =(

dengan demikian :

=

=

)

= =

(terbukti)

Contoh 3.4.3.4 Tentukan penyelesain dari sistem persamaan linier aljabar max-plus

Penyelesaian: )

. Jadi selesaian

adalah

Teorema 3.4.3.5 [2, 10, 12] Diberikan tif, maka

. Jika semua sirkuit dalam

mempunyai bobot nonposi-

.

Bukti:


45

Karena matriks

berdimensi

maka banyak simpul dari graf

. Sehingga semua lintasan dengan panjang lah panjang semua sirkuit kurang dari dari

. Sehingga untuk setiap

tersusun dari

adalah

sirkuit dengan jum-

dan ada suatu lintasan dengan panjang kurang dan untuk setiap

terdapat

sehingga: =

+

dengan

,

dan

Karena semua sirkuit mempunyai bobot nonpositif, maka untuk setiap

dan untuk

setiap

,

berlaku

dengan

Akibatnya

.

,

.

,

.

Dengan demikian 3.4.4 Sistem Persamaan Linier Aljabar Max-plus Bentuk Sistem persamaan linier aljabar Max-plus

, tidak selalu mempunyai

selesaian. Sehingga untuk menentukan selesaian

dapat diperlemah dengan

mendefinisikan beberapa konsep subselesaiannya. Definisi 3.4.4.1 Diberikan dan

merupakan himpunan

yang didefinisikan sama seperti pada

bersama operasi , serta didefinisikan

.

Definisi 3.4.4.2 Subselesaian sistem persamaan linier aljabar Max-plus . Subselesaian selalu ada, yaitu

memenuhi

adalah ,

jika

= 1, 2, 3,…n.

Teorema 3.4.4.3 Subselesaian terbesar dari sistem persamaan linier aljabar Max-plus dengan

adalah matriks

triks di

adalah

dan

adalah matriks

,

dengan elemen- elemen ma-

. Bila dalam aljabar klasik dapat ditulis menjadi untuk setiap

= 1, 2, …, n.

Bukti :


46

Pandang bahwa:

dan

}

dan

}

dan ,

}

dan

}

),

dan ),

}

dan

}

Jadi subselesaian terbesar dari sistem persamaan linier aljabar Max-plus adalah setiap vektor ,

yang komponen- komponennya memenuhi

. Jika vektor

didefinisikan dengan

. Maka akan diperoleh: {

), ),

dan

dan

} }

dan

Jadi vektor

}

tersebut merupakan subselesaian sistem persamaan linier

Karena

Maka

lam menentukan subselesaian

akibatnya

. Da-

, mula – mula dilakukan dengan menghitung

, yang ditunjukkan sebagai berikut:


47

Contoh 3.4.4.4 Tentukan selesaian sistem persamaan linier aljabar Max-plus berikut dengan terlebih dulu menentukan subselesaian terbesarnya. =

Mula-mula dihitung : =

. Dengan demikian subselesaian terbesar dari sistem persamaan linier terse-

but adalah

. Untuk melihat kesahihan selesaian tersebut, disubtitusikan =

pada

yaitu:

=

Akan memberikan hasil

. Maka

merupakan selesaian dari

sistem persamaan linier Aljabar Max-plus di atas. Contoh 3.4.4.5 Tentukan selesaian sistem persamaan linier aljabar Max-plus berikut dengan terlebih dulu menentukan subselesaian terbesarnya. =

Mula-mula di hitung :

=

=

subselesaian terbesar dari sistem persamaan linier tersebut adalah kesahihan selesaian tersebut, disubtitusikan

pada

. Dengan demikian . Untuk melihat =

yaitu:


48

Akan memberikan hasil

=

. Maka

bukan merupakan

selesaian dari sistem persamaan linier aljabar Max-plus di atas tetapi merupakan subselesaian. Contoh 3.4.4.6 Tabel 7. Perbandingan sistem persamaan linier pada aljabar klasik dan aljabar Max-plus

No Operasi pada aljabar klasik 1.

Tentukan nilai

Operasi pada Aljabar Max-plus

yang memenuhi Tentukan nilai

sistem persamaaa linier berikut:

yang memenuhi

sistem persamaan linier berikut: = (1)

Penyelesaian: Dengan mensubtitusikan (1) ke (2) diperoleh 0 = 0. Maka SPL tersebut mempunyai

selesaian banyak , hal ini

karena kartesius

. kedua

Dalam

garis

Penyelesaian: SPL di atas diubah menjadi bentuk kanonik yaitu: =

grafik

mempunyai

kemiringan yang sama dan berhimpit Dengan demikian diperoleh dua persadisemua titik sebagai berikut: maan afin yaitu: y

=

a).

=

b). 2x + 4y =10

3 1

Dengan mensubtitusikan persamaan afin

6x +12y =30

x

(a) kedalam persamaan afin (b) diperoleh persamaan afin yang baru yaitu: 3=

Teorema 3.3.3.2 persamaan afin

Gambar 25. Grafik SPL dan

2.

Tentukan nilai

1. Berdasarkan

3= yang memenuhi

sistem persamaan linier berikut:

1 tidak mempunyai se-

lesaian, karena diperoleh persamaa afin dengan

dan

dan


49

dan

yang tidak memenuhi salah

satu dari persamaan afin yang mempunyai selesaian. Sehingga sistem persa-

Penyelesaian: Bentuk sistem persamaan linier di atas tidak mempunyai

maan (1) tidak mempunyai selesaian.

selesaian, karena

. Dalam grafik kartesius kedua garis

tersebut

mempunyai

kemiringan yang sama dan saling sejajar sebagai berikut: y

6 4

x +y = 6 x+y =4

0

4

6

x

Gambar 26. Grafik SPL dan

Diperhatikan dari Tabel 7, penyelesaian sistem persamaan linier pada aljabar klasik dua variabel diperoleh dengan menentukan titik potong

kedua garis dari

persamaan pada grafik kartesius . Akan tetepi hal ini akan lebih sulit dilakukan untuk yang lebih dari dua variabel, sehingga untuk yang lebih dari dua varibel dapat dilakukan dengan eleminasi atau subtitusi. Pada sistem persamaan linier aljabar Max-plus penyelesaiannya dilakukan dengan mengubah kedalam bentuk kanonik, sehingga diperoleh persamaan afin. Penyelesaian persamaan afin aljabar Max-plus dapat dilakukan dengan menentukan titik potong kedua ruas persamaan afin.


BAB IV PENUTUP

4.1

Kesimpulan Diberikan himpunan bilangan real

, dinotasikan sebagai

dilengkapi dengan dua operasi biner , maka

, yang

. Jika diberikan sembarang bilangan

didefinisikan sebagai nilai maksimum dari salah satu dari

bilangan tersebut, dan Sistem matematika

didefinisikan sebagai jumlah dari kedua bilangan tersebut. disebut aljabar Max-plus dan dinotasikan dengan

Aljabar Max-plus merupakan salah satu struktur aljabar yang semilapangan komutatif idempoten dengan elemen identitas pada operasi penjumlahan dan pada operasi perkalian

(elemen satu) adalah

Himpunan matriks persegi berukuran dinotasikan sebagai biner

pada

moduloid atas

(elemen nol) adalah .

dengan elemen-elemen di

Matriks dalam aljabar Max-plus yang dilengkapi operasi dan satu operasi

dari

pada

, maka

. Moduloid yang ditambah satu operasi biner

merupakan dari

pada

membentuk aljabar idempoten. Pengoperasian matriks dalam aljabar Max-plus sama dengan pengoperasian matriks di aljabar klasik, yaitu banyaknya baris dari matriks yang dikali sama dengan banyaknya kolom dari matriks pengalinya. Fungsi linier dalam aljabar Max-plus mempunyai kemiringan 1. Sistem persamaan linier aljabar Max-plus secara umum berbentuk , untuk menentukan selesaianya diubah ke dalam bentuk kanonik. Untuk menentukan selesaian sistem persamaan linier bentuk pendekatan graf presenden dan bentuk

adalah dengan dengan memperlemah dengan

subselesaian (subsolusi). 4.2

Saran Penelitian ini dapat dilanjutkan dengan mencari polinomial karakteristik, nilai

eigen dan vektor eigen dalam aljabar Max-plus .

50



DAFTAR PUSTAKA 1.

Anton, H, “ Elementary Linear Algebra”, Wiley &Sons, Inc, New York, 2005.

2.

Baccelli, F, Cohen, G, Olsder, G.J. dan Quadrat, J.P, “Synchronization and Linearity”, Wiley, New York, 1992.

3.

Heidergott, B., “Max-plus Algebra and Queues”, Departement of Economics and Operations Research De boelelan 1105,1081 HV Amsterdam. The Netherlands, 2008.

4.

Hungerford, T.W, “Algebra Graduate Texts In Mathematics”, Springer, seattle, Washington, 1980.

5.

Kasie G.F, “Max-Plus Algebra”, Master’s Thesis submitted to the faculty of be Virginia Polytechnic Institute and State University, 2009

6.

Nasution, A.D.J, “Aljabar Max- Plus”, Skripsi, Fakultas MIPA Jurusan Matematika, Universitas Indonesia, Depok, 2004.

7.

Olsder.G.J dan Roos.C, “Cramer and Caylay-Hamilton in the Max-Algebra”, Delft University of Technology, Departemen of mathematics and informatics, Netherlands, 1987.

8.

Olsder.G.J dan Roos.C, “On the Characteristic equation and Minimal Realizations For Distcrete-event Dynamic Systems”, Delft University of Technology, Departemen of mathematics and informatics, Netherlands, 1990.

9.

Rudhito A.M., Wahyuni, S., Suparwanto, A. dan Susilo, F., “Sistem Persamaan Linier iterative Max-plus Interval”, Prosiding Seminar Nasional Penelitian, Pendidikan dan penerapan MIPA ,pp.263-272, UNY Mei 2008.

10.

Rudhito, A. M , “ Sistem Linier max-plus waktu –invariant”, Tesis, Universitas Gajah Mada, 2003.

11.

Schutter, B., “On the ultimate behavior of the sequence of consecutive powers of a matrix in the max-plus algebra,” Linear Algebra and Its Applications, vol. 307, no. 1–3, pp. 103–117, March 2000.

12.

Subiono, “Aljabar Maxplus dan Terapannya”, Diktat Mata kuliah, FMIPA-ITS, Surabaya, 2010

51



UNIVERSITAS INDONESIA PERBANDINGAN SISTEM PERSAMAAN LINIER DALAM ALJABAR KLASIK DAN ALJABAR MAX-PLUS TESIS MULYADI NPM

Recommend Documents