BAB II KAJIAN PUSTAKA
Pada bab ini akan diuraikan mengenai matriks (meliputi definisi matriks, operasi matriks, determinan dan invers matriks), aljabar max-plus, matriks atas aljabar max-plus, dan penyelesaian sistem persamaan linear max-plus
.
A. Matriks 1. Definisi Matriks Definisi 2.1. (Anton, 1987: 22) Sebuah matriks adalah susunan segi empat siku-siku dari bilangan-bilangan. Bilangan-bilangan dalam susunan matriks dinamakan entri. Matriks terdiri dari entri-entri yang disusun menurut baris dan kolom sehingga berbentuk persegi panjang dengan panjang dan lebar menunjukkan banyak baris dan banyak kolom. Matriks yang memiliki
baris dan
kolom disebut matriks berukuran
.
Bentuk umum dari matriks adalah sebagai berikut:
[
] atau [
]
Entri yang menempati baris ke- dan kolom ke- disebut entri sebagai dan
[
] dengan
kolom ditulis 1
dan ditulis
sebagai skalar. Matriks yang terdiri dari 1 baris
disebut dengan matriks baris dan yang terdiri atas
baris dan 1 kolom disebut matriks kolom.
4
Sebuah matriks dengan (persegi) berorde
baris dan
dan entri-entri
kolom dinamakan matriks kuadrat ,…,
,
diagonal utama dari . Sehingga bentuk matriks
dikatakan berada pada
dituliskan berikut
[
]
2. Operasi Matriks a. Penjumlahan matriks Definisi 2.2. (Anton, 1987: 23) Jika
dan
jumlah
adalah sebarang dua matriks yang ukurannya sama, maka
adalah matriks yang diperoleh dengan menambahkan bersama-
sama entri yang bersesuaian dalam matriks
dan
, jika ukuran matriksnya
berbeda maka tidak dapat ditambahkan.
Contoh 2.1: Diberikan matriks [
]
didapat
[
sedangkan
dan
[
]
*
+
] tidak didefinisikan.
5
b. Perkalian matriks Definisi 2.3. (Anton, 1987: 25) Jika
adalah matriks
dan
adalah matriks
, maka hasil kali
yang entri-entrinya ditentukan sebagai berikut,
untuk mencari entri dalam baris matriks
adalah matriks
dan kolom
dari
, pilihlah baris
dari
dan kolom dari matriks , kalikanlah entri-entri yang bersesuaian
dari baris dan kolom tersebut bersama-sama dan kemudian tambahkanlah hasil kali yang dihasilkan. Perkalian
dan
terdefinisi jika dan hanya jika banyak kolom matriks
sama dengan banyak baris matriks .
Contoh 2.2: *
Matriks
+ dan
*
+
dengan mengalikannya akan menghasilkan *
+*
*
+
*
+*
*
+
+
+
Jadi
6
c. Transpos matriks Definisi 2.4. (Anton, 1987: 27) Jika
adalah sebarang matriks
, maka transpos
dan didefinisikan dengan matriks baris pertama dari
dinyatakan oleh
yang kolom pertamanya adalah
, kolom keduanya adalah baris kedua dari
, demikian
juga dengan kolom ketiga adalah baris ketiga dari , dan seterusnya.
[
Matriks
]
transpos matriks
[
adalah
]
3. Determinan Misalkan
matriks persegi, fungsi determinan
determinan yang dinotasikan dengan
sering ditulis sebagai
atau | |. Fungsi determinan adalah
suatu fungsi yang mengasosiasikan matriks dengan bilangan real. Misal diberikan matriks
*
+ maka
–
. Determinan matriks berupa skalar
yang hanya terdefinisi untuk matriks bujur sangkar.
Berikut diberikan definisi determinan secara umum. Definisi 2.5. Diberikan matriks
[
] berukuran
dan determinan dari
dinyatakan dengan skalar yaitu sebagai berikut:
7
∑
penjumlahan dilakukan sampai Setiap dari
permutasi
dari
.
memuat tepat satu entri dari setiap baris dan setiap kolom . Jika
dikatakan permutasi genap yaitu jumlah inversi
seluruhnya adalah sebuah bilangan bulat yang genap dan
dikatakan
permutasi ganjil yaitu jumlah inversi seluruhnya adalah sebuah bilangan bulat yang ganjil.
Sebelumnya perlu diketahui definisi dari permutasi berikut Definisi 2.6. (Anton, 1987: 59) Permutasi himpunan bilangan-bilangan bulat
adalah susunan
bilangan-bilangan bulat menurut suatu aturan tanpa menghilangkan atau mengulangi bilangan-bilangan tersebut.
Umumnya, himpunan
akan mempunyai
permutasi yang berbeda. Untuk menyatakan permutasi umum dari himpunan
, maka dapat ditulis
pertama dalam permutasi,
,
adalah bilangan bulat
adalah bilangan bulat kedua dan seterusnya. Sebuah
invers (inversi) dikatakan terjadi dalam permutasi
jika sebuah
bilangan bulat yang lebih besar mendahului sebuah bilangan bulat yang lebih kecil. Jumlah invers seluruhnya yang terjadi dalam permutasi dapat diperoleh sebagai berikut:
8
1. Carilah banyaknya bilangan bulat yang lebih kecil dari membawa
dan yang
dalam permutasi tersebut
2. Carilah banyaknya bilangan bulat yang lebih kecil dari membawa
dan yang
dalam permutasi tersebut
3. Teruskan proses perhitungan ini untuk
.
Jumlah bilangan-bilangan ini akan sama dengan jumlah invers seluruhnya dalam permutasi tersebut.
Diberikan matriks
berukuran [
Karena
dan
permutasi dari
]
, berarti ada 6 permutasi dari (1,2,3) dengan daftar hasil ditunjukkan pada Tabel 1. berikut:
Tabel 1. Daftar Hasil Permutasi Permutasi
dari
Banyaknya Klasifikasi invers
(1,2,3)
0
genap
+
(1,3,2)
1
ganjil
-
(2,1,3)
1
ganjil
-
(2,3,1)
2
genap
+
(3,1,2)
2
genap
+
(3,2,1)
3
ganjil
-
9
Sehingga didapat ∑
Contoh 2.3: Diberikan matriks
[
]
Akan dicari ∑
Untuk matriks
berukuran
dikatakan singular, sehingga matriks dikatakan nonsingular, jika det sehingga matriks
dengan det
maka matriks
tidak memiliki invers. Sedangkan matriks maka matriks
memiliki invers,
invertible.
10
Berikut ciri-ciri matriks yang determinannya adalah , yaitu 1. Matriks 0 2. Baris 0 atau kolom 0 3. Matriks simetri 4. Baris merupakan kelipatan baris yang lain atau kolom merupakan kelipatan kolom yang lain
4. Invers Matriks Definisi 2.7. (Anton, 1987: 34) Jika
adalah matriks persegi,
dinamakan invers dari Karena
dikatakan invertible maka ada matriks
sehingga memenuhi
adalah invers dari
maka
dan
.
. Jadi
Contoh 2.4: *
Matriks
+ adalah invers dari matriks
* *
+* +*
+
*
+
+
*
+
*
+
Jadi
Suatu matriks
memiliki invers atau tidak memiliki invers dapat diketahui
dengan menunjukkan determinan dari matriks
bukan nol. Syarat matriks
memiliki invers ditunjukkan pada teorema berikut:
11
Teorema 2.1. (Anton, 1987: 74) Matriks
dapat dibalik jika dan hanya jika
.
Bukti: Jika
dapat dibalik maka . Jadi
sehingga .
Ketunggalan invers matriks ditunjukkan pada contoh berikut: Contoh 2.5: Diberikan matriks , dengan
dan
.
Akan ditunjukkan
Karena
, maka invers matriks tunggal.
Sifat-sifat dari invers matriks diberikan pada teorema berikut: Teorema 2.2. Untuk matriks
dan
berukuran
invertible maka diperoleh:
(1) (2) (3)
12
Bukti: (1) Dari definisi,
adalah invers dari
Akibatnya
sehingga
adalah invers dari
Karena
sehingga
maka
(2) Anggap
. . .
dan menunjukkan bahwa
. Diperoleh
. Jadi (3) Anggap
dan menunjukkan bahwa
. Dengan membentuk
. Oleh karena itu, .
B. Aljabar Max-Plus Definisi 2.8. Baccelli (2001: 102) Aljabar max-plus adalah himpunan operasi biner yaitu
dan
, operasi maksimum dinotasikan dengan
operasi penjumlahan dinotasikan dengan dinotasikan dengan didefinisikan dua operasi
∪ {-∞} yang dilengkapi dengan dua
. Selanjutnya (
∪ {-∞},
dan ,
)
dan {-∞} dinotasikan dengan ε. Untuk dan
, yaitu:
13
Contoh 2.6: Diberikan
Dalam aljabar max-plus,
merupakan elemen identitas terhadap operasi
,
sehingga , Elemen
.
merupakan elemen netral terhadap operasi , untuk
Jadi operasi
dan
adalah semiring, yaitu:
) merupakan semigrup komutatif dengan elemen netral {-∞}.
2. ( ∪ {-∞}, 3. Operasi
.
bersifat komutatif.
Struktur aljabar dari 1. ( ∪ {-∞},
, maka
) merupakan grup komutatif dengan elemen identitas 0.
dan
bersifat distributif.
4. Elemen netral bersifat menyerap terhadap operasi ,
a=a
, yaitu
=
C. Matriks atas Aljabar Max-Plus Himpunan matriks dengan
untuk
menunjukkan baris dan
aljabar linear, matriks
atas
dinotasikan
menunjukkan kolom. Sebagaimana dalam
dapat ditulis sebagai berikut:
14
(
, atau [
Entri baris ke- dan kolom ke- matriks
]
dinotasikan dengan
atau
. Penjumlahan dan perkalian pada matriks atas aljabar max-plus didefinisikan dengan cara mengganti operasi operasi
menjadi
Operasi
dan
menjadi
(maksimum) dan
(penjumlahan).
atas
dapat diperluas untuk operasi-operasi matriks pada
seperti pada kedua definisi berikut: Definisi 2.9. (Rudhito, 2004: 4) Diberikan
untuk
dan
} 1) Diketahui
. Didefinisikan
adalah matriks yang
unsur ke- -nya: untuk 2) Diketahui
,
dan . Didefinisikan
adalah matriks yang
unsur ke- -nya: untuk
dan
adalah matriks yang unsur ke- -nya: untuk
dan
15
Definisi 2.10. (Farlow, 2009: 12) a) Diberikan
, penjumlahannya didefinisikan sebagai operasi
maksimum dengan notasi
b) Diberikan
, maka
dengan
dan
, perkaliannya didefinisikan sebagai
operasi penjumlahan dengan notasi
, maka
c) Transpose matriks dinotasikan dengan aljabar linear
dengan
dan didefinisikan seperti dalam
.
d) Matriks identitas dalam aljabar max-plus berukuran
yaitu
yang
didefinisikan sebagai berikut: { Matriks identitas merupakan identitas terhadap operasi semua identitas
dan
untuk semua
untuk . Matriks
digunakan jika ukuran matriksnya sudah jelas.
e) Untuk matriks persegi (bujur sangkar) dan ke- dari
.
dinotasikan dengan
bilangan bulat positif, pangkat
yang didefinisikan dengan
⏟ Untuk f) Untuk sebarang matriks
dan sebarang skalar
,
didefinisikan dengan
16
Contoh 2.7: Diberikan
(
+ dan
(
+
(
+
(
+
(
+
Contoh 2.8: Diberikan
(
) dan
(
(
)
)
(
*
(
)
)
(
*
(
)
(
(
)
( (
Jadi
(
)
), maka
)
(
)
( (
* *
17
(
*
(
)
(
)
(
)
(
*
(
*
( (
* )
Jadi
Karena
, maka operasi
bersifat komutatif. Sedangkan operasi
pada matriks atas aljabar max-plus
tidak komutatif karena
.
Sifat-sifat matriks dapat dinyatakan pada teorema berikut: Teorema 2.3. (Subiono, 2010: 14) Beberapa sifat berikut berlaku untuk sebarang matriks
dan
dengan ukuran
yang bersesuaian dan operasi matriks terdefinisi i.
(asosiatif)
ii.
(asosiatif)
iii.
(distributif)
18
iv.
(distributif)
v.
(idempoten)
Bukti : Akan dibuktikan untuk (ii) dan (iii), sedangkan bukti yang lainnya mengikuti definisi operasi dan sifat-sifat operasi pada
.
Bukti (ii) : Ambil sebarang matriks
,
, dan
Entri baris ke- kolom ke- matriks
.
adalah sebagai berikut:
untuk
dan
.
Bukti (iii) : Ambil sebarang matriks
dan
Entri baris ke- dan kolom ke- matriks
. adalah sebagai berikut:
untuk
dan
.
19
Didefinisikan matriks
dengan
untuk setiap dan .
D. Penyelesaian Sistem Persamaan Linear Max-plus Menurut Subiono (2013: 33), kekurangan dari aljabar max-plus adalah tidak memiliki invers aditif. Hal ini yang menyulitkan untuk menyelesaikan sistem persamaan linear
. Penyelesaian sistem persamaan linear
menggunakan cara menentukan subsolusi terbesar.
Terlebih dahulu didefinisikan konsep subsolusi/subpenyelesaian berikut Definisi 2.11. (Rudhito, 2005: 160) Diberikan A
. Vektor x’
dan b
disebut suatu
subpenyelesaian sistem persamaan linear memenuhi
.
Subpenyelesaian berlaku
jika vektor x tersebut
selalu ada, karena untuk
=
selalu
b.
Definisi 2.12. (Rudhito, 2005: 160) Suatu subpenyelesaian ̂ dari sistem terbesar sistem sistem
jika
disebut subpenyelesaian
̂ untuk setiap subpenyelesaian
dari
.
20
Teorema 2.3. (Baccelli, et al., 2001: 110) Diberikan sama dengan
dengan unsur-unsur setiap kolomnya tidak semuanya dan
. Subpenyelesaian terbesar
diberikan oleh ̂ dengan ̂
,
ada dan dan
.
Bukti:
{
(
(
)
(
)
(
)
Unsur setiap kolom matriks setiap
selalu ada
sehingga
berlaku
)
tidak semuanya sama dengan , maka untuk yang berarti
dan
ada. Mengingat setiap
, maka koefisien-koefisien
tidak akan berpengaruh pada nilai Sehingga berlaku: (
)
(
)
(
)
( ( Jadi, subpenyelesaian sistem
) ) adalah setiap
yang komponen-
21
. Jika ̂
komponennya memenuhi ̂
didefinisikan dengan
untuk setiap
̂ ̂
̂ , maka
diperoleh ( ̂
)
(̂
(
)
)
(̂
) (
(
̂)
)
̂ didapat ̂ yang merupakan subpenyelesaian sistem persamaan linear max-plus ̂
karena
(
)
̂
, maka
̂ sehingga ̂ merupakan subpenyelesaian terbesar sistem
̂ . Akibatnya .
Terkait hal tersebut, dapat diketahui cara untuk menyelesaikan sistem persamaan
dengan langkah pertama yaitu terlebih dahulu menghitung
subpenyelesaian terbesarnya. Kemudian periksa subpenyelesaian terbesarnya itu memenuhi sistem persamaan atau tidak. Untuk mempermudah menghitung subpenyelesaian terbesar dari sistem persamaan
dapat ditentukan
dengan
̂
[
̂ ̂
]
̂
[
]
22
[
]
[
]
̂ Jadi sistem persamaan linear max-plus
mempunyai subsolusi terbesar
̂ dengan ̂ Sehingga ̂ merupakan solusi yang memenuhi persamaan
̂
.
Contoh 2.9: Sebagai contoh akan ditentukan solusi persamaan
*
+
* +
* +
Subsolusi dari persamaan di atas adalah ̂ *
+
*
[
]
[ *
+
] +
23
Jadi subsolusinya adalah ̂
Akan ditunjukkan ̂
* +
* + adalah subsolusi terbesar yang memenuhi persamaan
tersebut. Misal ambil subsolusi ̂
* + * + * +.
Selanjutnya dapat dicek untuk ̂
* +, maka ̂
*
+
* +
[ [
] ]
* +
untuk ̂
* +, maka ̂
*
+
[ [
* + ]
]
* +
24
untuk ̂
* +, maka ̂
*
+
* +
[
]
[
]
* +
untuk ̂
* +, maka ̂
*
+
* +
[ [
] ]
* + ̂ Jadi subsolusi terbesarnya adalah ̂ = * +. Sehingga didapat
= * + yang merupakan penyelesaian dari sistem persamaan
tersebut.
25
