BAB 2 TINJAUAN PUSTAKA

BAB 2 TINJAUAN PUSTAKA

2.1 Optimasi Non-Linier Suatu permasalahan optimasi disebut nonlinier jika fungsi tujuan dan kendalanya mempunyai bentuk nonlinier pada salah satu atau keduanya. Optimasi nonlinier ditinjau dari pandangan matematis merupakan topik lanjutan dan secara konseptual, sulit untuk diselesaikan. Untuk itu dibutuhkan pengetahuan aktif mengenai kalkulus, differensial dan aljabar linier (He, 2003). Kesulitan lain yang dihadapi, yaitu fungsi tujuan nonlinier, yang tidak mempunyai nilai minimum serta mempunyai daerah penyelesaian dengan batas nonlinier (tidak konvex). Secara umum tidak terdapat teknik penyelesaian yang terbaik, tetapi ada beberapa teknik yang mempunyai masa depan cerah dibandingkan yang lain. Banyak teknik penyelesaian optimasi nonlinier yang hanya efisien untuk menyelesaikan masalah yang mempunyai struktur matematis tertentu. Hampir semua teknik optimasi nonlinier modern mengandalkan pada algoritma numerik untuk mendapatkan jawabannya (Mohan dan Kannan, 2004). Beberapa permasalahan optimasi nonlinier diantaranya: 1. Optimasi satu variabel tanpa kendala 2. Optimasi multivariabel tanpa kendala 3. Optimasi multivariabel dengan kendala persamaan 4. Optimasi multivariabel dengan kendala pertidaksamaan Beberapa algoritma telah diajukan untuk menyelesaikan program taklinier. Di bawah ini disampaikan beberapa algoritma tersebut sebagai suatu kajian literatur.

5 Universitas Sumatera Utara

6 2.2 Metode Newton-Raphson Dalam analisis numerik, metode Newton (juga dikenal dengan metode NewtonRaphson), merupakan suatu metode yang cukup dikenal untuk mencari pendekatan terhadap akar fungsi rill. Metode Newton-Raphson sering konvergen dengan cepat, terutama bila iterasi dimulai cukup dekat dengan akar yang diinginkan. Namum bila iterasi dimulai jauh dari akar yang dicari, metode ini dapat meleset tanpa peringatan. Implementasi metode ini biasanya mendeteksi dan mengatasi kegagalan konvergensi. 2.2.1 Gagasan awal metode newton-Raphson Gagasan awal metode Newton-Raphson adalah metode yang digunakan untuk mencari akar dari sebuah fungsi rill. Metode ini dimulai dengan memperkirakan satu titik awal dan mendekatinya dengan memperlihatkan slope atau gradien pada titik tersebut. Diharapkan dari titik awal tersebut akan diperoleh pendekatan terhadap akar fungsi yang dimaksud.

