BAB II KAJIAN PUSTAKA
A. Aljabar Max-Plus 1. Pengertian Aljabar Max-Plus Aljabar Max-Plus adalah himpunan {} dengan himpunan semua bilangan real yang dilengkapi dengan operasi maksimum, dinotasikan dengan dan operasi penjumlahan yang dinotasikan dengan . Selanjutnya ( , , ) dinotasikan dengan max dan dinotasikan dengan ε. Elemen ε merupakan elemen netral terhadap operasi dan 0 merupakan elemen identitas terhadap operasi . Banyak peranan Aljabar Max-Plus dalam menyelesaikan persoalan di beberapa bidang seperti teori graf, kombinatorik, teori sistem, teori antrian, dan proses stokastik. Hal ini telah dibahas dalam beberapa buku dan jurnal seperti B. De Schutter, et.al (1998), Heidergott (1999), Bacelli,et.al (2001), dan Kasie G. Farlow, (2009). 2. Matriks dan Vektor pada Aljabar Max-Plus Masalah-masalah optimalisasi nonlinear dapat menjadi linear pada max , maka dalam hal ini akan dibahas mengenai matriks dan vektor pada max (Kasie G. Farlow, 2009:11).
7
8
a. Matriks Himpunan matriks n x m untuk n, m pada max dinotasikan dengan nxm max . Dalam matriks, n menunjukkan jumlah baris dan m menunjukkan jumlah kolom. Secara khusus dalam Aljabar, matriks A nxm max ditulis sebagai berikut:
a11 a21 a a22 A 21 an1 an 2
a1m a2 m anm
Matriks A untuk nilai masukkan ke-i baris dan ke-j kolom dinotasikan dengan Aij . Penjumlahan dan maksimum pada matriks dan vektor Aljabar Max-Plus didefinisikan dengan cara yang berbeda yakni maksimum dan penjumlahan . Definisi 2.1 (Kasie G. Farlow, 2009: 12) a. Untuk A, B nxn max maksimumnya didefinisikan A B dengan:
A Bij Aij Aij max( Aij , Bij ) b. Transpose dari matriks dinotasikan dengan AT dan secara khusus dalam Aljabar Max-Plus didefinisikan [ AT ]ij A ji c. Matriks identitas Aljabar Max-Plus nxn, En didefinisikan sebagai berikut: 0 jika i j
En ij
jika i j
9
d. Untuk matriks persegi dan k bilangan bulat positip, pangkat ke-k pada A dinotasikan dengan A k didefinisikan: Ak A A ...... A untuk k = 0 , A0 En sampai ke k
e. Untuk
sebarang
matriks
A nxm max
dan
sebarang
skalar
a max , a A didefinisikan sebagai berikut:
a Aij a Aij Contoh 2.1:
2 3 3 5 Diberikan A dan B , maka e 4 1 4
2 3 3 A B e 4 1 3 5 2 B A 1 4 e Jadi A B B A
5 max(2,3) 4 max(e, 1) 3 max(3, 2) 4 max(1, e)
max(3,5) 3 max(4, 4) e max(5,3) 3 max(4, 4) e
2 3 3 5 A B e 4 1 4 max(2 3,3 (1)) max(2 5,3 4) max(e 3, 4 (1)) max(e 5, 4 4) 5 7 3 8 3 5 2 3 B A 1 4 e 4 max(3 3,5 4) max(3 2,5 e) max((1) 2, 4 e) max((1) 3, 4 4) 5 9 4 8
5 4 5 4
10
Jadi A B B A
Operasi pada matriks A dan B bersifat komutatif untuk matriks karena A B B A , tetapi tidak. Matriks identitas merupakan identitas pada , A En A untuk semua A mxn max dan Em A A untuk semua A nxm max .
b. Vektor Anggota dari x nmax disebut vektor Max-Plus. Komponen ke-j dari vektor x dinotasikan dengan x j atau x j . Kolom ke-j dari matriks identitas En diketahui sebagai vektor basis ke-j pada nmax . Vektor ini dinotasikan dengan e j ( , , ,...., , , , ,... ) . Dengan kata lain, e merupakan masukkan ke-j pada vektor.
B. Matriks Atas Aljabar Max-Plus Operasi dan pada max dapat diperluas untuk operasioperasi matriks mxn max seperti dalam definisi berikut: Definisi 2.2 (Rudhito, 2004: 4) Diberikan mxn max { A ( Aij ) | Aij max untuk i 1, 2,...., m
dan j 1, 2,..., n} mxn 1. Diketahui max , A, B max . Didefinisikan A adalah matriks
yang unsur ke-ij-nya:
11
( A)ij Aij untuk i = 1,2, .. ,m dan j = 1,2, …., n dan A B
adalah matriks yang unsur ke-ij-nya: ( A B)ij Aij Bij untuk i = 1,2, .. ,m dan j = 1,2, …., n pxn 2. Diketahui A mxp max , B max . Didefinisikan A B adalah matriks yang
unsur ke-ij-nya: p
( A B)ij Aik Bkj untuk i = 1,2, .. ,m dan j = 1,2, …., n k 1
Contoh 2.2:
1 5 3 1 3 5 3 2 3 2 3 4 3 3 4 3 3 3 1 3 5 3 2 3 3 4 3 3 4 8 5 7 0 1 5 1 5 1 1 5 5 2 3 6 2 3 6 4 3 4 4 4 4 3 4 max(1,1) max(5,5) max(2,3) max( , 6) max(4, 4) max( 3, 4) 1 5 3 6 4 4
12
1 7 3 5 7 3 6 5 3 7 1 3 0 5 4 6 0 2 8 2 6 8 3 1 2 0 8 4 3 4 max( ,9,8) max(8,3,9) max( ,8,11) max( , 2,12) 9 9 11 12
Definisi 2.3 (Rudhito, 2004: 4) Matriks A, B mxn max dikatakan sama jika Aij Bij untuk setiap i dan j. Operasi dan untuk matriks tersebut memiliki sifat-sifat berikut: Teorema 2.1 (Subiono, 2010: 14) 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) (B C) (v) A A = A Bukti: Akan dibuktikan untuk (ii) dan (iii), sedangkan bukti yang lainnya mengikuti dari definisi operasi dan sifat-sifat operasi pada max. Bukti (ii), p p q m ambil sebarang matriks A nmax , B max , dan C qmax .
13
Elemen baris ke-i kolom ke-j matriks (A B) C adalah sebagai berikut: q p A B C ij Ai ,l Bl ,k Ck , j k 1 l 1 q
p
Ai ,l Bl ,k Ck , j k 1 l 1
p q Ai ,l Bl ,k Ck , j l 1 k 1
A B C i , j p untuk i n dan j m. Bukti (iii) ambil sebarang matriks A nmax dan B, C m qmax .
Elemen Baris ke-i kolom ke-j matriks A (B C) adalah sebagai berikut: A B C Ai ,k Bk , j Ck , j ij k 1 p
Ai ,k Bk , j Ai ,k Ck , j p
k 1
p p Ai ,k Bk , j Ai ,k Ck , j k 1 k 1 [( A B)]ij [( A C )]ij , untuk i n dan j m.
Didefinisikan matriks ɛ ∈ mmaxx n dengan (ɛ)ij : = ɛ untuk setiap i dan j. C. Semimodul Atas Aljabar Max-Plus Aljabar Max-Plus memiliki beberapa sifat khusus yang selanjutnya akan dibuktikan bahwa sifat-sifat tersebut terpenuhi. Perluasan operasi pada
max untuk matriks dalam mmaxx n , semimodul nmax dan relasi urutan berada di dalamnya.
14
Definisi 2.4 (Rudhito, 2004: 132) Suatu semiring (S, +, ×) adalah suatu himpunan tak kosong S disertai dengan dua operasi biner + dan ×, yang memenuhi aksioma berikut: 1. (S, +) merupakan semigrup komutatif dengan elemen netral 0, yaitu ∀ a, b, c ∈ S memenuhi a) a + b = b + a b) (a + b) + c = a + (b + c) c) a + 0 = 0 + a = a, 2. (S, ×) adalah semigrup dengan elemen satuan 1, yaitu ∀a, b, c ∈ S memenuhi a) (a × b) × c = a × (b × c) b) a × 1 = 1 × a = a, 3. Sifat penyerapan elemen netral 0 terhadap operasi ×, yaitu ∀a ∈ S memenuhi a × 0 = 0 × a = 0. 4. Operasi × distributif terhadap +, yaitu ∀a, b, c ∈ S berlaku a) (a + b) × c = (a × c) + (b × c) b) a × (b + c) = (a × b) + (a × c) Suatu semiring (S, +, ×) dikatakan komutatif jika operasi × bersifat komutatif, yaitu ∀a, b ∈ S : a × b = b × a.
15
Contoh 2.4: Diberikan
:= { } dengan
adalah himpunan semua
bilangan real dan : . didefinisikan operasi berikut: a, b ,
a b : = max{a, b} dan a b : = a + b. Misalkan 9 -3 = max{9, -3} = 9 dan -3 12 = -3 +12 = 9. Selanjutnya ditunjukkan ( , , ) merupakan semiring dengan elemen netral = -∞ dan elemen satuan e = 0, karena untuk setiap a, b, c ∈ berlaku : (i) a ⊕ b = max{a, b} = max{b, a} = b ⊕ a, (a ⊕ b) ⊕ c = max{max{a, b}, c} = max{a, b, c} = max{a, max{b,c}} = a ⊕ (b ⊕ c), a ⊕ = max{a, -∞} = max{-∞, a} = ⊕ a = a. (ii) (a ⊗ b) ⊗ c = (a + b) + c = a + (b + c) = a ⊗ (b ⊗ c), a ⊗ e = a + 0 = 0 + a = e ⊗ a = a, (iii) a ⊗ = a + (-∞) = -∞= -∞ + a = ⊗ a, (a ⊕ b) ⊗ c = max{a, b} + c = max{a + c, b + c} = (a ⊗ c)⊕(b⊗c), a ⊗ (b ⊕ c) = a + max{b, c} = max{a + b, a + c} = (a ⊗ b)⊕(a⊗b) Selanjutnya untuk lebih ringkasnya, penulisan semiring ( , , ) ditulis sebagai max . Definisi 2.5 (Rudhito, 2004: 133) Suatu semiring (S, +, ×) mempunyai sifat idempoten terhadap operasi + berlaku a + a = a, ∀a ∈ S.
16
Contoh 2.5:
max merupakan semiring komutatif yang sekaligus idempoten, sebab untuk setiap a, b ∈ berlaku a ⊗ b = a + b = b + a = b ⊗ a dan a ⊕ a = max{a, a} = a Definisi 2.6 (Rudhito, 2004: 133) 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 a-1 sehingga a × a-1= a-1 × a = 1. Struktur aljabar dari max adalah semifield (Bacelli, et.al, 1992: 102), yaitu: 1. ( , ) merupakan semigrup komutatif dengan elemen netral . 2. ( , ) merupakan grup komutatif dengan elemen identitas 0. 3. Operasi dan bersifat distributif. 4. Elemen netral bersifat menyerap terhadap operasi , yaitu a max , a a
Contoh 2.6: Semiring komutatif ( , , ) merupakan semifield karena untuk setiap a terdapat a sehingga berlaku a (a) = a + (a) = 0. Contoh berikut terlihat bahwa max merupakan semifield idempoten.
max disebut dengan Aljabar Max-Plus dan elemen-elemen max akan
17
disebut juga dengan skalar. Dalam hal urutan pengoperasian (jika tanda kurung tidak dituliskan), operasi mempunyai prioritas yang lebih tinggi dari pada operasi . Pangkat dalam Aljabar Max-Plus secara biasa diperkenalkan dengan menggunakan sifat assosiatif. Himpunan bilangan asli digabung dengan bilangan nol dinotasikan oleh dan didefinisikan untuk x max dan untuk semua n ∈ dengan n ≠ 0 xn : x x ... x n
untuk n = 0 didefenisikan xn : e( 0) . Perhatikan bahwa untuk setiap n ∈ , x n dalam aljabar biasa dibaca sebagai xn : x x ... x x x ... x nx n
n
Pangkat Aljabar Max-Plus mempunyai prioritas tertinggi dibandingkan operasi ⊕ dan ⊗ dalam hal urutan pengoperasian. Definisi 2.7 (Subiono, 2010: 15) (S,+,x) adalah semiring komutatif dengan elemen netral 0 dan 1. Semimodul M atas S adalah semigrup komutatif (M,+) bersama operasi perkalian skalar ● : S x M → M, dituliskan sebagai (α, x) → α.x yang memenuhi aksioma berikut: α,β S dan x,y M berlaku: 1. α ● ( x + y ) = α ● x + α ● y 2. ( α + β ) ● x = α ● x + β ● x 3. α ● ( β ● x ) = ( α x β ) ● x
18
4. 1 ● x = x 5. 0 ● x = 0 Suatu elemen dari suatu semimodul dinamakan vektor. Suatu 1 n1 contoh, n max adalah semimodul atas max . Dalam hal ini max cukup
ditulis nmax . Elemen ke-j dari suatu vektor x nmax dinotasikan oleh xj dan ditulis sebagai [x]j. Vektor di nmax dengan semua elemennya sama dengan e dinamakan vektor satuan dinotasikan oleh u ditulis sebagai [u]j = e untuk semua j n. Untuk setiap α max 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 nmax dan dinotasikan oleh ej. Jadi, elemen ke-j dari vektor ej
sama dengan e
sedangkan elemen lainnya sama dengan e. Berikut ini diberikan suatu relasi pada ahimpunan yang berkaitan dengan urutan dalam himpunan tersebut. Pengertian dari relasi ini dan beberapa sifat akan berguna dalam kajian Aljabar Max-Plus max . Contoh 2.7: xn Diberikan nmax := { x = [ x1, x2, …, xn]T | xi ∈ max , i = {1, 2,..,
n}. Untuk setiap x, y nmax dan untuk setiap max didefinisikan operasi dengan x y = [x1 y1, x2 y2, …, xn yn]T dan operasi perkalian skalar dengan x = x = [x1, x2, …, xn]T
19
x1 . Dengan memperhatikan Teorema 1 nmax dapat dipandang sebagai nmax
1) dan 2) terlihat bahwa (nmax , ) merupakan semigrup komutatif dengan elemen netral = [, , ..., ]T. Kemudian dengan memperhatikan Teorema 1 10), 9), dan 8), nmax merupakan semimodul atas max . Definisi 2.8 (Jek Siang, 2002: 323) Relasi pada suatu himpunan P dinamakan urutan parsial pada P jika untuk semua x, y, z P memenuhi, 1. a a, sifat refleksi 2. bila a b dan b a, maka a = b, sifat 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 dikatakan komparabel. Penulisan a b juga bisa ditulis b a. Bila a b dan a ≠ b, maka ditulis dengan a b. Apabila 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 idempotent. Contoh 2.8.1: Himpunan + adalah himpunan bilangan bulat positif. Relasi (kurang atau sama dengan) adalah sebuah parsial order pada + . Jawab : Bila (a,b) ada didalam R jika a b. Karena setiap bilangan bulat = dirinya sendiri refleksi Karena a b dan b a kecuali a = b antisimetri
20
Jika a b dan b c maka a c transitif Jadi terbukti bahwa ( +,) merupakan urutan parsial Contoh 2.8.2: Relasi R yang didefinisikan himpunan bilangan bulat positif oleh (x, y) R jika x membagi y (tanpa sisa). Akan ditunjukkan bahwa relasi R ini adalah refleksif, antisimetris, dan transitif. Karena jika x membagi habis y berarti y tidak membagi habis x kecuali x = y, R adalah sebuah relasi antisimetri Karena setiap bilangan bulat membagi habis dirinya sendiri, R merupakan suatu relasi refleksi Karena jika x membagi habis y, dan y membagi habis z, maka x membagi habis z, R adalah sebuah relasi transitif. Dengan demikian R adalah sebuah relasi pengurutan parsial. Contoh 2.8.3: didefinisikan himpunan bilangan bulat
( ,≤) merupakan poset yang terurut total Relasi kurang dari atau sama dengan pada bilangan bulat adalah urutan total karena jika x dan y bilangan bulat, maka x y atau y x. Teorema 2.2 (Subiono, 2010: 21) Jika ( , +) semigrup komutatif idempotent, maka relasi yang didefiniskan pada dengan a b a + b = b, maka relasi adalah urutan parsial pada .
21
Bukti : Diberikan sebarang elemen a , b dan c di , maka : (i) karena idempotent, maka a + a = a a a (ii) jika a b dan b a , maka a + b = b dan b + a = a dan karena komutatif, maka a + b = b + a = a , jadi a = b, (iii) jika a b dan b c, maka a + b = b dan b + c = c dan karena mempunyai sifat assosiatif, maka a + b = a + ( b + c ) = ( a + b ) + c = b + c = c, jadi a c. Akibat 2.1 (Subiono, 2010: 21) Relasi
“ m ”
yang
didefinisikan
pada
max
dengan
a b a b b merupakan urutan parsial pada max . Relasi ini merupakan urutan total pada max . Bukti : Karena ( , ) merupakan semigrup idempotent, maka menurut Teorema 2 relasi “ m ” yang didefinisikan pada max di atas merupakan urutan parsial
pada
max .
Jika
diambil
a, b max ,
maka
berlaku
mxn max
dengan
a b max(a, b) a atau a b max(a, b) a
Akibat 2.2 (Subiono, 2010: 22) : Relasi
“ m ”
yang
didefinisikan
pada
A m B A B B Aij Bij Aij m Bij untuk setiap i dan j merupakan urutan parsial pada mxn max .
22
Bukti: Dengan menggunakan Teorema 2 (i) dan (ii) dan (iii) terlihat bahwa (mxn max , ) merupakan semigrup komutatif idempotent. Sehingga menurut
Teorema 2 relasi “ m ” yang didefinisikan pada mxn max di atas merupakan urutan parsial. Akibat 2.3 (Subiono, 2010: 21): Relasi
“ m ”
yang
didefinisikan
pada
nmax
dengan
x m y x y y xi m yi untuk setiap i dan j merupakan urutan
parsial pada nmax . Bukti: (nmax , ) merupakan semigrup komutatif idempotent, maka relasi “ m ”
yang didefinisikan pada nmax merupakan urutan parsial pada nmax . Relasi “ m ” yang didefinisikan pada mxn max diatas bukan merupakan urutan total, karena untuk dua matriks A dan B masing-masing berukuran 2 x 2 sebagai mana berikut ini:
0 1 2 1 2 1 A dan B dengan A B . 1 2 1 0 1 2 Sehingga A B B dan A B A . Demikian juga relasi “ m ” yang didefinisikan pada nmax diatas bukan merupakan urutan total, karena terdapat vektor A 1, 2,3 dan B 2, 0, 1 dengan A B 1, 2,3 T
T
T
23
2,0, 1 2, 2,3 maka A B B dan A B A . T
T
Teorema 2.3 (Subiono, 2010: 23): n n Diberikan matriks A mmax . Bila vektor x, y mmax dengan x
m y, maka (A x) m A y. Bukti : n Untuk sebarang x, y mmax dengan x m y, maka
x y=y A(xy)=Ay
(A x ) ( A y ) = A y A x m A y Contoh 2.9: Diberikan matriks
3 2 4 6 dan vektor x , y A 5 4 6 8 Jelas bahwa x m y.
3 2 4 8 3 2 6 10 A x dan A y 5 4 6 10 5 4 8 12 Terlihat bahwa A ⊗ x m A ⊗ y.
D. Sistem Persamaan Linear Max-Plus A x b Sub penyelesaian terbesar pada sistem persamaan linier max-plus A x b akan dibahas pada sub bab ini. Kekurangan dari aljabar max-plus
adalah tidak adanya invers additive. Hal ini yang menyulitkan untuk
24
menyelesaikan sistem persamaan linear
A x b . Dalam aljabar
penyelesaian persamaan A x b tidak selalu ada, bila ada hal ini belum tentu tunggal. Contoh 2.10: Matriks A tidak harus matriks bujur sangkar, untuk matriks A ini selalu didapat sub penyelesaian terbesar dari A x b . Subpenyelesaian 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 (Subiono, 2010: 38).
3 x1 3 Diberikan sistem persamaan linear 7 9 x2 5 Persamaan A x b tidak punya penyelesaian, sebab bila punya
x1 3 x1 3 penyelesaian berarti ada x sehingga . 7 9 x2 5 x2 Didapat x1 = 0 dan max{7, 9 + x2} = 5, terlihat bahwa tidak akan ada x2 ∈
max sehingga max{7, 9 + x2}= 5. Jadi A ⊗ x = b tidak punya penyelesaian. Untuk itulah, masalah penyelesaian A x = b dapat diperlemah dengan mendefinisikan konsep subpenyelesaian berikut. Definisi 2.8 (Rudhito, 2005: 160) m n Diberikan A mxn max dan b max . Vektor x’ max disebut
suatu sub penyelesaian sistem persamaan linear A x = b jika vektor x tersebut memenuhi A x ’ m b .
25
Subpenyelesaian A x = b selalu ada, karena untuk = [ , , … , ] T selalu berlaku A = m b . Definisi 2.9 (Rudhito, 2005: 160) Suatu subpenyelesaian
xˆ
dari sistem A x = b disebut
subpenyelesaian terbesar sistem A x = b jika x ’ m xˆ untuk setia subpenyelesaian x ’ dari sistem A x = b. Teorema 2.4 (Baccelli, et.al., 2001: 110) Diberikan A mxn max dengan unsur-unsur setiap kolomnya tidak semuanya sama dengan
dan b m . Subpenyelesaian terbesar
A x = b ada dan diberikan oleh xˆ dengan - xˆ j max(bi Aij ) untuk setiap i = 1, 2, 3, …. ,m dan j = 1, 2, …. , n Bukti :
A11 x1 A12 x2 ... A1n xn m b1 A x A x ... A x b 21 1 22 2 2n n m 2 ( A x b) : A x A x ... A x b 1 m2 2 mn n m m m1
( Aij x j ) bi , i j
( Aij x j ) m bi , i , j ( Aij x j ) bi , i , j Unsur setiap kolom matriks A tidak semuanya sama dengan , maka untuk setiap j selalu ada i sehingga Aij yang berarti - Aij ada. Mengingat setiap a max berlaku a dan a a , maka
26
koefisien-koefisien Aij = tidak akan berpengaruh pada nilai A x . Sehingga oleh karena itu, berlaku:
( Aij x j ) bi , i , j ( Aij x j bi , i , j dengan Aij ) ( x j bi Aij , i , j dengan Aij ) ( x j min(bi Aij ), j dengan Aij ) i
( x j max(bi Aij ), j ) i
Jadi, subpenyelesaian sistem A x = b adalah setiap vektor x ’ yang komponen-komponennya memenuhi x'j max(bi Aij ), j . Jika i
vektor xˆ [ xˆ1 , xˆ2, ......., xˆn ]T didefinisikan dengan xˆ j max(bi Aij ) untuk i
setiap j = 1, 2, 3, …, n, maka diperoleh ( xˆ j max(bi Aij ), j ) i
( xˆ j min(bi Aij ), j dengan Aij ) i
( xˆ j bi Aij , j dengan Aij )
( Aij xˆ j m bi , i j
A xˆ m b
Vektor xˆ tersebut merupakan subpenyelesaian sistem A x = b karena xˆ j max(bi Aij ) xˆ j , j , maka x'j xˆ j , j . Akibatnya x' m xˆ i
sehingga vektor xˆ tersebut merupakan subpenyelesaian terbesar sistem A x = b. Terkait
hal
tersebut,
maka
dapat
diketahui
cara
untuk
menyelesaikan sistem persamaan A x b . Langkah pertama, dihitung
27
terlebih dahulu subpenyelesaian terbesarnya. Kemudian diperiksa subpenyelesaian terbesarnya itu memenuhi sistem persamaan atau tidak. Untuk mempermudah menghitung subpenyelesaian terbesar A x b , diperhatikan bahwa:
xˆ1 xˆ 2 ˆ x xˆn max(bi Ai1 ) i bi Ai 2 ) max( i max(b A ) i im i max( Ai1 bi ) i Ai 2 bi ) max( i max( A b ) im i i
A11 b1 A21 b2 ... Am1 bm A12 b1 A22 b2 ... Am 2 bm A1n b1 A2 n b2 ... Amn bm T A (b) Subpenyelesaian terbesar A x b dapat ditentukan dengan langkah pertama menghitung xˆ AT (b) . Dalam Teorema 4 tersebut, karena diasumsikan bahwa komponen setiap kolom matriks A tidak semuanya sama dengan , maka subpenyelesaian terbesar xˆ n .
28
Contoh 2.11: Sebelum mencari penyelesaian terbesar sistem persamaan berikut, terlebih dahulu menentukan subpenyelesaian terbesarnya.
3 3 14 5 x1 8 x 2 6 2 13 Hitung nilai AT (b)
14 3 5 2 11 A (b) 8 7 3 6 13 T
Sehingga didapatkan subpenyelesaian terbesar sistem persamaan di atas
11 adalah 7
3 3 14 11 11 Karena 5 8 maka 7 7 2 6 13
merupakan penyelesaian
sistem di atas. Contoh 2.12: Sebelum mencari penyelesaian terbesar sistem persamaan berikut, terlebih dulu menentukan subpenyelesaian terbesarnya.
3 3 14 5 x1 12 x 2 6 2 13 Hitung nilai AT (b) terlebih dahulu
29
14 3 5 2 11 A (b) 12 7 3 6 13 T
Sehingga didapatkan subpenyelesaian terbesar sistem persamaan di atas
11 adalah 7
3 3 14 5 11 12 7 2 6 13
Karena
maka
11 7
bukan
merupakan
penyelesaian sistem di atas. Persamaan
linear
Max-Plus
A x b
mempunyai
subpenyelesaian terbesar yang bukan merupakan penyelesaian, maka Sistem
Persamaan
Linear
Max-Plus
tersebut
tidak
mempunyai
penyelesaian. Ini dapat ditunjukkan sebagai berikut, andaikan x adalah penyelesaian Sistem Persamaan Linear Max-Plus A x b yang berarti ( A x )i bi untuk setiap i = 1, 2, …., m. Misalkan Sistem Persamaan
Linear Max-Plus A x b mempunyai subpenyelesaian terbesar xˆ yang bukan merupakan penyelesaian yang berarti terdapat i {1, 2, ….., m}, sehingga ( A xˆ )i bi . Untuk itu, x merupakan subpenyelesaian, maka
x m xˆ .
Akibatnya
berlaku
( A x ) m ( A xˆ)
yang
berarti
( A x )i ( A xˆ), untuk setiap i = 1, 2, …., m. Hal ini berakibat terdapat
i {1, 2, …. m}, sehingga ( A x )i ( A xˆ) bi , yang kontadiksi dengan pengandaian di atas.
30
Akibat 2.4 (Schutter and Boom, 2000: 3) Diberikan A mxn max dengan unsur-unsur setiap kolomnya tidak semuanya sama dengan dan b m . Jika xˆ adalah subpenyelesaian terbesar sistem persamaan linear Max-Plus A x b maka untuk setiap indeks j {1, 2, …. m} terdapat suatu indeks i(j) {1, 2, …. m} sedemikian sehingga Ai ( j ), j xˆ j bi ( j ) . Bukti : Karena xˆ subpenyelesaian
terbesar sistem A x b , maka
menurut Teorema 4 xˆ j min(bi Aij ) untuk j = 1, 2, …., n dengan i
Aij . Hal ini berarti untuk setiap indeks j {1, 2, …..n) terdapat suatu
indeks i(j) {1, 2, ….., m} sedemikian sehingga xˆ j bi ( j ) Ai ( j ), j atau Ai ( j ), j xˆ j bi ( j )
Definisi 2.10 (Rudhito, 2005 :162) Diberikan x [ x1 , x2 ,....., xn ]T n . Didefinisikan x
maks xi i
untuk i = 1, 2, ….,n. Diberikan masalah optimisasi yang berkaitan dengan sistem persamaan linear max-plus A x b berikut : Diberikan A mxn max dengan setiap kolom matriks A tidak semuanya sama dengan , dan
x m , maka A x b m .
Akibatnya b - A x merupakan hasil operasi pengurangan vektor dalam m .
31
Berikut teorema yang memberikan penyelesaian masalah optimisasi tersebut. Teorema 2.5 (Schutter, 1996 : 37) Diberikan A mxn setiap kolomnya tidak max dengan komponen semuanya sama dengan , dan b m . Vektor x # x
2
dengan xˆ
subpenyelesaian terbesar sistem A x = b dan b A xˆ ,
b A xˆ . Selanjutnya
merupakan vektor yang meminimalkan b A xˆ
2
Bukti : Misalkan xˆ subpenyelesaian terbesar sistem A x b (i) Jika xˆ adalah penyelesaian sistem A x b , maka (ii) b A xˆ
maks bi ( A xˆ )i 0 . i
Akibatnya xˆ meminimalkan b A xˆ
(iii) Jika xˆ bukan merupakan penyelesaian sistem A x b , maka
b A xˆ
maks bi ( A xˆ )i 0 . Karena A xˆ m b , maka i
maks bi ( A xˆ )i maks bi ( A xˆ )i . Himpunan indeks i yaitu {1, i
i
2, ….., m} dapat dipartisi menjadi tiga himpunan bagian I , J , K sedemikian sehingga:
b A xˆ
0 untuk semua i I
32
b A xˆ b A xˆ
untuk semua i J
, untuk semua i K , dengan 0 i 1
xˆ merupakan subpenyelesaian terbesar sistem A x = b, maka
menurut Akibat 2.4 untuk setiap indeks j {1, 2,....., n} terdapat suatu indeks
i( j ) {1, 2,....., m}
sedemikian
sehingga
Ai ( j ), j xˆ j bi ( j ) .
Akibatnya I tidak kosong, karena xˆ bukan merupakan penyelesaian sistem
A x b ,
maka
terdapat
suatu
indeks
i,
sehingga
maks bi ( A xˆ )i . Akibatnya himpunan J juga tidak kosong. i
Sementara himpunan K dapat kosong atau tidak kosong. Teorema 2.6 (Rudhito, 2005 :163) Setiap x yang memenuhi x m xˆ berlaku ( A x)m ( A xˆ) , yang berakibat maks bi ( A xˆ )i
maks bi ( A xˆ )i untuk setiap x m xˆ .
i
i
Dengan memperhatikan Teorema 2.5 diperoleh bahwa untuk sebarang
a max berlaku ( A xˆ) a A ( xˆ a) . Jika a 0 , maka xˆ m ( xˆ a) yang berakibat maks bi ( A xˆ )i i
maks bi ( A xˆ )i untuk i
suatu skalar positif a0 max . Didefinisikan b x(a) : xˆ a dengan a max, a 0 , bi ( A x(a))i bi (( A xˆ) a) , maka diperoleh:
33
a, jika i I bi ( A x(a))i a, jika i J a, jika i K i tidak kosong dan
I dan J
b A x(a )
yang
b A x#
a 0
i
b A x
. Diperoleh x # x( ) xˆ merupakan 2 2 2
meminimumkan
b A x
dan
diperoleh
max , . 2 2 2
Ditunjukkan bahwa tidak ada vektor b A x
i K , maka
max bi ( A x(a))i max( a , a ) yang mempunyai
nilai minimum untuk a vektor
0 i 1 untuk semua
2
2
x
yang memenuhi
. Misalkan terdapat vektor x n sedemikian sehingga
……………
(1)
Didefinisikan x xˆ maka A x A ( xˆ ) . xˆ merupakan subpenyelesaian terbesar sistem A x b maka menurut Akibat 2.4 untuk setiap j {1, 2,...., n} maka terdapat suatu indeks i(j) sedemikian sehingga Ai ( j ), j xˆ j bi ( j ) .
( A x )i ( j ) max( Ai ( j ), j xˆ j j ) Ai ( j ), j xˆ j j , maka diperoleh j
( A x )i ( j ) b j j . Karena ketaksamaan (1) maka j
setiap j {1, 2,...., n} .
2
(2) untuk
34
xˆ merupakan subpenyelesaian terbesar sistem A x b maka
terdapat
suatu
i {1, 2,...., m}
indeks
sedemikian
sehingga
bi ( A xˆ )i atau bi ( A xˆ )i . ( A xˆ )i Ai1 xˆ1 Ai 2 xˆ2 ..... Am xˆm max( Ai1 xˆ1 , Ai 2 xˆ2 ,....., Am xˆm ), maka Aij xˆ j bi
untuk setiap j {1, 2,...., n} . Akibatnya ( A x )i max( Aij xˆ j j ) max(bi j ) j
j
bi max j . Ketaksamaan (2), maka bi max j bi j
bi
2
j
2
. Jadi, terdapat suatu indeks i {1, 2,...., m} sedemikian, sehingga
( A x )i bi
b ( A x )
2
atau bi ( A x )i
2
2
.
Hal
ini
berakibat
, yang bertentangan dengan bahwa b ( A x )
bahwa
2
.
E. Sistem Event Diskret (SED) dan Aljabar Max-Plus Menurut Necoara et.al. (2008: 1), SED merupakan suatu keadaan sistem pasti bergantung dengan waktu yakni setiap waktu bertambah, maka keadaan sistem dipastikan berubah pula. Sistem yang demikian ini disebut dengan sistem terkendali waktu (time-driven system). Selain sistem tersebut, sering dijumpai pula suatu sistem yang berkembang berdasarkan kemunculan kejadiannya. Transisi keadaan merupakan hasil dari kejadian lain yang selaras (kejadian-kejadian yang bertindak sebagai kejadian input bagi transisi keadaan yang bersangkutan). Dengan kata
35
lain, perubahan keadaan merupakan hasil dari kejadian sebelumnya. Sistem seperti ini disebut dengan sistem terkendali kejadian (event-driven system). Aljabar Max-Plus dapat digunakan untuk menggambarkan secara linear dinamika waktu dari suatu sistem nonlinear dalam aljabar konvensional, sehingga pembahasan menjadi lebih mudah. Pendekatan Aljabar Max-Plus berguna untuk menentukan dan menganalisa berbagai sifat sistem, tetapi pendekatan hanya bisa diterapkan pada sebagian klas SED. Sub klas ini adalah sub klas dari waktu invarian SED deterministik. Tujuan utama dari jenis sistem event diskret dapat dijabarkan menggunakan model Sistem linear Max-Plus waktu invariant sebagai berikut: x(k 1) A x(k ) B u(k ) ……….(1)
y(k ) C x(k ) ……………………….(2) Diperhatikan suatu sistem produksi sederhana yang disajikan dalam Gambar 1 berikut: d1 = 5 u(k)
t1 = 2
P1
t3 = 1
d3 = 3 P3
t5 = 0
d2 = 6 t2 = 0
P2
t4 = 0
Gambar 1. Contoh Sistem Produksi Sederhana (Schutter, 1996 : 5)
y(k)
36
Sistem ini terdiri dari 3 unit pemrosesan P1, P2, P3 . Bahan baku dimasukkan ke P1 dan P2, diproses dan dikirimkan ke P3. Waktu pemrosesan untuk P1, P2 dan P3 berturut-turut adalah d1 = 5, d2 = 6 dan d3 = 3 satuan waktu. Diasumsikan bahwa bahan baku memerlukan t1 = 2 satuan waktu untuk dapat masuk dari input ke P1 dan memerlukan t3 = 1 satuan waktu dari produk yang telah diselesaikan di P1 untuk sampai di P3, sedangkan waktu transportasi yang lain diabaikan. Pada input sistem dan antara unit pemrosesan terdapat penyangga (buffer), yang berturutturut disebut buffer input dan buffer internal, dengan kapasitas yang cukup besar untuk menjamin tidak ada penyangga yang meluap (overflow). Suatu unit pemrosesan hanya dapat mulai bekerja untuk suatu produk baru jika ia telah menyelesaikan pemrosesan produk sebelumnya. Diasumsikan bahwa setiap unit pemrosesan mulai bekerja segera setelah bahan tersedia. Didefinisikan (Rudhito, 2003): i)
u(k+1) : waktu saat bahan baku dimasukkan ke sistem untuk pemrosesan ke-(k+1),
ii) xi(k)
: waktu saat unit pemrosesan ke-i mulai bekerja untuk pemrosesan ke-k,
iii) y(k)
: waktu saat produk ke-k yang diselesaikan meninggalkan sistem.
Waktu saat P1 mulai bekerja untuk pemrosesan ke-(k+1) dapat ditentukan sebagai berikut. Jika bahan mentah dimasukkan ke sistem untuk pemrosesan ke-(k+1), maka bahan mentah ini tersedia pada input
37
unit pemrosesan P1 pada waktu t = u(k+1) + 2. P1 hanya dapat mulai bekerja pada sejumlah bahan baku baru segera setelah menyelesaikan pemrosesan sebelumnya, yaitu sejumlah bahan baku untuk pemrosesan ke-k. Waktu pemrosesan pada P1 adalah d1 = 5 satuan waktu, maka produk setengah jadi ke-k akan meninggalkan P1 pada saat t = x1(k) + 5. Hal ini dapat dituliskan dengan: x1(k+1) = max (u(k+1) + 2, x1(k) + 5) untuk k = 1, 2, 3, ... . Dengan alasan yang sama untuk P2, P3 dan waktu saat produk ke-k yang diselesaikan meninggalkan sistem, diperoleh: x2(k+1) = max (u(k+1) + 0, x2(k) + 6) x3(k+1) = max (x1(k+1) + 5 + 1, x2(k+1) + 6 + 0, x3(k) + 3) = max (max (u(k+1) + 2, x1(k) + 5) + 6, max (u(k+1) + 0, x2(k) + 6) + 6, x3(k) + 3) = max (u(k+1) + 2 + 6, x1(k+1) + 5 + 6, u(k+1) + 0 + 6, x2(k) + 6 + 6, x3(k) + 3) = max ( x1(k) + 11, x2(k) + 12, x3(k) + 3, u(k+1) + 8) y(k) = x3(k) + 3 + 0 untuk k = 1, 2, 3, ... . Menggunakan operasi Aljabar Max-Plus, persamaan-persamaan dalam model sistem produksi sederhana di atas dapat dituliskan sebagai berikut: x1(k+1) = 5 x1(k) 2 u(k+1) x2(k+1) = 6 x2(k) u(k+1)
38
x3(k+1) = 11 x1(k) 12 x2(k) 3 x3(k) 8 u(k+1) y(k) = 3 x3(k) . Jika dituliskan dalam persamaan matriks dalam Aljabar Max-Plus, persamaan-persamaan di atas menjadi
5 x(k+1) = 6 x(k) 11 12 3 y(k) =
3
2 0 u(k+1) 8
x(k) untuk k = 1, 2, 3, ... , dengan x(k) = [x1(k),
x2(k), x3(k)] T. Hasil di atas dapat juga dituliskan dengan: x(k+1) = A x(k) B u(k+1) y(k) = C x(k) untuk k = 1, 2, 3, ... , dengan x(k) = [x1(k), x2(k), x3(k)] T 3max , keadaan
5 2 33 1 awal x(0) = x0 , A = 6 max , B = 0 3max 11 12 3 8 dan C =
3 . 3 1max
Sistem Event Diskret (SED) yang dibahas mempunyai waktu aktifitas dan barisan kejadian yang deterministik telah dilustrasikan pada contoh diatas. Matriks dalam persamaan sistemnya merupakan matriks konstan, yaitu tidak tergantung pada parameter k, sehingga sistemnya merupakan sistem waktu invariant. Sistem seperti dalam contoh di atas merupakan suatu contoh Sistem Linear Max-Plus Waktu Invariant seperti yang diberikan dalam definisi berikut.
39
Sistem
Event
Diskret
waktu
invariant
dapat
dianalisis
menggunakan beberapa teknik Aljabar Max-Plus yang diilustrasikan antara lain pada sistem produksi. Ada 5 jenis Sistem Event Diskret (SED) pada sistem produksi , diasumsikan bahwa ui(k), xi(k) dan yi(k) diketahui (Schutter, 1996: 8-11 ) yakni sebagai berikut: Jenis 1: Seri Ada 2 unit pemroses P1 dan P2 yang dihubungkan secara seri. Di antara P1 dan P2 ada penyangga dengan kapasitas terbatas N1. d1 u(k)
x1(k)
P1
d2
N1 x2(k)
P2
y(k)
Gambar 2. Sistem Produksi Seri Output penyangga dari pemroses unit P1 mempunyai kapasitas dari sebagian N1, P1 hanya dapat memulai proses ke-(k + 1) jika proses (k-N1) telah meninggalkan output penyangga dari P1, kemudian unit P2 memulai proses ke-(k-N1). Maka dari itu diperoleh: x1 (k 1) max(u (k ), x1 (k ) d1 , x2 (k N1 )) x1 (k 1) max( x2 (k ) d 2 , x1 (k 1) d1 ) y (k ) x2 (k ) d 2
Jenis 2: Assembly Berikut merupakan keadaan dimana satu unit pemroses (Pn+1) assembles yang berhubungan yang berasal dari unit-unit proses lainnya (P1, P2,…….. Pn ).
40
xi (k 1) max( xi (k ) di , ui (k ), xn1 (k Ni )) untuk i = 1, 2, 3, …. n d1 x1(k)
u1(k)
P1
d2 x2(k)
u2(k)
x3(k)
u3(k)
N1
dn+1
N2
xn+1(k)
P2
d n
y(k)
Pn+1
Nn
Pn
Gambar 3. Sistem Produksi Assembly
xn 1 (k 1) max( x1 (k 1) d1 , x2 (k 1) d 2 ....., xn (k 1) d n , xn 1 (k 1) d n 1 ) y(k ) xn 1 (k ) d n 1
Jenis 3: Splitting Sistem ini salah satu unit pemroses (P0) yang didistribusikan ke unit pemroses lainnya (P1, P2,…., Pn). Keadaan tersebut ditunjukkan sebagai berikut:
x0 (k 1) max( x0 (k ) d 0 , x1 (k N1 ), x2 (k N 2 )....., xn (k N n )) xi (k 1) max( xi (k ) di , x0 (k 1) d 0 ) untuk i 1, 2,..., n y (k ) xi (k ) di untuk i 1, 2,..., n
d1
N1
d0 u(k)
x0(k) P0
x1(k)
N2
N n
Gambar 4. Sistem Produksi Splitting
x2(k)
P1
d2 P2
y1(k)
y2(k)
dn xn(k)
Pn
yn(k)
41
Jenis 4: Paralel Diasumsikan bahwa terdapat suatu sistem dengan 3 unit pemroses (P0, P1 dan P2) dengan mengikuti aturan (i)
Bagian yang diberi angka ganjil meninggalkan unit pemroses P0 kemudian melanjutkan ke unit pemroses P1
(ii)
Bagian yang diberi angka genap meninggalkan unit pemroses P0 kemudian melanjutkan ke unit pemroses P2
Diketahui sistem yang digambarkan berikut ini: (i)
uo(k): waktu dimana bagian 2k-1 telah masuk ke dalam sistem
(ii)
ue(k): waktu dimana bagian 2k telah masuk ke dalam sistem
(iii)
x0o (k): waktu dimana bagian 2k–1 masuk ke unit pemroses P0
(iv)
x0e (k): waktu dimana bagian 2k masuk ke unit pemroses P0 N1 d0 0
u (k) ue(k)
x00 (k ) x0e (k )
P0
x1(k)
d1 P1
y1(k)
Bagian 1, 3,5,…. Bagian 2,4,6,…. N2
Gambar 5. Sistem Produksi Paralel Sistem tersebut dapat dideskripsikan dengan
d2 x2(k)
P2
y2(k)
42
x0o (k 1) max( x0e (k ) d 0 , u o (k 1), x1 (k N1 )) x0e (k 1) max( x00 (k 1) d 0 , u e (k 1), x2 (k N 2 )) x1 (k 1) max( x1 (k ) d1 , x00 (k 1) d 0 ) x1 (k 1) max(( x2 (k ) d 2 , x0e (k 1) d 0 ) y1 (k ) x1 (k ) d1 y2 (k ) x2 (k ) d 2 Dengan catatan bahwa u0o (k ) u(2k 2) dan u0e (k ) u(2k 1) untuk semua k 0
Jenis 5: Produksi Fleksibel dengan beberapa aktivitas Diketahui bahwa sebuah sistem dengan 3 unit pemroses (P1, P3, P4) pada dua jenis bagian (T1 dan T2) yang akan di produksi. Terdapat 4 aktivitas yang berbeda. T1 bagian yang pertama diproses pada unit P1 (aktivitas 1) dan kemudian dilakukan proses unit T3 (aktivitas 3). T2 pertama kali bagian yang diproses pada unit P1 (aktivitas 2) dan kemudian dilakukan proses pada P4 (aktivitas 4). Sederetan proses pada P1 adalah P1, P2, P1, P2……Waktu proses untuk aktivitas ke i adalah di. Jika diketahui: N3
T1 u1(k) x1(k)
d1
d3 x3(k)
P3
y1(k)
T1
P1 x2(k) T2
u2(k)
d2
T2 N4
d4 x4(k)
P4
y2(k)
Gambar 6. Sistem Produksi Fleksibel dengan beberapa aktivitas
43
(i)
ui(k): waktu dimana material untuk T, dimasukkan ke sistem sampai ke (k+1)
(ii)
xi(k): waktu dimana aktivitas ke-i dimulai sampai ke-k
(iii)
yi(k):
waktu
dimana
produk
diselesaikan
untuk
T,
dan
meninggalkan sistem. Sehingga diperoleh:
x1 (k 1) max( x2 (k ) d 2 , u1 (k ), x3 (k N 3 )) x2 (k 1) max( x1 (k 1) d1 , u2 (k ), x4 (k N 4 )) x3 (k 1) max( x3 (k ) d3 , x1 (k 1) d1 ) x4 (k 1) max( x4 (k ) d 4 , x2 (k 1) d 2 ) y1 (k ) x3 (k ) d3 y2 (k ) x4 (k ) d 4 Jika diketahui sistem yang terdiri dari sebuah kombinasi atas subsistem dari jenis 1 sampai dengan 5 dan dengan aktivitas yang ditentukan. Kemudian dari sistem tersebut dapat dideskripsikan secara umum dengan bentuk model: x(k 1) A0 x(k 1) A1 x(k ) ..... Aq x(k q) B u (k ) ...........(5.1) y (k ) C x(k ) .............................................................................................(5.2)
Setelah itu subtitusi x(k+1) pada ruas kanan (1) dan mengembalikan x(k+1) yang tidak muncul (yang selalu terjadi jika sistem tidak memuat loop).
44
F. Sistem Linear Max-Plus Waktu Invariant Definisi 2.11 (Schutter, 1996 : 156) Sistem Linear Max-Plus Waktu Invariant adalah SED (Sistem Event Diskret) yang dapat dinyatakan dengan persamaan berikut: x(k+1) = A x(k) B u(k+1)……..(2.11.1) y(k) = C x(k)……….………………...(2.11.2) n untuk k = 1, 2, 3, ... , dengan kondisi awal x(0) = x0, A nmax , B m n nmax , dan C lmax . Vektor x(k) nmax menyatakan keadaan (state),
u(k) mmax adalah vektor input, dan y(k) lmax adalah vektor output sistem saat waktu ke-k. SLMI seperti dalam definisi di atas secara singkat akan dituliskan dengan SLMI (A, B, C) dan dituliskan dengan SLMI (A, B, C, x0), jika kondisi awal x(0) = x0 diberikan. SLMI dengan satu input dan satu output akan disebut SLMI satu input satu output (SISO). Sedangkan SLMI dengan lebih dari satu input dan lebih dari satu output akan disebut SLMI multi input multi output (MIMO). Analisis Input-Output Sistem Linear Max-Plus Waktu-Invariant Subbab ini akan membahas analisis dan beberapa masalah inputoutput SLMI. Jika kondisi awal dan suatu barisan input diberikan untuk suatu SLMI (A, B, C, x0 ), maka secara rekursif dapat ditentukan suatu barisan vektor keadaan sistem dan barisan output sistem.
45
Diperhatikan sistem produksi sederhana (gambar 1), misalkan kondisi awal sistem x(0) = [0, 1, ]T yang berarti unit pemrosesan P1 dan P2 berturut-turut memulai aktifitasnya saat waktu 0 dan 1 sementara unit pemrosesan P3 masih kosong dan harus menunggu datangnya input dari P1 dan P2 . Bahan mentah dimasukkan sistem saat waktu 0, 9, 12, 24 dan seterusnya yang berarti diberikan barisan input u(1) = 0, u(2) = 9, u(3) = 12, u(4) = 24, dan seterusnya, dengan u(k) u(k+1) untuk setiap k = 1, 2, 3, .... Secara rekursif dapat ditentukan barisan vektor keadaan berikut
5 0 2 x(1) = A x(0) B u(1) = 6 1 0 0 11 12 3 8 5 = 7 13
2 5 0 = 7 8 13
10 x(2) = A x(1) B u(2) = 13 19
11 11 9 = 13 , 17 19
16 x(3) = A x(2) B u(3) = 19 25
14 16 12 = 19 , 20 25
21 x(4) = A x(3) B u(4) = 25 31
26 26 24 = 25 , dan seterusnya . 32 32
Kemudian diperoleh barisan output sistem sebagai berikut dengan menggunakan y(k) = x3(k) + 3 :
46
y(1) = 16, y(2) = 22, y(3) = 28, y(4) = 35, dan seterusnya yang berarti produk akan dapat diambil saat waktu 16, 22, 28, 35 dan seterusnya.. Teorema 2.7 (Input-Output SLMI (A, B, C, x0 )) (Schutter, 1996 : 161) Diberikan suatu bilangan bulat positip p. Jika vektor output y = [y(1), y(2), ... , y(p)] T dan vektor input u = [u(1), u(2), ... , u(p)] T pada SLMI (A, B, C, x0 ) , maka y = K x0 H u dengan
CB CA 2 C A CB dan H C A B K= p p 1 B C A p 2 B C A C A
. C B
Bukti: Jika diberikan kondisi awal x(0) = x0 dan barisan input u (k )k 0 , k
dengan induksi matematik akan dibuktikan berlaku x(k) = ( A x(0) ) (
k
( i 1
A
k i
B u(i) ) untuk k = 1, 2, 3, .......(2.7.1)
0
Diperhatikan bahwa x(1) = A x(0)B u(1) = A x(0) A Bu(1) 1
= ( A x(0) ) ( Jadi, (2.7.1) benar untuk k = 1. n
x(n)=( A x(0))( ( A n
i 1
n i
1
( i 1
1i
A
B u(i) ).
Misalkan benar untuk k = n yaitu
Bu(i))
47
maka x(n +1) = A x(n) B u(n +1) n
= A (( A x(0)) ( ( A n
n i
B u(i)))B u(n+1)
i 1
= (( A
n 1
n
x(0))( ( A
( n 1) i
B u(i)))B u(n +1)
i 1
= (( A
n 1
n 1
x(0))( ( A
( n 1) i
B u(i)))Bu(n+1).
i 1
Jadi, (2.7.1) benar untuk k = n +1. Akibatnya diperoleh k
y(k) = (C A x(0)) ( C A k
k i
B u(i)…………….(2.7.2)
i 1
untuk k = 1, 2, 3, ... . Diberikan suatu bilangan bulat positip p. Jika didefinisikan y = [y(1), y(2), ... ,
y(p)]T dan u = [u(1), u(2), ... ,
y(p)]T maka dari
persamaan (2.7.2) diperoleh: y(1) = C A x(0) C B u(1) 2
y(2) = C A x(0) C A B u(1) C B u(2)
p
y(p) = C A x(0) C A
p 1
B u(1) C A
… C B u(p). atau dalam persamaan matriks dapat dituliskan sebagai
p 2
B u(2)
48
y (1) C A CB y (2) C A 2 C A B CB = x(0) p p 1 p 2 B y ( p ) C A C A B C A
u (1) u (2) C B u ( p )
atau y = K x(0) H u ………………….(2.7.3) dengan
CB CA C A 2 C A B CB dan H = K= p p 1 p 2 B CA B C A C A
C B
Dalam sistem produksi, Teorema 2.7 berarti bahwa jika diketahui kondisi awal sistem dan barisan waktu saat bahan mentah dimasukkan ke sistem, maka dapat ditentukan barisan waktu saat produk selesai diproses dan meninggalkan sistem. Contoh 2.13: Diperhatikan sistem produksi sederhana dalam Gambar 1. Didefinisikan y = [y(1), y(2), y(3), y(4)]T. Jika diberikan x(0) = [0, 1, ]T dan u = [0, 9, 12, 24 ]T, maka diperoleh y = K x(0) H u dengan
14 19 K= 24 29
6 9 dan H = 27 12 33 15
15 21
11 16 11 . 21 16 11 27 21 16 11
Diperhatikan bahwa
16 11 16 22 20 22 y = K x(0) H u = = . 28 25 28 33 35 35
49
Hal ini mengartikan bahwa kondisi awal x(0) = [0, 1, ]T dan bahan baku dimasukkan ke dalam sistem pada saat waktu u(1) = 0, u(2) = 9, u(3) = 12, u(4) = 15, maka produk selesai dan akan meninggalkan sistem pada saat waktu y(1) = 16, y(2) = 22, y(3) = 28, y(4) = 34. Hasil pada contoh ini sesuai dengan perhitungan sebelumnya. Akibat 2.6 Input-Output SLMI (A, B, C, )(Schutter, 1996: 86) Diberikan suatu bilangan bulat positip p. Jika vektor output y = [y(1), y(2), ... , y(p)] T dan vektor input u = [u(1), u(2), ... , u(p)] T pada SLMI (A, B, C, ) , maka y = H u dengan
CB C A B CB H = p 1 p 2 B CA B C A
. C B
Bukti: Seperti bukti Teorema 2.7, dengan mengambil x0 = . Dalam sistem produksi, SLMI (A, B, C, ) merupakan keadaan awal sistem. Semua penyangga dalam keadaan kosong dan tidak ada unit pemrosesan yang memuat bahan mentah atau produk setengah jadi.
50
Contoh 2.14: Diperhatikan sistem produksi sederhana dalam Gambar 1. Didefinisikan y = [y(1), y(2), y(3), y(4)]T. Jika diberikan x(0) = , dan u = [0, 9, 12,
15 ]T, maka diperoleh y = H u dengan
11 16 11 . H= 21 16 11 27 21 16 11
11 0 16 11 9= Diperhatikan bahwa y = H u = 21 16 11 12 27 21 16 11 15
11 20 . 25 30
Hal ini mengartikan bahwa keadaan awal sistem semua penyangga dalam keadaan kosong dan tidak ada unit pemrosesan yang memuat bahan mentah atau produk setengah jadi. Selanjutnya bahan baku dimasukkan ke dalam sistem pada saat waktu u(1) = 0, u(2) = 9, u(3) = 12, u(4) = 15, maka produk selesai dan akan meninggalkan sistem pada saat waktu y(1) = 11, y(2) = 20, y(3) = 25, y(4) = 30. Berikut dibahas masalah input paling lambat pada SLMI (A, B, C, x0). Masalah input paling lambat pada SLMI (A, B, C, x0) adalah sebagai berikut : Teorema 2.8 (Rudhito, 2003: 62) Penyelesaian masalah input paling lambat pada SLMI(A, B, C, ɛ) dengan C B ≠ ɛ diberikan oleh uˆ [uˆ (1), uˆ (2),..., uˆ ( p)]T dengan
uˆ (k ) max( y(i) H i ,k ) , untuk k = 1, 2, …, p. 1i p
51
Bukti: K ɛ = ɛ, maka K ɛ H u = H u. Hal ini mengakibatkan masalah input paling lambat pada SLMI (A, B, C, ɛ) menjadi masalah menentukan vektor input u terbesar (waktu paling lambat) yang memenuhi H u m y. Masalah ini merupakan masalah menentukan sub penyelesaian terbesar sistem persamaan linear max-plus H u = y. C B ≠ ɛ maka komponen setiap kolom matriks H tidak semuanya sama dengan ɛ. Menurut Teorema 8, apabila H u = y diberikan oleh
uˆ [uˆ (1), uˆ (2),..., uˆ( p)]T dengan uˆ (k ) max( y(i) H i ,k ) , untuk k = 1, 1i p
2, …, p. Teorema 2.9 (Rudhito, 2003: 64) Diberikan SLMI (A, B, C, x0) dengan C B ≠ ɛ. Jika K x0 m y, maka penyelesaian masalah input paling lambat pada SLMI (A, B, C, x0) diberikan oleh uˆ [uˆ (1), uˆ (2),..., uˆ ( p)]T dengan
uˆ (k ) max( y(i) H i ,k ) , untuk k = 1, 2, …, p. 1i p
Bukti: K x0 m y, maka K x0 H u = y H u = y. Selanjutnya bukti seperti pada Teorema 8 di atas. Berikut dibahas mengenai masalah minimisasi simpangan maksimum output pada SLMI (A, B, C, x0). Masalah minimisasi simpangan maksimum output pada SLMI (A, B, C, x0) adalah sebagai berikut. Teorema 3.0 (Rudhito, 2003: 65) Penyelesaian masalah minimasi simpangan maksimum output pada SLMI(A, B, C, ɛ) dengan C B ≠ ɛ diberikan oleh u uˆ
2
52
dengan uˆ merupakan subpeyelesaian terbesar sistem H u = y dan
max ( y H uˆ)i . i
Bukti: K ɛ = ɛ, maka K ɛ H u = H u. Hal ini mengakibatkan masalah minimasi simpangan maksimum output ini jadi menentukan vektor input u sedemikian sehingga max ( y H U )i . Masalah ini i
merupakan masalah optimisasi yang berkaitan dengan sistem persamaan linear max-plus H u = y. Karena C B ≠ ɛ maka komponen setiap kolom matriks H tidak semuanya sama dengan ɛ. Menurut Teorema 2.5, suatu
penyelesaian
u
untuk
u uˆ
masalah
2
,
dengan
=
max ( y H uˆ) i dan uˆ merupakan subpenyelesaian terbesar sistem H i
u = y. Pembahasan
penyelesaian
masalah
minimasi
simpangan
maksimum output pada SLMI (A, B, C, ɛ) di atas juga dapat diperluas untuk SLMI (A, B, C, x0) dengan x0 ≠ ɛ, seperti diberikan dalam teorema berikut. Teorema 3.1 (Rudhito, 2003: 67) Diberikan SLMI (A, B, C, x0) dengan C B ≠ ɛ. Jika K x0 m y, maka penyelesaian masalah minimasi simpangan maksimum output pada SLMI (A, B, C, x0) diberikan oleh u uˆ
2
dengan uˆ merupakan
subpenyelesaian terbesar sistem H u = y dan = max ( y H uˆ )i . i
53
Bukti: K x0 m y, maka maka K x0 H u = y H u = y. Selanjutnya bukti seperti pada Teorema 9 di atas. Contoh 2.15 (Schutter, 1996: 51): Misal dari Sistem pada Gambar 1 produk akan diambil oleh pemesan pada
waktu
17,
11 T uˆ H ( y )
19,
24
dan
27,
16 21 27 17 0 19 6 11 16 21 , 24 11 11 16 11 27 16
maka
didapatkan
sehingga
waktu
paling lambat untuk memasukkan bahan ke dalam sistem adalah uˆ = [0, 6, 11, 16]T.
11 0 11 16 11 6 17 , ˆy H uˆ 21 16 11 11 22 27 21 16 11 16 27 sehingga waktu penyelesaian paling lambat dalam proses pengerjaan produk berturut-turut yˆ = [11, 17, 22, 27]T.
0 3 14 6 9 20 ˆ 6 , maka u u 3 dan y H u 14 25 2 11 16 19 30
