Optimasi Non-Linier
Pendahuluan Suatu permasalahan optimasi disebut nonlinier jika fungsi tujuan dan kendalanya
mempunyai bentuk nonlinier pada salah satu atau keduanya, contohnya adalah sebagai berikut:
Metode Optimasi Analitis
Satu Variabel tanpa Kendala Multi Variabel Tanpa Kendala Multi Variabel dengan Kendala Persamaan Multi Variabel dengan Kendala Pertidak-samaan
Metode Optimasi Numerik Satu Dimensi Teknik Eliminasi Teknik Pendekatan
Satu variable tanpa kendala (1) Dimisalkan x adalah variabel penentu dan f(x) adalah fungsi tujuan
dari suatu masalah. Metode optimasi menyelesaikan masalah: maksimalka n f(x) minimumkan f(x) atau x x
Untuk menyelesaikan permasalahan seperti tertera di atas
digunakan kalkulus diferensial yang dinyatakan seperti di bawah ini: Misalkan f adalah fungsi yang menerus dalam interval tertutup [a,b] dan dapat diderivasikan pada interval terbuka (a,b). (i) Jika f’(x) > 0 untuk seluruh x dalam (a,b), maka f adalah menanjak pada
[a,b]. (ii) Jika f’(x) < 0 untuk seluruh x dalam (a,b), maka f adalah menurun pada [a,b].
Satu variable tanpa kendala (2) Test derivasi pertama: Misalkan f adalah fungsi yang menerus
dalam interval tertutup [a,b] dan dapat diderivasikan pada interval terbuka (a,b) kecuali mungkin di titik c yang berada didalam (a,b). (i) Jika f’(x) > 0 untuk a < x < c dan f’(x) < 0 untuk c < x < b,
maka f(c) adalah sebuah maximum lokal dari f. (ii) Jika f’(x) < 0 untuk a < x < c dan f’(x) > 0 untuk c < x < b, maka f(c) adalah sebuah minimum lokal dari f. (iii) Jika f’(x) < 0 atau f’(x) > 0 untuk setiap x dalam (a,b) kecuali x = c, maka f(c) BUKAN sebuah nilai ekstrim.
Satu variable tanpa kendala (3) Test derivasi kedua: Misalkan f adalah fungsi yang dapat
diderivasikan pada interval terbuka yang berisi titik c dan f’(c) = 0, (i) Jika f ”(c) < 0, maka f(c) adalah sebuah maximum lokal dari f. (ii) Jika f ”(c) > 0, maka f(c) adalah sebuah minimum lokal dari f.
Satu variable tanpa kendala (4) Contoh 1:
Sebuah perusahaan catering (makanan ringan yang menyediakan konsumsi untuk suatu penataran di JTE FT UMY berusaha mengurangi pengeluaran untuk keperluan pembungkus. Bungkus tersebut terbuat dari kertas karton seperti tampak pada Gambar di samping. Keempat pojoknya akan dipotong segi empat samasisi sedemikian rupa sehingga volumenya menjadi maksimum.
Solusi
Ilustrasi Grafis
Satu variable tanpa kendala (5) Dari contoh di atas tampak bahwa dengan cara analitis
kalkulus diferensial nilai x yang memberikan nilai f maximum dapat dicari tanpa mengetahui nilai dari f itu sendiri. Untuk melengkapi teorema optimasi nonlinier satu variabel yang telah dijelaskan di atas disajikan teorema yang dapat digunakan untuk menentukan titik-titik ekstrem dari suatu fungsi satu variabel. Teorema: Misalkan f’(c) = f ”(c) = … = f(n-1)(c) = 0, tetapi f(n)(c) ≠ 0. Maka
f(c) adalah:
(i) nilai minimum dari f(x), jika f(n)(c) > 0 dan n adalah bilangan genap, (ii) nilai maximum dari f(x), jika f(n) (c) < 0 dan n adalah bilangan genap, (iii) bukan minimum dan maximum jika n adalah bilangan gasal.
Satu variable tanpa kendala (6) Contoh 2.
Tentukan maximum dan minimum dari fungsi di bawah ini f ( x) 12 x5 45x 4 40 x3 5
Penyelesaian:
Tugas UK3 Buat makalah Non Linier Programing: Max dan Min Tanpa dan Dengan Kendala Untuk Beberapa Variabel
Multi variable tanpa kendala (1) Cara analitis yang diterapkan pada permasalahan optimasi
satu variabel dapat pula diterapkan kepada permasalahan multi variabel. Secara umum teknik yang digunakan pada optimasi satu dimensi
dapat digunakan dalam optimasi multi variabel. Definisi dan simbol-simbol yang digunakan: (i ) f ( x1 , x2 ,..., xn ) akan ditulis sebagai f ( X ) dengan X {x1 , x2 ,..., xn } (ii ) f ( X * ) f ( x1* , x2* ,..., xn* ) (iii ) f ( X * )
f ( x1* , x2* ,..., xn* ) untuk j 1,2,..., n x j
f f f (iv) f ( X ) C setara dengan , ,..., {c1 , c2 ,..., cn } x x x 2 n 1 *
Multi variable tanpa kendala (2) Teorema: Jika f(X) mempunyai sebuah titik ekstrem (minimum
maupun maximum) pada X = X* dan jika derivasi pertama dari f(X) mempunyai nilai pada titik X*, maka ∇f(X*) = 0 PERHATIAN: Kebalikannya belum tentu benar yaitu jika ∇f(X*) = 0 maka X* adalah titik ekstrem.
Multi variable tanpa kendala (3) Teorema: Titik X* disebut titik maksimum lokal dari f(X) jika dan
hanya jika: (i) ∇f(X*) = 0 (ii) H(X*) < 0 definit negatif dengan H = matrik Hessian yang
didefinisikan sebagai: h11 h1n 2 f H dengan hij xi x j hn1 hnn H adalah definit negatif jika dan hanya jika (1) j H 0 untuk j 1,2,..., n j
dengan h11 h1 j H det j
h j1 h jj
Multi variable tanpa kendala (4) Teorema: Titik X* disebut titik minimum lokal dari f(X) jika dan
hanya jika: (i) ∇f(X*) = 0 (ii) H(X*) > 0 definit positif atau |H|j > 0 untuk j = 1,2,…,n
Multi variable tanpa kendala (5) Syarat Maksimum lokal
Syarat Minimum lokal
Multi variable tanpa kendala (6) Contoh 3: Tentukan titik-titik ekstrim dari fungsi:
f ( x1 , x2 ) x13 x23 2 x12 4 x22 6
Variabel dengan Kendala= (Pengali Lagrange)
Multi variable dengan Kendala Persamaan Pada bagian ini akan didiskusikan teknik optimasi multi
variabel dengan kendala persamaan yang mempunyai bentuk umum sebagai berikut: Min/Maks f f ( X ) Kendala g j ( X ) 0, dengan j 1,2,..., m dengan X {x1 , x2 ,..., xn }t
disini m ≤ n, jika terjadi bahwa m > n, maka biasanya tidak dapat
diselesaikan Untuk menyelesaikan permasalahan optimasi di atas, digunakan metode pengali Lagrange, yaitu: m
L( X , ) f ( X ) j g j ( X ) j 1
Multi variable dengan Kendala Persamaan Teorema: Syarat perlu bagi sebuah fungsi f(X) dengan kendala gj(X) = 0,
dengan j = 1, 2, …, m agar mempunyai minimum relatif pada titik X* adalah derivasi parsial pertama dari fungsi Lagrangenya yang didefinisikan sebagai L = L(x1,x2,…,xn, λ1,λ2,…,λn) terhadap setiap argumennya mempunyai nilai nol.
Teorema: Syarat harus bagi sebuah fungsi f(X) agar mempunyai minimum (atau
maximum) relatif pada titik X* adalah jika fungsi kuadrat, Q, yang didefinisikan sebagai 2L Q dxi dx j i 1 j 1 xi x j n
m
dievaluasi pada X = X* harus definit positif (atau negatif) untuk setiap nilai dX yang memenuhi semua kendala.
Multi variable dengan Kendala Persamaan Syarat perlu agar
2L Q dxi dx j i 1 j 1 xi x j n
m
menjadi definit positif (atau negatif) untuk setiap variasi nilai dX adalah setiap akar dari polinomial, zi, yang didapat dari determinan persamaan di bawah ini harus positif (atau negatif). ( L11 z ) L12 L21 ( L22 z ) Ln1 Ln 2
L13 L23 Ln 3
L1n g11 L2 n g12 ( Lnm z ) g m1
g m1 g 2n g mn
g11 g 21
g12 g 22
g13 g 23
g1n g 2n
0 0
0 0
g m1
gm2
g m3
g mn
0
0
2 L( X * , ) dengan Lij , xi x j 0
g i ( X * ) dan g ij x j
Sumber: Buku Pengantar Optimasi Non-Linier Ir. Djoko Luknanto, M.Sc., Ph.D.
