6
BAB 2 LANDASAN TEORI
2.1
Persediaan
2.1.1 Definisi Persediaan Persediaan adalah stok bahan yang digunakan untuk memudahkan produksi atau untuk memuaskan permintaan pelanggan. Secara khusus persediaan meliputi bahan baku, barang dalam proses dan barang jadi (Schroeder, 2000, P. 304). Persediaan juga bisa berarti penyimpanan sumber daya yang digunakan untuk memenuhi kebutuhan saat ini atau di masa mendatang (Heizer and Barry, 1996, P. 574). Persediaan meliputi persediaan bahan mentah, barang dalam proses, barang jadi, dan bahan-bahan pembantu atau bahan pelengkap (Ebert, 1996, P. 453). Persediaan adalah bahan atau barang yang disimpan yang akan digunakan untuk memenuhi tujuan tertentu, misalnya untuk proses produksi perakitan, untuk dijual kembali, untuk suku cadang dari suatu peralatan atau mesin (Herjanto, 1999, P. 219).
2.1.2 Fungsi Pengendali Persediaan Persediaan mempunyai beberapa fungsi (Herjanto, 1999, P. 220), antara lain: 1. Menghilangkan resiko keterlambatan pengiriman bahan baku atau barang yang dibutuhkan perusahaan.
7 2. Menghilangkan resiko jika bahan yang dipesan tidak baik atau barang yang dibutuhkan perusahaan. 3. Menghilangkan resiko terhadap kenaikan barang atau inflasi. 4. Untuk menyimpan bahan baku yang dihasilkan secara musiman sehingga perusahaan tidak akan mengalami kesulitan jika bahan itu tidak tersedia di pasaran. 5. Mendapatkan keuntungan dari pembelian berdasarkan pemotongan kuantitas (quantity discounts). 6. Memberikan pelayanan kepada pelanggan dengan tersedianya barang yang diperlukan
2.2
Model Optimalisasi Optimalisasi adalah sarana untuk mengekspresikan, dalam model matematika, hasil dari penyelesaian suatu masalah dengan cara terbaik (Nash dan Sofer, 1996, P. 3). Hal ini dapat diartikan sebagai menjalankan bisnis untuk memaksimalkan keuntungan dan efisiensi serta meminimalkan kerugian, biaya atau resiko. Keinginan untuk memecahkan masalah dengan model optimalisasi secara umum digunakan pada hampir semua bidang aplikasi. Model optimalisasi telah digunakan selama berabad-abad. Pada masa sekarang ini menjadi sangat cocok jika ingin mengembangkan bisnis menjadi semakin besar dan rumit. Para insinyur pun menjadi semakin ambisius. Dalam banyak keadaan, tidak lagi mungkin untuk membuat keputusan tanpa bantuan model optimalisasi. Sebagai contoh, dalam sebuah kerjasama multinasional yang
8 besar, persentase kecil suatu perkembangan dalam proses operasi mungkin meningkatkan penambahan keuntungan hingga jutaan dollar. Untuk model yang besar, dengan segala kerumitan yang ada, akan sedikit bermasalah jika tidak dapat diselesaikan. Beberapa dekade terakhir telah menjadi saksi pengembangan yang sangat mengejutkan dalam hardware dan software komputer, dan kemajuan ini telah membuat model optimalisasi menjadi alat yang umum dipakai dalam bisnis, ilmu pengetahuan, dan perusahaan. Sekarang ini, sangat mungkin untuk menyelesaikan permasalahan dengan ribuan atau bahkan jutaan peubah.
2.2.1 Sistem Persamaan Linear Simultan Sistem persamaan linear adalah pusat dari hampir semua algoritma optimalisasi, dan bagian dari model optimalisasi yang luas (Nash dan Sofer, 1996, P. 4). Sistem persamaan linear simultan timbul hampir di setiap cabang matematika, dalam beberapa hal, persamaan ini timbul langsung dari perumusan awal dari suatu permasalahan. Di dalam hal lain, penyelesaian dari persamaan merupakan salah satu bagian dari penyelesaian beberapa macam permasalahan lain. Dalam aljabar, terdapat dua macam metode dalam menyelesaikan sistem persamaan
linear
simultan,
yaitu:
eliminasi
dan
determinan.
Dalam
menyelesaikan sistem persamaan linear simultan dengan tiga peubah, metode determinan mempunyai kelebihan dibandingkan dengan metode eliminasi.
9 Tetapi dalam menyelesaikan sistem persamaan linear simultan dengan peubah yang lebih banyak, metode determinan menjadi sangat tidak praktis. Hal ini dikarenakan dalam menyelesaikan persamaan simultan dengan n peubah, diperlukan (n – 1)(n + 1)! perkalian. Sehingga untuk menyelesaikan suatu persamaan simultan dengan sepuluh peubah dengan menggunakan metode determinan, diperlukan 359.251.200 perkalian. Kurva merupakan pendekatan terbaik dari suatu himpunan data percobaan yang berkaitan dengan penyelesaian suatu sistem persamaan simultan. Penyelesaian satu set n persamaan dengan n peubah. Jika setiap suku dari setiap persamaan mengandung hanya satu peubah, dan setiap peubahnya berpangkat satu, maka persamaan tersebut disebut sistem persamaan linear. Apabila menggunakan dua peubah, grafik persaman linear yang terjadi berupa garis lurus. Apabila menggunakan tiga peubah, grafik persaman linear yang terjadi berupa sebuah bidang. Sedangkan jika menggunakan lebih dari tiga peubah, maka grafik yang terjadi disebut sebagai hyperplane. Jawaban yang dicari dari sistem persamaan linear simultan adalah satu himpunan nilai dari n peubah, yang apabila nilai-nilai tersebut disubtitusikan ke persamaan linear sebanyak n, maka diperoleh kesamaan pada semua sistem persamaan linear secara simultan. Sistem persamaan linear simultan belum tentu mempunyai jawaban. Suatu sistem persamaan linear simultan sembarang dapat mempunyai jawaban, tetapi juga tidak mustahil jika tidak mempunyai jawaban. Terdapat tiga kemungkinan jawaban dari sistem persamaan linear simultan sembarang, yaitu:
10 a. Sistem mempunyai jawaban yang unik. Contohnya: 3x+2y=6 x+2y=4
(2.1)
Jawaban yang memenuhi persamaan (2.1) adalah x = 1 dan y = 1,5. Tidak ada pasangan lain dari nilai x dan y yang dapat memenuhi persamaan (2.1). Sistem semacam ini yang menjadi tujuan utama dari pencarian suatu jawaban. Persamaan (2.1) dapat digambarkan diagram Cartesian dua dimensi, seperti pada gambar 2.1. Pada gambar 2.1, dapat dilihat bahwa kedua garis berpotongan hanya pada satu titik. Koordinat titik tersebut merupakan jawaban yang dicari dan yang dapat memenuhi sistem persamaan linear simultan (2.1).
Gambar 2.1 Sistem persamaan linear simultan yang mempunyai jawaban yang unik
11 b. Sistem tidak mempunyai jawaban. Contohnya: 3 x + 4 y = 10 6 x + 8 y = 12
(2.2)
Sistem persamaan linear simultan (2.2) tidak akan memiliki jawaban. Grafik persamaan (2.2) dapat dilihat pada gambar 2.2. Dapat dilihat terdapat dua garis yang sejajar. Kedua garis tersebut tidak akan saling berpotongan ataupun bersinggungan, sehingga persamaan (2.2) tidak akan mempunyai jawaban.
Gambar 2.2 Sistem persamaan linear simultan yang tidak mempunyai jawaban
c. Sistem mempunyai jumlah jawaban yang tak berhingga. Contohnya: 3x+2y=6 6 x + 4 y = 12
(2.3)
Sistem persamaan linear simultan (2.3) mempunyai banyak jawaban yang dapat memenuhi persamaan tersebut, seperti: x = 2, y = 0 ; x = 0, y = 3 ; x = 1, y = 1,5 ; dan seterusnya.
12
Gambar 2.3 Sistem persamaan linear simultan yang mempunyai jumlah jawab tak berhingga
Sistem persamaan garis yang sejajar dan sistem persamaan garis yang bersinggungan dikatakan singular. Sistem merupakan singular atau tidak, terkadang dapat diketahui dari perumusan suatu persoalan. Jika informasi tersebut tidak ada, maka tergantung dari metode penyelesaiannya untuk mengetahui suatu sistem adalah singular atau tidak, atau dapat juga melakukan pengujian eksplisit untuk mengetahui kemungkinannya. Suatu pengujian dapat dilakukan dengan cara menghitung determinan dari koefisien suatu sistem. Jika hasil perhitungan determinan tersebut adalah nol, maka sistem tersebut merupakan singular. Kekurangan dari pengujian tersebut adalah usaha menghitung determinan hampir sama dengan usaha menyelesaikan persamaan. Dari sudut pandang matematika, presisi tak terhingga dari suatu sistem memiliki dua kemungkinan, yaitu: singular atau tidak. Dari sudut pandang
13 perhitungan praktis, hampir semua sistem merupakan singular, yang memberikan jawaban yang mempunyai keandalan kecil. Pada
umumnya,
terdapat
dua
macam
teknik
numerik
untuk
menyelesaikan sistem persamaan linear simultan, yaitu: metode langsung yang berhingga dan metode tak langsung yang tak berhingga. Metode langsung pada prinsipnya (dengan mengabaikan galat pembulatan) akan memberikan jawab eksak, bila operasi matematika berhingga jumlahnya. Sedangkan metode tak langsung, pada prinsipnya membutuhkan suatu operasi matematika yang tak berhingga banyaknya untuk memberikan jawab eksak. Dengan kata lain metode tak langsung mempunyai galat pembulatan, sedangkan metode langsung tidak mempunyai galat pembulatan. Dalam sistem dengan kondisi buruk, galat pembulatan dalam metode langsung akan menghasilkan jawaban yang tidak berarti. Sedangkan metode tak langsung walaupun secara teoritik ada galat pemotongannnya, metode ini mungkin lebih baik karena galat pembulatan metode ini tidak mengumpul.
2.2.2 Metode Numerik Metode numerik adalah salah satu alternatif pencarian jawaban dalam permasalahan matematika yang tidak dapat diselesaikan secara analisis. Tujuan dari metode ini adalah mencari metode yang terbaik untuk memperoleh jawaban yang berguna dari persoalan matematika dan untuk menarik informasi yang berguna dari berbagai jawaban yang dapat diperoleh.
14 Dalam mengerjakan metode numerik terdapat beberapa cara pendekatan (Djojodihardjo, 2000, P. 2), yaitu: a. Pendekatan atau penyederhanaan perumusan persoalan sehingga dapat dipecahkan secara eksak. b. Mengusahakan diperolehnya jawab pendekatan dari persoalan yang perumusannya eksak. c. Gabungan dari kedua cara pemecahan diatas. Pada umumnya, metode numerik tidak mengutamakan diperolehnya jawaban yang eksak (tepat), tetapi mengusahakan perumusan metode yang menghasilkan jawaban pendekatan yang memiliki selisih sebesar suatu nilai yang ditentukan berdasarkan kesepakatan dari jawab eksak. Proses pemecahan persoalan pada umumnya berlangsung dalam tiga tahap (Djojodihardjo, 2000, P. 2), yaitu: a. Perumusan secara tepat dari model matematik dan model numerik yang berkaitan. b. Penyusunan metode untuk memecahkan persoalan numerik. c. Penerapan metode untuk menghitung jawaban yang dicari.
15
Gambar 2.4 Proses pemecahan persoalan dalam metode numerik
2.2.3 Cramer’s Rule Cramer’s rule adalah suatu rumusan untuk menyelesaikan sistem persamaan linear simultan berdasarkan determinan. Rumusan ini dinamakan oleh Gabriel Cramer (1704-1752), seorang matematikawan berkebangsaan Swiss.
2.2.3.1 Cramer’s Rule untuk dua persamaan dengan dua peubah Cramer’s rule menyatakan bahwa penyelesaian untuk ax + by = e dan cx + dy = f didapat dari perhitungan determinan.
16 e b f d x= Ly = a b c d
a e c f a b c d
(2.4)
Berikut ini merupakan bukti dari teorema (2.4) berdasarkan metode perkalian cross vektor. Ketika kita menemukan sistem persamaan linear simultan seperti : ⎧ ax + by = e ⎨ ⎩cx + dy = f
(2.5)
Kita dapat menemukan x dan y dengan menggunakan determinan berikut : D=
a b c d
x=
Dx D
e b f d x= a b c d
Dx =
y=
e f
b d
Dy =
a c
e f
, D≠0
Dy D e f y= b d
a c a c
(2.6)
Determinan ini merupakan aturan dari Cramer. ⎛a⎞ ⎛ b ⎞ Produk alternatif ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ adalah area parallelogram yang dihasilkan ⎝c⎠ ⎝d ⎠ ⎛a⎞ ⎛b⎞ dari vektor ⎜⎜ ⎟⎟ dan ⎜⎜ ⎟⎟ . ⎝c⎠ ⎝d ⎠ ⎛a⎞ ⎛ b ⎞ ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ = ad − bc. ⎝c⎠ ⎝d ⎠
⎛a⎞ ⎛a⎞ ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ = 0. ⎝c⎠ ⎝c⎠
(2.7)
17 Kemudian gunakan produk alternatif untuk menemukan sistem persamaan linear simulatan (2.5). ⎛a⎞ ⇔ x⎜⎜ ⎟⎟ + ⎝c⎠
⎛b⎞ ⎛ e ⎞ y⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ ⎝d ⎠ ⎝ f ⎠
(2.8)
⎛b⎞ Persamaan (2.8) dikalikan dengan vektor ⎜⎜ ⎟⎟ . Selain itu, persamaan ⎝d ⎠ ⎛a⎞ (2.8) juga dikalikan dengan vektor ⎜⎜ ⎟⎟ , sehingga terdapat dua persamaan yang ⎝c⎠ baru: ⎧ ⎛a⎞ ⎛ b ⎞ ⎛b⎞ ⎛b⎞ ⎛ e ⎞ ⎛b⎞ ⎪ x⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ + y⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ d ⎪ c ⎝d ⎠ ⎝d ⎠ ⎝ f ⎠ ⎝d ⎠ ⇒⎨ ⎝ ⎠ ⎝ ⎠ ⎪ x⎛⎜ a ⎞⎟ ∧ ⎛⎜ a ⎞⎟ + y⎛⎜ b ⎟⎞ ∧ ⎛⎜ a ⎞⎟ = ⎛⎜ e ⎞⎟ ∧ ⎛⎜ a ⎞⎟ ⎜d ⎟ ⎜c⎟ ⎜ f ⎟ ⎜c⎟ ⎪⎩ ⎜⎝ c ⎟⎠ ⎜⎝ c ⎟⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
(2.9)
Persamaan (2.9) dihitung dengan mempertimbangkan syarat (2.7) : ⎧ ⎛a⎞ ⎛ b ⎞ ⎛ e ⎞ ⎛ b ⎞ ⎪ x⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ d f d ⎪ c ⇒⎨ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎪ y⎛⎜ b ⎞⎟ ∧ ⎛⎜ a ⎞⎟ = ⎛⎜ e ⎞⎟ ∧ ⎛⎜ a ⎞⎟ ⎪⎩ ⎜⎝ d ⎟⎠ ⎜⎝ c ⎟⎠ ⎜⎝ f ⎟⎠ ⎜⎝ c ⎟⎠
(2.10)
⎛ e ⎞ ⎛b⎞ ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ f d ∴x = ⎝ ⎠ ⎝ ⎠ , ⎛a⎞ ⎛ b ⎞ ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ ⎝c⎠ ⎝d ⎠
(2.11)
⎛ e ⎞ ⎛a⎞ ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ f c y=⎝ ⎠ ⎝ ⎠ ⎛ b ⎞ ⎛a⎞ ⎜⎜ ⎟⎟ ∧ ⎜⎜ ⎟⎟ ⎝d ⎠ ⎝c⎠
Hasil (2.11) dapat diekspresikan menjadi determinan seperti berikut: e b f d x= a b c d
e f y= b d
a c a c
(2.12)
18 2.2.3.2 Cramer’s Rule untuk tiga persamaan dengan tiga peubah Terdapat sistem persamaan linear simultan: ⎧ a1 x + b1 y + c1 z = d 1 ⎪ ⎨ a 2 x + b2 y + c 2 z = d 2 ⎪a x + b y + c z = d 3 3 3 ⎩ 3
(2.13)
Persamaan (2.13) mempunyai determinan: a1
b1
c1
D ≡ a2
b2
c2
a3
b3
c3
(2.14)
Kemudian kalikan D dengan x, gunakan sifat determinan mengenai perkalian determinan dengan suatu konstanta, nilainya ekuivalen dengan perkalian pada setiap input dalam suatu kolom dengan konstanta tersebut. Sehingga:
a1
b1
c1
a1 x
b1
c1
x a2
b2
c2 = a2 x
b2
c2
a3
b3
c3
a3 x
b3
c3
(2.15)
Sifat determinan yang lain mengijinkan kita untuk menambahkan suatu konstanta dikalikan dengan suatu kolom ke suatu kolom dan mendapatkan determinan yang sama, maka tambahkan y dikalikan kolom 2 dan z dikalikan kolom 3 ke kolom 1 :
a1 x + b1 y + c1 z
b1
c1
d1
b1
c1
xD = a 2 x + b2 y + c 2 z
b2
c2 = d 2
b2
c2
a 3 x + b3 y + c 3 z
b3
c3
b3
c3
d3
(2.16)
Jika d = 0, maka persamaan (2.16) akan menghasilkan xD = 0, sehingga sistem persamaan linear simultan tersebut mempunyai jawaban yang tidak dapat
19 diturunkan (contohnya, (0,0,0)) hanya jika D = 0. Jika d ≠ 0 dan D = 0, maka persamaan tidak mempunyai jawaban unik. Sebaliknya jika d ≠ 0 dan D ≠ 0, maka jawaban yang diperoleh adalah:
x=
d1 d2 d3
b1 b2 b3
c1 c2 c3
(2.17)
D
Dengan perhitungan yang hampir sama, maka diperoleh:
y=
z=
a1 a2 a3
d1 d2 d3
c1 c2 c3
(2.18)
D
a1 a2
b1 b2
d1 d2
a3
b3
d3
(2.19)
D
2.2.3.3 Cramer’s Rule untuk n persamaan dengan n peubah Terdapat sistem persamaan linear simultan: ⎡ a11 ⎢ M ⎢ ⎢⎣a n1
a12
M an2
L a1n ⎤ ⎡ x1 ⎤ ⎡ d1 ⎤ O M ⎥⎥ ⎢⎢ M ⎥⎥ = ⎢⎢ M ⎥⎥ L a nn ⎥⎦ ⎢⎣ x n ⎥⎦ ⎢⎣d n ⎥⎦
(2.20)
dengan determinan: a11 D≡ M a n1
a12 M
L a1n O
M
a n 2 L a nn
(2.21)
20 Jika d = 0, maka persamaan akan mempunyai jawaban yang tidak dapat diturunkan hanya jika D = 0. Jika d ≠ 0 dan D = 0, maka persamaan tidak mempunyai jawaban unik. Selain itu (d ≠ 0 dan D ≠ 0), hitung:
a11 L a1( k −1)
Dk ≡ M O M a n1 L a n ( k −1)
d1
a1( k +1)
L a1n
M dn
M
O M L a nn
a n ( k +1)
(2.22)
Kemudian hitung x k = Dk / D untuk 1 ≤ k ≤ n .
2.2.4 Gauss-Jacobi Method Metode Gauss-Jacobi adalah salah satu metode menyelesaikan persamaan matriks pada matriks yang tidak mempunyai nilai nol pada diagonal utamanya (Bronshtein dan Semendyayev, 1997, P. 892). Setiap elemen diagonal dihitung, dan nilai pendekatan tersebut dimasukkan. Proses tersebut diiterasi hingga mencapai konvergen. Metode ini dinamakan oleh Carl Gustav Jacob Jacobi (1804-1851), seorang matematikawan berkebangsaan Jerman. Metode Gauss-Jacobi dapat dengan mudah didapat dengan cara memeriksa satu per satu dari n persamaan dalam sistem persamaan linear simultan Ax = b. Dalam persamaan ke-i: n
∑a j =1
ij
x j = bi
, i = 1, K , n
(2.23)
Kemudian menghitung nilai xi dengan menganggap nilai x awal telah ditentukan:
21 n
bi − ∑ aij x (jk ) j =1
x
( k +1) i
j ≠i
=
(2.24)
aii
Rumus tersebut yang disebut metode Gauss-Jacobi. Matriks yang dapat dikerjakan dengan metode Gauss-Jacobi harus merupakan matriks dominan diagonal. Dalam kondisi matriks, definisi dari metode Gauss-Jacobi dapat diekspresikan sebagai:
x ( k +1) = D −1 ( L + U ) x ( k ) + D −1b ⎡a11 ⎢0 ⎢ D=⎢ M ⎢ ⎢0 ⎢⎣ 0
(2.25)
M 0
O M L a n −1,n −1
0
L
0
0 ⎤ 0 ⎥⎥ M ⎥ ⎥ 0 ⎥ a nn ⎥⎦
0
L
0
0
L
0
M O − a n −1, 2 L
M 0
L
0
a 22 L
0
0
⎡ 0 ⎢ −a 21 ⎢ L=⎢ M ⎢ ⎢− a n −1,1 ⎢ − a n1 ⎣
⎡0 − a12 ⎢0 0 ⎢ U = ⎢M M ⎢ 0 ⎢0 ⎢⎣0 0
− an2
L − a n ,n −1
L − a1,n −1 L − a 2,n −1 O M 0 L L 0
0⎤ 0⎥⎥ M⎥ ⎥ 0⎥ 0⎥⎦
− a1n ⎤ − a 2 n ⎥⎥ M ⎥ ⎥ − a n −1,n ⎥ 0 ⎥⎦
Dimana matriks D, -L, dan -U masing-masing mewakili diagonal utama, diagonal segitiga bawah, dan diagonal segitiga atas dari suatu matriks A dengan persamaan Ax = b dan jumlah iterasi sebanyak k.
22 Rumusan (2.24) diiterasikan hingga mencapai keadaan konvergen. Cara untuk menentukan keadaan konvergen metode Gauss-Jacobi adalah jika semua nilai xi( k +1) dikurang xi(k ) mencapai selisih yang telah ditentukan. Mengurangi xi( k +1) dengan xi(k ) , menghasilkan:
ei( k +1) =
−1 n aij e (jk ) , ∑ aii j =1
i = 1, K , n
(2.26)
j ≠i
Dengan e k = x − x (k ) . Dalam bentuk matriks:
e ( k +1) = Me ( k ) , ⎡ ⎢ 0 ⎢ ⎢ a 21 ⎢ a 22 ⎢ M = −⎢ M ⎢ ⎢ ⎢ ⎢ a n1 ⎢⎣ a nn
k≥0
a12 a11
(2.27)
L
0 O 0 L
a n ,n −1 a nn
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ a n −1,n −1 ⎥ ⎥ 0 ⎥ ⎥⎦ a1n a11 a2n a 22 M a n −1,n
(2.28)
Dari (2.24), diperoleh: e ( k ) = M k e ( 0) ,
k ≥0
(2.29)
Untuk nilai x ( 0) yang telah ditentukan, kita mendapatkan x ( m ) → x jika dan hanya jika:
rσ (M ) < 1
(2.30)
Hal ini dapat dipenuhi jika M < 1 untuk beberapa aturan operator
matriks.
23 Kasus 1 : M n
∑a j =1 j ≠i
ij
< 1 . Hal ini berarti:
∞
< aii ,
i = 1, K , n
(2.31)
Dapat dikatakan bahwa matriks A pada persamaan (2.23) merupakan dominan secara diagonal. Dalam kasus ini: x − x ( k +1)
∞
≤ M
Kasus 2 : M n
aij
∑a i =1
1
∞
x − x (k )
∞
k≥0
,
(2.32)
< 1 . Hal ini berarti:
<1,
j = 1, K , n
(2.33)
ii
Dalam kasus ini: x − x ( k +1)
1
≤ M
1
x − x (k )
1
,
k≥0
(2.34)
2.2.5 Conjugate Gradient Method Dalam matematika, metode Conjugate Gradient merupakan suatu algoritma untuk solusi numerik dari beberapa sistem khusus persamaan linier yang mempunyai matriks yang simetris dan nilai elemennya positif berhingga. Metode Conjugate Gradient merupakan suatu metode iterasi. Metode ini dikembangkan pada tahun 1952 oleh Hestenes dan Stiefel. Metode Conjugate Gradient digunakan untuk menyelesaikan masalah minimalisasi kuadratik: f (x ) =
1 T x Qx − x T b , 2
x ∈ Rn
(2.35)
24 Atau secara ekuivalen untuk menyelesaikan sistem persamaan linier Qx − b = 0 , dimana Q merupakan matriks positif berhingga simetris n × n dan b
merupakan vector n. Algoritma ini membutuhkan iterasi, dimulai dari nilai awal x0 yang telah ditentukan (umumnya nilai x0 yang dipakai adalah 0).
Berikut ini merupakan langkah-langkah dalam algoritma Conjugate Gradient: 1. Ditentukan k = 0 dan tentukan nilai awal x ( 0) . 2. g ( 0) = ∇f ( x ( 0) ) .
(2.36)
Jika g ( 0) = 0 , maka iterasi berhenti. Selain itu, d ( 0 ) = − g ( 0 ) . 3. α k = −
g ( k )T d ( k ) . d ( k )T Qd ( k )
(2.37) (2.38)
4. x ( k +1) = x ( k ) + α k d ( k ) .
(2.39)
5. g ( k +1) = ∇f ( x ( k +1) ) .
(2.40)
Jika g ( k +1) = 0 , maka iterasi berhenti. Selain itu, lanjutkan ke langkah berikutnya. g ( k +1)T Qd ( k ) . 6. β k = ( k )T d Qd ( k )
(2.41)
7. d ( k +1) = − g ( k +1) + β k d ( k ) .
(2.42)
8. k = k + 1 . Kemudian lanjutkan ke langkah 3.
25
2.3
Penelitian Relevan Penelitian-penelitian
yang
pernah
dilakukan
peneliti
lain
dan
berhubungan dengan penelitian yang terkait dengan penulisan skripsi ini adalah sebagai berikut:
•
An Introduction To The Conjugate Gradient Method Without The Agonizing 1 Pain Edition 1 , 1994, Jonathan Richard Shewchuk. Membahas Conjugate 4 Gradient Method secara mendetail.
•
On The Modified Conjugate Gradient Method In Cloth Simulation, 1998, Uri M. Ascher, Eddy Boxerman. Menggunakan algoritma Modified Preconditioned Conjugate Gradient (MPCG) untuk simulasi pembuatan pakaian.
