PUSTAKA
Optimasi Numerik Materi Kuliah: Pengantar; Optimasi Satu Variabel; Optimasi Banyak Variabel
James B. Riggs, 1988, “An Introduction to Numerical Methods for Chemical Engineers”, Texas: Texas Tech University Press, Chapter 6
Steven C. Chapra & Raymond P. Canale, 2003, “Numerical Methods for Engineers: With Software and Programming Applications”, 4th edition, New York: McGraw-Hill Company Inc, Part Four
etc.
by: siti diyar kholisoh dy/Analisis Numerik JURUSAN TEKNIK KIMIA – FTI - UPN “VETERAN” YOGYAKARTA
INTRODUCTORY EXAMPLE
OBJECTIVES
Understand why and where optimization occurs in engineering problem solving.
Understand the major elements of the general optimization problem: (1) objective function, (2) decision variables, and (3) constraints.
Be able to distinguish between linear and nonlinear optimization, and between constrained and unconstrained problems.
Persoalan pemilihan diameter pipa untuk mengangkut fluida dari satu proses ke proses yang lain. Diameter pipa optimum, berdasarkan: Biaya investasi, dan biaya operasi $ / year Cost components Operating costs
Pipe diameter (in) 1
1,25
1,5
2
2,5
4697
660
312
164
56
Pipe capital costs
168
308
389
474
660
Pump capital costs
401
192
150
150
150
Total
5266 1160
852
788
866
Diameter pipa mana yang akan Anda pilih?
1
Definisi dan Jenis Optimasi
PENGANTAR-1
Definisi optimasi
Jenis optimasi: 1- maksimasi; 2- minimasi
Dua hal penting dalam studi optimasi: 1- fungsi objektif dan decision variables; 2- kendala (constraints)
Contoh-contoh persoalan optimasi dalam bidang engineering Contoh-contoh constraints yang menyertai persoalan optimasi
Optimasi merupakan suatu proses untuk mencari kondisi yang optimum, dalam arti paling menguntungkan. Optimasi bisa berupa maksimasi atau minimasi. Jika berkaitan dengan masalah keuntungan, maka keadaan optimum adalah keadaan yang memberikan keuntungan maksimum (maksimasi). Jika berkaitan dengan masalah pengeluaran/pengorbanan, maka keadaan optimum adalah keadaan yang memberikan pengeluaran/pengorbanan minimum (minimasi).
Fungsi Objektif Secara umum, fungsi yang akan dimaksimumkan atau diminimumkan disebut fungsi objektif (objective function), sedangkan harga-harga yang berpengaruh dan bisa dipilih disebut variabel (perubah) atau decision variable. Secara analitik, nilai maksimum atau minimum dari suatu persamaan: y = f(x) dapat diperoleh pada harga x yang memenuhi:
Contoh Persoalan Optimasi dalam Bidang Engineering
y’ = f’(x) = 0
Untuk fungsi yang sulit untuk diturunkan atau mempunyai turunan yang sulit dicari akarnya, proses optimasi dapat dilakukan secara numerik.
Design pump and heat transfer equipment for maximum efficiency Design waste water treatment system to meet water-quality standards of least cost Optimal planning and scheduling Optimal pipeline network Inventory control Maintenance planning to minimize cost etc.
2
Contoh Constraints yang Menyertai Persoalan Optimasi
Maximum process temperature Maximum flow rate limitation Maximum conversion limitation Product purity Strength of materials Environmental factor Safety consideration Availability of utilities Corrosion considerations Availability and characteristics of feed stocks Market demand for the product Space limitation An upper limit on the capital investment
PENGANTAR-3 Maksimum dan minimum lokal dan global:
PENGANTAR-2 Ilustrasi maksimasi (secara grafik): Beberapa istilah: Maksimum lokal Maksimum global A unimodal function One hump or one valley Catatan: Analog, untuk kasus minimasi
PENGANTAR-4 Perbedaan antara persoalan optimasi dengan pencarian/ penentuan akar persamaan:
3
PENGANTAR-5 Ilustrasi grafik optimasi dua variabel:
OPTIMASI SATU VARIABEL Tinjaulah sebuah fungsi dengan satu variabel sbb.: y = f(x) Ingin dicari harga x yang memberikan harga y maksimum (maksimasi) atau minimum (minimasi). Dalam hal ini, x yang diperoleh merupakan nilai x optimum fungsi.
Beberapa metode yang akan dibahas:
optimum
METODE GOLDEN SECTION Golden section merupakan salah satu cara atau metode optimasi numerik yang bisa dipakai untuk fungsi yang bersifat unimodal. Kedua tipe optimasi, yaitu maksimasi dan minimasi dapat diselesaikan dengan cara ini. Golden-section (search) method merupakan metode optimasi satu variabel yang sederhana, dan mempunyai pendekatan yang mirip dengan metode bisection dalam penentuan akar persamaan tak linier.
Metode golden section Metode Newton Metode interpolasi kuadrat dsb.
METODE GOLDEN SECTION Tinjaulah fungsi f(x) yang akan ditentukan maksimumnya, pada rentang x = xl dan x = xu (perhatikan gambar di samping). Mirip dengan bisection, ide dasar metode ini adalah memanfaatkan nilai yang lama sebagai nilai yang baru. Secara matematik:
l1 l2 = l0 l1
4
ALGORITMA (kasus maksimasi):
METODE GOLDEN SECTION Karena:
l0 = l1 + l2
maka:
l1 l = 2 l1 + l2 l1
Ambil kebalikannya dan kemudian definisikan:
l1 + l2 l1 = l1 l2 sehingga:
atau:
l l 1+ 2 = 1 l1 l2
R=
1 atau: 1 + R = R
l2 l1
R2 + R −1 = 0
Nilai akar positifnya:
2. Tentukan nilai x1 dan x2 di dalam rentang xl dan xu, sesuai dengan golden ratio (R)
d= (R biasa disebut sebagai
5 −1 R= = 0,61803... golden ratio atau golden number) 2
ALGORITMA (kasus maksimasi): 3. Berdasarkan harga f(x) pada 2 titik tersebut (x1 dan x2), diharapkan ada sebagian interval yang dapat dieliminasi, sehingga salah satu titik lama bisa dipakai lagi pada evaluasi langkah berikutnya. Jadi hanya diperlukan 1 titik baru. Ada 2 kasus: (a) Jika: f(x1) > f(x2) Maka: domain x antara xl dan x2 dieliminasi x2 lama = xl baru x1 lama = x2 baru xu lama = xu baru x1 baru Æ ditentukan
1. Mulai dari 2 nilai tebakan awal xl dan xu, yang mengapit titik maksimum.
(b) Jika: f(x2) > f(x1) Maka: domain x antara x1 dan xu dieliminasi x1 lama = xu baru x2 lama = x1 baru xl lama = xl baru x2 baru Æ ditentukan
5 −1 ( xu − xl ) 2
x1 = xl + d x2 = xu − d
METODE GOLDEN SECTION Algoritma untuk kasus minimasiÆ kebalikan dari algoritma untuk kasus maksimasi tersebut di atas
Efektivitas evaluasi dengan metode golden section: Misal diinginkan pengecilan interval sampai menjadi 0,001 dari semula, maka jumlah step yang diperlukan (N) adalah:
(0,618) N = 0,001 N = 14,3 ≈ 15 Jumlah evaluasi = 2 + (N – 1) x 1 = 16 Silakan pelajari contoh soal #1…!
5
METODE NEWTON
METODE INTERPOLASI KUADRAT
Metode ini menggunakan pendekatan yang sama dengan metode Newton dalam penentuan akar persamaan taklinier, melalui pendefinisian fungsi: g(x) = f’(x) Karena pada kondisi optimum:
f ' ( x*) = g ( x*) = 0 (x* menyatakan nilai x optimum) maka, nilai x* dapat diperoleh secara iteratif sebagai berikut:
xi +1 = xi −
f ' ( xi ) f ' ' ( xi )
Metode ini dapat digunakan untuk melakukan optimasi secara numerik. Hal ini disebabkan oleh penggunaan polinomial orde-dua yang menghasilkan pendekatan cukup baik terhadap bentuk f(x) di dekat titik optimumnya. (Perhatikan gambar di samping…)
Silakan pelajari contoh soal #2…!
METODE INTERPOLASI KUADRAT
OPTIMASI BANYAK VARIABEL
Jika mula-mula kita mempunyai tiga buah titik tebakan awal (yakni x0, x1, dan x2) yang mengapit titik optimumnya, maka sebuah parabola dapat di-fit-kan melalui ketiganya.
Misal diketahui sebuah fungsi dengan banyak variabel sbb:
Diferensiasikan persamaan yang diperoleh, set hasilnya menjadi sama dengan nol, dan perkiraan x optimum dapat ditentukan (dalam hal ini sebagai x3) sbb.:
Ingin dicari harga x1, x2, x3, ….., xn yang memberikan harga y maksimum (maksimasi) atau minimum (minimasi).
2
2
2
2
2
2
f ( x0 ) ( x1 − x2 ) + f ( x1 ) ( x2 − x0 ) + f ( x2 ) ( x0 − x1 ) x3 = 2 f ( x0 ) ( x1 − x2 ) + 2 f ( x1 ) ( x2 − x0 ) + 2 f ( x2 ) ( x0 − x1 ) Penentuan x3 dilakukan secara iteratif, melalui strategi yang sama dengan metode golden section, hingga diperoleh penyelesaian yang konvergen. Silakan pelajari contoh soal #3…!
y = f(x1, x2, x3, ….., xn)
Pengelompokan metodenya secara garis besar: (1) nongradient methods, dan (2) gradient methods
Beberapa metode yang akan dibahas:
Metode Hooke-Jeeves Metode langsung/ random search Metode steepest ascent (ascending)/ descent (descending)
6
METODE HOOKE-JEEVES Prinsip metode Hooke-Jeeves: (1) Eksplorasi nilai ∆xi (2) Mengulangi langkah sukses Optimasi dengan cara Hooke-Jeeves ditunjukkan dalam contoh berikut. Misal ingin dilakukan minimasi dari suatu fungsi: y = (x1 – 4)2 + 0,5.(x2 – 9)2 + 3 Sebagai cek, dengan mudah dapat terlihat bahwa minimum terjadi pada x1 = 4, x2 = 9, dan harga ymin = 3. Dipakai cara Hooke-Jeeves dengan titik awal x1 = 1, x2 = 16, serta interval awal Δx1 = 1 dan Δx2 = 2.
Eksplorasi dengan Δx1 = 0,2, Δx2 = 0,4
HOOKEJEEVES-3
X1
x2
y
Komentar
1
16
36,5
Basis
HOOKEJEEVES-2
Eksplorasi dengan Δx1 = 1, Δx2 =2 2
16
31,5
Sukses
2
18
47,5
Gagal
14
19,5
Sukses
2
Hasil perhitungan:
Mengulangi langkah sukses 3
12
8,5
Sukses
4
10
3,5
Sukses
5
8
4,5
Gagal
Eksplorasi dengan Δx1 = 1, Δx2 =2 5
10
4,5
Gagal
3
10
4,5
Gagal
4
12
7,5
Gagal
4
8
3,5
Gagal
HOOKE-JEEVES-4
4,2
10
3,54
Gagal
3,8
10
3,54
Gagal
Eksplorasi dengan Δx1 = 0,04, Δx2 = 0,08
4
10,4
4,96
Gagal
4,04
9,6
3,18
Sukses
4
Mengulangi langkah sukses 4
9,2
3,02
Sukses
4
8,8
3,02
Gagal
Eksplorasi dengan Δx1 = 0,2, Δx2 = 0,4 4,2
9,2
3,06
Gagal
3,8
9,2
3,06
Gagal
4,0
9,6
3,18
Gagal
4,0
8,8
3,02
Gagal
9,2
3,021
Gagal
3,96
9,2
3,021
Gagal
4,00
9,28
3,039
Gagal
9,12
3,007
Sukses
4,00
Mengulangi langkah sukses 4,00
9,04
3,0008
Sukses
4,00
8,96
3,0008
Gagal
Proses dihentikan setelah eksplorasi gagal, serta Δx1 dan Δx2 cukup kecil.
7
METODE LANGSUNG (RANDOM SEARCH)
Sesuai dengan namanya, metode ini secara berulangulang mengevaluasi nilai fungsi pada nilai-nilai variabel bebas tertentu (selected values) secara acak. Jika banyaknya sampel yang dicoba mencukupi, maka kondisi optimumnya akan teramati. Æ tidak efisien…! Metode ini dapat diterapkan untuk fungsi yang discontinuous dan non-differentiable sekalipun.
Pendekatan ini pada umumnya akan menghasilkan titik optimum global (bukan optimum lokal) Silakan pelajari contoh soal #5…!
PENCARIAN OPTIMUM f(x,y) h2
Titik optimum h1
h0
•2
1• y0
Merupakan jenis metode gradien yang paling sederhana.
Terminologi: steepest ascent Æ untuk pencarian maksimum fungsi steepest descent Æ untuk pencarian minimum fungsi Prinsip pencarian optimum: Dilakukan serangkaian proses transformasi untuk mengubah sebuah fungsi dengan banyak variabel (multidimensional function) menjadi sebuah fungsi dengan variabel tunggal (one-dimensional function), berdasarkan gradien arah pencarian. Langkah pencarian optimum ini
selanjutnya dilakukan secara berulang-ulang (iteratif).
Secara Numerik:
y
Berdasarkan nilai awal x = x0 & y = y0, dapat ditentukan nilai gradien (atau arah steepest ascent)-nya, yakni sebesar h0.
Sebagai ilustrasi, tinjaulah fungsi 2 variabel f(x,y) yang akan ditentukan titik maksimumnya. (lihat gambar di samping)
METODE STEEPEST ASCENT/DESCENT
Misal, untuk sebuah fungsi 2 variabel: f(x,y) yang akan dicari titik optimumnya, dengan nilai awal: x = x0 dan y = y0 Pada langkah iterasi pertama, nilai x dan y yang baru dapat ditentukan dengan:
x = x0 +
•0 x0
x
Berdasarkan h0, nilai maksimum fungsi dapat ditentukan, yakni pada titik “1”. Demikian seterusnya, proses ini dilakukan berulang-ulang hingga diperoleh titik optimum sesungguhnya.
∂f ∂x
h x0 , y 0
dan
y = y0 +
∂f ∂y
h x0 , y 0
8
∂f ∂x
dan
∂f ∂y
merupakan turunan parsial fungsi f(x,y) terhadap x dan y
Dalam hal ini, vektor gradien fungsinya dinyatakan sbg:
∇f =
∂f ∂f i+ j ∂x ∂y
Pada kasus ini, sebuah fungsi 2 variabel dalam x dan y, f(x,y), ditransformasikan menjadi sebuah fungsi satu variabel dalam h, g(h).
Contoh Aplikasi:
LOKASI OPTIMUM PENGOLAH LIMBAH TERPADU Sejumlah N pabrik dengan posisi koordinat masing-masing (xi,yi) menghasilkan limbah masing-masing sejumlah Qi. Akan dibangun suatu unit pengolah limbah terpadu untuk seluruh pabrik tersebut. Ongkos pengangkutan limbah dari pabrik ke unit pengolah limbah berbanding lurus dengan debit pangkat 0,6. Ingin ditentukan posisi (koordinat) unit pengolah limbah agar ongkos pengangkutan limbah minimum.
Analisis:
H arg a = k .( jarak )( . debit )
0,6
Misal: Lokasi pengolah limbah berada di titik P (xP, yP)
Nilai x dan y yang diperoleh pada langkah iterasi ini selanjutnya menjadi x0 dan y0 pada langkah iterasi berikutnya. Demikian seterusnya.
Jarak pabrik (xi,yi) ke lokasi pengolah limbah: di =
(x P
− x i )2 + (y P − y i )2
Ongkos transport dari pabrik (xi, yi):
Silakan pelajari contoh soal #4…!
Ongkos transport total: CT =
OPTIMASI FUNGSI 2 VARIABEL SECARA ANALITIK
N
∑ Ci
(sebuah perbandingan)
i =1
N
∑ Q i0 ,6 (x P f (x P , y P )
=k
=
i =1
− x i )2 + (y P − y i )2
Tinjaulah sebuah fungsi 2 variabel: f(x,y) Kriteria optimumnya dapat dibagi menjadi 3 kategori: f(x,y) mempunyai minimum lokal: ∂ 2f jika det(H) > 0 dan >0 2
Dicari nilai xP dan yP yang memberikan nilai CT minimum. Misal: y i xi yi Qi (3,7) 1 1 4 20 2 2 1 30 (1,4) 3 3 7 25 (8,3) 4 8 3 80 Dimisalkan pula: nilai k = 1
Ci = k .Qi0 ,6 . (x P − x i )2 + (y P − yi )2
∂x
f(x,y) mempunyai maksimum lokal: ∂ 2f <0 jika det(H) > 0 dan 2
∂x
(2,1) x
f(x,y) mempunyai titik belok (saddle point): jika det(H) < 0 ∂2 f det(H) merupakan nilai ∂x 2 determinan matriks Hessian yang det( H ) = 2 dinyatakan sebagai: ∂ f ∂y∂x
∂2 f ∂x∂y ∂2 f ∂y 2
9