Gambar 2.1 Metode newton-Raphson Jika terkaan awal pada akar adalah xi , sebuah garis singgung dapat ditarik dari titik [xi , (f (xi )]. Titik dimana garis singgung ini memotong sumbu x, menyatakan taksiran akar yang lebih baik. Turunan pertama di xi setara dengan kemiringan: f (xi ) =

f (xi ) − 0 xi − xi+1

Universitas Sumatera Utara

7 Sehingga, titik pendekatan untuk i +1 adalah xi+1 = xi −

f (xi ) f 0 (xi )

dimana i ≥ 0. Algoritma metode Newton-Raphson: 1. Definisikan fungsi f (x) dan f 0 (x) 2. Tentukan toleransi error (e) dan iterasi maksimum (n) 3. Tentukan nilai pendekatan awal x0 4. Hitung f(x0) dan f 0 (x0) 5. Untuk iterasi i = 1, 2, ...,n atau |f(xi )| ≥ e xi+1 = xi − (f (xi )/f 0 (xi )) Hitung f (x0) dan f 0 (x0) 6. Akar persamaan adalah nilai xi terakhir yang diperoleh. Permasalahan pada penggunaan metode Newton-Raphson adalah: 1. Metode ini tidak dapat digunakan ketika pendekatannya berada pada titik ekstrim atau titik puncak karena pada titik ini f 0 (x) = 0, sehingga nilai penyebut dari (f (x)/f 0 (x))f 0 (x) sama dengan nol, secara grafis dapat dilihat sebagai berikut : Bila titik pendekatan berada pada titik puncak, maka titik selanjutnya akan berada di tak berhingga. 2. Metode ini menjadi sulit atau lama mendapat penyelesaian, ketika titik pendekatannya berada diantara dua titik stasioner.


8

Gambar 2.2 Pendekatan pada titik puncak

Gambar 2.3 Pendekatan pada 2 titik puncak Bila titik pendekatan berada pada dua titik puncak, maka akan dapat mengakibatkan hilangnya penyelesaian (divergensi). Hal ini disebabkan titik selanjutnya berada pada salah satu titik puncak atau arah pendekatannya berbeda. Untuk dapat menyelesaikan kedua permasalahan pada metode Newton-Raphson ini, maka metode Newton-Raphson perlu dimodifikasi yaitu: 1. Bila titik pendekatan berada pada titik puncak, maka titik pendekatan tersebut harus digeser sedikit xi = xi + δ, dimana δ adalah konstanta yang di-


9 tentukan. Dengan demikian f 0 (xi ) 6= 0 dan metode Newton-Raphson tetap dapat berjalan. 2. Untuk menghindari titik-titik pendekatan yang berada jauh, ada baiknya metode Newton-Raphson ini didahului oleh metode tabel, sehingga dapat dijamin konvergensinya. 2.2.2 Metode pengali Lagrange Permasalahanpermasalahan nonlinier yang tidak dalam bentuk standar diselesaikan dengan mengubahnya ke dalam bentuk standar. Untuk menyelesaikan permasalahan ini, maka perlu dibentuk fungsi pengali Lagrange. Fungsi pengali Lagrange didefinisikan sebagai L(x1 , x2, ..., xn, λ1 , λ2 , ..., λm) = f (x) −

Pm

i=1

λi gi (x).

Dimana λi = (i = 1, 2, ..., m) adalah tetapan yang disebut pengali Lagrange. Kemudian dibentuk kembali persamaan berikut: δL = 0, δxi δL = 0, δxi

(j = 1, 2, ..., n) L(i = 1, 2, ..., m).

Metode pengali Lagrange ini ekuivalen dengan menggunakan persamaan kendala untuk menghilangkan beberapa variabel x tertentu dari fungsi objektif dan kemudian menyelesaikan persoalan maksimasi tanpa kendala dalam variabel-variabel x yang tersisa. 2.2.3 Vektor gradien dan matriks Hessian Dalam penyelesaian optimasi multivariabel dengan kendala persamaan yang diselesaikan dengan metode Newton-Raphson, terdapat istilah Vektor Gradien dan matriks Hessian. 1. Vektor Gradien Vektor Gradien adalah turunan parsial pertama dari fungsi pengali Lagrange


10 terhadap variable xi dan λi dimana (i = 1, 2, ..., n) dan (j = 1, 2, ..., m). Secara matematis Vektor Gradien dapat dituliskan: δL δL δL δL δL δL OL = , , ..., , , , ..., δx1 δx2 δxn δλ1 δλ2 δλm 2. Matriks Hessian Matriks Hessian adalah turunan parsial kedua dari fungsi pengali Lagrange terhadap variabel xi = (I = 1, 2, ..., n) dilanjutkan dengan turunan parsial terhadap x1 , x2, ..., xn, λ1 , λ2 , ..., λm dan variabel λj (j = 1, 2, ..., m) dilanjutkan dengan turunan parsial terhadap x1, x2, ..., xn, λ1 , λ2 , ..., λm. Matriks Hessian didefinisikan sebagai:  HL =

δ2 L δx1 δx1  δ2 L  δxn δx1  δ2 L  δλ1δx1 δ2 L δλm δx1

δ2 L δx1 δx2 δ2 L δxn δx2 δ2 L δλ1 δx2 δ2 L δλm δx2

··· ··· ··· ···

δ2 L δx1 δxn δ2 L δxn δxn δ2 L δλ1 δxn δ2 L δλm δxn

δ2 L δx1 δλ1 δ2 L δxnδλ1 δ2 L δλ1 δλ1 δ2 L δλm δλ1

δ2 L δx1 δλ2 δ2 L δxn δλ2 δ2 L δλ1 δλ2 δ2 L δλm δλ2

··· ··· ··· ···

δ2 L δx1 δλm δ2 L δxn δλm δ2 L δλ1 δλm δ2 L δλm δλm

    

2.3 Kondisi Karush-Kuhn Tucker Tabel 2.1 Kondisi Karush-Kuhn Tucker Persoalan Satu variabel tidak berkendala

Kondisi Perlu Untuk Optimalitas df =0 dx

Juga Cukup Jika f (x) konkaf

Banyak variabel tidak berkendala

df dxj

Berkendala, hanya kendala nonnegatif

df dxj

= 0 (j = 1, 2, ..., n) f (x) konkaf atau ≤ 0 jika xj = 0

Persoalan umum berkendala

Kondisi Karush-Kuhn Tucker

= 0 (j = 1, 2, ..., n) f (x) konkaf

f(x) konkaf dan gi (x) konveks (i = 0,1, ...,m)

Dari tabel 2.1 terlihat bahwa untuk kondisi persoalan umum disebut kondisi KarushKuhn Tucker (Hillier dan Lieberman, 2005).

Kondisi perlu dan cukup untuk

x ¯ = (¯ x1 , x ¯ 2, ..., x ¯ n) sebagai solusi optimal untuk persoalan nonlinear berikut: max (or min) f(x1 , x2, ..., xn)


11 Subject to : g1 (x1 , x2, ..., xn) ≤ b1 g1 (x1, x2 , ..., xn) ≤ bm . Untuk menggunakan hasil, semua kendala persoalan nonlinear harus kendalakendala dalam bentuk h(x1, x2, ..., xn) ≥ b harus ditulis sebagai h(x1 , x2, ..., xn) ≤ b harus diganti dengan h(x1 , x2, ..., xn) ≤ b dan −h(x1, x2 , ..., xn) ≤ −b (Winston dan Venkataramanan, 2003). Teorema 2.1 memberikan kondisi Kuhn-Tucker yang ¯2 , ..., x ¯ n) untuk memecahkan persoalan nonlinear. cukup bagi titik x ¯ = (¯ x1 , x Teorema 2.1 Andaikan persoalan nonlinear adalah persoalan maksimisasi. Jika x ¯ = (¯ x1 , x ¯ 2, ..., x ¯ n) adalah solusi optimal dari persoalan tersebut maka x ¯ = (¯ x1 , x ¯2, ..., x ¯n ) yang memenuhi δf(¯ x) X ¯ δgi (¯ x) − ≤ 0 (j = 1, 2, ..., n) λi δxj δx j i=1 i=m

"

¯ i [bi − gi (¯ λ x)] = 0 (j = 1, 2, ..., n) # i=m X δf δg ¯ i i = 0 (j = 1, 2, ..., n) − λ δxj δxj i=1 ¯i ≤ 0 λ

(j = 1, 2, ..., 3)

Teorema 2.2 Andaikan persoalan nonlinear adalah persoalan minimisasi. Jika ¯ 2, ..., x ¯ n) adalah solusi optimal dari persoalan tersebut maka harus memex ¯ = (¯ x1 , x ¯ 2 , ..., ¯λm yang memenuhi: ¯1, λ nuhi m kendala dan harus ada pengali λ x) δf(¯ x) X ¯ δgi (¯ − ≥ 0 (j = 1, 2, ..., n) λi δxj δx j i=1 i=m

"

¯ i [bi − gi (¯ λ x)] = 0 (j = 1, 2, ..., n) # i=m X δf δg ¯ i i = 0 (j = 1, 2, ..., n) − λ δxj δxj i=1 ¯i ≤ 0 λ

(j = 1, 2, ..., 3)

Skalar λi , I = 1, ..., m disebut kondisi complementary slackness yang menyatakan dua kemungkinan yaitu:


12 1. Jika gi (x) < 0 maka λi = 0 2. Jika λi < 0 maka gi (x) = 0 2.4 Metode Biseksi Kelebihan Metode Biseksi adalah selalu berhasil menemukan akar (solusi) yang dicari, atau dengan kata lain selalu konvergen. Sedangkan kekurangan metode biseksi adalah: 1. Metode biseksi hanya dapat dilakukan apabila ada akar persamaan pada interval yang diberikan. 2. Jika ada beberapa akar pada interval yang diberikan maka hanya satu akar saja yang dapat ditemukan. 3. Memiliki proses iterasi yang banyak sehingga memperlama proses penyelesaian. Tidak memandang bahwa sebenarnya akar atau solusi yang dicari dekat sekali dengan batas interval yang digunakan. 2.5 Metode Scant Kelebihan metode scant adalah: 1. Dapat digunakan untuk mencari akar-akar persamaan dari persamaan polinomial kompleks, atau persamaan yang turunan pertamanya sangat sulit didapatkan. 2. Laju konvergen cepat. 3. Cukup satu terkaan awal. Sedangkan kekurangan metode secant adalah: 1. Turunan harus di cari secara analitis. 2. Bisa divergen.


BAB 2 TINJAUAN PUSTAKA

Recommend Documents